X-Git-Url: https://git.verplant.org/?a=blobdiff_plain;f=src%2Futils_avltree.c;h=09cf2e6fee238f246780d5b191d22bb54f6c6f14;hb=63cbff115ba03717e81087d1419fc07c24d205c2;hp=f6b15b153844ec177eef8ea51eb68a65c89152e5;hpb=312e8cdc9c83155cd1fa0eab1509d0cc25d7a8e6;p=collectd.git

diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index f6b15b15..09cf2e6f 100644
--- a/src/utils_avltree.c
+++ b/src/utils_avltree.c
@@ -19,8 +19,12 @@
  * Authors:
  *   Florian octo Forster <octo at verplant.org>
  **/
+
+#include "config.h"
+
 #include <stdlib.h>
 #include <stdio.h>
+#include <string.h>
 #include <assert.h>
 
 #include "utils_avltree.h"
@@ -58,7 +62,7 @@ struct avl_iterator_s
 /*
  * private functions
  */
-#if 1
+#if 0
 static void verify_tree (avl_node_t *n)
 {
 	if (n == NULL)
@@ -230,17 +234,17 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
 		{
 			assert (n->right != NULL);
 			b_bottom = BALANCE (n->right);
-			assert ((b_bottom == -1) || (b_bottom == 1));
-			if (b_bottom == -1)
-				n = rotate_left (t, n);
-			else
+			assert ((b_bottom >= -1) || (b_bottom <= 1));
+			if (b_bottom == 1)
 				n = rotate_right_left (t, n);
+			else
+				n = rotate_left (t, n);
 		}
 		else if (b_top == 2)
 		{
 			assert (n->left != NULL);
 			b_bottom = BALANCE (n->left);
-			assert ((b_bottom == -1) || (b_bottom == 1));
+			assert ((b_bottom >= -1) || (b_bottom <= 1));
 			if (b_bottom == -1)
 				n = rotate_left_right (t, n);
 			else
@@ -260,21 +264,7 @@ static void rebalance (avl_tree_t *t, avl_node_t *n)
 	} /* while (n != NULL) */
 } /* void rebalance */
 
-static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
-{
-	avl_iterator_t *iter;
-
-	iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
-	if (iter == NULL)
-		return (NULL);
-
-	iter->tree = t;
-	iter->node = n;
-
-	return (iter);
-}
-
-void *avl_node_next (avl_tree_t *t, avl_node_t *n)
+static avl_node_t *avl_node_next (avl_tree_t *t, avl_node_t *n)
 {
 	avl_node_t *r; /* return node */
 
@@ -282,16 +272,31 @@ void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 	{
 		return (NULL);
 	}
-	else if (n->right == NULL)
-	{
 
+	/* If we can't descent any further, we have to backtrack to the first
+	 * parent that's bigger than we, i. e. who's _left_ child we are. */
+	if (n->right == NULL)
+	{
 		r = n->parent;
-		while (r != NULL)
+		while ((r != NULL) && (r->parent != NULL))
 		{
-			/* stop if a bigger node is found */
-			if (t->compare (n, r) < 0) /* n < r */
+			if (r->left == n)
 				break;
-			r = r->parent;
+			n = r;
+			r = n->parent;
+		}
+
+		/* n->right == NULL && r == NULL => t is root and has no next
+		 * r->left != n => r->right = n => r->parent == NULL */
+		if ((r == NULL) || (r->left != n))
+		{
+			assert ((r == NULL) || (r->parent == NULL));
+			return (NULL);
+		}
+		else
+		{
+			assert (r->left == n);
+			return (r);
 		}
 	}
 	else
@@ -302,9 +307,9 @@ void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 	}
 
 	return (r);
-}
+} /* avl_node_t *avl_node_next */
 
-void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
+static avl_node_t *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 {
 	avl_node_t *r; /* return node */
 
@@ -312,16 +317,31 @@ void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 	{
 		return (NULL);
 	}
-	else if (n->left == NULL)
-	{
 
+	/* If we can't descent any further, we have to backtrack to the first
+	 * parent that's smaller than we, i. e. who's _right_ child we are. */
+	if (n->left == NULL)
+	{
 		r = n->parent;
-		while (r != NULL)
+		while ((r != NULL) && (r->parent != NULL))
 		{
-			/* stop if a smaller node is found */
-			if (t->compare (n, r) > 0) /* n > r */
+			if (r->right == n)
 				break;
-			r = r->parent;
+			n = r;
+			r = n->parent;
+		}
+
+		/* n->left == NULL && r == NULL => t is root and has no next
+		 * r->right != n => r->left = n => r->parent == NULL */
+		if ((r == NULL) || (r->right != n))
+		{
+			assert ((r == NULL) || (r->parent == NULL));
+			return (NULL);
+		}
+		else
+		{
+			assert (r->right == n);
+			return (r);
 		}
 	}
 	else
@@ -332,12 +352,38 @@ void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 	}
 
 	return (r);
-}
+} /* avl_node_t *avl_node_prev */
 
 static int _remove (avl_tree_t *t, avl_node_t *n)
 {
 	assert ((t != NULL) && (n != NULL));
 
+	if ((n->left != NULL) && (n->right != NULL))
+	{
+		avl_node_t *r; /* replacement node */
+		if (BALANCE (n) > 0) /* left subtree is higher */
+		{
+			assert (n->left != NULL);
+			r = avl_node_prev (t, n);
+			
+		}
+		else /* right subtree is higher */
+		{
+			assert (n->right != NULL);
+			r = avl_node_next (t, n);
+		}
+
+		assert ((r->left == NULL) || (r->right == NULL));
+
+		/* copy content */
+		n->key   = r->key;
+		n->value = r->value;
+
+		n = r;
+	}
+
+	assert ((n->left == NULL) || (n->right == NULL));
+
 	if ((n->left == NULL) && (n->right == NULL))
 	{
 		/* Deleting a leave is easy */
@@ -360,25 +406,59 @@ static int _remove (avl_tree_t *t, avl_node_t *n)
 
 		free_node (n);
 	}
-	else
+	else if (n->left == NULL)
 	{
-		avl_node_t *r; /* replacement node */
-		if (BALANCE (n) > 0)
+		assert (BALANCE (n) == -1);
+		assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
+		if (n->parent == NULL)
 		{
-			assert (n->left != NULL);
-			r = avl_node_prev (t, n);
+			assert (t->root == n);
+			t->root = n->right;
+		}
+		else if (n->parent->left == n)
+		{
+			n->parent->left = n->right;
 		}
 		else
 		{
-			assert (n->right != NULL);
-			r = avl_node_next (t, n);
+			n->parent->right = n->right;
 		}
+		n->right->parent = n->parent;
 
-		/* copy content */
-		n->key   = r->key;
-		n->value = r->value;
+		if (n->parent != NULL)
+			rebalance (t, n->parent);
 
-		_remove (t, r);
+		n->right = NULL;
+		free_node (n);
+	}
+	else if (n->right == NULL)
+	{
+		assert (BALANCE (n) == 1);
+		assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
+		if (n->parent == NULL)
+		{
+			assert (t->root == n);
+			t->root = n->left;
+		}
+		else if (n->parent->left == n)
+		{
+			n->parent->left = n->left;
+		}
+		else
+		{
+			n->parent->right = n->left;
+		}
+		n->left->parent = n->parent;
+
+		if (n->parent != NULL)
+			rebalance (t, n->parent);
+
+		n->left = NULL;
+		free_node (n);
+	}
+	else
+	{
+		assert (0);
 	}
 
 	return (0);
@@ -391,6 +471,9 @@ avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 {
 	avl_tree_t *t;
 
+	if (compare == NULL)
+		return (NULL);
+
 	if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 		return (NULL);
 
@@ -473,7 +556,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 	return (0);
 } /* int avl_insert */
 
-int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
+int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue)
 {
 	avl_node_t *n;
 	int status;
@@ -509,53 +592,118 @@ int avl_get (avl_tree_t *t, const void *key, void **value)
 	return (0);
 }
 
-avl_iterator_t *avl_get_iterator (avl_tree_t *t)
+int avl_pick (avl_tree_t *t, void **key, void **value)
 {
 	avl_node_t *n;
+	avl_node_t *p;
+
+	if ((key == NULL) || (value == NULL))
+		return (-1);
+	if (t->root == NULL)
+		return (-1);
+
+	n = t->root;
+	while ((n->left != NULL) || (n->right != NULL))
+	{
+		int height_left  = (n->left  == NULL) ? 0 : n->left->height;
+		int height_right = (n->right == NULL) ? 0 : n->right->height;
+
+		if (height_left > height_right)
+			n = n->left;
+		else
+			n = n->right;
+	}
+
+	p = n->parent;
+	if (p == NULL)
+		t->root = NULL;
+	else if (p->left == n)
+		p->left = NULL;
+	else
+		p->right = NULL;
+
+	*key   = n->key;
+	*value = n->value;
+
+	free_node (n);
+	rebalance (t, p);
+
+	return (0);
+} /* int avl_pick */
+
+avl_iterator_t *avl_get_iterator (avl_tree_t *t)
+{
+	avl_iterator_t *iter;
 
 	if (t == NULL)
 		return (NULL);
 
-	for (n = t->root; n != NULL; n = n->left)
-		if (n->left == NULL)
-			break;
+	iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
+	if (iter == NULL)
+		return (NULL);
+	memset (iter, '\0', sizeof (avl_iterator_t));
+	iter->tree = t;
 
-	return (avl_create_iterator (t, n));
+	return (iter);
 } /* avl_iterator_t *avl_get_iterator */
 
-void *avl_iterator_next (avl_iterator_t *iter)
+int avl_iterator_next (avl_iterator_t *iter, void **key, void **value)
 {
 	avl_node_t *n;
 
-	if ((iter == NULL) || (iter->node == NULL))
-		return (NULL);
+	if ((iter == NULL) || (key == NULL) || (value == NULL))
+		return (-1);
 
-	n = avl_node_next (iter->tree, iter->node);
+	if (iter->node == NULL)
+	{
+		for (n = iter->tree->root; n != NULL; n = n->left)
+			if (n->left == NULL)
+				break;
+		iter->node = n;
+	}
+	else
+	{
+		n = avl_node_next (iter->tree, iter->node);
+	}
 
 	if (n == NULL)
-		return (NULL);
+		return (-1);
 
 	iter->node = n;
-	return (n);
+	*key = n->key;
+	*value = n->value;
 
-}
+	return (0);
+} /* int avl_iterator_next */
 
-void *avl_iterator_prev (avl_iterator_t *iter)
+int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value)
 {
 	avl_node_t *n;
 
-	if ((iter == NULL) || (iter->node == NULL))
-		return (NULL);
+	if ((iter == NULL) || (key == NULL) || (value == NULL))
+		return (-1);
 
-	n = avl_node_prev (iter->tree, iter->node);
+	if (iter->node == NULL)
+	{
+		for (n = iter->tree->root; n != NULL; n = n->left)
+			if (n->right == NULL)
+				break;
+		iter->node = n;
+	}
+	else
+	{
+		n = avl_node_prev (iter->tree, iter->node);
+	}
 
 	if (n == NULL)
-		return (NULL);
+		return (-1);
 
 	iter->node = n;
-	return (n);
+	*key = n->key;
+	*value = n->value;
 
-}
+	return (0);
+} /* int avl_iterator_prev */
 
 void avl_iterator_destroy (avl_iterator_t *iter)
 {