* applied patches from the most recent FreiFunkFirmware (and fixed compile errors...
[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  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  * $Id: lq_avl.c,v 1.2 2007/01/31 12:36:50 bernd67 Exp $
40  */
41
42 #include <stddef.h>
43 #ifndef DISABLE_SVEN_OLA
44 #include <time.h>
45 #endif
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 void avl_init(struct avl_tree *tree, int (*comp)(void *, void *))
53 {
54   tree->root = NULL;
55   tree->comp = comp;
56 }
57
58 #ifndef DISABLE_SVEN_OLA
59 static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
60 {
61   if (*(unsigned int *)key < *(unsigned int *)node->key) {
62     if (node->left != NULL) {
63       return avl_find_rec_ipv4(node->left, key);
64     }
65   }
66   else if (*(unsigned int *)key > *(unsigned int *)node->key) {
67     if (node->right != NULL) {
68       return avl_find_rec_ipv4(node->right, key);
69     }
70   }
71   return node;
72 }
73 #endif
74
75 static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
76                                      int (*comp)(void *, void *))
77 {
78   int diff;
79
80 #ifndef DISABLE_SVEN_OLA
81   if (0 == comp) {
82     return avl_find_rec_ipv4(node, key);
83   }
84 #endif
85   diff = (*comp)(key, node->key);
86
87   if (diff < 0)
88   {
89     if (node->left != NULL)
90       return avl_find_rec(node->left, key, comp);
91
92     return node;
93   }
94
95   if (diff > 0)
96   {
97     if (node->right != NULL)
98       return avl_find_rec(node->right, key, comp);
99
100     return node;
101   }
102
103   return node;
104 }
105
106 struct avl_node *avl_find(struct avl_tree *tree, void *key)
107 {
108   struct avl_node *node;
109
110   if (tree->root == NULL)
111     return NULL;
112
113   node = avl_find_rec(tree->root, key, tree->comp);
114
115 #ifndef DISABLE_SVEN_OLA
116   if (0 == tree->comp) {
117     if (0 != svenola_avl_comp_ipv4(node->key, key))
118       return NULL;
119   }
120   else
121 #endif
122   if ((*tree->comp)(node->key, key) != 0)
123     return NULL;
124
125   return node;
126 }
127
128 static void rotate_right(struct avl_tree *tree, struct avl_node *node)
129 {
130   struct avl_node *left, *parent;
131
132   left = node->left;
133   parent = node->parent;
134
135   left->parent = parent;
136   node->parent = left;
137
138   if (parent == NULL)
139     tree->root = left;
140
141   else
142   {
143     if (parent->left == node)
144       parent->left = left;
145
146     else
147       parent->right = left;
148   }
149
150   node->left = left->right;
151   left->right = node;
152
153   if (node->left != NULL)
154     node->left->parent = node;
155
156   node->balance += 1 - AVLMIN(left->balance, 0);
157   left->balance += 1 + AVLMAX(node->balance, 0);
158 }
159
160 static void rotate_left(struct avl_tree *tree, struct avl_node *node)
161 {
162   struct avl_node *right, *parent;
163
164   right = node->right;
165   parent = node->parent;
166
167   right->parent = parent;
168   node->parent = right;
169
170   if (parent == NULL)
171     tree->root = right;
172
173   else
174   {
175     if (parent->left == node)
176       parent->left = right;
177
178     else
179       parent->right = right;
180   }
181
182   node->right = right->left;
183   right->left = node;
184
185   if (node->right != NULL)
186     node->right->parent = node;
187
188   node->balance -= 1 + AVLMAX(right->balance, 0);
189   right->balance -= 1 - AVLMIN(node->balance, 0);
190 }
191
192 static void post_insert(struct avl_tree *tree, struct avl_node *node)
193 {
194   struct avl_node *parent;
195
196   if ((parent = node->parent) == NULL)
197     return;
198
199   if (node == parent->left)
200   {
201     parent->balance--;
202
203     if (parent->balance == 0)
204       return;
205
206     if (parent->balance == -1)
207     {
208       post_insert(tree, parent);
209       return;
210     }
211
212     if (node->balance == -1)
213     {
214       rotate_right(tree, parent);
215       return;
216     }
217
218     rotate_left(tree, node);
219     rotate_right(tree, node->parent->parent);
220     return;
221   }
222
223   parent->balance++;
224
225   if (parent->balance == 0)
226     return;
227
228   if (parent->balance == 1)
229   {
230     post_insert(tree, parent);
231     return;
232   }
233
234   if (node->balance == 1)
235   {
236     rotate_left(tree, parent);
237     return;
238   }
239
240   rotate_right(tree, node);
241   rotate_left(tree, node->parent->parent);
242   return;
243 }
244
245 int avl_insert(struct avl_tree *tree, struct avl_node *new)
246 {
247   struct avl_node *node;
248   int diff;
249
250   new->balance = 0;
251   new->left = NULL;
252   new->right = NULL;
253
254   if (tree->root == NULL)
255   {
256     new->parent = NULL;
257     tree->root = new;
258     return 0;
259   }
260
261   node = avl_find_rec(tree->root, new->key, tree->comp);
262
263 #ifndef DISABLE_SVEN_OLA
264   if (0 == tree->comp) {
265     diff = svenola_avl_comp_ipv4(new->key, node->key);
266   }
267   else
268 #endif
269   diff = (*tree->comp)(new->key, node->key);
270
271   if (diff == 0)
272     return -1;
273
274   if (node->balance == 1)
275   {
276     node->balance = 0;
277     new->parent = node;
278     node->left = new;
279     return 0;
280   }
281   
282   if (node->balance == -1)
283   {
284     node->balance = 0;
285     new->parent = node;
286     node->right = new;
287     return 0;
288   }
289
290   if (diff < 0)
291   {
292     node->balance = -1;
293     new->parent = node;
294     node->left = new;
295     post_insert(tree, node);
296     return 0;
297   }
298
299   node->balance = 1;
300   new->parent = node;
301   node->right = new;
302   post_insert(tree, node);
303   return 0;
304 }