Include strings.h instead of defining _BSD_SOURCE to get strcasecmp.

[sysdb.git] / src / utils / avltree.c

diff --git a/src/utils/avltree.c b/src/utils/avltree.c
index 353a3849c2c307c975413d72a9dba64dfc0f7258..f0987f54fdba41cce4f8fd85b9a7b11eb435f86c 100644 (file)
--- a/src/utils/avltree.c
+++ b/src/utils/avltree.c
@@ -36,6 +36,8 @@
 #include <assert.h>
 
 #include <stdlib.h>
+#include <string.h>
+#include <strings.h>
 #include <pthread.h>
 
 /*
@@ -66,8 +68,6 @@ struct node {
 struct sdb_avltree {
        pthread_rwlock_t lock;
 
-       sdb_object_cmp_cb cmp;
-
        node_t *root;
        size_t size;
 };
@@ -155,9 +155,30 @@ tree_clear(sdb_avltree_t *tree)
 {
        node_t *n;
 
-       n = node_smallest(tree);
+       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;
@@ -260,7 +281,7 @@ rebalance(sdb_avltree_t *tree, node_t *n)
  */
 
 sdb_avltree_t *
-sdb_avltree_create(sdb_object_cmp_cb cmp)
+sdb_avltree_create(void)
 {
        sdb_avltree_t *tree;
 
@@ -268,11 +289,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;
@@ -331,7 +348,7 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
        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);
@@ -362,6 +379,31 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
        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)
 {
@@ -394,7 +436,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)
@@ -416,18 +458,26 @@ sdb_avltree_iter_get_next(sdb_avltree_iter_t *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
+bool
 sdb_avltree_valid(sdb_avltree_t *tree)
 {
        node_t *n;
 
-       _Bool status = 1;
+       bool status = 1;
        size_t size = 0;
 
        if (! tree)