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 "config.h"
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32 #include <assert.h>
34 #include "utils_avltree.h"
36 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
37 - (((n)->right == NULL) ? 0 : (n)->right->height))
39 /*
40 * private data types
41 */
42 struct c_avl_node_s
43 {
44 void *key;
45 void *value;
47 int height;
48 struct c_avl_node_s *left;
49 struct c_avl_node_s *right;
50 struct c_avl_node_s *parent;
51 };
52 typedef struct c_avl_node_s c_avl_node_t;
54 struct c_avl_tree_s
55 {
56 c_avl_node_t *root;
57 int (*compare) (const void *, const void *);
58 int size;
59 };
61 struct c_avl_iterator_s
62 {
63 c_avl_tree_t *tree;
64 c_avl_node_t *node;
65 };
67 /*
68 * private functions
69 */
70 #if 0
71 static void verify_tree (c_avl_node_t *n)
72 {
73 if (n == NULL)
74 return;
76 verify_tree (n->left);
77 verify_tree (n->right);
79 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
80 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
81 } /* void verify_tree */
82 #else
83 # define verify_tree(n) /**/
84 #endif
86 static void free_node (c_avl_node_t *n)
87 {
88 if (n == NULL)
89 return;
91 if (n->left != NULL)
92 free_node (n->left);
93 if (n->right != NULL)
94 free_node (n->right);
96 free (n);
97 }
99 static int calc_height (c_avl_node_t *n)
100 {
101 int height_left;
102 int height_right;
104 if (n == NULL)
105 return (0);
107 height_left = (n->left == NULL) ? 0 : n->left->height;
108 height_right = (n->right == NULL) ? 0 : n->right->height;
110 return (((height_left > height_right)
111 ? height_left
112 : height_right) + 1);
113 } /* int calc_height */
115 static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
116 {
117 c_avl_node_t *n;
118 int cmp;
120 n = t->root;
121 while (n != NULL)
122 {
123 cmp = t->compare (key, n->key);
124 if (cmp == 0)
125 return (n);
126 else if (cmp < 0)
127 n = n->left;
128 else
129 n = n->right;
130 }
132 return (NULL);
133 }
135 /* (x) (y)
136 * / \ / \
137 * (y) /\ /\ (x)
138 * / \ /_c\ ==> / a\ / \
139 * /\ /\ /____\/\ /\
140 * / a\ /_b\ /_b\ /_c\
141 * /____\
142 */
143 static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
144 {
145 c_avl_node_t *p;
146 c_avl_node_t *y;
147 c_avl_node_t *b;
149 assert (x != NULL);
150 assert (x->left != NULL);
152 p = x->parent;
153 y = x->left;
154 b = y->right;
156 x->left = b;
157 if (b != NULL)
158 b->parent = x;
160 x->parent = y;
161 y->right = x;
163 y->parent = p;
164 assert ((p == NULL) || (p->left == x) || (p->right == x));
165 if (p == NULL)
166 t->root = y;
167 else if (p->left == x)
168 p->left = y;
169 else
170 p->right = y;
172 x->height = calc_height (x);
173 y->height = calc_height (y);
175 return (y);
176 } /* void rotate_right */
178 /*
179 * (x) (y)
180 * / \ / \
181 * /\ (y) (x) /\
182 * /_a\ / \ ==> / \ / c\
183 * /\ /\ /\ /\/____\
184 * /_b\ / c\ /_a\ /_b\
185 * /____\
186 */
187 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
188 {
189 c_avl_node_t *p;
190 c_avl_node_t *y;
191 c_avl_node_t *b;
193 assert (x != NULL);
194 assert (x->right != NULL);
196 p = x->parent;
197 y = x->right;
198 b = y->left;
200 x->right = b;
201 if (b != NULL)
202 b->parent = x;
204 x->parent = y;
205 y->left = x;
207 y->parent = p;
208 assert ((p == NULL) || (p->left == x) || (p->right == x));
209 if (p == NULL)
210 t->root = y;
211 else if (p->left == x)
212 p->left = y;
213 else
214 p->right = y;
216 x->height = calc_height (x);
217 y->height = calc_height (y);
219 return (y);
220 } /* void rotate_left */
222 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
223 {
224 rotate_left (t, x->left);
225 return (rotate_right (t, x));
226 } /* void rotate_left_right */
228 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
229 {
230 rotate_right (t, x->right);
231 return (rotate_left (t, x));
232 } /* void rotate_right_left */
234 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
235 {
236 int b_top;
237 int b_bottom;
239 while (n != NULL)
240 {
241 b_top = BALANCE (n);
242 assert ((b_top >= -2) && (b_top <= 2));
244 if (b_top == -2)
245 {
246 assert (n->right != NULL);
247 b_bottom = BALANCE (n->right);
248 assert ((b_bottom >= -1) || (b_bottom <= 1));
249 if (b_bottom == 1)
250 n = rotate_right_left (t, n);
251 else
252 n = rotate_left (t, n);
253 }
254 else if (b_top == 2)
255 {
256 assert (n->left != NULL);
257 b_bottom = BALANCE (n->left);
258 assert ((b_bottom >= -1) || (b_bottom <= 1));
259 if (b_bottom == -1)
260 n = rotate_left_right (t, n);
261 else
262 n = rotate_right (t, n);
263 }
264 else
265 {
266 int height = calc_height (n);
267 if (height == n->height)
268 break;
269 n->height = height;
270 }
272 assert (n->height == calc_height (n));
274 n = n->parent;
275 } /* while (n != NULL) */
276 } /* void rebalance */
278 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
279 {
280 c_avl_node_t *r; /* return node */
282 if (n == NULL)
283 {
284 return (NULL);
285 }
287 /* If we can't descent any further, we have to backtrack to the first
288 * parent that's bigger than we, i. e. who's _left_ child we are. */
289 if (n->right == NULL)
290 {
291 r = n->parent;
292 while ((r != NULL) && (r->parent != NULL))
293 {
294 if (r->left == n)
295 break;
296 n = r;
297 r = n->parent;
298 }
300 /* n->right == NULL && r == NULL => t is root and has no next
301 * r->left != n => r->right = n => r->parent == NULL */
302 if ((r == NULL) || (r->left != n))
303 {
304 assert ((r == NULL) || (r->parent == NULL));
305 return (NULL);
306 }
307 else
308 {
309 assert (r->left == n);
310 return (r);
311 }
312 }
313 else
314 {
315 r = n->right;
316 while (r->left != NULL)
317 r = r->left;
318 }
320 return (r);
321 } /* c_avl_node_t *c_avl_node_next */
323 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
324 {
325 c_avl_node_t *r; /* return node */
327 if (n == NULL)
328 {
329 return (NULL);
330 }
332 /* If we can't descent any further, we have to backtrack to the first
333 * parent that's smaller than we, i. e. who's _right_ child we are. */
334 if (n->left == NULL)
335 {
336 r = n->parent;
337 while ((r != NULL) && (r->parent != NULL))
338 {
339 if (r->right == n)
340 break;
341 n = r;
342 r = n->parent;
343 }
345 /* n->left == NULL && r == NULL => t is root and has no next
346 * r->right != n => r->left = n => r->parent == NULL */
347 if ((r == NULL) || (r->right != n))
348 {
349 assert ((r == NULL) || (r->parent == NULL));
350 return (NULL);
351 }
352 else
353 {
354 assert (r->right == n);
355 return (r);
356 }
357 }
358 else
359 {
360 r = n->left;
361 while (r->right != NULL)
362 r = r->right;
363 }
365 return (r);
366 } /* c_avl_node_t *c_avl_node_prev */
368 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
369 {
370 assert ((t != NULL) && (n != NULL));
372 if ((n->left != NULL) && (n->right != NULL))
373 {
374 c_avl_node_t *r; /* replacement node */
375 if (BALANCE (n) > 0) /* left subtree is higher */
376 {
377 assert (n->left != NULL);
378 r = c_avl_node_prev (n);
380 }
381 else /* right subtree is higher */
382 {
383 assert (n->right != NULL);
384 r = c_avl_node_next (n);
385 }
387 assert ((r->left == NULL) || (r->right == NULL));
389 /* copy content */
390 n->key = r->key;
391 n->value = r->value;
393 n = r;
394 }
396 assert ((n->left == NULL) || (n->right == NULL));
398 if ((n->left == NULL) && (n->right == NULL))
399 {
400 /* Deleting a leave is easy */
401 if (n->parent == NULL)
402 {
403 assert (t->root == n);
404 t->root = NULL;
405 }
406 else
407 {
408 assert ((n->parent->left == n)
409 || (n->parent->right == n));
410 if (n->parent->left == n)
411 n->parent->left = NULL;
412 else
413 n->parent->right = NULL;
415 rebalance (t, n->parent);
416 }
418 free_node (n);
419 }
420 else if (n->left == NULL)
421 {
422 assert (BALANCE (n) == -1);
423 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
424 if (n->parent == NULL)
425 {
426 assert (t->root == n);
427 t->root = n->right;
428 }
429 else if (n->parent->left == n)
430 {
431 n->parent->left = n->right;
432 }
433 else
434 {
435 n->parent->right = n->right;
436 }
437 n->right->parent = n->parent;
439 if (n->parent != NULL)
440 rebalance (t, n->parent);
442 n->right = NULL;
443 free_node (n);
444 }
445 else if (n->right == NULL)
446 {
447 assert (BALANCE (n) == 1);
448 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
449 if (n->parent == NULL)
450 {
451 assert (t->root == n);
452 t->root = n->left;
453 }
454 else if (n->parent->left == n)
455 {
456 n->parent->left = n->left;
457 }
458 else
459 {
460 n->parent->right = n->left;
461 }
462 n->left->parent = n->parent;
464 if (n->parent != NULL)
465 rebalance (t, n->parent);
467 n->left = NULL;
468 free_node (n);
469 }
470 else
471 {
472 assert (0);
473 }
475 return (0);
476 } /* void *_remove */
478 /*
479 * public functions
480 */
481 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
482 {
483 c_avl_tree_t *t;
485 if (compare == NULL)
486 return (NULL);
488 if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
489 return (NULL);
491 t->root = NULL;
492 t->compare = compare;
493 t->size = 0;
495 return (t);
496 }
498 void c_avl_destroy (c_avl_tree_t *t)
499 {
500 if (t == NULL)
501 return;
502 free_node (t->root);
503 free (t);
504 }
506 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
507 {
508 c_avl_node_t *new;
509 c_avl_node_t *nptr;
510 int cmp;
512 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
513 return (-1);
515 new->key = key;
516 new->value = value;
517 new->height = 1;
518 new->left = NULL;
519 new->right = NULL;
521 if (t->root == NULL)
522 {
523 new->parent = NULL;
524 t->root = new;
525 t->size = 1;
526 return (0);
527 }
529 nptr = t->root;
530 while (42)
531 {
532 cmp = t->compare (nptr->key, new->key);
533 if (cmp == 0)
534 {
535 free_node (new);
536 return (1);
537 }
538 else if (cmp < 0)
539 {
540 /* nptr < new */
541 if (nptr->right == NULL)
542 {
543 nptr->right = new;
544 new->parent = nptr;
545 rebalance (t, nptr);
546 break;
547 }
548 else
549 {
550 nptr = nptr->right;
551 }
552 }
553 else /* if (cmp > 0) */
554 {
555 /* nptr > new */
556 if (nptr->left == NULL)
557 {
558 nptr->left = new;
559 new->parent = nptr;
560 rebalance (t, nptr);
561 break;
562 }
563 else
564 {
565 nptr = nptr->left;
566 }
567 }
568 } /* while (42) */
570 verify_tree (t->root);
571 ++t->size;
572 return (0);
573 } /* int c_avl_insert */
575 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
576 {
577 c_avl_node_t *n;
578 int status;
580 assert (t != NULL);
582 n = search (t, key);
583 if (n == NULL)
584 return (-1);
586 if (rkey != NULL)
587 *rkey = n->key;
588 if (rvalue != NULL)
589 *rvalue = n->value;
591 status = _remove (t, n);
592 verify_tree (t->root);
593 --t->size;
594 return (status);
595 } /* void *c_avl_remove */
597 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
598 {
599 c_avl_node_t *n;
601 assert (t != NULL);
603 n = search (t, key);
604 if (n == NULL)
605 return (-1);
607 if (value != NULL)
608 *value = n->value;
610 return (0);
611 }
613 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
614 {
615 c_avl_node_t *n;
616 c_avl_node_t *p;
618 if ((key == NULL) || (value == NULL))
619 return (-1);
620 if (t->root == NULL)
621 return (-1);
623 n = t->root;
624 while ((n->left != NULL) || (n->right != NULL))
625 {
626 if (n->left == NULL)
627 {
628 n = n->right;
629 continue;
630 }
631 else if (n->right == NULL)
632 {
633 n = n->left;
634 continue;
635 }
637 if (n->left->height > n->right->height)
638 n = n->left;
639 else
640 n = n->right;
641 }
643 p = n->parent;
644 if (p == NULL)
645 t->root = NULL;
646 else if (p->left == n)
647 p->left = NULL;
648 else
649 p->right = NULL;
651 *key = n->key;
652 *value = n->value;
654 free_node (n);
655 --t->size;
656 rebalance (t, p);
658 return (0);
659 } /* int c_avl_pick */
661 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
662 {
663 c_avl_iterator_t *iter;
665 if (t == NULL)
666 return (NULL);
668 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
669 if (iter == NULL)
670 return (NULL);
671 memset (iter, '\0', sizeof (c_avl_iterator_t));
672 iter->tree = t;
674 return (iter);
675 } /* c_avl_iterator_t *c_avl_get_iterator */
677 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
678 {
679 c_avl_node_t *n;
681 if ((iter == NULL) || (key == NULL) || (value == NULL))
682 return (-1);
684 if (iter->node == NULL)
685 {
686 for (n = iter->tree->root; n != NULL; n = n->left)
687 if (n->left == NULL)
688 break;
689 iter->node = n;
690 }
691 else
692 {
693 n = c_avl_node_next (iter->node);
694 }
696 if (n == NULL)
697 return (-1);
699 iter->node = n;
700 *key = n->key;
701 *value = n->value;
703 return (0);
704 } /* int c_avl_iterator_next */
706 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
707 {
708 c_avl_node_t *n;
710 if ((iter == NULL) || (key == NULL) || (value == NULL))
711 return (-1);
713 if (iter->node == NULL)
714 {
715 for (n = iter->tree->root; n != NULL; n = n->left)
716 if (n->right == NULL)
717 break;
718 iter->node = n;
719 }
720 else
721 {
722 n = c_avl_node_prev (iter->node);
723 }
725 if (n == NULL)
726 return (-1);
728 iter->node = n;
729 *key = n->key;
730 *value = n->value;
732 return (0);
733 } /* int c_avl_iterator_prev */
735 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
736 {
737 free (iter);
738 }
740 int c_avl_size (c_avl_tree_t *t)
741 {
742 if (t == NULL)
743 return (0);
744 return (t->size);
745 }