1 /**
2 * collectd - src/utils_avltree.c
3 * Copyright (C) 2006,2007 Florian octo Forster
4 *
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:
11 *
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
14 *
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.
22 *
23 * Authors:
24 * Florian octo Forster <octo at collectd.org>
25 **/
27 #include <assert.h>
28 #include <stdlib.h>
30 #include "utils_avltree.h"
32 #define BALANCE(n) \
33 ((((n)->left == NULL) ? 0 : (n)->left->height) - \
34 (((n)->right == NULL) ? 0 : (n)->right->height))
36 /*
37 * private data types
38 */
39 struct c_avl_node_s {
40 void *key;
41 void *value;
43 int height;
44 struct c_avl_node_s *left;
45 struct c_avl_node_s *right;
46 struct c_avl_node_s *parent;
47 };
48 typedef struct c_avl_node_s c_avl_node_t;
50 struct c_avl_tree_s {
51 c_avl_node_t *root;
52 int (*compare)(const void *, const void *);
53 int size;
54 };
56 struct c_avl_iterator_s {
57 c_avl_tree_t *tree;
58 c_avl_node_t *node;
59 };
61 /*
62 * private functions
63 */
64 #if 0
65 static void verify_tree (c_avl_node_t *n)
66 {
67 if (n == NULL)
68 return;
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 */
76 #else
77 #define verify_tree(n) /**/
78 #endif
80 static void free_node(c_avl_node_t *n) {
81 if (n == NULL)
82 return;
84 if (n->left != NULL)
85 free_node(n->left);
86 if (n->right != NULL)
87 free_node(n->right);
89 free(n);
90 }
92 static int calc_height(c_avl_node_t *n) {
93 int height_left;
94 int height_right;
96 if (n == NULL)
97 return (0);
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) {
106 c_avl_node_t *n;
107 int cmp;
109 n = t->root;
110 while (n != NULL) {
111 cmp = t->compare(key, n->key);
112 if (cmp == 0)
113 return (n);
114 else if (cmp < 0)
115 n = n->left;
116 else
117 n = n->right;
118 }
120 return (NULL);
121 }
123 /* (x) (y)
124 * / \ / \
125 * (y) /\ /\ (x)
126 * / \ /_c\ ==> / a\ / \
127 * /\ /\ /____\/\ /\
128 * / a\ /_b\ /_b\ /_c\
129 * /____\
130 */
131 static c_avl_node_t *rotate_right(c_avl_tree_t *t, c_avl_node_t *x) {
132 c_avl_node_t *p;
133 c_avl_node_t *y;
134 c_avl_node_t *b;
136 assert(x != NULL);
137 assert(x->left != NULL);
139 p = x->parent;
140 y = x->left;
141 b = y->right;
143 x->left = b;
144 if (b != NULL)
145 b->parent = x;
147 x->parent = y;
148 y->right = x;
150 y->parent = p;
151 assert((p == NULL) || (p->left == x) || (p->right == x));
152 if (p == NULL)
153 t->root = y;
154 else if (p->left == x)
155 p->left = y;
156 else
157 p->right = y;
159 x->height = calc_height(x);
160 y->height = calc_height(y);
162 return (y);
163 } /* void rotate_right */
165 /*
166 * (x) (y)
167 * / \ / \
168 * /\ (y) (x) /\
169 * /_a\ / \ ==> / \ / c\
170 * /\ /\ /\ /\/____\
171 * /_b\ / c\ /_a\ /_b\
172 * /____\
173 */
174 static c_avl_node_t *rotate_left(c_avl_tree_t *t, c_avl_node_t *x) {
175 c_avl_node_t *p;
176 c_avl_node_t *y;
177 c_avl_node_t *b;
179 assert(x != NULL);
180 assert(x->right != NULL);
182 p = x->parent;
183 y = x->right;
184 b = y->left;
186 x->right = b;
187 if (b != NULL)
188 b->parent = x;
190 x->parent = y;
191 y->left = x;
193 y->parent = p;
194 assert((p == NULL) || (p->left == x) || (p->right == x));
195 if (p == NULL)
196 t->root = y;
197 else if (p->left == x)
198 p->left = y;
199 else
200 p->right = y;
202 x->height = calc_height(x);
203 y->height = calc_height(y);
205 return (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) {
219 int b_top;
220 int b_bottom;
222 while (n != NULL) {
223 b_top = BALANCE(n);
224 assert((b_top >= -2) && (b_top <= 2));
226 if (b_top == -2) {
227 assert(n->right != NULL);
228 b_bottom = BALANCE(n->right);
229 assert((b_bottom >= -1) && (b_bottom <= 1));
230 if (b_bottom == 1)
231 n = rotate_right_left(t, n);
232 else
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));
238 if (b_bottom == -1)
239 n = rotate_left_right(t, n);
240 else
241 n = rotate_right(t, n);
242 } else {
243 int height = calc_height(n);
244 if (height == n->height)
245 break;
246 n->height = height;
247 }
249 assert(n->height == calc_height(n));
251 n = n->parent;
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 */
258 if (n == NULL) {
259 return (NULL);
260 }
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) {
265 r = n->parent;
266 while ((r != NULL) && (r->parent != NULL)) {
267 if (r->left == n)
268 break;
269 n = r;
270 r = n->parent;
271 }
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));
277 return (NULL);
278 } else {
279 assert(r->left == n);
280 return (r);
281 }
282 } else {
283 r = n->right;
284 while (r->left != NULL)
285 r = r->left;
286 }
288 return (r);
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 */
294 if (n == NULL) {
295 return (NULL);
296 }
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) {
301 r = n->parent;
302 while ((r != NULL) && (r->parent != NULL)) {
303 if (r->right == n)
304 break;
305 n = r;
306 r = n->parent;
307 }
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));
313 return (NULL);
314 } else {
315 assert(r->right == n);
316 return (r);
317 }
318 } else {
319 r = n->left;
320 while (r->right != NULL)
321 r = r->right;
322 }
324 return (r);
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 */
333 {
334 assert(n->left != NULL);
335 r = c_avl_node_prev(n);
337 } else /* right subtree is higher */
338 {
339 assert(n->right != NULL);
340 r = c_avl_node_next(n);
341 }
343 assert((r->left == NULL) || (r->right == NULL));
345 /* copy content */
346 n->key = r->key;
347 n->value = r->value;
349 n = r;
350 }
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);
358 t->root = NULL;
359 } else {
360 assert((n->parent->left == n) || (n->parent->right == n));
361 if (n->parent->left == n)
362 n->parent->left = NULL;
363 else
364 n->parent->right = NULL;
366 rebalance(t, n->parent);
367 }
369 free_node(n);
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);
376 t->root = n->right;
377 } else if (n->parent->left == n) {
378 n->parent->left = n->right;
379 } else {
380 n->parent->right = n->right;
381 }
382 n->right->parent = n->parent;
384 if (n->parent != NULL)
385 rebalance(t, n->parent);
387 n->right = NULL;
388 free_node(n);
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);
395 t->root = n->left;
396 } else if (n->parent->left == n) {
397 n->parent->left = n->left;
398 } else {
399 n->parent->right = n->left;
400 }
401 n->left->parent = n->parent;
403 if (n->parent != NULL)
404 rebalance(t, n->parent);
406 n->left = NULL;
407 free_node(n);
408 } else {
409 assert(0);
410 }
412 return (0);
413 } /* void *_remove */
415 /*
416 * public functions
417 */
418 c_avl_tree_t *c_avl_create(int (*compare)(const void *, const void *)) {
419 c_avl_tree_t *t;
421 if (compare == NULL)
422 return (NULL);
424 if ((t = malloc(sizeof(*t))) == NULL)
425 return (NULL);
427 t->root = NULL;
428 t->compare = compare;
429 t->size = 0;
431 return (t);
432 }
434 void c_avl_destroy(c_avl_tree_t *t) {
435 if (t == NULL)
436 return;
437 free_node(t->root);
438 free(t);
439 }
441 int c_avl_insert(c_avl_tree_t *t, void *key, void *value) {
442 c_avl_node_t *new;
443 c_avl_node_t *nptr;
444 int cmp;
446 if ((new = malloc(sizeof(*new))) == NULL)
447 return (-1);
449 new->key = key;
450 new->value = value;
451 new->height = 1;
452 new->left = NULL;
453 new->right = NULL;
455 if (t->root == NULL) {
456 new->parent = NULL;
457 t->root = new;
458 t->size = 1;
459 return (0);
460 }
462 nptr = t->root;
463 while (42) {
464 cmp = t->compare(nptr->key, new->key);
465 if (cmp == 0) {
466 free_node(new);
467 return (1);
468 } else if (cmp < 0) {
469 /* nptr < new */
470 if (nptr->right == NULL) {
471 nptr->right = new;
472 new->parent = nptr;
473 rebalance(t, nptr);
474 break;
475 } else {
476 nptr = nptr->right;
477 }
478 } else /* if (cmp > 0) */
479 {
480 /* nptr > new */
481 if (nptr->left == NULL) {
482 nptr->left = new;
483 new->parent = nptr;
484 rebalance(t, nptr);
485 break;
486 } else {
487 nptr = nptr->left;
488 }
489 }
490 } /* while (42) */
492 verify_tree(t->root);
493 ++t->size;
494 return (0);
495 } /* int c_avl_insert */
497 int c_avl_remove(c_avl_tree_t *t, const void *key, void **rkey, void **rvalue) {
498 c_avl_node_t *n;
499 int status;
501 assert(t != NULL);
503 n = search(t, key);
504 if (n == NULL)
505 return (-1);
507 if (rkey != NULL)
508 *rkey = n->key;
509 if (rvalue != NULL)
510 *rvalue = n->value;
512 status = _remove(t, n);
513 verify_tree(t->root);
514 --t->size;
515 return (status);
516 } /* void *c_avl_remove */
518 int c_avl_get(c_avl_tree_t *t, const void *key, void **value) {
519 c_avl_node_t *n;
521 assert(t != NULL);
523 n = search(t, key);
524 if (n == NULL)
525 return (-1);
527 if (value != NULL)
528 *value = n->value;
530 return (0);
531 }
533 int c_avl_pick(c_avl_tree_t *t, void **key, void **value) {
534 c_avl_node_t *n;
535 c_avl_node_t *p;
537 if ((key == NULL) || (value == NULL))
538 return (-1);
539 if (t->root == NULL)
540 return (-1);
542 n = t->root;
543 while ((n->left != NULL) || (n->right != NULL)) {
544 if (n->left == NULL) {
545 n = n->right;
546 continue;
547 } else if (n->right == NULL) {
548 n = n->left;
549 continue;
550 }
552 if (n->left->height > n->right->height)
553 n = n->left;
554 else
555 n = n->right;
556 }
558 p = n->parent;
559 if (p == NULL)
560 t->root = NULL;
561 else if (p->left == n)
562 p->left = NULL;
563 else
564 p->right = NULL;
566 *key = n->key;
567 *value = n->value;
569 free_node(n);
570 --t->size;
571 rebalance(t, p);
573 return (0);
574 } /* int c_avl_pick */
576 c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t) {
577 c_avl_iterator_t *iter;
579 if (t == NULL)
580 return (NULL);
582 iter = calloc(1, sizeof(*iter));
583 if (iter == NULL)
584 return (NULL);
585 iter->tree = t;
587 return (iter);
588 } /* c_avl_iterator_t *c_avl_get_iterator */
590 int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value) {
591 c_avl_node_t *n;
593 if ((iter == NULL) || (key == NULL) || (value == NULL))
594 return (-1);
596 if (iter->node == NULL) {
597 for (n = iter->tree->root; n != NULL; n = n->left)
598 if (n->left == NULL)
599 break;
600 iter->node = n;
601 } else {
602 n = c_avl_node_next(iter->node);
603 }
605 if (n == NULL)
606 return (-1);
608 iter->node = n;
609 *key = n->key;
610 *value = n->value;
612 return (0);
613 } /* int c_avl_iterator_next */
615 int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) {
616 c_avl_node_t *n;
618 if ((iter == NULL) || (key == NULL) || (value == NULL))
619 return (-1);
621 if (iter->node == NULL) {
622 for (n = iter->tree->root; n != NULL; n = n->left)
623 if (n->right == NULL)
624 break;
625 iter->node = n;
626 } else {
627 n = c_avl_node_prev(iter->node);
628 }
630 if (n == NULL)
631 return (-1);
633 iter->node = n;
634 *key = n->key;
635 *value = n->value;
637 return (0);
638 } /* int c_avl_iterator_prev */
640 void c_avl_iterator_destroy(c_avl_iterator_t *iter) { free(iter); }
642 int c_avl_size(c_avl_tree_t *t) {
643 if (t == NULL)
644 return (0);
645 return (t->size);
646 }