2 avl.c -- AVL tree management
4 Copyright (C) 1998 Michael H. Buselli
5 2000-2004 Ivo Timmermans <ivo@tinc-vpn.org>,
6 2000-2004 Guus Sliepen <guus@tinc-vpn.org>
7 2000-2004 Wessel Dankers <wsl@tinc-vpn.org>
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
25 Modified 2000-11-28 by Wessel Dankers <wsl@tinc-vpn.org> to use counts
26 instead of depths, to add the ->next and ->prev and to generally obfuscate
27 the code. Mail me if you found a bug.
29 Cleaned up and incorporated some of the ideas from the red-black tree
30 library for inclusion into tinc (http://www.tinc-vpn.org/) by
31 Guus Sliepen <guus@tinc-vpn.org>.
38 #include "support/avl.h"
39 #include "support/xalloc.h"
42 #define AVL_NODE_COUNT(n) ((n) ? (n)->count : 0)
43 #define AVL_L_COUNT(n) (AVL_NODE_COUNT((n)->left))
44 #define AVL_R_COUNT(n) (AVL_NODE_COUNT((n)->right))
45 #define AVL_CALC_COUNT(n) (AVL_L_COUNT(n) + AVL_R_COUNT(n) + 1)
49 #define AVL_NODE_DEPTH(n) ((n) ? (n)->depth : 0)
50 #define L_AVL_DEPTH(n) (AVL_NODE_DEPTH((n)->left))
51 #define R_AVL_DEPTH(n) (AVL_NODE_DEPTH((n)->right))
52 #define AVL_CALC_DEPTH(n) ((L_AVL_DEPTH(n)>R_AVL_DEPTH(n)?L_AVL_DEPTH(n):R_AVL_DEPTH(n)) + 1)
56 static int lg(unsigned int u) __attribute__ ((__const__));
58 static int lg(unsigned int u) {
91 /* Internal helper functions */
93 static int avl_check_balance(const avl_node_t *node) {
97 d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node);
99 return d < -1 ? -1 : d > 1 ? 1 : 0;
102 * d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node));
103 * d = d<-1?-1:d>1?1:0;
107 pl = lg(AVL_L_COUNT(node));
108 r = AVL_R_COUNT(node);
113 if(pl < 2 || r >> pl - 2)
120 static void avl_rebalance(avl_tree_t *tree, avl_node_t *node) {
124 avl_node_t **superparent;
129 parent = node->parent;
133 parent->left ? &parent->left : &parent->right : &tree->root;
135 switch (avl_check_balance(node)) {
139 if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
141 if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
143 node->left = child->right;
145 node->left->parent = node;
148 node->parent = child;
149 *superparent = child;
150 child->parent = parent;
152 node->count = AVL_CALC_COUNT(node);
153 child->count = AVL_CALC_COUNT(child);
156 node->depth = AVL_CALC_DEPTH(node);
157 child->depth = AVL_CALC_DEPTH(child);
160 gchild = child->right;
161 node->left = gchild->right;
164 node->left->parent = node;
165 child->right = gchild->left;
168 child->right->parent = child;
169 gchild->right = node;
172 gchild->right->parent = gchild;
173 gchild->left = child;
176 gchild->left->parent = gchild;
177 *superparent = gchild;
179 gchild->parent = parent;
181 node->count = AVL_CALC_COUNT(node);
182 child->count = AVL_CALC_COUNT(child);
183 gchild->count = AVL_CALC_COUNT(gchild);
186 node->depth = AVL_CALC_DEPTH(node);
187 child->depth = AVL_CALC_DEPTH(child);
188 gchild->depth = AVL_CALC_DEPTH(gchild);
196 if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
198 if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
200 node->right = child->left;
202 node->right->parent = node;
204 node->parent = child;
205 *superparent = child;
206 child->parent = parent;
208 node->count = AVL_CALC_COUNT(node);
209 child->count = AVL_CALC_COUNT(child);
212 node->depth = AVL_CALC_DEPTH(node);
213 child->depth = AVL_CALC_DEPTH(child);
216 gchild = child->left;
217 node->right = gchild->left;
220 node->right->parent = node;
221 child->left = gchild->right;
224 child->left->parent = child;
228 gchild->left->parent = gchild;
229 gchild->right = child;
232 gchild->right->parent = gchild;
234 *superparent = gchild;
235 gchild->parent = parent;
237 node->count = AVL_CALC_COUNT(node);
238 child->count = AVL_CALC_COUNT(child);
239 gchild->count = AVL_CALC_COUNT(gchild);
242 node->depth = AVL_CALC_DEPTH(node);
243 child->depth = AVL_CALC_DEPTH(child);
244 gchild->depth = AVL_CALC_DEPTH(gchild);
251 node->count = AVL_CALC_COUNT(node);
254 node->depth = AVL_CALC_DEPTH(node);
261 static int avl_compare(const void *a, const void *b) {
265 /* (De)constructors */
267 avl_tree_t *avl_tree_new(avl_compare_t compare, avl_action_t free) {
271 tree->compare = compare ?: avl_compare;
277 void avl_tree_free(avl_tree_t *tree) {
281 avl_node_t *avl_node_new(void) {
284 return clear(new(node));
287 void avl_node_free(avl_tree_t *tree, avl_node_t *node) {
288 if(node->data && tree->free)
289 tree->free(node->data);
296 void *avl_get(const avl_tree_t *tree, const void *data) {
299 node = avl_get_node(tree, data);
301 return node ? node->data : NULL;
304 void *avl_get_closest(const avl_tree_t *tree, const void *data, int *result) {
307 node = avl_get_closest_node(tree, data, result);
309 return node ? node->data : NULL;
312 void *avl_get_closest_smaller(const avl_tree_t *tree, const void *data) {
315 node = avl_get_closest_smaller_node(tree, data);
317 return node ? node->data : NULL;
320 void *avl_get_closest_greater(const avl_tree_t *tree, const void *data) {
323 node = avl_get_closest_greater_node(tree, data);
325 return node ? node->data : NULL;
328 avl_node_t *avl_get_node(const avl_tree_t *tree, const void *data) {
332 node = avl_get_closest_node(tree, data, &result);
334 return result ? NULL : node;
337 avl_node_t *avl_get_closest_node(const avl_tree_t *tree, const void *data, int *result) {
350 c = tree->compare(data, node->data);
378 avl_node_t *avl_get_closest_smaller_node(const avl_tree_t *tree, const void *data) {
382 node = avl_get_closest_node(tree, data, &result);
390 avl_node_t *avl_get_closest_greater_node(const avl_tree_t *tree, const void *data) {
394 node = avl_get_closest_node(tree, data, &result);
402 /* Insertion and deletion */
404 avl_node_t *avl_add(avl_tree_t *tree, void *data) {
405 avl_node_t *node, *result;
407 node = avl_node_new();
410 result = avl_add_node(tree, node);
418 avl_node_t *avl_add_node(avl_tree_t *tree, avl_node_t *node) {
423 avl_add_top(tree, node);
425 closest = avl_get_closest_node(tree, node->data, &result);
429 avl_add_before(tree, closest, node);
433 avl_add_after(tree, closest, node);
451 void avl_add_top(avl_tree_t *tree, avl_node_t *node) {
452 node->prev = node->next = node->parent = NULL;
453 tree->head = tree->tail = tree->root = node;
456 void avl_add_before(avl_tree_t *tree, avl_node_t *before, avl_node_t *node) {
459 avl_add_after(tree, tree->tail, node);
461 avl_add_top(tree, node);
466 node->parent = before;
467 node->prev = before->prev;
470 avl_add_after(tree, before->prev, node);
475 before->prev->next = node;
482 avl_rebalance(tree, before);
485 void avl_add_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) {
488 avl_add_before(tree, tree->head, node);
490 avl_add_top(tree, node);
495 avl_add_before(tree, after->next, node);
500 node->parent = after;
501 node->next = after->next;
504 after->next->prev = node;
511 avl_rebalance(tree, after);
514 avl_node_t *avl_unlink(avl_tree_t *tree, const void *data) {
517 node = avl_get_node(tree, data);
520 avl_unlink_node(tree, node);
525 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) {
527 avl_node_t **superparent;
528 avl_node_t *subst, *left, *right;
532 node->prev->next = node->next;
534 tree->head = node->next;
536 node->next->prev = node->prev;
538 tree->tail = node->prev;
540 parent = node->parent;
544 parent->left ? &parent->left : &parent->right : &tree->root;
549 *superparent = right;
552 right->parent = parent;
557 left->parent = parent;
565 balnode = subst->parent;
566 balnode->right = subst->left;
569 balnode->right->parent = balnode;
572 left->parent = subst;
575 subst->right = right;
576 subst->parent = parent;
577 right->parent = subst;
578 *superparent = subst;
581 avl_rebalance(tree, balnode);
583 node->next = node->prev = node->parent = node->left = node->right = NULL;
593 void avl_del_node(avl_tree_t *tree, avl_node_t *node) {
594 avl_unlink_node(tree, node);
595 avl_node_free(tree, node);
598 bool avl_del(avl_tree_t *tree, void *data) {
601 node = avl_get_node(tree, data);
604 avl_del_node(tree, node);
609 /* Fast tree cleanup */
611 void avl_tree_del(avl_tree_t *tree) {
614 avl_foreach_node(tree, node, avl_node_free(tree, node));
622 avl_count_t avl_count(const avl_tree_t *tree) {
623 return AVL_NODE_COUNT(tree->root);
626 void *avl_get_indexed(const avl_tree_t *tree, avl_count_t index) {
629 node = avl_get_indexed_node(tree, index);
631 return node ? node->data : NULL;
634 avl_node_t *avl_get_indexed_node(const avl_tree_t *tree, avl_count_t index) {
641 c = AVL_L_COUNT(node);
645 } else if(index > c) {
656 avl_count_t avl_index(const avl_node_t *node) {
660 index = AVL_L_COUNT(node);
662 while((next = node->parent)) {
663 if(node == next->right)
664 index += AVL_L_COUNT(next) + 1;
672 avl_depth_t avl_depth(const avl_tree_t *tree) {
673 return AVL_NODE_DEPTH(tree->root);