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