Merge pull request #2115 from dvdhrm/rbtree

basic: add RB-Tree implementation

3 files changed, 1338 insertions, 0 deletions

diff --git a/src/basic/c-rbtree.c b/src/basic/c-rbtree.c
new file mode 100644
index 0000000000..914d7e5229
--- /dev/null
+++ b/src/basic/c-rbtree.c
@@ -0,0 +1,679 @@
+/***
+  This file is part of systemd. See COPYING for details.
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/*
+ * 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_rbtree_swap_child()
+ *     c_rbtree_set_parent_and_color()
+ * 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 <stddef.h>
+#include "c-rbtree.h"
+
+enum {
+        C_RBNODE_RED   = 0,
+        C_RBNODE_BLACK = 1,
+};
+
+static inline unsigned long c_rbnode_color(CRBNode *n) {
+        return (unsigned long)n->__parent_and_color & 1UL;
+}
+
+static inline _Bool c_rbnode_is_red(CRBNode *n) {
+        return c_rbnode_color(n) == C_RBNODE_RED;
+}
+
+static inline _Bool c_rbnode_is_black(CRBNode *n) {
+        return c_rbnode_color(n) == C_RBNODE_BLACK;
+}
+
+/**
+ * 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.
+ */
+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.
+ */
+CRBNode *c_rbnode_rightmost(CRBNode *n) {
+        if (n)
+                while (n->right)
+                        n = n->right;
+        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.
+ */
+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.
+ */
+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_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.
+ */
+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.
+ */
+CRBNode *c_rbtree_last(CRBTree *t) {
+        assert(t);
+        return c_rbnode_rightmost(t->root);
+}
+
+/*
+ * Set the color and parent of a node. This should be treated as a simple
+ * assignment of the 'color' 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_color(CRBNode *n, CRBNode *p, unsigned long c) {
+        assert(!((unsigned long)p & 1));
+        assert(c < 2);
+        n->__parent_and_color = (CRBNode*)((unsigned long)p | c);
+}
+
+/* same as c_rbnode_set_parent_and_color(), but keeps the current parent */
+static inline void c_rbnode_set_color(CRBNode *n, unsigned long c) {
+        c_rbnode_set_parent_and_color(n, c_rbnode_parent(n), c);
+}
+
+/* same as c_rbnode_set_parent_and_color(), but keeps the current color */
+static inline void c_rbnode_set_parent(CRBNode *n, CRBNode *p) {
+        c_rbnode_set_parent_and_color(n, p, c_rbnode_color(n));
+}
+
+/*
+ * This function partially replaces an existing child pointer to a new one. The
+ * existing child must be given as @old, the new child as @new. @p must be the
+ * parent of @old (or NULL if it has no parent).
+ * This function ensures that the parent of @old now points to @new. However,
+ * it does *NOT* change the parent pointer of @new. The caller must ensure
+ * this.
+ * If @p is NULL, this function ensures that the root-pointer is adjusted
+ * instead (given as @t).
+ */
+static inline void c_rbtree_swap_child(CRBTree *t, CRBNode *p, CRBNode *old, CRBNode *new) {
+        if (p) {
+                if (p->left == old)
+                        p->left = new;
+                else
+                        p->right = new;
+        } else {
+                t->root = new;
+        }
+}
+
+static inline CRBNode *c_rbtree_paint_one(CRBTree *t, CRBNode *n) {
+        CRBNode *p, *g, *gg, *u, *x;
+
+        /*
+         * Paint a single node according to RB-Tree rules. The node must
+         * already be linked into the tree and painted red.
+         * We repaint the node or rotate the tree, if required. In case a
+         * recursive repaint is required, the next node to be re-painted
+         * is returned.
+         *      p: parent
+         *      g: grandparent
+         *      gg: grandgrandparent
+         *      u: uncle
+         *      x: temporary
+         */
+
+        /* node is red, so we can access the parent directly */
+        p = n->__parent_and_color;
+
+        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_color(n, p, C_RBNODE_BLACK);
+                n = 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. */
+                n = NULL;
+        } else if (p == p->__parent_and_color->left) { /* parent is red, so grandparent exists */
+                g = p->__parent_and_color;
+                gg = c_rbnode_parent(g);
+                u = g->right;
+
+                if (u && c_rbnode_is_red(u)) {
+                        /* Case 3:
+                         * Parent and uncle are both red. We know the
+                         * grandparent must be black then. Repaint parent and
+                         * uncle black, the grandparent red and recurse into
+                         * the grandparent. */
+                        c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED);
+                        n = g;
+                } else {
+                        /* parent is red, uncle is black */
+
+                        if (n == p->right) {
+                                /* Case 4:
+                                 * We're the right child. Rotate on parent to
+                                 * become left child, so we can handle it the
+                                 * same as case 5. */
+                                x = n->left;
+                                p->right = n->left;
+                                n->left = p;
+                                if (x)
+                                        c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+                                c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED);
+                                p = n;
+                        }
+
+                        /* 'n' is invalid from here on! */
+                        n = NULL;
+
+                        /* Case 5:
+                         * We're the red left child or a red parent, black
+                         * grandparent and uncle. Rotate on grandparent and
+                         * switch color with parent. Number of black nodes on
+                         * each path stays the same, but we got rid of the
+                         * double red path. As the grandparent is still black,
+                         * we're done. */
+                        x = p->right;
+                        g->left = x;
+                        p->right = g;
+                        if (x)
+                                c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED);
+                        c_rbtree_swap_child(t, gg, g, p);
+                }
+        } else /* if (p == p->__parent_and_color->left) */ { /* same as above, but mirrored */
+                g = p->__parent_and_color;
+                gg = c_rbnode_parent(g);
+                u = g->left;
+
+                if (u && c_rbnode_is_red(u)) {
+                        c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED);
+                        n = g;
+                } else {
+                        if (n == p->left) {
+                                x = n->right;
+                                p->left = n->right;
+                                n->right = p;
+                                if (x)
+                                        c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+                                c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED);
+                                p = n;
+                        }
+
+                        n = NULL;
+
+                        x = p->left;
+                        g->right = x;
+                        p->left = g;
+                        if (x)
+                                c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED);
+                        c_rbtree_swap_child(t, gg, g, p);
+                }
+        }
+
+        return n;
+}
+
+static inline void c_rbtree_paint(CRBTree *t, CRBNode *n) {
+        assert(t);
+        assert(n);
+
+        while (n)
+                n = c_rbtree_paint_one(t, 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_rbtree_remove_init().
+ * In those cases, you should validate that a node is unlinked before you call
+ * c_rbtree_add().
+ */
+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_color(n, p, C_RBNODE_RED);
+        n->left = n->right = NULL;
+        *l = n;
+
+        c_rbtree_paint(t, n);
+}
+
+static inline CRBNode *c_rbtree_rebalance_one(CRBTree *t, CRBNode *p, CRBNode *n) {
+        CRBNode *s, *x, *y, *g;
+
+        /*
+         * Rebalance tree after a node was removed. This happens only if you
+         * remove a black node and one path is now left with an unbalanced
+         * number or black nodes.
+         * This function assumes all paths through p and n have one black node
+         * less than all other paths. If recursive fixup is required, the
+         * current node is returned.
+         */
+
+        if (n == p->left) {
+                s = p->right;
+                if (c_rbnode_is_red(s)) {
+                        /* Case 3:
+                         * 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. */
+                        g = c_rbnode_parent(p);
+                        x = s->left;
+                        p->right = x;
+                        s->left = p;
+                        c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
+                        c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED);
+                        c_rbtree_swap_child(t, g, p, s);
+                        s = x;
+                }
+
+                x = s->right;
+                if (!x || c_rbnode_is_black(x)) {
+                        y = s->left;
+                        if (!y || c_rbnode_is_black(y)) {
+                                /* Case 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,
+                                 * or we fix it recursively one layer up, which
+                                 * will rotate the red sibling as parent. */
+                                c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED);
+                                if (c_rbnode_is_black(p))
+                                        return p;
+
+                                c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK);
+                                return NULL;
+                        }
+
+                        /* 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;
+                        s->left = y->right;
+                        y->right = s;
+                        p->right = y;
+                        if (x)
+                                c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+                        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. */
+                g = c_rbnode_parent(p);
+                y = s->left;
+                p->right = y;
+                s->left = p;
+                c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+                if (y)
+                        c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y));
+                c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
+                c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK);
+                c_rbtree_swap_child(t, g, p, s);
+        } else /* if (!n || n == p->right) */ { /* same as above, but mirrored */
+                s = p->left;
+                if (c_rbnode_is_red(s)) {
+                        g = c_rbnode_parent(p);
+                        x = s->right;
+                        p->left = x;
+                        s->right = p;
+                        c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(s, g, C_RBNODE_BLACK);
+                        c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED);
+                        c_rbtree_swap_child(t, g, p, s);
+                        s = x;
+                }
+
+                x = s->left;
+                if (!x || c_rbnode_is_black(x)) {
+                        y = s->right;
+                        if (!y || c_rbnode_is_black(y)) {
+                                c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED);
+                                if (c_rbnode_is_black(p))
+                                        return p;
+
+                                c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK);
+                                return NULL;
+                        }
+
+                        x = y->left;
+                        s->right = y->left;
+                        y->left = s;
+                        p->left = y;
+                        if (x)
+                                c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+                        x = s;
+                        s = y;
+                }
+
+                g = c_rbnode_parent(p);
+                y = s->right;
+                p->left = y;
+                s->right = p;
+                c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
+                if (y)
+                        c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y));
+                c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
+                c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK);
+                c_rbtree_swap_child(t, g, p, s);
+        }
+
+        return NULL;
+}
+
+static inline void c_rbtree_rebalance(CRBTree *t, CRBNode *p) {
+        CRBNode *n = NULL;
+
+        assert(t);
+        assert(p);
+
+        do {
+                n = c_rbtree_rebalance_one(t, p, n);
+                p = n ? c_rbnode_parent(n) : NULL;
+        } while (p);
+}
+
+/**
+ * c_rbtree_remove() - remove node from tree
+ * @t:          tree to operate one
+ * @n:          node to remove
+ *
+ * This removes the given node from its tree. Once unlinked, the tree is
+ * rebalanced.
+ * The caller *must* ensure that the given tree is actually the tree it is
+ * linked on. Otherwise, behavior is undefined.
+ *
+ * This does *NOT* reset @n to being unlinked (for performance reason, this
+ * function *never* modifies @n at all). If you need this, use
+ * c_rbtree_remove_init().
+ */
+void c_rbtree_remove(CRBTree *t, CRBNode *n) {
+        CRBNode *p, *s, *gc, *x, *next = NULL;
+        unsigned long c;
+
+        assert(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 cannot have two children by
+         *    itself (two interior nodes can never be successive). Therefore,
+         *    we can simply swap the node with its successor (including color)
+         *    and have reduced this case to either of the first two.
+         *
+         * 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).
+         *
+         *      p: parent
+         *      s: successor
+         *      gc: grand-...-child
+         *      x: temporary
+         *      next: next node to rebalance on
+         */
+
+        if (!n->left) {
+                /*
+                 * Case 1:
+                 * The node has no left child. If it neither has a right child,
+                 * it is a leaf-node and we can simply unlink it. If it also
+                 * was black, we have to rebalance, as always if we remove a
+                 * black node.
+                 * But if the node has a right child, the child *must* be red
+                 * (otherwise, the right path has more black nodes as 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.
+                 */
+                p = c_rbnode_parent(n);
+                c = c_rbnode_color(n);
+                c_rbtree_swap_child(t, p, n, n->right);
+                if (n->right)
+                        c_rbnode_set_parent_and_color(n->right, p, c);
+                else
+                        next = (c == C_RBNODE_BLACK) ? p : NULL;
+        } else if (!n->right) {
+                /*
+                 * Case 1.1:
+                 * The node has exactly one child, and it is on the left. Treat
+                 * it as mirrored case of Case 1 (i.e., replace the node by its
+                 * child).
+                 */
+                p = c_rbnode_parent(n);
+                c = c_rbnode_color(n);
+                c_rbtree_swap_child(t, p, n, n->left);
+                c_rbnode_set_parent_and_color(n->left, p, c);
+        } else {
+                /*
+                 * Case 2:
+                 * We are dealing with a full interior node with a child not on
+                 * both sides. 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.
+                 */
+                s = n->right;
+                if (!s->left) {
+                        /* right child is next, no need to touch grandchild */
+                        p = s;
+                        gc = s->right;
+                } else {
+                        /* find successor and swap partially */
+                        s = c_rbnode_leftmost(s);
+                        p = c_rbnode_parent(s);
+
+                        gc = s->right;
+                        p->left = s->right;
+                        s->right = n->right;
+                        c_rbnode_set_parent(n->right, s);
+                }
+
+                /* node is partially swapped, now remove as in Case 1 */
+                s->left = n->left;
+                c_rbnode_set_parent(n->left, s);
+
+                x = c_rbnode_parent(n);
+                c = c_rbnode_color(n);
+                c_rbtree_swap_child(t, x, n, s);
+                if (gc)
+                        c_rbnode_set_parent_and_color(gc, p, C_RBNODE_BLACK);
+                else
+                        next = c_rbnode_is_black(s) ? p : NULL;
+                c_rbnode_set_parent_and_color(s, x, c);
+        }
+
+        if (next)
+                c_rbtree_rebalance(t, next);
+}
diff --git a/src/basic/c-rbtree.h b/src/basic/c-rbtree.h
new file mode 100644
index 0000000000..20c5515ca1
--- /dev/null
+++ b/src/basic/c-rbtree.h
@@ -0,0 +1,297 @@
+#pragma once
+
+/***
+  This file is part of systemd. See COPYING for details.
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/*
+ * Standalone Red-Black-Tree Implementation in Standard ISO-C11
+ *
+ * This header 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 a fully in control of 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 *singly*
+ * 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 an implementation detail
+ * and encodes the parent pointer and color of the node.
+ * 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
+
+typedef struct CRBNode CRBNode;
+typedef struct CRBTree CRBTree;
+
+/**
+ * struct CRBNode - Node of a Red-Black Tree
+ * @__parent_and_color:         internal state
+ * @left:                       left child, or NULL
+ * @right:                      right child, or NULL
+ *
+ * Each node in an RB-Tree must embed an 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_color 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 {
+        CRBNode *__parent_and_color;
+        CRBNode *left;
+        CRBNode *right;
+};
+
+#define C_RBNODE_INIT(_var) { .__parent_and_color = &(_var) }
+
+CRBNode *c_rbnode_leftmost(CRBNode *n);
+CRBNode *c_rbnode_rightmost(CRBNode *n);
+CRBNode *c_rbnode_next(CRBNode *n);
+CRBNode *c_rbnode_prev(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 {
+        CRBNode *root;
+};
+
+CRBNode *c_rbtree_first(CRBTree *t);
+CRBNode *c_rbtree_last(CRBTree *t);
+
+void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n);
+void c_rbtree_remove(CRBTree *t, 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_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_rbtree_remove() does *NOT* mark the node
+ * as unlinked. You have to call c_rbnode_init() yourself after removal, or use
+ * the c_rbtree_remove_init() helper.
+ *
+ * Return: true if the node is linked, false if not.
+ */
+static inline _Bool c_rbnode_is_linked(CRBNode *n) {
+        return n && n->__parent_and_color != n;
+}
+
+/**
+ * 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 how its semantics.
+ *
+ * Return: Pointer to parent.
+ */
+static inline CRBNode *c_rbnode_parent(CRBNode *n) {
+        return (CRBNode*)((unsigned long)n->__parent_and_color & ~1UL);
+}
+
+/**
+ * c_rbtree_remove_init() - safely remove node from tree and reinitialize it
+ * @t:          tree to operate on
+ * @n:          node to remove, or NULL
+ *
+ * This is almost the same as c_rbtree_remove(), 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_rbtree_remove_init(CRBTree *t, CRBNode *n) {
+        if (c_rbnode_is_linked(n)) {
+                c_rbtree_remove(t, n);
+                c_rbnode_init(n);
+        }
+}
+
+/**
+ * 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 -1
+ * if @key orders before @n, 0 if both compare equal, and 1 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
+ * @_t:         type of the structure that embeds the nodes
+ * @_o:         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 @_t, and the name of the embedded CRBNode member as @_o.
+ *
+ * See c_rbtree_find_node() for more details.
+ *
+ * Return: Pointer to found entry, NULL if not found.
+ */
+#define c_rbtree_find_entry(_m, _f, _k, _t, _o) \
+        ((_t *)(((char *)c_rbtree_find_node((_m), (_f), (_k)) ?: \
+                (char *)NULL + offsetof(_t, _o)) - offsetof(_t, _o)))
+
+/**
+ * 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;
+}
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/src/test/test-rbtree.c b/src/test/test-rbtree.c
new file mode 100644
index 0000000000..8ae416c557
--- /dev/null
+++ b/src/test/test-rbtree.c
@@ -0,0 +1,362 @@
+/***
+  This file is part of systemd. See COPYING for details.
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/*
+ * Tests for RB-Tree
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include "c-rbtree.h"
+
+/* verify that all API calls are exported */
+static void test_api(void) {
+        CRBTree t = {};
+        CRBNode n = C_RBNODE_INIT(n);
+
+        assert(!c_rbnode_is_linked(&n));
+
+        /* init, is_linked, add, remove, remove_init */
+
+        c_rbtree_add(&t, NULL, &t.root, &n);
+        assert(c_rbnode_is_linked(&n));
+
+        c_rbtree_remove_init(&t, &n);
+        assert(!c_rbnode_is_linked(&n));
+
+        c_rbtree_add(&t, NULL, &t.root, &n);
+        assert(c_rbnode_is_linked(&n));
+
+        c_rbtree_remove(&t, &n);
+        assert(c_rbnode_is_linked(&n)); /* @n wasn't touched */
+
+        c_rbnode_init(&n);
+        assert(!c_rbnode_is_linked(&n));
+
+        /* first, last, leftmost, rightmost, next, prev */
+
+        assert(!c_rbtree_first(&t));
+        assert(!c_rbtree_last(&t));
+        assert(&n == c_rbnode_leftmost(&n));
+        assert(&n == c_rbnode_rightmost(&n));
+        assert(!c_rbnode_next(&n));
+        assert(!c_rbnode_prev(&n));
+}
+
+/* copied from c-rbtree.c, relies on internal representation */
+static inline _Bool c_rbnode_is_red(CRBNode *n) {
+        return !((unsigned long)n->__parent_and_color & 1UL);
+}
+
+/* copied from c-rbtree.c, relies on internal representation */
+static inline _Bool c_rbnode_is_black(CRBNode *n) {
+        return !!((unsigned long)n->__parent_and_color & 1UL);
+}
+
+static size_t validate(CRBTree *t) {
+        unsigned int i_black, n_black;
+        CRBNode *n, *p, *o;
+        size_t count = 0;
+
+        assert(t);
+        assert(!t->root || c_rbnode_is_black(t->root));
+
+        /* traverse to left-most child, count black nodes */
+        i_black = 0;
+        n = t->root;
+        while (n && n->left) {
+                if (c_rbnode_is_black(n))
+                        ++i_black;
+                n = n->left;
+        }
+        n_black = i_black;
+
+        /*
+         * Traverse tree and verify correctness:
+         *  1) A node is either red or black
+         *  2) The root is black
+         *  3) All leaves are black
+         *  4) Every red node must have two black child nodes
+         *  5) Every path to a leaf contains the same number of black nodes
+         *
+         * Note that NULL nodes are considered black, which is why we don't
+         * check for 3).
+         */
+        o = NULL;
+        while (n) {
+                ++count;
+
+                /* verify natural order */
+                assert(n > o);
+                o = n;
+
+                /* verify consistency */
+                assert(!n->right || c_rbnode_parent(n->right) == n);
+                assert(!n->left || c_rbnode_parent(n->left) == n);
+
+                /* verify 2) */
+                if (!c_rbnode_parent(n))
+                        assert(c_rbnode_is_black(n));
+
+                if (c_rbnode_is_red(n)) {
+                        /* verify 4) */
+                        assert(!n->left || c_rbnode_is_black(n->left));
+                        assert(!n->right || c_rbnode_is_black(n->right));
+                } else {
+                        /* verify 1) */
+                        assert(c_rbnode_is_black(n));
+                }
+
+                /* verify 5) */
+                if (!n->left && !n->right)
+                        assert(i_black == n_black);
+
+                /* get next node */
+                if (n->right) {
+                        n = n->right;
+                        if (c_rbnode_is_black(n))
+                                ++i_black;
+
+                        while (n->left) {
+                                n = n->left;
+                                if (c_rbnode_is_black(n))
+                                        ++i_black;
+                        }
+                } else {
+                        while ((p = c_rbnode_parent(n)) && n == p->right) {
+                                n = p;
+                                if (c_rbnode_is_black(p->right))
+                                        --i_black;
+                        }
+
+                        n = p;
+                        if (p && c_rbnode_is_black(p->left))
+                                --i_black;
+                }
+        }
+
+        return count;
+}
+
+static void insert(CRBTree *t, CRBNode *n) {
+        CRBNode **i, *p;
+
+        assert(t);
+        assert(n);
+        assert(!c_rbnode_is_linked(n));
+
+        i = &t->root;
+        p = NULL;
+        while (*i) {
+                p = *i;
+                if (n < *i) {
+                        i = &(*i)->left;
+                } else {
+                        assert(n > *i);
+                        i = &(*i)->right;
+                }
+        }
+
+        c_rbtree_add(t, p, i, n);
+}
+
+static void shuffle(void **nodes, size_t n_memb) {
+        unsigned int i, j;
+        void *t;
+
+        for (i = 0; i < n_memb; ++i) {
+                j = rand() % n_memb;
+                t = nodes[j];
+                nodes[j] = nodes[i];
+                nodes[i] = t;
+        }
+}
+
+/* run some pseudo-random tests on the tree */
+static void test_shuffle(void) {
+        CRBNode *nodes[256];
+        CRBTree t = {};
+        unsigned int i, j;
+        size_t n;
+
+        /* allocate and initialize all nodes */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                nodes[i] = malloc(sizeof(*nodes[i]));
+                assert(nodes[i]);
+                c_rbnode_init(nodes[i]);
+        }
+
+        /* shuffle nodes and validate *empty* tree */
+        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+        n = validate(&t);
+        assert(n == 0);
+
+        /* add all nodes and validate after each insertion */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                insert(&t, nodes[i]);
+                n = validate(&t);
+                assert(n == i + 1);
+        }
+
+        /* shuffle nodes again */
+        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all nodes (in different order) and validate on each round */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_rbtree_remove(&t, nodes[i]);
+                n = validate(&t);
+                assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+                c_rbnode_init(nodes[i]);
+        }
+
+        /* shuffle nodes and validate *empty* tree again */
+        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+        n = validate(&t);
+        assert(n == 0);
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                insert(&t, nodes[i]);
+                n = validate(&t);
+                assert(n == i + 1);
+        }
+
+        /* 4 times, remove half of the nodes and add them again */
+        for (j = 0; j < 4; ++j) {
+                /* shuffle nodes again */
+                shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+                /* remove half of the nodes */
+                for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
+                        c_rbtree_remove(&t, nodes[i]);
+                        n = validate(&t);
+                        assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+                        c_rbnode_init(nodes[i]);
+                }
+
+                /* shuffle the removed half */
+                shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes) / 2);
+
+                /* add the removed half again */
+                for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
+                        insert(&t, nodes[i]);
+                        n = validate(&t);
+                        assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1);
+                }
+        }
+
+        /* shuffle nodes again */
+        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_rbtree_remove(&t, nodes[i]);
+                n = validate(&t);
+                assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+                c_rbnode_init(nodes[i]);
+        }
+
+        /* free nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                free(nodes[i]);
+}
+
+typedef struct {
+        unsigned long key;
+        CRBNode rb;
+} Node;
+
+#define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb)))
+
+static int compare(CRBTree *t, void *k, CRBNode *n) {
+        unsigned long key = (unsigned long)k;
+        Node *node = node_from_rb(n);
+
+        return (key < node->key) ? -1 : (key > node->key) ? 1 : 0;
+}
+
+/* run tests against the c_rbtree_find*() helpers */
+static void test_map(void) {
+        CRBNode **slot, *p;
+        CRBTree t = {};
+        Node *nodes[2048];
+        unsigned long i;
+
+        /* allocate and initialize all nodes */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                nodes[i] = malloc(sizeof(*nodes[i]));
+                assert(nodes[i]);
+                nodes[i]->key = i;
+                c_rbnode_init(&nodes[i]->rb);
+        }
+
+        /* shuffle nodes */
+        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* add all nodes, and verify that each node is linked */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                assert(!c_rbnode_is_linked(&nodes[i]->rb));
+                assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+
+                slot = c_rbtree_find_slot(&t, compare, (void *)nodes[i]->key, &p);
+                assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+
+                assert(c_rbnode_is_linked(&nodes[i]->rb));
+                assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+        }
+
+        /* shuffle nodes again */
+        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all nodes (in different order) */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                assert(c_rbnode_is_linked(&nodes[i]->rb));
+                assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+
+                c_rbtree_remove_init(&t, &nodes[i]->rb);
+
+                assert(!c_rbnode_is_linked(&nodes[i]->rb));
+                assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
+        }
+
+        /* free nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                free(nodes[i]);
+}
+
+int main(int argc, char **argv) {
+        unsigned int i;
+
+        /* we want stable tests, so use fixed seed */
+        srand(0xdeadbeef);
+
+        test_api();
+
+        /*
+         * The tests are pseudo random; run them multiple times, each run will
+         * have different orders and thus different results.
+         */
+        for (i = 0; i < 4; ++i) {
+                test_shuffle();
+                test_map();
+        }
+
+        return 0;
+}