New upstream version 1.16.0 upstream/1.16.0

3 files changed, 1588 insertions, 0 deletions

diff --git a/shared/c-rbtree/src/c-rbtree-private.h b/shared/c-rbtree/src/c-rbtree-private.h
new file mode 100644
index 00000000..25b9ba01
--- /dev/null
+++ b/shared/c-rbtree/src/c-rbtree-private.h
@@ -0,0 +1,40 @@
+#pragma once
+
+/*
+ * Private definitions
+ * This file contains private definitions for the RB-Tree implementation, but
+ * which are used by our test-suite.
+ */
+
+#include <stddef.h>
+#include "c-rbtree.h"
+
+/*
+ * Macros
+ */
+
+#define _public_ __attribute__((__visibility__("default")))
+
+/*
+ * Nodes
+ */
+
+static inline void *c_rbnode_raw(CRBNode *n) {
+        return (void *)(n->__parent_and_flags & ~C_RBNODE_FLAG_MASK);
+}
+
+static inline unsigned long c_rbnode_flags(CRBNode *n) {
+        return n->__parent_and_flags & C_RBNODE_FLAG_MASK;
+}
+
+static inline _Bool c_rbnode_is_red(CRBNode *n) {
+        return c_rbnode_flags(n) & C_RBNODE_RED;
+}
+
+static inline _Bool c_rbnode_is_black(CRBNode *n) {
+        return !(c_rbnode_flags(n) & C_RBNODE_RED);
+}
+
+static inline _Bool c_rbnode_is_root(CRBNode *n) {
+        return c_rbnode_flags(n) & C_RBNODE_ROOT;
+}
diff --git a/shared/c-rbtree/src/c-rbtree.c b/shared/c-rbtree/src/c-rbtree.c
new file mode 100644
index 00000000..f58db849
--- /dev/null
+++ b/shared/c-rbtree/src/c-rbtree.c
@@ -0,0 +1,1118 @@
+/*
+ * RB-Tree Implementation
+ * This implements the insertion/removal of elements in RB-Trees. You're highly
+ * recommended to have an RB-Tree documentation at hand when reading this. Both
+ * insertion and removal can be split into a handful of situations that can
+ * occur. Those situations are enumerated as "Case 1" to "Case n" here, and
+ * follow closely the cases described in most RB-Tree documentations. This file
+ * does not explain why it is enough to handle just those cases, nor does it
+ * provide a proof of correctness. Dig out your algorithm 101 handbook if
+ * you're interested.
+ *
+ * This implementation is *not* straightforward. Usually, a handful of
+ * rotation, reparent, swap and link helpers can be used to implement the
+ * rebalance operations. However, those often perform unnecessary writes.
+ * Therefore, this implementation hard-codes all the operations. You're highly
+ * recommended to look at the two basic helpers before reading the code:
+ *     c_rbnode_swap_child()
+ *     c_rbnode_set_parent_and_flags()
+ * Those are the only helpers used, hence, you should really know what they do
+ * before digging into the code.
+ *
+ * For a highlevel documentation of the API, see the header file and docbook
+ * comments.
+ */
+
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
+
+#include "c-rbtree-private.h"
+#include "c-rbtree.h"
+
+/*
+ * We use alignas(8) to enforce 64bit alignment of structure fields. This is
+ * according to ISO-C11, so we rely on the compiler to implement this. However,
+ * at the same time we don't want to exceed native malloc() alignment on target
+ * platforms. Hence, we also verify against max_align_t.
+ */
+static_assert(alignof(CRBNode) <= alignof(max_align_t), "Invalid RBNode alignment");
+static_assert(alignof(CRBNode) >= 8, "Invalid CRBNode alignment");
+static_assert(alignof(CRBTree) <= alignof(max_align_t), "Invalid RBTree alignment");
+static_assert(alignof(CRBTree) >= 8, "Invalid CRBTree alignment");
+
+/**
+ * c_rbnode_leftmost() - return leftmost child
+ * @n:          current node, or NULL
+ *
+ * This returns the leftmost child of @n. If @n is NULL, this will return NULL.
+ * In all other cases, this function returns a valid pointer. That is, if @n
+ * does not have any left children, this returns @n.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to leftmost child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_leftmost(CRBNode *n) {
+        if (n)
+                while (n->left)
+                        n = n->left;
+        return n;
+}
+
+/**
+ * c_rbnode_rightmost() - return rightmost child
+ * @n:          current node, or NULL
+ *
+ * This returns the rightmost child of @n. If @n is NULL, this will return
+ * NULL. In all other cases, this function returns a valid pointer. That is, if
+ * @n does not have any right children, this returns @n.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to rightmost child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_rightmost(CRBNode *n) {
+        if (n)
+                while (n->right)
+                        n = n->right;
+        return n;
+}
+
+/**
+ * c_rbnode_leftdeepest() - return left-deepest child
+ * @n:          current node, or NULL
+ *
+ * This returns the left-deepest child of @n. If @n is NULL, this will return
+ * NULL. In all other cases, this function returns a valid pointer. That is, if
+ * @n does not have any children, this returns @n.
+ *
+ * The left-deepest child is defined as the deepest child without any left
+ * (grand-...)siblings.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to left-deepest child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_leftdeepest(CRBNode *n) {
+        if (n) {
+                for (;;) {
+                        if (n->left)
+                                n = n->left;
+                        else if (n->right)
+                                n = n->right;
+                        else
+                                break;
+                }
+        }
+        return n;
+}
+
+/**
+ * c_rbnode_rightdeepest() - return right-deepest child
+ * @n:          current node, or NULL
+ *
+ * This returns the right-deepest child of @n. If @n is NULL, this will return
+ * NULL. In all other cases, this function returns a valid pointer. That is, if
+ * @n does not have any children, this returns @n.
+ *
+ * The right-deepest child is defined as the deepest child without any right
+ * (grand-...)siblings.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to right-deepest child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_rightdeepest(CRBNode *n) {
+        if (n) {
+                for (;;) {
+                        if (n->right)
+                                n = n->right;
+                        else if (n->left)
+                                n = n->left;
+                        else
+                                break;
+                }
+        }
+        return n;
+}
+
+/**
+ * c_rbnode_next() - return next node
+ * @n:          current node, or NULL
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically next node to @n. If @n is NULL, the last node or
+ * unlinked, this returns NULL.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to next node, or NULL.
+ */
+_public_ CRBNode *c_rbnode_next(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+        if (n->right)
+                return c_rbnode_leftmost(n->right);
+
+        while ((p = c_rbnode_parent(n)) && n == p->right)
+                n = p;
+
+        return p;
+}
+
+/**
+ * c_rbnode_prev() - return previous node
+ * @n:          current node, or NULL
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically previous node to @n. If @n is NULL, the first node or
+ * unlinked, this returns NULL.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to previous node, or NULL.
+ */
+_public_ CRBNode *c_rbnode_prev(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+        if (n->left)
+                return c_rbnode_rightmost(n->left);
+
+        while ((p = c_rbnode_parent(n)) && n == p->left)
+                n = p;
+
+        return p;
+}
+
+/**
+ * c_rbnode_next_postorder() - return next node in post-order
+ * @n:          current node, or NULL
+ *
+ * This returns the next node to @n, based on a left-to-right post-order
+ * traversal. If @n is NULL, the root node, or unlinked, this returns NULL.
+ *
+ * This implements a left-to-right post-order traversal: First visit the left
+ * child of a node, then the right, and lastly the node itself. Children are
+ * traversed recursively.
+ *
+ * This function can be used to implement a left-to-right post-order traversal:
+ *
+ *     for (n = c_rbtree_first_postorder(t); n; n = c_rbnode_next_postorder(n))
+ *             visit(n);
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to next node, or NULL.
+ */
+_public_ CRBNode *c_rbnode_next_postorder(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+
+        p = c_rbnode_parent(n);
+        if (p && n == p->left && p->right)
+                return c_rbnode_leftdeepest(p->right);
+
+        return p;
+}
+
+/**
+ * c_rbnode_prev_postorder() - return previous node in post-order
+ * @n:          current node, or NULL
+ *
+ * This returns the previous node to @n, based on a left-to-right post-order
+ * traversal. That is, it is the inverse operation to c_rbnode_next_postorder().
+ * If @n is NULL, the left-deepest node, or unlinked, this returns NULL.
+ *
+ * This function returns the logical previous node in a directed post-order
+ * traversal. That is, it effectively does a pre-order traversal (since a
+ * reverse post-order traversal is a pre-order traversal). This function does
+ * NOT do a right-to-left post-order traversal! In other words, the following
+ * invariant is guaranteed, if c_rbnode_next_postorder(n) is non-NULL:
+ *
+ *     n == c_rbnode_prev_postorder(c_rbnode_next_postorder(n))
+ *
+ * This function can be used to implement a right-to-left pre-order traversal,
+ * using the fact that a reverse post-order traversal is also a valid pre-order
+ * traversal:
+ *
+ *     for (n = c_rbtree_last_postorder(t); n; n = c_rbnode_prev_postorder(n))
+ *             visit(n);
+ *
+ * This would effectively perform a right-to-left pre-order traversal: first
+ * visit a parent, then its right child, then its left child. Both children are
+ * traversed recursively.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to previous node in post-order, or NULL.
+ */
+_public_ CRBNode *c_rbnode_prev_postorder(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+        if (n->right)
+                return n->right;
+        if (n->left)
+                return n->left;
+
+        while ((p = c_rbnode_parent(n))) {
+                if (p->left && n != p->left)
+                        return p->left;
+                n = p;
+        }
+
+        return NULL;
+}
+
+/**
+ * c_rbtree_first() - return first node
+ * @t:          tree to operate on
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically first node in @t. If @t is empty, NULL is returned.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to first node, or NULL.
+ */
+_public_ CRBNode *c_rbtree_first(CRBTree *t) {
+        assert(t);
+        return c_rbnode_leftmost(t->root);
+}
+
+/**
+ * c_rbtree_last() - return last node
+ * @t:          tree to operate on
+ *
+ * An RB-Tree always defines a linear order of its elements. This function
+ * returns the logically last node in @t. If @t is empty, NULL is returned.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to last node, or NULL.
+ */
+_public_ CRBNode *c_rbtree_last(CRBTree *t) {
+        assert(t);
+        return c_rbnode_rightmost(t->root);
+}
+
+/**
+ * c_rbtree_first_postorder() - return first node in post-order
+ * @t:          tree to operate on
+ *
+ * This returns the first node of a left-to-right post-order traversal. That
+ * is, it returns the left-deepest leaf. If the tree is empty, this returns
+ * NULL.
+ *
+ * This can also be interpreted as the last node of a right-to-left pre-order
+ * traversal.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to first node in post-order, or NULL.
+ */
+_public_ CRBNode *c_rbtree_first_postorder(CRBTree *t) {
+        assert(t);
+        return c_rbnode_leftdeepest(t->root);
+}
+
+/**
+ * c_rbtree_last_postorder() - return last node in post-order
+ * @t:          tree to operate on
+ *
+ * This returns the last node of a left-to-right post-order traversal. That is,
+ * it always returns the root node, or NULL if the tree is empty.
+ *
+ * This can also be interpreted as the first node of a right-to-left pre-order
+ * traversal.
+ *
+ * Fixed runtime (n: number of elements in tree): O(1)
+ *
+ * Return: Pointer to last node in post-order, or NULL.
+ */
+_public_ CRBNode *c_rbtree_last_postorder(CRBTree *t) {
+        assert(t);
+        return t->root;
+}
+
+static inline void c_rbtree_store(CRBNode **ptr, CRBNode *addr) {
+        /*
+         * We use volatile accesses whenever we STORE @left or @right members
+         * of a node. This guarantees that any parallel, lockless lookup gets
+         * to see those stores in the correct order, which itself guarantees
+         * that there're no temporary loops during tree rotation.
+         * Note that you still need to properly synchronize your accesses via
+         * seqlocks, rcu, whatever. We just guarantee that you get *some*
+         * result on a lockless traversal and never run into endless loops, or
+         * undefined behavior.
+         */
+        *(volatile CRBNode **)ptr = addr;
+}
+
+/*
+ * Set the flags and parent of a node. This should be treated as a simple
+ * assignment of the 'flags' and 'parent' fields of the node. No other magic is
+ * applied. But since both fields share its backing memory, this helper
+ * function is provided.
+ */
+static inline void c_rbnode_set_parent_and_flags(CRBNode *n, CRBNode *p, unsigned long flags) {
+        n->__parent_and_flags = (unsigned long)p | flags;
+}
+
+/*
+ * Nodes in the tree do not separately store a point to the tree root. That is,
+ * there is no way to access the tree-root in O(1) given an arbitrary node.
+ * Fortunately, this is usually not required. The only situation where this is
+ * needed is when rotating the root-node itself.
+ *
+ * In case of the root node, c_rbnode_parent() returns NULL. We use this fact
+ * to re-use the parent-pointer storage of the root node to point to the
+ * CRBTree root. This way, we can rotate the root-node (or add/remove it)
+ * without requiring a separate tree-root pointer.
+ *
+ * However, to keep the tree-modification functions simple, we hide this detail
+ * whenever possible. This means, c_rbnode_parent() will continue to return
+ * NULL, and tree modifications will boldly reset the pointer to NULL on
+ * rotation. Hence, the only way to retain this pointer is to call
+ * c_rbnode_pop_root() on a possible root-node before rotating. This returns
+ * NULL if the node in question is not the root node. Otherwise, it returns the
+ * tree-root, and clears the pointer/flag from the node in question. This way,
+ * you can perform tree operations as usual. Afterwards, use
+ * c_rbnode_push_root() to restore the root-pointer on any possible new root.
+ */
+static inline CRBTree *c_rbnode_pop_root(CRBNode *n) {
+        CRBTree *t = NULL;
+
+        if (c_rbnode_is_root(n)) {
+                t = c_rbnode_raw(n);
+                n->__parent_and_flags = c_rbnode_flags(n) & ~C_RBNODE_ROOT;
+        }
+
+        return t;
+}
+
+/* counter-part to c_rbnode_pop_root() */
+static inline CRBTree *c_rbnode_push_root(CRBNode *n, CRBTree *t) {
+        if (t) {
+                if (n)
+                        n->__parent_and_flags = (unsigned long)t
+                                                | c_rbnode_flags(n)
+                                                | C_RBNODE_ROOT;
+                c_rbtree_store(&t->root, n);
+        }
+
+        return NULL;
+}
+
+/*
+ * This function partially swaps a child node with another one. That is, this
+ * function changes the parent of @old to point to @new. That is, you use it
+ * when swapping @old with @new, to update the parent's left/right pointer.
+ * This function does *NOT* perform a full swap, nor does it touch any 'parent'
+ * pointer.
+ *
+ * The sole purpose of this function is to shortcut left/right conditionals
+ * like this:
+ *
+ *     if (old == old->parent->left)
+ *             old->parent->left = new;
+ *     else
+ *             old->parent->right = new;
+ *
+ * That's it! If @old is the root node, this will do nothing. The caller must
+ * employ c_rbnode_pop_root() and c_rbnode_push_root().
+ */
+static inline void c_rbnode_swap_child(CRBNode *old, CRBNode *new) {
+        CRBNode *p = c_rbnode_parent(old);
+
+        if (p) {
+                if (p->left == old)
+                        c_rbtree_store(&p->left, new);
+                else
+                        c_rbtree_store(&p->right, new);
+        }
+}
+
+/**
+ * c_rbtree_move() - move tree
+ * @to:         destination tree
+ * @from:       source tree
+ *
+ * This imports the entire tree from @from into @to. @to must be empty! @from
+ * will be empty afterwards.
+ *
+ * Note that this operates in O(1) time. Only the root-entry is updated to
+ * point to the new tree-root.
+ */
+_public_ void c_rbtree_move(CRBTree *to, CRBTree *from) {
+        CRBTree *t;
+
+        assert(!to->root);
+
+        if (from->root) {
+                t = c_rbnode_pop_root(from->root);
+                assert(t == from);
+
+                to->root = from->root;
+                from->root = NULL;
+
+                c_rbnode_push_root(to->root, to);
+        }
+}
+
+static inline void c_rbtree_paint_terminal(CRBNode *n) {
+        CRBNode *p, *g, *gg, *x;
+        CRBTree *t;
+
+        /*
+         * Case 4:
+         * This path assumes @n is red, @p is red, but the uncle is unset or
+         * black. This implies @g exists and is black.
+         *
+         * This case requires up to 2 rotations to restore the tree invariants.
+         * That is, it runs in O(1) time and fully restores the RB-Tree
+         * invariants, all at the cost of performing at mots 2 rotations.
+         */
+
+        p = c_rbnode_parent(n);
+        g = c_rbnode_parent(p);
+        gg = c_rbnode_parent(g);
+
+        assert(c_rbnode_is_red(p));
+        assert(c_rbnode_is_black(g));
+        assert(p == g->left || !g->left || c_rbnode_is_black(g->left));
+        assert(p == g->right || !g->right || c_rbnode_is_black(g->right));
+
+        if (p == g->left) {
+                if (n == p->right) {
+                        /*
+                         * We're the right red child of a red parent, which is
+                         * a left child. Rotate on parent and consider us to be
+                         * the old parent and the old parent to be us, making us
+                         * the left child instead of the right child so we can
+                         * handle it the same as below. Rotating two red nodes
+                         * changes none of the invariants.
+                         */
+                        x = n->left;
+                        c_rbtree_store(&p->right, x);
+                        c_rbtree_store(&n->left, p);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x));
+                        c_rbnode_set_parent_and_flags(p, n, c_rbnode_flags(p));
+                        p = n;
+                }
+
+                /* 'n' is invalid from here on! */
+
+                /*
+                 * We're the red left child of a red parent, black grandparent
+                 * and uncle. Rotate parent on grandparent and switch their
+                 * colors, making the parent black and the grandparent red. The
+                 * root of this subtree was changed from the grandparent to the
+                 * parent, but the color remained black, so the number of black
+                 * nodes on each path stays the same. However, we got rid of
+                 * the double red path as we are still the (red) child of the
+                 * parent, which has now turned black. Note that had we been
+                 * the right child, rather than the left child, we would now be
+                 * the left child of the old grandparent, and we would still
+                 * have a double red path. As the new grandparent remains
+                 * black, we're done.
+                 */
+                x = p->right;
+                t = c_rbnode_pop_root(g);
+                c_rbtree_store(&g->left, x);
+                c_rbtree_store(&p->right, g);
+                c_rbnode_swap_child(g, p);
+                if (x)
+                        c_rbnode_set_parent_and_flags(x, g, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(p, gg, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(g, p, c_rbnode_flags(g) | C_RBNODE_RED);
+                c_rbnode_push_root(p, t);
+        } else /* if (p == g->right) */ { /* same as above, but mirrored */
+                if (n == p->left) {
+                        x = n->right;
+                        c_rbtree_store(&p->left, n->right);
+                        c_rbtree_store(&n->right, p);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x));
+                        c_rbnode_set_parent_and_flags(p, n, c_rbnode_flags(p));
+                        p = n;
+                }
+
+                x = p->left;
+                t = c_rbnode_pop_root(g);
+                c_rbtree_store(&g->right, x);
+                c_rbtree_store(&p->left, g);
+                c_rbnode_swap_child(g, p);
+                if (x)
+                        c_rbnode_set_parent_and_flags(x, g, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(p, gg, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(g, p, c_rbnode_flags(g) | C_RBNODE_RED);
+                c_rbnode_push_root(p, t);
+        }
+}
+
+static inline CRBNode *c_rbtree_paint_path(CRBNode *n) {
+        CRBNode *p, *g, *u;
+
+        for (;;) {
+                p = c_rbnode_parent(n);
+                if (!p) {
+                        /*
+                         * Case 1:
+                         * We reached the root. Mark it black and be done. As
+                         * all leaf-paths share the root, the ratio of black
+                         * nodes on each path stays the same.
+                         */
+                        c_rbnode_set_parent_and_flags(n, c_rbnode_raw(n), c_rbnode_flags(n) & ~C_RBNODE_RED);
+                        return NULL;
+                } else if (c_rbnode_is_black(p)) {
+                        /*
+                         * Case 2:
+                         * The parent is already black. As our node is red, we
+                         * did not change the number of black nodes on any
+                         * path, nor do we have multiple consecutive red nodes.
+                         * There is nothing to be done.
+                         */
+                        return NULL;
+                }
+
+                g = c_rbnode_parent(p);
+                u = (p == g->left) ? g->right : g->left;
+                if (!u || !c_rbnode_is_red(u)) {
+                        /*
+                         * Case 4:
+                         * The parent is red, but its uncle is black. By
+                         * rotating the parent above the uncle, we distribute
+                         * the red nodes and thus restore the tree invariants.
+                         * No recursive fixup will be needed afterwards. Hence,
+                         * just let the caller know about @n and make them do
+                         * the rotations.
+                         */
+                        return n;
+                }
+
+                /*
+                 * Case 3:
+                 * Parent and uncle are both red, and grandparent is black.
+                 * Repaint parent and uncle black, the grandparent red and
+                 * recurse into the grandparent. Note that this is the only
+                 * recursive case. That is, this step restores the tree
+                 * invariants for the sub-tree below @p (including @n), but
+                 * needs to continue the re-coloring two levels up.
+                 */
+                c_rbnode_set_parent_and_flags(p, g, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(u, g, c_rbnode_flags(u) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(g, c_rbnode_raw(g), c_rbnode_flags(g) | C_RBNODE_RED);
+                n = g;
+        }
+}
+
+static inline void c_rbtree_paint(CRBNode *n) {
+        /*
+         * When a new node is inserted into an RB-Tree, we always link it as a
+         * tail-node and paint it red. This way, the node will not violate the
+         * rb-tree invariants regarding the number of black nodes on all paths.
+         *
+         * However, a red node must never have another bordering red-node (ie.,
+         * child or parent). Since the node is newly linked, it does not have
+         * any children. Therefore, all we need to do is fix the path upwards
+         * through all parents until we hit a black parent or can otherwise fix
+         * the coloring.
+         *
+         * This function first walks up the path from @n towards the tree root
+         * (done in c_rbtree_paint_path()). This recolors its parent/uncle, if
+         * possible, until it hits a sub-tree that cannot be fixed via
+         * re-coloring. After c_rbtree_paint_path() returns, there are two
+         * possible outcomes:
+         *
+         *         1) @n is NULL, in which case the tree invariants were
+         *            restored by mere recoloring. Nothing is to be done.
+         *
+         *         2) @n is non-NULL, but points to a red ancestor of the
+         *            original node. In this case we need to restore the tree
+         *            invariants via a simple left or right rotation. This will
+         *            be done by c_rbtree_paint_terminal().
+         *
+         * As a summary, this function runs O(log(n)) re-coloring operations in
+         * the worst case, followed by O(1) rotations as final restoration. The
+         * amortized cost, however, is O(1), since re-coloring only recurses
+         * upwards if it hits a red uncle (which can only happen if a previous
+         * operation terminated its operation on that layer).
+         * While amortized painting of inserted nodes is O(1), finding the
+         * correct spot to link the node (before painting it) still requires a
+         * search in the binary tree in O(log(n)).
+         */
+        n = c_rbtree_paint_path(n);
+        if (n)
+                c_rbtree_paint_terminal(n);
+}
+
+/**
+ * c_rbnode_link() - link node into tree
+ * @p:          parent node to link under
+ * @l:          left/right slot of @p to link at
+ * @n:          node to add
+ *
+ * This links @n into an tree underneath another node. The caller must provide
+ * the exact spot where to link the node. That is, the caller must traverse the
+ * tree based on their search order. Once they hit a leaf where to insert the
+ * node, call this function to link it and rebalance the tree.
+ *
+ * For this to work, the caller must provide a pointer to the parent node. If
+ * the tree might be empty, you must resort to c_rbtree_add().
+ *
+ * In most cases you are better off using c_rbtree_add(). See there for details
+ * how tree-insertion works.
+ */
+_public_ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n) {
+        assert(p);
+        assert(l);
+        assert(n);
+        assert(l == &p->left || l == &p->right);
+
+        c_rbnode_set_parent_and_flags(n, p, C_RBNODE_RED);
+        c_rbtree_store(&n->left, NULL);
+        c_rbtree_store(&n->right, NULL);
+        c_rbtree_store(l, n);
+
+        c_rbtree_paint(n);
+}
+
+/**
+ * c_rbtree_add() - add node to tree
+ * @t:          tree to operate one
+ * @p:          parent node to link under, or NULL
+ * @l:          left/right slot of @p (or root) to link at
+ * @n:          node to add
+ *
+ * This links @n into the tree given as @t. The caller must provide the exact
+ * spot where to link the node. That is, the caller must traverse the tree
+ * based on their search order. Once they hit a leaf where to insert the node,
+ * call this function to link it and rebalance the tree.
+ *
+ * A typical insertion would look like this (@t is your tree, @n is your node):
+ *
+ *        CRBNode **i, *p;
+ *
+ *        i = &t->root;
+ *        p = NULL;
+ *        while (*i) {
+ *                p = *i;
+ *                if (compare(n, *i) < 0)
+ *                        i = &(*i)->left;
+ *                else
+ *                        i = &(*i)->right;
+ *        }
+ *
+ *        c_rbtree_add(t, p, i, n);
+ *
+ * Once the node is linked into the tree, a simple lookup on the same tree can
+ * be coded like this:
+ *
+ *        CRBNode *i;
+ *
+ *        i = t->root;
+ *        while (i) {
+ *                int v = compare(n, i);
+ *                if (v < 0)
+ *                        i = (*i)->left;
+ *                else if (v > 0)
+ *                        i = (*i)->right;
+ *                else
+ *                        break;
+ *        }
+ *
+ * When you add nodes to a tree, the memory contents of the node do not matter.
+ * That is, there is no need to initialize the node via c_rbnode_init().
+ * However, if you relink nodes multiple times during their lifetime, it is
+ * usually very convenient to use c_rbnode_init() and c_rbnode_unlink() (rather
+ * than c_rbnode_unlink_stale()). In those cases, you should validate that a
+ * node is unlinked before you call c_rbtree_add().
+ */
+_public_ void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n) {
+        assert(t);
+        assert(l);
+        assert(n);
+        assert(!p || l == &p->left || l == &p->right);
+        assert(p || l == &t->root);
+
+        c_rbnode_set_parent_and_flags(n, p, C_RBNODE_RED);
+        c_rbtree_store(&n->left, NULL);
+        c_rbtree_store(&n->right, NULL);
+
+        if (p)
+                c_rbtree_store(l, n);
+        else
+                c_rbnode_push_root(n, t);
+
+        c_rbtree_paint(n);
+}
+
+static inline void c_rbnode_rebalance_terminal(CRBNode *p, CRBNode *previous) {
+        CRBNode *s, *x, *y, *g;
+        CRBTree *t;
+
+        if (previous == p->left) {
+                s = p->right;
+                if (c_rbnode_is_red(s)) {
+                        /*
+                         * Case 2:
+                         * We have a red node as sibling. Rotate it onto our
+                         * side so we can later on turn it black. This way, we
+                         * gain the additional black node in our path.
+                         */
+                        t = c_rbnode_pop_root(p);
+                        g = c_rbnode_parent(p);
+                        x = s->left;
+                        c_rbtree_store(&p->right, x);
+                        c_rbtree_store(&s->left, p);
+                        c_rbnode_swap_child(p, s);
+                        c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(s) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) | C_RBNODE_RED);
+                        c_rbnode_push_root(s, t);
+                        s = x;
+                }
+
+                x = s->right;
+                if (!x || c_rbnode_is_black(x)) {
+                        y = s->left;
+                        if (!y || c_rbnode_is_black(y)) {
+                                /*
+                                 * Case 3+4:
+                                 * Our sibling is black and has only black
+                                 * children. Flip it red and turn parent black.
+                                 * This way we gained a black node in our path.
+                                 * Note that the parent must be red, otherwise
+                                 * it must have been handled by our caller.
+                                 */
+                                assert(c_rbnode_is_red(p));
+                                c_rbnode_set_parent_and_flags(s, p, c_rbnode_flags(s) | C_RBNODE_RED);
+                                c_rbnode_set_parent_and_flags(p, c_rbnode_parent(p), c_rbnode_flags(p) & ~C_RBNODE_RED);
+                                return;
+                        }
+
+                        /*
+                         * Case 5:
+                         * Left child of our sibling is red, right one is black.
+                         * Rotate on parent so the right child of our sibling is
+                         * now red, and we can fall through to case 6.
+                         */
+                        x = y->right;
+                        c_rbtree_store(&s->left, y->right);
+                        c_rbtree_store(&y->right, s);
+                        c_rbtree_store(&p->right, y);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        x = s;
+                        s = y;
+                }
+
+                /*
+                 * Case 6:
+                 * The right child of our sibling is red. Rotate left and flip
+                 * colors, which gains us an additional black node in our path,
+                 * that was previously on our sibling.
+                 */
+                t = c_rbnode_pop_root(p);
+                g = c_rbnode_parent(p);
+                y = s->left;
+                c_rbtree_store(&p->right, y);
+                c_rbtree_store(&s->left, p);
+                c_rbnode_swap_child(p, s);
+                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                if (y)
+                        c_rbnode_set_parent_and_flags(y, p, c_rbnode_flags(y));
+                c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(p));
+                c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_push_root(s, t);
+        } else /* if (previous == p->right) */ { /* same as above, but mirrored */
+                s = p->left;
+                if (c_rbnode_is_red(s)) {
+                        t = c_rbnode_pop_root(p);
+                        g = c_rbnode_parent(p);
+                        x = s->right;
+                        c_rbtree_store(&p->left, x);
+                        c_rbtree_store(&s->right, p);
+                        c_rbnode_swap_child(p, s);
+                        c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(s) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) | C_RBNODE_RED);
+                        c_rbnode_push_root(s, t);
+                        s = x;
+                }
+
+                x = s->left;
+                if (!x || c_rbnode_is_black(x)) {
+                        y = s->right;
+                        if (!y || c_rbnode_is_black(y)) {
+                                assert(c_rbnode_is_red(p));
+                                c_rbnode_set_parent_and_flags(s, p, c_rbnode_flags(s) | C_RBNODE_RED);
+                                c_rbnode_set_parent_and_flags(p, c_rbnode_parent(p), c_rbnode_flags(p) & ~C_RBNODE_RED);
+                                return;
+                        }
+
+                        x = y->left;
+                        c_rbtree_store(&s->right, y->left);
+                        c_rbtree_store(&y->left, s);
+                        c_rbtree_store(&p->left, y);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        x = s;
+                        s = y;
+                }
+
+                t = c_rbnode_pop_root(p);
+                g = c_rbnode_parent(p);
+                y = s->right;
+                c_rbtree_store(&p->left, y);
+                c_rbtree_store(&s->right, p);
+                c_rbnode_swap_child(p, s);
+                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                if (y)
+                        c_rbnode_set_parent_and_flags(y, p, c_rbnode_flags(y));
+                c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(p));
+                c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_push_root(s, t);
+        }
+}
+
+static inline CRBNode *c_rbnode_rebalance_path(CRBNode *p, CRBNode **previous) {
+        CRBNode *s, *nl, *nr;
+
+        while (p) {
+                s = (*previous == p->left) ? p->right : p->left;
+                nl = s->left;
+                nr = s->right;
+
+                /*
+                 * If the sibling under @p is black and exclusively has black
+                 * children itself (i.e., nephews/nieces in @nl/@nr), then we
+                 * can easily re-color to fix this sub-tree, and continue one
+                 * layer up. However, if that's not the case, we have tree
+                 * rotations at our hands to move one of the black nodes into
+                 * our path, then turning the red node black to fully restore
+                 * the RB-Tree invariants again. This fixup will be done by the
+                 * caller, so we just let them know where to do that.
+                 */
+                if (c_rbnode_is_red(s) ||
+                    (nl && c_rbnode_is_red(nl)) ||
+                    (nr && c_rbnode_is_red(nr)))
+                        return p;
+
+                /*
+                 * Case 3+4:
+                 * Sibling is black, and all nephews/nieces are black. Flip
+                 * sibling red. This way the sibling lost a black node in its
+                 * path, thus getting even with our path. However, paths not
+                 * going through @p haven't been fixed up, hence we proceed
+                 * recursively one layer up.
+                 * Before we continue one layer up, there are two possible
+                 * terminations: If the parent is red, we can turn it black.
+                 * This terminates the rebalancing, since the entire point of
+                 * rebalancing is that everything below @p has one black node
+                 * less than everything else. Lastly, if there is no layer
+                 * above, we hit the tree root and nothing is left to be done.
+                 */
+                c_rbnode_set_parent_and_flags(s, p, c_rbnode_flags(s) | C_RBNODE_RED);
+                if (c_rbnode_is_red(p)) {
+                        c_rbnode_set_parent_and_flags(p, c_rbnode_parent(p), c_rbnode_flags(p) & ~C_RBNODE_RED);
+                        return NULL;
+                }
+
+                *previous = p;
+                p = c_rbnode_parent(p);
+        }
+
+        return NULL;
+}
+
+static inline void c_rbnode_rebalance(CRBNode *n) {
+        CRBNode *previous = NULL;
+
+        /*
+         * Rebalance a tree after a node was removed. This function must be
+         * called on the parent of the leaf that was removed. It will first
+         * perform a recursive re-coloring on the parents of @n, until it
+         * either hits the tree-root, or a condition where a tree-rotation is
+         * needed to restore the RB-Tree invariants.
+         */
+
+        n = c_rbnode_rebalance_path(n, &previous);
+        if (n)
+                c_rbnode_rebalance_terminal(n, previous);
+}
+
+/**
+ * c_rbnode_unlink_stale() - remove node from tree
+ * @n:          node to remove
+ *
+ * This removes the given node from its tree. Once unlinked, the tree is
+ * rebalanced.
+ *
+ * This does *NOT* reset @n to being unlinked. If you need this, use
+ * c_rbtree_unlink().
+ */
+_public_ void c_rbnode_unlink_stale(CRBNode *n) {
+        CRBTree *t;
+
+        assert(n);
+        assert(c_rbnode_is_linked(n));
+
+        /*
+         * There are three distinct cases during node removal of a tree:
+         *  * The node has no children, in which case it can simply be removed.
+         *  * The node has exactly one child, in which case the child displaces
+         *    its parent.
+         *  * The node has two children, in which case there is guaranteed to
+         *    be a successor to the node (successor being the node ordered
+         *    directly after it). This successor is the leftmost descendant of
+         *    the node's right child, so it cannot have a left child of its own.
+         *    Therefore, we can simply swap the node with its successor (including
+         *    color) and remove the node from its new place, which will be one of
+         *    the first two cases.
+         *
+         * Whenever the node we removed was black, we have to rebalance the
+         * tree. Note that this affects the actual node we _remove_, not @n (in
+         * case we swap it).
+         */
+
+        if (!n->left && !n->right) {
+                /*
+                 * Case 1.0
+                 * The node has no children, it is a leaf-node and we
+                 * can simply unlink it. If it was also black, we have
+                 * to rebalance.
+                 */
+                t = c_rbnode_pop_root(n);
+                c_rbnode_swap_child(n, NULL);
+                c_rbnode_push_root(NULL, t);
+
+                if (c_rbnode_is_black(n))
+                        c_rbnode_rebalance(c_rbnode_parent(n));
+        } else if (!n->left && n->right) {
+                /*
+                 * Case 1.1:
+                 * The node has exactly one child, and it is on the
+                 * right. The child *must* be red (otherwise, the right
+                 * path has more black nodes than the non-existing left
+                 * path), and the node to be removed must hence be
+                 * black. We simply replace the node with its child,
+                 * turning the red child black, and thus no rebalancing
+                 * is required.
+                 */
+                t = c_rbnode_pop_root(n);
+                c_rbnode_swap_child(n, n->right);
+                c_rbnode_set_parent_and_flags(n->right, c_rbnode_parent(n), c_rbnode_flags(n->right) & ~C_RBNODE_RED);
+                c_rbnode_push_root(n->right, t);
+        } else if (n->left && !n->right) {
+                /*
+                 * Case 1.2:
+                 * The node has exactly one child, and it is on the left. Treat
+                 * it as mirrored case of Case 1.1 (i.e., replace the node by
+                 * its child).
+                 */
+                t = c_rbnode_pop_root(n);
+                c_rbnode_swap_child(n, n->left);
+                c_rbnode_set_parent_and_flags(n->left, c_rbnode_parent(n), c_rbnode_flags(n->left) & ~C_RBNODE_RED);
+                c_rbnode_push_root(n->left, t);
+        } else /* if (n->left && n->right) */ {
+                CRBNode *s, *p, *c, *next = NULL;
+
+                /* Cache possible tree-root during tree-rotations. */
+                t = c_rbnode_pop_root(n);
+
+                /*
+                 * Case 1.3:
+                 * We are dealing with a full interior node with a child on
+                 * both sides. We want to find its successor and swap it,
+                 * then remove the node similar to Case 1. For performance
+                 * reasons we don't perform the full swap, but skip links
+                 * that are about to be removed, anyway.
+                 *
+                 * First locate the successor, remember its child and the
+                 * parent the original node should have been linked on,
+                 * before being removed. Then link up both the successor's
+                 * new children and old child.
+                 *
+                 *      s: successor
+                 *      p: parent
+                 *      c: right (and only potential) child of successor
+                 *      next: next node to rebalance on
+                 */
+                s = n->right;
+                if (!s->left) {
+                        /*
+                         * The immediate right child is the successor,
+                         * the successor's right child remains linked
+                         * as before.
+                         */
+                        p = s;
+                        c = s->right;
+                } else {
+                        s = c_rbnode_leftmost(s);
+                        p = c_rbnode_parent(s);
+                        c = s->right;
+
+                        /*
+                         * The new parent pointer of the successor's
+                         * child is set below.
+                         */
+                        c_rbtree_store(&p->left, c);
+
+                        c_rbtree_store(&s->right, n->right);
+                        c_rbnode_set_parent_and_flags(n->right, s, c_rbnode_flags(n->right));
+                }
+
+                /*
+                 * In both the above cases, the successor's left child
+                 * needs to be replaced with the left child of the node
+                 * that is being removed.
+                 */
+                c_rbtree_store(&s->left, n->left);
+                c_rbnode_set_parent_and_flags(n->left, s, c_rbnode_flags(n->left));
+
+                /*
+                 * As in cases 1.1 and 1.0 above, if successor was a
+                 * black leaf, we need to rebalance the tree, otherwise
+                 * it must have a red child, so simply recolor that black
+                 * and continue. Note that @next must be stored here, as
+                 * the original color of the successor is forgotten below.
+                 */
+                if (c)
+                        c_rbnode_set_parent_and_flags(c, p, c_rbnode_flags(c) & ~C_RBNODE_RED);
+                else
+                        next = c_rbnode_is_black(s) ? p : NULL;
+
+                /*
+                 * Update the successor, to inherit the parent and color
+                 * from the node being removed.
+                 */
+                if (c_rbnode_is_red(n))
+                        c_rbnode_set_parent_and_flags(s, c_rbnode_parent(n), c_rbnode_flags(s) | C_RBNODE_RED);
+                else
+                        c_rbnode_set_parent_and_flags(s, c_rbnode_parent(n), c_rbnode_flags(s) & ~C_RBNODE_RED);
+
+                /*
+                 * Update the parent of the node being removed. Note that this
+                 * needs to happen after the parent of the successor is set
+                 * above, as that call would clear the root pointer, if set.
+                 */
+                c_rbnode_swap_child(n, s);
+
+                /* Possibly restore saved tree-root. */
+                c_rbnode_push_root(s, t);
+
+                if (next)
+                        c_rbnode_rebalance(next);
+        }
+}
diff --git a/shared/c-rbtree/src/c-rbtree.h b/shared/c-rbtree/src/c-rbtree.h
new file mode 100644
index 00000000..cb33fcf7
--- /dev/null
+++ b/shared/c-rbtree/src/c-rbtree.h
@@ -0,0 +1,430 @@
+#pragma once
+
+/**
+ * Standalone Red-Black-Tree Implementation in Standard ISO-C11
+ *
+ * This library provides an RB-Tree API, that is fully implemented in ISO-C11
+ * and has no external dependencies. Furthermore, tree traversal, memory
+ * allocations, and key comparisons are completely controlled by the API user.
+ * The implementation only provides the RB-Tree specific rebalancing and
+ * coloring.
+ *
+ * A tree is represented by the "CRBTree" structure. It contains a *single*
+ * field, which is a pointer to the root node. If NULL, the tree is empty. If
+ * non-NULL, there is at least a single element in the tree.
+ *
+ * Each node of the tree is represented by the "CRBNode" structure. It has
+ * three fields. The @left and @right members can be accessed by the API user
+ * directly to traverse the tree. The third member is a combination of the
+ * parent pointer and a set of flags.
+ * API users are required to embed the CRBNode object into their own objects
+ * and then use offsetof() (i.e., container_of() and friends) to turn CRBNode
+ * pointers into pointers to their own structure.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
+
+typedef struct CRBNode CRBNode;
+typedef struct CRBTree CRBTree;
+
+/* implementation detail */
+#define C_RBNODE_RED                    (0x1UL)
+#define C_RBNODE_ROOT                   (0x2UL)
+#define C_RBNODE_UNUSED3                (0x4UL)
+#define C_RBNODE_FLAG_MASK              (0x7UL)
+
+/**
+ * struct CRBNode - Node of a Red-Black Tree
+ * @__parent_and_flags:         internal state
+ * @left:                       left child, or NULL
+ * @right:                      right child, or NULL
+ *
+ * Each node in an RB-Tree must embed a CRBNode object. This object contains
+ * pointers to its left and right child, which can be freely accessed by the
+ * API user at any time. They are NULL, if the node does not have a left/right
+ * child.
+ *
+ * The @__parent_and_flags field must never be accessed directly. It encodes
+ * the pointer to the parent node, and the color of the node. Use the accessor
+ * functions instead.
+ *
+ * There is no reason to initialize a CRBNode object before linking it.
+ * However, if you need a boolean state that tells you whether the node is
+ * linked or not, you should initialize the node via c_rbnode_init() or
+ * C_RBNODE_INIT.
+ */
+struct CRBNode {
+        alignas(8) unsigned long __parent_and_flags;
+        CRBNode *left;
+        CRBNode *right;
+};
+
+#define C_RBNODE_INIT(_var) { .__parent_and_flags = (unsigned long)&(_var) }
+
+CRBNode *c_rbnode_leftmost(CRBNode *n);
+CRBNode *c_rbnode_rightmost(CRBNode *n);
+CRBNode *c_rbnode_leftdeepest(CRBNode *n);
+CRBNode *c_rbnode_rightdeepest(CRBNode *n);
+CRBNode *c_rbnode_next(CRBNode *n);
+CRBNode *c_rbnode_prev(CRBNode *n);
+CRBNode *c_rbnode_next_postorder(CRBNode *n);
+CRBNode *c_rbnode_prev_postorder(CRBNode *n);
+
+void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n);
+void c_rbnode_unlink_stale(CRBNode *n);
+
+/**
+ * struct CRBTree - Red-Black Tree
+ * @root:       pointer to the root node, or NULL
+ *
+ * Each Red-Black Tree is rooted in an CRBTree object. This object contains a
+ * pointer to the root node of the tree. The API user is free to access the
+ * @root member at any time, and use it to traverse the tree.
+ *
+ * To initialize an RB-Tree, set it to NULL / all zero.
+ */
+struct CRBTree {
+        alignas(8) CRBNode *root;
+};
+
+#define C_RBTREE_INIT {}
+
+CRBNode *c_rbtree_first(CRBTree *t);
+CRBNode *c_rbtree_last(CRBTree *t);
+CRBNode *c_rbtree_first_postorder(CRBTree *t);
+CRBNode *c_rbtree_last_postorder(CRBTree *t);
+
+void c_rbtree_move(CRBTree *to, CRBTree *from);
+void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n);
+
+/**
+ * c_rbnode_init() - mark a node as unlinked
+ * @n:          node to operate on
+ *
+ * This marks the node @n as unlinked. The node will be set to a valid state
+ * that can never happen if the node is linked in a tree. Furthermore, this
+ * state is fully known to the implementation, and as such handled gracefully
+ * in all cases.
+ *
+ * You are *NOT* required to call this on your node. c_rbtree_add() can handle
+ * uninitialized nodes just fine. However, calling this allows to use
+ * c_rbnode_is_linked() to check for the state of a node. Furthermore,
+ * iterators and accessors can be called on initialized (yet unlinked) nodes.
+ *
+ * Use the C_RBNODE_INIT macro if you want to initialize static variables.
+ */
+static inline void c_rbnode_init(CRBNode *n) {
+        *n = (CRBNode)C_RBNODE_INIT(*n);
+}
+
+/**
+ * c_rbnode_entry() - get parent container of tree node
+ * @_what:              tree node, or NULL
+ * @_t:                 type of parent container
+ * @_m:                 member name of tree node in @_t
+ *
+ * If the tree node @_what is embedded into a surrounding structure, this will
+ * turn the tree node pointer @_what into a pointer to the parent container
+ * (using offsetof(3), or sometimes called container_of(3)).
+ *
+ * If @_what is NULL, this will also return NULL.
+ *
+ * Return: Pointer to parent container, or NULL.
+ */
+#define c_rbnode_entry(_what, _t, _m) \
+        ((_t *)(void *)(((unsigned long)(void *)(_what) ?: \
+                         offsetof(_t, _m)) - offsetof(_t, _m)))
+
+/**
+ * c_rbnode_parent() - return parent pointer
+ * @n           node to access
+ *
+ * This returns a pointer to the parent of the given node @n. If @n does not
+ * have a parent, NULL is returned. If @n is not linked, @n itself is returned.
+ *
+ * You should not call this on unlinked or uninitialized nodes! If you do, you
+ * better know its semantics.
+ *
+ * Return: Pointer to parent.
+ */
+static inline CRBNode *c_rbnode_parent(CRBNode *n) {
+        return (n->__parent_and_flags & C_RBNODE_ROOT) ?
+                        NULL :
+                        (void *)(n->__parent_and_flags & ~C_RBNODE_FLAG_MASK);
+}
+
+/**
+ * c_rbnode_is_linked() - check whether a node is linked
+ * @n:          node to check, or NULL
+ *
+ * This checks whether the passed node is linked. If you pass NULL, or if the
+ * node is not linked into a tree, this will return false. Otherwise, this
+ * returns true.
+ *
+ * Note that you must have either linked the node or initialized it, before
+ * calling this function. Never call this function on uninitialized nodes.
+ * Furthermore, removing a node via c_rbnode_unlink_stale() does *NOT* mark the
+ * node as unlinked. You have to call c_rbnode_init() yourself after removal, or
+ * use the c_rbnode_unlink() helper.
+ *
+ * Return: true if the node is linked, false if not.
+ */
+static inline _Bool c_rbnode_is_linked(CRBNode *n) {
+        return n && c_rbnode_parent(n) != n;
+}
+
+/**
+ * c_rbnode_unlink() - safely remove node from tree and reinitialize it
+ * @n:          node to remove, or NULL
+ *
+ * This is almost the same as c_rbnode_unlink_stale(), but extends it slightly, to be
+ * more convenient to use in many cases:
+ *  - if @n is unlinked or NULL, this is a no-op
+ *  - @n is reinitialized after being removed
+ */
+static inline void c_rbnode_unlink(CRBNode *n) {
+        if (c_rbnode_is_linked(n)) {
+                c_rbnode_unlink_stale(n);
+                c_rbnode_init(n);
+        }
+}
+
+/**
+ * c_rbtree_init() - initialize a new RB-Tree
+ * @t:          tree to operate on
+ *
+ * This initializes a new, empty RB-Tree. An RB-Tree must be initialized before
+ * any other functions are called on it. Alternatively, you can zero its memory
+ * or assign C_RBTREE_INIT.
+ */
+static inline void c_rbtree_init(CRBTree *t) {
+        *t = (CRBTree)C_RBTREE_INIT;
+}
+
+/**
+ * c_rbtree_is_empty() - check whether an RB-tree is empty
+ * @t:          tree to operate on
+ *
+ * This checks whether the passed RB-Tree is empty.
+ *
+ * Return: True if tree is empty, false otherwise.
+ */
+static inline _Bool c_rbtree_is_empty(CRBTree *t) {
+        return !t->root;
+}
+
+/**
+ * CRBCompareFunc - compare a node to a key
+ * @t:          tree where the node is linked to
+ * @k:          key to compare
+ * @n:          node to compare
+ *
+ * If you use the tree-traversal helpers (which are optional), you need to
+ * provide this callback so they can compare nodes in a tree to the key you
+ * look for.
+ *
+ * The tree @t is provided as optional context to this callback. The key you
+ * look for is provided as @k, the current node that should be compared to is
+ * provided as @n. This function should work like strcmp(), that is, return <0
+ * if @key orders before @n, 0 if both compare equal, and >0 if it orders after
+ * @n.
+ */
+typedef int (*CRBCompareFunc) (CRBTree *t, void *k, CRBNode *n);
+
+/**
+ * c_rbtree_find_node() - find node
+ * @t:          tree to search through
+ * @f:          comparison function
+ * @k:          key to search for
+ *
+ * This searches through @t for a node that compares equal to @k. The function
+ * @f must be provided by the caller, which is used to compare nodes to @k. See
+ * the documentation of CRBCompareFunc for details.
+ *
+ * If there are multiple entries that compare equal to @k, this will return a
+ * pseudo-randomly picked node. If you need stable lookup functions for trees
+ * where duplicate entries are allowed, you better code your own lookup.
+ *
+ * Return: Pointer to matching node, or NULL.
+ */
+static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const void *k) {
+        CRBNode *i;
+
+        assert(t);
+        assert(f);
+
+        i = t->root;
+        while (i) {
+                int v = f(t, (void *)k, i);
+                if (v < 0)
+                        i = i->left;
+                else if (v > 0)
+                        i = i->right;
+                else
+                        return i;
+        }
+
+        return NULL;
+}
+
+/**
+ * c_rbtree_find_entry() - find entry
+ * @_t:         tree to search through
+ * @_f:         comparison function
+ * @_k:         key to search for
+ * @_s:         type of the structure that embeds the nodes
+ * @_m:         name of the node-member in type @_t
+ *
+ * This is very similar to c_rbtree_find_node(), but instead of returning a
+ * pointer to the CRBNode, it returns a pointer to the surrounding object. This
+ * object must embed the CRBNode object. The type of the surrounding object
+ * must be given as @_s, and the name of the embedded CRBNode member as @_m.
+ *
+ * See c_rbtree_find_node() and c_rbnode_entry() for more details.
+ *
+ * Return: Pointer to found entry, NULL if not found.
+ */
+#define c_rbtree_find_entry(_t, _f, _k, _s, _m) \
+        c_rbnode_entry(c_rbtree_find_node((_t), (_f), (_k)), _s, _m)
+
+/**
+ * c_rbtree_find_slot() - find slot to insert new node
+ * @t:          tree to search through
+ * @f:          comparison function
+ * @k:          key to search for
+ * @p:          output storage for parent pointer
+ *
+ * This searches through @t just like c_rbtree_find_node() does. However,
+ * instead of returning a pointer to a node that compares equal to @k, this
+ * searches for a slot to insert a node with key @k. A pointer to the slot is
+ * returned, and a pointer to the parent of the slot is stored in @p. Both
+ * can be passed directly to c_rbtree_add(), together with your node to insert.
+ *
+ * If there already is a node in the tree, that compares equal to @k, this will
+ * return NULL and store the conflicting node in @p. In all other cases,
+ * this will return a pointer (non-NULL) to the empty slot to insert the node
+ * at. @p will point to the parent node of that slot.
+ *
+ * If you want trees that allow duplicate nodes, you better code your own
+ * insertion function.
+ *
+ * Return: Pointer to slot to insert node, or NULL on conflicts.
+ */
+static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const void *k, CRBNode **p) {
+        CRBNode **i;
+
+        assert(t);
+        assert(f);
+        assert(p);
+
+        i = &t->root;
+        *p = NULL;
+        while (*i) {
+                int v = f(t, (void *)k, *i);
+                *p = *i;
+                if (v < 0)
+                        i = &(*i)->left;
+                else if (v > 0)
+                        i = &(*i)->right;
+                else
+                        return NULL;
+        }
+
+        return i;
+}
+
+/**
+ * c_rbtree_for_each*() - iterators
+ *
+ * The c_rbtree_for_each*() macros provide simple for-loop wrappers to iterate
+ * an RB-Tree. They come in a set of flavours:
+ *
+ *   - "entry": This combines c_rbnode_entry() with the loop iterator, so the
+ *              iterator always has the type of the surrounding object, rather
+ *              than CRBNode.
+ *
+ *   - "safe": The loop iterator always keeps track of the next element to
+ *             visit. This means, you can safely modify the current element,
+ *             while retaining loop-integrity.
+ *             You still must not touch any other entry of the tree. Otherwise,
+ *             the loop-iterator will be corrupted. Also remember to only
+ *             modify the tree in a way compatible with your iterator-order.
+ *             That is, if you use in-order iteration (default), you can unlink
+ *             your current object, including re-balancing the tree. However,
+ *             if you use post-order, you must not trigger a tree rebalance
+ *             operation, since it is not an invariant of post-order iteration.
+ *
+ *   - "postorder": Rather than the default in-order iteration, this iterates
+ *                  the tree in post-order.
+ *
+ *   - "unlink": This unlinks the current element from the tree before the loop
+ *               code is run. Note that the tree is not rebalanced. That is,
+ *               you must never break out of the loop. If you do so, the tree
+ *               is corrupted.
+ */
+
+#define c_rbtree_for_each(_iter, _tree)                                                                 \
+        for (_iter = c_rbtree_first(_tree);                                                             \
+             _iter;                                                                                     \
+             _iter = c_rbnode_next(_iter))
+
+#define c_rbtree_for_each_entry(_iter, _tree, _m)                                                       \
+        for (_iter = c_rbnode_entry(c_rbtree_first(_tree), __typeof__(*_iter), _m);                     \
+             _iter;                                                                                     \
+             _iter = c_rbnode_entry(c_rbnode_next(&_iter->_m), __typeof__(*_iter), _m))
+
+#define c_rbtree_for_each_safe(_iter, _safe, _tree)                                                     \
+        for (_iter = c_rbtree_first(_tree), _safe = c_rbnode_next(_iter);                               \
+             _iter;                                                                                     \
+             _iter = _safe, _safe = c_rbnode_next(_safe))
+
+#define c_rbtree_for_each_entry_safe(_iter, _safe, _tree, _m)                                           \
+        for (_iter = c_rbnode_entry(c_rbtree_first(_tree), __typeof__(*_iter), _m),                     \
+             _safe = _iter ? c_rbnode_entry(c_rbnode_next(&_iter->_m), __typeof__(*_iter), _m) : NULL;  \
+             _iter;                                                                                     \
+             _iter = _safe,                                                                             \
+             _safe = _safe ? c_rbnode_entry(c_rbnode_next(&_safe->_m), __typeof__(*_iter), _m) : NULL)
+
+#define c_rbtree_for_each_postorder(_iter, _tree)                                                       \
+        for (_iter = c_rbtree_first_postorder(_tree);                                                   \
+             _iter;                                                                                     \
+             _iter = c_rbnode_next_postorder(_iter))                                                    \
+
+#define c_rbtree_for_each_entry_postorder(_iter, _tree, _m)                                             \
+        for (_iter = c_rbnode_entry(c_rbtree_first_postorder(_tree), __typeof__(*_iter), _m);           \
+             _iter;                                                                                     \
+             _iter = c_rbnode_entry(c_rbnode_next_postorder(&_iter->_m), __typeof__(*_iter), _m))
+
+#define c_rbtree_for_each_safe_postorder(_iter, _safe, _tree)                                           \
+        for (_iter = c_rbtree_first_postorder(_tree), _safe = c_rbnode_next_postorder(_iter);           \
+             _iter;                                                                                     \
+             _iter = _safe, _safe = c_rbnode_next_postorder(_safe))
+
+#define c_rbtree_for_each_entry_safe_postorder(_iter, _safe, _tree, _m)                                                 \
+        for (_iter = c_rbnode_entry(c_rbtree_first_postorder(_tree), __typeof__(*_iter), _m),                           \
+             _safe = _iter ? c_rbnode_entry(c_rbnode_next_postorder(&_iter->_m), __typeof__(*_iter), _m) : NULL;        \
+             _iter;                                                                                                     \
+             _iter = _safe,                                                                                             \
+             _safe = _safe ? c_rbnode_entry(c_rbnode_next_postorder(&_safe->_m), __typeof__(*_iter), _m) : NULL)
+
+#define c_rbtree_for_each_safe_postorder_unlink(_iter, _safe, _tree)                                    \
+        for (_iter = c_rbtree_first_postorder(_tree), _safe = c_rbnode_next_postorder(_iter);           \
+             _iter ? ((*_iter = (CRBNode)C_RBNODE_INIT(*_iter)), 1) : (((_tree)->root = NULL), 0);      \
+             _iter = _safe, _safe = c_rbnode_next_postorder(_safe))                                     \
+
+#define c_rbtree_for_each_entry_safe_postorder_unlink(_iter, _safe, _tree, _m)                                          \
+        for (_iter = c_rbnode_entry(c_rbtree_first_postorder(_tree), __typeof__(*_iter), _m),                           \
+             _safe = _iter ? c_rbnode_entry(c_rbnode_next_postorder(&_iter->_m), __typeof__(*_iter), _m) : NULL;        \
+             _iter ? ((_iter->_m = (CRBNode)C_RBNODE_INIT(_iter->_m)), 1) : (((_tree)->root = NULL), 0);                \
+             _iter = _safe,                                                                                             \
+             _safe = _safe ? c_rbnode_entry(c_rbnode_next_postorder(&_safe->_m), __typeof__(*_iter), _m) : NULL)
+
+#ifdef __cplusplus
+}
+#endif