+/**
+ * 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 <stdlib.h>
+#include <stdio.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
/*
* private functions
*/
+#if 0
+static void verify_tree (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 (avl_node_t *n)
{
if (n == NULL)
free (n);
}
+static int calc_height (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 avl_node_t *search (avl_tree_t *t, const void *key)
{
avl_node_t *n;
return (NULL);
}
-static void rebalance (avl_tree_t *t, avl_node_t *n)
+/* (x) (y)
+ * / \ / \
+ * (y) /\ /\ (x)
+ * / \ /_c\ ==> / a\ / \
+ * /\ /\ /____\/\ /\
+ * / a\ /_b\ /_b\ /_c\
+ * /____\
+ */
+static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
{
- int height_left;
- int height_right;
- int height_new;
- int cmp;
+ avl_node_t *p;
+ avl_node_t *y;
+ 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 avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
+{
+ avl_node_t *p;
+ avl_node_t *y;
+ 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;
- /* 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));
- }
+ x->height = calc_height (x);
+ y->height = calc_height (y);
- n->height = height_new;
+ return (y);
+} /* void rotate_left */
- cmp = height_right - height_left;
- if (cmp < -1)
- {
- avl_node_t *l;
- avl_node_t *lr;
+static avl_node_t *rotate_left_right (avl_tree_t *t, 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 avl_node_t *rotate_right_left (avl_tree_t *t, 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 (avl_tree_t *t, 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;
- }
-
- 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;
+ 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;
- }
-
- 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;
+ 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 */
}
return (r);
-}
+} /* void *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 */
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);
- _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);
{
nptr->right = new;
new->parent = nptr;
- nptr = NULL;
+ rebalance (t, nptr);
break;
}
else
{
nptr->left = new;
new->parent = nptr;
- nptr = NULL;
+ rebalance (t, nptr);
break;
}
else
}
} /* while (42) */
- assert ((new->parent != NULL)
- && ((new->parent->left == new)
- || (new->parent->right == new)));
-
+ verify_tree (t->root);
return (0);
} /* int avl_insert */
int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
{
avl_node_t *n;
+ int status;
assert (t != NULL);
if (rvalue != NULL)
*rvalue = n->value;
- return (_remove (t, n));
+ status = _remove (t, n);
+ verify_tree (t->root);
+ return (status);
} /* void *avl_remove */
int avl_get (avl_tree_t *t, const void *key, void **value)
return (avl_create_iterator (t, n));
} /* avl_iterator_t *avl_get_iterator */
+int avl_pick (avl_tree_t *t, void **key, void **value)
+{
+ avl_node_t *n;
+ avl_node_t *p;
+
+ assert ((key != NULL) && (value != NULL));
+ 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 */
+
void *avl_iterator_next (avl_iterator_t *iter)
{
avl_node_t *n;
projects / collectd.git / blobdiff