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>
26 #include "utils_avltree.h"
28 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
29 - (((n)->right == NULL) ? 0 : (n)->right->height))
40 struct avl_node_s *left;
41 struct avl_node_s *right;
42 struct avl_node_s *parent;
44 typedef struct avl_node_s avl_node_t;
49 int (*compare) (const void *, const void *);
62 static void verify_tree (avl_node_t *n)
67 verify_tree (n->left);
68 verify_tree (n->right);
70 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
71 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
72 } /* void verify_tree */
74 # define verify_tree(n) /**/
77 static void free_node (avl_node_t *n)
90 static int calc_height (avl_node_t *n)
98 height_left = (n->left == NULL) ? 0 : n->left->height;
99 height_right = (n->right == NULL) ? 0 : n->right->height;
101 return (((height_left > height_right)
103 : height_right) + 1);
104 } /* int calc_height */
106 static avl_node_t *search (avl_tree_t *t, const void *key)
114 cmp = t->compare (key, n->key);
129 * / \ /_c\ ==> / a\ / \
131 * / a\ /_b\ /_b\ /_c\
134 static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
152 assert ((p == NULL) || (p->left == x) || (p->right == x));
155 else if (p->left == x)
160 x->height = calc_height (x);
161 y->height = calc_height (y);
164 } /* void rotate_left */
170 * /_a\ / \ ==> / \ / c\
172 * /_b\ / c\ /_a\ /_b\
175 static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
193 assert ((p == NULL) || (p->left == x) || (p->right == x));
196 else if (p->left == x)
201 x->height = calc_height (x);
202 y->height = calc_height (y);
205 } /* void rotate_left */
207 static avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_t *x)
209 rotate_left (t, x->left);
210 return (rotate_right (t, x));
211 } /* void rotate_left_right */
213 static avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_t *x)
215 rotate_right (t, x->right);
216 return (rotate_left (t, x));
217 } /* void rotate_right_left */
219 static void rebalance (avl_tree_t *t, avl_node_t *n)
227 assert ((b_top >= -2) && (b_top <= 2));
231 assert (n->right != NULL);
232 b_bottom = BALANCE (n->right);
233 assert ((b_bottom >= -1) || (b_bottom <= 1));
235 n = rotate_right_left (t, n);
237 n = rotate_left (t, n);
241 assert (n->left != NULL);
242 b_bottom = BALANCE (n->left);
243 assert ((b_bottom >= -1) || (b_bottom <= 1));
245 n = rotate_left_right (t, n);
247 n = rotate_right (t, n);
251 int height = calc_height (n);
252 if (height == n->height)
257 assert (n->height == calc_height (n));
260 } /* while (n != NULL) */
261 } /* void rebalance */
263 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
265 avl_iterator_t *iter;
267 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
277 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
279 avl_node_t *r; /* return node */
285 else if (n->right == NULL)
291 /* stop if a bigger node is found */
292 if (t->compare (n, r) < 0) /* n < r */
300 while (r->left != NULL)
307 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
309 avl_node_t *r; /* return node */
315 else if (n->left == NULL)
321 /* stop if a smaller node is found */
322 if (t->compare (n, r) > 0) /* n > r */
330 while (r->right != NULL)
337 static int _remove (avl_tree_t *t, avl_node_t *n)
339 assert ((t != NULL) && (n != NULL));
341 if ((n->left != NULL) && (n->right != NULL))
343 avl_node_t *r; /* replacement node */
344 if (BALANCE (n) > 0) /* left subtree is higher */
346 assert (n->left != NULL);
347 r = avl_node_prev (t, n);
350 else /* right subtree is higher */
352 assert (n->right != NULL);
353 r = avl_node_next (t, n);
356 assert ((r->left == NULL) || (r->right == NULL));
365 assert ((n->left == NULL) || (n->right == NULL));
367 if ((n->left == NULL) && (n->right == NULL))
369 /* Deleting a leave is easy */
370 if (n->parent == NULL)
372 assert (t->root == n);
377 assert ((n->parent->left == n)
378 || (n->parent->right == n));
379 if (n->parent->left == n)
380 n->parent->left = NULL;
382 n->parent->right = NULL;
384 rebalance (t, n->parent);
389 else if (n->left == NULL)
391 assert (BALANCE (n) == -1);
392 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
393 if (n->parent == NULL)
395 assert (t->root == n);
398 else if (n->parent->left == n)
400 n->parent->left = n->right;
404 n->parent->right = n->right;
406 n->right->parent = n->parent;
408 if (n->parent != NULL)
409 rebalance (t, n->parent);
414 else if (n->right == 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->left;
429 n->parent->right = n->left;
431 n->left->parent = n->parent;
433 if (n->parent != NULL)
434 rebalance (t, n->parent);
445 } /* void *_remove */
450 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
454 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
458 t->compare = compare;
463 void avl_destroy (avl_tree_t *t)
469 int avl_insert (avl_tree_t *t, void *key, void *value)
475 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
494 cmp = t->compare (nptr->key, new->key);
503 if (nptr->right == NULL)
515 else /* if (cmp > 0) */
518 if (nptr->left == NULL)
532 verify_tree (t->root);
534 } /* int avl_insert */
536 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
552 status = _remove (t, n);
553 verify_tree (t->root);
555 } /* void *avl_remove */
557 int avl_get (avl_tree_t *t, const void *key, void **value)
561 assert (value != NULL);
572 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
579 for (n = t->root; n != NULL; n = n->left)
583 return (avl_create_iterator (t, n));
584 } /* avl_iterator_t *avl_get_iterator */
586 void *avl_iterator_next (avl_iterator_t *iter)
590 if ((iter == NULL) || (iter->node == NULL))
593 n = avl_node_next (iter->tree, iter->node);
603 void *avl_iterator_prev (avl_iterator_t *iter)
607 if ((iter == NULL) || (iter->node == NULL))
610 n = avl_node_prev (iter->tree, iter->node);
620 void avl_iterator_destroy (avl_iterator_t *iter)