2 avl_tree.c -- avl_ tree and linked list convenience
3 Copyright (C) 1998 Michael H. Buselli
4 2000-2003 Ivo Timmermans <ivo@o2w.nl>,
5 2000-2003 Guus Sliepen <guus@sliepen.eu.org>
6 2000-2003 Wessel Dankers <wsl@nl.linux.org>
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
24 Modified 2000-11-28 by Wessel Dankers <wsl@nl.linux.org> to use counts
25 instead of depths, to add the ->next and ->prev and to generally obfuscate
26 the code. Mail me if you found a bug.
28 Cleaned up and incorporated some of the ideas from the red-black tree
29 library for inclusion into tinc (http://tinc.nl.linux.org/) by
30 Guus Sliepen <guus@sliepen.eu.org>.
32 $Id: avl_tree.c,v 1.1.2.17 2003/07/24 12:08:14 guus Exp $
41 #define AVL_NODE_COUNT(n) ((n) ? (n)->count : 0)
42 #define AVL_L_COUNT(n) (AVL_NODE_COUNT((n)->left))
43 #define AVL_R_COUNT(n) (AVL_NODE_COUNT((n)->right))
44 #define AVL_CALC_COUNT(n) (AVL_L_COUNT(n) + AVL_R_COUNT(n) + 1)
48 #define AVL_NODE_DEPTH(n) ((n) ? (n)->depth : 0)
49 #define L_AVL_DEPTH(n) (AVL_NODE_DEPTH((n)->left))
50 #define R_AVL_DEPTH(n) (AVL_NODE_DEPTH((n)->right))
51 #define AVL_CALC_DEPTH(n) ((L_AVL_DEPTH(n)>R_AVL_DEPTH(n)?L_AVL_DEPTH(n):R_AVL_DEPTH(n)) + 1)
55 static int lg(unsigned int u) __attribute__ ((const));
57 static int lg(unsigned int u)
91 /* Internal helper functions */
93 static int avl_check_balance(const avl_node_t *node)
98 d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node);
100 return d < -1 ? -1 : d > 1 ? 1 : 0;
103 * d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node));
104 * d = d<-1?-1:d>1?1:0;
108 pl = lg(AVL_L_COUNT(node));
109 r = AVL_R_COUNT(node);
114 if(pl < 2 || r >> pl - 2)
121 static void avl_rebalance(avl_tree_t *tree, avl_node_t *node)
126 avl_node_t **superparent;
131 parent = node->parent;
135 parent->left ? &parent->left : &parent->right : &tree->root;
137 switch (avl_check_balance(node)) {
141 if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
143 if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
145 node->left = child->right;
147 node->left->parent = node;
150 node->parent = child;
151 *superparent = child;
152 child->parent = parent;
154 node->count = AVL_CALC_COUNT(node);
155 child->count = AVL_CALC_COUNT(child);
158 node->depth = AVL_CALC_DEPTH(node);
159 child->depth = AVL_CALC_DEPTH(child);
162 gchild = child->right;
163 node->left = gchild->right;
166 node->left->parent = node;
167 child->right = gchild->left;
170 child->right->parent = child;
171 gchild->right = node;
174 gchild->right->parent = gchild;
175 gchild->left = child;
178 gchild->left->parent = gchild;
179 *superparent = gchild;
181 gchild->parent = parent;
183 node->count = AVL_CALC_COUNT(node);
184 child->count = AVL_CALC_COUNT(child);
185 gchild->count = AVL_CALC_COUNT(gchild);
188 node->depth = AVL_CALC_DEPTH(node);
189 child->depth = AVL_CALC_DEPTH(child);
190 gchild->depth = AVL_CALC_DEPTH(gchild);
198 if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
200 if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
202 node->right = child->left;
204 node->right->parent = node;
206 node->parent = child;
207 *superparent = child;
208 child->parent = parent;
210 node->count = AVL_CALC_COUNT(node);
211 child->count = AVL_CALC_COUNT(child);
214 node->depth = AVL_CALC_DEPTH(node);
215 child->depth = AVL_CALC_DEPTH(child);
218 gchild = child->left;
219 node->right = gchild->left;
222 node->right->parent = node;
223 child->left = gchild->right;
226 child->left->parent = child;
230 gchild->left->parent = gchild;
231 gchild->right = child;
234 gchild->right->parent = gchild;
236 *superparent = gchild;
237 gchild->parent = parent;
239 node->count = AVL_CALC_COUNT(node);
240 child->count = AVL_CALC_COUNT(child);
241 gchild->count = AVL_CALC_COUNT(gchild);
244 node->depth = AVL_CALC_DEPTH(node);
245 child->depth = AVL_CALC_DEPTH(child);
246 gchild->depth = AVL_CALC_DEPTH(gchild);
253 node->count = AVL_CALC_COUNT(node);
256 node->depth = AVL_CALC_DEPTH(node);
263 /* (De)constructors */
265 avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete)
269 tree = xmalloc_and_zero(sizeof(avl_tree_t));
270 tree->compare = compare;
271 tree->delete = delete;
276 void avl_free_tree(avl_tree_t *tree)
281 avl_node_t *avl_alloc_node(void)
283 return (avl_node_t *)xmalloc_and_zero(sizeof(avl_node_t));
286 void avl_free_node(avl_tree_t *tree, avl_node_t *node)
288 if(node->data && tree->delete)
289 tree->delete(node->data);
296 void *avl_search(const avl_tree_t *tree, const void *data)
300 node = avl_search_node(tree, data);
302 return node ? node->data : NULL;
305 void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result)
309 node = avl_search_closest_node(tree, data, result);
311 return node ? node->data : NULL;
314 void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data)
318 node = avl_search_closest_smaller_node(tree, data);
320 return node ? node->data : NULL;
323 void *avl_search_closest_greater(const avl_tree_t *tree, const void *data)
327 node = avl_search_closest_greater_node(tree, data);
329 return node ? node->data : NULL;
332 avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data)
337 node = avl_search_closest_node(tree, data, &result);
339 return result ? NULL : node;
342 avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
357 c = tree->compare(data, node->data);
385 avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree,
391 node = avl_search_closest_node(tree, data, &result);
399 avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree,
405 node = avl_search_closest_node(tree, data, &result);
413 /* Insertion and deletion */
415 avl_node_t *avl_insert(avl_tree_t *tree, void *data)
417 avl_node_t *closest, *new;
421 new = avl_alloc_node();
423 avl_insert_top(tree, new);
425 closest = avl_search_closest_node(tree, data, &result);
429 new = avl_alloc_node();
431 avl_insert_before(tree, closest, new);
435 new = avl_alloc_node();
437 avl_insert_after(tree, closest, new);
455 avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
461 avl_insert_top(tree, node);
463 closest = avl_search_closest_node(tree, node->data, &result);
467 avl_insert_before(tree, closest, node);
471 avl_insert_after(tree, closest, node);
489 void avl_insert_top(avl_tree_t *tree, avl_node_t *node)
491 node->prev = node->next = node->parent = NULL;
492 tree->head = tree->tail = tree->root = node;
495 void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
500 avl_insert_after(tree, tree->tail, node);
502 avl_insert_top(tree, node);
507 node->parent = before;
508 node->prev = before->prev;
511 avl_insert_after(tree, before->prev, node);
516 before->prev->next = node;
523 avl_rebalance(tree, before);
526 void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
530 avl_insert_before(tree, tree->head, node);
532 avl_insert_top(tree, node);
537 avl_insert_before(tree, after->next, node);
542 node->parent = after;
543 node->next = after->next;
546 after->next->prev = node;
553 avl_rebalance(tree, after);
556 avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
560 node = avl_search_node(tree, data);
563 avl_unlink_node(tree, node);
568 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
571 avl_node_t **superparent;
572 avl_node_t *subst, *left, *right;
576 node->prev->next = node->next;
578 tree->head = node->next;
580 node->next->prev = node->prev;
582 tree->tail = node->prev;
584 parent = node->parent;
588 parent->left ? &parent->left : &parent->right : &tree->root;
593 *superparent = right;
596 right->parent = parent;
601 left->parent = parent;
609 balnode = subst->parent;
610 balnode->right = subst->left;
613 balnode->right->parent = balnode;
616 left->parent = subst;
619 subst->right = right;
620 subst->parent = parent;
621 right->parent = subst;
622 *superparent = subst;
625 avl_rebalance(tree, balnode);
627 node->next = node->prev = node->parent = node->left = node->right = NULL;
637 void avl_delete_node(avl_tree_t *tree, avl_node_t *node)
639 avl_unlink_node(tree, node);
640 avl_free_node(tree, node);
643 void avl_delete(avl_tree_t *tree, void *data)
647 node = avl_search_node(tree, data);
650 avl_delete_node(tree, node);
653 /* Fast tree cleanup */
655 void avl_delete_tree(avl_tree_t *tree)
657 avl_node_t *node, *next;
659 for(node = tree->root; node; node = next) {
661 avl_free_node(tree, node);
669 void avl_foreach(const avl_tree_t *tree, avl_action_t action)
671 avl_node_t *node, *next;
673 for(node = tree->head; node; node = next) {
679 void avl_foreach_node(const avl_tree_t *tree, avl_action_t action)
681 avl_node_t *node, *next;
683 for(node = tree->head; node; node = next) {
692 unsigned int avl_count(const avl_tree_t *tree)
694 return AVL_NODE_COUNT(tree->root);
697 avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index)
705 c = AVL_L_COUNT(node);
709 } else if(index > c) {
720 unsigned int avl_index(const avl_node_t *node)
725 index = AVL_L_COUNT(node);
727 while((next = node->parent)) {
728 if(node == next->right)
729 index += AVL_L_COUNT(next) + 1;
737 unsigned int avl_depth(const avl_tree_t *tree)
739 return AVL_NODE_DEPTH(tree->root);