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 <stdlib.h>
28 #include <assert.h>
30 #include "utils_avltree.h"
32 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
33 - (((n)->right == NULL) ? 0 : (n)->right->height))
35 /*
36 * private data types
37 */
38 struct c_avl_node_s
39 {
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 {
52 c_avl_node_t *root;
53 int (*compare) (const void *, const void *);
54 int size;
55 };
57 struct c_avl_iterator_s
58 {
59 c_avl_tree_t *tree;
60 c_avl_node_t *node;
61 };
63 /*
64 * private functions
65 */
66 #if 0
67 static void verify_tree (c_avl_node_t *n)
68 {
69 if (n == NULL)
70 return;
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 */
78 #else
79 # define verify_tree(n) /**/
80 #endif
82 static void free_node (c_avl_node_t *n)
83 {
84 if (n == NULL)
85 return;
87 if (n->left != NULL)
88 free_node (n->left);
89 if (n->right != NULL)
90 free_node (n->right);
92 free (n);
93 }
95 static int calc_height (c_avl_node_t *n)
96 {
97 int height_left;
98 int height_right;
100 if (n == NULL)
101 return (0);
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)
107 ? height_left
108 : height_right) + 1);
109 } /* int calc_height */
111 static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
112 {
113 c_avl_node_t *n;
114 int cmp;
116 n = t->root;
117 while (n != NULL)
118 {
119 cmp = t->compare (key, n->key);
120 if (cmp == 0)
121 return (n);
122 else if (cmp < 0)
123 n = n->left;
124 else
125 n = n->right;
126 }
128 return (NULL);
129 }
131 /* (x) (y)
132 * / \ / \
133 * (y) /\ /\ (x)
134 * / \ /_c\ ==> / a\ / \
135 * /\ /\ /____\/\ /\
136 * / a\ /_b\ /_b\ /_c\
137 * /____\
138 */
139 static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
140 {
141 c_avl_node_t *p;
142 c_avl_node_t *y;
143 c_avl_node_t *b;
145 assert (x != NULL);
146 assert (x->left != NULL);
148 p = x->parent;
149 y = x->left;
150 b = y->right;
152 x->left = b;
153 if (b != NULL)
154 b->parent = x;
156 x->parent = y;
157 y->right = x;
159 y->parent = p;
160 assert ((p == NULL) || (p->left == x) || (p->right == x));
161 if (p == NULL)
162 t->root = y;
163 else if (p->left == x)
164 p->left = y;
165 else
166 p->right = y;
168 x->height = calc_height (x);
169 y->height = calc_height (y);
171 return (y);
172 } /* void rotate_right */
174 /*
175 * (x) (y)
176 * / \ / \
177 * /\ (y) (x) /\
178 * /_a\ / \ ==> / \ / c\
179 * /\ /\ /\ /\/____\
180 * /_b\ / c\ /_a\ /_b\
181 * /____\
182 */
183 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
184 {
185 c_avl_node_t *p;
186 c_avl_node_t *y;
187 c_avl_node_t *b;
189 assert (x != NULL);
190 assert (x->right != NULL);
192 p = x->parent;
193 y = x->right;
194 b = y->left;
196 x->right = b;
197 if (b != NULL)
198 b->parent = x;
200 x->parent = y;
201 y->left = x;
203 y->parent = p;
204 assert ((p == NULL) || (p->left == x) || (p->right == x));
205 if (p == NULL)
206 t->root = y;
207 else if (p->left == x)
208 p->left = y;
209 else
210 p->right = y;
212 x->height = calc_height (x);
213 y->height = calc_height (y);
215 return (y);
216 } /* void rotate_left */
218 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
219 {
220 rotate_left (t, x->left);
221 return (rotate_right (t, x));
222 } /* void rotate_left_right */
224 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
225 {
226 rotate_right (t, x->right);
227 return (rotate_left (t, x));
228 } /* void rotate_right_left */
230 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
231 {
232 int b_top;
233 int b_bottom;
235 while (n != NULL)
236 {
237 b_top = BALANCE (n);
238 assert ((b_top >= -2) && (b_top <= 2));
240 if (b_top == -2)
241 {
242 assert (n->right != NULL);
243 b_bottom = BALANCE (n->right);
244 assert ((b_bottom >= -1) && (b_bottom <= 1));
245 if (b_bottom == 1)
246 n = rotate_right_left (t, n);
247 else
248 n = rotate_left (t, n);
249 }
250 else if (b_top == 2)
251 {
252 assert (n->left != NULL);
253 b_bottom = BALANCE (n->left);
254 assert ((b_bottom >= -1) && (b_bottom <= 1));
255 if (b_bottom == -1)
256 n = rotate_left_right (t, n);
257 else
258 n = rotate_right (t, n);
259 }
260 else
261 {
262 int height = calc_height (n);
263 if (height == n->height)
264 break;
265 n->height = height;
266 }
268 assert (n->height == calc_height (n));
270 n = n->parent;
271 } /* while (n != NULL) */
272 } /* void rebalance */
274 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
275 {
276 c_avl_node_t *r; /* return node */
278 if (n == NULL)
279 {
280 return (NULL);
281 }
283 /* If we can't descent any further, we have to backtrack to the first
284 * parent that's bigger than we, i. e. who's _left_ child we are. */
285 if (n->right == NULL)
286 {
287 r = n->parent;
288 while ((r != NULL) && (r->parent != NULL))
289 {
290 if (r->left == n)
291 break;
292 n = r;
293 r = n->parent;
294 }
296 /* n->right == NULL && r == NULL => t is root and has no next
297 * r->left != n => r->right = n => r->parent == NULL */
298 if ((r == NULL) || (r->left != n))
299 {
300 assert ((r == NULL) || (r->parent == NULL));
301 return (NULL);
302 }
303 else
304 {
305 assert (r->left == n);
306 return (r);
307 }
308 }
309 else
310 {
311 r = n->right;
312 while (r->left != NULL)
313 r = r->left;
314 }
316 return (r);
317 } /* c_avl_node_t *c_avl_node_next */
319 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
320 {
321 c_avl_node_t *r; /* return node */
323 if (n == NULL)
324 {
325 return (NULL);
326 }
328 /* If we can't descent any further, we have to backtrack to the first
329 * parent that's smaller than we, i. e. who's _right_ child we are. */
330 if (n->left == NULL)
331 {
332 r = n->parent;
333 while ((r != NULL) && (r->parent != NULL))
334 {
335 if (r->right == n)
336 break;
337 n = r;
338 r = n->parent;
339 }
341 /* n->left == NULL && r == NULL => t is root and has no next
342 * r->right != n => r->left = n => r->parent == NULL */
343 if ((r == NULL) || (r->right != n))
344 {
345 assert ((r == NULL) || (r->parent == NULL));
346 return (NULL);
347 }
348 else
349 {
350 assert (r->right == n);
351 return (r);
352 }
353 }
354 else
355 {
356 r = n->left;
357 while (r->right != NULL)
358 r = r->right;
359 }
361 return (r);
362 } /* c_avl_node_t *c_avl_node_prev */
364 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
365 {
366 assert ((t != NULL) && (n != NULL));
368 if ((n->left != NULL) && (n->right != NULL))
369 {
370 c_avl_node_t *r; /* replacement node */
371 if (BALANCE (n) > 0) /* left subtree is higher */
372 {
373 assert (n->left != NULL);
374 r = c_avl_node_prev (n);
376 }
377 else /* right subtree is higher */
378 {
379 assert (n->right != NULL);
380 r = c_avl_node_next (n);
381 }
383 assert ((r->left == NULL) || (r->right == NULL));
385 /* copy content */
386 n->key = r->key;
387 n->value = r->value;
389 n = r;
390 }
392 assert ((n->left == NULL) || (n->right == NULL));
394 if ((n->left == NULL) && (n->right == NULL))
395 {
396 /* Deleting a leave is easy */
397 if (n->parent == NULL)
398 {
399 assert (t->root == n);
400 t->root = NULL;
401 }
402 else
403 {
404 assert ((n->parent->left == n)
405 || (n->parent->right == n));
406 if (n->parent->left == n)
407 n->parent->left = NULL;
408 else
409 n->parent->right = NULL;
411 rebalance (t, n->parent);
412 }
414 free_node (n);
415 }
416 else if (n->left == NULL)
417 {
418 assert (BALANCE (n) == -1);
419 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
420 if (n->parent == NULL)
421 {
422 assert (t->root == n);
423 t->root = n->right;
424 }
425 else if (n->parent->left == n)
426 {
427 n->parent->left = n->right;
428 }
429 else
430 {
431 n->parent->right = n->right;
432 }
433 n->right->parent = n->parent;
435 if (n->parent != NULL)
436 rebalance (t, n->parent);
438 n->right = NULL;
439 free_node (n);
440 }
441 else if (n->right == NULL)
442 {
443 assert (BALANCE (n) == 1);
444 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
445 if (n->parent == NULL)
446 {
447 assert (t->root == n);
448 t->root = n->left;
449 }
450 else if (n->parent->left == n)
451 {
452 n->parent->left = n->left;
453 }
454 else
455 {
456 n->parent->right = n->left;
457 }
458 n->left->parent = n->parent;
460 if (n->parent != NULL)
461 rebalance (t, n->parent);
463 n->left = NULL;
464 free_node (n);
465 }
466 else
467 {
468 assert (0);
469 }
471 return (0);
472 } /* void *_remove */
474 /*
475 * public functions
476 */
477 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
478 {
479 c_avl_tree_t *t;
481 if (compare == NULL)
482 return (NULL);
484 if ((t = malloc (sizeof (*t))) == NULL)
485 return (NULL);
487 t->root = NULL;
488 t->compare = compare;
489 t->size = 0;
491 return (t);
492 }
494 void c_avl_destroy (c_avl_tree_t *t)
495 {
496 if (t == NULL)
497 return;
498 free_node (t->root);
499 free (t);
500 }
502 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
503 {
504 c_avl_node_t *new;
505 c_avl_node_t *nptr;
506 int cmp;
508 if ((new = malloc (sizeof (*new))) == NULL)
509 return (-1);
511 new->key = key;
512 new->value = value;
513 new->height = 1;
514 new->left = NULL;
515 new->right = NULL;
517 if (t->root == NULL)
518 {
519 new->parent = NULL;
520 t->root = new;
521 t->size = 1;
522 return (0);
523 }
525 nptr = t->root;
526 while (42)
527 {
528 cmp = t->compare (nptr->key, new->key);
529 if (cmp == 0)
530 {
531 free_node (new);
532 return (1);
533 }
534 else if (cmp < 0)
535 {
536 /* nptr < new */
537 if (nptr->right == NULL)
538 {
539 nptr->right = new;
540 new->parent = nptr;
541 rebalance (t, nptr);
542 break;
543 }
544 else
545 {
546 nptr = nptr->right;
547 }
548 }
549 else /* if (cmp > 0) */
550 {
551 /* nptr > new */
552 if (nptr->left == NULL)
553 {
554 nptr->left = new;
555 new->parent = nptr;
556 rebalance (t, nptr);
557 break;
558 }
559 else
560 {
561 nptr = nptr->left;
562 }
563 }
564 } /* while (42) */
566 verify_tree (t->root);
567 ++t->size;
568 return (0);
569 } /* int c_avl_insert */
571 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
572 {
573 c_avl_node_t *n;
574 int status;
576 assert (t != NULL);
578 n = search (t, key);
579 if (n == NULL)
580 return (-1);
582 if (rkey != NULL)
583 *rkey = n->key;
584 if (rvalue != NULL)
585 *rvalue = n->value;
587 status = _remove (t, n);
588 verify_tree (t->root);
589 --t->size;
590 return (status);
591 } /* void *c_avl_remove */
593 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
594 {
595 c_avl_node_t *n;
597 assert (t != NULL);
599 n = search (t, key);
600 if (n == NULL)
601 return (-1);
603 if (value != NULL)
604 *value = n->value;
606 return (0);
607 }
609 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
610 {
611 c_avl_node_t *n;
612 c_avl_node_t *p;
614 if ((key == NULL) || (value == NULL))
615 return (-1);
616 if (t->root == NULL)
617 return (-1);
619 n = t->root;
620 while ((n->left != NULL) || (n->right != NULL))
621 {
622 if (n->left == NULL)
623 {
624 n = n->right;
625 continue;
626 }
627 else if (n->right == NULL)
628 {
629 n = n->left;
630 continue;
631 }
633 if (n->left->height > n->right->height)
634 n = n->left;
635 else
636 n = n->right;
637 }
639 p = n->parent;
640 if (p == NULL)
641 t->root = NULL;
642 else if (p->left == n)
643 p->left = NULL;
644 else
645 p->right = NULL;
647 *key = n->key;
648 *value = n->value;
650 free_node (n);
651 --t->size;
652 rebalance (t, p);
654 return (0);
655 } /* int c_avl_pick */
657 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
658 {
659 c_avl_iterator_t *iter;
661 if (t == NULL)
662 return (NULL);
664 iter = calloc (1, sizeof (*iter));
665 if (iter == NULL)
666 return (NULL);
667 iter->tree = t;
669 return (iter);
670 } /* c_avl_iterator_t *c_avl_get_iterator */
672 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
673 {
674 c_avl_node_t *n;
676 if ((iter == NULL) || (key == NULL) || (value == NULL))
677 return (-1);
679 if (iter->node == NULL)
680 {
681 for (n = iter->tree->root; n != NULL; n = n->left)
682 if (n->left == NULL)
683 break;
684 iter->node = n;
685 }
686 else
687 {
688 n = c_avl_node_next (iter->node);
689 }
691 if (n == NULL)
692 return (-1);
694 iter->node = n;
695 *key = n->key;
696 *value = n->value;
698 return (0);
699 } /* int c_avl_iterator_next */
701 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
702 {
703 c_avl_node_t *n;
705 if ((iter == NULL) || (key == NULL) || (value == NULL))
706 return (-1);
708 if (iter->node == NULL)
709 {
710 for (n = iter->tree->root; n != NULL; n = n->left)
711 if (n->right == NULL)
712 break;
713 iter->node = n;
714 }
715 else
716 {
717 n = c_avl_node_prev (iter->node);
718 }
720 if (n == NULL)
721 return (-1);
723 iter->node = n;
724 *key = n->key;
725 *value = n->value;
727 return (0);
728 } /* int c_avl_iterator_prev */
730 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
731 {
732 free (iter);
733 }
735 int c_avl_size (c_avl_tree_t *t)
736 {
737 if (t == NULL)
738 return (0);
739 return (t->size);
740 }