src/utils_avltree.[ch]: Changed the interface to return the key upon deletion.

[collectd.git] / src / utils_avltree.c

diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index c3e83ae..275cb9b 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,8 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
                if (height_new == n->height)
                        break;
 
+               n->height = height_new;
+
                cmp = height_right - height_left;
                if (cmp < -1)
                {
@@ -100,8 +102,22 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
                        n->parent = l;
                        n->left = lr;
 
-                       if (n == t->root)
+                       if (lr != NULL)
+                               lr->parent = n;
+
+                       if (l->parent == NULL)
+                       {
+                               assert (t->root == n);
                                t->root = l;
+                       }
+                       else
+                       {
+                               assert ((l->parent->left == n) || (l->parent->right == n));
+                               if (l->parent->left == n)
+                                       l->parent->left = l;
+                               else
+                                       l->parent->right = l;
+                       }
                }
                else if (cmp > 1)
                {
@@ -116,13 +132,31 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
                        n->parent = r;
                        n->right = rl;
 
-                       if (n == t->root)
+                       if (rl != NULL)
+                               rl->parent = n;
+
+                       if (r->parent == NULL)
+                       {
+                               assert (t->root == n);
                                t->root = r;
+                       }
+                       else
+                       {
+                               assert ((r->parent->left == n) || (r->parent->right == n));
+                               if (r->parent->left == n)
+                                       r->parent->left = r;
+                               else
+                                       r->parent->right = r;
+                       }
                }
                else
                {
                        n = n->parent;
                }
+
+               assert ((n == NULL) || (n->parent == NULL)
+                               || (n->parent->left == n)
+                               || (n->parent->right == n));
        } /* while (n != NULL) */
 } /* void rebalance */
 
@@ -200,14 +234,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 */
@@ -224,6 +254,8 @@ static void *remove (avl_tree_t *t, avl_node_t *n)
                                n->parent->left = NULL;
                        else
                                n->parent->right = NULL;
+
+                       rebalance (t, n->parent);
                }
 
                free_node (n);
@@ -244,11 +276,11 @@ static void *remove (avl_tree_t *t, avl_node_t *n)
                n->key   = r->key;
                n->value = r->value;
 
-               remove (t, r);
+               _remove (t, r);
        }
 
-       return (ret);
-} /* void *remove */
+       return (0);
+} /* void *_remove */
 
 /*
  * public functions
@@ -283,7 +315,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 
        new->key = key;
        new->value = value;
-       new->height = 0;
+       new->height = 1;
        new->left = NULL;
        new->right = NULL;
 
@@ -335,12 +367,14 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
                }
        } /* while (42) */
 
-       rebalance (t, new->parent);
+       assert ((new->parent != NULL)
+                       && ((new->parent->left == new)
+                               || (new->parent->right == new)));
 
        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;
 
@@ -348,20 +382,29 @@ void *avl_remove (avl_tree_t *t, void *key)
 
        n = search (t, key);
        if (n == NULL)
-               return (NULL);
+               return (-1);
 
-       return (remove (t, n));
+       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);
+
+       *value = n->value;
 
-       return (n->value);
+       return (0);
 }
 
 avl_iterator_t *avl_get_iterator (avl_tree_t *t)