FreeBSD - Tree macro tutorial

BSD systems include macros for several useful structures and algorithms, including several types of lists and trees. While the lists are easy to use, I always forget the right order of declarations for trees. So here it is, how to use tree macros in FreeBSD (C language):

First, declare the structure that is to be stored in the tree:

    struct mydata {
        RB_ENTRY(mydata) linkage;
        int payload;
    };

Second, declare the comparison function. This function compares two structures in the way similar to strcmp():

    static int mydata_cmp(struct mydata *e1, struct mydata *e2) {
        return e2->payload - e1->payload;
    }

Next, declare the head structure and head entry. Head structure is the struct type of the tree head, and it's the way tree is accessed.

    RB_HEAD(mydata_entries, mydata) head = RB_INITIALIZER(&head);

You're now ready to declare the prototypes for the internal tree structures and the functions themselves:

    RB_PROTOTYPE(mydata_entries, mydata, linkage, mydata_cmp);
    RB_GENERATE(mydata_entries, mydata, linkage, mydata_cmp);

The tree can now be used normally, the way described in the manual:

    struct mydata *data;
    RB_INSERT(mydata_entries, &head, data);

    struct mydata find;
    find.payload = 42;
    data = RB_FIND(mydata_entries, &head, &find);

    RB_FOREACH(data, mydata_entries, &head)
        printf("%d\n", data->payload);

In the examples above:

mydata is the structure to be stored in the tree. It contains some arbitrary payload data but must contain an TREE_ENTRY element.
mydata_entries is the type that contains the tree. It's declared by the RB_HEAD macro.
head is the tree head.

Subpages

Misc. links