src/utils_avltree.c: Fix and endless loop. Added more `assert's.

[collectd.git] / src / utils_avltree.c

diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index 3665760..f2c5d06 100644 (file)
--- a/src/utils_avltree.c
+++ b/src/utils_avltree.c
@@ -49,7 +49,7 @@ static void free_node (avl_node_t *n)
        free (n);
 }
 
-static avl_node_t *search (avl_tree_t *t, void *key)
+static avl_node_t *search (avl_tree_t *t, const void *key)
 {
        avl_node_t *n;
        int cmp;
@@ -86,6 +86,18 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
                if (height_new == n->height)
                        break;
 
+               /* FIXME */
+               if (n->left != NULL)
+               {
+                       cmp = BALANCE(n->left);
+                       assert ((cmp >= -1) && (cmp <= 1));
+               }
+               if (n->right != NULL)
+               {
+                       cmp = BALANCE(n->right);
+                       assert ((cmp >= -1) && (cmp <= 1));
+               }
+
                n->height = height_new;
 
                cmp = height_right - height_left;
@@ -118,6 +130,24 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
                                else
                                        l->parent->right = l;
                        }
+
+                       height_left = (n->left == NULL) ? 0 : n->left->height;
+                       height_right = (n->right == NULL) ? 0 : n->right->height;
+                       height_new = 1 + ((height_left > height_right) ? height_left : height_right);
+                       cmp = BALANCE(n);
+                       assert (height_new < n->height);
+                       assert ((cmp >= -1) || (cmp <= 1));
+                       n->height = height_new;
+
+                       height_left = (l->left == NULL) ? 0 : l->left->height;
+                       height_right = (l->right == NULL) ? 0 : l->right->height;
+                       height_new = 1 + ((height_left > height_right) ? height_left : height_right);
+                       cmp = BALANCE(l);
+                       assert (height_new >= l->height);
+                       assert ((cmp >= -1) || (cmp <= 1));
+                       l->height = height_new;
+
+                       n = l->parent;
                }
                else if (cmp > 1)
                {
@@ -148,6 +178,24 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
                                else
                                        r->parent->right = r;
                        }
+
+                       height_left = (n->left == NULL) ? 0 : n->left->height;
+                       height_right = (n->right == NULL) ? 0 : n->right->height;
+                       height_new = 1 + ((height_left > height_right) ? height_left : height_right);
+                       cmp = BALANCE(n);
+                       assert (height_new < n->height);
+                       assert ((cmp >= -1) || (cmp <= 1));
+                       n->height = height_new;
+
+                       height_left = (r->left == NULL) ? 0 : r->left->height;
+                       height_right = (r->right == NULL) ? 0 : r->right->height;
+                       height_new = 1 + ((height_left > height_right) ? height_left : height_right);
+                       cmp = BALANCE(r);
+                       assert (height_new >= r->height);
+                       assert ((cmp >= -1) || (cmp <= 1));
+                       r->height = height_new;
+
+                       n = r->parent;
                }
                else
                {
@@ -234,14 +282,10 @@ void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
        return (r);
 }
 
-static void *_remove (avl_tree_t *t, avl_node_t *n)
+static int _remove (avl_tree_t *t, avl_node_t *n)
 {
-       void *ret;
-
        assert ((t != NULL) && (n != NULL));
 
-       ret = n->value;
-
        if ((n->left == NULL) && (n->right == NULL))
        {
                /* Deleting a leave is easy */
@@ -283,7 +327,7 @@ static void *_remove (avl_tree_t *t, avl_node_t *n)
                _remove (t, r);
        }
 
-       return (ret);
+       return (0);
 } /* void *_remove */
 
 /*
@@ -378,7 +422,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
        return (0);
 } /* int avl_insert */
 
-void *avl_remove (avl_tree_t *t, void *key)
+int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 {
        avl_node_t *n;
 
@@ -386,20 +430,29 @@ void *avl_remove (avl_tree_t *t, void *key)
 
        n = search (t, key);
        if (n == NULL)
-               return (NULL);
+               return (-1);
+
+       if (rkey != NULL)
+               *rkey = n->key;
+       if (rvalue != NULL)
+               *rvalue = n->value;
 
        return (_remove (t, n));
 } /* void *avl_remove */
 
-void *avl_get (avl_tree_t *t, void *key)
+int avl_get (avl_tree_t *t, const void *key, void **value)
 {
        avl_node_t *n;
 
+       assert (value != NULL);
+
        n = search (t, key);
        if (n == NULL)
-               return (NULL);
+               return (-1);
 
-       return (n->value);
+       *value = n->value;
+
+       return (0);
 }
 
 avl_iterator_t *avl_get_iterator (avl_tree_t *t)