diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/basic/c-rbtree.c | 674 | ||||
| -rw-r--r-- | src/basic/c-rbtree.h | 297 | ||||
| -rw-r--r-- | src/test/test-rbtree.c | 362 |
3 files changed, 0 insertions, 1333 deletions
diff --git a/src/basic/c-rbtree.c b/src/basic/c-rbtree.c deleted file mode 100644 index cf5a7242df..0000000000 --- a/src/basic/c-rbtree.c +++ /dev/null @@ -1,674 +0,0 @@ -/*** - 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 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 deleted file mode 100644 index 20c5515ca1..0000000000 --- a/src/basic/c-rbtree.h +++ /dev/null @@ -1,297 +0,0 @@ -#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 deleted file mode 100644 index 8ae416c557..0000000000 --- a/src/test/test-rbtree.c +++ /dev/null @@ -1,362 +0,0 @@ -/*** - 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; -} |