da793b32d0fdf51d7e3bf98f041c9a99c3d6669f
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 p = x->parent;
150 y = x->left;
151 b = y->right;
153 x->left = b;
154 if (b != NULL)
155 b->parent = x;
157 x->parent = y;
158 y->right = x;
160 y->parent = p;
161 assert ((p == NULL) || (p->left == x) || (p->right == x));
162 if (p == NULL)
163 t->root = y;
164 else if (p->left == x)
165 p->left = y;
166 else
167 p->right = y;
169 x->height = calc_height (x);
170 y->height = calc_height (y);
172 return (y);
173 } /* void rotate_left */
175 /*
176 * (x) (y)
177 * / \ / \
178 * /\ (y) (x) /\
179 * /_a\ / \ ==> / \ / c\
180 * /\ /\ /\ /\/____\
181 * /_b\ / c\ /_a\ /_b\
182 * /____\
183 */
184 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
185 {
186 c_avl_node_t *p;
187 c_avl_node_t *y;
188 c_avl_node_t *b;
190 p = x->parent;
191 y = x->right;
192 b = y->left;
194 x->right = b;
195 if (b != NULL)
196 b->parent = x;
198 x->parent = y;
199 y->left = x;
201 y->parent = p;
202 assert ((p == NULL) || (p->left == x) || (p->right == x));
203 if (p == NULL)
204 t->root = y;
205 else if (p->left == x)
206 p->left = y;
207 else
208 p->right = y;
210 x->height = calc_height (x);
211 y->height = calc_height (y);
213 return (y);
214 } /* void rotate_left */
216 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
217 {
218 rotate_left (t, x->left);
219 return (rotate_right (t, x));
220 } /* void rotate_left_right */
222 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
223 {
224 rotate_right (t, x->right);
225 return (rotate_left (t, x));
226 } /* void rotate_right_left */
228 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
229 {
230 int b_top;
231 int b_bottom;
233 while (n != NULL)
234 {
235 b_top = BALANCE (n);
236 assert ((b_top >= -2) && (b_top <= 2));
238 if (b_top == -2)
239 {
240 assert (n->right != NULL);
241 b_bottom = BALANCE (n->right);
242 assert ((b_bottom >= -1) || (b_bottom <= 1));
243 if (b_bottom == 1)
244 n = rotate_right_left (t, n);
245 else
246 n = rotate_left (t, n);
247 }
248 else if (b_top == 2)
249 {
250 assert (n->left != NULL);
251 b_bottom = BALANCE (n->left);
252 assert ((b_bottom >= -1) || (b_bottom <= 1));
253 if (b_bottom == -1)
254 n = rotate_left_right (t, n);
255 else
256 n = rotate_right (t, n);
257 }
258 else
259 {
260 int height = calc_height (n);
261 if (height == n->height)
262 break;
263 n->height = height;
264 }
266 assert (n->height == calc_height (n));
268 n = n->parent;
269 } /* while (n != NULL) */
270 } /* void rebalance */
272 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
273 {
274 c_avl_node_t *r; /* return node */
276 if (n == NULL)
277 {
278 return (NULL);
279 }
281 /* If we can't descent any further, we have to backtrack to the first
282 * parent that's bigger than we, i. e. who's _left_ child we are. */
283 if (n->right == NULL)
284 {
285 r = n->parent;
286 while ((r != NULL) && (r->parent != NULL))
287 {
288 if (r->left == n)
289 break;
290 n = r;
291 r = n->parent;
292 }
294 /* n->right == NULL && r == NULL => t is root and has no next
295 * r->left != n => r->right = n => r->parent == NULL */
296 if ((r == NULL) || (r->left != n))
297 {
298 assert ((r == NULL) || (r->parent == NULL));
299 return (NULL);
300 }
301 else
302 {
303 assert (r->left == n);
304 return (r);
305 }
306 }
307 else
308 {
309 r = n->right;
310 while (r->left != NULL)
311 r = r->left;
312 }
314 return (r);
315 } /* c_avl_node_t *c_avl_node_next */
317 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
318 {
319 c_avl_node_t *r; /* return node */
321 if (n == NULL)
322 {
323 return (NULL);
324 }
326 /* If we can't descent any further, we have to backtrack to the first
327 * parent that's smaller than we, i. e. who's _right_ child we are. */
328 if (n->left == NULL)
329 {
330 r = n->parent;
331 while ((r != NULL) && (r->parent != NULL))
332 {
333 if (r->right == n)
334 break;
335 n = r;
336 r = n->parent;
337 }
339 /* n->left == NULL && r == NULL => t is root and has no next
340 * r->right != n => r->left = n => r->parent == NULL */
341 if ((r == NULL) || (r->right != n))
342 {
343 assert ((r == NULL) || (r->parent == NULL));
344 return (NULL);
345 }
346 else
347 {
348 assert (r->right == n);
349 return (r);
350 }
351 }
352 else
353 {
354 r = n->left;
355 while (r->right != NULL)
356 r = r->right;
357 }
359 return (r);
360 } /* c_avl_node_t *c_avl_node_prev */
362 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
363 {
364 assert ((t != NULL) && (n != NULL));
366 if ((n->left != NULL) && (n->right != NULL))
367 {
368 c_avl_node_t *r; /* replacement node */
369 if (BALANCE (n) > 0) /* left subtree is higher */
370 {
371 assert (n->left != NULL);
372 r = c_avl_node_prev (n);
374 }
375 else /* right subtree is higher */
376 {
377 assert (n->right != NULL);
378 r = c_avl_node_next (n);
379 }
381 assert ((r->left == NULL) || (r->right == NULL));
383 /* copy content */
384 n->key = r->key;
385 n->value = r->value;
387 n = r;
388 }
390 assert ((n->left == NULL) || (n->right == NULL));
392 if ((n->left == NULL) && (n->right == NULL))
393 {
394 /* Deleting a leave is easy */
395 if (n->parent == NULL)
396 {
397 assert (t->root == n);
398 t->root = NULL;
399 }
400 else
401 {
402 assert ((n->parent->left == n)
403 || (n->parent->right == n));
404 if (n->parent->left == n)
405 n->parent->left = NULL;
406 else
407 n->parent->right = NULL;
409 rebalance (t, n->parent);
410 }
412 free_node (n);
413 }
414 else if (n->left == NULL)
415 {
416 assert (BALANCE (n) == -1);
417 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
418 if (n->parent == NULL)
419 {
420 assert (t->root == n);
421 t->root = n->right;
422 }
423 else if (n->parent->left == n)
424 {
425 n->parent->left = n->right;
426 }
427 else
428 {
429 n->parent->right = n->right;
430 }
431 n->right->parent = n->parent;
433 if (n->parent != NULL)
434 rebalance (t, n->parent);
436 n->right = NULL;
437 free_node (n);
438 }
439 else if (n->right == NULL)
440 {
441 assert (BALANCE (n) == 1);
442 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
443 if (n->parent == NULL)
444 {
445 assert (t->root == n);
446 t->root = n->left;
447 }
448 else if (n->parent->left == n)
449 {
450 n->parent->left = n->left;
451 }
452 else
453 {
454 n->parent->right = n->left;
455 }
456 n->left->parent = n->parent;
458 if (n->parent != NULL)
459 rebalance (t, n->parent);
461 n->left = NULL;
462 free_node (n);
463 }
464 else
465 {
466 assert (0);
467 }
469 return (0);
470 } /* void *_remove */
472 /*
473 * public functions
474 */
475 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
476 {
477 c_avl_tree_t *t;
479 if (compare == NULL)
480 return (NULL);
482 if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
483 return (NULL);
485 t->root = NULL;
486 t->compare = compare;
487 t->size = 0;
489 return (t);
490 }
492 void c_avl_destroy (c_avl_tree_t *t)
493 {
494 if (t == NULL)
495 return;
496 free_node (t->root);
497 free (t);
498 }
500 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
501 {
502 c_avl_node_t *new;
503 c_avl_node_t *nptr;
504 int cmp;
506 if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
507 return (-1);
509 new->key = key;
510 new->value = value;
511 new->height = 1;
512 new->left = NULL;
513 new->right = NULL;
515 if (t->root == NULL)
516 {
517 new->parent = NULL;
518 t->root = new;
519 t->size = 1;
520 return (0);
521 }
523 nptr = t->root;
524 while (42)
525 {
526 cmp = t->compare (nptr->key, new->key);
527 if (cmp == 0)
528 {
529 free_node (new);
530 return (1);
531 }
532 else if (cmp < 0)
533 {
534 /* nptr < new */
535 if (nptr->right == NULL)
536 {
537 nptr->right = new;
538 new->parent = nptr;
539 rebalance (t, nptr);
540 break;
541 }
542 else
543 {
544 nptr = nptr->right;
545 }
546 }
547 else /* if (cmp > 0) */
548 {
549 /* nptr > new */
550 if (nptr->left == NULL)
551 {
552 nptr->left = new;
553 new->parent = nptr;
554 rebalance (t, nptr);
555 break;
556 }
557 else
558 {
559 nptr = nptr->left;
560 }
561 }
562 } /* while (42) */
564 verify_tree (t->root);
565 ++t->size;
566 return (0);
567 } /* int c_avl_insert */
569 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
570 {
571 c_avl_node_t *n;
572 int status;
574 assert (t != NULL);
576 n = search (t, key);
577 if (n == NULL)
578 return (-1);
580 if (rkey != NULL)
581 *rkey = n->key;
582 if (rvalue != NULL)
583 *rvalue = n->value;
585 status = _remove (t, n);
586 verify_tree (t->root);
587 --t->size;
588 return (status);
589 } /* void *c_avl_remove */
591 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
592 {
593 c_avl_node_t *n;
595 assert (t != NULL);
597 n = search (t, key);
598 if (n == NULL)
599 return (-1);
601 if (value != NULL)
602 *value = n->value;
604 return (0);
605 }
607 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
608 {
609 c_avl_node_t *n;
610 c_avl_node_t *p;
612 if ((key == NULL) || (value == NULL))
613 return (-1);
614 if (t->root == NULL)
615 return (-1);
617 n = t->root;
618 while ((n->left != NULL) || (n->right != NULL))
619 {
620 if (n->left == NULL)
621 {
622 n = n->right;
623 continue;
624 }
625 else if (n->right == NULL)
626 {
627 n = n->left;
628 continue;
629 }
631 if (n->left->height > n->right->height)
632 n = n->left;
633 else
634 n = n->right;
635 }
637 p = n->parent;
638 if (p == NULL)
639 t->root = NULL;
640 else if (p->left == n)
641 p->left = NULL;
642 else
643 p->right = NULL;
645 *key = n->key;
646 *value = n->value;
648 free_node (n);
649 rebalance (t, p);
651 return (0);
652 } /* int c_avl_pick */
654 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
655 {
656 c_avl_iterator_t *iter;
658 if (t == NULL)
659 return (NULL);
661 iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
662 if (iter == NULL)
663 return (NULL);
664 memset (iter, '\0', sizeof (c_avl_iterator_t));
665 iter->tree = t;
667 return (iter);
668 } /* c_avl_iterator_t *c_avl_get_iterator */
670 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
671 {
672 c_avl_node_t *n;
674 if ((iter == NULL) || (key == NULL) || (value == NULL))
675 return (-1);
677 if (iter->node == NULL)
678 {
679 for (n = iter->tree->root; n != NULL; n = n->left)
680 if (n->left == NULL)
681 break;
682 iter->node = n;
683 }
684 else
685 {
686 n = c_avl_node_next (iter->node);
687 }
689 if (n == NULL)
690 return (-1);
692 iter->node = n;
693 *key = n->key;
694 *value = n->value;
696 return (0);
697 } /* int c_avl_iterator_next */
699 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
700 {
701 c_avl_node_t *n;
703 if ((iter == NULL) || (key == NULL) || (value == NULL))
704 return (-1);
706 if (iter->node == NULL)
707 {
708 for (n = iter->tree->root; n != NULL; n = n->left)
709 if (n->right == NULL)
710 break;
711 iter->node = n;
712 }
713 else
714 {
715 n = c_avl_node_prev (iter->node);
716 }
718 if (n == NULL)
719 return (-1);
721 iter->node = n;
722 *key = n->key;
723 *value = n->value;
725 return (0);
726 } /* int c_avl_iterator_prev */
728 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
729 {
730 free (iter);
731 }
733 int c_avl_size (c_avl_tree_t *t)
734 {
735 if (t == NULL)
736 return (0);
737 return (t->size);
738 }