a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann This file is part of systemd. See COPYING for details.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann systemd is free software; you can redistribute it and/or modify it
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann under the terms of the GNU Lesser General Public License as published by
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann the Free Software Foundation; either version 2.1 of the License, or
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann (at your option) any later version.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann systemd is distributed in the hope that it will be useful, but
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann WITHOUT ANY WARRANTY; without even the implied warranty of
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann Lesser General Public License for more details.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann You should have received a copy of the GNU Lesser General Public License
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann along with systemd; If not, see <http://www.gnu.org/licenses/>.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * RB-Tree Implementation
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This implements the insertion/removal of elements in RB-Trees. You're highly
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * recommended to have an RB-Tree documentation at hand when reading this. Both
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * insertion and removal can be split into a handful of situations that can
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * occur. Those situations are enumerated as "Case 1" to "Case n" here, and
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * follow closely the cases described in most RB-Tree documentations. This file
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * does not explain why it is enough to handle just those cases, nor does it
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * provide a proof of correctness. Dig out your algorithm 101 handbook if
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * you're interested.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This implementation is *not* straightforward. Usually, a handful of
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * rotation, reparent, swap and link helpers can be used to implement the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * rebalance operations. However, those often perform unnecessary writes.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Therefore, this implementation hard-codes all the operations. You're highly
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * recommended to look at the two basic helpers before reading the code:
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_swap_child()
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_set_parent_and_color()
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Those are the only helpers used, hence, you should really know what they do
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * before digging into the code.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * For a highlevel documentation of the API, see the header file and docbook
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline unsigned long c_rbnode_color(CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann return (unsigned long)n->__parent_and_color & 1UL;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline _Bool c_rbnode_is_red(CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline _Bool c_rbnode_is_black(CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbnode_leftmost() - return leftmost child
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n: current node, or NULL
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This returns the leftmost child of @n. If @n is NULL, this will return NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * In all other cases, this function returns a valid pointer. That is, if @n
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * does not have any left children, this returns @n.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Worst case runtime (n: number of elements in tree): O(log(n))
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Return: Pointer to leftmost child, or NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbnode_rightmost() - return rightmost child
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n: current node, or NULL
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This returns the rightmost child of @n. If @n is NULL, this will return
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * NULL. In all other cases, this function returns a valid pointer. That is, if
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n does not have any right children, this returns @n.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Worst case runtime (n: number of elements in tree): O(log(n))
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Return: Pointer to rightmost child, or NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbnode_next() - return next node
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n: current node, or NULL
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * An RB-Tree always defines a linear order of its elements. This function
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * returns the logically next node to @n. If @n is NULL, the last node or
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * unlinked, this returns NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Worst case runtime (n: number of elements in tree): O(log(n))
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Return: Pointer to next node, or NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann while ((p = c_rbnode_parent(n)) && n == p->right)
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbnode_prev() - return previous node
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n: current node, or NULL
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * An RB-Tree always defines a linear order of its elements. This function
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * returns the logically previous node to @n. If @n is NULL, the first node or
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * unlinked, this returns NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Worst case runtime (n: number of elements in tree): O(log(n))
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Return: Pointer to previous node, or NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann while ((p = c_rbnode_parent(n)) && n == p->left)
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_first() - return first node
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @t: tree to operate on
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * An RB-Tree always defines a linear order of its elements. This function
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * returns the logically first node in @t. If @t is empty, NULL is returned.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Fixed runtime (n: number of elements in tree): O(log(n))
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Return: Pointer to first node, or NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_last() - return last node
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @t: tree to operate on
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * An RB-Tree always defines a linear order of its elements. This function
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * returns the logically last node in @t. If @t is empty, NULL is returned.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Fixed runtime (n: number of elements in tree): O(log(n))
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Return: Pointer to last node, or NULL.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Set the color and parent of a node. This should be treated as a simple
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * assignment of the 'color' and 'parent' fields of the node. No other magic is
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * applied. But since both fields share its backing memory, this helper
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * function is provided.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline void c_rbnode_set_parent_and_color(CRBNode *n, CRBNode *p, unsigned long c) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann n->__parent_and_color = (CRBNode*)((unsigned long)p | c);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann/* same as c_rbnode_set_parent_and_color(), but keeps the current parent */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline void c_rbnode_set_color(CRBNode *n, unsigned long c) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(n, c_rbnode_parent(n), c);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann/* same as c_rbnode_set_parent_and_color(), but keeps the current color */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline void c_rbnode_set_parent(CRBNode *n, CRBNode *p) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(n, p, c_rbnode_color(n));
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This function partially replaces an existing child pointer to a new one. The
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * existing child must be given as @old, the new child as @new. @p must be the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * parent of @old (or NULL if it has no parent).
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This function ensures that the parent of @old now points to @new. However,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * it does *NOT* change the parent pointer of @new. The caller must ensure
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * If @p is NULL, this function ensures that the root-pointer is adjusted
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * instead (given as @t).
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline void c_rbtree_swap_child(CRBTree *t, CRBNode *p, CRBNode *old, CRBNode *new) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline CRBNode *c_rbtree_paint_one(CRBTree *t, CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Paint a single node according to RB-Tree rules. The node must
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * already be linked into the tree and painted red.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * We repaint the node or rotate the tree, if required. In case a
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * recursive repaint is required, the next node to be re-painted
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * is returned.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * g: grandparent
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * gg: grandgrandparent
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * x: temporary
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann /* node is red, so we can access the parent directly */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * We reached the root. Mark it black and be done. As all
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * leaf-paths share the root, the ratio of black nodes on each
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * path stays the same. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(n, p, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann } else if (c_rbnode_is_black(p)) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * The parent is already black. As our node is red, we did not
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * change the number of black nodes on any path, nor do we have
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * multiple consecutive red nodes. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann } else if (p == p->__parent_and_color->left) { /* parent is red, so grandparent exists */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Parent and uncle are both red. We know the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * grandparent must be black then. Repaint parent and
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * uncle black, the grandparent red and recurse into
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * the grandparent. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann /* parent is red, uncle is black */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann if (n == p->right) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * We're the right child. Rotate on parent to
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * become left child, so we can handle it the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * same as case 5. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann /* 'n' is invalid from here on! */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * We're the red left child or a red parent, black
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * grandparent and uncle. Rotate on grandparent and
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * switch color with parent. Number of black nodes on
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * each path stays the same, but we got rid of the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * double red path. As the grandparent is still black,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * we're done. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann } else /* if (p == p->__parent_and_color->left) */ { /* same as above, but mirrored */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann if (n == p->left) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline void c_rbtree_paint(CRBTree *t, CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_add() - add node to tree
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @t: tree to operate one
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @p: parent node to link under, or NULL
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @l: left/right slot of @p (or root) to link at
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n: node to add
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This links @n into the tree given as @t. The caller must provide the exact
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * spot where to link the node. That is, the caller must traverse the tree
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * based on their search order. Once they hit a leaf where to insert the node,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * call this function to link it and rebalance the tree.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * A typical insertion would look like this (@t is your tree, @n is your node):
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * CRBNode **i, *p;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * i = &t->root;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * while (*i) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * if (compare(n, *i) < 0)
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * i = &(*i)->left;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * i = &(*i)->right;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_add(t, p, i, n);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Once the node is linked into the tree, a simple lookup on the same tree can
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * be coded like this:
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * CRBNode *i;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * i = t->root;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * while (i) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * int v = compare(n, i);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * i = (*i)->left;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * else if (v > 0)
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * i = (*i)->right;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * When you add nodes to a tree, the memory contents of the node do not matter.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * That is, there is no need to initialize the node via c_rbnode_init().
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * However, if you relink nodes multiple times during their lifetime, it is
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * usually very convenient to use c_rbnode_init() and c_rbtree_remove_init().
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * In those cases, you should validate that a node is unlinked before you call
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_add().
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannvoid c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann assert(!p || l == &p->left || l == &p->right);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(n, p, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline CRBNode *c_rbtree_rebalance_one(CRBTree *t, CRBNode *p, CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann CRBNode *s, *x, *y, *g;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Rebalance tree after a node was removed. This happens only if you
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * remove a black node and one path is now left with an unbalanced
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * number or black nodes.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This function assumes all paths through p and n have one black node
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * less than all other paths. If recursive fixup is required, the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * current node is returned.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann if (n == p->left) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * We have a red node as sibling. Rotate it onto our
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * side so we can later on turn it black. This way, we
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * gain the additional black node in our path. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Our sibling is black and has only black
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * children. Flip it red and turn parent black.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This way we gained a black node in our path,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * or we fix it recursively one layer up, which
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * will rotate the red sibling as parent. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Left child of our sibling is red, right one is black.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Rotate on parent so the right child of our sibling is
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * now red, and we can fall through to case 6. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * The right child of our sibling is red. Rotate left and flip
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * colors, which gains us an additional black node in our path,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * that was previously on our sibling. */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y));
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann } else /* if (!n || n == p->right) */ { /* same as above, but mirrored */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(s, g, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y));
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p));
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannstatic inline void c_rbtree_rebalance(CRBTree *t, CRBNode *p) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_remove() - remove node from tree
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @t: tree to operate one
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * @n: node to remove
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This removes the given node from its tree. Once unlinked, the tree is
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * rebalanced.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * The caller *must* ensure that the given tree is actually the tree it is
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * linked on. Otherwise, behavior is undefined.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * This does *NOT* reset @n to being unlinked (for performance reason, this
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * function *never* modifies @n at all). If you need this, use
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * c_rbtree_remove_init().
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmannvoid c_rbtree_remove(CRBTree *t, CRBNode *n) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann unsigned long c;
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * There are three distinct cases during node removal of a tree:
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * * The node has no children, in which case it can simply be removed.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * * The node has exactly one child, in which case the child displaces
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * its parent.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * * The node has two children, in which case there is guaranteed to
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * be a successor to the node (successor being the node ordered
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * directly after it). This successor cannot have two children by
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * itself (two interior nodes can never be successive). Therefore,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * we can simply swap the node with its successor (including color)
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * and have reduced this case to either of the first two.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * Whenever the node we removed was black, we have to rebalance the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * tree. Note that this affects the actual node we _remove_, not @n (in
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * case we swap it).
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * s: successor
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * gc: grand-...-child
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * x: temporary
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * next: next node to rebalance on
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * The node has no left child. If it neither has a right child,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * it is a leaf-node and we can simply unlink it. If it also
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * was black, we have to rebalance, as always if we remove a
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * black node.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * But if the node has a right child, the child *must* be red
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * (otherwise, the right path has more black nodes as the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * non-existing left path), and the node to be removed must
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * hence be black. We simply replace the node with its child,
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * turning the red child black, and thus no rebalancing is
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(n->right, p, c);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann } else if (!n->right) {
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * The node has exactly one child, and it is on the left. Treat
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * it as mirrored case of Case 1 (i.e., replace the node by its
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann c_rbnode_set_parent_and_color(n->left, p, c);
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * We are dealing with a full interior node with a child not on
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * both sides. Find its successor and swap it. Then remove the
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * node similar to Case 1. For performance reasons we don't
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * perform the full swap, but skip links that are about to be
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann * removed, anyway.
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann /* right child is next, no need to touch grandchild */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann /* find successor and swap partially */
a0e4cae82065edae47885614d73c534171aa8f7bDavid Herrmann /* node is partially swapped, now remove as in Case 1 */