rbtree: implement a "threaded LLRB tree"

Change the left-leaning red-black (LLRB) trees into left-leaning
threaded red-black trees. Instead of NULL pointers at leaf nodes, use
the otherwise unused field as a pointer to the lexical predecessor
(left) or successor (right). This allows fast previous/next
interator operation without needing to keep track of the root of the
tree at all times.

The additional metadata that needs to be kept can be done for "free"
simply by changing "bool red" into a flag field.

Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>

0 files changed, 0 insertions, 0 deletions