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 avl_node_s
39 {
40 void *key;
41 void *value;
43 int height;
44 struct avl_node_s *left;
45 struct avl_node_s *right;
46 struct avl_node_s *parent;
47 };
48 typedef struct avl_node_s avl_node_t;
50 struct avl_tree_s
51 {
52 avl_node_t *root;
53 int (*compare) (const void *, const void *);
54 };
56 struct avl_iterator_s
57 {
58 avl_tree_t *tree;
59 avl_node_t *node;
60 };
62 /*
63 * private functions
64 */
65 #if 0
66 static void verify_tree (avl_node_t *n)
67 {
68 if (n == NULL)
69 return;
71 verify_tree (n->left);
72 verify_tree (n->right);
74 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
75 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
76 } /* void verify_tree */
77 #else
78 # define verify_tree(n) /**/
79 #endif
81 static void free_node (avl_node_t *n)
82 {
83 if (n == NULL)
84 return;
86 if (n->left != NULL)
87 free_node (n->left);
88 if (n->right != NULL)
89 free_node (n->right);
91 free (n);
92 }
94 static int calc_height (avl_node_t *n)
95 {
96 int height_left;
97 int height_right;
99 if (n == NULL)
100 return (0);
102 height_left = (n->left == NULL) ? 0 : n->left->height;
103 height_right = (n->right == NULL) ? 0 : n->right->height;
105 return (((height_left > height_right)
106 ? height_left
107 : height_right) + 1);
108 } /* int calc_height */
110 static avl_node_t *search (avl_tree_t *t, const void *key)
111 {
112 avl_node_t *n;
113 int cmp;
115 n = t->root;
116 while (n != NULL)
117 {
118 cmp = t->compare (key, n->key);
119 if (cmp == 0)
120 return (n);
121 else if (cmp < 0)
122 n = n->left;
123 else
124 n = n->right;
125 }
127 return (NULL);
128 }
130 /* (x) (y)
131 * / \ / \
132 * (y) /\ /\ (x)
133 * / \ /_c\ ==> / a\ / \
134 * /\ /\ /____\/\ /\
135 * / a\ /_b\ /_b\ /_c\
136 * /____\
137 */
138 static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
139 {
140 avl_node_t *p;
141 avl_node_t *y;
142 avl_node_t *b;
144 p = x->parent;
145 y = x->left;
146 b = y->right;
148 x->left = b;
149 if (b != NULL)
150 b->parent = x;
152 x->parent = y;
153 y->right = x;
155 y->parent = p;
156 assert ((p == NULL) || (p->left == x) || (p->right == x));
157 if (p == NULL)
158 t->root = y;
159 else if (p->left == x)
160 p->left = y;
161 else
162 p->right = y;
164 x->height = calc_height (x);
165 y->height = calc_height (y);
167 return (y);
168 } /* void rotate_left */
170 /*
171 * (x) (y)
172 * / \ / \
173 * /\ (y) (x) /\
174 * /_a\ / \ ==> / \ / c\
175 * /\ /\ /\ /\/____\
176 * /_b\ / c\ /_a\ /_b\
177 * /____\
178 */
179 static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
180 {
181 avl_node_t *p;
182 avl_node_t *y;
183 avl_node_t *b;
185 p = x->parent;
186 y = x->right;
187 b = y->left;
189 x->right = b;
190 if (b != NULL)
191 b->parent = x;
193 x->parent = y;
194 y->left = x;
196 y->parent = p;
197 assert ((p == NULL) || (p->left == x) || (p->right == x));
198 if (p == NULL)
199 t->root = y;
200 else if (p->left == x)
201 p->left = y;
202 else
203 p->right = y;
205 x->height = calc_height (x);
206 y->height = calc_height (y);
208 return (y);
209 } /* void rotate_left */
211 static avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_t *x)
212 {
213 rotate_left (t, x->left);
214 return (rotate_right (t, x));
215 } /* void rotate_left_right */
217 static avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_t *x)
218 {
219 rotate_right (t, x->right);
220 return (rotate_left (t, x));
221 } /* void rotate_right_left */
223 static void rebalance (avl_tree_t *t, avl_node_t *n)
224 {
225 int b_top;
226 int b_bottom;
228 while (n != NULL)
229 {
230 b_top = BALANCE (n);
231 assert ((b_top >= -2) && (b_top <= 2));
233 if (b_top == -2)
234 {
235 assert (n->right != NULL);
236 b_bottom = BALANCE (n->right);
237 assert ((b_bottom >= -1) || (b_bottom <= 1));
238 if (b_bottom == 1)
239 n = rotate_right_left (t, n);
240 else
241 n = rotate_left (t, n);
242 }
243 else if (b_top == 2)
244 {
245 assert (n->left != NULL);
246 b_bottom = BALANCE (n->left);
247 assert ((b_bottom >= -1) || (b_bottom <= 1));
248 if (b_bottom == -1)
249 n = rotate_left_right (t, n);
250 else
251 n = rotate_right (t, n);
252 }
253 else
254 {
255 int height = calc_height (n);
256 if (height == n->height)
257 break;
258 n->height = height;
259 }
261 assert (n->height == calc_height (n));
263 n = n->parent;
264 } /* while (n != NULL) */
265 } /* void rebalance */
267 static avl_node_t *avl_node_next (avl_tree_t *t, avl_node_t *n)
268 {
269 avl_node_t *r; /* return node */
271 if (n == NULL)
272 {
273 return (NULL);
274 }
276 /* If we can't descent any further, we have to backtrack to the first
277 * parent that's bigger than we, i. e. who's _left_ child we are. */
278 if (n->right == NULL)
279 {
280 r = n->parent;
281 while ((r != NULL) && (r->parent != NULL))
282 {
283 if (r->left == n)
284 break;
285 n = r;
286 r = n->parent;
287 }
289 /* n->right == NULL && r == NULL => t is root and has no next
290 * r->left != n => r->right = n => r->parent == NULL */
291 if ((r == NULL) || (r->left != n))
292 {
293 assert ((r == NULL) || (r->parent == NULL));
294 return (NULL);
295 }
296 else
297 {
298 assert (r->left == n);
299 return (r);
300 }
301 }
302 else
303 {
304 r = n->right;
305 while (r->left != NULL)
306 r = r->left;
307 }
309 return (r);
310 } /* avl_node_t *avl_node_next */
312 static avl_node_t *avl_node_prev (avl_tree_t *t, avl_node_t *n)
313 {
314 avl_node_t *r; /* return node */
316 if (n == NULL)
317 {
318 return (NULL);
319 }
321 /* If we can't descent any further, we have to backtrack to the first
322 * parent that's smaller than we, i. e. who's _right_ child we are. */
323 if (n->left == NULL)
324 {
325 r = n->parent;
326 while ((r != NULL) && (r->parent != NULL))
327 {
328 if (r->right == n)
329 break;
330 n = r;
331 r = n->parent;
332 }
334 /* n->left == NULL && r == NULL => t is root and has no next
335 * r->right != n => r->left = n => r->parent == NULL */
336 if ((r == NULL) || (r->right != n))
337 {
338 assert ((r == NULL) || (r->parent == NULL));
339 return (NULL);
340 }
341 else
342 {
343 assert (r->right == n);
344 return (r);
345 }
346 }
347 else
348 {
349 r = n->left;
350 while (r->right != NULL)
351 r = r->right;
352 }
354 return (r);
355 } /* avl_node_t *avl_node_prev */
357 static int _remove (avl_tree_t *t, avl_node_t *n)
358 {
359 assert ((t != NULL) && (n != NULL));
361 if ((n->left != NULL) && (n->right != NULL))
362 {
363 avl_node_t *r; /* replacement node */
364 if (BALANCE (n) > 0) /* left subtree is higher */
365 {
366 assert (n->left != NULL);
367 r = avl_node_prev (t, n);
369 }
370 else /* right subtree is higher */
371 {
372 assert (n->right != NULL);
373 r = avl_node_next (t, n);
374 }
376 assert ((r->left == NULL) || (r->right == NULL));
378 /* copy content */
379 n->key = r->key;
380 n->value = r->value;
382 n = r;
383 }
385 assert ((n->left == NULL) || (n->right == NULL));
387 if ((n->left == NULL) && (n->right == NULL))
388 {
389 /* Deleting a leave is easy */
390 if (n->parent == NULL)
391 {
392 assert (t->root == n);
393 t->root = NULL;
394 }
395 else
396 {
397 assert ((n->parent->left == n)
398 || (n->parent->right == n));
399 if (n->parent->left == n)
400 n->parent->left = NULL;
401 else
402 n->parent->right = NULL;
404 rebalance (t, n->parent);
405 }
407 free_node (n);
408 }
409 else if (n->left == NULL)
410 {
411 assert (BALANCE (n) == -1);
412 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
413 if (n->parent == NULL)
414 {
415 assert (t->root == n);
416 t->root = n->right;
417 }
418 else if (n->parent->left == n)
419 {
420 n->parent->left = n->right;
421 }
422 else
423 {
424 n->parent->right = n->right;
425 }
426 n->right->parent = n->parent;
428 if (n->parent != NULL)
429 rebalance (t, n->parent);
431 n->right = NULL;
432 free_node (n);
433 }
434 else if (n->right == NULL)
435 {
436 assert (BALANCE (n) == 1);
437 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
438 if (n->parent == NULL)
439 {
440 assert (t->root == n);
441 t->root = n->left;
442 }
443 else if (n->parent->left == n)
444 {
445 n->parent->left = n->left;
446 }
447 else
448 {
449 n->parent->right = n->left;
450 }
451 n->left->parent = n->parent;
453 if (n->parent != NULL)
454 rebalance (t, n->parent);
456 n->left = NULL;
457 free_node (n);
458 }
459 else
460 {
461 assert (0);
462 }
464 return (0);
465 } /* void *_remove */
467 /*
468 * public functions
469 */
470 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
471 {
472 avl_tree_t *t;
474 if (compare == NULL)
475 return (NULL);
477 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
478 return (NULL);
480 t->root = NULL;
481 t->compare = compare;
483 return (t);
484 }
486 void avl_destroy (avl_tree_t *t)
487 {
488 free_node (t->root);
489 free (t);
490 }
492 int avl_insert (avl_tree_t *t, void *key, void *value)
493 {
494 avl_node_t *new;
495 avl_node_t *nptr;
496 int cmp;
498 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
499 return (-1);
501 new->key = key;
502 new->value = value;
503 new->height = 1;
504 new->left = NULL;
505 new->right = NULL;
507 if (t->root == NULL)
508 {
509 new->parent = NULL;
510 t->root = new;
511 return (0);
512 }
514 nptr = t->root;
515 while (42)
516 {
517 cmp = t->compare (nptr->key, new->key);
518 if (cmp == 0)
519 {
520 free_node (new);
521 return (-1);
522 }
523 else if (cmp < 0)
524 {
525 /* nptr < new */
526 if (nptr->right == NULL)
527 {
528 nptr->right = new;
529 new->parent = nptr;
530 rebalance (t, nptr);
531 break;
532 }
533 else
534 {
535 nptr = nptr->right;
536 }
537 }
538 else /* if (cmp > 0) */
539 {
540 /* nptr > new */
541 if (nptr->left == NULL)
542 {
543 nptr->left = new;
544 new->parent = nptr;
545 rebalance (t, nptr);
546 break;
547 }
548 else
549 {
550 nptr = nptr->left;
551 }
552 }
553 } /* while (42) */
555 verify_tree (t->root);
556 return (0);
557 } /* int avl_insert */
559 int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue)
560 {
561 avl_node_t *n;
562 int status;
564 assert (t != NULL);
566 n = search (t, key);
567 if (n == NULL)
568 return (-1);
570 if (rkey != NULL)
571 *rkey = n->key;
572 if (rvalue != NULL)
573 *rvalue = n->value;
575 status = _remove (t, n);
576 verify_tree (t->root);
577 return (status);
578 } /* void *avl_remove */
580 int avl_get (avl_tree_t *t, const void *key, void **value)
581 {
582 avl_node_t *n;
584 assert (value != NULL);
586 n = search (t, key);
587 if (n == NULL)
588 return (-1);
590 *value = n->value;
592 return (0);
593 }
595 int avl_pick (avl_tree_t *t, void **key, void **value)
596 {
597 avl_node_t *n;
598 avl_node_t *p;
600 if ((key == NULL) || (value == NULL))
601 return (-1);
602 if (t->root == NULL)
603 return (-1);
605 n = t->root;
606 while ((n->left != NULL) || (n->right != NULL))
607 {
608 int height_left = (n->left == NULL) ? 0 : n->left->height;
609 int height_right = (n->right == NULL) ? 0 : n->right->height;
611 if (height_left > height_right)
612 n = n->left;
613 else
614 n = n->right;
615 }
617 p = n->parent;
618 if (p == NULL)
619 t->root = NULL;
620 else if (p->left == n)
621 p->left = NULL;
622 else
623 p->right = NULL;
625 *key = n->key;
626 *value = n->value;
628 free_node (n);
629 rebalance (t, p);
631 return (0);
632 } /* int avl_pick */
634 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
635 {
636 avl_iterator_t *iter;
638 if (t == NULL)
639 return (NULL);
641 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
642 if (iter == NULL)
643 return (NULL);
644 memset (iter, '\0', sizeof (avl_iterator_t));
645 iter->tree = t;
647 return (iter);
648 } /* avl_iterator_t *avl_get_iterator */
650 int avl_iterator_next (avl_iterator_t *iter, void **key, void **value)
651 {
652 avl_node_t *n;
654 if ((iter == NULL) || (key == NULL) || (value == NULL))
655 return (-1);
657 if (iter->node == NULL)
658 {
659 for (n = iter->tree->root; n != NULL; n = n->left)
660 if (n->left == NULL)
661 break;
662 iter->node = n;
663 }
664 else
665 {
666 n = avl_node_next (iter->tree, iter->node);
667 }
669 if (n == NULL)
670 return (-1);
672 iter->node = n;
673 *key = n->key;
674 *value = n->value;
676 return (0);
677 } /* int avl_iterator_next */
679 int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value)
680 {
681 avl_node_t *n;
683 if ((iter == NULL) || (key == NULL) || (value == NULL))
684 return (-1);
686 if (iter->node == NULL)
687 {
688 for (n = iter->tree->root; n != NULL; n = n->left)
689 if (n->right == NULL)
690 break;
691 iter->node = n;
692 }
693 else
694 {
695 n = avl_node_prev (iter->tree, iter->node);
696 }
698 if (n == NULL)
699 return (-1);
701 iter->node = n;
702 *key = n->key;
703 *value = n->value;
705 return (0);
706 } /* int avl_iterator_prev */
708 void avl_iterator_destroy (avl_iterator_t *iter)
709 {
710 free (iter);
711 }