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