Update avl implementation to current packetbb version
[olsrd.git] / src / common / avl.c
1 /*
2  * PacketBB handler library (see RFC 5444)
3  * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
4  * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org/git for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  */
40
41 #include <stdbool.h>
42 #include <stddef.h>
43 #include <stdint.h>
44 #include <time.h>
45 #include <string.h>
46
47 #include "avl.h"
48 #include "list.h"
49
50 /**
51  * internal type save inline function to calculate the maximum of
52  * to integers without macro implementation.
53  *
54  * @param x first parameter of maximum function
55  * @param y second parameter of maximum function
56  * @return largest integer of both parameters
57  */
58 static inline int avl_max(int x, int y) {
59   return x > y ? x : y;
60 }
61
62 /**
63  * internal type save inline function to calculate the minimum of
64  * to integers without macro implementation.
65  *
66  * @param x first parameter of minimum function
67  * @param y second parameter of minimum function
68  * @return smallest integer of both parameters
69  */
70 static inline int avl_min(int x, int y) {
71   return x < y ? x : y;
72 }
73
74 static struct avl_node *
75 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
76 static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
77 static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
78 static void post_insert(struct avl_tree *tree, struct avl_node *node);
79 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
80 static void avl_remove(struct avl_tree *tree, struct avl_node *node);
81
82 /**
83  * Initialize a new avl_tree struct
84  * @param tree pointer to avl-tree
85  * @param comp pointer to comparator for the tree
86  * @param allow_dups true if the tree allows multiple
87  *   elements with the same
88  * @param ptr custom parameter for comparator
89  */
90 void
91 avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
92 {
93   list_init_head(&tree->list_head);
94   tree->root = NULL;
95   tree->count = 0;
96   tree->comp = comp;
97   tree->allow_dups = allow_dups;
98   tree->cmp_ptr = ptr;
99 }
100
101 /**
102  * Finds a node in an avl-tree with a certain key
103  * @param tree pointer to avl-tree
104  * @param key pointer to key
105  * @return pointer to avl-node with key, NULL if no node with
106  *    this key exists.
107  */
108 struct avl_node *
109 avl_find(const struct avl_tree *tree, const void *key)
110 {
111   struct avl_node *node;
112   int diff;
113
114   if (tree->root == NULL)
115     return NULL;
116
117   node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
118
119   return diff == 0 ? node : NULL;
120 }
121
122 /**
123  * Finds the last node in an avl-tree with a key less or equal
124  * than the specified key
125  * @param tree pointer to avl-tree
126  * @param key pointer to specified key
127  * @return pointer to avl-node, NULL if no node with
128  *    key less or equal specified key exists.
129  */
130 struct avl_node *
131 avl_find_lessequal(const struct avl_tree *tree, const void *key) {
132   struct avl_node *node, *next;
133   int diff;
134
135   if (tree->root == NULL)
136     return NULL;
137
138   node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
139
140   /* go left as long as key<node.key */
141   while (diff < 0) {
142     if (list_is_first(&tree->list_head, &node->list)) {
143       return NULL;
144     }
145
146     node = (struct avl_node *)node->list.prev;
147     diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
148   }
149
150   /* go right as long as key>=next_node.key */
151   next = node;
152   while (diff >= 0) {
153     node = next;
154     if (list_is_last(&tree->list_head, &node->list)) {
155       break;
156     }
157
158     next = (struct avl_node *)node->list.next;
159     diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
160   }
161   return node;
162 }
163
164 /**
165  * Finds the first node in an avl-tree with a key greater or equal
166  * than the specified key
167  * @param tree pointer to avl-tree
168  * @param key pointer to specified key
169  * @return pointer to avl-node, NULL if no node with
170  *    key greater or equal specified key exists.
171  */
172 struct avl_node *
173 avl_find_greaterequal(const struct avl_tree *tree, const void *key) {
174   struct avl_node *node, *next;
175   int diff;
176
177   if (tree->root == NULL)
178     return NULL;
179
180   node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
181
182   /* go right as long as key>node.key */
183   while (diff > 0) {
184     if (list_is_last(&tree->list_head, &node->list)) {
185       return NULL;
186     }
187
188     node = (struct avl_node *)node->list.next;
189     diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
190   }
191
192   /* go left as long as key<=next_node.key */
193   next = node;
194   while (diff <= 0) {
195     node = next;
196     if (list_is_first(&tree->list_head, &node->list)) {
197       break;
198     }
199
200     next = (struct avl_node *)node->list.prev;
201     diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
202   }
203   return node;
204 }
205
206 /**
207  * Inserts an avl_node into a tree
208  * @param tree pointer to tree
209  * @param new pointer to node
210  * @return 0 if node was inserted successfully, -1 if it was not inserted
211  *   because of a key collision
212  */
213 int
214 avl_insert(struct avl_tree *tree, struct avl_node *new)
215 {
216   struct avl_node *node, *next, *last;
217   int diff;
218
219   new->parent = NULL;
220
221   new->left = NULL;
222   new->right = NULL;
223
224   new->balance = 0;
225   new->leader = true;
226
227   if (tree->root == NULL) {
228     list_add_head(&tree->list_head, &new->list);
229     tree->root = new;
230     tree->count = 1;
231     return 0;
232   }
233
234   node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
235
236   last = node;
237
238   while (!list_is_last(&tree->list_head, &last->list)) {
239     next = list_next_element(last, list);
240     if (next->leader) {
241       break;
242     }
243     last = next;
244   }
245
246   diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
247
248   if (diff == 0) {
249     if (!tree->allow_dups)
250       return -1;
251
252     new->leader = 0;
253
254     avl_insert_after(tree, last, new);
255     return 0;
256   }
257
258   if (node->balance == 1) {
259     avl_insert_before(tree, node, new);
260
261     node->balance = 0;
262     new->parent = node;
263     node->left = new;
264     return 0;
265   }
266
267   if (node->balance == -1) {
268     avl_insert_after(tree, last, new);
269
270     node->balance = 0;
271     new->parent = node;
272     node->right = new;
273     return 0;
274   }
275
276   if (diff < 0) {
277     avl_insert_before(tree, node, new);
278
279     node->balance = -1;
280     new->parent = node;
281     node->left = new;
282     post_insert(tree, node);
283     return 0;
284   }
285
286   avl_insert_after(tree, last, new);
287
288   node->balance = 1;
289   new->parent = node;
290   node->right = new;
291   post_insert(tree, node);
292   return 0;
293 }
294
295 /**
296  * Remove a node from an avl tree
297  * @param tree pointer to tree
298  * @param node pointer to node
299  */
300 void
301 avl_delete(struct avl_tree *tree, struct avl_node *node)
302 {
303   struct avl_node *next;
304   struct avl_node *parent;
305   struct avl_node *left;
306   struct avl_node *right;
307   if (node->leader) {
308     if (tree->allow_dups
309         && !list_is_last(&tree->list_head, &node->list)
310         && !(next = list_next_element(node, list))->leader) {
311       next->leader = true;
312       next->balance = node->balance;
313
314       parent = node->parent;
315       left = node->left;
316       right = node->right;
317
318       next->parent = parent;
319       next->left = left;
320       next->right = right;
321
322       if (parent == NULL)
323         tree->root = next;
324
325       else {
326         if (node == parent->left)
327           parent->left = next;
328
329         else
330           parent->right = next;
331       }
332
333       if (left != NULL)
334         left->parent = next;
335
336       if (right != NULL)
337         right->parent = next;
338     }
339
340     else
341       avl_delete_worker(tree, node);
342   }
343
344   avl_remove(tree, node);
345 }
346
347 static struct avl_node *
348 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
349 {
350   int diff;
351
352   diff = (*comp) (key, node->key, cmp_ptr);
353   *cmp_result = diff;
354
355   if (diff < 0) {
356     if (node->left != NULL)
357       return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
358
359     return node;
360   }
361
362   if (diff > 0) {
363     if (node->right != NULL)
364       return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
365
366     return node;
367   }
368
369   return node;
370 }
371
372 static void
373 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
374 {
375   struct avl_node *left, *parent;
376
377   left = node->left;
378   parent = node->parent;
379
380   left->parent = parent;
381   node->parent = left;
382
383   if (parent == NULL)
384     tree->root = left;
385
386   else {
387     if (parent->left == node)
388       parent->left = left;
389
390     else
391       parent->right = left;
392   }
393
394   node->left = left->right;
395   left->right = node;
396
397   if (node->left != NULL)
398     node->left->parent = node;
399
400   node->balance += 1 - avl_min(left->balance, 0);
401   left->balance += 1 + avl_max(node->balance, 0);
402 }
403
404 static void
405 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
406 {
407   struct avl_node *right, *parent;
408
409   right = node->right;
410   parent = node->parent;
411
412   right->parent = parent;
413   node->parent = right;
414
415   if (parent == NULL)
416     tree->root = right;
417
418   else {
419     if (parent->left == node)
420       parent->left = right;
421
422     else
423       parent->right = right;
424   }
425
426   node->right = right->left;
427   right->left = node;
428
429   if (node->right != NULL)
430     node->right->parent = node;
431
432   node->balance -= 1 + avl_max(right->balance, 0);
433   right->balance -= 1 - avl_min(node->balance, 0);
434 }
435
436 static void
437 post_insert(struct avl_tree *tree, struct avl_node *node)
438 {
439   struct avl_node *parent = node->parent;
440
441   if (parent == NULL)
442     return;
443
444   if (node == parent->left) {
445     parent->balance--;
446
447     if (parent->balance == 0)
448       return;
449
450     if (parent->balance == -1) {
451       post_insert(tree, parent);
452       return;
453     }
454
455     if (node->balance == -1) {
456       avl_rotate_right(tree, parent);
457       return;
458     }
459
460     avl_rotate_left(tree, node);
461     avl_rotate_right(tree, node->parent->parent);
462     return;
463   }
464
465   parent->balance++;
466
467   if (parent->balance == 0)
468     return;
469
470   if (parent->balance == 1) {
471     post_insert(tree, parent);
472     return;
473   }
474
475   if (node->balance == 1) {
476     avl_rotate_left(tree, parent);
477     return;
478   }
479
480   avl_rotate_right(tree, node);
481   avl_rotate_left(tree, node->parent->parent);
482 }
483
484 static void
485 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
486 {
487   list_add_before(&pos_node->list, &node->list);
488   tree->count++;
489 }
490
491 static void
492 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
493 {
494   list_add_after(&pos_node->list, &node->list);
495   tree->count++;
496 }
497
498 static void
499 avl_remove(struct avl_tree *tree, struct avl_node *node)
500 {
501   list_remove(&node->list);
502   tree->count--;
503 }
504
505 static void
506 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
507 {
508   struct avl_node *parent;
509
510   if ((parent = node->parent) == NULL)
511     return;
512
513   if (node == parent->left) {
514     parent->balance++;
515
516     if (parent->balance == 0) {
517       avl_post_delete(tree, parent);
518       return;
519     }
520
521     if (parent->balance == 1)
522       return;
523
524     if (parent->right->balance == 0) {
525       avl_rotate_left(tree, parent);
526       return;
527     }
528
529     if (parent->right->balance == 1) {
530       avl_rotate_left(tree, parent);
531       avl_post_delete(tree, parent->parent);
532       return;
533     }
534
535     avl_rotate_right(tree, parent->right);
536     avl_rotate_left(tree, parent);
537     avl_post_delete(tree, parent->parent);
538     return;
539   }
540
541   parent->balance--;
542
543   if (parent->balance == 0) {
544     avl_post_delete(tree, parent);
545     return;
546   }
547
548   if (parent->balance == -1)
549     return;
550
551   if (parent->left->balance == 0) {
552     avl_rotate_right(tree, parent);
553     return;
554   }
555
556   if (parent->left->balance == -1) {
557     avl_rotate_right(tree, parent);
558     avl_post_delete(tree, parent->parent);
559     return;
560   }
561
562   avl_rotate_left(tree, parent->left);
563   avl_rotate_right(tree, parent);
564   avl_post_delete(tree, parent->parent);
565 }
566
567 static struct avl_node *
568 avl_local_min(struct avl_node *node)
569 {
570   while (node->left != NULL)
571     node = node->left;
572
573   return node;
574 }
575
576 #if 0
577 static struct avl_node *
578 avl_local_max(struct avl_node *node)
579 {
580   while (node->right != NULL)
581     node = node->right;
582
583   return node;
584 }
585 #endif
586
587 static void
588 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
589 {
590   struct avl_node *parent, *min;
591
592   parent = node->parent;
593
594   if (node->left == NULL && node->right == NULL) {
595     if (parent == NULL) {
596       tree->root = NULL;
597       return;
598     }
599
600     if (parent->left == node) {
601       parent->left = NULL;
602       parent->balance++;
603
604       if (parent->balance == 1)
605         return;
606
607       if (parent->balance == 0) {
608         avl_post_delete(tree, parent);
609         return;
610       }
611
612       if (parent->right->balance == 0) {
613         avl_rotate_left(tree, parent);
614         return;
615       }
616
617       if (parent->right->balance == 1) {
618         avl_rotate_left(tree, parent);
619         avl_post_delete(tree, parent->parent);
620         return;
621       }
622
623       avl_rotate_right(tree, parent->right);
624       avl_rotate_left(tree, parent);
625       avl_post_delete(tree, parent->parent);
626       return;
627     }
628
629     if (parent->right == node) {
630       parent->right = NULL;
631       parent->balance--;
632
633       if (parent->balance == -1)
634         return;
635
636       if (parent->balance == 0) {
637         avl_post_delete(tree, parent);
638         return;
639       }
640
641       if (parent->left->balance == 0) {
642         avl_rotate_right(tree, parent);
643         return;
644       }
645
646       if (parent->left->balance == -1) {
647         avl_rotate_right(tree, parent);
648         avl_post_delete(tree, parent->parent);
649         return;
650       }
651
652       avl_rotate_left(tree, parent->left);
653       avl_rotate_right(tree, parent);
654       avl_post_delete(tree, parent->parent);
655       return;
656     }
657   }
658
659   if (node->left == NULL) {
660     if (parent == NULL) {
661       tree->root = node->right;
662       node->right->parent = NULL;
663       return;
664     }
665
666     node->right->parent = parent;
667
668     if (parent->left == node)
669       parent->left = node->right;
670
671     else
672       parent->right = node->right;
673
674     avl_post_delete(tree, node->right);
675     return;
676   }
677
678   if (node->right == NULL) {
679     if (parent == NULL) {
680       tree->root = node->left;
681       node->left->parent = NULL;
682       return;
683     }
684
685     node->left->parent = parent;
686
687     if (parent->left == node)
688       parent->left = node->left;
689
690     else
691       parent->right = node->left;
692
693     avl_post_delete(tree, node->left);
694     return;
695   }
696
697   min = avl_local_min(node->right);
698   avl_delete_worker(tree, min);
699   parent = node->parent;
700
701   min->balance = node->balance;
702   min->parent = parent;
703   min->left = node->left;
704   min->right = node->right;
705
706   if (min->left != NULL)
707     min->left->parent = min;
708
709   if (min->right != NULL)
710     min->right->parent = min;
711
712   if (parent == NULL) {
713     tree->root = min;
714     return;
715   }
716
717   if (parent->left == node) {
718     parent->left = min;
719     return;
720   }
721
722   parent->right = min;
723 }
724
725 /*
726  * Local Variables:
727  * c-basic-offset: 2
728  * indent-tabs-mode: nil
729  * End:
730  */