C metaprogramming: BSD's sys/tree.h red-black trees
2022-11-28 00:00:00 +0000 UTCPart of a series of posts about metaprogramming in C:
- C metaprogramming: type-generic lists and queues using sys/queue.h
- C metaprogramming: BSD’s
sys/tree.hred-black trees (you are here)
BSD-flavored Unixes include a library similar to the more universal sys/queue.h called sys/tree.h. This standalone header file provides two tree implementations: splay trees and red-black trees.
Red-black trees are a type of self-balancing binary search tree with worst-case O(log n) performance on search, inserts and deletes. In this post I will share a very simple associative array implementation using the sys/tree.h red-black trees and discuss some of the metaprogramming techniques used to create the library.
RB_ENTRY and RB_HEAD: creating the node and head types
Similarly to sys/queue.h a red-black tree node and head structure can be defined as in this snippet:
struct node {
RB_ENTRY(node) entry;
int key, val;
};
RB_HEAD(int_assoc, node);
The expanded macros result in this C code:
struct node {
struct {
struct node *rbe_left;
struct node *rbe_right;
struct node *rbe_parent;
int rbe_color;
} entry;
int key, val;
};
struct int_assoc {
struct node *rbh_root;
};
Nothing too unusual here. Note that the head structure has only one field – a root node. The entry structure added to the node type contains pointers to the children and parent node, allowing total traversal of the tree from any given node.
Also note the field rbe_color – this flag is used to implement the red-black self-balancing algorithms.
Since the tree is a binary search tree, how is the sort order determined? This is where sys/tree.h becomes more interesting.
RB_PROTOTYPE and RB_GENERATE: draw the rest of the owl
The RB_PROTOTYPE and RB_GENERATE macros do some heavy lifting. Before we dive in, we need a strcmp-style function for our tree nodes. Here is ours, providing a total sort order on our associative array entries:
int keycmp(struct node* e1, struct node* e2) {
return (e1->key < e2->key ? -1 : e1->key > e2->key);
}
Simple enough – sort the array based on its keys. How does the tree implementation make use of this function? We invoke the RB_PROTOTYPE and RB_GENERATE macros like this:
RB_PROTOTYPE(int_assoc, node, entry, keycmp)
RB_GENERATE(int_assoc, node, entry, keycmp)
The macros accept the arguments in this order:
RB_PROTOTYPE(head_struct_name, type_struct_name, RB_ENTRY_field_name, comparison_function)
These macros generate a significant amount of code. In my expanded intermediate file, roughly 431 lines. The RB_PROTOTYPE macro is responsible for these 9 lines:
void int_assoc_RB_INSERT_COLOR(struct int_assoc *, struct node *);
void int_assoc_RB_REMOVE_COLOR(struct int_assoc *, struct node *, struct node *);
struct node *int_assoc_RB_REMOVE(struct int_assoc *, struct node *);
/* ... omitted ... */
This macro does what it says on the tin – generates function prototypes for the red-black tree operations. Here are the relevant macro definitions:
#define RB_PROTOTYPE(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
/* ... omitted ... */
Note one odd construct–the double hash ##. This stands for the preprocessor concatenation operation documented here. This operation allows concatenating the identifier, symbol, or other text provided as a macro argument with an identifier or other text in the expanded macro. So here, our head structure’s name is concatenated to the beginning of each function prototype as we saw in the intermediate code above.
The remaining 422 lines are generated by the RB_GENERATE macro. This macro generates the function implementations for operations on red-black trees.
Where does our keycmp function come in? Let’s look at some generated code:
struct node * int_assoc_RB_FIND(struct int_assoc *head, struct node *elm) {
struct node *tmp = (head)->rbh_root;
int comp;
while (tmp) {
comp = keycmp(elm, tmp);
if (comp < 0) tmp = (tmp)->entry.rbe_left;
else if (comp > 0) tmp = (tmp)->entry.rbe_right;
else return (tmp);
}
return (
((void *)0)
);
}
The above code defines the internal find function on our red-black tree. The keycmp identifier for our function has been substituted in by the macro RB_GENERATE. The arguments elm and tmp are both of the appropriate type struct node*. Note the name node was also passed to RB_GENERATE as an argument. Here is the responsible snippet of the RB_GENERATE macro:
/* our invocation was: RB_GENERATE(int_assoc, node, entry, keycmp) */
#define RB_GENERATE(name, type, field, cmp) \
RB_GENERATE_INTERNAL(name, type, field, cmp,)
#define RB_GENERATE_STATIC(name, type, field, cmp) \
RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
/* ... some lines omitted ... */
/* Finds the node with the same key as elm */ \
attr struct type * \
name##_RB_FIND(struct name *head, struct type *elm) \
{ \
struct type *tmp = RB_ROOT(head); \
int comp; \
while (tmp) { \
comp = cmp(elm, tmp); \
if (comp < 0) \
tmp = RB_LEFT(tmp, field); \
else if (comp > 0) \
tmp = RB_RIGHT(tmp, field); \
else \
return (tmp); \
} \
return (NULL); \
} \
At first glance, this is simple enough. The name parameter is our head type, substituted into both the identifier for this generated function and for the type declaration of the head function argument. The type parameter is our node type, substituted in for the type declaration of the iterator variable and the second function argument. field was expanded into our tree entry structure field name entry. Finally cmp was expanded into the identifier for our comparison function keycmp.
But notice something else. The macro definition includes references to the macros RB_ROOT, RB_LEFT, and RB_RIGHT. In our generated code, these macros are also expanded. That is, the C preprocessor expands macros called within other macros. There are some nuances as outlined in the Macro Pitfalls section of the GCC manual.
Implementing associative array operations
The red-black tree functions can now be invoked by helper macros like RB_INSERT(head_struct_name, head_ptr, inserted_node_ptr). Here’s an example implementing the insert operation on our simple int->int associative array:
int int_assoc_insert(struct int_assoc* head, int key, int value) {
struct node* n = malloc(sizeof(struct node));
if (n == NULL) return 1;
n->key = key;
n->val = value;
if (RB_INSERT(int_assoc, head, n) == NULL) return 0;
/* means we had a duplicate */
return 1;
}
And here is the definition of RB_INSERT:
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
The concatenation operator ## is used here again to construct the identifier for the appropriate generated function int_assoc_RB_INSERT.
Similarly easy definitions for an associative array update and get operation are enabled by these helper macros.
Conclusion
Metaprogramming through the C preprocessor enables the BSD sys/tree.h library to offer a convenient, easy to understand API for creating all types of red-black trees storing arbitrary underlying structures. Macros again show their utility in simplifying the implementation of complex data structure operations – like the involved red-black tree insert and remove operations.
This red-black tree implementation is a shining example of the time and effort saved by metaprogrammed data structures in C. For example, the Wikipedia article on red-black trees lists 6 cases for both insertion and deletion of a node! These are not simple to implement over and over again.
It is easy to forget that the C preprocessor can be a relatively blunt instrument. Unlike in a language with higher-order types or some other mechanism for reasoning about types, there is nothing inherent to C or the preprocessor to stop you from providing nonsense arguments or subtly broken arguments to a macro like RB_INSERT. Language servers like clangd can give you hints about the proper use of macros, but this isn’t a silver bullet in my experience.
The code of the example associative array implementation and a lightly modified version of OpenBSD’s sys/tree.h are available here.