f445e21e4b36fbe97f96409346980a0a3307e755
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 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
264 {
265 avl_iterator_t *iter;
267 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
268 if (iter == NULL)
269 return (NULL);
271 iter->tree = t;
272 iter->node = n;
274 return (iter);
275 }
277 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
278 {
279 avl_node_t *r; /* return node */
281 if (n == NULL)
282 {
283 return (NULL);
284 }
285 else if (n->right == NULL)
286 {
288 r = n->parent;
289 while (r != NULL)
290 {
291 /* stop if a bigger node is found */
292 if (t->compare (n, r) < 0) /* n < r */
293 break;
294 r = r->parent;
295 }
296 }
297 else
298 {
299 r = n->right;
300 while (r->left != NULL)
301 r = r->left;
302 }
304 return (r);
305 }
307 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
308 {
309 avl_node_t *r; /* return node */
311 if (n == NULL)
312 {
313 return (NULL);
314 }
315 else if (n->left == NULL)
316 {
318 r = n->parent;
319 while (r != NULL)
320 {
321 /* stop if a smaller node is found */
322 if (t->compare (n, r) > 0) /* n > r */
323 break;
324 r = r->parent;
325 }
326 }
327 else
328 {
329 r = n->left;
330 while (r->right != NULL)
331 r = r->right;
332 }
334 return (r);
335 }
337 static int _remove (avl_tree_t *t, avl_node_t *n)
338 {
339 assert ((t != NULL) && (n != NULL));
341 if ((n->left != NULL) && (n->right != NULL))
342 {
343 avl_node_t *r; /* replacement node */
344 if (BALANCE (n) > 0) /* left subtree is higher */
345 {
346 assert (n->left != NULL);
347 r = avl_node_prev (t, n);
349 }
350 else /* right subtree is higher */
351 {
352 assert (n->right != NULL);
353 r = avl_node_next (t, n);
354 }
356 assert ((r->left == NULL) || (r->right == NULL));
358 /* copy content */
359 n->key = r->key;
360 n->value = r->value;
362 n = r;
363 }
365 assert ((n->left == NULL) || (n->right == NULL));
367 if ((n->left == NULL) && (n->right == NULL))
368 {
369 /* Deleting a leave is easy */
370 if (n->parent == NULL)
371 {
372 assert (t->root == n);
373 t->root = NULL;
374 }
375 else
376 {
377 assert ((n->parent->left == n)
378 || (n->parent->right == n));
379 if (n->parent->left == n)
380 n->parent->left = NULL;
381 else
382 n->parent->right = NULL;
384 rebalance (t, n->parent);
385 }
387 free_node (n);
388 }
389 else if (n->left == NULL)
390 {
391 assert (BALANCE (n) == -1);
392 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
393 if (n->parent == NULL)
394 {
395 assert (t->root == n);
396 t->root = n->right;
397 }
398 else if (n->parent->left == n)
399 {
400 n->parent->left = n->right;
401 }
402 else
403 {
404 n->parent->right = n->right;
405 }
406 n->right->parent = n->parent;
408 if (n->parent != NULL)
409 rebalance (t, n->parent);
411 n->right = NULL;
412 free_node (n);
413 }
414 else if (n->right == 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->left;
422 }
423 else if (n->parent->left == n)
424 {
425 n->parent->left = n->left;
426 }
427 else
428 {
429 n->parent->right = n->left;
430 }
431 n->left->parent = n->parent;
433 if (n->parent != NULL)
434 rebalance (t, n->parent);
436 n->left = NULL;
437 free_node (n);
438 }
439 else
440 {
441 assert (0);
442 }
444 return (0);
445 } /* void *_remove */
447 /*
448 * public functions
449 */
450 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
451 {
452 avl_tree_t *t;
454 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
455 return (NULL);
457 t->root = NULL;
458 t->compare = compare;
460 return (t);
461 }
463 void avl_destroy (avl_tree_t *t)
464 {
465 free_node (t->root);
466 free (t);
467 }
469 int avl_insert (avl_tree_t *t, void *key, void *value)
470 {
471 avl_node_t *new;
472 avl_node_t *nptr;
473 int cmp;
475 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
476 return (-1);
478 new->key = key;
479 new->value = value;
480 new->height = 1;
481 new->left = NULL;
482 new->right = NULL;
484 if (t->root == NULL)
485 {
486 new->parent = NULL;
487 t->root = new;
488 return (0);
489 }
491 nptr = t->root;
492 while (42)
493 {
494 cmp = t->compare (nptr->key, new->key);
495 if (cmp == 0)
496 {
497 free_node (new);
498 return (-1);
499 }
500 else if (cmp < 0)
501 {
502 /* nptr < new */
503 if (nptr->right == NULL)
504 {
505 nptr->right = new;
506 new->parent = nptr;
507 rebalance (t, nptr);
508 break;
509 }
510 else
511 {
512 nptr = nptr->right;
513 }
514 }
515 else /* if (cmp > 0) */
516 {
517 /* nptr > new */
518 if (nptr->left == NULL)
519 {
520 nptr->left = new;
521 new->parent = nptr;
522 rebalance (t, nptr);
523 break;
524 }
525 else
526 {
527 nptr = nptr->left;
528 }
529 }
530 } /* while (42) */
532 verify_tree (t->root);
533 return (0);
534 } /* int avl_insert */
536 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
537 {
538 avl_node_t *n;
539 int status;
541 assert (t != NULL);
543 n = search (t, key);
544 if (n == NULL)
545 return (-1);
547 if (rkey != NULL)
548 *rkey = n->key;
549 if (rvalue != NULL)
550 *rvalue = n->value;
552 status = _remove (t, n);
553 verify_tree (t->root);
554 return (status);
555 } /* void *avl_remove */
557 int avl_get (avl_tree_t *t, const void *key, void **value)
558 {
559 avl_node_t *n;
561 assert (value != NULL);
563 n = search (t, key);
564 if (n == NULL)
565 return (-1);
567 *value = n->value;
569 return (0);
570 }
572 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
573 {
574 avl_node_t *n;
576 if (t == NULL)
577 return (NULL);
579 for (n = t->root; n != NULL; n = n->left)
580 if (n->left == NULL)
581 break;
583 return (avl_create_iterator (t, n));
584 } /* avl_iterator_t *avl_get_iterator */
586 void *avl_iterator_next (avl_iterator_t *iter)
587 {
588 avl_node_t *n;
590 if ((iter == NULL) || (iter->node == NULL))
591 return (NULL);
593 n = avl_node_next (iter->tree, iter->node);
595 if (n == NULL)
596 return (NULL);
598 iter->node = n;
599 return (n);
601 }
603 void *avl_iterator_prev (avl_iterator_t *iter)
604 {
605 avl_node_t *n;
607 if ((iter == NULL) || (iter->node == NULL))
608 return (NULL);
610 n = avl_node_prev (iter->tree, iter->node);
612 if (n == NULL)
613 return (NULL);
615 iter->node = n;
616 return (n);
618 }
620 void avl_iterator_destroy (avl_iterator_t *iter)
621 {
622 free (iter);
623 }