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>
30 #include "utils_avltree.h"
32 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
33 - (((n)->right == NULL) ? 0 : (n)->right->height))
44 struct c_avl_node_s *left;
45 struct c_avl_node_s *right;
46 struct c_avl_node_s *parent;
48 typedef struct c_avl_node_s c_avl_node_t;
53 int (*compare) (const void *, const void *);
57 struct c_avl_iterator_s
67 static void verify_tree (c_avl_node_t *n)
72 verify_tree (n->left);
73 verify_tree (n->right);
75 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
76 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
77 } /* void verify_tree */
79 # define verify_tree(n) /**/
82 static void free_node (c_avl_node_t *n)
95 static int calc_height (c_avl_node_t *n)
103 height_left = (n->left == NULL) ? 0 : n->left->height;
104 height_right = (n->right == NULL) ? 0 : n->right->height;
106 return (((height_left > height_right)
108 : height_right) + 1);
109 } /* int calc_height */
111 static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
119 cmp = t->compare (key, n->key);
134 * / \ /_c\ ==> / a\ / \
136 * / a\ /_b\ /_b\ /_c\
139 static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
157 assert ((p == NULL) || (p->left == x) || (p->right == x));
160 else if (p->left == x)
165 x->height = calc_height (x);
166 y->height = calc_height (y);
169 } /* void rotate_left */
175 * /_a\ / \ ==> / \ / c\
177 * /_b\ / c\ /_a\ /_b\
180 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
198 assert ((p == NULL) || (p->left == x) || (p->right == x));
201 else if (p->left == x)
206 x->height = calc_height (x);
207 y->height = calc_height (y);
210 } /* void rotate_left */
212 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
214 rotate_left (t, x->left);
215 return (rotate_right (t, x));
216 } /* void rotate_left_right */
218 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
220 rotate_right (t, x->right);
221 return (rotate_left (t, x));
222 } /* void rotate_right_left */
224 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
232 assert ((b_top >= -2) && (b_top <= 2));
236 assert (n->right != NULL);
237 b_bottom = BALANCE (n->right);
238 assert ((b_bottom >= -1) || (b_bottom <= 1));
240 n = rotate_right_left (t, n);
242 n = rotate_left (t, n);
246 assert (n->left != NULL);
247 b_bottom = BALANCE (n->left);
248 assert ((b_bottom >= -1) || (b_bottom <= 1));
250 n = rotate_left_right (t, n);
252 n = rotate_right (t, n);
256 int height = calc_height (n);
257 if (height == n->height)
262 assert (n->height == calc_height (n));
265 } /* while (n != NULL) */
266 } /* void rebalance */
268 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
270 c_avl_node_t *r; /* return node */
277 /* If we can't descent any further, we have to backtrack to the first
278 * parent that's bigger than we, i. e. who's _left_ child we are. */
279 if (n->right == NULL)
282 while ((r != NULL) && (r->parent != NULL))
290 /* n->right == NULL && r == NULL => t is root and has no next
291 * r->left != n => r->right = n => r->parent == NULL */
292 if ((r == NULL) || (r->left != n))
294 assert ((r == NULL) || (r->parent == NULL));
299 assert (r->left == n);
306 while (r->left != NULL)
311 } /* c_avl_node_t *c_avl_node_next */
313 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
315 c_avl_node_t *r; /* return node */
322 /* If we can't descent any further, we have to backtrack to the first
323 * parent that's smaller than we, i. e. who's _right_ child we are. */
327 while ((r != NULL) && (r->parent != NULL))
335 /* n->left == NULL && r == NULL => t is root and has no next
336 * r->right != n => r->left = n => r->parent == NULL */
337 if ((r == NULL) || (r->right != n))
339 assert ((r == NULL) || (r->parent == NULL));
344 assert (r->right == n);
351 while (r->right != NULL)
356 } /* c_avl_node_t *c_avl_node_prev */
358 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
360 assert ((t != NULL) && (n != NULL));
362 if ((n->left != NULL) && (n->right != NULL))
364 c_avl_node_t *r; /* replacement node */
365 if (BALANCE (n) > 0) /* left subtree is higher */
367 assert (n->left != NULL);
368 r = c_avl_node_prev (n);
371 else /* right subtree is higher */
373 assert (n->right != NULL);
374 r = c_avl_node_next (n);
377 assert ((r->left == NULL) || (r->right == NULL));
386 assert ((n->left == NULL) || (n->right == NULL));
388 if ((n->left == NULL) && (n->right == NULL))
390 /* Deleting a leave is easy */
391 if (n->parent == NULL)
393 assert (t->root == n);
398 assert ((n->parent->left == n)
399 || (n->parent->right == n));
400 if (n->parent->left == n)
401 n->parent->left = NULL;
403 n->parent->right = NULL;
405 rebalance (t, n->parent);
410 else if (n->left == NULL)
412 assert (BALANCE (n) == -1);
413 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
414 if (n->parent == NULL)
416 assert (t->root == n);
419 else if (n->parent->left == n)
421 n->parent->left = n->right;
425 n->parent->right = n->right;
427 n->right->parent = n->parent;
429 if (n->parent != NULL)
430 rebalance (t, n->parent);
435 else if (n->right == NULL)
437 assert (BALANCE (n) == 1);
438 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
439 if (n->parent == NULL)
441 assert (t->root == n);
444 else if (n->parent->left == n)
446 n->parent->left = n->left;
450 n->parent->right = n->left;
452 n->left->parent = n->parent;
454 if (n->parent != NULL)
455 rebalance (t, n->parent);
466 } /* void *_remove */
471 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
478 if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
482 t->compare = compare;
488 void c_avl_destroy (c_avl_tree_t *t)
496 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
502 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
522 cmp = t->compare (nptr->key, new->key);
531 if (nptr->right == NULL)
543 else /* if (cmp > 0) */
546 if (nptr->left == NULL)
560 verify_tree (t->root);
563 } /* int c_avl_insert */
565 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
581 status = _remove (t, n);
582 verify_tree (t->root);
585 } /* void *c_avl_remove */
587 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
603 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
608 if ((key == NULL) || (value == NULL))
614 while ((n->left != NULL) || (n->right != NULL))
616 int height_left = (n->left == NULL) ? 0 : n->left->height;
617 int height_right = (n->right == NULL) ? 0 : n->right->height;
619 if (height_left > height_right)
628 else if (p->left == n)
640 } /* int c_avl_pick */
642 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
644 c_avl_iterator_t *iter;
649 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
652 memset (iter, '\0', sizeof (c_avl_iterator_t));
656 } /* c_avl_iterator_t *c_avl_get_iterator */
658 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
662 if ((iter == NULL) || (key == NULL) || (value == NULL))
665 if (iter->node == NULL)
667 for (n = iter->tree->root; n != NULL; n = n->left)
674 n = c_avl_node_next (iter->node);
685 } /* int c_avl_iterator_next */
687 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
691 if ((iter == NULL) || (key == NULL) || (value == NULL))
694 if (iter->node == NULL)
696 for (n = iter->tree->root; n != NULL; n = n->left)
697 if (n->right == NULL)
703 n = c_avl_node_prev (iter->node);
714 } /* int c_avl_iterator_prev */
716 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
721 int c_avl_size (c_avl_tree_t *t)