2 * collectd - src/utils_avltree.c
3 * Copyright (C) 2006,2007 Florian octo Forster
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * Florian octo Forster <octo at verplant.org>
27 #include "utils_avltree.h"
29 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
30 - (((n)->right == NULL) ? 0 : (n)->right->height))
41 struct avl_node_s *left;
42 struct avl_node_s *right;
43 struct avl_node_s *parent;
45 typedef struct avl_node_s avl_node_t;
50 int (*compare) (const void *, const void *);
63 static void verify_tree (avl_node_t *n)
68 verify_tree (n->left);
69 verify_tree (n->right);
71 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
72 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
73 } /* void verify_tree */
75 # define verify_tree(n) /**/
78 static void free_node (avl_node_t *n)
91 static int calc_height (avl_node_t *n)
99 height_left = (n->left == NULL) ? 0 : n->left->height;
100 height_right = (n->right == NULL) ? 0 : n->right->height;
102 return (((height_left > height_right)
104 : height_right) + 1);
105 } /* int calc_height */
107 static avl_node_t *search (avl_tree_t *t, const void *key)
115 cmp = t->compare (key, n->key);
130 * / \ /_c\ ==> / a\ / \
132 * / a\ /_b\ /_b\ /_c\
135 static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
153 assert ((p == NULL) || (p->left == x) || (p->right == x));
156 else if (p->left == x)
161 x->height = calc_height (x);
162 y->height = calc_height (y);
165 } /* void rotate_left */
171 * /_a\ / \ ==> / \ / c\
173 * /_b\ / c\ /_a\ /_b\
176 static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
194 assert ((p == NULL) || (p->left == x) || (p->right == x));
197 else if (p->left == x)
202 x->height = calc_height (x);
203 y->height = calc_height (y);
206 } /* void rotate_left */
208 static avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_t *x)
210 rotate_left (t, x->left);
211 return (rotate_right (t, x));
212 } /* void rotate_left_right */
214 static avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_t *x)
216 rotate_right (t, x->right);
217 return (rotate_left (t, x));
218 } /* void rotate_right_left */
220 static void rebalance (avl_tree_t *t, avl_node_t *n)
228 assert ((b_top >= -2) && (b_top <= 2));
232 assert (n->right != NULL);
233 b_bottom = BALANCE (n->right);
234 assert ((b_bottom >= -1) || (b_bottom <= 1));
236 n = rotate_right_left (t, n);
238 n = rotate_left (t, n);
242 assert (n->left != NULL);
243 b_bottom = BALANCE (n->left);
244 assert ((b_bottom >= -1) || (b_bottom <= 1));
246 n = rotate_left_right (t, n);
248 n = rotate_right (t, n);
252 int height = calc_height (n);
253 if (height == n->height)
258 assert (n->height == calc_height (n));
261 } /* while (n != NULL) */
262 } /* void rebalance */
264 static avl_node_t *avl_node_next (avl_tree_t *t, avl_node_t *n)
266 avl_node_t *r; /* return node */
273 /* If we can't descent any further, we have to backtrack to the first
274 * parent that's bigger than we, i. e. who's _left_ child we are. */
275 if (n->right == NULL)
278 while ((r != NULL) && (r->parent != NULL))
286 /* n->right == NULL && r == NULL => t is root and has no next
287 * r->left != n => r->right = n => r->parent == NULL */
288 if ((r == NULL) || (r->left != n))
290 assert ((r == NULL) || (r->parent == NULL));
295 assert (r->left == n);
302 while (r->left != NULL)
307 } /* avl_node_t *avl_node_next */
309 static avl_node_t *avl_node_prev (avl_tree_t *t, avl_node_t *n)
311 avl_node_t *r; /* return node */
318 /* If we can't descent any further, we have to backtrack to the first
319 * parent that's smaller than we, i. e. who's _right_ child we are. */
323 while ((r != NULL) && (r->parent != NULL))
331 /* n->left == NULL && r == NULL => t is root and has no next
332 * r->right != n => r->left = n => r->parent == NULL */
333 if ((r == NULL) || (r->right != n))
335 assert ((r == NULL) || (r->parent == NULL));
340 assert (r->right == n);
347 while (r->right != NULL)
352 } /* avl_node_t *avl_node_prev */
354 static int _remove (avl_tree_t *t, avl_node_t *n)
356 assert ((t != NULL) && (n != NULL));
358 if ((n->left != NULL) && (n->right != NULL))
360 avl_node_t *r; /* replacement node */
361 if (BALANCE (n) > 0) /* left subtree is higher */
363 assert (n->left != NULL);
364 r = avl_node_prev (t, n);
367 else /* right subtree is higher */
369 assert (n->right != NULL);
370 r = avl_node_next (t, n);
373 assert ((r->left == NULL) || (r->right == NULL));
382 assert ((n->left == NULL) || (n->right == NULL));
384 if ((n->left == NULL) && (n->right == NULL))
386 /* Deleting a leave is easy */
387 if (n->parent == NULL)
389 assert (t->root == n);
394 assert ((n->parent->left == n)
395 || (n->parent->right == n));
396 if (n->parent->left == n)
397 n->parent->left = NULL;
399 n->parent->right = NULL;
401 rebalance (t, n->parent);
406 else if (n->left == NULL)
408 assert (BALANCE (n) == -1);
409 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
410 if (n->parent == NULL)
412 assert (t->root == n);
415 else if (n->parent->left == n)
417 n->parent->left = n->right;
421 n->parent->right = n->right;
423 n->right->parent = n->parent;
425 if (n->parent != NULL)
426 rebalance (t, n->parent);
431 else if (n->right == NULL)
433 assert (BALANCE (n) == 1);
434 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
435 if (n->parent == NULL)
437 assert (t->root == n);
440 else if (n->parent->left == n)
442 n->parent->left = n->left;
446 n->parent->right = n->left;
448 n->left->parent = n->parent;
450 if (n->parent != NULL)
451 rebalance (t, n->parent);
462 } /* void *_remove */
467 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
474 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
478 t->compare = compare;
483 void avl_destroy (avl_tree_t *t)
489 int avl_insert (avl_tree_t *t, void *key, void *value)
495 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
514 cmp = t->compare (nptr->key, new->key);
523 if (nptr->right == NULL)
535 else /* if (cmp > 0) */
538 if (nptr->left == NULL)
552 verify_tree (t->root);
554 } /* int avl_insert */
556 int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue)
572 status = _remove (t, n);
573 verify_tree (t->root);
575 } /* void *avl_remove */
577 int avl_get (avl_tree_t *t, const void *key, void **value)
581 assert (value != NULL);
592 int avl_pick (avl_tree_t *t, void **key, void **value)
597 if ((key == NULL) || (value == NULL))
603 while ((n->left != NULL) || (n->right != NULL))
605 int height_left = (n->left == NULL) ? 0 : n->left->height;
606 int height_right = (n->right == NULL) ? 0 : n->right->height;
608 if (height_left > height_right)
617 else if (p->left == n)
631 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
633 avl_iterator_t *iter;
638 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
641 memset (iter, '\0', sizeof (avl_iterator_t));
645 } /* avl_iterator_t *avl_get_iterator */
647 int avl_iterator_next (avl_iterator_t *iter, void **key, void **value)
651 if ((iter == NULL) || (key == NULL) || (value == NULL))
654 if (iter->node == NULL)
656 for (n = iter->tree->root; n != NULL; n = n->left)
663 n = avl_node_next (iter->tree, iter->node);
674 } /* int avl_iterator_next */
676 int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value)
680 if ((iter == NULL) || (key == NULL) || (value == NULL))
683 if (iter->node == NULL)
685 for (n = iter->tree->root; n != NULL; n = n->left)
686 if (n->right == NULL)
692 n = avl_node_prev (iter->tree, iter->node);
703 } /* int avl_iterator_prev */
705 void avl_iterator_destroy (avl_iterator_t *iter)