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