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