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