![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
diff --git a/src/utils/avltree.c b/src/utils/avltree.c
index 7c810599135cf94658791fd1acb5c0a41f759852..f0987f54fdba41cce4f8fd85b9a7b11eb435f86c 100644 (file)
--- a/src/utils/avltree.c
+++ b/src/utils/avltree.c
# include "config.h"
#endif /* HAVE_CONFIG_H */
+#include "sysdb.h"
#include "utils/avltree.h"
+#include "utils/error.h"
#include <assert.h>
#include <stdlib.h>
+#include <string.h>
+#include <strings.h>
#include <pthread.h>
/*
node_t *parent;
node_t *left;
node_t *right;
+
+ size_t height;
};
+#define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
+#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;
};
sdb_object_ref(obj);
n->obj = obj;
n->parent = n->left = n->right = NULL;
+ n->height = 1;
return n;
} /* node_create */
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;
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;
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;
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;
}
while (42) {
assert(parent);
- diff = tree->cmp(obj, parent->obj);
+ diff = strcasecmp(obj->name, parent->obj->name);
if (! diff) {
node_destroy(n);
+ pthread_rwlock_unlock(&tree->lock);
return -1;
}
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)
{
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;
free(iter);
} /* sdb_avltree_iter_destroy */
-_Bool
+bool
sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
{
if (! iter)
return n ? n->obj : NULL;
} /* sdb_avltree_iter_get_next */
+sdb_object_t *
+sdb_avltree_iter_peek_next(sdb_avltree_iter_t *iter)
+{
+ if ((! iter) || (! iter->node))
+ return NULL;
+ return iter->node->obj;
+} /* sdb_avltree_iter_peek_next */
+
size_t
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 : */