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 **/
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include <string.h>
25 #include <assert.h>
27 #include "utils_avltree.h"
29 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
30 - (((n)->right == NULL) ? 0 : (n)->right->height))
32 /*
33 * private data types
34 */
35 struct avl_node_s
36 {
37 void *key;
38 void *value;
40 int height;
41 struct avl_node_s *left;
42 struct avl_node_s *right;
43 struct avl_node_s *parent;
44 };
45 typedef struct avl_node_s avl_node_t;
47 struct avl_tree_s
48 {
49 avl_node_t *root;
50 int (*compare) (const void *, const void *);
51 };
53 struct avl_iterator_s
54 {
55 avl_tree_t *tree;
56 avl_node_t *node;
57 };
59 /*
60 * private functions
61 */
62 #if 0
63 static void verify_tree (avl_node_t *n)
64 {
65 if (n == NULL)
66 return;
68 verify_tree (n->left);
69 verify_tree (n->right);
71 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
72 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
73 } /* void verify_tree */
74 #else
75 # define verify_tree(n) /**/
76 #endif
78 static void free_node (avl_node_t *n)
79 {
80 if (n == NULL)
81 return;
83 if (n->left != NULL)
84 free_node (n->left);
85 if (n->right != NULL)
86 free_node (n->right);
88 free (n);
89 }
91 static int calc_height (avl_node_t *n)
92 {
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)
103 ? height_left
104 : height_right) + 1);
105 } /* int calc_height */
107 static avl_node_t *search (avl_tree_t *t, const void *key)
108 {
109 avl_node_t *n;
110 int cmp;
112 n = t->root;
113 while (n != NULL)
114 {
115 cmp = t->compare (key, n->key);
116 if (cmp == 0)
117 return (n);
118 else if (cmp < 0)
119 n = n->left;
120 else
121 n = n->right;
122 }
124 return (NULL);
125 }
127 /* (x) (y)
128 * / \ / \
129 * (y) /\ /\ (x)
130 * / \ /_c\ ==> / a\ / \
131 * /\ /\ /____\/\ /\
132 * / a\ /_b\ /_b\ /_c\
133 * /____\
134 */
135 static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
136 {
137 avl_node_t *p;
138 avl_node_t *y;
139 avl_node_t *b;
141 p = x->parent;
142 y = x->left;
143 b = y->right;
145 x->left = b;
146 if (b != NULL)
147 b->parent = x;
149 x->parent = y;
150 y->right = x;
152 y->parent = p;
153 assert ((p == NULL) || (p->left == x) || (p->right == x));
154 if (p == NULL)
155 t->root = y;
156 else if (p->left == x)
157 p->left = y;
158 else
159 p->right = y;
161 x->height = calc_height (x);
162 y->height = calc_height (y);
164 return (y);
165 } /* void rotate_left */
167 /*
168 * (x) (y)
169 * / \ / \
170 * /\ (y) (x) /\
171 * /_a\ / \ ==> / \ / c\
172 * /\ /\ /\ /\/____\
173 * /_b\ / c\ /_a\ /_b\
174 * /____\
175 */
176 static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
177 {
178 avl_node_t *p;
179 avl_node_t *y;
180 avl_node_t *b;
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 avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_t *x)
209 {
210 rotate_left (t, x->left);
211 return (rotate_right (t, x));
212 } /* void rotate_left_right */
214 static avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_t *x)
215 {
216 rotate_right (t, x->right);
217 return (rotate_left (t, x));
218 } /* void rotate_right_left */
220 static void rebalance (avl_tree_t *t, avl_node_t *n)
221 {
222 int b_top;
223 int b_bottom;
225 while (n != NULL)
226 {
227 b_top = BALANCE (n);
228 assert ((b_top >= -2) && (b_top <= 2));
230 if (b_top == -2)
231 {
232 assert (n->right != NULL);
233 b_bottom = BALANCE (n->right);
234 assert ((b_bottom >= -1) || (b_bottom <= 1));
235 if (b_bottom == 1)
236 n = rotate_right_left (t, n);
237 else
238 n = rotate_left (t, n);
239 }
240 else if (b_top == 2)
241 {
242 assert (n->left != NULL);
243 b_bottom = BALANCE (n->left);
244 assert ((b_bottom >= -1) || (b_bottom <= 1));
245 if (b_bottom == -1)
246 n = rotate_left_right (t, n);
247 else
248 n = rotate_right (t, n);
249 }
250 else
251 {
252 int height = calc_height (n);
253 if (height == n->height)
254 break;
255 n->height = height;
256 }
258 assert (n->height == calc_height (n));
260 n = n->parent;
261 } /* while (n != NULL) */
262 } /* void rebalance */
264 static avl_node_t *avl_node_next (avl_tree_t *t, avl_node_t *n)
265 {
266 avl_node_t *r; /* return node */
268 if (n == NULL)
269 {
270 return (NULL);
271 }
273 /* If we can't descent any further, we have to backtrack to the first
274 * parent that's bigger than we, i. e. who's _left_ child we are. */
275 if (n->right == NULL)
276 {
277 r = n->parent;
278 while ((r != NULL) && (r->parent != NULL))
279 {
280 if (r->left == n)
281 break;
282 n = r;
283 r = n->parent;
284 }
286 /* n->right == NULL && r == NULL => t is root and has no next
287 * r->left != n => r->right = n => r->parent == NULL */
288 if ((r == NULL) || (r->left != n))
289 {
290 assert ((r == NULL) || (r->parent == NULL));
291 return (NULL);
292 }
293 else
294 {
295 assert (r->left == n);
296 return (r);
297 }
298 }
299 else
300 {
301 r = n->right;
302 while (r->left != NULL)
303 r = r->left;
304 }
306 return (r);
307 } /* avl_node_t *avl_node_next */
309 static avl_node_t *avl_node_prev (avl_tree_t *t, avl_node_t *n)
310 {
311 avl_node_t *r; /* return node */
313 if (n == NULL)
314 {
315 return (NULL);
316 }
318 /* If we can't descent any further, we have to backtrack to the first
319 * parent that's smaller than we, i. e. who's _right_ child we are. */
320 if (n->left == NULL)
321 {
322 r = n->parent;
323 while ((r != NULL) && (r->parent != NULL))
324 {
325 if (r->right == n)
326 break;
327 n = r;
328 r = n->parent;
329 }
331 /* n->left == NULL && r == NULL => t is root and has no next
332 * r->right != n => r->left = n => r->parent == NULL */
333 if ((r == NULL) || (r->right != n))
334 {
335 assert ((r == NULL) || (r->parent == NULL));
336 return (NULL);
337 }
338 else
339 {
340 assert (r->right == n);
341 return (r);
342 }
343 }
344 else
345 {
346 r = n->left;
347 while (r->right != NULL)
348 r = r->right;
349 }
351 return (r);
352 } /* avl_node_t *avl_node_prev */
354 static int _remove (avl_tree_t *t, avl_node_t *n)
355 {
356 assert ((t != NULL) && (n != NULL));
358 if ((n->left != NULL) && (n->right != NULL))
359 {
360 avl_node_t *r; /* replacement node */
361 if (BALANCE (n) > 0) /* left subtree is higher */
362 {
363 assert (n->left != NULL);
364 r = avl_node_prev (t, n);
366 }
367 else /* right subtree is higher */
368 {
369 assert (n->right != NULL);
370 r = avl_node_next (t, n);
371 }
373 assert ((r->left == NULL) || (r->right == NULL));
375 /* copy content */
376 n->key = r->key;
377 n->value = r->value;
379 n = r;
380 }
382 assert ((n->left == NULL) || (n->right == NULL));
384 if ((n->left == NULL) && (n->right == NULL))
385 {
386 /* Deleting a leave is easy */
387 if (n->parent == NULL)
388 {
389 assert (t->root == n);
390 t->root = NULL;
391 }
392 else
393 {
394 assert ((n->parent->left == n)
395 || (n->parent->right == n));
396 if (n->parent->left == n)
397 n->parent->left = NULL;
398 else
399 n->parent->right = NULL;
401 rebalance (t, n->parent);
402 }
404 free_node (n);
405 }
406 else if (n->left == NULL)
407 {
408 assert (BALANCE (n) == -1);
409 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
410 if (n->parent == NULL)
411 {
412 assert (t->root == n);
413 t->root = n->right;
414 }
415 else if (n->parent->left == n)
416 {
417 n->parent->left = n->right;
418 }
419 else
420 {
421 n->parent->right = n->right;
422 }
423 n->right->parent = n->parent;
425 if (n->parent != NULL)
426 rebalance (t, n->parent);
428 n->right = NULL;
429 free_node (n);
430 }
431 else if (n->right == NULL)
432 {
433 assert (BALANCE (n) == 1);
434 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
435 if (n->parent == NULL)
436 {
437 assert (t->root == n);
438 t->root = n->left;
439 }
440 else if (n->parent->left == n)
441 {
442 n->parent->left = n->left;
443 }
444 else
445 {
446 n->parent->right = n->left;
447 }
448 n->left->parent = n->parent;
450 if (n->parent != NULL)
451 rebalance (t, n->parent);
453 n->left = NULL;
454 free_node (n);
455 }
456 else
457 {
458 assert (0);
459 }
461 return (0);
462 } /* void *_remove */
464 /*
465 * public functions
466 */
467 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
468 {
469 avl_tree_t *t;
471 if (compare == NULL)
472 return (NULL);
474 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
475 return (NULL);
477 t->root = NULL;
478 t->compare = compare;
480 return (t);
481 }
483 void avl_destroy (avl_tree_t *t)
484 {
485 free_node (t->root);
486 free (t);
487 }
489 int avl_insert (avl_tree_t *t, void *key, void *value)
490 {
491 avl_node_t *new;
492 avl_node_t *nptr;
493 int cmp;
495 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
496 return (-1);
498 new->key = key;
499 new->value = value;
500 new->height = 1;
501 new->left = NULL;
502 new->right = NULL;
504 if (t->root == NULL)
505 {
506 new->parent = NULL;
507 t->root = new;
508 return (0);
509 }
511 nptr = t->root;
512 while (42)
513 {
514 cmp = t->compare (nptr->key, new->key);
515 if (cmp == 0)
516 {
517 free_node (new);
518 return (-1);
519 }
520 else if (cmp < 0)
521 {
522 /* nptr < new */
523 if (nptr->right == NULL)
524 {
525 nptr->right = new;
526 new->parent = nptr;
527 rebalance (t, nptr);
528 break;
529 }
530 else
531 {
532 nptr = nptr->right;
533 }
534 }
535 else /* if (cmp > 0) */
536 {
537 /* nptr > new */
538 if (nptr->left == NULL)
539 {
540 nptr->left = new;
541 new->parent = nptr;
542 rebalance (t, nptr);
543 break;
544 }
545 else
546 {
547 nptr = nptr->left;
548 }
549 }
550 } /* while (42) */
552 verify_tree (t->root);
553 return (0);
554 } /* int avl_insert */
556 int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue)
557 {
558 avl_node_t *n;
559 int status;
561 assert (t != NULL);
563 n = search (t, key);
564 if (n == NULL)
565 return (-1);
567 if (rkey != NULL)
568 *rkey = n->key;
569 if (rvalue != NULL)
570 *rvalue = n->value;
572 status = _remove (t, n);
573 verify_tree (t->root);
574 return (status);
575 } /* void *avl_remove */
577 int avl_get (avl_tree_t *t, const void *key, void **value)
578 {
579 avl_node_t *n;
581 assert (value != NULL);
583 n = search (t, key);
584 if (n == NULL)
585 return (-1);
587 *value = n->value;
589 return (0);
590 }
592 int avl_pick (avl_tree_t *t, void **key, void **value)
593 {
594 avl_node_t *n;
595 avl_node_t *p;
597 if ((key == NULL) || (value == NULL))
598 return (-1);
599 if (t->root == NULL)
600 return (-1);
602 n = t->root;
603 while ((n->left != NULL) || (n->right != NULL))
604 {
605 int height_left = (n->left == NULL) ? 0 : n->left->height;
606 int height_right = (n->right == NULL) ? 0 : n->right->height;
608 if (height_left > height_right)
609 n = n->left;
610 else
611 n = n->right;
612 }
614 p = n->parent;
615 if (p == NULL)
616 t->root = NULL;
617 else if (p->left == n)
618 p->left = NULL;
619 else
620 p->right = NULL;
622 *key = n->key;
623 *value = n->value;
625 free_node (n);
626 rebalance (t, p);
628 return (0);
629 } /* int avl_pick */
631 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
632 {
633 avl_iterator_t *iter;
635 if (t == NULL)
636 return (NULL);
638 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
639 if (iter == NULL)
640 return (NULL);
641 memset (iter, '\0', sizeof (avl_iterator_t));
642 iter->tree = t;
644 return (iter);
645 } /* avl_iterator_t *avl_get_iterator */
647 int avl_iterator_next (avl_iterator_t *iter, void **key, void **value)
648 {
649 avl_node_t *n;
651 if ((iter == NULL) || (key == NULL) || (value == NULL))
652 return (-1);
654 if (iter->node == NULL)
655 {
656 for (n = iter->tree->root; n != NULL; n = n->left)
657 if (n->left == NULL)
658 break;
659 iter->node = n;
660 }
661 else
662 {
663 n = avl_node_next (iter->tree, iter->node);
664 }
666 if (n == NULL)
667 return (-1);
669 iter->node = n;
670 *key = n->key;
671 *value = n->value;
673 return (0);
674 } /* int avl_iterator_next */
676 int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value)
677 {
678 avl_node_t *n;
680 if ((iter == NULL) || (key == NULL) || (value == NULL))
681 return (-1);
683 if (iter->node == NULL)
684 {
685 for (n = iter->tree->root; n != NULL; n = n->left)
686 if (n->right == NULL)
687 break;
688 iter->node = n;
689 }
690 else
691 {
692 n = avl_node_prev (iter->tree, iter->node);
693 }
695 if (n == NULL)
696 return (-1);
698 iter->node = n;
699 *key = n->key;
700 *value = n->value;
702 return (0);
703 } /* int avl_iterator_prev */
705 void avl_iterator_destroy (avl_iterator_t *iter)
706 {
707 free (iter);
708 }