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>
30 #include "utils_avltree.h"
33 ((((n)->left == NULL) ? 0 : (n)->left->height) - \
34 (((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;
52 int (*compare)(const void *, const void *);
56 struct c_avl_iterator_s {
65 static void verify_tree (c_avl_node_t *n)
70 verify_tree (n->left);
71 verify_tree (n->right);
73 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
74 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
75 } /* void verify_tree */
77 #define verify_tree(n) /**/
80 static void free_node(c_avl_node_t *n) {
92 static int calc_height(c_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) ? height_left : height_right) + 1;
103 } /* int calc_height */
105 static c_avl_node_t *search(c_avl_tree_t *t, const void *key) {
111 cmp = t->compare(key, n->key);
126 * / \ /_c\ ==> / a\ / \
128 * / a\ /_b\ /_b\ /_c\
131 static c_avl_node_t *rotate_right(c_avl_tree_t *t, c_avl_node_t *x) {
137 assert(x->left != NULL);
151 assert((p == NULL) || (p->left == x) || (p->right == x));
154 else if (p->left == x)
159 x->height = calc_height(x);
160 y->height = calc_height(y);
163 } /* void rotate_right */
169 * /_a\ / \ ==> / \ / c\
171 * /_b\ / c\ /_a\ /_b\
174 static c_avl_node_t *rotate_left(c_avl_tree_t *t, c_avl_node_t *x) {
180 assert(x->right != NULL);
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 c_avl_node_t *rotate_left_right(c_avl_tree_t *t, c_avl_node_t *x) {
209 rotate_left(t, x->left);
210 return rotate_right(t, x);
211 } /* void rotate_left_right */
213 static c_avl_node_t *rotate_right_left(c_avl_tree_t *t, c_avl_node_t *x) {
214 rotate_right(t, x->right);
215 return rotate_left(t, x);
216 } /* void rotate_right_left */
218 static void rebalance(c_avl_tree_t *t, c_avl_node_t *n) {
224 assert((b_top >= -2) && (b_top <= 2));
227 assert(n->right != NULL);
228 b_bottom = BALANCE(n->right);
229 assert((b_bottom >= -1) && (b_bottom <= 1));
231 n = rotate_right_left(t, n);
233 n = rotate_left(t, n);
234 } else if (b_top == 2) {
235 assert(n->left != NULL);
236 b_bottom = BALANCE(n->left);
237 assert((b_bottom >= -1) && (b_bottom <= 1));
239 n = rotate_left_right(t, n);
241 n = rotate_right(t, n);
243 int height = calc_height(n);
244 if (height == n->height)
249 assert(n->height == calc_height(n));
252 } /* while (n != NULL) */
253 } /* void rebalance */
255 static c_avl_node_t *c_avl_node_next(c_avl_node_t *n) {
256 c_avl_node_t *r; /* return node */
262 /* If we can't descent any further, we have to backtrack to the first
263 * parent that's bigger than we, i. e. who's _left_ child we are. */
264 if (n->right == NULL) {
266 while ((r != NULL) && (r->parent != NULL)) {
273 /* n->right == NULL && r == NULL => t is root and has no next
274 * r->left != n => r->right = n => r->parent == NULL */
275 if ((r == NULL) || (r->left != n)) {
276 assert((r == NULL) || (r->parent == NULL));
279 assert(r->left == n);
284 while (r->left != NULL)
289 } /* c_avl_node_t *c_avl_node_next */
291 static c_avl_node_t *c_avl_node_prev(c_avl_node_t *n) {
292 c_avl_node_t *r; /* return node */
298 /* If we can't descent any further, we have to backtrack to the first
299 * parent that's smaller than we, i. e. who's _right_ child we are. */
300 if (n->left == NULL) {
302 while ((r != NULL) && (r->parent != NULL)) {
309 /* n->left == NULL && r == NULL => t is root and has no next
310 * r->right != n => r->left = n => r->parent == NULL */
311 if ((r == NULL) || (r->right != n)) {
312 assert((r == NULL) || (r->parent == NULL));
315 assert(r->right == n);
320 while (r->right != NULL)
325 } /* c_avl_node_t *c_avl_node_prev */
327 static int _remove(c_avl_tree_t *t, c_avl_node_t *n) {
328 assert((t != NULL) && (n != NULL));
330 if ((n->left != NULL) && (n->right != NULL)) {
331 c_avl_node_t *r; /* replacement node */
332 if (BALANCE(n) > 0) /* left subtree is higher */
334 assert(n->left != NULL);
335 r = c_avl_node_prev(n);
337 } else /* right subtree is higher */
339 assert(n->right != NULL);
340 r = c_avl_node_next(n);
343 assert((r->left == NULL) || (r->right == NULL));
352 assert((n->left == NULL) || (n->right == NULL));
354 if ((n->left == NULL) && (n->right == NULL)) {
355 /* Deleting a leave is easy */
356 if (n->parent == NULL) {
357 assert(t->root == n);
360 assert((n->parent->left == n) || (n->parent->right == n));
361 if (n->parent->left == n)
362 n->parent->left = NULL;
364 n->parent->right = NULL;
366 rebalance(t, n->parent);
370 } else if (n->left == NULL) {
371 assert(BALANCE(n) == -1);
372 assert((n->parent == NULL) || (n->parent->left == n) ||
373 (n->parent->right == n));
374 if (n->parent == NULL) {
375 assert(t->root == n);
377 } else if (n->parent->left == n) {
378 n->parent->left = n->right;
380 n->parent->right = n->right;
382 n->right->parent = n->parent;
384 if (n->parent != NULL)
385 rebalance(t, n->parent);
389 } else if (n->right == NULL) {
390 assert(BALANCE(n) == 1);
391 assert((n->parent == NULL) || (n->parent->left == n) ||
392 (n->parent->right == n));
393 if (n->parent == NULL) {
394 assert(t->root == n);
396 } else if (n->parent->left == n) {
397 n->parent->left = n->left;
399 n->parent->right = n->left;
401 n->left->parent = n->parent;
403 if (n->parent != NULL)
404 rebalance(t, n->parent);
413 } /* void *_remove */
418 c_avl_tree_t *c_avl_create(int (*compare)(const void *, const void *)) {
424 if ((t = malloc(sizeof(*t))) == NULL)
428 t->compare = compare;
434 void c_avl_destroy(c_avl_tree_t *t) {
441 int c_avl_insert(c_avl_tree_t *t, void *key, void *value) {
446 if ((new = malloc(sizeof(*new))) == NULL)
455 if (t->root == NULL) {
464 cmp = t->compare(nptr->key, new->key);
468 } else if (cmp < 0) {
470 if (nptr->right == NULL) {
478 } else /* if (cmp > 0) */
481 if (nptr->left == NULL) {
492 verify_tree(t->root);
495 } /* int c_avl_insert */
497 int c_avl_remove(c_avl_tree_t *t, const void *key, void **rkey, void **rvalue) {
512 status = _remove(t, n);
513 verify_tree(t->root);
516 } /* void *c_avl_remove */
518 int c_avl_get(c_avl_tree_t *t, const void *key, void **value) {
533 int c_avl_pick(c_avl_tree_t *t, void **key, void **value) {
539 if ((key == NULL) || (value == NULL))
545 while ((n->left != NULL) || (n->right != NULL)) {
546 if (n->left == NULL) {
549 } else if (n->right == NULL) {
554 if (n->left->height > n->right->height)
563 else if (p->left == n)
576 } /* int c_avl_pick */
578 c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t) {
579 c_avl_iterator_t *iter;
584 iter = calloc(1, sizeof(*iter));
590 } /* c_avl_iterator_t *c_avl_get_iterator */
592 int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value) {
595 if ((iter == NULL) || (key == NULL) || (value == NULL))
598 if (iter->node == NULL) {
599 for (n = iter->tree->root; n != NULL; n = n->left)
604 n = c_avl_node_next(iter->node);
615 } /* int c_avl_iterator_next */
617 int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) {
620 if ((iter == NULL) || (key == NULL) || (value == NULL))
623 if (iter->node == NULL) {
624 for (n = iter->tree->root; n != NULL; n = n->left)
625 if (n->right == NULL)
629 n = c_avl_node_prev(iter->node);
640 } /* int c_avl_iterator_prev */
642 void c_avl_iterator_destroy(c_avl_iterator_t *iter) { free(iter); }
644 int c_avl_size(c_avl_tree_t *t) {