Debian Codegraph @

src/utils/avltree/avltree.c

raw
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/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->right)
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 }