../

Living on the BSD Trees

2022-08-17

Both FreeBSD and OpenBSD systems come with a very useful Red-Black tree and Splay tree implementation.

This implementation is header-only, requires no external dependencies, and is generic. Therefore, using it on Linux is also quite simple.

Getting the Header File

Run:

curl https://raw.githubusercontent.com/openbsd/src/master/sys/sys/tree.h -o tree.h

This header file includes sys/_null.h, a file that does not exist in Linux. However, since tree.h uses this file only to define NULL, changing it to stdlib.h works just fine.

// #include <sys/_null.h>
#include <stdlib.h>

Declaration

The trees in the tree.h header file are actually implemented entirely as macros, so they need to be expanded before use. For example, if you want the value type in the tree to be double, create a new header file named double_tree.h and declare it as follows:

#ifndef DOUBLE_TREE_H_
#define DOUBLE_TREE_H_

#include "tree.h"

struct double_treenode {
    RB_ENTRY(double_treenode) entry;
    double val;
};

int double_cmp(struct double_treenode *e1, struct double_treenode *e2);

RB_HEAD(double_tree, double_treenode);
RB_PROTOTYPE(double_tree, double_treenode, entry, double_cmp)

#endif

Definition

Then create the source file double_tree.c and add the necessary function definitions:

#include "double_tree.h"

int double_cmp(struct double_treenode *e1, struct double_treenode *e2); {
    if (e1->val < e2->val) {
        return -1;
    } else if (e1->val > e2->val) {
        return 1;
    }
    return 0;
}

RB_GENERATE(double_tree, double_treenode, entry, double_cmp)

Usage

Here is how to use this double_tree.

Initialization

Create the tree and initialize it:

RB_HEAD(double_tree, double_treenode) head;
RB_INIT(&head);

Initialization can also be done in one line:

RB_HEAD(double_tree, double_treenode) head = RB_INITIALIZER(&head);

Insertion

struct double_treenode *n;
double data[5] = {1.0, 2.0, 3.0, 4.0, 5.0};
for (int i = 0; i < 5; i++) {
    n = malloc(sizeof(struct double_treenode));
    n->val = data[i];
    RB_INSERT(double_tree, &head, n);
}

Find and Remove

struct double_treenode find;
find.val = 3.0

struct double_treenode *iter;
iter = RB_FIND(double_tree, &head, &find);

if (iter != NULL) {
    printf("Found\n");
    RB_REMOVE(double_tree, &head, iter);
    free(iter);
}

Traversal

RB_FOREACH(iter, double_tree, &head) {
    // Do something on iter->val
    ...
}

Actually, RB_FOREACH(iter, double_tree, &head) is essentially:

for (iter = RB_MIN(double_tree, &head);
        iter != NULL;
        iter = RB_NEXT(double_tree, &head, iter))

You can use RB_MIN to get the minimum node in the tree; RB_NEXT to get the next element after iter; and RB_MAX for the maximum node.

If you want to traverse the tree in a different order, you can use RB_LEFT and RB_RIGHT. For example, printing the tree using pre-order traversal:

void
print_tree(struct double_treenode *n)
{
    struct double_treenode *left, *right;

    if (n == NULL) {
        printf("nil");
        return;
    }
    left = RB_LEFT(n, entry);
    right = RB_RIGHT(n, entry);
    if (left == NULL && right == NULL)
        printf("%d", n->val);
    else {
        printf("%d(", n->val);
        print_tree(left);
        printf(",");
        print_tree(right);
        printf(")");
    }
}

Others

There is something very strange: Arch Linux includes the man page for tree.h (visible by running man 3 tree), but the header file itself cannot be found.

This article only covers Red-Black trees, but Splay trees are actually quite similar, so I won’t repeat the details here. You can refer directly to the documentation.

Errata

Thanks to @w3cing for the reminder. The RB_TREE provided in FreeBSD’s tree.h is actually not a Red-Black tree. “RB” stands for Rank-Balanced tree, and the specific implementation is a weak AVL tree. FreeBSD made a modification to tree.h in August 2020.

Mistivia - https://mistivia.com