Modify linked list when inserting a node into or removing a node from the
[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.6 2007/03/27 19:37:13 tlopatic 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)
276 {
277   struct avl_node *node;
278   int diff;
279
280   new->balance = 0;
281   new->left = NULL;
282   new->right = NULL;
283
284   new->next = NULL;
285   new->prev = NULL;
286
287   if (tree->root == NULL)
288   {
289     new->parent = NULL;
290     tree->root = new;
291     return 0;
292   }
293
294   node = find_rec(tree->root, new->key, tree->comp);
295
296   if (0 == tree->comp)
297     diff = inline_avl_comp_ipv4(new->key, node->key);
298
299   else
300     diff = (*tree->comp)(new->key, node->key);
301
302   if (diff == 0)
303     return -1;
304
305   if (node->balance == 1)
306   {
307     insert_before(node, new);
308
309     node->balance = 0;
310     new->parent = node;
311     node->left = new;
312     return 0;
313   }
314   
315   if (node->balance == -1)
316   {
317     insert_after(node, new);
318
319     node->balance = 0;
320     new->parent = node;
321     node->right = new;
322     return 0;
323   }
324
325   if (diff < 0)
326   {
327     insert_before(node, new);
328
329     node->balance = -1;
330     new->parent = node;
331     node->left = new;
332     post_insert(tree, node);
333     return 0;
334   }
335
336   insert_after(node, new);
337
338   node->balance = 1;
339   new->parent = node;
340   node->right = new;
341   post_insert(tree, node);
342   return 0;
343 }
344
345 static void post_delete(struct avl_tree *tree, struct avl_node *node)
346 {
347   struct avl_node *parent;
348
349   if ((parent = node->parent) == NULL)
350     return;
351
352   if (node == parent->left)
353   {
354     parent->balance++;
355
356     if (parent->balance == 0)
357     {
358       post_delete(tree, parent);
359       return;
360     }
361     
362     if (parent->balance == 1)
363       return;
364
365     if (parent->right->balance == 0)
366     {
367       rotate_left(tree, parent);
368       return;
369     }
370
371     if (parent->right->balance == 1)
372     {
373       rotate_left(tree, parent);
374       post_delete(tree, parent->parent);
375       return;
376     }
377
378     rotate_right(tree, parent->right);
379     rotate_left(tree, parent);
380     post_delete(tree, parent->parent);
381     return;
382   }
383
384   parent->balance--;
385
386   if (parent->balance == 0)
387   {
388     post_delete(tree, parent);
389     return;
390   }
391     
392   if (parent->balance == -1)
393     return;
394
395   if (parent->left->balance == 0)
396   {
397     rotate_right(tree, parent);
398     return;
399   }
400
401   if (parent->left->balance == -1)
402   {
403     rotate_right(tree, parent);
404     post_delete(tree, parent->parent);
405     return;
406   }
407
408   rotate_left(tree, parent->left);
409   rotate_right(tree, parent);
410   post_delete(tree, parent->parent);
411 }
412
413 static struct avl_node *local_min(struct avl_node *node)
414 {
415   if (node->left == NULL)
416     return node;
417
418   return local_min(node->left);
419 }
420
421 static void delete_worker(struct avl_tree *tree, struct avl_node *node)
422 {
423   struct avl_node *parent, *min;
424
425   parent = node->parent;
426
427   if (node->left == NULL && node->right == NULL)
428   {
429     if (parent == NULL)
430     {
431       tree->root = NULL;
432       return;
433     }
434
435     if (parent->left == node)
436     {
437       parent->left = NULL;
438       parent->balance++;
439
440       if (parent->balance == 1)
441         return;
442
443       if (parent->balance == 0)
444       {
445         post_delete(tree, parent);
446         return;
447       }
448
449       if (parent->right->balance == 0)
450       {
451         rotate_left(tree, parent);
452         return;
453       }
454       
455       if (parent->right->balance == 1)
456       {
457         rotate_left(tree, parent);
458         post_delete(tree, parent->parent);
459         return;
460       }
461
462       rotate_right(tree, parent->right);
463       rotate_left(tree, parent);
464       post_delete(tree, parent->parent);
465       return;
466     }
467
468     if (parent->right == node)
469     {
470       parent->right = NULL;
471       parent->balance--;
472
473       if (parent->balance == -1)
474         return;
475
476       if (parent->balance == 0)
477       {
478         post_delete(tree, parent);
479         return;
480       }
481
482       if (parent->left->balance == 0)
483       {
484         rotate_right(tree, parent);
485         return;
486       }
487       
488       if (parent->left->balance == -1)
489       {
490         rotate_right(tree, parent);
491         post_delete(tree, parent->parent);
492         return;
493       }
494
495       rotate_left(tree, parent->left);
496       rotate_right(tree, parent);
497       post_delete(tree, parent->parent);
498       return;
499     }
500   }
501
502   if (node->left == NULL)
503   {
504     if (parent == NULL)
505     {
506       tree->root = node->right;
507       node->right->parent = NULL;
508       return;
509     }
510
511     node->right->parent = parent;
512
513     if (parent->left == node)
514       parent->left = node->right;
515     
516     else
517       parent->right = node->right;
518
519     post_delete(tree, node->right);
520     return;
521   }
522
523   if (node->right == NULL)
524   {
525     if (parent == NULL)
526     {
527       tree->root = node->left;
528       node->left->parent = NULL;
529       return;
530     }
531
532     node->left->parent = parent;
533
534     if (parent->left == node)
535       parent->left = node->left;
536
537     else
538       parent->right = node->left;
539
540     post_delete(tree, node->left);
541     return;
542   }
543
544   min = local_min(node->right);
545   delete_worker(tree, min);
546   parent = node->parent;
547
548   min->balance = node->balance;
549   min->parent = parent;
550   min->left = node->left;
551   min->right = node->right;
552
553   if (min->left != NULL)
554     min->left->parent = min;
555
556   if (min->right != NULL)
557     min->right->parent = min;
558     
559   if (parent == NULL)
560   {
561     tree->root = min;
562     return;
563   }
564
565   if (parent->left == node)
566   {
567     parent->left = min;
568     return;
569   }
570
571   parent->right = min;
572 }
573
574 void avl_delete(struct avl_tree *tree, struct avl_node *node)
575 {
576   delete_worker(tree, node);
577   remove(node);
578
579   node->balance = 0xdeadbeef;
580
581   node->left = (struct avl_node *)0xdeadbeef;
582   node->right = (struct avl_node *)0xdeadbeef;
583
584   node->key = (void *)0xdeadbeef;
585
586   node->data = (void *)0xdeadbeef;
587 }
588
589 struct avl_node *avl_walk_first(struct avl_tree *tree)
590 {
591   struct avl_node *node = tree->root;
592
593   if (node == NULL)
594     return NULL;
595
596   return local_min(node);
597 }
598
599 struct avl_node *avl_walk_next(struct avl_node *node)
600 {
601   return node->next;
602 }