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