added the SPF refactoring from Hannes Gredler <hannes@gredler.at>:
[olsrd.git] / src / lq_avl.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
4  * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
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 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  * $Id: lq_avl.c,v 1.10 2007/07/05 22:43:46 bernd67 Exp $
41  */
42
43 #include <stddef.h>
44 #include <time.h>
45 #include <string.h>
46
47 #include "lq_avl.h"
48
49 #define AVLMAX(x, y) ((x > y) ? x : y)
50 #define AVLMIN(x, y) ((x < y) ? x : y)
51
52 /*
53  * dummy comparison pointer
54  * set to zero for a fast inline ipv4 comparison
55  */
56 int (*avl_comp_default)(void *, void *) = 0;
57
58 int avl_comp_ipv4(void *ip1, void *ip2)
59 {
60     return(*(unsigned int *)ip1 == *(unsigned int *)ip2 ? 0 : \
61            *(unsigned int *)ip1 < *(unsigned int *)ip2 ? -1 : +1);
62 }
63
64 int avl_comp_ipv6(void *ip1, void *ip2)
65 {
66   return memcmp(ip1, ip2, 16);
67 }
68
69 void avl_init(struct avl_tree *tree, int (*comp)(void *, void *))
70 {
71   tree->root = NULL;
72   tree->comp = comp;
73 }
74
75 static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
76 {
77   if (*(unsigned int *)key < *(unsigned int *)node->key)
78   {
79     if (node->left != NULL)
80       return avl_find_rec_ipv4(node->left, key);
81   }
82
83   else if (*(unsigned int *)key > *(unsigned int *)node->key)
84   {
85     if (node->right != NULL)
86       return avl_find_rec_ipv4(node->right, key);
87   }
88
89   return node;
90 }
91
92 static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
93                                      int (*comp)(void *, void *))
94 {
95   int diff;
96
97   if (0 == comp)
98     return avl_find_rec_ipv4(node, key);
99
100   diff = (*comp)(key, node->key);
101
102   if (diff < 0)
103   {
104     if (node->left != NULL)
105       return avl_find_rec(node->left, key, comp);
106
107     return node;
108   }
109
110   if (diff > 0)
111   {
112     if (node->right != NULL)
113       return avl_find_rec(node->right, key, comp);
114
115     return node;
116   }
117
118   return node;
119 }
120
121 struct avl_node *avl_find(struct avl_tree *tree, void *key)
122 {
123   struct avl_node *node;
124
125   if (tree->root == NULL)
126     return NULL;
127
128   node = avl_find_rec(tree->root, key, tree->comp);
129
130   if (0 == tree->comp)
131   {
132     if (0 != inline_avl_comp_ipv4(node->key, key))
133       return NULL;
134   }
135
136   else
137   {
138     if ((*tree->comp)(node->key, key) != 0)
139       return NULL;
140   }
141
142   return node;
143 }
144
145 static void avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
146 {
147   struct avl_node *left, *parent;
148
149   left = node->left;
150   parent = node->parent;
151
152   left->parent = parent;
153   node->parent = left;
154
155   if (parent == NULL)
156     tree->root = left;
157
158   else
159   {
160     if (parent->left == node)
161       parent->left = left;
162
163     else
164       parent->right = left;
165   }
166
167   node->left = left->right;
168   left->right = node;
169
170   if (node->left != NULL)
171     node->left->parent = node;
172
173   node->balance += 1 - AVLMIN(left->balance, 0);
174   left->balance += 1 + AVLMAX(node->balance, 0);
175 }
176
177 static void avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
178 {
179   struct avl_node *right, *parent;
180
181   right = node->right;
182   parent = node->parent;
183
184   right->parent = parent;
185   node->parent = right;
186
187   if (parent == NULL)
188     tree->root = right;
189
190   else
191   {
192     if (parent->left == node)
193       parent->left = right;
194
195     else
196       parent->right = right;
197   }
198
199   node->right = right->left;
200   right->left = node;
201
202   if (node->right != NULL)
203     node->right->parent = node;
204
205   node->balance -= 1 + AVLMAX(right->balance, 0);
206   right->balance -= 1 - AVLMIN(node->balance, 0);
207 }
208
209 static void post_insert(struct avl_tree *tree, struct avl_node *node)
210 {
211   struct avl_node *parent;
212
213   if ((parent = node->parent) == NULL)
214     return;
215
216   if (node == parent->left)
217   {
218     parent->balance--;
219
220     if (parent->balance == 0)
221       return;
222
223     if (parent->balance == -1)
224     {
225       post_insert(tree, parent);
226       return;
227     }
228
229     if (node->balance == -1)
230     {
231       avl_rotate_right(tree, parent);
232       return;
233     }
234
235     avl_rotate_left(tree, node);
236     avl_rotate_right(tree, node->parent->parent);
237     return;
238   }
239
240   parent->balance++;
241
242   if (parent->balance == 0)
243     return;
244
245   if (parent->balance == 1)
246   {
247     post_insert(tree, parent);
248     return;
249   }
250
251   if (node->balance == 1)
252   {
253     avl_rotate_left(tree, parent);
254     return;
255   }
256
257   avl_rotate_right(tree, node);
258   avl_rotate_left(tree, node->parent->parent);
259   return;
260 }
261
262 static void avl_insert_before(struct avl_node *pos_node, struct avl_node *node)
263 {
264   if (pos_node->prev != NULL)
265     pos_node->prev->next = node;
266
267   node->prev = pos_node->prev;
268   node->next = pos_node;
269
270   pos_node->prev = node;
271 }
272
273 static void avl_insert_after(struct avl_node *pos_node, struct avl_node *node)
274 {
275   if (pos_node->next != NULL)
276     pos_node->next->prev = node;
277
278   node->prev = pos_node;
279   node->next = pos_node->next;
280
281   pos_node->next = node;
282 }
283
284 static void avl_remove(struct avl_node *node)
285 {
286   if (node->prev != NULL)
287     node->prev->next = node->next;
288
289   if (node->next != NULL)
290     node->next->prev = node->prev;
291 }
292
293 int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
294 {
295   struct avl_node *node;
296   struct avl_node *last;
297   int diff;
298
299   new->parent = NULL;
300
301   new->left = NULL;
302   new->right = NULL;
303
304   new->next = NULL;
305   new->prev = NULL;
306
307   new->balance = 0;
308   new->leader = 1;
309
310   if (tree->root == NULL)
311   {
312     tree->root = new;
313     return 0;
314   }
315
316   node = avl_find_rec(tree->root, new->key, tree->comp);
317
318   last = node;
319
320   while (last->next != NULL && last->next->leader == 0)
321     last = last->next;
322
323   if (0 == tree->comp)
324     diff = inline_avl_comp_ipv4(new->key, node->key);
325
326   else
327     diff = (*tree->comp)(new->key, node->key);
328
329   if (diff == 0)
330   {
331     if (allow_duplicates == 0)
332       return -1;
333
334     new->leader = 0;
335
336     avl_insert_after(last, new);
337     return 0;
338   }
339
340   if (node->balance == 1)
341   {
342     avl_insert_before(node, new);
343
344     node->balance = 0;
345     new->parent = node;
346     node->left = new;
347     return 0;
348   }
349   
350   if (node->balance == -1)
351   {
352     avl_insert_after(last, new);
353
354     node->balance = 0;
355     new->parent = node;
356     node->right = new;
357     return 0;
358   }
359
360   if (diff < 0)
361   {
362     avl_insert_before(node, new);
363
364     node->balance = -1;
365     new->parent = node;
366     node->left = new;
367     post_insert(tree, node);
368     return 0;
369   }
370
371   avl_insert_after(last, new);
372
373   node->balance = 1;
374   new->parent = node;
375   node->right = new;
376   post_insert(tree, node);
377   return 0;
378 }
379
380 static void avl_post_delete(struct avl_tree *tree, struct avl_node *node)
381 {
382   struct avl_node *parent;
383
384   if ((parent = node->parent) == NULL)
385     return;
386
387   if (node == parent->left)
388   {
389     parent->balance++;
390
391     if (parent->balance == 0)
392     {
393       avl_post_delete(tree, parent);
394       return;
395     }
396     
397     if (parent->balance == 1)
398       return;
399
400     if (parent->right->balance == 0)
401     {
402       avl_rotate_left(tree, parent);
403       return;
404     }
405
406     if (parent->right->balance == 1)
407     {
408       avl_rotate_left(tree, parent);
409       avl_post_delete(tree, parent->parent);
410       return;
411     }
412
413     avl_rotate_right(tree, parent->right);
414     avl_rotate_left(tree, parent);
415     avl_post_delete(tree, parent->parent);
416     return;
417   }
418
419   parent->balance--;
420
421   if (parent->balance == 0)
422   {
423     avl_post_delete(tree, parent);
424     return;
425   }
426     
427   if (parent->balance == -1)
428     return;
429
430   if (parent->left->balance == 0)
431   {
432     avl_rotate_right(tree, parent);
433     return;
434   }
435
436   if (parent->left->balance == -1)
437   {
438     avl_rotate_right(tree, parent);
439     avl_post_delete(tree, parent->parent);
440     return;
441   }
442
443   avl_rotate_left(tree, parent->left);
444   avl_rotate_right(tree, parent);
445   avl_post_delete(tree, parent->parent);
446 }
447
448 static struct avl_node *avl_local_min(struct avl_node *node)
449 {
450   while (node->left != NULL)
451     node = node->left;
452
453   return node;
454 }
455
456 static struct avl_node *avl_local_max(struct avl_node *node)
457 {
458   while (node->right != NULL)
459     node = node->right;
460
461   return node;
462 }
463
464 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
465 {
466   struct avl_node *parent, *min;
467
468   parent = node->parent;
469
470   if (node->left == NULL && node->right == NULL)
471   {
472     if (parent == NULL)
473     {
474       tree->root = NULL;
475       return;
476     }
477
478     if (parent->left == node)
479     {
480       parent->left = NULL;
481       parent->balance++;
482
483       if (parent->balance == 1)
484         return;
485
486       if (parent->balance == 0)
487       {
488         avl_post_delete(tree, parent);
489         return;
490       }
491
492       if (parent->right->balance == 0)
493       {
494         avl_rotate_left(tree, parent);
495         return;
496       }
497       
498       if (parent->right->balance == 1)
499       {
500         avl_rotate_left(tree, parent);
501         avl_post_delete(tree, parent->parent);
502         return;
503       }
504
505       avl_rotate_right(tree, parent->right);
506       avl_rotate_left(tree, parent);
507       avl_post_delete(tree, parent->parent);
508       return;
509     }
510
511     if (parent->right == node)
512     {
513       parent->right = NULL;
514       parent->balance--;
515
516       if (parent->balance == -1)
517         return;
518
519       if (parent->balance == 0)
520       {
521         avl_post_delete(tree, parent);
522         return;
523       }
524
525       if (parent->left->balance == 0)
526       {
527         avl_rotate_right(tree, parent);
528         return;
529       }
530       
531       if (parent->left->balance == -1)
532       {
533         avl_rotate_right(tree, parent);
534         avl_post_delete(tree, parent->parent);
535         return;
536       }
537
538       avl_rotate_left(tree, parent->left);
539       avl_rotate_right(tree, parent);
540       avl_post_delete(tree, parent->parent);
541       return;
542     }
543   }
544
545   if (node->left == NULL)
546   {
547     if (parent == NULL)
548     {
549       tree->root = node->right;
550       node->right->parent = NULL;
551       return;
552     }
553
554     node->right->parent = parent;
555
556     if (parent->left == node)
557       parent->left = node->right;
558     
559     else
560       parent->right = node->right;
561
562     avl_post_delete(tree, node->right);
563     return;
564   }
565
566   if (node->right == NULL)
567   {
568     if (parent == NULL)
569     {
570       tree->root = node->left;
571       node->left->parent = NULL;
572       return;
573     }
574
575     node->left->parent = parent;
576
577     if (parent->left == node)
578       parent->left = node->left;
579
580     else
581       parent->right = node->left;
582
583     avl_post_delete(tree, node->left);
584     return;
585   }
586
587   min = avl_local_min(node->right);
588   avl_delete_worker(tree, min);
589   parent = node->parent;
590
591   min->balance = node->balance;
592   min->parent = parent;
593   min->left = node->left;
594   min->right = node->right;
595
596   if (min->left != NULL)
597     min->left->parent = min;
598
599   if (min->right != NULL)
600     min->right->parent = min;
601     
602   if (parent == NULL)
603   {
604     tree->root = min;
605     return;
606   }
607
608   if (parent->left == node)
609   {
610     parent->left = min;
611     return;
612   }
613
614   parent->right = min;
615 }
616
617 void avl_delete(struct avl_tree *tree, struct avl_node *node)
618 {
619   struct avl_node *next;
620   struct avl_node *parent;
621   struct avl_node *left;
622   struct avl_node *right;
623
624   if (node->leader != 0)
625   {
626     next = node->next;
627
628     if (next != NULL && next->leader == 0)
629     {
630       next->leader = 1;
631       next->balance = node->balance;
632
633       parent = node->parent;
634       left = node->left;
635       right = node->right;
636
637       next->parent = parent;
638       next->left = left;
639       next->right = right;
640
641       if (parent == NULL)
642         tree->root = next;
643
644       else
645       {
646         if (node == parent->left)
647           parent->left = next;
648
649         else
650           parent->right = next;
651       }
652
653       if (left != NULL)
654         left->parent = next;
655
656       if (right != NULL)
657         right->parent = next;
658     }
659
660     else
661       avl_delete_worker(tree, node);
662   }
663
664   avl_remove(node);
665 }
666
667 struct avl_node *avl_walk_first(struct avl_tree *tree)
668 {
669   struct avl_node *node = tree->root;
670
671   if (node == NULL)
672     return NULL;
673
674   return avl_local_min(node);
675 }
676
677 struct avl_node *avl_walk_last(struct avl_tree *tree)
678 {
679   struct avl_node *node = tree->root;
680
681   if (node == NULL)
682     return NULL;
683
684   return avl_local_max(node);
685 }
686
687 struct avl_node *avl_walk_next(struct avl_node *node)
688 {
689   return node->next;
690 }
691
692 struct avl_node *avl_walk_prev(struct avl_node *node)
693 {
694   return node->prev;
695 }
696
697 /*
698  * Local Variables:
699  * c-basic-offset: 2
700  * End:
701  */