rb.h -- Red-black tree implementation

rb.h implements left-leaning red-black trees as C preprocessor macros, and is used extensively in jemalloc. Similar implementations predate this one, such as OpenBSD's sys/tree.h and my own obsolete rb.h. However, those implementations require approximately four pointer-size fields per node (left child, right child, parent, color), whereas this one requires only two (left child, right child + color). The only notable disadvantage is that insertion/removal are ~2X slower, due to using a single pass algorithm rather than lazy node fixup. For more discussion, see this blog post.

For those concerned about correctness and performance, a test program and benchmark program are available. Comparable benchmark programs are also available for sys/tree.h and for my old rb.h.

Last updated Wednesday 2007/08/08 12:11:15 (PDT)