Fix compiler warnings.
[tinc] / lib / avl_tree.c
1 /*
2     avl_tree.c -- avl_ tree and linked list convenience
3     Copyright (C) 1998 Michael H. Buselli
4                   2000,2001 Ivo Timmermans <ivo@o2w.nl>,
5                   2000,2001 Guus Sliepen <guus@sliepen.eu.org>
6                   2000,2001 Wessel Dankers <wsl@nl.linux.org>
7
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.
12
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.
17
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.
21
22     Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
23
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.
27
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>.
31
32     $Id: avl_tree.c,v 1.1.2.12 2002/09/10 09:40:15 guus Exp $
33 */
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <xalloc.h>
38
39 #include "avl_tree.h"
40
41 #ifdef AVL_COUNT
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)
46 #endif
47
48 #ifdef AVL_DEPTH
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)
53 #endif
54
55 #ifndef AVL_DEPTH
56 int lg(unsigned int u)
57 {
58         int r = 1;
59
60         if(!u)
61                 return 0;
62
63         if(u & 0xffff0000) {
64                 u >>= 16;
65                 r += 16;
66         }
67
68         if(u & 0x0000ff00) {
69                 u >>= 8;
70                 r += 8;
71         }
72
73         if(u & 0x000000f0) {
74                 u >>= 4;
75                 r += 4;
76         }
77
78         if(u & 0x0000000c) {
79                 u >>= 2;
80                 r += 2;
81         }
82
83         if(u & 0x00000002)
84                 r++;
85
86         return r;
87 }
88 #endif
89
90 /* Internal helper functions */
91
92 int avl_check_balance(avl_node_t *node)
93 {
94 #ifdef AVL_DEPTH
95         int d;
96
97         d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node);
98
99         return d < -1 ? -1 : d > 1 ? 1 : 0;
100 #else
101 /*      int d;
102  *      d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node));
103  *      d = d<-1?-1:d>1?1:0;
104  */
105         int pl, r;
106
107         pl = lg(AVL_L_COUNT(node));
108         r = AVL_R_COUNT(node);
109
110         if(r >> pl + 1)
111                 return 1;
112
113         if(pl < 2 || r >> pl - 2)
114                 return 0;
115
116         return -1;
117 #endif
118 }
119
120 void avl_rebalance(avl_tree_t *tree, avl_node_t *node)
121 {
122         avl_node_t *child;
123         avl_node_t *gchild;
124         avl_node_t *parent;
125         avl_node_t **superparent;
126
127         parent = node;
128
129         while(node) {
130                 parent = node->parent;
131
132                 superparent =
133                         parent ? node ==
134                         parent->left ? &parent->left : &parent->right : &tree->root;
135
136                 switch (avl_check_balance(node)) {
137                         case -1:
138                                 child = node->left;
139 #ifdef AVL_DEPTH
140                                 if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
141 #else
142                                 if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
143 #endif
144                                         node->left = child->right;
145                                         if(node->left)
146                                                 node->left->parent = node;
147
148                                         child->right = node;
149                                         node->parent = child;
150                                         *superparent = child;
151                                         child->parent = parent;
152 #ifdef AVL_COUNT
153                                         node->count = AVL_CALC_COUNT(node);
154                                         child->count = AVL_CALC_COUNT(child);
155 #endif
156 #ifdef AVL_DEPTH
157                                         node->depth = AVL_CALC_DEPTH(node);
158                                         child->depth = AVL_CALC_DEPTH(child);
159 #endif
160                                 } else {
161                                         gchild = child->right;
162                                         node->left = gchild->right;
163
164                                         if(node->left)
165                                                 node->left->parent = node;
166                                         child->right = gchild->left;
167
168                                         if(child->right)
169                                                 child->right->parent = child;
170                                         gchild->right = node;
171
172                                         if(gchild->right)
173                                                 gchild->right->parent = gchild;
174                                         gchild->left = child;
175
176                                         if(gchild->left)
177                                                 gchild->left->parent = gchild;
178                                         *superparent = gchild;
179
180                                         gchild->parent = parent;
181 #ifdef AVL_COUNT
182                                         node->count = AVL_CALC_COUNT(node);
183                                         child->count = AVL_CALC_COUNT(child);
184                                         gchild->count = AVL_CALC_COUNT(gchild);
185 #endif
186 #ifdef AVL_DEPTH
187                                         node->depth = AVL_CALC_DEPTH(node);
188                                         child->depth = AVL_CALC_DEPTH(child);
189                                         gchild->depth = AVL_CALC_DEPTH(gchild);
190 #endif
191                                 }
192                                 break;
193
194                         case 1:
195                                 child = node->right;
196 #ifdef AVL_DEPTH
197                                 if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
198 #else
199                                 if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
200 #endif
201                                         node->right = child->left;
202                                         if(node->right)
203                                                 node->right->parent = node;
204                                         child->left = node;
205                                         node->parent = child;
206                                         *superparent = child;
207                                         child->parent = parent;
208 #ifdef AVL_COUNT
209                                         node->count = AVL_CALC_COUNT(node);
210                                         child->count = AVL_CALC_COUNT(child);
211 #endif
212 #ifdef AVL_DEPTH
213                                         node->depth = AVL_CALC_DEPTH(node);
214                                         child->depth = AVL_CALC_DEPTH(child);
215 #endif
216                                 } else {
217                                         gchild = child->left;
218                                         node->right = gchild->left;
219
220                                         if(node->right)
221                                                 node->right->parent = node;
222                                         child->left = gchild->right;
223
224                                         if(child->left)
225                                                 child->left->parent = child;
226                                         gchild->left = node;
227
228                                         if(gchild->left)
229                                                 gchild->left->parent = gchild;
230                                         gchild->right = child;
231
232                                         if(gchild->right)
233                                                 gchild->right->parent = gchild;
234
235                                         *superparent = gchild;
236                                         gchild->parent = parent;
237 #ifdef AVL_COUNT
238                                         node->count = AVL_CALC_COUNT(node);
239                                         child->count = AVL_CALC_COUNT(child);
240                                         gchild->count = AVL_CALC_COUNT(gchild);
241 #endif
242 #ifdef AVL_DEPTH
243                                         node->depth = AVL_CALC_DEPTH(node);
244                                         child->depth = AVL_CALC_DEPTH(child);
245                                         gchild->depth = AVL_CALC_DEPTH(gchild);
246 #endif
247                                 }
248                                 break;
249
250                         default:
251 #ifdef AVL_COUNT
252                                 node->count = AVL_CALC_COUNT(node);
253 #endif
254 #ifdef AVL_DEPTH
255                                 node->depth = AVL_CALC_DEPTH(node);
256 #endif
257                 }
258                 node = parent;
259         }
260 }
261
262 /* (De)constructors */
263
264 avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete)
265 {
266         avl_tree_t *tree;
267
268         tree = xmalloc_and_zero(sizeof(avl_tree_t));
269         tree->compare = compare;
270         tree->delete = delete;
271
272         return tree;
273 }
274
275 void avl_free_tree(avl_tree_t *tree)
276 {
277         free(tree);
278 }
279
280 avl_node_t *avl_alloc_node(void)
281 {
282         return (avl_node_t *)xmalloc_and_zero(sizeof(avl_node_t));
283 }
284
285 void avl_free_node(avl_tree_t *tree, avl_node_t *node)
286 {
287         if(node->data && tree->delete)
288                 tree->delete(node->data);
289
290         free(node);
291 }
292
293 /* Searching */
294
295 void *avl_search(const avl_tree_t *tree, const void *data)
296 {
297         avl_node_t *node;
298
299         node = avl_search_node(tree, data);
300
301         return node ? node->data : NULL;
302 }
303
304 void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result)
305 {
306         avl_node_t *node;
307
308         node = avl_search_closest_node(tree, data, result);
309
310         return node ? node->data : NULL;
311 }
312
313 void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data)
314 {
315         avl_node_t *node;
316
317         node = avl_search_closest_smaller_node(tree, data);
318
319         return node ? node->data : NULL;
320 }
321
322 void *avl_search_closest_greater(const avl_tree_t *tree, const void *data)
323 {
324         avl_node_t *node;
325
326         node = avl_search_closest_greater_node(tree, data);
327
328         return node ? node->data : NULL;
329 }
330
331 avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data)
332 {
333         avl_node_t *node;
334         int result;
335
336         node = avl_search_closest_node(tree, data, &result);
337
338         return result ? NULL : node;
339 }
340
341 avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
342                                                                         int *result)
343 {
344         avl_node_t *node;
345         int c;
346
347         node = tree->root;
348
349         if(!node) {
350                 if(result)
351                         *result = 0;
352                 return NULL;
353         }
354
355         for(;;) {
356                 c = tree->compare(data, node->data);
357
358                 if(c < 0) {
359                         if(node->left)
360                                 node = node->left;
361                         else {
362                                 if(result)
363                                         *result = -1;
364                                 break;
365                         }
366                 } else if(c > 0) {
367                         if(node->right)
368                                 node = node->right;
369                         else {
370                                 if(result)
371                                         *result = 1;
372                                 break;
373                         }
374                 } else {
375                         if(result)
376                                 *result = 0;
377                         break;
378                 }
379         }
380
381         return node;
382 }
383
384 avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree,
385                                                                                         const void *data)
386 {
387         avl_node_t *node;
388         int result;
389
390         node = avl_search_closest_node(tree, data, &result);
391
392         if(result < 0)
393                 node = node->prev;
394
395         return node;
396 }
397
398 avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree,
399                                                                                         const void *data)
400 {
401         avl_node_t *node;
402         int result;
403
404         node = avl_search_closest_node(tree, data, &result);
405
406         if(result > 0)
407                 node = node->next;
408
409         return node;
410 }
411
412 /* Insertion and deletion */
413
414 avl_node_t *avl_insert(avl_tree_t *tree, void *data)
415 {
416         avl_node_t *closest, *new;
417         int result;
418
419         if(!tree->root) {
420                 new = avl_alloc_node();
421                 new->data = data;
422                 avl_insert_top(tree, new);
423         } else {
424                 closest = avl_search_closest_node(tree, data, &result);
425
426                 switch (result) {
427                         case -1:
428                                 new = avl_alloc_node();
429                                 new->data = data;
430                                 avl_insert_before(tree, closest, new);
431                                 break;
432
433                         case 1:
434                                 new = avl_alloc_node();
435                                 new->data = data;
436                                 avl_insert_after(tree, closest, new);
437                                 break;
438
439                         default:
440                                 return NULL;
441                 }
442         }
443
444 #ifdef AVL_COUNT
445         new->count = 1;
446 #endif
447 #ifdef AVL_DEPTH
448         new->depth = 1;
449 #endif
450
451         return new;
452 }
453
454 avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
455 {
456         avl_node_t *closest;
457         int result;
458
459         if(!tree->root)
460                 avl_insert_top(tree, node);
461         else {
462                 closest = avl_search_closest_node(tree, node->data, &result);
463
464                 switch (result) {
465                         case -1:
466                                 avl_insert_before(tree, closest, node);
467                                 break;
468
469                         case 1:
470                                 avl_insert_after(tree, closest, node);
471                                 break;
472
473                         case 0:
474                                 return NULL;
475                 }
476         }
477
478 #ifdef AVL_COUNT
479         node->count = 1;
480 #endif
481 #ifdef AVL_DEPTH
482         node->depth = 1;
483 #endif
484
485         return node;
486 }
487
488 void avl_insert_top(avl_tree_t *tree, avl_node_t *node)
489 {
490         node->prev = node->next = node->parent = NULL;
491         tree->head = tree->tail = tree->root = node;
492 }
493
494 void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
495                                            avl_node_t *node)
496 {
497         if(!before) {
498                 if(tree->tail)
499                         avl_insert_after(tree, tree->tail, node);
500                 else
501                         avl_insert_top(tree, node);
502                 return;
503         }
504
505         node->next = before;
506         node->parent = before;
507         node->prev = before->prev;
508
509         if(before->left) {
510                 avl_insert_after(tree, before->prev, node);
511                 return;
512         }
513
514         if(before->prev)
515                 before->prev->next = node;
516         else
517                 tree->head = node;
518
519         before->prev = node;
520         before->left = node;
521
522         avl_rebalance(tree, before->parent);
523 }
524
525 void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
526 {
527         if(!after) {
528                 if(tree->head)
529                         avl_insert_before(tree, tree->head, node);
530                 else
531                         avl_insert_top(tree, node);
532                 return;
533         }
534
535         if(after->right) {
536                 avl_insert_before(tree, after->next, node);
537                 return;
538         }
539
540         node->prev = after;
541         node->parent = after;
542         node->next = after->next;
543
544         if(after->next)
545                 after->next->prev = node;
546         else
547                 tree->tail = node;
548
549         after->next = node;
550         after->right = node;
551
552         avl_rebalance(tree, after->parent);
553 }
554
555 avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
556 {
557         avl_node_t *node;
558
559         node = avl_search_node(tree, data);
560
561         if(node)
562                 avl_unlink_node(tree, node);
563
564         return node;
565 }
566
567 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
568 {
569         avl_node_t *parent;
570         avl_node_t **superparent;
571         avl_node_t *subst, *left, *right;
572         avl_node_t *balnode;
573
574         if(node->prev)
575                 node->prev->next = node->next;
576         else
577                 tree->head = node->next;
578         if(node->next)
579                 node->next->prev = node->prev;
580         else
581                 tree->tail = node->prev;
582
583         parent = node->parent;
584
585         superparent =
586                 parent ? node ==
587                 parent->left ? &parent->left : &parent->right : &tree->root;
588
589         left = node->left;
590         right = node->right;
591         if(!left) {
592                 *superparent = right;
593
594                 if(right)
595                         right->parent = parent;
596
597                 balnode = parent;
598         } else if(!right) {
599                 *superparent = left;
600                 left->parent = parent;
601                 balnode = parent;
602         } else {
603                 subst = node->prev;
604
605                 if(subst == left) {
606                         balnode = subst;
607                 } else {
608                         balnode = subst->parent;
609                         balnode->right = subst->left;
610
611                         if(balnode->right)
612                                 balnode->right->parent = balnode;
613
614                         subst->left = left;
615                         left->parent = subst;
616                 }
617
618                 subst->right = right;
619                 subst->parent = parent;
620                 right->parent = subst;
621                 *superparent = subst;
622         }
623
624         avl_rebalance(tree, balnode);
625
626         node->next = node->prev = node->parent = node->left = node->right = NULL;
627
628 #ifdef AVL_COUNT
629         node->count = 0;
630 #endif
631 #ifdef AVL_DEPTH
632         node->depth = 0;
633 #endif
634 }
635
636 void avl_delete_node(avl_tree_t *tree, avl_node_t *node)
637 {
638         avl_unlink_node(tree, node);
639         avl_free_node(tree, node);
640 }
641
642 void avl_delete(avl_tree_t *tree, void *data)
643 {
644         avl_node_t *node;
645
646         node = avl_search_node(tree, data);
647
648         if(node)
649                 avl_delete_node(tree, node);
650 }
651
652 /* Fast tree cleanup */
653
654 void avl_delete_tree(avl_tree_t *tree)
655 {
656         avl_node_t *node, *next;
657
658         for(node = tree->root; node; node = next) {
659                 next = node->next;
660                 avl_free_node(tree, node);
661         }
662
663         avl_free_tree(tree);
664 }
665
666 /* Tree walking */
667
668 void avl_foreach(avl_tree_t *tree, avl_action_t action)
669 {
670         avl_node_t *node, *next;
671
672         for(node = tree->head; node; node = next) {
673                 next = node->next;
674                 action(node->data);
675         }
676 }
677
678 void avl_foreach_node(avl_tree_t *tree, avl_action_t action)
679 {
680         avl_node_t *node, *next;
681
682         for(node = tree->head; node; node = next) {
683                 next = node->next;
684                 action(node);
685         }
686 }
687
688 /* Indexing */
689
690 #ifdef AVL_COUNT
691 unsigned int avl_count(avl_tree_t *tree)
692 {
693         return AVL_NODE_COUNT(tree->root);
694 }
695
696 avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index)
697 {
698         avl_node_t *node;
699         unsigned int c;
700
701         node = tree->root;
702
703         while(node) {
704                 c = AVL_L_COUNT(node);
705
706                 if(index < c) {
707                         node = node->left;
708                 } else if(index > c) {
709                         node = node->right;
710                         index -= c + 1;
711                 } else {
712                         return node;
713                 }
714         }
715
716         return NULL;
717 }
718
719 unsigned int avl_index(const avl_node_t *node)
720 {
721         avl_node_t *next;
722         unsigned int index;
723
724         index = AVL_L_COUNT(node);
725
726         while((next = node->parent)) {
727                 if(node == next->right)
728                         index += AVL_L_COUNT(next) + 1;
729                 node = next;
730         }
731
732         return index;
733 }
734 #endif
735 #ifdef AVL_DEPTH
736 unsigned int avl_depth(avl_tree_t *tree)
737 {
738         return AVL_NODE_DEPTH(tree->root);
739 }
740 #endif