Red-black tree C implementation
Based on Julienne Walker's http://eternallyconfuzzled.com/ red-black tree implementation.
Usage
First, grab the source into your project, you'll need just those two:
wget https://raw.github.com/mirek/rb_tree/master/rb_tree.h
wget https://raw.github.com/mirek/rb_tree/master/rb_tree.c
Let's say you want to store struct iovec objects (defined in sys/uio.h) with the following definition:
struct iovec {
void *iov_base; // [XSI] Base address of I/O memory region
size_t iov_len; // [XSI] Size of region iov_base points to
};
You'll need to provide comparison callback for your object. Let's say you want to keep track of the length of the iovec buffers, your callback should look similar to:
int
my_cmp_cb (struct rb_tree *self, struct rb_node *node_a, struct rb_node *node_b) {
struct iovec *a = (struct iovec *) node_a->value;
struct iovec *b = (struct iovec *) node_b->value;
return (a->iov_len > b->iov_len) - (a->iov_len < b->iov_len);
}
To create your red-black tree:
struct rb_tree *tree = rb_tree_create(my_cmp_cb);
if (tree) {
// Use the tree here...
for (int i = 0; i < 10; i++) {
struct iovec *v = malloc(sizeof *v);
v->iov_base = (void *) i;
v->iov_len = i * i;
// Default insert, which allocates internal rb_nodes for you.
rb_tree_insert(tree, v);
}
// To f
struct iovec *f = rb_tree_find(tree, & (struct iovec) { .iov_base = (void *) 7, .iov_len = 0 });
if (r) {
fprintf(stdout, "found iovec(.iov_base = %p, .iov_len = %zu)\n", f->iov_base, f->iov_len)
} else {
printf("not found\n");
}
// Dealloc call can take optional parameter to notify on each node
// being deleted so you can free the node and/or your object:
rb_tree_dealloc(tree, NULL);
}
Above example will leak because malloc is not balanced with free.
If you want to iterate over elements (here in reverse order):
struct rb_iter *iter = rb_iter_create();
if (iter) {
for (struct iovec *v = rb_iter_last(iter, tree); v; v = rb_iter_prev(iter)) {
printf("- %p %zu\n", v->iov_base, v->iov_len);
}
rb_iter_dealloc(iter);
}
License
None (Public Domain).