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 free_node (t->root);
491 free (t);
492 }
494 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
495 {
496 c_avl_node_t *new;
497 c_avl_node_t *nptr;
498 int cmp;
500 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
501 return (-1);
503 new->key = key;
504 new->value = value;
505 new->height = 1;
506 new->left = NULL;
507 new->right = NULL;
509 if (t->root == NULL)
510 {
511 new->parent = NULL;
512 t->root = new;
513 return (0);
514 }
516 nptr = t->root;
517 while (42)
518 {
519 cmp = t->compare (nptr->key, new->key);
520 if (cmp == 0)
521 {
522 free_node (new);
523 return (1);
524 }
525 else if (cmp < 0)
526 {
527 /* nptr < new */
528 if (nptr->right == NULL)
529 {
530 nptr->right = new;
531 new->parent = nptr;
532 rebalance (t, nptr);
533 break;
534 }
535 else
536 {
537 nptr = nptr->right;
538 }
539 }
540 else /* if (cmp > 0) */
541 {
542 /* nptr > new */
543 if (nptr->left == NULL)
544 {
545 nptr->left = new;
546 new->parent = nptr;
547 rebalance (t, nptr);
548 break;
549 }
550 else
551 {
552 nptr = nptr->left;
553 }
554 }
555 } /* while (42) */
557 verify_tree (t->root);
558 ++t->size;
559 return (0);
560 } /* int c_avl_insert */
562 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
563 {
564 c_avl_node_t *n;
565 int status;
567 assert (t != NULL);
569 n = search (t, key);
570 if (n == NULL)
571 return (-1);
573 if (rkey != NULL)
574 *rkey = n->key;
575 if (rvalue != NULL)
576 *rvalue = n->value;
578 status = _remove (t, n);
579 verify_tree (t->root);
580 --t->size;
581 return (status);
582 } /* void *c_avl_remove */
584 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
585 {
586 c_avl_node_t *n;
588 assert (t != NULL);
590 n = search (t, key);
591 if (n == NULL)
592 return (-1);
594 if (value != NULL)
595 *value = n->value;
597 return (0);
598 }
600 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
601 {
602 c_avl_node_t *n;
603 c_avl_node_t *p;
605 if ((key == NULL) || (value == NULL))
606 return (-1);
607 if (t->root == NULL)
608 return (-1);
610 n = t->root;
611 while ((n->left != NULL) || (n->right != NULL))
612 {
613 int height_left = (n->left == NULL) ? 0 : n->left->height;
614 int height_right = (n->right == NULL) ? 0 : n->right->height;
616 if (height_left > height_right)
617 n = n->left;
618 else
619 n = n->right;
620 }
622 p = n->parent;
623 if (p == NULL)
624 t->root = NULL;
625 else if (p->left == n)
626 p->left = NULL;
627 else
628 p->right = NULL;
630 *key = n->key;
631 *value = n->value;
633 free_node (n);
634 rebalance (t, p);
636 return (0);
637 } /* int c_avl_pick */
639 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
640 {
641 c_avl_iterator_t *iter;
643 if (t == NULL)
644 return (NULL);
646 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
647 if (iter == NULL)
648 return (NULL);
649 memset (iter, '\0', sizeof (c_avl_iterator_t));
650 iter->tree = t;
652 return (iter);
653 } /* c_avl_iterator_t *c_avl_get_iterator */
655 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
656 {
657 c_avl_node_t *n;
659 if ((iter == NULL) || (key == NULL) || (value == NULL))
660 return (-1);
662 if (iter->node == NULL)
663 {
664 for (n = iter->tree->root; n != NULL; n = n->left)
665 if (n->left == NULL)
666 break;
667 iter->node = n;
668 }
669 else
670 {
671 n = c_avl_node_next (iter->node);
672 }
674 if (n == NULL)
675 return (-1);
677 iter->node = n;
678 *key = n->key;
679 *value = n->value;
681 return (0);
682 } /* int c_avl_iterator_next */
684 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
685 {
686 c_avl_node_t *n;
688 if ((iter == NULL) || (key == NULL) || (value == NULL))
689 return (-1);
691 if (iter->node == NULL)
692 {
693 for (n = iter->tree->root; n != NULL; n = n->left)
694 if (n->right == NULL)
695 break;
696 iter->node = n;
697 }
698 else
699 {
700 n = c_avl_node_prev (iter->node);
701 }
703 if (n == NULL)
704 return (-1);
706 iter->node = n;
707 *key = n->key;
708 *value = n->value;
710 return (0);
711 } /* int c_avl_iterator_prev */
713 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
714 {
715 free (iter);
716 }
718 int c_avl_size (c_avl_tree_t *t)
719 {
720 if (t == NULL)
721 return (0);
722 return (t->size);
723 }