rb3ptr is a 3-pointer red-black tree implementation in C. I created it initially in 2017 when I wanted to implement Fortune's Algorithm, which never happened because I got stuck in the quest to make the best Red-black tree ever :-). In 2019 I added augmentation and did some cleanups and improvements to be able to use it in a text editor project, where it is now underlying a text rope data structure.
rb3ptr might see further development as part of that editor project, but I decided to give it its own repository. Balancing search trees are non-trivial to code, and rb3ptr seems to have reached a pretty functional state and it has developped a flexible API.If you are used to C++'s std::map or similar data structures, then rb3ptr might turn out to be not as easy to use as expected. It has an idiomatic C interface. But that's ok. rb3ptr has different design goals:
1) It doesn't hide any implementation details - you can write custom iteration code, or use different comparison functions to drive a search, or have trees whose nodes don't even have any defined ordering except their positional relationship in the tree. These features are required for some algorithms. The text rope implementation that I did for my text editor could definitely not be done with std::map.
2) rb3ptr also supports augmentation. To augment a tree means computing and caching per-node information that is the result of a node's data as well as its childs' augmented data. For example, one might cache in each node the total weight of that node's subtree (i.e. the sum of a certain attribute over all the subtree's nodes). Augmentation must be explicitly supported by a tree implementation because the computed data must be updated in all the affected nodes after insertions or deletions (consider rebalancing rotations!)
3) rb3ptr is an intrusively linked tree, which means that it does not allocate any memory when you "insert" a node. In fact it never allocates any memory. The user simply embeds a node link structure into the actual payload (data), and the tree implementation is completely agnostic about the actual data stored "in the node". Instead, if you need to search an item, you make a function that converts a pointer to the embedded link structure into a pointer to the actual data structure, and then you can do whatever you want to do with that data pointer (e.g. compare two nodes' "keys").
rb3ptr is probably similar to the implementation in the linux kernel source tree, but unlike that, it is readily usable as part of any other project.
In 2017, I wrote a blog post about some of rb3ptr's implementation details.
Page created: 2019-08-13
Updated: 2019-11-21