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 key;
        int value;
    };
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->key - e1->key;
    }
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.key = 42;
    data = RB_FIND(mydata_entries, &head, &find);

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

In the examples above:

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