diff --git a/src/utils/avltree.c b/src/utils/avltree.c
index 8c13233b2eabb6dd7f3fbfd3e408eaccf99f5a0f..87db2f78d0e9b8e7c1eee042af3f32de0c697887 100644 (file)
--- a/src/utils/avltree.c
+++ b/src/utils/avltree.c
#include "sysdb.h"
#include "utils/avltree.h"
+#include "utils/error.h"
#include <assert.h>
#include <stdlib.h>
+#include <string.h>
#include <pthread.h>
/*
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)
struct sdb_avltree {
pthread_rwlock_t lock;
- sdb_object_cmp_cb cmp;
-
node_t *root;
size_t size;
};
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;
*/
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;
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 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 : */