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