reformat the avl library
[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   tree->comp = comp;
86 }
87
88 static struct avl_node *
89 avl_find_rec_ipv4(struct avl_node *node, const void *key)
90 {
91   if (*(const unsigned int *)key < *(const unsigned int *)node->key) {
92     if (node->left != NULL)
93       return avl_find_rec_ipv4(node->left, key);
94   }
95
96   else if (*(const unsigned int *)key > *(const unsigned int *)node->key) {
97     if (node->right != NULL)
98       return avl_find_rec_ipv4(node->right, key);
99   }
100
101   return node;
102 }
103
104 static struct avl_node *
105 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp)
106 {
107   int diff;
108
109   if (NULL == comp)
110     return avl_find_rec_ipv4(node, key);
111
112   diff = (*comp) (key, node->key);
113
114   if (diff < 0) {
115     if (node->left != NULL)
116       return avl_find_rec(node->left, key, comp);
117
118     return node;
119   }
120
121   if (diff > 0) {
122     if (node->right != NULL)
123       return avl_find_rec(node->right, key, comp);
124
125     return node;
126   }
127
128   return node;
129 }
130
131 struct avl_node *
132 avl_find(struct avl_tree *tree, const void *key)
133 {
134   struct avl_node *node;
135
136   if (tree->root == NULL)
137     return NULL;
138
139   node = avl_find_rec(tree->root, key, tree->comp);
140
141   if (NULL == tree->comp) {
142     if (0 != ip4cmp(node->key, key))
143       return NULL;
144   }
145
146   else {
147     if ((*tree->comp) (node->key, key) != 0)
148       return NULL;
149   }
150
151   return node;
152 }
153
154 static void
155 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
156 {
157   struct avl_node *left, *parent;
158
159   left = node->left;
160   parent = node->parent;
161
162   left->parent = parent;
163   node->parent = left;
164
165   if (parent == NULL)
166     tree->root = left;
167
168   else {
169     if (parent->left == node)
170       parent->left = left;
171
172     else
173       parent->right = left;
174   }
175
176   node->left = left->right;
177   left->right = node;
178
179   if (node->left != NULL)
180     node->left->parent = node;
181
182   node->balance += 1 - MIN(left->balance, 0);
183   left->balance += 1 + MAX(node->balance, 0);
184 }
185
186 static void
187 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
188 {
189   struct avl_node *right, *parent;
190
191   right = node->right;
192   parent = node->parent;
193
194   right->parent = parent;
195   node->parent = right;
196
197   if (parent == NULL)
198     tree->root = right;
199
200   else {
201     if (parent->left == node)
202       parent->left = right;
203
204     else
205       parent->right = right;
206   }
207
208   node->right = right->left;
209   right->left = node;
210
211   if (node->right != NULL)
212     node->right->parent = node;
213
214   node->balance -= 1 + MAX(right->balance, 0);
215   right->balance -= 1 - MIN(node->balance, 0);
216 }
217
218 static void
219 post_insert(struct avl_tree *tree, struct avl_node *node)
220 {
221   struct avl_node *parent = node->parent;
222
223   if (parent == NULL)
224     return;
225
226   if (node == parent->left) {
227     parent->balance--;
228
229     if (parent->balance == 0)
230       return;
231
232     if (parent->balance == -1) {
233       post_insert(tree, parent);
234       return;
235     }
236
237     if (node->balance == -1) {
238       avl_rotate_right(tree, parent);
239       return;
240     }
241
242     avl_rotate_left(tree, node);
243     avl_rotate_right(tree, node->parent->parent);
244     return;
245   }
246
247   parent->balance++;
248
249   if (parent->balance == 0)
250     return;
251
252   if (parent->balance == 1) {
253     post_insert(tree, parent);
254     return;
255   }
256
257   if (node->balance == 1) {
258     avl_rotate_left(tree, parent);
259     return;
260   }
261
262   avl_rotate_right(tree, node);
263   avl_rotate_left(tree, node->parent->parent);
264 }
265
266 static void
267 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node,
268                   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,
285                  struct avl_node *node)
286 {
287   if (pos_node->next != NULL)
288     pos_node->next->prev = node;
289   else
290     tree->last = node;
291
292   node->prev = pos_node;
293   node->next = pos_node->next;
294
295   pos_node->next = node;
296
297   tree->count++;
298 }
299
300 static void
301 avl_remove(struct avl_tree *tree, struct avl_node *node)
302 {
303   if (node->prev != NULL)
304     node->prev->next = node->next;
305   else
306     tree->first = node->next;
307
308   if (node->next != NULL)
309     node->next->prev = node->prev;
310   else
311     tree->last = node->prev;
312
313   tree->count--;
314 }
315
316 int
317 avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
318 {
319   struct avl_node *node;
320   struct avl_node *last;
321   int diff;
322
323   new->parent = NULL;
324
325   new->left = NULL;
326   new->right = NULL;
327
328   new->next = NULL;
329   new->prev = NULL;
330
331   new->balance = 0;
332   new->leader = 1;
333
334   if (tree->root == NULL) {
335     tree->root = new;
336     tree->first = new;
337     tree->last = new;
338     tree->count = 1;
339     return 0;
340   }
341
342   node = avl_find_rec(tree->root, new->key, tree->comp);
343
344   last = node;
345
346   while (last->next != NULL && last->next->leader == 0)
347     last = last->next;
348
349   if (NULL == tree->comp)
350     diff = ip4cmp(new->key, node->key);
351
352   else
353     diff = (*tree->comp) (new->key, node->key);
354
355   if (diff == 0) {
356     if (allow_duplicates == AVL_DUP_NO)
357       return -1;
358
359     new->leader = 0;
360
361     avl_insert_after(tree, last, new);
362     return 0;
363   }
364
365   if (node->balance == 1) {
366     avl_insert_before(tree, node, new);
367
368     node->balance = 0;
369     new->parent = node;
370     node->left = new;
371     return 0;
372   }
373
374   if (node->balance == -1) {
375     avl_insert_after(tree, last, new);
376
377     node->balance = 0;
378     new->parent = node;
379     node->right = new;
380     return 0;
381   }
382
383   if (diff < 0) {
384     avl_insert_before(tree, node, new);
385
386     node->balance = -1;
387     new->parent = node;
388     node->left = new;
389     post_insert(tree, node);
390     return 0;
391   }
392
393   avl_insert_after(tree, last, new);
394
395   node->balance = 1;
396   new->parent = node;
397   node->right = new;
398   post_insert(tree, node);
399   return 0;
400 }
401
402 static void
403 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
404 {
405   struct avl_node *parent;
406
407   if ((parent = node->parent) == NULL)
408     return;
409
410   if (node == parent->left) {
411     parent->balance++;
412
413     if (parent->balance == 0) {
414       avl_post_delete(tree, parent);
415       return;
416     }
417
418     if (parent->balance == 1)
419       return;
420
421     if (parent->right->balance == 0) {
422       avl_rotate_left(tree, parent);
423       return;
424     }
425
426     if (parent->right->balance == 1) {
427       avl_rotate_left(tree, parent);
428       avl_post_delete(tree, parent->parent);
429       return;
430     }
431
432     avl_rotate_right(tree, parent->right);
433     avl_rotate_left(tree, parent);
434     avl_post_delete(tree, parent->parent);
435     return;
436   }
437
438   parent->balance--;
439
440   if (parent->balance == 0) {
441     avl_post_delete(tree, parent);
442     return;
443   }
444
445   if (parent->balance == -1)
446     return;
447
448   if (parent->left->balance == 0) {
449     avl_rotate_right(tree, parent);
450     return;
451   }
452
453   if (parent->left->balance == -1) {
454     avl_rotate_right(tree, parent);
455     avl_post_delete(tree, parent->parent);
456     return;
457   }
458
459   avl_rotate_left(tree, parent->left);
460   avl_rotate_right(tree, parent);
461   avl_post_delete(tree, parent->parent);
462 }
463
464 static struct avl_node *
465 avl_local_min(struct avl_node *node)
466 {
467   while (node->left != NULL)
468     node = node->left;
469
470   return node;
471 }
472
473 #if 0
474 static struct avl_node *
475 avl_local_max(struct avl_node *node)
476 {
477   while (node->right != NULL)
478     node = node->right;
479
480   return node;
481 }
482 #endif
483
484 static void
485 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
486 {
487   struct avl_node *parent, *min;
488
489   parent = node->parent;
490
491   if (node->left == NULL && node->right == NULL) {
492     if (parent == NULL) {
493       tree->root = NULL;
494       return;
495     }
496
497     if (parent->left == node) {
498       parent->left = NULL;
499       parent->balance++;
500
501       if (parent->balance == 1)
502         return;
503
504       if (parent->balance == 0) {
505         avl_post_delete(tree, parent);
506         return;
507       }
508
509       if (parent->right->balance == 0) {
510         avl_rotate_left(tree, parent);
511         return;
512       }
513
514       if (parent->right->balance == 1) {
515         avl_rotate_left(tree, parent);
516         avl_post_delete(tree, parent->parent);
517         return;
518       }
519
520       avl_rotate_right(tree, parent->right);
521       avl_rotate_left(tree, parent);
522       avl_post_delete(tree, parent->parent);
523       return;
524     }
525
526     if (parent->right == node) {
527       parent->right = NULL;
528       parent->balance--;
529
530       if (parent->balance == -1)
531         return;
532
533       if (parent->balance == 0) {
534         avl_post_delete(tree, parent);
535         return;
536       }
537
538       if (parent->left->balance == 0) {
539         avl_rotate_right(tree, parent);
540         return;
541       }
542
543       if (parent->left->balance == -1) {
544         avl_rotate_right(tree, parent);
545         avl_post_delete(tree, parent->parent);
546         return;
547       }
548
549       avl_rotate_left(tree, parent->left);
550       avl_rotate_right(tree, parent);
551       avl_post_delete(tree, parent->parent);
552       return;
553     }
554   }
555
556   if (node->left == NULL) {
557     if (parent == NULL) {
558       tree->root = node->right;
559       node->right->parent = NULL;
560       return;
561     }
562
563     node->right->parent = parent;
564
565     if (parent->left == node)
566       parent->left = node->right;
567
568     else
569       parent->right = node->right;
570
571     avl_post_delete(tree, node->right);
572     return;
573   }
574
575   if (node->right == NULL) {
576     if (parent == NULL) {
577       tree->root = node->left;
578       node->left->parent = NULL;
579       return;
580     }
581
582     node->left->parent = parent;
583
584     if (parent->left == node)
585       parent->left = node->left;
586
587     else
588       parent->right = node->left;
589
590     avl_post_delete(tree, node->left);
591     return;
592   }
593
594   min = avl_local_min(node->right);
595   avl_delete_worker(tree, min);
596   parent = node->parent;
597
598   min->balance = node->balance;
599   min->parent = parent;
600   min->left = node->left;
601   min->right = node->right;
602
603   if (min->left != NULL)
604     min->left->parent = min;
605
606   if (min->right != NULL)
607     min->right->parent = min;
608
609   if (parent == NULL) {
610     tree->root = min;
611     return;
612   }
613
614   if (parent->left == node) {
615     parent->left = min;
616     return;
617   }
618
619   parent->right = min;
620 }
621
622 void
623 avl_delete(struct avl_tree *tree, struct avl_node *node)
624 {
625   struct avl_node *next;
626   struct avl_node *parent;
627   struct avl_node *left;
628   struct avl_node *right;
629
630   if (node->leader != 0) {
631     next = node->next;
632
633     if (next != NULL && next->leader == 0) {
634       next->leader = 1;
635       next->balance = node->balance;
636
637       parent = node->parent;
638       left = node->left;
639       right = node->right;
640
641       next->parent = parent;
642       next->left = left;
643       next->right = right;
644
645       if (parent == NULL)
646         tree->root = next;
647
648       else {
649         if (node == parent->left)
650           parent->left = next;
651
652         else
653           parent->right = next;
654       }
655
656       if (left != NULL)
657         left->parent = next;
658
659       if (right != NULL)
660         right->parent = next;
661     }
662
663     else
664       avl_delete_worker(tree, node);
665   }
666
667   avl_remove(tree, node);
668 }
669
670 /*
671  * Local Variables:
672  * c-basic-offset: 2
673  * End:
674  */