"A tree from OpenBSD"

Red-Black Tree is a popular data structure. But it is not in the libc.

From the OpenBSD, there is a tree.h which define a SPLAY tree and a Red-Black Tree.

It don't need any other things. It is use by many projects.

OpenBSD Apple NodeJS

Define a tree

struct xxx {
    int key;
    int val;
    RB_ENTRY(xxx) node;
};


int mycomp(struct xxx* a, struct xxx* b)
{
    if (a->key > b-> key) {
        return 1;
    }
    if (a->key == b-> key) {
        return 0;
    }
    if (a->key < b-> key) {
        return -1;
    }
}

RB_HEAD(xtree_t, xxx);
RB_GENERATE_STATIC(xtree_t, xxx, node, mycomp);

It is a little like STL of C++, the RB_HEAD will generate the type of the tree xtree_t.

The RB_GENERATE_STATIC will generate several static functions to operate the tree.

There are also a RB_GENERATE which generate generial functions

Note: The name of compare function must be not defined as comp. Becasue in the functions generated by the Macro, there is a int named comp. So if the name is same, there will be problems

Using the tree

    struct xtree_t tt;
    RB_INIT(&tt);
    int i = 0;
    for (i = 0; i < 10000; i++) {
        struct xxx* p = (struct xxx*)malloc(sizeof(struct xxx));
        p->key = i;
        p->val = i * 10;
        RB_INSERT(xtree_t, &tt, p);
    }

    for (i = 0; i < 10000; i++) {
        struct xxx key;
        key.key = i;
        struct xxx* p = NULL;
        p = RB_FIND(xtree_t, &tt, &key);
        printf("find %d\n", p->val);
    }

    struct xxx* x = NULL;
    struct xxx* y = NULL;
    RB_FOREACH_SAFE(x, xtree_t, &tt, y)  {
        RB_REMOVE(xtree_t, &tt, x);
        if (NULL != x) {
            free(x);
            x = NULL;
        }
    }

In the tree.h there is a SPLAY_TREE too. The way to use it is simlar to the RB_TREE