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)
161 assert ((p == NULL) || (p->left == x) || (p->right == x));
164 else if (p->left == x)
169 x->height = calc_height (x);
170 y->height = calc_height (y);
173 } /* void rotate_left */
179 * /_a\ / \ ==> / \ / c\
181 * /_b\ / c\ /_a\ /_b\
184 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
202 assert ((p == NULL) || (p->left == x) || (p->right == x));
205 else if (p->left == x)
210 x->height = calc_height (x);
211 y->height = calc_height (y);
214 } /* void rotate_left */
216 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
218 rotate_left (t, x->left);
219 return (rotate_right (t, x));
220 } /* void rotate_left_right */
222 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
224 rotate_right (t, x->right);
225 return (rotate_left (t, x));
226 } /* void rotate_right_left */
228 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
236 assert ((b_top >= -2) && (b_top <= 2));
240 assert (n->right != NULL);
241 b_bottom = BALANCE (n->right);
242 assert ((b_bottom >= -1) || (b_bottom <= 1));
244 n = rotate_right_left (t, n);
246 n = rotate_left (t, n);
250 assert (n->left != NULL);
251 b_bottom = BALANCE (n->left);
252 assert ((b_bottom >= -1) || (b_bottom <= 1));
254 n = rotate_left_right (t, n);
256 n = rotate_right (t, n);
260 int height = calc_height (n);
261 if (height == n->height)
266 assert (n->height == calc_height (n));
269 } /* while (n != NULL) */
270 } /* void rebalance */
272 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
274 c_avl_node_t *r; /* return node */
281 /* If we can't descent any further, we have to backtrack to the first
282 * parent that's bigger than we, i. e. who's _left_ child we are. */
283 if (n->right == NULL)
286 while ((r != NULL) && (r->parent != NULL))
294 /* n->right == NULL && r == NULL => t is root and has no next
295 * r->left != n => r->right = n => r->parent == NULL */
296 if ((r == NULL) || (r->left != n))
298 assert ((r == NULL) || (r->parent == NULL));
303 assert (r->left == n);
310 while (r->left != NULL)
315 } /* c_avl_node_t *c_avl_node_next */
317 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
319 c_avl_node_t *r; /* return node */
326 /* If we can't descent any further, we have to backtrack to the first
327 * parent that's smaller than we, i. e. who's _right_ child we are. */
331 while ((r != NULL) && (r->parent != NULL))
339 /* n->left == NULL && r == NULL => t is root and has no next
340 * r->right != n => r->left = n => r->parent == NULL */
341 if ((r == NULL) || (r->right != n))
343 assert ((r == NULL) || (r->parent == NULL));
348 assert (r->right == n);
355 while (r->right != NULL)
360 } /* c_avl_node_t *c_avl_node_prev */
362 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
364 assert ((t != NULL) && (n != NULL));
366 if ((n->left != NULL) && (n->right != NULL))
368 c_avl_node_t *r; /* replacement node */
369 if (BALANCE (n) > 0) /* left subtree is higher */
371 assert (n->left != NULL);
372 r = c_avl_node_prev (n);
375 else /* right subtree is higher */
377 assert (n->right != NULL);
378 r = c_avl_node_next (n);
381 assert ((r->left == NULL) || (r->right == NULL));
390 assert ((n->left == NULL) || (n->right == NULL));
392 if ((n->left == NULL) && (n->right == NULL))
394 /* Deleting a leave is easy */
395 if (n->parent == NULL)
397 assert (t->root == n);
402 assert ((n->parent->left == n)
403 || (n->parent->right == n));
404 if (n->parent->left == n)
405 n->parent->left = NULL;
407 n->parent->right = NULL;
409 rebalance (t, n->parent);
414 else if (n->left == NULL)
416 assert (BALANCE (n) == -1);
417 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
418 if (n->parent == NULL)
420 assert (t->root == n);
423 else if (n->parent->left == n)
425 n->parent->left = n->right;
429 n->parent->right = n->right;
431 n->right->parent = n->parent;
433 if (n->parent != NULL)
434 rebalance (t, n->parent);
439 else if (n->right == NULL)
441 assert (BALANCE (n) == 1);
442 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
443 if (n->parent == NULL)
445 assert (t->root == n);
448 else if (n->parent->left == n)
450 n->parent->left = n->left;
454 n->parent->right = n->left;
456 n->left->parent = n->parent;
458 if (n->parent != NULL)
459 rebalance (t, n->parent);
470 } /* void *_remove */
475 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
482 if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
486 t->compare = compare;
492 void c_avl_destroy (c_avl_tree_t *t)
500 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
506 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
526 cmp = t->compare (nptr->key, new->key);
535 if (nptr->right == NULL)
547 else /* if (cmp > 0) */
550 if (nptr->left == NULL)
564 verify_tree (t->root);
567 } /* int c_avl_insert */
569 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
585 status = _remove (t, n);
586 verify_tree (t->root);
589 } /* void *c_avl_remove */
591 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
607 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
612 if ((key == NULL) || (value == NULL))
618 while ((n->left != NULL) || (n->right != NULL))
620 int height_left = (n->left == NULL) ? 0 : n->left->height;
621 int height_right = (n->right == NULL) ? 0 : n->right->height;
623 if (height_left > height_right)
632 else if (p->left == n)
644 } /* int c_avl_pick */
646 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
648 c_avl_iterator_t *iter;
653 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
656 memset (iter, '\0', sizeof (c_avl_iterator_t));
660 } /* c_avl_iterator_t *c_avl_get_iterator */
662 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
666 if ((iter == NULL) || (key == NULL) || (value == NULL))
669 if (iter->node == NULL)
671 for (n = iter->tree->root; n != NULL; n = n->left)
678 n = c_avl_node_next (iter->node);
689 } /* int c_avl_iterator_next */
691 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
695 if ((iter == NULL) || (key == NULL) || (value == NULL))
698 if (iter->node == NULL)
700 for (n = iter->tree->root; n != NULL; n = n->left)
701 if (n->right == NULL)
707 n = c_avl_node_prev (iter->node);
718 } /* int c_avl_iterator_prev */
720 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
725 int c_avl_size (c_avl_tree_t *t)