From 50b37d4a27d3295a29afca2286f1a5a086142cec Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:49:46 +0200 Subject: Adding upstream version 3.2.1+dfsg. Signed-off-by: Daniel Baumann --- src/lib/rbtree.c | 744 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 744 insertions(+) create mode 100644 src/lib/rbtree.c (limited to 'src/lib/rbtree.c') diff --git a/src/lib/rbtree.c b/src/lib/rbtree.c new file mode 100644 index 0000000..d9892bd --- /dev/null +++ b/src/lib/rbtree.c @@ -0,0 +1,744 @@ +/* + * rbtree.c RED-BLACK balanced binary trees. + * + * Version: $Id$ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA + * + * Copyright 2004,2006 The FreeRADIUS server project + */ + +RCSID("$Id$") + +#include + +#ifdef HAVE_PTHREAD_H +#include + +#define PTHREAD_MUTEX_LOCK(_x) if (_x->lock) pthread_mutex_lock(&((_x)->mutex)) +#define PTHREAD_MUTEX_UNLOCK(_x) if (_x->lock) pthread_mutex_unlock(&((_x)->mutex)) +#else +#define PTHREAD_MUTEX_LOCK(_x) +#define PTHREAD_MUTEX_UNLOCK(_x) +#endif + +/* Red-Black tree description */ +typedef enum { + BLACK, + RED +} node_colour_t; + +struct rbnode_t { + rbnode_t *left; //!< Left child + rbnode_t *right; //!< Right child + rbnode_t *parent; //!< Parent + node_colour_t colour; //!< Node colour (BLACK, RED) + void *data; //!< data stored in node +}; + +#define NIL &sentinel /* all leafs are sentinels */ +static rbnode_t sentinel = { NIL, NIL, NIL, BLACK, NULL}; + +#define NOT_AT_ROOT(_node) ((_node) != NIL) + +struct rbtree_t { +#ifndef NDEBUG + uint32_t magic; +#endif + rbnode_t *root; + int num_elements; + rb_comparator_t compare; + rb_free_t free; + bool replace; +#ifdef HAVE_PTHREAD_H + bool lock; + pthread_mutex_t mutex; +#endif +}; +#define RBTREE_MAGIC (0x5ad09c42) + +/** Walks the tree to delete all nodes Does NOT re-balance it! + * + */ +static void free_walker(rbtree_t *tree, rbnode_t *x) +{ + (void) talloc_get_type_abort(x, rbnode_t); + + if (x->left != NIL) free_walker(tree, x->left); + if (x->right != NIL) free_walker(tree, x->right); + + if (tree->free) tree->free(x->data); + talloc_free(x); +} + +void rbtree_free(rbtree_t *tree) +{ + if (!tree) return; + + PTHREAD_MUTEX_LOCK(tree); + + /* + * walk the tree, deleting the nodes... + */ + if (tree->root != NIL) free_walker(tree, tree->root); + +#ifndef NDEBUG + tree->magic = 0; +#endif + tree->root = NULL; + + PTHREAD_MUTEX_UNLOCK(tree); + +#ifdef HAVE_PTHREAD_H + if (tree->lock) pthread_mutex_destroy(&tree->mutex); +#endif + + talloc_free(tree); +} + +/** Create a new RED-BLACK tree + * + */ +rbtree_t *rbtree_create(TALLOC_CTX *ctx, rb_comparator_t compare, rb_free_t node_free, int flags) +{ + rbtree_t *tree; + + if (!compare) return NULL; + + tree = talloc_zero(ctx, rbtree_t); + if (!tree) return NULL; + +#ifndef NDEBUG + tree->magic = RBTREE_MAGIC; +#endif + tree->root = NIL; + tree->compare = compare; + tree->replace = (flags & RBTREE_FLAG_REPLACE) != 0 ? true : false; +#ifdef HAVE_PTHREAD_H + tree->lock = (flags & RBTREE_FLAG_LOCK) != 0 ? true : false; + if (tree->lock) { + pthread_mutex_init(&tree->mutex, NULL); + } +#endif + tree->free = node_free; + + return tree; +} + +/** Rotate Node x to left + * + */ +static void rotate_left(rbtree_t *tree, rbnode_t *x) +{ + + rbnode_t *y = x->right; + + /* establish x->right link */ + x->right = y->left; + if (y->left != NIL) y->left->parent = x; + + /* establish y->parent link */ + if (y != NIL) y->parent = x->parent; + if (NOT_AT_ROOT(x->parent)) { + if (x == x->parent->left) { + x->parent->left = y; + } else { + x->parent->right = y; + } + } else { + tree->root = y; + } + + /* link x and y */ + y->left = x; + if (x != NIL) x->parent = y; +} + +/** Rotate Node x to right + * + */ +static void rotate_right(rbtree_t *tree, rbnode_t *x) +{ + rbnode_t *y = x->left; + + /* establish x->left link */ + x->left = y->right; + if (y->right != NIL) y->right->parent = x; + + /* establish y->parent link */ + if (y != NIL) y->parent = x->parent; + if (NOT_AT_ROOT(x->parent)) { + if (x == x->parent->right) { + x->parent->right = y; + } else { + x->parent->left = y; + } + } else { + tree->root = y; + } + + /* link x and y */ + y->right = x; + if (x != NIL) x->parent = y; +} + +/** Maintain red-black tree balance after inserting node x + * + */ +static void insert_fixup(rbtree_t *tree, rbnode_t *x) +{ + /* check RED-BLACK properties */ + while ((x != tree->root) && (x->parent->colour == RED)) { + /* we have a violation */ + if (x->parent == x->parent->parent->left) { + rbnode_t *y = x->parent->parent->right; + if (y->colour == RED) { + + /* uncle is RED */ + x->parent->colour = BLACK; + y->colour = BLACK; + x->parent->parent->colour = RED; + x = x->parent->parent; + } else { + + /* uncle is BLACK */ + if (x == x->parent->right) { + /* make x a left child */ + x = x->parent; + rotate_left(tree, x); + } + + /* recolour and rotate */ + x->parent->colour = BLACK; + x->parent->parent->colour = RED; + rotate_right(tree, x->parent->parent); + } + } else { + + /* mirror image of above code */ + rbnode_t *y = x->parent->parent->left; + if (y->colour == RED) { + + /* uncle is RED */ + x->parent->colour = BLACK; + y->colour = BLACK; + x->parent->parent->colour = RED; + x = x->parent->parent; + } else { + + /* uncle is BLACK */ + if (x == x->parent->left) { + x = x->parent; + rotate_right(tree, x); + } + x->parent->colour = BLACK; + x->parent->parent->colour = RED; + rotate_left(tree, x->parent->parent); + } + } + } + + if (tree->root != NIL) tree->root->colour = BLACK; /* Avoid cache-dirty on NIL */ +} + + +/** Insert an element into the tree + * + */ +rbnode_t *rbtree_insert_node(rbtree_t *tree, void *data) +{ + rbnode_t *current, *parent, *x; + + PTHREAD_MUTEX_LOCK(tree); + + /* find where node belongs */ + current = tree->root; + parent = NIL; + while (current != NIL) { + int result; + + /* + * See if two entries are identical. + */ + result = tree->compare(data, current->data); + if (result == 0) { + /* + * Don't replace the entry. + */ + if (!tree->replace) { + PTHREAD_MUTEX_UNLOCK(tree); + return NULL; + } + + /* + * Do replace the entry. + */ + if (tree->free) tree->free(current->data); + current->data = data; + PTHREAD_MUTEX_UNLOCK(tree); + return current; + } + + parent = current; + current = (result < 0) ? current->left : current->right; + } + + /* setup new node */ + x = talloc_zero(tree, rbnode_t); + if (!x) { + fr_strerror_printf("No memory for new rbtree node"); + PTHREAD_MUTEX_UNLOCK(tree); + return NULL; + } + + x->data = data; + x->parent = parent; + x->left = NIL; + x->right = NIL; + x->colour = RED; + + /* insert node in tree */ + if (NOT_AT_ROOT(parent)) { + if (tree->compare(data, parent->data) <= 0) { + parent->left = x; + } else { + parent->right = x; + } + } else { + tree->root = x; + } + + insert_fixup(tree, x); + + tree->num_elements++; + + PTHREAD_MUTEX_UNLOCK(tree); + return x; +} + +bool rbtree_insert(rbtree_t *tree, void *data) +{ + if (rbtree_insert_node(tree, data)) return true; + return false; +} + +/** Maintain RED-BLACK tree balance after deleting node x + * + */ +static void delete_fixup(rbtree_t *tree, rbnode_t *x, rbnode_t *parent) +{ + + while (x != tree->root && x->colour == BLACK) { + if (x == parent->left) { + rbnode_t *w = parent->right; + if (w->colour == RED) { + w->colour = BLACK; + parent->colour = RED; /* parent != NIL? */ + rotate_left(tree, parent); + w = parent->right; + } + if ((w->left->colour == BLACK) && (w->right->colour == BLACK)) { + if (w != NIL) w->colour = RED; + x = parent; + parent = x->parent; + } else { + if (w->right->colour == BLACK) { + if (w->left != NIL) w->left->colour = BLACK; + w->colour = RED; + rotate_right(tree, w); + w = parent->right; + } + w->colour = parent->colour; + if (parent != NIL) parent->colour = BLACK; + if (w->right->colour != BLACK) { + w->right->colour = BLACK; + } + rotate_left(tree, parent); + x = tree->root; + } + } else { + rbnode_t *w = parent->left; + if (w->colour == RED) { + w->colour = BLACK; + parent->colour = RED; /* parent != NIL? */ + rotate_right(tree, parent); + w = parent->left; + } + if ((w->right->colour == BLACK) && (w->left->colour == BLACK)) { + if (w != NIL) w->colour = RED; + x = parent; + parent = x->parent; + } else { + if (w->left->colour == BLACK) { + if (w->right != NIL) w->right->colour = BLACK; + w->colour = RED; + rotate_left(tree, w); + w = parent->left; + } + w->colour = parent->colour; + if (parent != NIL) parent->colour = BLACK; + if (w->left->colour != BLACK) { + w->left->colour = BLACK; + } + rotate_right(tree, parent); + x = tree->root; + } + } + } + if (x != NIL) x->colour = BLACK; /* Avoid cache-dirty on NIL */ +} + +/** Delete an element (z) from the tree + * + */ +static void rbtree_delete_internal(rbtree_t *tree, rbnode_t *z, bool skiplock) +{ + rbnode_t *x, *y; + rbnode_t *parent; + + if (!z || z == NIL) return; + + if (!skiplock) { + PTHREAD_MUTEX_LOCK(tree); + } + + if (z->left == NIL || z->right == NIL) { + /* y has a NIL node as a child */ + y = z; + } else { + /* find tree successor with a NIL node as a child */ + y = z->right; + while (y->left != NIL) y = y->left; + } + + /* x is y's only child */ + if (y->left != NIL) { + x = y->left; + } else { + x = y->right; /* may be NIL! */ + } + + /* remove y from the parent chain */ + parent = y->parent; + if (x != NIL) x->parent = parent; + + if (NOT_AT_ROOT(parent)) { + if (y == parent->left) { + parent->left = x; + } else { + parent->right = x; + } + } else { + tree->root = x; + } + + if (y != z) { + if (tree->free) tree->free(z->data); + z->data = y->data; + y->data = NULL; + + if ((y->colour == BLACK) && NOT_AT_ROOT(parent)) { + delete_fixup(tree, x, parent); + } + + /* + * The user structure in y->data MAy include a + * pointer to y. In that case, we CANNOT delete + * y. Instead, we copy z (which is now in the + * tree) to y, and fix up the parent/child + * pointers. + */ + memcpy(y, z, sizeof(*y)); + + if (NOT_AT_ROOT(y->parent)) { + if (y->parent->left == z) y->parent->left = y; + if (y->parent->right == z) y->parent->right = y; + } else { + tree->root = y; + } + if (y->left->parent == z) y->left->parent = y; + if (y->right->parent == z) y->right->parent = y; + + talloc_free(z); + + } else { + if (tree->free) tree->free(y->data); + + if (y->colour == BLACK) + delete_fixup(tree, x, parent); + + talloc_free(y); + } + + tree->num_elements--; + if (!skiplock) { + PTHREAD_MUTEX_UNLOCK(tree); + } +} +void rbtree_delete(rbtree_t *tree, rbnode_t *z) { + rbtree_delete_internal(tree, z, false); +} + +/** Delete a node from the tree, based on given data, which MUST have come from rbtree_finddata(). + * + * + */ +bool rbtree_deletebydata(rbtree_t *tree, void const *data) +{ + rbnode_t *node = rbtree_find(tree, data); + + if (!node) return false; + + rbtree_delete(tree, node); + + return true; +} + + +/** Find an element in the tree, returning the data, not the node + * + */ +rbnode_t *rbtree_find(rbtree_t *tree, void const *data) +{ + rbnode_t *current; + + PTHREAD_MUTEX_LOCK(tree); + current = tree->root; + + while (current != NIL) { + int result = tree->compare(data, current->data); + + if (result == 0) { + PTHREAD_MUTEX_UNLOCK(tree); + return current; + } else { + current = (result < 0) ? + current->left : current->right; + } + } + + PTHREAD_MUTEX_UNLOCK(tree); + return NULL; +} + +/** Find the user data. + * + */ +void *rbtree_finddata(rbtree_t *tree, void const *data) +{ + rbnode_t *x; + + x = rbtree_find(tree, data); + if (!x) return NULL; + + return x->data; +} + +/** Walk the tree, Pre-order + * + * We call ourselves recursively for each function, but that's OK, + * as the stack is only log(N) deep, which is ~12 entries deep. + */ +static int walk_node_pre_order(rbnode_t *x, rb_walker_t compare, void *context) +{ + int rcode; + rbnode_t *left, *right; + + left = x->left; + right = x->right; + + rcode = compare(context, x->data); + if (rcode != 0) return rcode; + + if (left != NIL) { + rcode = walk_node_pre_order(left, compare, context); + if (rcode != 0) return rcode; + } + + if (right != NIL) { + rcode = walk_node_pre_order(right, compare, context); + if (rcode != 0) return rcode; + } + + return 0; /* we know everything returned zero */ +} + +/** rbtree_in_order + * + */ +static int walk_node_in_order(rbnode_t *x, rb_walker_t compare, void *context) +{ + int rcode; + rbnode_t *right; + + if (x->left != NIL) { + rcode = walk_node_in_order(x->left, compare, context); + if (rcode != 0) return rcode; + } + + right = x->right; + + rcode = compare(context, x->data); + if (rcode != 0) return rcode; + + if (right != NIL) { + rcode = walk_node_in_order(right, compare, context); + if (rcode != 0) return rcode; + } + + return 0; /* we know everything returned zero */ +} + + +/** rbtree_post_order + * + */ +static int walk_node_post_order(rbnode_t *x, rb_walker_t compare, void *context) +{ + int rcode; + + if (x->left != NIL) { + rcode = walk_node_post_order(x->left, compare, context); + if (rcode != 0) return rcode; + } + + if (x->right != NIL) { + rcode = walk_node_post_order(x->right, compare, context); + if (rcode != 0) return rcode; + } + + rcode = compare(context, x->data); + if (rcode != 0) return rcode; + + return 0; /* we know everything returned zero */ +} + + +/** rbtree_delete_order + * + * This executes an rbtree_in_order-like walk that adapts to changes in the + * tree above it, which may occur because we allow the compare to + * tell us to delete the current node. + * + * The compare should return: + * + * < 0 - on error + * 0 - continue walking, don't delete the node + * 1 - delete the node and stop walking + * 2 - delete the node and continue walking + */ +static int walk_delete_order(rbtree_t *tree, rb_walker_t compare, void *context) +{ + rbnode_t *solid, *x; + int rcode = 0; + + /* Keep track of last node that refused deletion. */ + solid = NIL; + while (solid == NIL) { + x = tree->root; + if (x == NIL) break; + descend: + while (x->left != NIL) { + x = x->left; + } + visit: + rcode = compare(context, x->data); + if (rcode < 0) { + return rcode; + } + if (rcode) { + rbtree_delete_internal(tree, x, true); + if (rcode != 2) { + return rcode; + } + } else { + solid = x; + } + } + if (solid != NIL) { + x = solid; + if (x->right != NIL) { + x = x->right; + goto descend; + } + while (NOT_AT_ROOT(x->parent)) { + if (x->parent->left == x) { + x = x->parent; + goto visit; + } + x = x->parent; + } + } + return rcode; +} + + +/* + * walk the entire tree. The compare function CANNOT modify + * the tree. + * + * The compare function should return 0 to continue walking. + * Any other value stops the walk, and is returned. + */ +int rbtree_walk(rbtree_t *tree, rb_order_t order, rb_walker_t compare, void *context) +{ + int rcode; + + if (tree->root == NIL) return 0; + + PTHREAD_MUTEX_LOCK(tree); + + switch (order) { + case RBTREE_PRE_ORDER: + rcode = walk_node_pre_order(tree->root, compare, context); + break; + + case RBTREE_IN_ORDER: + rcode = walk_node_in_order(tree->root, compare, context); + break; + + case RBTREE_POST_ORDER: + rcode = walk_node_post_order(tree->root, compare, context); + break; + + case RBTREE_DELETE_ORDER: + rcode = walk_delete_order(tree, compare, context); + break; + + default: + rcode = -1; + break; + } + + PTHREAD_MUTEX_UNLOCK(tree); + return rcode; +} + +uint32_t rbtree_num_elements(rbtree_t *tree) +{ + if (!tree) return 0; + + return tree->num_elements; +} + +/* + * Given a Node, return the data. + */ +void *rbtree_node2data(UNUSED rbtree_t *tree, rbnode_t *node) +{ + if (!node) return NULL; + + return node->data; +} -- cgit v1.2.3