X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Futils_avltree.c;h=3e258e95d8c6834271823cab5aa5cddfc3a4845a;hb=4e57613ae19a71a0f180f0648223a139f48c932c;hp=275cb9b37acb6c651d55cbb301797c3e22723a07;hpb=6b95d15beca00fb69dd4eaceeb101ea49f9fcb04;p=collectd.git

diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index 275cb9b3..3e258e95 100644
--- a/src/utils_avltree.c
+++ b/src/utils_avltree.c
@@ -1,42 +1,84 @@
+/**
+ * collectd - src/utils_avltree.c
+ * Copyright (C) 2006,2007  Florian octo Forster
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
+ *
+ * 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"
 
-#define BALANCE(n) ((((n)->right == NULL) ? 0 : (n)->right->height) \
-				 - (((n)->left == NULL) ? 0 : (n)->left->height))
+#define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
+		- (((n)->right == NULL) ? 0 : (n)->right->height))
 
 /*
  * private data types
  */
-struct avl_node_s
+struct c_avl_node_s
 {
 	void *key;
 	void *value;
 
 	int height;
-	struct avl_node_s *left;
-	struct avl_node_s *right;
-	struct avl_node_s *parent;
+	struct c_avl_node_s *left;
+	struct c_avl_node_s *right;
+	struct c_avl_node_s *parent;
 };
-typedef struct avl_node_s avl_node_t;
+typedef struct c_avl_node_s c_avl_node_t;
 
-struct avl_tree_s
+struct c_avl_tree_s
 {
-	avl_node_t *root;
+	c_avl_node_t *root;
 	int (*compare) (const void *, const void *);
 };
 
-struct avl_iterator_s
+struct c_avl_iterator_s
 {
-	avl_tree_t *tree;
-	avl_node_t *node;
+	c_avl_tree_t *tree;
+	c_avl_node_t *node;
 };
 
 /*
  * private functions
  */
-static void free_node (avl_node_t *n)
+#if 0
+static void verify_tree (c_avl_node_t *n)
+{
+	if (n == NULL)
+		return;
+
+	verify_tree (n->left);
+	verify_tree (n->right);
+
+	assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
+	assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
+} /* void verify_tree */
+#else
+# define verify_tree(n) /**/
+#endif
+
+static void free_node (c_avl_node_t *n)
 {
 	if (n == NULL)
 		return;
@@ -49,9 +91,25 @@ static void free_node (avl_node_t *n)
 	free (n);
 }
 
-static avl_node_t *search (avl_tree_t *t, const void *key)
+static int calc_height (c_avl_node_t *n)
+{
+	int height_left;
+	int height_right;
+
+	if (n == NULL)
+		return (0);
+
+	height_left  = (n->left == NULL)  ? 0 : n->left->height;
+	height_right = (n->right == NULL) ? 0 : n->right->height;
+
+	return (((height_left > height_right)
+				? height_left
+				: height_right) + 1);
+} /* int calc_height */
+
+static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
 {
-	avl_node_t *n;
+	c_avl_node_t *n;
 	int cmp;
 
 	n = t->root;
@@ -69,129 +127,176 @@ static avl_node_t *search (avl_tree_t *t, const void *key)
 	return (NULL);
 }
 
-static void rebalance (avl_tree_t *t, avl_node_t *n)
+/*         (x)             (y)
+ *        /   \           /   \
+ *     (y)    /\         /\    (x)
+ *    /   \  /_c\  ==>  / a\  /   \
+ *   /\   /\           /____\/\   /\
+ *  / a\ /_b\               /_b\ /_c\
+ * /____\
+ */
+static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
 {
-	int height_left;
-	int height_right;
-	int height_new;
-	int cmp;
+	c_avl_node_t *p;
+	c_avl_node_t *y;
+	c_avl_node_t *b;
+
+	p = x->parent;
+	y = x->left;
+	b = y->right;
+
+	x->left = b;
+	if (b != NULL)
+		b->parent = x;
+
+	x->parent = y;
+	y->right = x;
+
+	y->parent = p;
+	assert ((p == NULL) || (p->left == x) || (p->right == x));
+	if (p == NULL)
+		t->root = y;
+	else if (p->left == x)
+		p->left = y;
+	else
+		p->right = y;
 
-	while (n != NULL)
-	{
-		height_left = (n->left == NULL) ? 0 : n->left->height;
-		height_right = (n->right == NULL) ? 0 : n->right->height;
+	x->height = calc_height (x);
+	y->height = calc_height (y);
 
-		height_new = 1 + ((height_left > height_right) ? height_left : height_right);
+	return (y);
+} /* void rotate_left */
 
-		if (height_new == n->height)
-			break;
+/*
+ *    (x)                   (y)
+ *   /   \                 /   \
+ *  /\    (y)           (x)    /\
+ * /_a\  /   \   ==>   /   \  / c\
+ *      /\   /\       /\   /\/____\
+ *     /_b\ / c\     /_a\ /_b\
+ *         /____\
+ */
+static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
+{
+	c_avl_node_t *p;
+	c_avl_node_t *y;
+	c_avl_node_t *b;
+
+	p = x->parent;
+	y = x->right;
+	b = y->left;
+
+	x->right = b;
+	if (b != NULL)
+		b->parent = x;
+
+	x->parent = y;
+	y->left = x;
+
+	y->parent = p;
+	assert ((p == NULL) || (p->left == x) || (p->right == x));
+	if (p == NULL)
+		t->root = y;
+	else if (p->left == x)
+		p->left = y;
+	else
+		p->right = y;
 
-		n->height = height_new;
+	x->height = calc_height (x);
+	y->height = calc_height (y);
 
-		cmp = height_right - height_left;
-		if (cmp < -1)
-		{
-			avl_node_t *l;
-			avl_node_t *lr;
+	return (y);
+} /* void rotate_left */
+
+static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
+{
+	rotate_left (t, x->left);
+	return (rotate_right (t, x));
+} /* void rotate_left_right */
 
-			l = n->left;
-			lr = l->right;
+static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
+{
+	rotate_right (t, x->right);
+	return (rotate_left (t, x));
+} /* void rotate_right_left */
 
-			l->right = n;
-			l->parent = n->parent;
-			n->parent = l;
-			n->left = lr;
+static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
+{
+	int b_top;
+	int b_bottom;
 
-			if (lr != NULL)
-				lr->parent = n;
+	while (n != NULL)
+	{
+		b_top = BALANCE (n);
+		assert ((b_top >= -2) && (b_top <= 2));
 
-			if (l->parent == NULL)
-			{
-				assert (t->root == n);
-				t->root = l;
-			}
+		if (b_top == -2)
+		{
+			assert (n->right != NULL);
+			b_bottom = BALANCE (n->right);
+			assert ((b_bottom >= -1) || (b_bottom <= 1));
+			if (b_bottom == 1)
+				n = rotate_right_left (t, n);
 			else
-			{
-				assert ((l->parent->left == n) || (l->parent->right == n));
-				if (l->parent->left == n)
-					l->parent->left = l;
-				else
-					l->parent->right = l;
-			}
+				n = rotate_left (t, n);
 		}
-		else if (cmp > 1)
+		else if (b_top == 2)
 		{
-			avl_node_t *r;
-			avl_node_t *rl;
-
-			r = n->right;
-			rl = r->left;
-
-			r->left = n;
-			r->parent = n->parent;
-			n->parent = r;
-			n->right = rl;
-
-			if (rl != NULL)
-				rl->parent = n;
-
-			if (r->parent == NULL)
-			{
-				assert (t->root == n);
-				t->root = r;
-			}
+			assert (n->left != NULL);
+			b_bottom = BALANCE (n->left);
+			assert ((b_bottom >= -1) || (b_bottom <= 1));
+			if (b_bottom == -1)
+				n = rotate_left_right (t, n);
 			else
-			{
-				assert ((r->parent->left == n) || (r->parent->right == n));
-				if (r->parent->left == n)
-					r->parent->left = r;
-				else
-					r->parent->right = r;
-			}
+				n = rotate_right (t, n);
 		}
 		else
 		{
-			n = n->parent;
+			int height = calc_height (n);
+			if (height == n->height)
+				break;
+			n->height = height;
 		}
 
-		assert ((n == NULL) || (n->parent == NULL)
-				|| (n->parent->left == n)
-				|| (n->parent->right == n));
+		assert (n->height == calc_height (n));
+
+		n = n->parent;
 	} /* while (n != NULL) */
 } /* void rebalance */
 
-static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
+static c_avl_node_t *c_avl_node_next (c_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)
-{
-	avl_node_t *r; /* return node */
+	c_avl_node_t *r; /* return node */
 
 	if (n == NULL)
 	{
 		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
@@ -202,26 +307,41 @@ void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 	}
 
 	return (r);
-}
+} /* c_avl_node_t *c_avl_node_next */
 
-void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
+static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
 {
-	avl_node_t *r; /* return node */
+	c_avl_node_t *r; /* return node */
 
 	if (n == NULL)
 	{
 		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
@@ -232,12 +352,38 @@ void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 	}
 
 	return (r);
-}
+} /* c_avl_node_t *c_avl_node_prev */
 
-static int _remove (avl_tree_t *t, avl_node_t *n)
+static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
 {
 	assert ((t != NULL) && (n != NULL));
 
+	if ((n->left != NULL) && (n->right != NULL))
+	{
+		c_avl_node_t *r; /* replacement node */
+		if (BALANCE (n) > 0) /* left subtree is higher */
+		{
+			assert (n->left != NULL);
+			r = c_avl_node_prev (n);
+			
+		}
+		else /* right subtree is higher */
+		{
+			assert (n->right != NULL);
+			r = c_avl_node_next (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 */
@@ -260,23 +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->key   = r->key;
-		n->value = r->value;
+		n->right->parent = n->parent;
+
+		if (n->parent != NULL)
+			rebalance (t, n->parent);
+
+		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);
 
-		_remove (t, r);
+		n->left = NULL;
+		free_node (n);
+	}
+	else
+	{
+		assert (0);
 	}
 
 	return (0);
@@ -285,11 +467,14 @@ static int _remove (avl_tree_t *t, avl_node_t *n)
 /*
  * public functions
  */
-avl_tree_t *avl_create (int (*compare) (const void *, const void *))
+c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
 {
-	avl_tree_t *t;
+	c_avl_tree_t *t;
+
+	if (compare == NULL)
+		return (NULL);
 
-	if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
+	if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
 		return (NULL);
 
 	t->root = NULL;
@@ -298,19 +483,19 @@ avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 	return (t);
 }
 
-void avl_destroy (avl_tree_t *t)
+void c_avl_destroy (c_avl_tree_t *t)
 {
 	free_node (t->root);
 	free (t);
 }
 
-int avl_insert (avl_tree_t *t, void *key, void *value)
+int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
 {
-	avl_node_t *new;
-	avl_node_t *nptr;
+	c_avl_node_t *new;
+	c_avl_node_t *nptr;
 	int cmp;
 
-	if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
+	if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
 		return (-1);
 
 	new->key = key;
@@ -333,7 +518,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 		if (cmp == 0)
 		{
 			free_node (new);
-			return (-1);
+			return (1);
 		}
 		else if (cmp < 0)
 		{
@@ -342,7 +527,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 			{
 				nptr->right = new;
 				new->parent = nptr;
-				nptr = NULL;
+				rebalance (t, nptr);
 				break;
 			}
 			else
@@ -357,7 +542,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 			{
 				nptr->left = new;
 				new->parent = nptr;
-				nptr = NULL;
+				rebalance (t, nptr);
 				break;
 			}
 			else
@@ -367,16 +552,14 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 		}
 	} /* while (42) */
 
-	assert ((new->parent != NULL)
-			&& ((new->parent->left == new)
-				|| (new->parent->right == new)));
-
+	verify_tree (t->root);
 	return (0);
-} /* int avl_insert */
+} /* int c_avl_insert */
 
-int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
+int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
 {
-	avl_node_t *n;
+	c_avl_node_t *n;
+	int status;
 
 	assert (t != NULL);
 
@@ -389,73 +572,141 @@ int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 	if (rvalue != NULL)
 		*rvalue = n->value;
 
-	return (_remove (t, n));
-} /* void *avl_remove */
+	status = _remove (t, n);
+	verify_tree (t->root);
+	return (status);
+} /* void *c_avl_remove */
 
-int avl_get (avl_tree_t *t, const void *key, void **value)
+int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
 {
-	avl_node_t *n;
+	c_avl_node_t *n;
 
-	assert (value != NULL);
+	assert (t != NULL);
 
 	n = search (t, key);
 	if (n == NULL)
 		return (-1);
 
-	*value = n->value;
+	if (value != NULL)
+		*value = n->value;
 
 	return (0);
 }
 
-avl_iterator_t *avl_get_iterator (avl_tree_t *t)
+int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
+{
+	c_avl_node_t *n;
+	c_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 c_avl_pick */
+
+c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
 {
-	avl_node_t *n;
+	c_avl_iterator_t *iter;
 
 	if (t == NULL)
 		return (NULL);
 
-	for (n = t->root; n != NULL; n = n->left)
-		if (n->left == NULL)
-			break;
+	iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
+	if (iter == NULL)
+		return (NULL);
+	memset (iter, '\0', sizeof (c_avl_iterator_t));
+	iter->tree = t;
 
-	return (avl_create_iterator (t, n));
-} /* avl_iterator_t *avl_get_iterator */
+	return (iter);
+} /* c_avl_iterator_t *c_avl_get_iterator */
 
-void *avl_iterator_next (avl_iterator_t *iter)
+int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
 {
-	avl_node_t *n;
+	c_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 = c_avl_node_next (iter->node);
+	}
 
 	if (n == NULL)
-		return (NULL);
+		return (-1);
 
 	iter->node = n;
-	return (n);
+	*key = n->key;
+	*value = n->value;
 
-}
+	return (0);
+} /* int c_avl_iterator_next */
 
-void *avl_iterator_prev (avl_iterator_t *iter)
+int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
 {
-	avl_node_t *n;
+	c_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 = c_avl_node_prev (iter->node);
+	}
 
 	if (n == NULL)
-		return (NULL);
+		return (-1);
 
 	iter->node = n;
-	return (n);
+	*key = n->key;
+	*value = n->value;
 
-}
+	return (0);
+} /* int c_avl_iterator_prev */
 
-void avl_iterator_destroy (avl_iterator_t *iter)
+void c_avl_iterator_destroy (c_avl_iterator_t *iter)
 {
 	free (iter);
 }