Address review comments:
[collectd.git] / src / daemon / utils_avltree.c
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  **/
26
27 #include <stdlib.h>
28 #include <assert.h>
29
30 #include "utils_avltree.h"
31
32 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
33                 - (((n)->right == NULL) ? 0 : (n)->right->height))
34
35 /*
36  * private data types
37  */
38 struct c_avl_node_s
39 {
40         void *key;
41         void *value;
42
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;
49
50 struct c_avl_tree_s
51 {
52         c_avl_node_t *root;
53         int (*compare) (const void *, const void *);
54         int size;
55 };
56
57 struct c_avl_iterator_s
58 {
59         c_avl_tree_t *tree;
60         c_avl_node_t *node;
61 };
62
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;
71
72         verify_tree (n->left);
73         verify_tree (n->right);
74
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
81
82 static void free_node (c_avl_node_t *n)
83 {
84         if (n == NULL)
85                 return;
86
87         if (n->left != NULL)
88                 free_node (n->left);
89         if (n->right != NULL)
90                 free_node (n->right);
91
92         free (n);
93 }
94
95 static int calc_height (c_avl_node_t *n)
96 {
97         int height_left;
98         int height_right;
99
100         if (n == NULL)
101                 return (0);
102
103         height_left  = (n->left == NULL)  ? 0 : n->left->height;
104         height_right = (n->right == NULL) ? 0 : n->right->height;
105
106         return (((height_left > height_right)
107                                 ? height_left
108                                 : height_right) + 1);
109 } /* int calc_height */
110
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;
115
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         }
127
128         return (NULL);
129 }
130
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;
144
145         assert (x != NULL);
146         assert (x->left != NULL);
147
148         p = x->parent;
149         y = x->left;
150         b = y->right;
151
152         x->left = b;
153         if (b != NULL)
154                 b->parent = x;
155
156         x->parent = y;
157         y->right = x;
158
159         y->parent = p;
160         assert ((p == NULL) || (p->left == x) || (p->right == x));
161         if (p == NULL)
162                 t->root = y;
163         else if (p->left == x)
164                 p->left = y;
165         else
166                 p->right = y;
167
168         x->height = calc_height (x);
169         y->height = calc_height (y);
170
171         return (y);
172 } /* void rotate_right */
173
174 /*
175  *    (x)                   (y)
176  *   /   \                 /   \
177  *  /\    (y)           (x)    /\
178  * /_a\  /   \   ==>   /   \  / c\
179  *      /\   /\       /\   /\/____\
180  *     /_b\ / c\     /_a\ /_b\
181  *         /____\
182  */
183 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
184 {
185         c_avl_node_t *p;
186         c_avl_node_t *y;
187         c_avl_node_t *b;
188
189         assert (x != NULL);
190         assert (x->right != NULL);
191
192         p = x->parent;
193         y = x->right;
194         b = y->left;
195
196         x->right = b;
197         if (b != NULL)
198                 b->parent = x;
199
200         x->parent = y;
201         y->left = x;
202
203         y->parent = p;
204         assert ((p == NULL) || (p->left == x) || (p->right == x));
205         if (p == NULL)
206                 t->root = y;
207         else if (p->left == x)
208                 p->left = y;
209         else
210                 p->right = y;
211
212         x->height = calc_height (x);
213         y->height = calc_height (y);
214
215         return (y);
216 } /* void rotate_left */
217
218 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
219 {
220         rotate_left (t, x->left);
221         return (rotate_right (t, x));
222 } /* void rotate_left_right */
223
224 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
225 {
226         rotate_right (t, x->right);
227         return (rotate_left (t, x));
228 } /* void rotate_right_left */
229
230 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
231 {
232         int b_top;
233         int b_bottom;
234
235         while (n != NULL)
236         {
237                 b_top = BALANCE (n);
238                 assert ((b_top >= -2) && (b_top <= 2));
239
240                 if (b_top == -2)
241                 {
242                         assert (n->right != NULL);
243                         b_bottom = BALANCE (n->right);
244                         assert ((b_bottom >= -1) && (b_bottom <= 1));
245                         if (b_bottom == 1)
246                                 n = rotate_right_left (t, n);
247                         else
248                                 n = rotate_left (t, n);
249                 }
250                 else if (b_top == 2)
251                 {
252                         assert (n->left != NULL);
253                         b_bottom = BALANCE (n->left);
254                         assert ((b_bottom >= -1) && (b_bottom <= 1));
255                         if (b_bottom == -1)
256                                 n = rotate_left_right (t, n);
257                         else
258                                 n = rotate_right (t, n);
259                 }
260                 else
261                 {
262                         int height = calc_height (n);
263                         if (height == n->height)
264                                 break;
265                         n->height = height;
266                 }
267
268                 assert (n->height == calc_height (n));
269
270                 n = n->parent;
271         } /* while (n != NULL) */
272 } /* void rebalance */
273
274 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
275 {
276         c_avl_node_t *r; /* return node */
277
278         if (n == NULL)
279         {
280                 return (NULL);
281         }
282
283         /* If we can't descent any further, we have to backtrack to the first
284          * parent that's bigger than we, i. e. who's _left_ child we are. */
285         if (n->right == NULL)
286         {
287                 r = n->parent;
288                 while ((r != NULL) && (r->parent != NULL))
289                 {
290                         if (r->left == n)
291                                 break;
292                         n = r;
293                         r = n->parent;
294                 }
295
296                 /* n->right == NULL && r == NULL => t is root and has no next
297                  * r->left != n => r->right = n => r->parent == NULL */
298                 if ((r == NULL) || (r->left != n))
299                 {
300                         assert ((r == NULL) || (r->parent == NULL));
301                         return (NULL);
302                 }
303                 else
304                 {
305                         assert (r->left == n);
306                         return (r);
307                 }
308         }
309         else
310         {
311                 r = n->right;
312                 while (r->left != NULL)
313                         r = r->left;
314         }
315
316         return (r);
317 } /* c_avl_node_t *c_avl_node_next */
318
319 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
320 {
321         c_avl_node_t *r; /* return node */
322
323         if (n == NULL)
324         {
325                 return (NULL);
326         }
327
328         /* If we can't descent any further, we have to backtrack to the first
329          * parent that's smaller than we, i. e. who's _right_ child we are. */
330         if (n->left == NULL)
331         {
332                 r = n->parent;
333                 while ((r != NULL) && (r->parent != NULL))
334                 {
335                         if (r->right == n)
336                                 break;
337                         n = r;
338                         r = n->parent;
339                 }
340
341                 /* n->left == NULL && r == NULL => t is root and has no next
342                  * r->right != n => r->left = n => r->parent == NULL */
343                 if ((r == NULL) || (r->right != n))
344                 {
345                         assert ((r == NULL) || (r->parent == NULL));
346                         return (NULL);
347                 }
348                 else
349                 {
350                         assert (r->right == n);
351                         return (r);
352                 }
353         }
354         else
355         {
356                 r = n->left;
357                 while (r->right != NULL)
358                         r = r->right;
359         }
360
361         return (r);
362 } /* c_avl_node_t *c_avl_node_prev */
363
364 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
365 {
366         assert ((t != NULL) && (n != NULL));
367
368         if ((n->left != NULL) && (n->right != NULL))
369         {
370                 c_avl_node_t *r; /* replacement node */
371                 if (BALANCE (n) > 0) /* left subtree is higher */
372                 {
373                         assert (n->left != NULL);
374                         r = c_avl_node_prev (n);
375                         
376                 }
377                 else /* right subtree is higher */
378                 {
379                         assert (n->right != NULL);
380                         r = c_avl_node_next (n);
381                 }
382
383                 assert ((r->left == NULL) || (r->right == NULL));
384
385                 /* copy content */
386                 n->key   = r->key;
387                 n->value = r->value;
388
389                 n = r;
390         }
391
392         assert ((n->left == NULL) || (n->right == NULL));
393
394         if ((n->left == NULL) && (n->right == NULL))
395         {
396                 /* Deleting a leave is easy */
397                 if (n->parent == NULL)
398                 {
399                         assert (t->root == n);
400                         t->root = NULL;
401                 }
402                 else
403                 {
404                         assert ((n->parent->left == n)
405                                         || (n->parent->right == n));
406                         if (n->parent->left == n)
407                                 n->parent->left = NULL;
408                         else
409                                 n->parent->right = NULL;
410
411                         rebalance (t, n->parent);
412                 }
413
414                 free_node (n);
415         }
416         else if (n->left == NULL)
417         {
418                 assert (BALANCE (n) == -1);
419                 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
420                 if (n->parent == NULL)
421                 {
422                         assert (t->root == n);
423                         t->root = n->right;
424                 }
425                 else if (n->parent->left == n)
426                 {
427                         n->parent->left = n->right;
428                 }
429                 else
430                 {
431                         n->parent->right = n->right;
432                 }
433                 n->right->parent = n->parent;
434
435                 if (n->parent != NULL)
436                         rebalance (t, n->parent);
437
438                 n->right = NULL;
439                 free_node (n);
440         }
441         else if (n->right == NULL)
442         {
443                 assert (BALANCE (n) == 1);
444                 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
445                 if (n->parent == NULL)
446                 {
447                         assert (t->root == n);
448                         t->root = n->left;
449                 }
450                 else if (n->parent->left == n)
451                 {
452                         n->parent->left = n->left;
453                 }
454                 else
455                 {
456                         n->parent->right = n->left;
457                 }
458                 n->left->parent = n->parent;
459
460                 if (n->parent != NULL)
461                         rebalance (t, n->parent);
462
463                 n->left = NULL;
464                 free_node (n);
465         }
466         else
467         {
468                 assert (0);
469         }
470
471         return (0);
472 } /* void *_remove */
473
474 /*
475  * public functions
476  */
477 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
478 {
479         c_avl_tree_t *t;
480
481         if (compare == NULL)
482                 return (NULL);
483
484         if ((t = malloc (sizeof (*t))) == NULL)
485                 return (NULL);
486
487         t->root = NULL;
488         t->compare = compare;
489         t->size = 0;
490
491         return (t);
492 }
493
494 void c_avl_destroy (c_avl_tree_t *t)
495 {
496         if (t == NULL)
497                 return;
498         free_node (t->root);
499         free (t);
500 }
501
502 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
503 {
504         c_avl_node_t *new;
505         c_avl_node_t *nptr;
506         int cmp;
507
508         if ((new = malloc (sizeof (*new))) == NULL)
509                 return (-1);
510
511         new->key = key;
512         new->value = value;
513         new->height = 1;
514         new->left = NULL;
515         new->right = NULL;
516
517         if (t->root == NULL)
518         {
519                 new->parent = NULL;
520                 t->root = new;
521                 t->size = 1;
522                 return (0);
523         }
524
525         nptr = t->root;
526         while (42)
527         {
528                 cmp = t->compare (nptr->key, new->key);
529                 if (cmp == 0)
530                 {
531                         free_node (new);
532                         return (1);
533                 }
534                 else if (cmp < 0)
535                 {
536                         /* nptr < new */
537                         if (nptr->right == NULL)
538                         {
539                                 nptr->right = new;
540                                 new->parent = nptr;
541                                 rebalance (t, nptr);
542                                 break;
543                         }
544                         else
545                         {
546                                 nptr = nptr->right;
547                         }
548                 }
549                 else /* if (cmp > 0) */
550                 {
551                         /* nptr > new */
552                         if (nptr->left == NULL)
553                         {
554                                 nptr->left = new;
555                                 new->parent = nptr;
556                                 rebalance (t, nptr);
557                                 break;
558                         }
559                         else
560                         {
561                                 nptr = nptr->left;
562                         }
563                 }
564         } /* while (42) */
565
566         verify_tree (t->root);
567         ++t->size;
568         return (0);
569 } /* int c_avl_insert */
570
571 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
572 {
573         c_avl_node_t *n;
574         int status;
575
576         assert (t != NULL);
577
578         n = search (t, key);
579         if (n == NULL)
580                 return (-1);
581
582         if (rkey != NULL)
583                 *rkey = n->key;
584         if (rvalue != NULL)
585                 *rvalue = n->value;
586
587         status = _remove (t, n);
588         verify_tree (t->root);
589         --t->size;
590         return (status);
591 } /* void *c_avl_remove */
592
593 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
594 {
595         c_avl_node_t *n;
596
597         assert (t != NULL);
598
599         n = search (t, key);
600         if (n == NULL)
601                 return (-1);
602
603         if (value != NULL)
604                 *value = n->value;
605
606         return (0);
607 }
608
609 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
610 {
611         c_avl_node_t *n;
612         c_avl_node_t *p;
613
614         if ((key == NULL) || (value == NULL))
615                 return (-1);
616         if (t->root == NULL)
617                 return (-1);
618
619         n = t->root;
620         while ((n->left != NULL) || (n->right != NULL))
621         {
622                 if (n->left == NULL)
623                 {
624                         n = n->right;
625                         continue;
626                 }
627                 else if (n->right == NULL)
628                 {
629                         n = n->left;
630                         continue;
631                 }
632
633                 if (n->left->height > n->right->height)
634                         n = n->left;
635                 else
636                         n = n->right;
637         }
638
639         p = n->parent;
640         if (p == NULL)
641                 t->root = NULL;
642         else if (p->left == n)
643                 p->left = NULL;
644         else
645                 p->right = NULL;
646
647         *key   = n->key;
648         *value = n->value;
649
650         free_node (n);
651         --t->size;
652         rebalance (t, p);
653
654         return (0);
655 } /* int c_avl_pick */
656
657 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
658 {
659         c_avl_iterator_t *iter;
660
661         if (t == NULL)
662                 return (NULL);
663
664         iter = calloc (1, sizeof (*iter));
665         if (iter == NULL)
666                 return (NULL);
667         iter->tree = t;
668
669         return (iter);
670 } /* c_avl_iterator_t *c_avl_get_iterator */
671
672 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
673 {
674         c_avl_node_t *n;
675
676         if ((iter == NULL) || (key == NULL) || (value == NULL))
677                 return (-1);
678
679         if (iter->node == NULL)
680         {
681                 for (n = iter->tree->root; n != NULL; n = n->left)
682                         if (n->left == NULL)
683                                 break;
684                 iter->node = n;
685         }
686         else
687         {
688                 n = c_avl_node_next (iter->node);
689         }
690
691         if (n == NULL)
692                 return (-1);
693
694         iter->node = n;
695         *key = n->key;
696         *value = n->value;
697
698         return (0);
699 } /* int c_avl_iterator_next */
700
701 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
702 {
703         c_avl_node_t *n;
704
705         if ((iter == NULL) || (key == NULL) || (value == NULL))
706                 return (-1);
707
708         if (iter->node == NULL)
709         {
710                 for (n = iter->tree->root; n != NULL; n = n->left)
711                         if (n->right == NULL)
712                                 break;
713                 iter->node = n;
714         }
715         else
716         {
717                 n = c_avl_node_prev (iter->node);
718         }
719
720         if (n == NULL)
721                 return (-1);
722
723         iter->node = n;
724         *key = n->key;
725         *value = n->value;
726
727         return (0);
728 } /* int c_avl_iterator_prev */
729
730 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
731 {
732         free (iter);
733 }
734
735 int c_avl_size (c_avl_tree_t *t)
736 {
737         if (t == NULL)
738                 return (0);
739         return (t->size);
740 }