1 /**
2 * collectd - src/utils_avltree.c
3 * Copyright (C) 2006,2007 Florian octo Forster
4 *
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.
9 *
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.
14 *
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
18 *
19 * Authors:
20 * Florian octo Forster <octo at verplant.org>
21 **/
23 #include "config.h"
25 #include <stdlib.h>
26 #include <stdio.h>
27 #include <string.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 p = x->parent;
146 y = x->left;
147 b = y->right;
149 x->left = b;
150 if (b != NULL)
151 b->parent = x;
153 x->parent = y;
154 y->right = x;
156 y->parent = p;
157 assert ((p == NULL) || (p->left == x) || (p->right == x));
158 if (p == NULL)
159 t->root = y;
160 else if (p->left == x)
161 p->left = y;
162 else
163 p->right = y;
165 x->height = calc_height (x);
166 y->height = calc_height (y);
168 return (y);
169 } /* void rotate_left */
171 /*
172 * (x) (y)
173 * / \ / \
174 * /\ (y) (x) /\
175 * /_a\ / \ ==> / \ / c\
176 * /\ /\ /\ /\/____\
177 * /_b\ / c\ /_a\ /_b\
178 * /____\
179 */
180 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
181 {
182 c_avl_node_t *p;
183 c_avl_node_t *y;
184 c_avl_node_t *b;
186 p = x->parent;
187 y = x->right;
188 b = y->left;
190 x->right = b;
191 if (b != NULL)
192 b->parent = x;
194 x->parent = y;
195 y->left = x;
197 y->parent = p;
198 assert ((p == NULL) || (p->left == x) || (p->right == x));
199 if (p == NULL)
200 t->root = y;
201 else if (p->left == x)
202 p->left = y;
203 else
204 p->right = y;
206 x->height = calc_height (x);
207 y->height = calc_height (y);
209 return (y);
210 } /* void rotate_left */
212 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
213 {
214 rotate_left (t, x->left);
215 return (rotate_right (t, x));
216 } /* void rotate_left_right */
218 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
219 {
220 rotate_right (t, x->right);
221 return (rotate_left (t, x));
222 } /* void rotate_right_left */
224 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
225 {
226 int b_top;
227 int b_bottom;
229 while (n != NULL)
230 {
231 b_top = BALANCE (n);
232 assert ((b_top >= -2) && (b_top <= 2));
234 if (b_top == -2)
235 {
236 assert (n->right != NULL);
237 b_bottom = BALANCE (n->right);
238 assert ((b_bottom >= -1) || (b_bottom <= 1));
239 if (b_bottom == 1)
240 n = rotate_right_left (t, n);
241 else
242 n = rotate_left (t, n);
243 }
244 else if (b_top == 2)
245 {
246 assert (n->left != NULL);
247 b_bottom = BALANCE (n->left);
248 assert ((b_bottom >= -1) || (b_bottom <= 1));
249 if (b_bottom == -1)
250 n = rotate_left_right (t, n);
251 else
252 n = rotate_right (t, n);
253 }
254 else
255 {
256 int height = calc_height (n);
257 if (height == n->height)
258 break;
259 n->height = height;
260 }
262 assert (n->height == calc_height (n));
264 n = n->parent;
265 } /* while (n != NULL) */
266 } /* void rebalance */
268 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
269 {
270 c_avl_node_t *r; /* return node */
272 if (n == NULL)
273 {
274 return (NULL);
275 }
277 /* If we can't descent any further, we have to backtrack to the first
278 * parent that's bigger than we, i. e. who's _left_ child we are. */
279 if (n->right == NULL)
280 {
281 r = n->parent;
282 while ((r != NULL) && (r->parent != NULL))
283 {
284 if (r->left == n)
285 break;
286 n = r;
287 r = n->parent;
288 }
290 /* n->right == NULL && r == NULL => t is root and has no next
291 * r->left != n => r->right = n => r->parent == NULL */
292 if ((r == NULL) || (r->left != n))
293 {
294 assert ((r == NULL) || (r->parent == NULL));
295 return (NULL);
296 }
297 else
298 {
299 assert (r->left == n);
300 return (r);
301 }
302 }
303 else
304 {
305 r = n->right;
306 while (r->left != NULL)
307 r = r->left;
308 }
310 return (r);
311 } /* c_avl_node_t *c_avl_node_next */
313 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
314 {
315 c_avl_node_t *r; /* return node */
317 if (n == NULL)
318 {
319 return (NULL);
320 }
322 /* If we can't descent any further, we have to backtrack to the first
323 * parent that's smaller than we, i. e. who's _right_ child we are. */
324 if (n->left == NULL)
325 {
326 r = n->parent;
327 while ((r != NULL) && (r->parent != NULL))
328 {
329 if (r->right == n)
330 break;
331 n = r;
332 r = n->parent;
333 }
335 /* n->left == NULL && r == NULL => t is root and has no next
336 * r->right != n => r->left = n => r->parent == NULL */
337 if ((r == NULL) || (r->right != n))
338 {
339 assert ((r == NULL) || (r->parent == NULL));
340 return (NULL);
341 }
342 else
343 {
344 assert (r->right == n);
345 return (r);
346 }
347 }
348 else
349 {
350 r = n->left;
351 while (r->right != NULL)
352 r = r->right;
353 }
355 return (r);
356 } /* c_avl_node_t *c_avl_node_prev */
358 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
359 {
360 assert ((t != NULL) && (n != NULL));
362 if ((n->left != NULL) && (n->right != NULL))
363 {
364 c_avl_node_t *r; /* replacement node */
365 if (BALANCE (n) > 0) /* left subtree is higher */
366 {
367 assert (n->left != NULL);
368 r = c_avl_node_prev (n);
370 }
371 else /* right subtree is higher */
372 {
373 assert (n->right != NULL);
374 r = c_avl_node_next (n);
375 }
377 assert ((r->left == NULL) || (r->right == NULL));
379 /* copy content */
380 n->key = r->key;
381 n->value = r->value;
383 n = r;
384 }
386 assert ((n->left == NULL) || (n->right == NULL));
388 if ((n->left == NULL) && (n->right == NULL))
389 {
390 /* Deleting a leave is easy */
391 if (n->parent == NULL)
392 {
393 assert (t->root == n);
394 t->root = NULL;
395 }
396 else
397 {
398 assert ((n->parent->left == n)
399 || (n->parent->right == n));
400 if (n->parent->left == n)
401 n->parent->left = NULL;
402 else
403 n->parent->right = NULL;
405 rebalance (t, n->parent);
406 }
408 free_node (n);
409 }
410 else if (n->left == NULL)
411 {
412 assert (BALANCE (n) == -1);
413 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
414 if (n->parent == NULL)
415 {
416 assert (t->root == n);
417 t->root = n->right;
418 }
419 else if (n->parent->left == n)
420 {
421 n->parent->left = n->right;
422 }
423 else
424 {
425 n->parent->right = n->right;
426 }
427 n->right->parent = n->parent;
429 if (n->parent != NULL)
430 rebalance (t, n->parent);
432 n->right = NULL;
433 free_node (n);
434 }
435 else if (n->right == NULL)
436 {
437 assert (BALANCE (n) == 1);
438 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
439 if (n->parent == NULL)
440 {
441 assert (t->root == n);
442 t->root = n->left;
443 }
444 else if (n->parent->left == n)
445 {
446 n->parent->left = n->left;
447 }
448 else
449 {
450 n->parent->right = n->left;
451 }
452 n->left->parent = n->parent;
454 if (n->parent != NULL)
455 rebalance (t, n->parent);
457 n->left = NULL;
458 free_node (n);
459 }
460 else
461 {
462 assert (0);
463 }
465 return (0);
466 } /* void *_remove */
468 /*
469 * public functions
470 */
471 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
472 {
473 c_avl_tree_t *t;
475 if (compare == NULL)
476 return (NULL);
478 if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
479 return (NULL);
481 t->root = NULL;
482 t->compare = compare;
483 t->size = 0;
485 return (t);
486 }
488 void c_avl_destroy (c_avl_tree_t *t)
489 {
490 if (t == NULL)
491 return;
492 free_node (t->root);
493 free (t);
494 }
496 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
497 {
498 c_avl_node_t *new;
499 c_avl_node_t *nptr;
500 int cmp;
502 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
503 return (-1);
505 new->key = key;
506 new->value = value;
507 new->height = 1;
508 new->left = NULL;
509 new->right = NULL;
511 if (t->root == NULL)
512 {
513 new->parent = NULL;
514 t->root = new;
515 t->size = 1;
516 return (0);
517 }
519 nptr = t->root;
520 while (42)
521 {
522 cmp = t->compare (nptr->key, new->key);
523 if (cmp == 0)
524 {
525 free_node (new);
526 return (1);
527 }
528 else if (cmp < 0)
529 {
530 /* nptr < new */
531 if (nptr->right == NULL)
532 {
533 nptr->right = new;
534 new->parent = nptr;
535 rebalance (t, nptr);
536 break;
537 }
538 else
539 {
540 nptr = nptr->right;
541 }
542 }
543 else /* if (cmp > 0) */
544 {
545 /* nptr > new */
546 if (nptr->left == NULL)
547 {
548 nptr->left = new;
549 new->parent = nptr;
550 rebalance (t, nptr);
551 break;
552 }
553 else
554 {
555 nptr = nptr->left;
556 }
557 }
558 } /* while (42) */
560 verify_tree (t->root);
561 ++t->size;
562 return (0);
563 } /* int c_avl_insert */
565 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
566 {
567 c_avl_node_t *n;
568 int status;
570 assert (t != NULL);
572 n = search (t, key);
573 if (n == NULL)
574 return (-1);
576 if (rkey != NULL)
577 *rkey = n->key;
578 if (rvalue != NULL)
579 *rvalue = n->value;
581 status = _remove (t, n);
582 verify_tree (t->root);
583 --t->size;
584 return (status);
585 } /* void *c_avl_remove */
587 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
588 {
589 c_avl_node_t *n;
591 assert (t != NULL);
593 n = search (t, key);
594 if (n == NULL)
595 return (-1);
597 if (value != NULL)
598 *value = n->value;
600 return (0);
601 }
603 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
604 {
605 c_avl_node_t *n;
606 c_avl_node_t *p;
608 if ((key == NULL) || (value == NULL))
609 return (-1);
610 if (t->root == NULL)
611 return (-1);
613 n = t->root;
614 while ((n->left != NULL) || (n->right != NULL))
615 {
616 int height_left = (n->left == NULL) ? 0 : n->left->height;
617 int height_right = (n->right == NULL) ? 0 : n->right->height;
619 if (height_left > height_right)
620 n = n->left;
621 else
622 n = n->right;
623 }
625 p = n->parent;
626 if (p == NULL)
627 t->root = NULL;
628 else if (p->left == n)
629 p->left = NULL;
630 else
631 p->right = NULL;
633 *key = n->key;
634 *value = n->value;
636 free_node (n);
637 rebalance (t, p);
639 return (0);
640 } /* int c_avl_pick */
642 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
643 {
644 c_avl_iterator_t *iter;
646 if (t == NULL)
647 return (NULL);
649 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
650 if (iter == NULL)
651 return (NULL);
652 memset (iter, '\0', sizeof (c_avl_iterator_t));
653 iter->tree = t;
655 return (iter);
656 } /* c_avl_iterator_t *c_avl_get_iterator */
658 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
659 {
660 c_avl_node_t *n;
662 if ((iter == NULL) || (key == NULL) || (value == NULL))
663 return (-1);
665 if (iter->node == NULL)
666 {
667 for (n = iter->tree->root; n != NULL; n = n->left)
668 if (n->left == NULL)
669 break;
670 iter->node = n;
671 }
672 else
673 {
674 n = c_avl_node_next (iter->node);
675 }
677 if (n == NULL)
678 return (-1);
680 iter->node = n;
681 *key = n->key;
682 *value = n->value;
684 return (0);
685 } /* int c_avl_iterator_next */
687 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
688 {
689 c_avl_node_t *n;
691 if ((iter == NULL) || (key == NULL) || (value == NULL))
692 return (-1);
694 if (iter->node == NULL)
695 {
696 for (n = iter->tree->root; n != NULL; n = n->left)
697 if (n->right == NULL)
698 break;
699 iter->node = n;
700 }
701 else
702 {
703 n = c_avl_node_prev (iter->node);
704 }
706 if (n == NULL)
707 return (-1);
709 iter->node = n;
710 *key = n->key;
711 *value = n->value;
713 return (0);
714 } /* int c_avl_iterator_prev */
716 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
717 {
718 free (iter);
719 }
721 int c_avl_size (c_avl_tree_t *t)
722 {
723 if (t == NULL)
724 return (0);
725 return (t->size);
726 }