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