2 * collectd - src/utils_avltree.c
3 * Copyright (C) 2006,2007 Florian octo Forster
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
24 * Florian octo Forster <octo at collectd.org>
34 #include "utils_avltree.h"
36 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
37 - (((n)->right == NULL) ? 0 : (n)->right->height))
48 struct c_avl_node_s *left;
49 struct c_avl_node_s *right;
50 struct c_avl_node_s *parent;
52 typedef struct c_avl_node_s c_avl_node_t;
57 int (*compare) (const void *, const void *);
61 struct c_avl_iterator_s
71 static void verify_tree (c_avl_node_t *n)
76 verify_tree (n->left);
77 verify_tree (n->right);
79 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
80 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
81 } /* void verify_tree */
83 # define verify_tree(n) /**/
86 static void free_node (c_avl_node_t *n)
99 static int calc_height (c_avl_node_t *n)
107 height_left = (n->left == NULL) ? 0 : n->left->height;
108 height_right = (n->right == NULL) ? 0 : n->right->height;
110 return (((height_left > height_right)
112 : height_right) + 1);
113 } /* int calc_height */
115 static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
123 cmp = t->compare (key, n->key);
138 * / \ /_c\ ==> / a\ / \
140 * / a\ /_b\ /_b\ /_c\
143 static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
150 assert (x->left != NULL);
164 assert ((p == NULL) || (p->left == x) || (p->right == x));
167 else if (p->left == x)
172 x->height = calc_height (x);
173 y->height = calc_height (y);
176 } /* void rotate_right */
182 * /_a\ / \ ==> / \ / c\
184 * /_b\ / c\ /_a\ /_b\
187 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
194 assert (x->right != NULL);
208 assert ((p == NULL) || (p->left == x) || (p->right == x));
211 else if (p->left == x)
216 x->height = calc_height (x);
217 y->height = calc_height (y);
220 } /* void rotate_left */
222 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
224 rotate_left (t, x->left);
225 return (rotate_right (t, x));
226 } /* void rotate_left_right */
228 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
230 rotate_right (t, x->right);
231 return (rotate_left (t, x));
232 } /* void rotate_right_left */
234 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
242 assert ((b_top >= -2) && (b_top <= 2));
246 assert (n->right != NULL);
247 b_bottom = BALANCE (n->right);
248 assert ((b_bottom >= -1) || (b_bottom <= 1));
250 n = rotate_right_left (t, n);
252 n = rotate_left (t, n);
256 assert (n->left != NULL);
257 b_bottom = BALANCE (n->left);
258 assert ((b_bottom >= -1) || (b_bottom <= 1));
260 n = rotate_left_right (t, n);
262 n = rotate_right (t, n);
266 int height = calc_height (n);
267 if (height == n->height)
272 assert (n->height == calc_height (n));
275 } /* while (n != NULL) */
276 } /* void rebalance */
278 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
280 c_avl_node_t *r; /* return node */
287 /* If we can't descent any further, we have to backtrack to the first
288 * parent that's bigger than we, i. e. who's _left_ child we are. */
289 if (n->right == NULL)
292 while ((r != NULL) && (r->parent != NULL))
300 /* n->right == NULL && r == NULL => t is root and has no next
301 * r->left != n => r->right = n => r->parent == NULL */
302 if ((r == NULL) || (r->left != n))
304 assert ((r == NULL) || (r->parent == NULL));
309 assert (r->left == n);
316 while (r->left != NULL)
321 } /* c_avl_node_t *c_avl_node_next */
323 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
325 c_avl_node_t *r; /* return node */
332 /* If we can't descent any further, we have to backtrack to the first
333 * parent that's smaller than we, i. e. who's _right_ child we are. */
337 while ((r != NULL) && (r->parent != NULL))
345 /* n->left == NULL && r == NULL => t is root and has no next
346 * r->right != n => r->left = n => r->parent == NULL */
347 if ((r == NULL) || (r->right != n))
349 assert ((r == NULL) || (r->parent == NULL));
354 assert (r->right == n);
361 while (r->right != NULL)
366 } /* c_avl_node_t *c_avl_node_prev */
368 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
370 assert ((t != NULL) && (n != NULL));
372 if ((n->left != NULL) && (n->right != NULL))
374 c_avl_node_t *r; /* replacement node */
375 if (BALANCE (n) > 0) /* left subtree is higher */
377 assert (n->left != NULL);
378 r = c_avl_node_prev (n);
381 else /* right subtree is higher */
383 assert (n->right != NULL);
384 r = c_avl_node_next (n);
387 assert ((r->left == NULL) || (r->right == NULL));
396 assert ((n->left == NULL) || (n->right == NULL));
398 if ((n->left == NULL) && (n->right == NULL))
400 /* Deleting a leave is easy */
401 if (n->parent == NULL)
403 assert (t->root == n);
408 assert ((n->parent->left == n)
409 || (n->parent->right == n));
410 if (n->parent->left == n)
411 n->parent->left = NULL;
413 n->parent->right = NULL;
415 rebalance (t, n->parent);
420 else if (n->left == NULL)
422 assert (BALANCE (n) == -1);
423 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
424 if (n->parent == NULL)
426 assert (t->root == n);
429 else if (n->parent->left == n)
431 n->parent->left = n->right;
435 n->parent->right = n->right;
437 n->right->parent = n->parent;
439 if (n->parent != NULL)
440 rebalance (t, n->parent);
445 else if (n->right == NULL)
447 assert (BALANCE (n) == 1);
448 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
449 if (n->parent == NULL)
451 assert (t->root == n);
454 else if (n->parent->left == n)
456 n->parent->left = n->left;
460 n->parent->right = n->left;
462 n->left->parent = n->parent;
464 if (n->parent != NULL)
465 rebalance (t, n->parent);
476 } /* void *_remove */
481 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
488 if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
492 t->compare = compare;
498 void c_avl_destroy (c_avl_tree_t *t)
506 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
512 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
532 cmp = t->compare (nptr->key, new->key);
541 if (nptr->right == NULL)
553 else /* if (cmp > 0) */
556 if (nptr->left == NULL)
570 verify_tree (t->root);
573 } /* int c_avl_insert */
575 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
591 status = _remove (t, n);
592 verify_tree (t->root);
595 } /* void *c_avl_remove */
597 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
613 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
618 if ((key == NULL) || (value == NULL))
624 while ((n->left != NULL) || (n->right != NULL))
631 else if (n->right == NULL)
637 if (n->left->height > n->right->height)
646 else if (p->left == n)
658 } /* int c_avl_pick */
660 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
662 c_avl_iterator_t *iter;
667 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
670 memset (iter, '\0', sizeof (c_avl_iterator_t));
674 } /* c_avl_iterator_t *c_avl_get_iterator */
676 int c_avl_iterator_next (c_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)
692 n = c_avl_node_next (iter->node);
703 } /* int c_avl_iterator_next */
705 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
709 if ((iter == NULL) || (key == NULL) || (value == NULL))
712 if (iter->node == NULL)
714 for (n = iter->tree->root; n != NULL; n = n->left)
715 if (n->right == NULL)
721 n = c_avl_node_prev (iter->node);
732 } /* int c_avl_iterator_prev */
734 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
739 int c_avl_size (c_avl_tree_t *t)