rb3ptr - Red-black tree implemenation

rb3ptr is an implementation of a 3-pointer red-black tree (written in C) that I worked on in 2017, and then again in 2019 as part of a text editor project. It currently lives as part of that text editor where it's likely to get further improvements. Nevertheless, since I think that balancing search trees are non-trivial to code, and since rb3ptr seems to have reached a pretty functional state and has a solid API, I'm putting a snapshot version of the code here, so it can be a thing on its own.

Here are the files, extracted from my project astedit as of 2019-08-13: rb3ptr.c rb3ptr.h

Note that rb3ptr has an idiomatic C interface. It's not as "easy" to use as for example std::map in C++. But that's ok, since it has completely 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! And these things are not just nice to have, but actually necessary for many 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