X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=src%2Futils%2Favltree.c;h=54c1895673a8dd68e6aeccf4655615db00078930;hb=49b5a4d2e8e4fb1e4f67c2a368d8d2e3e76b765f;hp=95c004d32ffbe10ae39a31b9a146a80adccd2b41;hpb=4a307afc0bddeba03e26d2d6d284b3f96f80a931;p=sysdb.git diff --git a/src/utils/avltree.c b/src/utils/avltree.c index 95c004d..54c1895 100644 --- a/src/utils/avltree.c +++ b/src/utils/avltree.c @@ -29,10 +29,14 @@ # include "config.h" #endif /* HAVE_CONFIG_H */ +#include "sysdb.h" #include "utils/avltree.h" +#include "utils/error.h" -#include +#include +#include +#include #include /* @@ -48,13 +52,21 @@ struct node { node_t *parent; node_t *left; node_t *right; + + size_t height; }; +#define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "") +#define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0) +#define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \ + NODE_HEIGHT((n)->left)) + 1) + +#define BALANCE(n) \ + ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0) + struct sdb_avltree { pthread_rwlock_t lock; - sdb_object_cmp_cb cmp; - node_t *root; size_t size; }; @@ -87,6 +99,7 @@ node_create(sdb_object_t *obj) sdb_object_ref(obj); n->obj = obj; n->parent = n->left = n->right = NULL; + n->height = 1; return n; } /* node_create */ @@ -122,14 +135,49 @@ node_next(node_t *n) return next; } /* node_next */ +static node_t * +node_smallest(sdb_avltree_t *tree) +{ + node_t *n; + + if (! tree) + return NULL; + + n = tree->root; + while (n && n->left) + n = n->left; + return n; +} /* node_smallest */ + static void tree_clear(sdb_avltree_t *tree) { node_t *n; + if ((! tree) || (! tree->root)) + return; + + /* do a depth-first iteration and delete the leafs */ n = tree->root; while (n) { - node_t *tmp = node_next(n); + node_t *tmp; + + if (n->left) { + n = n->left; + continue; + } + else if (n->right) { + n = n->right; + continue; + } + + tmp = n->parent; + if (tmp) { + if (tmp->left == n) + tmp->left = NULL; + else + tmp->right = NULL; + } node_destroy(n); n = tmp; @@ -139,12 +187,100 @@ tree_clear(sdb_avltree_t *tree) tree->size = 0; } /* tree_clear */ +/* Switch node 'n' with its right child, making 'n' + * the new left child of that node. */ +static void +rotate_left(sdb_avltree_t *tree, node_t *n) +{ + node_t *n2 = n->right; + node_t *c = n2->left; + + n2->parent = n->parent; + if (! n2->parent) + tree->root = n2; + else if (n2->parent->left == n) + n2->parent->left = n2; + else + n2->parent->right = n2; + + n2->left = n; + n->parent = n2; + + n->right = c; + if (c) + c->parent = n; + + n->height = CALC_HEIGHT(n); + n2->height = CALC_HEIGHT(n2); +} /* rotate_left */ + +/* Switch node 'n' with its left child, making 'n' + * the new right child of that node. */ +static void +rotate_right(sdb_avltree_t *tree, node_t *n) +{ + node_t *n2 = n->left; + node_t *c = n2->right; + + n2->parent = n->parent; + if (! n2->parent) + tree->root = n2; + else if (n2->parent->left == n) + n2->parent->left = n2; + else + n2->parent->right = n2; + + n2->right = n; + n->parent = n2; + + n->left = c; + if (c) + c->parent = n; + + n->height = CALC_HEIGHT(n); + n2->height = CALC_HEIGHT(n2); +} /* rotate_right */ + +/* Rebalance a tree starting at node 'n' towards the root; + * also, update the node heights all the way up to the root. */ +static void +rebalance(sdb_avltree_t *tree, node_t *n) +{ + for ( ; n; n = n->parent) { + int bf = BALANCE(n); + + if (bf == 0) + return; + + if ((-1 <= bf) && (bf <= 1)) { + n->height = CALC_HEIGHT(n); + continue; + } + + assert((-2 <= bf) && (bf <= 2)); + + if (bf == 2) { + if (BALANCE(n->left) == -1) + rotate_left(tree, n->left); + rotate_right(tree, n); + } + else { + if (BALANCE(n->right) == 1) + rotate_right(tree, n->right); + rotate_left(tree, n); + } + + /* n was moved downwards; get back to the previous level */ + n = n->parent; + } +} /* rebalance */ + /* * public API */ sdb_avltree_t * -sdb_avltree_create(sdb_object_cmp_cb cmp) +sdb_avltree_create(void) { sdb_avltree_t *tree; @@ -152,11 +288,7 @@ sdb_avltree_create(sdb_object_cmp_cb cmp) if (! tree) return NULL; - if (! cmp) - cmp = sdb_object_cmp_by_name; - pthread_rwlock_init(&tree->lock, /* attr = */ NULL); - tree->cmp = cmp; tree->root = NULL; tree->size = 0; @@ -202,11 +334,23 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj) if (! n) return -1; + pthread_rwlock_wrlock(&tree->lock); + + if (! tree->root) { + tree->root = n; + tree->size = 1; + pthread_rwlock_unlock(&tree->lock); + return 0; + } + parent = tree->root; - while (parent) { - diff = tree->cmp(obj, parent->obj); + while (42) { + assert(parent); + + diff = strcasecmp(obj->name, parent->obj->name); if (! diff) { node_destroy(n); + pthread_rwlock_unlock(&tree->lock); return -1; } @@ -226,22 +370,39 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj) } } - if (! parent) { - /* new root */ - if (diff < 0) - n->right = tree->root; - else - n->left = tree->root; - tree->root = n; - } - n->parent = parent; ++tree->size; - /* XXX: rebalance */ + rebalance(tree, parent); + pthread_rwlock_unlock(&tree->lock); return 0; } /* sdb_avltree_insert */ +sdb_object_t * +sdb_avltree_lookup(sdb_avltree_t *tree, const char *name) +{ + node_t *n; + + if (! tree) + return NULL; + + n = tree->root; + while (n) { + int diff = strcasecmp(n->obj->name, name); + + if (! diff) { + sdb_object_ref(n->obj); + return n->obj; + } + + if (diff < 0) + n = n->right; + else + n = n->left; + } + return NULL; +} /* sdb_avltree_lookup_by_name */ + sdb_avltree_iter_t * sdb_avltree_get_iter(sdb_avltree_t *tree) { @@ -257,9 +418,7 @@ sdb_avltree_get_iter(sdb_avltree_t *tree) pthread_rwlock_rdlock(&tree->lock); iter->tree = tree; - iter->node = tree->root->left; - while (iter->node && iter->node->left) - iter->node = iter->node->left; + iter->node = node_smallest(tree); pthread_rwlock_unlock(&tree->lock); return iter; @@ -276,7 +435,7 @@ sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter) free(iter); } /* sdb_avltree_iter_destroy */ -_Bool +bool sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter) { if (! iter) @@ -304,5 +463,56 @@ sdb_avltree_size(sdb_avltree_t *tree) return tree ? tree->size : 0; } /* sdb_avltree_size */ +bool +sdb_avltree_valid(sdb_avltree_t *tree) +{ + node_t *n; + + bool status = 1; + size_t size = 0; + + if (! tree) + return 1; + + for (n = node_smallest(tree); n; n = node_next(n)) { + int bf = BALANCE(n); + + if ((bf < -1) || (1 < bf)) { + sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)", + NODE_NAME(n), bf); + status = 0; + } + + if (NODE_HEIGHT(n) != n->height) { + sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': " + "%zu; expected: %zu", NODE_NAME(n), n->height, + NODE_HEIGHT(n)); + status = 0; + } + + if (n->parent && (n->parent->left != n) && (n->parent->right != n)) { + sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of " + "node '%s': {left: %s, right: %s}; expected: %s", + NODE_NAME(n), NODE_NAME(n->parent->left), + NODE_NAME(n->parent->right), NODE_NAME(n)); + status = 0; + } + if ((! n->parent) && (n != tree->root)) { + sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not " + "have a parent", NODE_NAME(n)); + status = 0; + } + + ++size; + } + + if (size != tree->size) { + sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu", + tree->size, size); + status = 0; + } + return status; +} /* sdb_avltree_valid */ + /* vim: set tw=78 sw=4 ts=4 noexpandtab : */