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