diff options
Diffstat (limited to 'contrib/rb3ptr')
| -rw-r--r-- | contrib/rb3ptr/Makefile.am | 6 | ||||
| -rw-r--r-- | contrib/rb3ptr/rb3ptr.c | 505 | ||||
| -rw-r--r-- | contrib/rb3ptr/rb3ptr.h | 474 |
3 files changed, 985 insertions, 0 deletions
diff --git a/contrib/rb3ptr/Makefile.am b/contrib/rb3ptr/Makefile.am new file mode 100644 index 0000000..fc660e7 --- /dev/null +++ b/contrib/rb3ptr/Makefile.am @@ -0,0 +1,6 @@ +# Source: http://jstimpfle.de/projects/rb3ptr/rb3ptr.html +# https://github.com/jstimpfle/rb3ptr +AM_CPPFLAGS = -I. + +noinst_LTLIBRARIES = librb3ptr.la +librb3ptr_la_SOURCES = rb3ptr.c rb3ptr.h diff --git a/contrib/rb3ptr/rb3ptr.c b/contrib/rb3ptr/rb3ptr.c new file mode 100644 index 0000000..aa72b1e --- /dev/null +++ b/contrib/rb3ptr/rb3ptr.c @@ -0,0 +1,505 @@ +/* rb3ptr -- Intrusively linked 3-pointer Red-black tree implementation */ + +/* Copyright (C) 2019, Jens Stimpfle */ + +/* +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software is furnished to do so, +subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS +FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR +COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER +IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +*/ + +#include <rb3ptr.h> +#include <stddef.h> // offsetof() + +enum { + _RB3_DIR_BIT = 1 << 0, + _RB3_COLOR_BIT = 1 << 1, + _RB3_BLACK = 0, + _RB3_RED = _RB3_COLOR_BIT, +}; + +static inline rb3_ptr rb3_child_ptr(struct rb3_head *head, int color) +{ + return (rb3_ptr) head | color; +} + +static inline rb3_ptr rb3_parent_ptr(struct rb3_head *head, int dir) +{ + return (rb3_ptr) head | dir; +} + +static inline struct rb3_head *rb3_get_black_child(struct rb3_head *head, int dir) +{ + return (struct rb3_head *) head->child[dir]; +} + +static inline int rb3_get_color_bit(struct rb3_head *head, int dir) +{ + return head->child[dir] & _RB3_COLOR_BIT; +} + +static inline int rb3_is_red(struct rb3_head *head, int dir) +{ + return rb3_get_color_bit(head, dir) != 0; +} + +static inline void rb3_set_red(struct rb3_head *head, int dir) +{ + head->child[dir] |= _RB3_COLOR_BIT; +} + +static inline void rb3_set_black(struct rb3_head *head, int dir) +{ + head->child[dir] &= ~_RB3_COLOR_BIT; +} + +static inline void rb3_connect(struct rb3_head *head, int dir, struct rb3_head *child, int color) +{ + head->child[dir] = rb3_child_ptr(child, color); + child->parent = rb3_parent_ptr(head, dir); +} + +static inline void rb3_connect_null(struct rb3_head *head, int dir, struct rb3_head *child, int color) +{ + head->child[dir] = rb3_child_ptr(child, color); + if (child) + child->parent = rb3_parent_ptr(head, dir); +} + +struct rb3_tree *rb3_get_containing_tree(struct rb3_head *head) +{ + while (rb3_get_parent(head)) + head = rb3_get_parent(head); + return (struct rb3_tree *) ((char *) head - (offsetof(struct rb3_head, child[0]))); +} + +static struct rb3_head *rb3_get_minmax_in_subtree(struct rb3_head *head, int dir) +{ + if (!head) + return _RB3_NULL; + while (rb3_has_child(head, dir)) + head = rb3_get_child(head, dir); + return head; +} + +struct rb3_head *rb3_get_minmax(struct rb3_tree *tree, int dir) +{ + return rb3_get_minmax_in_subtree(rb3_get_root(tree), dir); +} + +struct rb3_head *rb3_get_prevnext_descendant(struct rb3_head *head, int dir) +{ + return rb3_get_minmax_in_subtree(rb3_get_child(head, dir), !dir); +} + +struct rb3_head *rb3_get_prevnext_ancestor(struct rb3_head *head, int dir) +{ + /* + * Note: the direction is "reversed" for our purposes here, since + * the bit indicates the direction from the parent to `head` + */ + while (head && rb3_get_parent_dir(head) == dir) { + head = rb3_get_parent(head); + } + if (head) { + head = rb3_get_parent(head); + if (!head || rb3_is_base(head)) + return _RB3_NULL; + return head; + } + return _RB3_NULL; +} + +struct rb3_head *rb3_get_prevnext(struct rb3_head *head, int dir) +{ + if (rb3_has_child(head, dir)) + return rb3_get_prevnext_descendant(head, dir); + else + return rb3_get_prevnext_ancestor(head, dir); +} + +void rb3_update_augment(struct rb3_head *head, rb3_augment_func *augment) +{ + while (!rb3_is_base(head)) { + augment(head); + head = rb3_get_parent(head); + } +} + +static void rb3_rebalance_after_link(struct rb3_head *head, rb3_augment_func *augment) +{ + struct rb3_head *pnt; + struct rb3_head *gpnt; + struct rb3_head *ggpnt; + int left; + int right; + int gdir; + int ggdir; + + if (!rb3_get_parent(rb3_get_parent(head))) { + rb3_set_black(rb3_get_parent(head), RB3_LEFT); + if (augment) + augment(head); + return; + } + + if (!rb3_is_red(rb3_get_parent(rb3_get_parent(head)), rb3_get_parent_dir(rb3_get_parent(head)))) { + /* parent is black */ + if (augment) + rb3_update_augment(head, augment); + return; + } + + /* + * Since parent is red parent can't be the root. + * So we have at least a grandparent node, and grand-grandparent + * is either a real node or the base head. + */ + pnt = rb3_get_parent(head); + gpnt = rb3_get_parent(pnt); + ggpnt = rb3_get_parent(gpnt); + left = rb3_get_parent_dir(head); + right = !rb3_get_parent_dir(head); + gdir = rb3_get_parent_dir(pnt); + ggdir = rb3_get_parent_dir(gpnt); + + if (rb3_is_red(gpnt, !gdir)) { + /* uncle and parent are both red */ + rb3_set_red(ggpnt, ggdir); + rb3_set_black(gpnt, RB3_LEFT); + rb3_set_black(gpnt, RB3_RIGHT); + if (augment) + rb3_update_augment(head, augment); + rb3_rebalance_after_link(gpnt, augment); + } else if (gdir == right) { + rb3_connect_null(pnt, left, rb3_get_black_child(head, right), _RB3_BLACK); + rb3_connect_null(gpnt, right, rb3_get_black_child(head, left), _RB3_BLACK); + rb3_connect(head, left, gpnt, _RB3_RED); + rb3_connect(head, right, pnt, _RB3_RED); + rb3_connect(ggpnt, ggdir, head, _RB3_BLACK); + if (augment) { + augment(pnt); + augment(gpnt); + rb3_update_augment(head, augment); + } + } else { + rb3_connect_null(gpnt, left, rb3_get_black_child(pnt, right), _RB3_BLACK); + rb3_connect(pnt, right, gpnt, _RB3_RED); + rb3_connect(ggpnt, ggdir, pnt, _RB3_BLACK); + if (augment) { + augment(gpnt); + rb3_update_augment(head, augment); + } + } +} + +static void rb3_rebalance_after_unlink(struct rb3_head *pnt, int pdir, rb3_augment_func *augment) +{ + struct rb3_head *gpnt; + struct rb3_head *sibling; + struct rb3_head *sleft; + struct rb3_head *sleftleft; + struct rb3_head *sleftright; + enum rb3_dir left; + enum rb3_dir right; + enum rb3_dir gdir; + + if (!rb3_get_parent(pnt)) + return; + + left = pdir; // define "left" as the direction from parent to deleted node + right = !pdir; + gpnt = rb3_get_parent(pnt); + gdir = rb3_get_parent_dir(pnt); + sibling = rb3_get_child(pnt, right); + sleft = rb3_get_child(sibling, left); + + if (rb3_is_red(pnt, right)) { + /* sibling is red */ + rb3_connect(pnt, right, sleft, _RB3_BLACK); + rb3_connect(sibling, left, pnt, _RB3_RED); + rb3_connect(gpnt, gdir, sibling, _RB3_BLACK); + if (augment) + augment(sleft); + rb3_rebalance_after_unlink(pnt, pdir, augment); + } else if (rb3_is_red(sibling, right)) { + /* outer child of sibling is red */ + rb3_connect_null(pnt, right, sleft, rb3_get_color_bit(sibling, left)); + rb3_connect(sibling, left, pnt, _RB3_BLACK); + rb3_connect(gpnt, gdir, sibling, rb3_get_color_bit(gpnt, gdir)); + if (augment) { + rb3_update_augment(pnt, augment); + } + rb3_set_black(sibling, right); + } else if (rb3_is_red(sibling, left)) { + /* inner child of sibling is red */ + sleftleft = rb3_get_child(sleft, left); + sleftright = rb3_get_child(sleft, right); + rb3_connect_null(pnt, right, sleftleft, _RB3_BLACK); + rb3_connect_null(sibling, left, sleftright, _RB3_BLACK); + rb3_connect(sleft, left, pnt, _RB3_BLACK); + rb3_connect(sleft, right, sibling, _RB3_BLACK); + rb3_connect(gpnt, gdir, sleft, rb3_get_color_bit(gpnt, gdir)); + if (augment) { + augment(sibling); + rb3_update_augment(pnt, augment); + } + } else if (rb3_is_red(gpnt, gdir)) { + /* parent is red */ + rb3_set_red(pnt, right); + rb3_set_black(gpnt, gdir); + if (augment) + rb3_update_augment(pnt, augment); + } else { + /* all relevant nodes are black */ + rb3_set_red(pnt, right); + if (augment) + augment(pnt); + rb3_rebalance_after_unlink(gpnt, gdir, augment); + } +} + +void rb3_link_and_rebalance_and_maybe_augment(struct rb3_head *head, struct rb3_head *parent, int dir, rb3_augment_func *augment) +{ + _RB3_ASSERT(dir == RB3_LEFT || dir == RB3_RIGHT); + _RB3_ASSERT(!rb3_has_child(parent, dir)); + + parent->child[dir] = rb3_child_ptr(head, _RB3_RED); + head->parent = rb3_parent_ptr(parent, dir); + head->child[RB3_LEFT] = rb3_child_ptr(_RB3_NULL, _RB3_BLACK); + head->child[RB3_RIGHT] = rb3_child_ptr(_RB3_NULL, _RB3_BLACK); + rb3_rebalance_after_link(head, augment); +} + +void rb3_replace_and_maybe_augment(struct rb3_head *head, struct rb3_head *newhead, rb3_augment_func *augment) +{ + struct rb3_head *left; + struct rb3_head *right; + struct rb3_head *parent; + int pdir; + int pcol; + + *newhead = *head; + + left = rb3_get_child(head, RB3_LEFT); + right = rb3_get_child(head, RB3_RIGHT); + parent = rb3_get_parent(head); + pdir = rb3_get_parent_dir(head); + pcol = rb3_get_color_bit(parent, pdir); + + if (left) + left->parent = rb3_parent_ptr(newhead, RB3_LEFT); + if (right) + right->parent = rb3_parent_ptr(newhead, RB3_RIGHT); + parent->child[pdir] = rb3_child_ptr(newhead, pcol); + + if (augment) + rb3_update_augment(newhead, augment); +} + +static void rb3_unlink_noninternal_and_rebalance_and_maybe_augment(struct rb3_head *head, rb3_augment_func *augment) +{ + struct rb3_head *pnt; + struct rb3_head *cld; + int pdir; + int dir; + + dir = rb3_get_child(head, RB3_RIGHT) ? RB3_RIGHT : RB3_LEFT; + pnt = rb3_get_parent(head); + cld = rb3_get_child(head, dir); + pdir = rb3_get_parent_dir(head); + + int mustRebalance = !rb3_is_red(pnt, pdir) && !rb3_is_red(head, dir); + + /* since we added the possibility for augmentation, + we need to remove `head` *before* the rebalancing that we do below. + (Otherwise the augmentation function would still see the to-be-deleted child). */ + rb3_connect_null(pnt, pdir, cld, _RB3_BLACK); + + if (mustRebalance) + /* To be deleted node is black (and child cannot be repainted) + * => height decreased */ + rb3_rebalance_after_unlink(pnt, pdir, augment); + else if (augment) + /* the augment wasn't done since we didn't rebalance. So we need to do it separately. + TODO: Could we restrict the augmentation done during rebalancing to just the + nodes that aren't not be augmented by a regular rb3_augment_ancestors(pnt, augment)? */ + rb3_update_augment(pnt, augment); +} + +static void rb3_unlink_internal_and_rebalance_and_maybe_augment(struct rb3_head *head, rb3_augment_func *augment) +{ + struct rb3_head *subst; + + subst = rb3_get_next_descendant(head); + rb3_unlink_noninternal_and_rebalance_and_maybe_augment(subst, augment); + rb3_replace_and_maybe_augment(head, subst, augment); +} + +void rb3_unlink_and_rebalance_and_maybe_augment(struct rb3_head *head, rb3_augment_func *augment) +{ + if (rb3_has_child(head, RB3_LEFT) && rb3_has_child(head, RB3_RIGHT)) + rb3_unlink_internal_and_rebalance_and_maybe_augment(head, augment); + else + rb3_unlink_noninternal_and_rebalance_and_maybe_augment(head, augment); +} + +struct rb3_head *rb3_find_parent_in_subtree(struct rb3_head *parent, int dir, rb3_cmp cmp, void *data, struct rb3_head **parent_out, int *dir_out) +{ + return rb3_INLINE_find(parent, dir, cmp, data, parent_out, dir_out); +} + +struct rb3_head *rb3_insert(struct rb3_tree *tree, struct rb3_head *head, rb3_cmp cmp, void *data) +{ + struct rb3_head *found; + struct rb3_head *parent; + int dir; + + parent = rb3_get_base(tree); + dir = RB3_LEFT; + found = rb3_find_parent_in_subtree(parent, dir, cmp, data, &parent, &dir); + if (found) + return found; + rb3_link_and_rebalance(head, parent, dir); + return _RB3_NULL; +} + +struct rb3_head *rb3_delete(struct rb3_tree *tree, rb3_cmp cmp, void *data) +{ + struct rb3_head *found; + + found = rb3_find(tree, cmp, data); + if (found) { + rb3_unlink_and_rebalance(found); + return found; + } + return _RB3_NULL; +} + +struct rb3_head *rb3_find_parent(struct rb3_tree *tree, rb3_cmp cmp, void *data, struct rb3_head **parent_out, int *dir_out) +{ + return rb3_find_parent_in_subtree(rb3_get_base(tree), RB3_LEFT, cmp, data, parent_out, dir_out); +} + +struct rb3_head *rb3_find(struct rb3_tree *tree, rb3_cmp cmp, void *data) +{ + return rb3_find_parent_in_subtree(rb3_get_base(tree), RB3_LEFT, cmp, data, _RB3_NULL, _RB3_NULL); +} + +void rb3_link_and_rebalance(struct rb3_head *head, struct rb3_head *parent, int dir) +{ + rb3_link_and_rebalance_and_maybe_augment(head, parent, dir, _RB3_NULL); +} + +void rb3_unlink_and_rebalance(struct rb3_head *head) +{ + rb3_unlink_and_rebalance_and_maybe_augment(head, _RB3_NULL); +} + +void rb3_replace(struct rb3_head *head, struct rb3_head *newhead) +{ + rb3_replace_and_maybe_augment(head, newhead, _RB3_NULL); +} + +void rb3_link_and_rebalance_and_augment(struct rb3_head *head, struct rb3_head *parent, int dir, rb3_augment_func *augment) +{ + rb3_link_and_rebalance_and_maybe_augment(head, parent, dir, augment); +} + +void rb3_unlink_and_rebalance_and_augment(struct rb3_head *head, rb3_augment_func *augment) +{ + rb3_unlink_and_rebalance_and_maybe_augment(head, augment); +} + +void rb3_replace_and_augment(struct rb3_head *head, struct rb3_head *newhead, rb3_augment_func *augment) +{ + rb3_replace_and_maybe_augment(head, newhead, augment); +} + + +/* DEBUG STUFF */ + +#include <stdio.h> +static void visit_inorder_helper(struct rb3_head *head, int isred) +{ + if (!head) + return; + printf(" ("); + visit_inorder_helper(rb3_get_child(head, RB3_LEFT), rb3_is_red(head, RB3_LEFT)); + printf("%s", isred ? "R" : "B"); + visit_inorder_helper(rb3_get_child(head, RB3_RIGHT), rb3_is_red(head, RB3_RIGHT)); + printf(")"); +} + +static void visit_inorder(struct rb3_tree *tree) +{ + visit_inorder_helper(rb3_get_root(tree), 0); + printf("\n"); +} + +static int rb3_is_valid_tree_helper(struct rb3_head *head, int isred, int dir, int *depth) +{ + int i; + int depths[2] = { 1,1 }; + + *depth = 1; + + if (!head) { + if (isred) { + printf("red leaf child!\n"); + return 0; + } + return 1; + } + + if (rb3_get_parent_dir(head) != dir) { + printf("Directions messed up!\n"); + return 0; + } + + for (i = 0; i < 2; i++) { + if (isred && rb3_get_color_bit(head, i)) { + printf("two red in a row!\n"); + return 0; + } + if (!rb3_is_valid_tree_helper(rb3_get_child(head, i), + rb3_is_red(head, i), i, &depths[i])) + return 0; + } + if (depths[0] != depths[1]) { + printf("Unbalanced tree! got %d and %d\n", depths[0], depths[1]); + return 0; + } + *depth = depths[0] + !isred; + + return 1; +} + +int rb3_check_tree(struct rb3_tree *tree) +{ + int depth; + int valid; + + if (rb3_is_red(&tree->base, RB3_LEFT)) { + printf("Error! root is red.\n"); + return 0; + } + + valid = rb3_is_valid_tree_helper(rb3_get_root(tree), 0, 0, &depth); + if (!valid) + visit_inorder(tree); + return valid; +} diff --git a/contrib/rb3ptr/rb3ptr.h b/contrib/rb3ptr/rb3ptr.h new file mode 100644 index 0000000..1765113 --- /dev/null +++ b/contrib/rb3ptr/rb3ptr.h @@ -0,0 +1,474 @@ +/* rb3ptr -- Intrusively linked 3-pointer Red-black tree implementation */ + +/* Copyright (C) 2019, Jens Stimpfle */ + +/* +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software is furnished to do so, +subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS +FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR +COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER +IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +*/ + +#ifdef RB3PTR_H_INCLUDED +#error rb3ptr.h included twice! +#endif +#define RB3PTR_H_INCLUDED + +#ifndef UINTPTR_MAX /* detect stdint.h */ +#include <stdint.h> /* uintptr_t */ +#endif + +#ifndef _RB3_ASSERT +#ifndef assert +#include <assert.h> +#endif +#define _RB3_ASSERT(x) assert(x) +#endif + +#ifndef _RB3_NULL +#ifndef NULL +#include <stddef.h> +#endif +#define _RB3_NULL NULL +#endif + + +#ifdef __cplusplus // not yet tested +extern "C" { +#endif + + +/** + * Directions for navigation in the tree. + */ +enum rb3_dir { + RB3_LEFT = 0, + RB3_RIGHT = 1, +}; + +/** + * This type is used to efficiently store a pointer (at least 4-byte aligned) + * and some more information in the unused low bits. + */ +typedef uintptr_t rb3_ptr; + +/** + * Node type for 3-pointer Red-black trees. + * Contains left, right, and parent pointers. + * The left and right pointers have additional color bits. + * The parent pointer contains a direction bit indicating the direction + * to this child. + */ +struct rb3_head { + rb3_ptr child[2]; + rb3_ptr parent; +}; + +/** + * Tree type. It's just a fake base head that is wrapped for type safety and + * future extensibility. + */ +struct rb3_tree { + struct rb3_head base; +}; + +/** + * User-provided comparison function. It is used during tree searches. + * At each visited node, the function is called with that node as first + * argument and some additional user-provided data. + * + * It should returns a value less than, equal to, or greater than, 0, + * depending on whether the node compares less than, equal to, or greater + * than, the user-provided data. + */ +typedef int rb3_cmp(struct rb3_head *head, void *data); + +/** + * User-provided augment function. Used to do recomputations when a child changed. + */ +typedef void rb3_augment_func(struct rb3_head *head /*, void *data */); + +/** + * Initialize an rb3_head. + * After initialization, rb3_is_head_linked() will return false. + */ +static inline void rb3_reset_head(struct rb3_head *head) +{ + head->child[RB3_LEFT] = 0; + head->child[RB3_RIGHT] = 0; + head->parent = 0; +} + +/** + * Initialize an rb3_tree. + */ +static inline void rb3_reset_tree(struct rb3_tree *tree) +{ + tree->base.child[RB3_LEFT] = 0; + /* ! see doc of rb3_is_base(). */ + tree->base.child[RB3_RIGHT] = 3; + tree->base.parent = 0; +} + +/** + * Get base head of tree. + * + * Warning: the base head is never embedded in a client payload structure. + * It's just a link to host the real root of the tree as its left child. + */ +static inline struct rb3_head *rb3_get_base(struct rb3_tree *tree) +{ + return &tree->base; +} + +/** + * Test if given head is base of tree. + */ +static inline int rb3_is_base(struct rb3_head *head) +{ + /* We could check for the parent pointer being null, but by having + * a special sentinel right child value instead, we can make this + * function distinguish the base from unlinked pointers as well. + * + * A side effect is that this breaks programs with trees that are not + * initialized with rb3_init(), which could be a good or a bad thing, + * I don't know. */ + return head->child[RB3_RIGHT] == 3; +} + +/** + * Check if a non-base head is linked in a (any) tree. + */ +static inline int rb3_is_head_linked(struct rb3_head *head) +{ + return head->parent != 0; +} + +/** + * Get child in given direction, or NULL if there is no such child. `dir` + * must be RB3_LEFT or RB3_RIGHT. + */ +static inline struct rb3_head *rb3_get_child(struct rb3_head *head, int dir) +{ + return (struct rb3_head *)((head->child[dir]) & ~3); +} + +/* + * Test if a (left or right) child exists. + * This is slightly more efficient than calling rb3_get_child() and comparing + * to NULL. + */ +static inline int rb3_has_child(struct rb3_head *head, int dir) +{ + return head->child[dir] != 0; +} + +/** + * Get direction from parent to child by testing the direction. + * + * Return RB3_LEFT or RB3_RIGHT, depending on whether this node is the left or + * right child of its parent node. If the given node is the root node, + * RB3_LEFT is returned. (Technically the root node is the left child of the + * base node). + * + * This is more convenient and (in theory) more efficient than getting the + * parent and testing its left and right child. + */ +static inline int rb3_get_parent_dir(struct rb3_head *head) +{ + return head->parent & 1; +} + +/** + * Get parent head, or NULL if given node is the base head. + * + * Note that normally you don't want to visit the base head but stop already + * at the root node. + */ +static inline struct rb3_head *rb3_get_parent(struct rb3_head *head) +{ + return (struct rb3_head *)(head->parent & ~3); +} + +/** + * Get topmost element of tree (or NULL if empty) + */ +static inline struct rb3_head *rb3_get_root(struct rb3_tree *tree) +{ + return rb3_get_child(&tree->base, RB3_LEFT); +} + +/** + * Check if tree is empty. + */ +static inline int rb3_is_empty(struct rb3_tree *tree) +{ + struct rb3_head *base = rb3_get_base(tree); + return !rb3_has_child(base, RB3_LEFT); +} + +/** + * Get minimum or maximum node in the tree, depending on the value of `dir` + * (RB3_LEFT or RB3_RIGHT) + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_get_minmax(struct rb3_tree *tree, int dir); + +/** + * Get minimum (leftmost) element, or NULL if tree is empty. + * + * Time complexity: O(log n) + */ +static inline struct rb3_head *rb3_get_min(struct rb3_tree *tree) +{ + return rb3_get_minmax(tree, RB3_LEFT); +} + +/** + * Get previous or next in-order descendant, depending on the value of `dir` + * (RB3_LEFT or RB3_RIGHT). + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_get_prevnext_descendant(struct rb3_head *head, int dir); + +/** + * Get previous or next in-order ancestor, depending on the value of `dir` + * (RB3_LEFT or RB3_RIGHT). + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_get_prevnext_ancestor(struct rb3_head *head, int dir); + +/** + * Get previous or next in-order node, depending on the value of `dir`. + * + * Time complexity: O(log n), amortized over sequential scan: O(1) + */ +extern struct rb3_head *rb3_get_prevnext(struct rb3_head *head, int dir); + +/** + * Get maximum (rightmost) element, or NULL if tree is empty + * + * Time complexity: O(log n) + */ +static inline struct rb3_head *rb3_get_max(struct rb3_tree *tree) +{ + return rb3_get_minmax(tree, RB3_RIGHT); +} + +/** + * Get previous in-order node (maximal node in the tree that sorts before the + * given element) or NULL if no such element is in the tree. + * + * Time complexity: O(log n), amortized over sequential scan: O(1) + */ +static inline struct rb3_head *rb3_get_prev(struct rb3_head *head) +{ + return rb3_get_prevnext(head, RB3_LEFT); +} + +/** + * Get next in-order node (minimal node in the tree that sorts after the given + * element) or NULL if no such element is in the tree. + * + * Time complexity: O(log n), amortized over sequential scan: O(1) + */ +static inline struct rb3_head *rb3_get_next(struct rb3_head *head) +{ + return rb3_get_prevnext(head, RB3_RIGHT); +} + +/** + * Get previous in-order descendant (maximal descendant node that sorts before + * the given element) or NULL if no such element is in the tree. + * + * Time complexity: O(log n) + */ +static inline struct rb3_head *rb3_get_prev_descendant(struct rb3_head *head) +{ + return rb3_get_prevnext_descendant(head, RB3_LEFT); +} + +/** + * Get next in-order descendant (minimal descendant node that sorts after the + * given element) or NULL if no such element is in the tree. + * + * Time complexity: O(log n) + */ +static inline struct rb3_head *rb3_get_next_descendant(struct rb3_head *head) +{ + return rb3_get_prevnext_descendant(head, RB3_RIGHT); +} + +/** + * Get previous in-order ancestor (maximal ancestor node that sorts before the + * given element) or NULL if no such element is in the tree. + * + * Time complexity: O(log n) + */ +static inline struct rb3_head *rb3_get_prev_ancestor(struct rb3_head *head) +{ + return rb3_get_prevnext_ancestor(head, RB3_LEFT); +} + +/** + * Get next in-order ancestor (minimal ancestor node that sorts after the + * given element) or NULL if no such element is in the tree. + * + * Time complexity: O(log n) + */ +static inline struct rb3_head *rb3_get_next_ancestor(struct rb3_head *head) +{ + return rb3_get_prevnext_ancestor(head, RB3_RIGHT); +} + +/** + * Find a node in `tree` using `cmp` to direct the search. At each visited + * node in the tree `cmp` is called with that node and `data` as arguments. + * If a node that compares equal is found, it is returned. Otherwise, NULL is + * returned. + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_find(struct rb3_tree *tree, rb3_cmp cmp, void *data); + +/** + * Find a suitable insertion point for a new node in `tree` using `cmp` and + * `data` to direct the search. At each visited node in the tree `cmp` is + * called with that node and `data` as arguments. If a node that compares + * equal is found, it is returned. Otherwise, NULL is returned and the + * insertion point is returned as parent node and child direction in + * `parent_out` and `dir_out`. + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_find_parent(struct rb3_tree *tree, rb3_cmp cmp, void *data, struct rb3_head **parent_out, int *dir_out); + +/** + * Link `head` into `tree` below another node in the given direction (RB3_LEFT + * or RB3_RIGHT). The new node must replace a leaf. You can use + * rb3_find_parent() to find the insertion point. + * + * `head` must not be linked into another tree when this function is called. + * + * Time complexity: O(log n) + */ +extern void rb3_link_and_rebalance(struct rb3_head *head, struct rb3_head *parent, int dir); + +/** + * Unlink `head` from its current tree. + * + * Time complexity: O(log n) + */ +extern void rb3_unlink_and_rebalance(struct rb3_head *head); + +/** + * Replace `head` with `newhead`. `head` must be linked in a tree and + * `newhead` must not be linked in a tree. + */ +extern void rb3_replace(struct rb3_head *head, struct rb3_head *newhead); + +/** + * Like rb3_link_and_rebalance(), but call an augmentation function for each + * subtree that has been changed. + */ +extern void rb3_link_and_rebalance_and_augment(struct rb3_head *head, struct rb3_head *parent, int dir, rb3_augment_func *augment); + +/** + * Like rb3_unlink_and_rebalance(), but call an augmentation function for each + * subtree that has been changed. + */ +extern void rb3_unlink_and_rebalance_and_augment(struct rb3_head *head, rb3_augment_func *augment); + +/** + * Like rb3_replace(), but call an augmentation function for each subtree that has changed. + */ +extern void rb3_replace_and_augment(struct rb3_head *head, struct rb3_head *newhead, rb3_augment_func *augment); + +/** + * Update by calling the augmentation func for `head` and all its ancestors. + */ +extern void rb3_update_augment(struct rb3_head *head, rb3_augment_func *augment); + +/** + * Find suitable insertion point for a new node in a subtree, directed by the + * given search function. The subtree is given by its parent node `parent` and + * child direction `dir`. The insertion point and its child direction are + * returned in `parent_out` and `dir_out`. + * + * If the searched node is already in the tree (the compare function returns + * 0), it is returned. In this case `parent_out` and `dir_out` are left + * untouched. Otherwise NULL is returned. + */ +extern struct rb3_head *rb3_find_parent_in_subtree(struct rb3_head *parent, int dir, rb3_cmp cmp, void *data, struct rb3_head **parent_out, int *dir_out); + +/** + * Insert `head` into `tree` using `cmp` and `data` to direct the search. At + * each visited node in the tree `cmp` is called with that node and `data` as + * arguments (in that order). If a node that compares equal is found, it is + * returned. Otherwise, `head` is inserted into the tree and NULL is + * returned. + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_insert(struct rb3_tree *tree, struct rb3_head *head, rb3_cmp cmp, void *data); + +/** + * Find and delete a node from `tree` using `cmp` to direct the search. At + * each visited node in the tree `cmp` is called with that node and `head` as + * arguments (in that order). If a node that compares equal is found, it is + * unlinked from the tree and returned. Otherwise, NULL is returned. + * + * Time complexity: O(log n) + */ +extern struct rb3_head *rb3_delete(struct rb3_tree *tree, rb3_cmp cmp, void *data); + +/** + * Given a node that is known to be linked in _some_ tree, find that tree. + * + * This involves a little hackery with offsetof(3) + */ +extern struct rb3_tree *rb3_get_containing_tree(struct rb3_head *head); + + +/* +XXX: is inlining the search function advantageous? +*/ +static inline struct rb3_head *rb3_INLINE_find(struct rb3_head *parent, int dir, rb3_cmp cmp, void *data, struct rb3_head **parent_out, int *dir_out) +{ + _RB3_ASSERT(parent != _RB3_NULL); + while (rb3_has_child(parent, dir)) { + parent = rb3_get_child(parent, dir); + int r = cmp(parent, data); + if (r == 0) + return parent; + dir = (r < 0) ? RB3_RIGHT : RB3_LEFT; + } + if (parent_out) + *parent_out = parent; + if (dir_out) + *dir_out = dir; + return _RB3_NULL; +} + +/**************** DEBUG STUFF *******************/ +int rb3_check_tree(struct rb3_tree *tree); +/************************************************/ + +#ifdef __cplusplus +} // extern "C" +#endif |