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 <assert.h>
26 #include "utils_avltree.h"
28 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
29 - (((n)->right == NULL) ? 0 : (n)->right->height))
31 /*
32 * private data types
33 */
34 struct avl_node_s
35 {
36 void *key;
37 void *value;
39 int height;
40 struct avl_node_s *left;
41 struct avl_node_s *right;
42 struct avl_node_s *parent;
43 };
44 typedef struct avl_node_s avl_node_t;
46 struct avl_tree_s
47 {
48 avl_node_t *root;
49 int (*compare) (const void *, const void *);
50 };
52 struct avl_iterator_s
53 {
54 avl_tree_t *tree;
55 avl_node_t *node;
56 };
58 /*
59 * private functions
60 */
61 #if 0
62 static void verify_tree (avl_node_t *n)
63 {
64 if (n == NULL)
65 return;
67 verify_tree (n->left);
68 verify_tree (n->right);
70 assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
71 assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
72 } /* void verify_tree */
73 #else
74 # define verify_tree(n) /**/
75 #endif
77 static void free_node (avl_node_t *n)
78 {
79 if (n == NULL)
80 return;
82 if (n->left != NULL)
83 free_node (n->left);
84 if (n->right != NULL)
85 free_node (n->right);
87 free (n);
88 }
90 static int calc_height (avl_node_t *n)
91 {
92 int height_left;
93 int height_right;
95 if (n == NULL)
96 return (0);
98 height_left = (n->left == NULL) ? 0 : n->left->height;
99 height_right = (n->right == NULL) ? 0 : n->right->height;
101 return (((height_left > height_right)
102 ? height_left
103 : height_right) + 1);
104 } /* int calc_height */
106 static avl_node_t *search (avl_tree_t *t, const void *key)
107 {
108 avl_node_t *n;
109 int cmp;
111 n = t->root;
112 while (n != NULL)
113 {
114 cmp = t->compare (key, n->key);
115 if (cmp == 0)
116 return (n);
117 else if (cmp < 0)
118 n = n->left;
119 else
120 n = n->right;
121 }
123 return (NULL);
124 }
126 /* (x) (y)
127 * / \ / \
128 * (y) /\ /\ (x)
129 * / \ /_c\ ==> / a\ / \
130 * /\ /\ /____\/\ /\
131 * / a\ /_b\ /_b\ /_c\
132 * /____\
133 */
134 static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
135 {
136 avl_node_t *p;
137 avl_node_t *y;
138 avl_node_t *b;
140 p = x->parent;
141 y = x->left;
142 b = y->right;
144 x->left = b;
145 if (b != NULL)
146 b->parent = x;
148 x->parent = y;
149 y->right = x;
151 y->parent = p;
152 assert ((p == NULL) || (p->left == x) || (p->right == x));
153 if (p == NULL)
154 t->root = y;
155 else if (p->left == x)
156 p->left = y;
157 else
158 p->right = y;
160 x->height = calc_height (x);
161 y->height = calc_height (y);
163 return (y);
164 } /* void rotate_left */
166 /*
167 * (x) (y)
168 * / \ / \
169 * /\ (y) (x) /\
170 * /_a\ / \ ==> / \ / c\
171 * /\ /\ /\ /\/____\
172 * /_b\ / c\ /_a\ /_b\
173 * /____\
174 */
175 static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
176 {
177 avl_node_t *p;
178 avl_node_t *y;
179 avl_node_t *b;
181 p = x->parent;
182 y = x->right;
183 b = y->left;
185 x->right = b;
186 if (b != NULL)
187 b->parent = x;
189 x->parent = y;
190 y->left = x;
192 y->parent = p;
193 assert ((p == NULL) || (p->left == x) || (p->right == x));
194 if (p == NULL)
195 t->root = y;
196 else if (p->left == x)
197 p->left = y;
198 else
199 p->right = y;
201 x->height = calc_height (x);
202 y->height = calc_height (y);
204 return (y);
205 } /* void rotate_left */
207 static avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_t *x)
208 {
209 rotate_left (t, x->left);
210 return (rotate_right (t, x));
211 } /* void rotate_left_right */
213 static avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_t *x)
214 {
215 rotate_right (t, x->right);
216 return (rotate_left (t, x));
217 } /* void rotate_right_left */
219 static void rebalance (avl_tree_t *t, avl_node_t *n)
220 {
221 int b_top;
222 int b_bottom;
224 while (n != NULL)
225 {
226 b_top = BALANCE (n);
227 assert ((b_top >= -2) && (b_top <= 2));
229 if (b_top == -2)
230 {
231 assert (n->right != NULL);
232 b_bottom = BALANCE (n->right);
233 assert ((b_bottom >= -1) || (b_bottom <= 1));
234 if (b_bottom == 1)
235 n = rotate_right_left (t, n);
236 else
237 n = rotate_left (t, n);
238 }
239 else if (b_top == 2)
240 {
241 assert (n->left != NULL);
242 b_bottom = BALANCE (n->left);
243 assert ((b_bottom >= -1) || (b_bottom <= 1));
244 if (b_bottom == -1)
245 n = rotate_left_right (t, n);
246 else
247 n = rotate_right (t, n);
248 }
249 else
250 {
251 int height = calc_height (n);
252 if (height == n->height)
253 break;
254 n->height = height;
255 }
257 assert (n->height == calc_height (n));
259 n = n->parent;
260 } /* while (n != NULL) */
261 } /* void rebalance */
263 #if 0
264 /* This code disabled until a need arises. */
265 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
266 {
267 avl_iterator_t *iter;
269 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
270 if (iter == NULL)
271 return (NULL);
273 iter->tree = t;
274 iter->node = n;
276 return (iter);
277 }
278 #endif
280 static void *avl_node_next (avl_tree_t *t, avl_node_t *n)
281 {
282 avl_node_t *r; /* return node */
284 if (n == NULL)
285 {
286 return (NULL);
287 }
288 else if (n->right == NULL)
289 {
291 r = n->parent;
292 while (r != NULL)
293 {
294 /* stop if a bigger node is found */
295 if (t->compare (n, r) < 0) /* n < r */
296 break;
297 r = r->parent;
298 }
299 }
300 else
301 {
302 r = n->right;
303 while (r->left != NULL)
304 r = r->left;
305 }
307 return (r);
308 }
310 static void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
311 {
312 avl_node_t *r; /* return node */
314 if (n == NULL)
315 {
316 return (NULL);
317 }
318 else if (n->left == NULL)
319 {
321 r = n->parent;
322 while (r != NULL)
323 {
324 /* stop if a smaller node is found */
325 if (t->compare (n, r) > 0) /* n > r */
326 break;
327 r = r->parent;
328 }
329 }
330 else
331 {
332 r = n->left;
333 while (r->right != NULL)
334 r = r->right;
335 }
337 return (r);
338 } /* void *avl_node_prev */
340 static int _remove (avl_tree_t *t, avl_node_t *n)
341 {
342 assert ((t != NULL) && (n != NULL));
344 if ((n->left != NULL) && (n->right != NULL))
345 {
346 avl_node_t *r; /* replacement node */
347 if (BALANCE (n) > 0) /* left subtree is higher */
348 {
349 assert (n->left != NULL);
350 r = avl_node_prev (t, n);
352 }
353 else /* right subtree is higher */
354 {
355 assert (n->right != NULL);
356 r = avl_node_next (t, n);
357 }
359 assert ((r->left == NULL) || (r->right == NULL));
361 /* copy content */
362 n->key = r->key;
363 n->value = r->value;
365 n = r;
366 }
368 assert ((n->left == NULL) || (n->right == NULL));
370 if ((n->left == NULL) && (n->right == NULL))
371 {
372 /* Deleting a leave is easy */
373 if (n->parent == NULL)
374 {
375 assert (t->root == n);
376 t->root = NULL;
377 }
378 else
379 {
380 assert ((n->parent->left == n)
381 || (n->parent->right == n));
382 if (n->parent->left == n)
383 n->parent->left = NULL;
384 else
385 n->parent->right = NULL;
387 rebalance (t, n->parent);
388 }
390 free_node (n);
391 }
392 else if (n->left == NULL)
393 {
394 assert (BALANCE (n) == -1);
395 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
396 if (n->parent == NULL)
397 {
398 assert (t->root == n);
399 t->root = n->right;
400 }
401 else if (n->parent->left == n)
402 {
403 n->parent->left = n->right;
404 }
405 else
406 {
407 n->parent->right = n->right;
408 }
409 n->right->parent = n->parent;
411 if (n->parent != NULL)
412 rebalance (t, n->parent);
414 n->right = NULL;
415 free_node (n);
416 }
417 else if (n->right == NULL)
418 {
419 assert (BALANCE (n) == 1);
420 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
421 if (n->parent == NULL)
422 {
423 assert (t->root == n);
424 t->root = n->left;
425 }
426 else if (n->parent->left == n)
427 {
428 n->parent->left = n->left;
429 }
430 else
431 {
432 n->parent->right = n->left;
433 }
434 n->left->parent = n->parent;
436 if (n->parent != NULL)
437 rebalance (t, n->parent);
439 n->left = NULL;
440 free_node (n);
441 }
442 else
443 {
444 assert (0);
445 }
447 return (0);
448 } /* void *_remove */
450 /*
451 * public functions
452 */
453 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
454 {
455 avl_tree_t *t;
457 if (compare == NULL)
458 return (NULL);
460 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
461 return (NULL);
463 t->root = NULL;
464 t->compare = compare;
466 return (t);
467 }
469 void avl_destroy (avl_tree_t *t)
470 {
471 free_node (t->root);
472 free (t);
473 }
475 int avl_insert (avl_tree_t *t, void *key, void *value)
476 {
477 avl_node_t *new;
478 avl_node_t *nptr;
479 int cmp;
481 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
482 return (-1);
484 new->key = key;
485 new->value = value;
486 new->height = 1;
487 new->left = NULL;
488 new->right = NULL;
490 if (t->root == NULL)
491 {
492 new->parent = NULL;
493 t->root = new;
494 return (0);
495 }
497 nptr = t->root;
498 while (42)
499 {
500 cmp = t->compare (nptr->key, new->key);
501 if (cmp == 0)
502 {
503 free_node (new);
504 return (-1);
505 }
506 else if (cmp < 0)
507 {
508 /* nptr < new */
509 if (nptr->right == NULL)
510 {
511 nptr->right = new;
512 new->parent = nptr;
513 rebalance (t, nptr);
514 break;
515 }
516 else
517 {
518 nptr = nptr->right;
519 }
520 }
521 else /* if (cmp > 0) */
522 {
523 /* nptr > new */
524 if (nptr->left == NULL)
525 {
526 nptr->left = new;
527 new->parent = nptr;
528 rebalance (t, nptr);
529 break;
530 }
531 else
532 {
533 nptr = nptr->left;
534 }
535 }
536 } /* while (42) */
538 verify_tree (t->root);
539 return (0);
540 } /* int avl_insert */
542 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
543 {
544 avl_node_t *n;
545 int status;
547 assert (t != NULL);
549 n = search (t, key);
550 if (n == NULL)
551 return (-1);
553 if (rkey != NULL)
554 *rkey = n->key;
555 if (rvalue != NULL)
556 *rvalue = n->value;
558 status = _remove (t, n);
559 verify_tree (t->root);
560 return (status);
561 } /* void *avl_remove */
563 int avl_get (avl_tree_t *t, const void *key, void **value)
564 {
565 avl_node_t *n;
567 assert (value != NULL);
569 n = search (t, key);
570 if (n == NULL)
571 return (-1);
573 *value = n->value;
575 return (0);
576 }
578 int avl_pick (avl_tree_t *t, void **key, void **value)
579 {
580 avl_node_t *n;
581 avl_node_t *p;
583 if ((key == NULL) || (value == NULL))
584 return (-1);
585 if (t->root == NULL)
586 return (-1);
588 n = t->root;
589 while ((n->left != NULL) || (n->right != NULL))
590 {
591 int height_left = (n->left == NULL) ? 0 : n->left->height;
592 int height_right = (n->right == NULL) ? 0 : n->right->height;
594 if (height_left > height_right)
595 n = n->left;
596 else
597 n = n->right;
598 }
600 p = n->parent;
601 if (p == NULL)
602 t->root = NULL;
603 else if (p->left == n)
604 p->left = NULL;
605 else
606 p->right = NULL;
608 *key = n->key;
609 *value = n->value;
611 free_node (n);
612 rebalance (t, p);
614 return (0);
615 } /* int avl_pick */
617 #if 0
618 /* This code disabled until a need arises. */
619 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
620 {
621 avl_node_t *n;
623 if (t == NULL)
624 return (NULL);
626 for (n = t->root; n != NULL; n = n->left)
627 if (n->left == NULL)
628 break;
630 return (avl_create_iterator (t, n));
631 } /* avl_iterator_t *avl_get_iterator */
633 void *avl_iterator_next (avl_iterator_t *iter)
634 {
635 avl_node_t *n;
637 if ((iter == NULL) || (iter->node == NULL))
638 return (NULL);
640 n = avl_node_next (iter->tree, iter->node);
642 if (n == NULL)
643 return (NULL);
645 iter->node = n;
646 return (n);
648 }
650 void *avl_iterator_prev (avl_iterator_t *iter)
651 {
652 avl_node_t *n;
654 if ((iter == NULL) || (iter->node == NULL))
655 return (NULL);
657 n = avl_node_prev (iter->tree, iter->node);
659 if (n == NULL)
660 return (NULL);
662 iter->node = n;
663 return (n);
665 }
667 void avl_iterator_destroy (avl_iterator_t *iter)
668 {
669 free (iter);
670 }
671 #endif /* 0 */