Page MenuHomeFreeBSD
Files F6736930

treetest.c
dougm (Doug Moore)
Actions

Authored By
dougm
Jun 18 2020, 3:49 AM
Size
1 KB
Referenced Files
None
Subscribers
None

treetest.c
View Options

#include <stdlib.h>
#define RB_AUGMENT(entry) augment(entry)
//#include <sys/tree.h>
#include <stdint.h>
#if 0
#include "freebsd/src/sys/sys/tag.tree.h"
#else
#include "freebsd/src/sys/sys/tree.h"
#endif
struct item {
RB_ENTRY(item) it_entry;
int val;
int sum;
};
static void
augment(struct item *it)
{
struct item *child;
int sum;
sum = it->val;
if ((child = RB_LEFT(it, it_entry)) != NULL)
sum += child->sum;
if ((child = RB_RIGHT(it, it_entry)) != NULL)
sum += child->sum;
it->sum = sum;
}
static int
item_cmp(struct item *a, struct item *b)
{
return a->val < b->val ? -1 : a->val > b->val;
}
RB_HEAD(item_tree, item) tree = RB_INITIALIZER(&tree);
RB_GENERATE_STATIC(item_tree, item, it_entry, item_cmp);
#include <stdio.h>
void tree_print(struct item *it, int depth)
{
struct item *p = it; //RB_PTR(it, it_entry);
if (p != NULL) {
int red = RB_COLOR(it, it_entry); // RB_ISRED(it);
if (!red)
depth += 8;
tree_print(RB_RIGHT(p, it_entry), depth);
printf("%*c%d:%d\n", depth + (red?4:0),
(red ? 'R' : 'B'), p->val, p->sum);
tree_print(RB_LEFT(p, it_entry), depth);
}
}
int main()
{
for (;;) {
int val;
#if 1
scanf("%d", &val);
#else
val = random() % 199999 - 9999;
#endif
if (val > 0) {
struct item it;
it.val = val;
struct item *it2 = RB_FIND(item_tree, &tree, &it);
if (!it2) {
struct item *it3 = malloc(sizeof(*it3));
it3->val = val;
RB_INSERT(item_tree, &tree, it3);
}
} else if (val < 0) {
struct item it;
it.val = -val;
struct item *it2 = RB_FIND(item_tree, &tree, &it);
if (it2) {
RB_REMOVE(item_tree, &tree, it2);
free(it2);
}
}
printf("===\n");
tree_print(RB_ROOT(&tree), 0);
printf("===\n");
}
}

File Metadata

Mime Type
text/x-c
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
2627339
Default Alt Text
treetest.c (1 KB)

Event Timeline