projects / feed / routing.git / blob
? search:


c1d97432f6e319ee557f79aaad6118cfa6b42714
[feed/routing.git] / olsrd / patches / 100-rename-avl-to-olsrd_avl.patch
1 From 4b91b102eb6edb63472728dd3545e3dff800a5a0 Mon Sep 17 00:00:00 2001
2 From: Nick Hainke <vincent@systemli.org>
3 Date: Sat, 15 Jan 2022 16:13:24 +0100
4 Subject: [PATCH] rename avl to olsrd_avl
5
6 ---
7 lib/nameservice/src/nameservice.c | 4 +-
8 lib/netjson/src/olsrd_netjson.c | 12 +-
9 lib/netjson/src/olsrd_netjson_helpers.c | 74 +++++-----
10 lib/netjson/src/olsrd_netjson_helpers.h | 18 +--
11 src/common/{avl.c => olsrd_avl.c} | 184 ++++++++++++------------
12 src/common/{avl.h => olsrd_avl.h} | 90 ++++++------
13 src/duplicate_set.c | 18 +--
14 src/duplicate_set.h | 12 +-
15 src/gateway.c | 18 +--
16 src/gateway.h | 16 +--
17 src/kernel_tunnel.h | 4 +-
18 src/linux/kernel_tunnel.c | 12 +-
19 src/lq_packet.c | 6 +-
20 src/lq_plugin.c | 14 +-
21 src/lq_plugin.h | 14 +-
22 src/olsr.c | 12 +-
23 src/olsr_spf.c | 36 ++---
24 src/process_routes.c | 22 +--
25 src/routing_table.c | 56 ++++----
26 src/routing_table.h | 36 ++---
27 src/scheduler.c | 30 ++--
28 src/tc_set.c | 30 ++--
29 src/tc_set.h | 38 ++---
30 24 files changed, 390 insertions(+), 390 deletions(-)
31 rename src/common/{avl.c => olsrd_avl.c} (67%)
32 rename src/common/{avl.h => olsrd_avl.h} (58%)
33 --- a/lib/nameservice/src/nameservice.c
34 +++ b/lib/nameservice/src/nameservice.c
35 @@ -1621,13 +1621,13 @@ void
36 lookup_defhna_latlon(union olsr_ip_addr *ip)
37 {
38 struct rt_entry *rt;
39 - struct avl_node *rt_tree_node;
40 + struct olsrd_avl_node *rt_tree_node;
41 struct olsr_ip_prefix prefix;
42
43 memset(ip, 0, sizeof(*ip));
44 memset(&prefix, 0, sizeof(prefix));
45
46 - if (NULL != (rt_tree_node = avl_find(&routingtree, &prefix))) {
47 + if (NULL != (rt_tree_node = olsrd_avl_find(&routingtree, &prefix))) {
48 rt = rt_tree2rt(rt_tree_node);
49 *ip = rt->rt_best->rtp_nexthop.gateway;
50 }
51 --- a/lib/netjson/src/olsrd_netjson.c
52 +++ b/lib/netjson/src/olsrd_netjson.c
53 @@ -52,7 +52,7 @@
54 #include "info/info_types.h"
55 #include "info/http_headers.h"
56 #include "info/json_helpers.h"
57 -#include "common/avl.h"
58 +#include "common/olsrd_avl.h"
59 #include "olsr.h"
60 #include "builddata.h"
61 #include "routing_table.h"
62 @@ -161,7 +161,7 @@ void ipc_print_network_routes(struct aut
63 }
64
65 void ipc_print_network_graph(struct autobuf *abuf) {
66 - struct avl_tree nodes;
67 + struct olsrd_avl_tree nodes;
68 struct mid_entry mid_self;
69 struct node_entry * node_self;
70 struct tc_entry * tc;
71 @@ -169,7 +169,7 @@ void ipc_print_network_graph(struct auto
72 struct neighbor_entry * neighbor;
73 int idx;
74
75 - avl_init(&nodes, (olsr_cnf->ip_version == AF_INET) ? avl_comp_ipv4 : avl_comp_ipv6);
76 + olsrd_avl_init(&nodes, (olsr_cnf->ip_version == AF_INET) ? olsrd_avl_comp_ipv4 : olsrd_avl_comp_ipv6);
77
78 /* mandatory */
79 abuf_json_string(&json_session, abuf, "type", "NetworkGraph");
80 @@ -226,8 +226,8 @@ void ipc_print_network_graph(struct auto
81
82 abuf_json_mark_object(&json_session, true, true, abuf, "nodes");
83 while (nodes.count > 0) {
84 - struct avl_node *node = avl_walk_first(&nodes);
85 - struct node_entry *node_entry = avlnode2node(node);
86 + struct olsrd_avl_node *node = olsrd_avl_walk_first(&nodes);
87 + struct node_entry *node_entry = olsrd_avlnode2node(node);
88
89 if (!node_entry->isAlias) {
90 abuf_json_mark_array_entry(&json_session, true, abuf);
91 @@ -265,7 +265,7 @@ void ipc_print_network_graph(struct auto
92 netjson_cleanup_mid_self(node_self);
93 }
94
95 - avl_delete(&nodes, node);
96 + olsrd_avl_delete(&nodes, node);
97 free(node);
98 }
99 abuf_json_mark_object(&json_session, false, true, abuf, NULL);
100 --- a/lib/netjson/src/olsrd_netjson_helpers.c
101 +++ b/lib/netjson/src/olsrd_netjson_helpers.c
102 @@ -57,7 +57,7 @@ struct node_entry * netjson_constructMid
103
104 node_self = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - MID - self");
105 memset(node_self, 0, sizeof(*node_self));
106 - node_self->avl.key = &olsr_cnf->main_addr;
107 + node_self->olsrd_avl.key = &olsr_cnf->main_addr;
108 node_self->isAlias = false;
109 node_self->mid = mid;
110
111 @@ -93,7 +93,7 @@ struct node_entry * netjson_constructMid
112
113 node_self_alias = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - MID - self alias");
114 memset(node_self_alias, 0, sizeof(*node_self_alias));
115 - node_self_alias->avl.key = addr;
116 + node_self_alias->olsrd_avl.key = addr;
117 node_self_alias->isAlias = true;
118 node_self_alias->mid = mid;
119
120 @@ -112,7 +112,7 @@ struct node_entry * netjson_constructMid
121 }
122
123 void netjson_cleanup_mid_self(struct node_entry *node_entry) {
124 - if (node_entry->avl.key != &olsr_cnf->main_addr) {
125 + if (node_entry->olsrd_avl.key != &olsr_cnf->main_addr) {
126 return;
127 }
128
129 @@ -123,21 +123,21 @@ void netjson_cleanup_mid_self(struct nod
130 }
131 }
132
133 -void netjson_midIntoNodesTree(struct avl_tree *nodes, struct mid_entry *mid) {
134 - struct avl_node *avlnode;
135 +void netjson_midIntoNodesTree(struct olsrd_avl_tree *nodes, struct mid_entry *mid) {
136 + struct olsrd_avl_node *olsrd_avlnode;
137 struct node_entry *node;
138 struct mid_address *alias;
139
140 - avlnode = avl_find(nodes, &mid->main_addr);
141 - if (!avlnode) {
142 + olsrd_avlnode = olsrd_avl_find(nodes, &mid->main_addr);
143 + if (!olsrd_avlnode) {
144 /* the IP address is not yet known */
145
146 node = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - MID - main");
147 memset(node, 0, sizeof(*node));
148 - node->avl.key = &mid->main_addr;
149 + node->olsrd_avl.key = &mid->main_addr;
150 node->isAlias = false;
151 node->mid = mid;
152 - if (avl_insert(nodes, &node->avl, AVL_DUP_NO) == -1) {
153 + if (olsrd_avl_insert(nodes, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
154 /* duplicate */
155 free(node);
156 }
157 @@ -145,16 +145,16 @@ void netjson_midIntoNodesTree(struct avl
158
159 alias = mid->aliases;
160 while (alias) {
161 - avlnode = avl_find(nodes, &alias->alias);
162 - if (!avlnode) {
163 + olsrd_avlnode = olsrd_avl_find(nodes, &alias->alias);
164 + if (!olsrd_avlnode) {
165 /* the IP address is not yet known */
166
167 node = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - MID - alias");
168 memset(node, 0, sizeof(*node));
169 - node->avl.key = &alias->alias;
170 + node->olsrd_avl.key = &alias->alias;
171 node->isAlias = true;
172 node->mid = mid;
173 - if (avl_insert(nodes, &node->avl, AVL_DUP_NO) == -1) {
174 + if (olsrd_avl_insert(nodes, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
175 /* duplicate */
176 free(node);
177 }
178 @@ -164,12 +164,12 @@ void netjson_midIntoNodesTree(struct avl
179 }
180 }
181
182 -void netjson_tcIntoNodesTree(struct avl_tree *nodes, struct tc_entry *tc) {
183 - struct avl_node *avlnode;
184 +void netjson_tcIntoNodesTree(struct olsrd_avl_tree *nodes, struct tc_entry *tc) {
185 + struct olsrd_avl_node *olsrd_avlnode;
186 struct node_entry *node;
187
188 - avlnode = avl_find(nodes, &tc->addr);
189 - if (avlnode) {
190 + olsrd_avlnode = olsrd_avl_find(nodes, &tc->addr);
191 + if (olsrd_avlnode) {
192 /* the IP address is already known */
193 return;
194 }
195 @@ -178,21 +178,21 @@ void netjson_tcIntoNodesTree(struct avl_
196
197 node = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - TC - main");
198 memset(node, 0, sizeof(*node));
199 - node->avl.key = &tc->addr;
200 + node->olsrd_avl.key = &tc->addr;
201 node->isAlias = false;
202 node->tc = tc;
203 - if (avl_insert(nodes, &node->avl, AVL_DUP_NO) == -1) {
204 + if (olsrd_avl_insert(nodes, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
205 /* duplicate */
206 free(node);
207 }
208 }
209
210 -void netjson_tcEdgeIntoNodesTree(struct avl_tree *nodes, struct tc_edge_entry *tc_edge) {
211 - struct avl_node *avlnode;
212 +void netjson_tcEdgeIntoNodesTree(struct olsrd_avl_tree *nodes, struct tc_edge_entry *tc_edge) {
213 + struct olsrd_avl_node *olsrd_avlnode;
214 struct node_entry *node;
215
216 - avlnode = avl_find(nodes, &tc_edge->T_dest_addr);
217 - if (avlnode) {
218 + olsrd_avlnode = olsrd_avl_find(nodes, &tc_edge->T_dest_addr);
219 + if (olsrd_avlnode) {
220 /* the IP address is already known */
221 return;
222 }
223 @@ -201,21 +201,21 @@ void netjson_tcEdgeIntoNodesTree(struct
224
225 node = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - TC - main");
226 memset(node, 0, sizeof(*node));
227 - node->avl.key = &tc_edge->T_dest_addr;
228 + node->olsrd_avl.key = &tc_edge->T_dest_addr;
229 node->isAlias = false;
230 node->tc_edge = tc_edge;
231 - if (avl_insert(nodes, &node->avl, AVL_DUP_NO) == -1) {
232 + if (olsrd_avl_insert(nodes, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
233 /* duplicate */
234 free(node);
235 }
236 }
237
238 -void netjson_linkIntoNodesTree(struct avl_tree *nodes, struct link_entry *link, union olsr_ip_addr *addr) {
239 - struct avl_node *avlnode;
240 +void netjson_linkIntoNodesTree(struct olsrd_avl_tree *nodes, struct link_entry *link, union olsr_ip_addr *addr) {
241 + struct olsrd_avl_node *olsrd_avlnode;
242 struct node_entry *node;
243
244 - avlnode = avl_find(nodes, addr);
245 - if (avlnode) {
246 + olsrd_avlnode = olsrd_avl_find(nodes, addr);
247 + if (olsrd_avlnode) {
248 /* the IP address is already known */
249 return;
250 }
251 @@ -224,21 +224,21 @@ void netjson_linkIntoNodesTree(struct av
252
253 node = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - link");
254 memset(node, 0, sizeof(*node));
255 - node->avl.key = addr;
256 + node->olsrd_avl.key = addr;
257 node->isAlias = false;
258 node->link = link;
259 - if (avl_insert(nodes, &node->avl, AVL_DUP_NO) == -1) {
260 + if (olsrd_avl_insert(nodes, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
261 /* duplicate */
262 free(node);
263 }
264 }
265
266 -void netjson_neighborIntoNodesTree(struct avl_tree *nodes, struct neighbor_entry *neighbor) {
267 - struct avl_node *avlnode;
268 +void netjson_neighborIntoNodesTree(struct olsrd_avl_tree *nodes, struct neighbor_entry *neighbor) {
269 + struct olsrd_avl_node *olsrd_avlnode;
270 struct node_entry *node;
271
272 - avlnode = avl_find(nodes, &neighbor->neighbor_main_addr);
273 - if (avlnode) {
274 + olsrd_avlnode = olsrd_avl_find(nodes, &neighbor->neighbor_main_addr);
275 + if (olsrd_avlnode) {
276 /* the IP address is already known */
277 return;
278 }
279 @@ -247,10 +247,10 @@ void netjson_neighborIntoNodesTree(struc
280
281 node = olsr_malloc(sizeof(struct node_entry), "netjson NetworkGraph node - neighbor");
282 memset(node, 0, sizeof(*node));
283 - node->avl.key = &neighbor->neighbor_main_addr;
284 + node->olsrd_avl.key = &neighbor->neighbor_main_addr;
285 node->isAlias = false;
286 node->neighbor = neighbor;
287 - if (avl_insert(nodes, &node->avl, AVL_DUP_NO) == -1) {
288 + if (olsrd_avl_insert(nodes, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
289 /* duplicate */
290 free(node);
291 }
292 --- a/lib/netjson/src/olsrd_netjson_helpers.h
293 +++ b/lib/netjson/src/olsrd_netjson_helpers.h
294 @@ -48,7 +48,7 @@
295
296 #include <stdbool.h>
297
298 -#include "common/avl.h"
299 +#include "common/olsrd_avl.h"
300 #include "mid_set.h"
301 #include "tc_set.h"
302 #include "link_set.h"
303 @@ -56,7 +56,7 @@
304 #include "olsr_types.h"
305
306 struct node_entry {
307 - struct avl_node avl;
308 + struct olsrd_avl_node olsrd_avl;
309 bool isAlias;
310 struct mid_entry *mid;
311 struct tc_entry *tc;
312 @@ -65,15 +65,15 @@ struct node_entry {
313 struct neighbor_entry *neighbor;
314 };
315
316 -/* static INLINE struct node_entry * avlnode2node(struct avl_node *ptr) */
317 -AVLNODE2STRUCT(avlnode2node, struct node_entry, avl);
318 +/* static INLINE struct node_entry * olsrd_avlnode2node(struct olsrd_avl_node *ptr) */
319 +OLSRD_AVLNODE2STRUCT(olsrd_avlnode2node, struct node_entry, olsrd_avl);
320
321 struct node_entry * netjson_constructMidSelf(struct mid_entry *mid);
322 void netjson_cleanup_mid_self(struct node_entry *node_entry);
323 -void netjson_midIntoNodesTree(struct avl_tree *nodes, struct mid_entry *mid);
324 -void netjson_tcIntoNodesTree(struct avl_tree *nodes, struct tc_entry *tc);
325 -void netjson_tcEdgeIntoNodesTree(struct avl_tree *nodes, struct tc_edge_entry *tc_edge);
326 -void netjson_linkIntoNodesTree(struct avl_tree *nodes, struct link_entry *link, union olsr_ip_addr *addr);
327 -void netjson_neighborIntoNodesTree(struct avl_tree *nodes, struct neighbor_entry *neigh);
328 +void netjson_midIntoNodesTree(struct olsrd_avl_tree *nodes, struct mid_entry *mid);
329 +void netjson_tcIntoNodesTree(struct olsrd_avl_tree *nodes, struct tc_entry *tc);
330 +void netjson_tcEdgeIntoNodesTree(struct olsrd_avl_tree *nodes, struct tc_edge_entry *tc_edge);
331 +void netjson_linkIntoNodesTree(struct olsrd_avl_tree *nodes, struct link_entry *link, union olsr_ip_addr *addr);
332 +void netjson_neighborIntoNodesTree(struct olsrd_avl_tree *nodes, struct neighbor_entry *neigh);
333
334 #endif /* LIB_NETJSON_SRC_OLSRD_NETJSON_HELPERS_H_ */
335 --- a/src/common/avl.c
336 +++ /dev/null
337 @@ -1,664 +0,0 @@
338 -/*
339 - * The olsr.org Optimized Link-State Routing daemon (olsrd)
340 - *
341 - * (c) by the OLSR project
342 - *
343 - * See our Git repository to find out who worked on this file
344 - * and thus is a copyright holder on it.
345 - *
346 - * All rights reserved.
347 - *
348 - * Redistribution and use in source and binary forms, with or without
349 - * modification, are permitted provided that the following conditions
350 - * are met:
351 - *
352 - * * Redistributions of source code must retain the above copyright
353 - * notice, this list of conditions and the following disclaimer.
354 - * * Redistributions in binary form must reproduce the above copyright
355 - * notice, this list of conditions and the following disclaimer in
356 - * the documentation and/or other materials provided with the
357 - * distribution.
358 - * * Neither the name of olsr.org, olsrd nor the names of its
359 - * contributors may be used to endorse or promote products derived
360 - * from this software without specific prior written permission.
361 - *
362 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
363 - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
364 - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
365 - * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
366 - * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
367 - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
368 - * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
369 - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
370 - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
371 - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
372 - * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
373 - * POSSIBILITY OF SUCH DAMAGE.
374 - *
375 - * Visit http://www.olsr.org for more information.
376 - *
377 - * If you find this software useful feel free to make a donation
378 - * to the project. For more information see the website or contact
379 - * the copyright holders.
380 - *
381 - */
382 -
383 -#include <stddef.h>
384 -#include <time.h>
385 -#include <string.h>
386 -
387 -#include "ipcalc.h"
388 -#include "common/avl.h"
389 -#include "net_olsr.h"
390 -
391 -/*
392 - * default comparison pointers
393 - * set to the respective compare function.
394 - * if avl_comp_default is set to zero, a fast
395 - * INLINE ipv4 comparison will be executed.
396 - */
397 -avl_tree_comp avl_comp_default = NULL;
398 -avl_tree_comp avl_comp_prefix_default;
399 -
400 -int
401 -avl_comp_ipv4(const void *ip1, const void *ip2)
402 -{
403 - return ip4cmp(ip1, ip2);
404 -}
405 -
406 -int
407 -avl_comp_ipv6(const void *ip1, const void *ip2)
408 -{
409 - return ip6cmp(ip1, ip2);
410 -}
411 -
412 -int
413 -avl_comp_mac(const void *ip1, const void *ip2)
414 -{
415 - return memcmp(ip1, ip2, 6);
416 -}
417 -
418 -void
419 -avl_init(struct avl_tree *tree, avl_tree_comp comp)
420 -{
421 - tree->root = NULL;
422 - tree->first = NULL;
423 - tree->last = NULL;
424 - tree->count = 0;
425 -
426 - tree->comp = comp == avl_comp_ipv4 ? NULL : comp;
427 -}
428 -
429 -static struct avl_node *
430 -avl_find_rec_ipv4(struct avl_node *node, const void *key)
431 -{
432 - if (*(const unsigned int *)key < *(const unsigned int *)node->key) {
433 - if (node->left != NULL)
434 - return avl_find_rec_ipv4(node->left, key);
435 - }
436 -
437 - else if (*(const unsigned int *)key > *(const unsigned int *)node->key) {
438 - if (node->right != NULL)
439 - return avl_find_rec_ipv4(node->right, key);
440 - }
441 -
442 - return node;
443 -}
444 -
445 -static struct avl_node *
446 -avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp)
447 -{
448 - int diff;
449 -
450 - if (NULL == comp)
451 - return avl_find_rec_ipv4(node, key);
452 -
453 - diff = (*comp) (key, node->key);
454 -
455 - if (diff < 0) {
456 - if (node->left != NULL)
457 - return avl_find_rec(node->left, key, comp);
458 -
459 - return node;
460 - }
461 -
462 - if (diff > 0) {
463 - if (node->right != NULL)
464 - return avl_find_rec(node->right, key, comp);
465 -
466 - return node;
467 - }
468 -
469 - return node;
470 -}
471 -
472 -struct avl_node *
473 -avl_find(struct avl_tree *tree, const void *key)
474 -{
475 - struct avl_node *node;
476 -
477 - if (tree->root == NULL)
478 - return NULL;
479 -
480 - node = avl_find_rec(tree->root, key, tree->comp);
481 -
482 - if (NULL == tree->comp) {
483 - if (0 != ip4cmp(node->key, key))
484 - return NULL;
485 - }
486 -
487 - else {
488 - if ((*tree->comp) (node->key, key) != 0)
489 - return NULL;
490 - }
491 -
492 - return node;
493 -}
494 -
495 -static void
496 -avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
497 -{
498 - struct avl_node *left, *parent;
499 -
500 - left = node->left;
501 - parent = node->parent;
502 -
503 - left->parent = parent;
504 - node->parent = left;
505 -
506 - if (parent == NULL)
507 - tree->root = left;
508 -
509 - else {
510 - if (parent->left == node)
511 - parent->left = left;
512 -
513 - else
514 - parent->right = left;
515 - }
516 -
517 - node->left = left->right;
518 - left->right = node;
519 -
520 - if (node->left != NULL)
521 - node->left->parent = node;
522 -
523 - node->balance += 1 - MIN(left->balance, 0);
524 - left->balance += 1 + MAX(node->balance, 0);
525 -}
526 -
527 -static void
528 -avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
529 -{
530 - struct avl_node *right, *parent;
531 -
532 - right = node->right;
533 - parent = node->parent;
534 -
535 - right->parent = parent;
536 - node->parent = right;
537 -
538 - if (parent == NULL)
539 - tree->root = right;
540 -
541 - else {
542 - if (parent->left == node)
543 - parent->left = right;
544 -
545 - else
546 - parent->right = right;
547 - }
548 -
549 - node->right = right->left;
550 - right->left = node;
551 -
552 - if (node->right != NULL)
553 - node->right->parent = node;
554 -
555 - node->balance -= 1 + MAX(right->balance, 0);
556 - right->balance -= 1 - MIN(node->balance, 0);
557 -}
558 -
559 -static void
560 -post_insert(struct avl_tree *tree, struct avl_node *node)
561 -{
562 - struct avl_node *parent = node->parent;
563 -
564 - if (parent == NULL)
565 - return;
566 -
567 - if (node == parent->left) {
568 - parent->balance--;
569 -
570 - if (parent->balance == 0)
571 - return;
572 -
573 - if (parent->balance == -1) {
574 - post_insert(tree, parent);
575 - return;
576 - }
577 -
578 - if (node->balance == -1) {
579 - avl_rotate_right(tree, parent);
580 - return;
581 - }
582 -
583 - avl_rotate_left(tree, node);
584 - avl_rotate_right(tree, node->parent->parent);
585 - return;
586 - }
587 -
588 - parent->balance++;
589 -
590 - if (parent->balance == 0)
591 - return;
592 -
593 - if (parent->balance == 1) {
594 - post_insert(tree, parent);
595 - return;
596 - }
597 -
598 - if (node->balance == 1) {
599 - avl_rotate_left(tree, parent);
600 - return;
601 - }
602 -
603 - avl_rotate_right(tree, node);
604 - avl_rotate_left(tree, node->parent->parent);
605 -}
606 -
607 -static void
608 -avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
609 -{
610 - if (pos_node->prev != NULL)
611 - pos_node->prev->next = node;
612 - else
613 - tree->first = node;
614 -
615 - node->prev = pos_node->prev;
616 - node->next = pos_node;
617 -
618 - pos_node->prev = node;
619 -
620 - tree->count++;
621 -}
622 -
623 -static void
624 -avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
625 -{
626 - if (pos_node->next != NULL)
627 - pos_node->next->prev = node;
628 - else
629 - tree->last = node;
630 -
631 - node->prev = pos_node;
632 - node->next = pos_node->next;
633 -
634 - pos_node->next = node;
635 -
636 - tree->count++;
637 -}
638 -
639 -static void
640 -avl_remove(struct avl_tree *tree, struct avl_node *node)
641 -{
642 - if (node->prev != NULL)
643 - node->prev->next = node->next;
644 - else
645 - tree->first = node->next;
646 -
647 - if (node->next != NULL)
648 - node->next->prev = node->prev;
649 - else
650 - tree->last = node->prev;
651 -
652 - tree->count--;
653 -}
654 -
655 -int
656 -avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
657 -{
658 - struct avl_node *node;
659 - struct avl_node *last;
660 - int diff;
661 -
662 - new->parent = NULL;
663 -
664 - new->left = NULL;
665 - new->right = NULL;
666 -
667 - new->next = NULL;
668 - new->prev = NULL;
669 -
670 - new->balance = 0;
671 - new->leader = 1;
672 -
673 - if (tree->root == NULL) {
674 - tree->root = new;
675 - tree->first = new;
676 - tree->last = new;
677 - tree->count = 1;
678 - return 0;
679 - }
680 -
681 - node = avl_find_rec(tree->root, new->key, tree->comp);
682 -
683 - last = node;
684 -
685 - while (last->next != NULL && last->next->leader == 0)
686 - last = last->next;
687 -
688 - if (NULL == tree->comp)
689 - diff = ip4cmp(new->key, node->key);
690 -
691 - else
692 - diff = (*tree->comp) (new->key, node->key);
693 -
694 - if (diff == 0) {
695 - if (allow_duplicates == AVL_DUP_NO)
696 - return -1;
697 -
698 - new->leader = 0;
699 -
700 - avl_insert_after(tree, last, new);
701 - return 0;
702 - }
703 -
704 - if (node->balance == 1) {
705 - avl_insert_before(tree, node, new);
706 -
707 - node->balance = 0;
708 - new->parent = node;
709 - node->left = new;
710 - return 0;
711 - }
712 -
713 - if (node->balance == -1) {
714 - avl_insert_after(tree, last, new);
715 -
716 - node->balance = 0;
717 - new->parent = node;
718 - node->right = new;
719 - return 0;
720 - }
721 -
722 - if (diff < 0) {
723 - avl_insert_before(tree, node, new);
724 -
725 - node->balance = -1;
726 - new->parent = node;
727 - node->left = new;
728 - post_insert(tree, node);
729 - return 0;
730 - }
731 -
732 - avl_insert_after(tree, last, new);
733 -
734 - node->balance = 1;
735 - new->parent = node;
736 - node->right = new;
737 - post_insert(tree, node);
738 - return 0;
739 -}
740 -
741 -static void
742 -avl_post_delete(struct avl_tree *tree, struct avl_node *node)
743 -{
744 - struct avl_node *parent;
745 -
746 - if ((parent = node->parent) == NULL)
747 - return;
748 -
749 - if (node == parent->left) {
750 - parent->balance++;
751 -
752 - if (parent->balance == 0) {
753 - avl_post_delete(tree, parent);
754 - return;
755 - }
756 -
757 - if (parent->balance == 1)
758 - return;
759 -
760 - if (parent->right->balance == 0) {
761 - avl_rotate_left(tree, parent);
762 - return;
763 - }
764 -
765 - if (parent->right->balance == 1) {
766 - avl_rotate_left(tree, parent);
767 - avl_post_delete(tree, parent->parent);
768 - return;
769 - }
770 -
771 - avl_rotate_right(tree, parent->right);
772 - avl_rotate_left(tree, parent);
773 - avl_post_delete(tree, parent->parent);
774 - return;
775 - }
776 -
777 - parent->balance--;
778 -
779 - if (parent->balance == 0) {
780 - avl_post_delete(tree, parent);
781 - return;
782 - }
783 -
784 - if (parent->balance == -1)
785 - return;
786 -
787 - if (parent->left->balance == 0) {
788 - avl_rotate_right(tree, parent);
789 - return;
790 - }
791 -
792 - if (parent->left->balance == -1) {
793 - avl_rotate_right(tree, parent);
794 - avl_post_delete(tree, parent->parent);
795 - return;
796 - }
797 -
798 - avl_rotate_left(tree, parent->left);
799 - avl_rotate_right(tree, parent);
800 - avl_post_delete(tree, parent->parent);
801 -}
802 -
803 -static struct avl_node *
804 -avl_local_min(struct avl_node *node)
805 -{
806 - while (node->left != NULL)
807 - node = node->left;
808 -
809 - return node;
810 -}
811 -
812 -static void
813 -avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
814 -{
815 - struct avl_node *parent, *min;
816 -
817 - parent = node->parent;
818 -
819 - if (node->left == NULL && node->right == NULL) {
820 - if (parent == NULL) {
821 - tree->root = NULL;
822 - return;
823 - }
824 -
825 - if (parent->left == node) {
826 - parent->left = NULL;
827 - parent->balance++;
828 -
829 - if (parent->balance == 1)
830 - return;
831 -
832 - if (parent->balance == 0) {
833 - avl_post_delete(tree, parent);
834 - return;
835 - }
836 -
837 - if (parent->right->balance == 0) {
838 - avl_rotate_left(tree, parent);
839 - return;
840 - }
841 -
842 - if (parent->right->balance == 1) {
843 - avl_rotate_left(tree, parent);
844 - avl_post_delete(tree, parent->parent);
845 - return;
846 - }
847 -
848 - avl_rotate_right(tree, parent->right);
849 - avl_rotate_left(tree, parent);
850 - avl_post_delete(tree, parent->parent);
851 - }
852 - else {
853 - parent->right = NULL;
854 - parent->balance--;
855 -
856 - if (parent->balance == -1)
857 - return;
858 -
859 - if (parent->balance == 0) {
860 - avl_post_delete(tree, parent);
861 - return;
862 - }
863 -
864 - if (parent->left->balance == 0) {
865 - avl_rotate_right(tree, parent);
866 - return;
867 - }
868 -
869 - if (parent->left->balance == -1) {
870 - avl_rotate_right(tree, parent);
871 - avl_post_delete(tree, parent->parent);
872 - return;
873 - }
874 -
875 - avl_rotate_left(tree, parent->left);
876 - avl_rotate_right(tree, parent);
877 - avl_post_delete(tree, parent->parent);
878 - }
879 - return;
880 - }
881 -
882 - if (node->left == NULL) {
883 - if (parent == NULL) {
884 - tree->root = node->right;
885 - node->right->parent = NULL;
886 - return;
887 - }
888 -
889 - node->right->parent = parent;
890 -
891 - if (parent->left == node)
892 - parent->left = node->right;
893 -
894 - else
895 - parent->right = node->right;
896 -
897 - avl_post_delete(tree, node->right);
898 - return;
899 - }
900 -
901 - if (node->right == NULL) {
902 - if (parent == NULL) {
903 - tree->root = node->left;
904 - node->left->parent = NULL;
905 - return;
906 - }
907 -
908 - node->left->parent = parent;
909 -
910 - if (parent->left == node)
911 - parent->left = node->left;
912 -
913 - else
914 - parent->right = node->left;
915 -
916 - avl_post_delete(tree, node->left);
917 - return;
918 - }
919 -
920 - min = avl_local_min(node->right);
921 - avl_delete_worker(tree, min);
922 - parent = node->parent;
923 -
924 - min->balance = node->balance;
925 - min->parent = parent;
926 - min->left = node->left;
927 - min->right = node->right;
928 -
929 - if (min->left != NULL)
930 - min->left->parent = min;
931 -
932 - if (min->right != NULL)
933 - min->right->parent = min;
934 -
935 - if (parent == NULL) {
936 - tree->root = min;
937 - return;
938 - }
939 -
940 - if (parent->left == node) {
941 - parent->left = min;
942 - return;
943 - }
944 -
945 - parent->right = min;
946 -}
947 -
948 -void
949 -avl_delete(struct avl_tree *tree, struct avl_node *node)
950 -{
951 - struct avl_node *next;
952 - struct avl_node *parent;
953 - struct avl_node *left;
954 - struct avl_node *right;
955 -
956 - if (node->leader != 0) {
957 - next = node->next;
958 -
959 - if (next != NULL && next->leader == 0) {
960 - next->leader = 1;
961 - next->balance = node->balance;
962 -
963 - parent = node->parent;
964 - left = node->left;
965 - right = node->right;
966 -
967 - next->parent = parent;
968 - next->left = left;
969 - next->right = right;
970 -
971 - if (parent == NULL)
972 - tree->root = next;
973 -
974 - else {
975 - if (node == parent->left)
976 - parent->left = next;
977 -
978 - else
979 - parent->right = next;
980 - }
981 -
982 - if (left != NULL)
983 - left->parent = next;
984 -
985 - if (right != NULL)
986 - right->parent = next;
987 - }
988 -
989 - else
990 - avl_delete_worker(tree, node);
991 - }
992 -
993 - avl_remove(tree, node);
994 -}
995 -
996 -/*
997 - * Local Variables:
998 - * c-basic-offset: 2
999 - * indent-tabs-mode: nil
1000 - * End:
1001 - */
1002 --- /dev/null
1003 +++ b/src/common/olsrd_avl.c
1004 @@ -0,0 +1,664 @@
1005 +/*
1006 + * The olsr.org Optimized Link-State Routing daemon (olsrd)
1007 + *
1008 + * (c) by the OLSR project
1009 + *
1010 + * See our Git repository to find out who worked on this file
1011 + * and thus is a copyright holder on it.
1012 + *
1013 + * All rights reserved.
1014 + *
1015 + * Redistribution and use in source and binary forms, with or without
1016 + * modification, are permitted provided that the following conditions
1017 + * are met:
1018 + *
1019 + * * Redistributions of source code must retain the above copyright
1020 + * notice, this list of conditions and the following disclaimer.
1021 + * * Redistributions in binary form must reproduce the above copyright
1022 + * notice, this list of conditions and the following disclaimer in
1023 + * the documentation and/or other materials provided with the
1024 + * distribution.
1025 + * * Neither the name of olsr.org, olsrd nor the names of its
1026 + * contributors may be used to endorse or promote products derived
1027 + * from this software without specific prior written permission.
1028 + *
1029 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1030 + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1031 + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
1032 + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
1033 + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
1034 + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
1035 + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
1036 + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1037 + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1038 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
1039 + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1040 + * POSSIBILITY OF SUCH DAMAGE.
1041 + *
1042 + * Visit http://www.olsr.org for more information.
1043 + *
1044 + * If you find this software useful feel free to make a donation
1045 + * to the project. For more information see the website or contact
1046 + * the copyright holders.
1047 + *
1048 + */
1049 +
1050 +#include <stddef.h>
1051 +#include <time.h>
1052 +#include <string.h>
1053 +
1054 +#include "ipcalc.h"
1055 +#include "common/olsrd_avl.h"
1056 +#include "net_olsr.h"
1057 +
1058 +/*
1059 + * default comparison pointers
1060 + * set to the respective compare function.
1061 + * if olsrd_avl_comp_default is set to zero, a fast
1062 + * INLINE ipv4 comparison will be executed.
1063 + */
1064 +olsrd_avl_tree_comp olsrd_avl_comp_default = NULL;
1065 +olsrd_avl_tree_comp olsrd_avl_comp_prefix_default;
1066 +
1067 +int
1068 +olsrd_avl_comp_ipv4(const void *ip1, const void *ip2)
1069 +{
1070 + return ip4cmp(ip1, ip2);
1071 +}
1072 +
1073 +int
1074 +olsrd_avl_comp_ipv6(const void *ip1, const void *ip2)
1075 +{
1076 + return ip6cmp(ip1, ip2);
1077 +}
1078 +
1079 +int
1080 +olsrd_avl_comp_mac(const void *ip1, const void *ip2)
1081 +{
1082 + return memcmp(ip1, ip2, 6);
1083 +}
1084 +
1085 +void
1086 +olsrd_avl_init(struct olsrd_avl_tree *tree, olsrd_avl_tree_comp comp)
1087 +{
1088 + tree->root = NULL;
1089 + tree->first = NULL;
1090 + tree->last = NULL;
1091 + tree->count = 0;
1092 +
1093 + tree->comp = comp == olsrd_avl_comp_ipv4 ? NULL : comp;
1094 +}
1095 +
1096 +static struct olsrd_avl_node *
1097 +olsrd_avl_find_rec_ipv4(struct olsrd_avl_node *node, const void *key)
1098 +{
1099 + if (*(const unsigned int *)key < *(const unsigned int *)node->key) {
1100 + if (node->left != NULL)
1101 + return olsrd_avl_find_rec_ipv4(node->left, key);
1102 + }
1103 +
1104 + else if (*(const unsigned int *)key > *(const unsigned int *)node->key) {
1105 + if (node->right != NULL)
1106 + return olsrd_avl_find_rec_ipv4(node->right, key);
1107 + }
1108 +
1109 + return node;
1110 +}
1111 +
1112 +static struct olsrd_avl_node *
1113 +olsrd_avl_find_rec(struct olsrd_avl_node *node, const void *key, olsrd_avl_tree_comp comp)
1114 +{
1115 + int diff;
1116 +
1117 + if (NULL == comp)
1118 + return olsrd_avl_find_rec_ipv4(node, key);
1119 +
1120 + diff = (*comp) (key, node->key);
1121 +
1122 + if (diff < 0) {
1123 + if (node->left != NULL)
1124 + return olsrd_avl_find_rec(node->left, key, comp);
1125 +
1126 + return node;
1127 + }
1128 +
1129 + if (diff > 0) {
1130 + if (node->right != NULL)
1131 + return olsrd_avl_find_rec(node->right, key, comp);
1132 +
1133 + return node;
1134 + }
1135 +
1136 + return node;
1137 +}
1138 +
1139 +struct olsrd_avl_node *
1140 +olsrd_avl_find(struct olsrd_avl_tree *tree, const void *key)
1141 +{
1142 + struct olsrd_avl_node *node;
1143 +
1144 + if (tree->root == NULL)
1145 + return NULL;
1146 +
1147 + node = olsrd_avl_find_rec(tree->root, key, tree->comp);
1148 +
1149 + if (NULL == tree->comp) {
1150 + if (0 != ip4cmp(node->key, key))
1151 + return NULL;
1152 + }
1153 +
1154 + else {
1155 + if ((*tree->comp) (node->key, key) != 0)
1156 + return NULL;
1157 + }
1158 +
1159 + return node;
1160 +}
1161 +
1162 +static void
1163 +olsrd_avl_rotate_right(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1164 +{
1165 + struct olsrd_avl_node *left, *parent;
1166 +
1167 + left = node->left;
1168 + parent = node->parent;
1169 +
1170 + left->parent = parent;
1171 + node->parent = left;
1172 +
1173 + if (parent == NULL)
1174 + tree->root = left;
1175 +
1176 + else {
1177 + if (parent->left == node)
1178 + parent->left = left;
1179 +
1180 + else
1181 + parent->right = left;
1182 + }
1183 +
1184 + node->left = left->right;
1185 + left->right = node;
1186 +
1187 + if (node->left != NULL)
1188 + node->left->parent = node;
1189 +
1190 + node->balance += 1 - MIN(left->balance, 0);
1191 + left->balance += 1 + MAX(node->balance, 0);
1192 +}
1193 +
1194 +static void
1195 +olsrd_avl_rotate_left(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1196 +{
1197 + struct olsrd_avl_node *right, *parent;
1198 +
1199 + right = node->right;
1200 + parent = node->parent;
1201 +
1202 + right->parent = parent;
1203 + node->parent = right;
1204 +
1205 + if (parent == NULL)
1206 + tree->root = right;
1207 +
1208 + else {
1209 + if (parent->left == node)
1210 + parent->left = right;
1211 +
1212 + else
1213 + parent->right = right;
1214 + }
1215 +
1216 + node->right = right->left;
1217 + right->left = node;
1218 +
1219 + if (node->right != NULL)
1220 + node->right->parent = node;
1221 +
1222 + node->balance -= 1 + MAX(right->balance, 0);
1223 + right->balance -= 1 - MIN(node->balance, 0);
1224 +}
1225 +
1226 +static void
1227 +post_insert(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1228 +{
1229 + struct olsrd_avl_node *parent = node->parent;
1230 +
1231 + if (parent == NULL)
1232 + return;
1233 +
1234 + if (node == parent->left) {
1235 + parent->balance--;
1236 +
1237 + if (parent->balance == 0)
1238 + return;
1239 +
1240 + if (parent->balance == -1) {
1241 + post_insert(tree, parent);
1242 + return;
1243 + }
1244 +
1245 + if (node->balance == -1) {
1246 + olsrd_avl_rotate_right(tree, parent);
1247 + return;
1248 + }
1249 +
1250 + olsrd_avl_rotate_left(tree, node);
1251 + olsrd_avl_rotate_right(tree, node->parent->parent);
1252 + return;
1253 + }
1254 +
1255 + parent->balance++;
1256 +
1257 + if (parent->balance == 0)
1258 + return;
1259 +
1260 + if (parent->balance == 1) {
1261 + post_insert(tree, parent);
1262 + return;
1263 + }
1264 +
1265 + if (node->balance == 1) {
1266 + olsrd_avl_rotate_left(tree, parent);
1267 + return;
1268 + }
1269 +
1270 + olsrd_avl_rotate_right(tree, node);
1271 + olsrd_avl_rotate_left(tree, node->parent->parent);
1272 +}
1273 +
1274 +static void
1275 +olsrd_avl_insert_before(struct olsrd_avl_tree *tree, struct olsrd_avl_node *pos_node, struct olsrd_avl_node *node)
1276 +{
1277 + if (pos_node->prev != NULL)
1278 + pos_node->prev->next = node;
1279 + else
1280 + tree->first = node;
1281 +
1282 + node->prev = pos_node->prev;
1283 + node->next = pos_node;
1284 +
1285 + pos_node->prev = node;
1286 +
1287 + tree->count++;
1288 +}
1289 +
1290 +static void
1291 +olsrd_avl_insert_after(struct olsrd_avl_tree *tree, struct olsrd_avl_node *pos_node, struct olsrd_avl_node *node)
1292 +{
1293 + if (pos_node->next != NULL)
1294 + pos_node->next->prev = node;
1295 + else
1296 + tree->last = node;
1297 +
1298 + node->prev = pos_node;
1299 + node->next = pos_node->next;
1300 +
1301 + pos_node->next = node;
1302 +
1303 + tree->count++;
1304 +}
1305 +
1306 +static void
1307 +olsrd_avl_remove(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1308 +{
1309 + if (node->prev != NULL)
1310 + node->prev->next = node->next;
1311 + else
1312 + tree->first = node->next;
1313 +
1314 + if (node->next != NULL)
1315 + node->next->prev = node->prev;
1316 + else
1317 + tree->last = node->prev;
1318 +
1319 + tree->count--;
1320 +}
1321 +
1322 +int
1323 +olsrd_avl_insert(struct olsrd_avl_tree *tree, struct olsrd_avl_node *new, int allow_duplicates)
1324 +{
1325 + struct olsrd_avl_node *node;
1326 + struct olsrd_avl_node *last;
1327 + int diff;
1328 +
1329 + new->parent = NULL;
1330 +
1331 + new->left = NULL;
1332 + new->right = NULL;
1333 +
1334 + new->next = NULL;
1335 + new->prev = NULL;
1336 +
1337 + new->balance = 0;
1338 + new->leader = 1;
1339 +
1340 + if (tree->root == NULL) {
1341 + tree->root = new;
1342 + tree->first = new;
1343 + tree->last = new;
1344 + tree->count = 1;
1345 + return 0;
1346 + }
1347 +
1348 + node = olsrd_avl_find_rec(tree->root, new->key, tree->comp);
1349 +
1350 + last = node;
1351 +
1352 + while (last->next != NULL && last->next->leader == 0)
1353 + last = last->next;
1354 +
1355 + if (NULL == tree->comp)
1356 + diff = ip4cmp(new->key, node->key);
1357 +
1358 + else
1359 + diff = (*tree->comp) (new->key, node->key);
1360 +
1361 + if (diff == 0) {
1362 + if (allow_duplicates == OLSRD_AVL_DUP_NO)
1363 + return -1;
1364 +
1365 + new->leader = 0;
1366 +
1367 + olsrd_avl_insert_after(tree, last, new);
1368 + return 0;
1369 + }
1370 +
1371 + if (node->balance == 1) {
1372 + olsrd_avl_insert_before(tree, node, new);
1373 +
1374 + node->balance = 0;
1375 + new->parent = node;
1376 + node->left = new;
1377 + return 0;
1378 + }
1379 +
1380 + if (node->balance == -1) {
1381 + olsrd_avl_insert_after(tree, last, new);
1382 +
1383 + node->balance = 0;
1384 + new->parent = node;
1385 + node->right = new;
1386 + return 0;
1387 + }
1388 +
1389 + if (diff < 0) {
1390 + olsrd_avl_insert_before(tree, node, new);
1391 +
1392 + node->balance = -1;
1393 + new->parent = node;
1394 + node->left = new;
1395 + post_insert(tree, node);
1396 + return 0;
1397 + }
1398 +
1399 + olsrd_avl_insert_after(tree, last, new);
1400 +
1401 + node->balance = 1;
1402 + new->parent = node;
1403 + node->right = new;
1404 + post_insert(tree, node);
1405 + return 0;
1406 +}
1407 +
1408 +static void
1409 +olsrd_avl_post_delete(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1410 +{
1411 + struct olsrd_avl_node *parent;
1412 +
1413 + if ((parent = node->parent) == NULL)
1414 + return;
1415 +
1416 + if (node == parent->left) {
1417 + parent->balance++;
1418 +
1419 + if (parent->balance == 0) {
1420 + olsrd_avl_post_delete(tree, parent);
1421 + return;
1422 + }
1423 +
1424 + if (parent->balance == 1)
1425 + return;
1426 +
1427 + if (parent->right->balance == 0) {
1428 + olsrd_avl_rotate_left(tree, parent);
1429 + return;
1430 + }
1431 +
1432 + if (parent->right->balance == 1) {
1433 + olsrd_avl_rotate_left(tree, parent);
1434 + olsrd_avl_post_delete(tree, parent->parent);
1435 + return;
1436 + }
1437 +
1438 + olsrd_avl_rotate_right(tree, parent->right);
1439 + olsrd_avl_rotate_left(tree, parent);
1440 + olsrd_avl_post_delete(tree, parent->parent);
1441 + return;
1442 + }
1443 +
1444 + parent->balance--;
1445 +
1446 + if (parent->balance == 0) {
1447 + olsrd_avl_post_delete(tree, parent);
1448 + return;
1449 + }
1450 +
1451 + if (parent->balance == -1)
1452 + return;
1453 +
1454 + if (parent->left->balance == 0) {
1455 + olsrd_avl_rotate_right(tree, parent);
1456 + return;
1457 + }
1458 +
1459 + if (parent->left->balance == -1) {
1460 + olsrd_avl_rotate_right(tree, parent);
1461 + olsrd_avl_post_delete(tree, parent->parent);
1462 + return;
1463 + }
1464 +
1465 + olsrd_avl_rotate_left(tree, parent->left);
1466 + olsrd_avl_rotate_right(tree, parent);
1467 + olsrd_avl_post_delete(tree, parent->parent);
1468 +}
1469 +
1470 +static struct olsrd_avl_node *
1471 +olsrd_avl_local_min(struct olsrd_avl_node *node)
1472 +{
1473 + while (node->left != NULL)
1474 + node = node->left;
1475 +
1476 + return node;
1477 +}
1478 +
1479 +static void
1480 +olsrd_avl_delete_worker(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1481 +{
1482 + struct olsrd_avl_node *parent, *min;
1483 +
1484 + parent = node->parent;
1485 +
1486 + if (node->left == NULL && node->right == NULL) {
1487 + if (parent == NULL) {
1488 + tree->root = NULL;
1489 + return;
1490 + }
1491 +
1492 + if (parent->left == node) {
1493 + parent->left = NULL;
1494 + parent->balance++;
1495 +
1496 + if (parent->balance == 1)
1497 + return;
1498 +
1499 + if (parent->balance == 0) {
1500 + olsrd_avl_post_delete(tree, parent);
1501 + return;
1502 + }
1503 +
1504 + if (parent->right->balance == 0) {
1505 + olsrd_avl_rotate_left(tree, parent);
1506 + return;
1507 + }
1508 +
1509 + if (parent->right->balance == 1) {
1510 + olsrd_avl_rotate_left(tree, parent);
1511 + olsrd_avl_post_delete(tree, parent->parent);
1512 + return;
1513 + }
1514 +
1515 + olsrd_avl_rotate_right(tree, parent->right);
1516 + olsrd_avl_rotate_left(tree, parent);
1517 + olsrd_avl_post_delete(tree, parent->parent);
1518 + }
1519 + else {
1520 + parent->right = NULL;
1521 + parent->balance--;
1522 +
1523 + if (parent->balance == -1)
1524 + return;
1525 +
1526 + if (parent->balance == 0) {
1527 + olsrd_avl_post_delete(tree, parent);
1528 + return;
1529 + }
1530 +
1531 + if (parent->left->balance == 0) {
1532 + olsrd_avl_rotate_right(tree, parent);
1533 + return;
1534 + }
1535 +
1536 + if (parent->left->balance == -1) {
1537 + olsrd_avl_rotate_right(tree, parent);
1538 + olsrd_avl_post_delete(tree, parent->parent);
1539 + return;
1540 + }
1541 +
1542 + olsrd_avl_rotate_left(tree, parent->left);
1543 + olsrd_avl_rotate_right(tree, parent);
1544 + olsrd_avl_post_delete(tree, parent->parent);
1545 + }
1546 + return;
1547 + }
1548 +
1549 + if (node->left == NULL) {
1550 + if (parent == NULL) {
1551 + tree->root = node->right;
1552 + node->right->parent = NULL;
1553 + return;
1554 + }
1555 +
1556 + node->right->parent = parent;
1557 +
1558 + if (parent->left == node)
1559 + parent->left = node->right;
1560 +
1561 + else
1562 + parent->right = node->right;
1563 +
1564 + olsrd_avl_post_delete(tree, node->right);
1565 + return;
1566 + }
1567 +
1568 + if (node->right == NULL) {
1569 + if (parent == NULL) {
1570 + tree->root = node->left;
1571 + node->left->parent = NULL;
1572 + return;
1573 + }
1574 +
1575 + node->left->parent = parent;
1576 +
1577 + if (parent->left == node)
1578 + parent->left = node->left;
1579 +
1580 + else
1581 + parent->right = node->left;
1582 +
1583 + olsrd_avl_post_delete(tree, node->left);
1584 + return;
1585 + }
1586 +
1587 + min = olsrd_avl_local_min(node->right);
1588 + olsrd_avl_delete_worker(tree, min);
1589 + parent = node->parent;
1590 +
1591 + min->balance = node->balance;
1592 + min->parent = parent;
1593 + min->left = node->left;
1594 + min->right = node->right;
1595 +
1596 + if (min->left != NULL)
1597 + min->left->parent = min;
1598 +
1599 + if (min->right != NULL)
1600 + min->right->parent = min;
1601 +
1602 + if (parent == NULL) {
1603 + tree->root = min;
1604 + return;
1605 + }
1606 +
1607 + if (parent->left == node) {
1608 + parent->left = min;
1609 + return;
1610 + }
1611 +
1612 + parent->right = min;
1613 +}
1614 +
1615 +void
1616 +olsrd_avl_delete(struct olsrd_avl_tree *tree, struct olsrd_avl_node *node)
1617 +{
1618 + struct olsrd_avl_node *next;
1619 + struct olsrd_avl_node *parent;
1620 + struct olsrd_avl_node *left;
1621 + struct olsrd_avl_node *right;
1622 +
1623 + if (node->leader != 0) {
1624 + next = node->next;
1625 +
1626 + if (next != NULL && next->leader == 0) {
1627 + next->leader = 1;
1628 + next->balance = node->balance;
1629 +
1630 + parent = node->parent;
1631 + left = node->left;
1632 + right = node->right;
1633 +
1634 + next->parent = parent;
1635 + next->left = left;
1636 + next->right = right;
1637 +
1638 + if (parent == NULL)
1639 + tree->root = next;
1640 +
1641 + else {
1642 + if (node == parent->left)
1643 + parent->left = next;
1644 +
1645 + else
1646 + parent->right = next;
1647 + }
1648 +
1649 + if (left != NULL)
1650 + left->parent = next;
1651 +
1652 + if (right != NULL)
1653 + right->parent = next;
1654 + }
1655 +
1656 + else
1657 + olsrd_avl_delete_worker(tree, node);
1658 + }
1659 +
1660 + olsrd_avl_remove(tree, node);
1661 +}
1662 +
1663 +/*
1664 + * Local Variables:
1665 + * c-basic-offset: 2
1666 + * indent-tabs-mode: nil
1667 + * End:
1668 + */
1669 --- a/src/common/avl.h
1670 +++ /dev/null
1671 @@ -1,183 +0,0 @@
1672 -/*
1673 - * The olsr.org Optimized Link-State Routing daemon (olsrd)
1674 - *
1675 - * (c) by the OLSR project
1676 - *
1677 - * See our Git repository to find out who worked on this file
1678 - * and thus is a copyright holder on it.
1679 - *
1680 - * All rights reserved.
1681 - *
1682 - * Redistribution and use in source and binary forms, with or without
1683 - * modification, are permitted provided that the following conditions
1684 - * are met:
1685 - *
1686 - * * Redistributions of source code must retain the above copyright
1687 - * notice, this list of conditions and the following disclaimer.
1688 - * * Redistributions in binary form must reproduce the above copyright
1689 - * notice, this list of conditions and the following disclaimer in
1690 - * the documentation and/or other materials provided with the
1691 - * distribution.
1692 - * * Neither the name of olsr.org, olsrd nor the names of its
1693 - * contributors may be used to endorse or promote products derived
1694 - * from this software without specific prior written permission.
1695 - *
1696 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1697 - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1698 - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
1699 - * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
1700 - * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
1701 - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
1702 - * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
1703 - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1704 - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1705 - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
1706 - * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1707 - * POSSIBILITY OF SUCH DAMAGE.
1708 - *
1709 - * Visit http://www.olsr.org for more information.
1710 - *
1711 - * If you find this software useful feel free to make a donation
1712 - * to the project. For more information see the website or contact
1713 - * the copyright holders.
1714 - *
1715 - */
1716 -
1717 -#ifndef _AVL_H
1718 -#define _AVL_H
1719 -
1720 -#include <stddef.h>
1721 -#include "compiler.h"
1722 -#include "defs.h"
1723 -
1724 -struct avl_node {
1725 - struct avl_node *parent;
1726 - struct avl_node *left;
1727 - struct avl_node *right;
1728 - struct avl_node *next;
1729 - struct avl_node *prev;
1730 - void *key;
1731 - signed char balance;
1732 - unsigned char leader;
1733 -};
1734 -
1735 -typedef int (*avl_tree_comp) (const void *, const void *);
1736 -
1737 -struct avl_tree {
1738 - struct avl_node *root;
1739 - struct avl_node *first;
1740 - struct avl_node *last;
1741 - unsigned int count;
1742 - avl_tree_comp comp;
1743 -};
1744 -
1745 -#define AVL_DUP 1
1746 -#define AVL_DUP_NO 0
1747 -
1748 -void avl_init(struct avl_tree *, avl_tree_comp);
1749 -struct avl_node *avl_find(struct avl_tree *, const void *);
1750 -int avl_insert(struct avl_tree *, struct avl_node *, int);
1751 -void avl_delete(struct avl_tree *, struct avl_node *);
1752 -
1753 -static INLINE struct avl_node *
1754 -avl_walk_first(struct avl_tree *tree)
1755 -{
1756 - if (!tree) {
1757 - return NULL;
1758 - }
1759 -
1760 - return tree->first;
1761 -}
1762 -static INLINE struct avl_node *
1763 -avl_walk_last(struct avl_tree *tree)
1764 -{
1765 - if (!tree) {
1766 - return NULL;
1767 - }
1768 -
1769 - return tree->last;
1770 -}
1771 -static INLINE struct avl_node *
1772 -avl_walk_next(struct avl_node *node)
1773 -{
1774 - if (!node) {
1775 - return NULL;
1776 - }
1777 -
1778 - return node->next;
1779 -}
1780 -static INLINE struct avl_node *
1781 -avl_walk_prev(struct avl_node *node)
1782 -{
1783 - if (!node) {
1784 - return NULL;
1785 - }
1786 -
1787 - return node->prev;
1788 -}
1789 -
1790 -/* and const versions*/
1791 -static INLINE const struct avl_node *
1792 -avl_walk_first_c(const struct avl_tree *tree)
1793 -{
1794 - if (!tree) {
1795 - return NULL;
1796 - }
1797 -
1798 - return tree->first;
1799 -}
1800 -static INLINE const struct avl_node *
1801 -avl_walk_last_c(const struct avl_tree *tree)
1802 -{
1803 - if (!tree) {
1804 - return NULL;
1805 - }
1806 -
1807 - return tree->last;
1808 -}
1809 -static INLINE const struct avl_node *
1810 -avl_walk_next_c(const struct avl_node *node)
1811 -{
1812 - if (!node) {
1813 - return NULL;
1814 - }
1815 -
1816 - return node->next;
1817 -}
1818 -static INLINE const struct avl_node *
1819 -avl_walk_prev_c(const struct avl_node *node)
1820 -{
1821 - if (!node) {
1822 - return NULL;
1823 - }
1824 -
1825 - return node->prev;
1826 -}
1827 -
1828 -extern avl_tree_comp avl_comp_default;
1829 -extern avl_tree_comp avl_comp_prefix_default;
1830 -extern int avl_comp_ipv4(const void *, const void *);
1831 -extern int avl_comp_ipv6(const void *, const void *);
1832 -extern int avl_comp_mac(const void *, const void *);
1833 -
1834 -/*
1835 - * Macro to define an INLINE function to map from a list_node offset back to the
1836 - * base of the datastructure. That way you save an extra data pointer.
1837 - */
1838 -#define AVLNODE2STRUCT(funcname, structname, avlnodename) \
1839 -static INLINE structname * funcname (struct avl_node *ptr)\
1840 -{\
1841 - return( \
1842 - ptr ? \
1843 - (structname *) (((size_t) ptr) - offsetof(structname, avlnodename)) : \
1844 - NULL); \
1845 -}
1846 -
1847 -#endif /* _AVL_H */
1848 -
1849 -/*
1850 - * Local Variables:
1851 - * c-basic-offset: 2
1852 - * indent-tabs-mode: nil
1853 - * End:
1854 - */
1855 --- /dev/null
1856 +++ b/src/common/olsrd_avl.h
1857 @@ -0,0 +1,183 @@
1858 +/*
1859 + * The olsr.org Optimized Link-State Routing daemon (olsrd)
1860 + *
1861 + * (c) by the OLSR project
1862 + *
1863 + * See our Git repository to find out who worked on this file
1864 + * and thus is a copyright holder on it.
1865 + *
1866 + * All rights reserved.
1867 + *
1868 + * Redistribution and use in source and binary forms, with or without
1869 + * modification, are permitted provided that the following conditions
1870 + * are met:
1871 + *
1872 + * * Redistributions of source code must retain the above copyright
1873 + * notice, this list of conditions and the following disclaimer.
1874 + * * Redistributions in binary form must reproduce the above copyright
1875 + * notice, this list of conditions and the following disclaimer in
1876 + * the documentation and/or other materials provided with the
1877 + * distribution.
1878 + * * Neither the name of olsr.org, olsrd nor the names of its
1879 + * contributors may be used to endorse or promote products derived
1880 + * from this software without specific prior written permission.
1881 + *
1882 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1883 + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1884 + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
1885 + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
1886 + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
1887 + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
1888 + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
1889 + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1890 + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1891 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
1892 + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1893 + * POSSIBILITY OF SUCH DAMAGE.
1894 + *
1895 + * Visit http://www.olsr.org for more information.
1896 + *
1897 + * If you find this software useful feel free to make a donation
1898 + * to the project. For more information see the website or contact
1899 + * the copyright holders.
1900 + *
1901 + */
1902 +
1903 +#ifndef _OLSRD_AVL_H
1904 +#define _OLSRD_AVL_H
1905 +
1906 +#include <stddef.h>
1907 +#include "compiler.h"
1908 +#include "defs.h"
1909 +
1910 +struct olsrd_avl_node {
1911 + struct olsrd_avl_node *parent;
1912 + struct olsrd_avl_node *left;
1913 + struct olsrd_avl_node *right;
1914 + struct olsrd_avl_node *next;
1915 + struct olsrd_avl_node *prev;
1916 + void *key;
1917 + signed char balance;
1918 + unsigned char leader;
1919 +};
1920 +
1921 +typedef int (*olsrd_avl_tree_comp) (const void *, const void *);
1922 +
1923 +struct olsrd_avl_tree {
1924 + struct olsrd_avl_node *root;
1925 + struct olsrd_avl_node *first;
1926 + struct olsrd_avl_node *last;
1927 + unsigned int count;
1928 + olsrd_avl_tree_comp comp;
1929 +};
1930 +
1931 +#define OLSRD_AVL_DUP 1
1932 +#define OLSRD_AVL_DUP_NO 0
1933 +
1934 +void olsrd_avl_init(struct olsrd_avl_tree *, olsrd_avl_tree_comp);
1935 +struct olsrd_avl_node *olsrd_avl_find(struct olsrd_avl_tree *, const void *);
1936 +int olsrd_avl_insert(struct olsrd_avl_tree *, struct olsrd_avl_node *, int);
1937 +void olsrd_avl_delete(struct olsrd_avl_tree *, struct olsrd_avl_node *);
1938 +
1939 +static INLINE struct olsrd_avl_node *
1940 +olsrd_avl_walk_first(struct olsrd_avl_tree *tree)
1941 +{
1942 + if (!tree) {
1943 + return NULL;
1944 + }
1945 +
1946 + return tree->first;
1947 +}
1948 +static INLINE struct olsrd_avl_node *
1949 +olsrd_avl_walk_last(struct olsrd_avl_tree *tree)
1950 +{
1951 + if (!tree) {
1952 + return NULL;
1953 + }
1954 +
1955 + return tree->last;
1956 +}
1957 +static INLINE struct olsrd_avl_node *
1958 +olsrd_avl_walk_next(struct olsrd_avl_node *node)
1959 +{
1960 + if (!node) {
1961 + return NULL;
1962 + }
1963 +
1964 + return node->next;
1965 +}
1966 +static INLINE struct olsrd_avl_node *
1967 +olsrd_avl_walk_prev(struct olsrd_avl_node *node)
1968 +{
1969 + if (!node) {
1970 + return NULL;
1971 + }
1972 +
1973 + return node->prev;
1974 +}
1975 +
1976 +/* and const versions*/
1977 +static INLINE const struct olsrd_avl_node *
1978 +olsrd_avl_walk_first_c(const struct olsrd_avl_tree *tree)
1979 +{
1980 + if (!tree) {
1981 + return NULL;
1982 + }
1983 +
1984 + return tree->first;
1985 +}
1986 +static INLINE const struct olsrd_avl_node *
1987 +olsrd_avl_walk_last_c(const struct olsrd_avl_tree *tree)
1988 +{
1989 + if (!tree) {
1990 + return NULL;
1991 + }
1992 +
1993 + return tree->last;
1994 +}
1995 +static INLINE const struct olsrd_avl_node *
1996 +olsrd_avl_walk_next_c(const struct olsrd_avl_node *node)
1997 +{
1998 + if (!node) {
1999 + return NULL;
2000 + }
2001 +
2002 + return node->next;
2003 +}
2004 +static INLINE const struct olsrd_avl_node *
2005 +olsrd_avl_walk_prev_c(const struct olsrd_avl_node *node)
2006 +{
2007 + if (!node) {
2008 + return NULL;
2009 + }
2010 +
2011 + return node->prev;
2012 +}
2013 +
2014 +extern olsrd_avl_tree_comp olsrd_avl_comp_default;
2015 +extern olsrd_avl_tree_comp olsrd_avl_comp_prefix_default;
2016 +extern int olsrd_avl_comp_ipv4(const void *, const void *);
2017 +extern int olsrd_avl_comp_ipv6(const void *, const void *);
2018 +extern int olsrd_avl_comp_mac(const void *, const void *);
2019 +
2020 +/*
2021 + * Macro to define an INLINE function to map from a list_node offset back to the
2022 + * base of the datastructure. That way you save an extra data pointer.
2023 + */
2024 +#define OLSRD_AVLNODE2STRUCT(funcname, structname, olsrd_avlnodename) \
2025 +static INLINE structname * funcname (struct olsrd_avl_node *ptr)\
2026 +{\
2027 + return( \
2028 + ptr ? \
2029 + (structname *) (((size_t) ptr) - offsetof(structname, olsrd_avlnodename)) : \
2030 + NULL); \
2031 +}
2032 +
2033 +#endif /* _OLSRD_AVL_H */
2034 +
2035 +/*
2036 + * Local Variables:
2037 + * c-basic-offset: 2
2038 + * indent-tabs-mode: nil
2039 + * End:
2040 + */
2041 --- a/src/duplicate_set.c
2042 +++ b/src/duplicate_set.c
2043 @@ -45,7 +45,7 @@
2044
2045 #include "duplicate_set.h"
2046 #include "ipcalc.h"
2047 -#include "common/avl.h"
2048 +#include "common/olsrd_avl.h"
2049 #include "olsr.h"
2050 #include "mid_set.h"
2051 #include "scheduler.h"
2052 @@ -53,13 +53,13 @@
2053
2054 static void olsr_cleanup_duplicate_entry(void *unused);
2055
2056 -struct avl_tree duplicate_set;
2057 +struct olsrd_avl_tree duplicate_set;
2058 struct timer_entry *duplicate_cleanup_timer;
2059
2060 void
2061 olsr_init_duplicate_set(void)
2062 {
2063 - avl_init(&duplicate_set, olsr_cnf->ip_version == AF_INET ? &avl_comp_ipv4 : &avl_comp_ipv6);
2064 + olsrd_avl_init(&duplicate_set, olsr_cnf->ip_version == AF_INET ? &olsrd_avl_comp_ipv4 : &olsrd_avl_comp_ipv6);
2065
2066 olsr_set_timer(&duplicate_cleanup_timer, DUPLICATE_CLEANUP_INTERVAL, DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_PERIODIC,
2067 &olsr_cleanup_duplicate_entry, NULL, 0);
2068 @@ -68,7 +68,7 @@ olsr_init_duplicate_set(void)
2069 void olsr_cleanup_duplicates(union olsr_ip_addr *orig) {
2070 struct dup_entry *entry;
2071
2072 - entry = (struct dup_entry *)avl_find(&duplicate_set, orig);
2073 + entry = (struct dup_entry *)olsrd_avl_find(&duplicate_set, orig);
2074 if (entry != NULL) {
2075 entry->too_low_counter = DUP_MAX_TOO_LOW - 2;
2076 }
2077 @@ -83,7 +83,7 @@ olsr_create_duplicate_entry(void *ip, ui
2078 memcpy(&entry->ip, ip, olsr_cnf->ip_version == AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
2079 entry->seqnr = seqnr;
2080 entry->too_low_counter = 0;
2081 - entry->avl.key = &entry->ip;
2082 + entry->olsrd_avl.key = &entry->ip;
2083 entry->array = 0;
2084 }
2085 return entry;
2086 @@ -96,7 +96,7 @@ olsr_cleanup_duplicate_entry(void __attr
2087
2088 OLSR_FOR_ALL_DUP_ENTRIES(entry) {
2089 if (TIMED_OUT(entry->valid_until)) {
2090 - avl_delete(&duplicate_set, &entry->avl);
2091 + olsrd_avl_delete(&duplicate_set, &entry->olsrd_avl);
2092 free(entry);
2093 }
2094 }
2095 @@ -143,11 +143,11 @@ olsr_message_is_duplicate(union olsr_mes
2096
2097 valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
2098
2099 - entry = (struct dup_entry *)avl_find(&duplicate_set, ip);
2100 + entry = (struct dup_entry *)olsrd_avl_find(&duplicate_set, ip);
2101 if (entry == NULL) {
2102 entry = olsr_create_duplicate_entry(ip, seqnr);
2103 if (entry != NULL) {
2104 - avl_insert(&duplicate_set, &entry->avl, 0);
2105 + olsrd_avl_insert(&duplicate_set, &entry->olsrd_avl, 0);
2106 entry->valid_until = valid_until;
2107 }
2108 return false; // okay, we process this package
2109 @@ -209,7 +209,7 @@ olsr_print_duplicate_table(void)
2110 olsr_wallclock_string(), ipwidth, "Node IP", "DupArray", "VTime");
2111
2112 OLSR_FOR_ALL_DUP_ENTRIES(entry) {
2113 - OLSR_PRINTF(1, "%-*s %08x %s\n", ipwidth, olsr_ip_to_string(&addrbuf, (union olsr_ip_addr *)(entry->avl.key)),
2114 + OLSR_PRINTF(1, "%-*s %08x %s\n", ipwidth, olsr_ip_to_string(&addrbuf, (union olsr_ip_addr *)(entry->olsrd_avl.key)),
2115 entry->array, olsr_clock_string(entry->valid_until));
2116 } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
2117 }
2118 --- a/src/duplicate_set.h
2119 +++ b/src/duplicate_set.h
2120 @@ -49,7 +49,7 @@
2121 #include "defs.h"
2122 #include "olsr.h"
2123 #include "mantissa.h"
2124 -#include "common/avl.h"
2125 +#include "common/olsrd_avl.h"
2126
2127 #define DUPLICATE_CLEANUP_INTERVAL 15000
2128 #define DUPLICATE_CLEANUP_JITTER 25
2129 @@ -57,7 +57,7 @@
2130 #define DUP_MAX_TOO_LOW 16
2131
2132 struct dup_entry {
2133 - struct avl_node avl;
2134 + struct olsrd_avl_node olsrd_avl;
2135 union olsr_ip_addr ip;
2136 uint16_t seqnr;
2137 uint16_t too_low_counter;
2138 @@ -65,7 +65,7 @@ struct dup_entry {
2139 uint32_t valid_until;
2140 };
2141
2142 -AVLNODE2STRUCT(duptree2dupentry, struct dup_entry, avl);
2143 +OLSRD_AVLNODE2STRUCT(duptree2dupentry, struct dup_entry, olsrd_avl);
2144
2145 void olsr_init_duplicate_set(void);
2146 void olsr_cleanup_duplicates(union olsr_ip_addr *orig);
2147 @@ -80,10 +80,10 @@ void olsr_print_duplicate_table(void);
2148
2149 #define OLSR_FOR_ALL_DUP_ENTRIES(dup) \
2150 { \
2151 - struct avl_node *dup_tree_node, *next_dup_tree_node; \
2152 - for (dup_tree_node = avl_walk_first(&duplicate_set); \
2153 + struct olsrd_avl_node *dup_tree_node, *next_dup_tree_node; \
2154 + for (dup_tree_node = olsrd_avl_walk_first(&duplicate_set); \
2155 dup_tree_node; dup_tree_node = next_dup_tree_node) { \
2156 - next_dup_tree_node = avl_walk_next(dup_tree_node); \
2157 + next_dup_tree_node = olsrd_avl_walk_next(dup_tree_node); \
2158 dup = duptree2dupentry(dup_tree_node);
2159 #define OLSR_FOR_ALL_DUP_ENTRIES_END(dup) }}
2160
2161 --- a/src/gateway.c
2162 +++ b/src/gateway.c
2163 @@ -45,7 +45,7 @@
2164
2165 #ifdef __linux__
2166
2167 -#include "common/avl.h"
2168 +#include "common/olsrd_avl.h"
2169 #include "defs.h"
2170 #include "ipcalc.h"
2171 #include "olsr.h"
2172 @@ -89,7 +89,7 @@ static struct olsr_ip_prefix ipv4_slash_
2173 static struct olsr_ip_prefix ipv4_slash_1_routes[2];
2174
2175 /** the gateway tree */
2176 -struct avl_tree gateway_tree;
2177 +struct olsrd_avl_tree gateway_tree;
2178
2179 /** gateway cookie */
2180 static struct olsr_cookie_info *gateway_entry_mem_cookie = NULL;
2181 @@ -713,7 +713,7 @@ static void cleanup_gateway_handler(void
2182 }
2183
2184 /* remove gateway entry */
2185 - avl_delete(&gateway_tree, &gw->node);
2186 + olsrd_avl_delete(&gateway_tree, &gw->node);
2187 olsr_cookie_free(gateway_entry_mem_cookie, gw);
2188 }
2189
2190 @@ -837,7 +837,7 @@ int olsr_init_gateways(void) {
2191 gw_container_entry_mem_cookie = olsr_alloc_cookie("gw_container_entry_mem_cookie", OLSR_COOKIE_TYPE_MEMORY);
2192 olsr_cookie_set_memory_size(gw_container_entry_mem_cookie, sizeof(struct gw_container_entry));
2193
2194 - avl_init(&gateway_tree, avl_comp_default);
2195 + olsrd_avl_init(&gateway_tree, olsrd_avl_comp_default);
2196
2197 olsr_gw_list_init(&gw_list_ipv4, olsr_cnf->smart_gw_use_count);
2198 olsr_gw_list_init(&gw_list_ipv6, olsr_cnf->smart_gw_use_count);
2199 @@ -1078,7 +1078,7 @@ void olsr_cleanup_gateways(void) {
2200 OLSR_FOR_ALL_GWS_END(gw);
2201
2202 /* there should be no more gateways */
2203 - assert(!avl_walk_first(&gateway_tree));
2204 + assert(!olsrd_avl_walk_first(&gateway_tree));
2205 assert(!current_ipv4_gw);
2206 assert(!current_ipv6_gw);
2207
2208 @@ -1244,14 +1244,14 @@ void olsr_update_gateway_entry(union ols
2209 struct gw_container_entry * new_gw_in_list;
2210 uint8_t *ptr;
2211 int64_t prev_path_cost = 0;
2212 - struct gateway_entry *gw = node2gateway(avl_find(&gateway_tree, originator));
2213 + struct gateway_entry *gw = node2gateway(olsrd_avl_find(&gateway_tree, originator));
2214
2215 if (!gw) {
2216 gw = olsr_cookie_malloc(gateway_entry_mem_cookie);
2217 gw->originator = *originator;
2218 gw->node.key = &gw->originator;
2219
2220 - avl_insert(&gateway_tree, &gw->node, AVL_DUP_NO);
2221 + olsrd_avl_insert(&gateway_tree, &gw->node, OLSRD_AVL_DUP_NO);
2222 } else if (olsr_seqno_diff(seqno, gw->seqno) <= 0) {
2223 /* ignore older HNAs */
2224 return;
2225 @@ -1353,7 +1353,7 @@ void olsr_update_gateway_entry(union ols
2226 * gateway tree immediately, else it is removed on a delayed schedule.
2227 */
2228 void olsr_delete_gateway_entry(union olsr_ip_addr *originator, uint8_t prefixlen, bool immediate) {
2229 - olsr_delete_gateway_tree_entry(node2gateway(avl_find(&gateway_tree, originator)), prefixlen, immediate);
2230 + olsr_delete_gateway_tree_entry(node2gateway(olsrd_avl_find(&gateway_tree, originator)), prefixlen, immediate);
2231 }
2232
2233 /**
2234 @@ -1526,7 +1526,7 @@ bool olsr_set_inet_gateway(struct gatewa
2235 return true;
2236 }
2237
2238 - new_gw = node2gateway(avl_find(&gateway_tree, &chosen_gw->originator));
2239 + new_gw = node2gateway(olsrd_avl_find(&gateway_tree, &chosen_gw->originator));
2240 if (!new_gw) {
2241 /* the originator is not in the gateway tree, we can't set it as gateway */
2242 return true;
2243 --- a/src/gateway.h
2244 +++ b/src/gateway.h
2245 @@ -46,7 +46,7 @@
2246 #ifndef GATEWAY_H_
2247 #define GATEWAY_H_
2248
2249 -#include "common/avl.h"
2250 +#include "common/olsrd_avl.h"
2251 #include "common/list.h"
2252 #include "defs.h"
2253 #include "olsr.h"
2254 @@ -96,7 +96,7 @@ enum gateway_hna_fields {
2255
2256 /** a gateway entry */
2257 struct gateway_entry {
2258 - struct avl_node node;
2259 + struct olsrd_avl_node node;
2260 union olsr_ip_addr originator;
2261 struct olsr_ip_prefix external_prefix;
2262 uint32_t uplink;
2263 @@ -129,27 +129,27 @@ struct interfaceName {
2264 #endif /* __linux__ */
2265
2266 /**
2267 - * static INLINE struct gateway_entry * node2gateway (struct avl_node *ptr)
2268 + * static INLINE struct gateway_entry * node2gateway (struct olsrd_avl_node *ptr)
2269 *
2270 * Converts a node into a gateway entry
2271 */
2272 -AVLNODE2STRUCT(node2gateway, struct gateway_entry, node);
2273 +OLSRD_AVLNODE2STRUCT(node2gateway, struct gateway_entry, node);
2274
2275 /**
2276 * Loop over all gateway entries and put the iterated gateway entry in gw
2277 */
2278 #define OLSR_FOR_ALL_GATEWAY_ENTRIES(gw) \
2279 { \
2280 - struct avl_node *gw_node, *next_gw_node; \
2281 - for (gw_node = avl_walk_first(&gateway_tree); \
2282 + struct olsrd_avl_node *gw_node, *next_gw_node; \
2283 + for (gw_node = olsrd_avl_walk_first(&gateway_tree); \
2284 gw_node; gw_node = next_gw_node) { \
2285 - next_gw_node = avl_walk_next(gw_node); \
2286 + next_gw_node = olsrd_avl_walk_next(gw_node); \
2287 gw = node2gateway(gw_node); \
2288 if (gw) {
2289 #define OLSR_FOR_ALL_GATEWAY_ENTRIES_END(gw) }}}
2290
2291 /** the gateway tree */
2292 -extern struct avl_tree gateway_tree;
2293 +extern struct olsrd_avl_tree gateway_tree;
2294
2295 /** the list IPv4 gateways */
2296 extern struct gw_list gw_list_ipv4;
2297 --- a/src/kernel_tunnel.h
2298 +++ b/src/kernel_tunnel.h
2299 @@ -55,7 +55,7 @@
2300
2301 #include "defs.h"
2302 #include "olsr_types.h"
2303 -#include "common/avl.h"
2304 +#include "common/olsrd_avl.h"
2305
2306 #define TUNNEL_ENDPOINT_IF "tunl0"
2307 #define TUNNEL_ENDPOINT_IF6 "ip6tnl0"
2308 @@ -67,7 +67,7 @@
2309 #endif
2310
2311 struct olsr_iptunnel_entry {
2312 - struct avl_node node;
2313 + struct olsrd_avl_node node;
2314 union olsr_ip_addr target;
2315
2316 char if_name[IF_NAMESIZE];
2317 --- a/src/linux/kernel_tunnel.c
2318 +++ b/src/linux/kernel_tunnel.c
2319 @@ -84,12 +84,12 @@
2320
2321 static bool store_iptunnel_state;
2322 static struct olsr_cookie_info *tunnel_cookie;
2323 -static struct avl_tree tunnel_tree;
2324 +static struct olsrd_avl_tree tunnel_tree;
2325
2326 int olsr_os_init_iptunnel(const char * dev) {
2327 tunnel_cookie = olsr_alloc_cookie("iptunnel", OLSR_COOKIE_TYPE_MEMORY);
2328 olsr_cookie_set_memory_size(tunnel_cookie, sizeof(struct olsr_iptunnel_entry));
2329 - avl_init(&tunnel_tree, avl_comp_default);
2330 + olsrd_avl_init(&tunnel_tree, olsrd_avl_comp_default);
2331
2332 store_iptunnel_state = olsr_if_isup(dev);
2333 if (store_iptunnel_state) {
2334 @@ -107,7 +107,7 @@ void olsr_os_cleanup_iptunnel(const char
2335 struct olsr_iptunnel_entry *t;
2336
2337 /* kill tunnel */
2338 - t = (struct olsr_iptunnel_entry *)avl_walk_first(&tunnel_tree);
2339 + t = (struct olsr_iptunnel_entry *)olsrd_avl_walk_first(&tunnel_tree);
2340 t->usage = 1;
2341
2342 olsr_os_del_ipip_tunnel(t);
2343 @@ -201,7 +201,7 @@ struct olsr_iptunnel_entry *olsr_os_add_
2344
2345 assert(olsr_cnf->ip_version == AF_INET6 || transportV4);
2346
2347 - t = (struct olsr_iptunnel_entry *)avl_find(&tunnel_tree, target);
2348 + t = (struct olsr_iptunnel_entry *)olsrd_avl_find(&tunnel_tree, target);
2349 if (t == NULL) {
2350 int if_idx;
2351 struct ipaddr_str buf;
2352 @@ -228,7 +228,7 @@ struct olsr_iptunnel_entry *olsr_os_add_
2353 strscpy(t->if_name, name, sizeof(t->if_name));
2354 t->if_index = if_idx;
2355
2356 - avl_insert(&tunnel_tree, &t->node, AVL_DUP_NO);
2357 + olsrd_avl_insert(&tunnel_tree, &t->node, OLSRD_AVL_DUP_NO);
2358 }
2359
2360 t->usage++;
2361 @@ -253,7 +253,7 @@ void olsr_os_del_ipip_tunnel(struct olsr
2362 olsr_if_set_state(t->if_name, false);
2363 os_ip_tunnel(t->if_name, NULL);
2364
2365 - avl_delete(&tunnel_tree, &t->node);
2366 + olsrd_avl_delete(&tunnel_tree, &t->node);
2367 olsr_cookie_free(tunnel_cookie, t);
2368 }
2369 #endif /* __linux__ */
2370 --- a/src/lq_packet.c
2371 +++ b/src/lq_packet.c
2372 @@ -272,16 +272,16 @@ create_lq_tc(struct lq_tc_message *lq_tc
2373
2374 /* Queue the neighbour entry. */
2375
2376 - // TODO: ugly hack until neighbor table is ported to avl tree
2377 + // TODO: ugly hack until neighbor table is ported to olsrd_avl tree
2378
2379 - if (lq_tc->neigh == NULL || avl_comp_default(&lq_tc->neigh->address, &neigh->address) > 0) {
2380 + if (lq_tc->neigh == NULL || olsrd_avl_comp_default(&lq_tc->neigh->address, &neigh->address) > 0) {
2381 neigh->next = lq_tc->neigh;
2382 lq_tc->neigh = neigh;
2383 } else {
2384 struct tc_mpr_addr *last = lq_tc->neigh, *n = last->next;
2385
2386 while (n) {
2387 - if (avl_comp_default(&n->address, &neigh->address) > 0) {
2388 + if (olsrd_avl_comp_default(&n->address, &neigh->address) > 0) {
2389 break;
2390 }
2391 last = n;
2392 --- a/src/lq_plugin.c
2393 +++ b/src/lq_plugin.c
2394 @@ -50,7 +50,7 @@
2395 #include "packet.h"
2396 #include "olsr.h"
2397 #include "two_hop_neighbor_table.h"
2398 -#include "common/avl.h"
2399 +#include "common/olsrd_avl.h"
2400
2401 #include "lq_plugin_default_float.h"
2402 #include "lq_plugin_default_fpm.h"
2403 @@ -64,17 +64,17 @@
2404 #include <assert.h>
2405 #include <math.h>
2406
2407 -struct avl_tree lq_handler_tree;
2408 +struct olsrd_avl_tree lq_handler_tree;
2409 struct lq_handler *active_lq_handler = NULL;
2410
2411 /**
2412 - * case-insensitive string comparator for avl-trees
2413 + * case-insensitive string comparator for olsrd_avl-trees
2414 * @param str1
2415 * @param str2
2416 * @return
2417 */
2418 int
2419 -avl_strcasecmp(const void *str1, const void *str2)
2420 +olsrd_avl_strcasecmp(const void *str1, const void *str2)
2421 {
2422 return strcasecmp(str1, str2);
2423 }
2424 @@ -88,7 +88,7 @@ activate_lq_handler(const char *name)
2425 {
2426 struct lq_handler_node *node;
2427
2428 - node = (struct lq_handler_node *)avl_find(&lq_handler_tree, name);
2429 + node = (struct lq_handler_node *)olsrd_avl_find(&lq_handler_tree, name);
2430 if (node == NULL) {
2431 char buf[1024];
2432 snprintf(buf, sizeof(buf), "Error, unknown lq_handler '%s'", name);
2433 @@ -106,7 +106,7 @@ activate_lq_handler(const char *name)
2434 void
2435 init_lq_handler_tree(void)
2436 {
2437 - avl_init(&lq_handler_tree, &avl_strcasecmp);
2438 + olsrd_avl_init(&lq_handler_tree, &olsrd_avl_strcasecmp);
2439 register_lq_handler(&lq_etx_float_handler, LQ_ALGORITHM_ETX_FLOAT_NAME);
2440 register_lq_handler(&lq_etx_fpm_handler, LQ_ALGORITHM_ETX_FPM_NAME);
2441 register_lq_handler(&lq_etx_ff_handler, LQ_ALGORITHM_ETX_FF_NAME);
2442 @@ -147,7 +147,7 @@ register_lq_handler(struct lq_handler *h
2443 node->node.key = node->name;
2444 node->handler = handler;
2445
2446 - avl_insert(&lq_handler_tree, &node->node, false);
2447 + olsrd_avl_insert(&lq_handler_tree, &node->node, false);
2448 }
2449
2450 /**
2451 --- a/src/lq_plugin.h
2452 +++ b/src/lq_plugin.h
2453 @@ -51,7 +51,7 @@
2454 #include "olsr_spf.h"
2455 #include "lq_packet.h"
2456 #include "packet.h"
2457 -#include "common/avl.h"
2458 +#include "common/olsrd_avl.h"
2459
2460 #define LINK_COST_BROKEN (1u<<22)
2461 #define ROUTE_COST_BROKEN (0xffffffffu)
2462 @@ -97,23 +97,23 @@ struct lq_handler {
2463 };
2464
2465 struct lq_handler_node {
2466 - struct avl_node node;
2467 + struct olsrd_avl_node node;
2468 struct lq_handler *handler;
2469 char name[0];
2470 };
2471
2472 -AVLNODE2STRUCT(lq_handler_tree2lq_handler_node, struct lq_handler_node, node);
2473 +OLSRD_AVLNODE2STRUCT(lq_handler_tree2lq_handler_node, struct lq_handler_node, node);
2474
2475 #define OLSR_FOR_ALL_LQ_HANDLERS(lq) \
2476 { \
2477 - struct avl_node *lq_tree_node, *next_lq_tree_node; \
2478 - for (lq_tree_node = avl_walk_first(&lq_handler_tree); \
2479 + struct olsrd_avl_node *lq_tree_node, *next_lq_tree_node; \
2480 + for (lq_tree_node = olsrd_avl_walk_first(&lq_handler_tree); \
2481 lq_tree_node; lq_tree_node = next_lq_tree_node) { \
2482 - next_lq_tree_node = avl_walk_next(lq_tree_node); \
2483 + next_lq_tree_node = olsrd_avl_walk_next(lq_tree_node); \
2484 lq = lq_handler_tree2lq_handler_node(lq_tree_node);
2485 #define OLSR_FOR_ALL_LQ_HANDLERS_END(tc) }}
2486
2487 -int avl_strcasecmp(const void *str1, const void *str2);
2488 +int olsrd_avl_strcasecmp(const void *str1, const void *str2);
2489 void init_lq_handler_tree(void);
2490
2491 void register_lq_handler(struct lq_handler *handler, const char *name);
2492 --- a/src/olsr.c
2493 +++ b/src/olsr.c
2494 @@ -65,7 +65,7 @@
2495 #include "neighbor_table.h"
2496 #include "log.h"
2497 #include "lq_packet.h"
2498 -#include "common/avl.h"
2499 +#include "common/olsrd_avl.h"
2500 #include "net_olsr.h"
2501 #include "lq_plugin.h"
2502 #include "gateway.h"
2503 @@ -260,13 +260,13 @@ olsr_init_tables(void)
2504 changes_neighborhood = false;
2505 changes_hna = false;
2506
2507 - /* Set avl tree comparator */
2508 + /* Set olsrd_avl tree comparator */
2509 if (olsr_cnf->ipsize == 4) {
2510 - avl_comp_default = avl_comp_ipv4;
2511 - avl_comp_prefix_default = avl_comp_ipv4_prefix;
2512 + olsrd_avl_comp_default = olsrd_avl_comp_ipv4;
2513 + olsrd_avl_comp_prefix_default = olsrd_avl_comp_ipv4_prefix;
2514 } else {
2515 - avl_comp_default = avl_comp_ipv6;
2516 - avl_comp_prefix_default = avl_comp_ipv6_prefix;
2517 + olsrd_avl_comp_default = olsrd_avl_comp_ipv6;
2518 + olsrd_avl_comp_prefix_default = olsrd_avl_comp_ipv6_prefix;
2519 }
2520
2521 /* Initialize lq plugin set */
2522 --- a/src/olsr_spf.c
2523 +++ b/src/olsr_spf.c
2524 @@ -47,7 +47,7 @@
2525 * Implementation of Dijkstras algorithm. Initially all nodes
2526 * are initialized to infinite cost. First we put ourselves
2527 * on the heap of reachable nodes. Our heap implementation
2528 - * is based on an AVL tree which gives interesting performance
2529 + * is based on an OLSRD_AVL tree which gives interesting performance
2530 * characteristics for the frequent operations of minimum key
2531 * extraction and re-keying. Next all neighbors of a node are
2532 * explored and put on the heap if the cost of reaching them is
2533 @@ -67,7 +67,7 @@
2534 #include "mid_set.h"
2535 #include "hna_set.h"
2536 #include "common/list.h"
2537 -#include "common/avl.h"
2538 +#include "common/olsrd_avl.h"
2539 #include "olsr_spf.h"
2540 #include "net_olsr.h"
2541 #include "lq_plugin.h"
2542 @@ -80,7 +80,7 @@
2543 struct timer_entry *spf_backoff_timer = NULL;
2544
2545 /*
2546 - * avl_comp_etx
2547 + * olsrd_avl_comp_etx
2548 *
2549 * compare two etx metrics.
2550 * return 0 if there is an exact match and
2551 @@ -89,7 +89,7 @@ struct timer_entry *spf_backoff_timer =
2552 * after compiler optimization.
2553 */
2554 static int
2555 -avl_comp_etx(const void *etx1, const void *etx2)
2556 +olsrd_avl_comp_etx(const void *etx1, const void *etx2)
2557 {
2558 if (*(const olsr_linkcost *)etx1 < *(const olsr_linkcost *)etx2) {
2559 return -1;
2560 @@ -108,7 +108,7 @@ avl_comp_etx(const void *etx1, const voi
2561 * Key an existing vertex to a candidate tree.
2562 */
2563 static void
2564 -olsr_spf_add_cand_tree(struct avl_tree *tree, struct tc_entry *tc)
2565 +olsr_spf_add_cand_tree(struct olsrd_avl_tree *tree, struct tc_entry *tc)
2566 {
2567 #if !defined(NODEBUG) && defined(DEBUG)
2568 struct ipaddr_str buf;
2569 @@ -121,7 +121,7 @@ olsr_spf_add_cand_tree(struct avl_tree *
2570 get_linkcost_text(tc->path_cost, true, &lqbuffer));
2571 #endif /* DEBUG */
2572
2573 - avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
2574 + olsrd_avl_insert(tree, &tc->cand_tree_node, OLSRD_AVL_DUP);
2575 }
2576
2577 /*
2578 @@ -130,7 +130,7 @@ olsr_spf_add_cand_tree(struct avl_tree *
2579 * Unkey an existing vertex from a candidate tree.
2580 */
2581 static void
2582 -olsr_spf_del_cand_tree(struct avl_tree *tree, struct tc_entry *tc)
2583 +olsr_spf_del_cand_tree(struct olsrd_avl_tree *tree, struct tc_entry *tc)
2584 {
2585
2586 #ifdef DEBUG
2587 @@ -142,7 +142,7 @@ olsr_spf_del_cand_tree(struct avl_tree *
2588 get_linkcost_text(tc->path_cost, true, &lqbuffer));
2589 #endif /* DEBUG */
2590
2591 - avl_delete(tree, &tc->cand_tree_node);
2592 + olsrd_avl_delete(tree, &tc->cand_tree_node);
2593 }
2594
2595 /*
2596 @@ -175,9 +175,9 @@ olsr_spf_add_path_list(struct list_node
2597 * return the node with the minimum pathcost.
2598 */
2599 static struct tc_entry *
2600 -olsr_spf_extract_best(struct avl_tree *tree)
2601 +olsr_spf_extract_best(struct olsrd_avl_tree *tree)
2602 {
2603 - struct avl_node *node = avl_walk_first(tree);
2604 + struct olsrd_avl_node *node = olsrd_avl_walk_first(tree);
2605
2606 return (node ? cand_tree2tc(node) : NULL);
2607 }
2608 @@ -190,9 +190,9 @@ olsr_spf_extract_best(struct avl_tree *t
2609 * path cost is better.
2610 */
2611 static void
2612 -olsr_spf_relax(struct avl_tree *cand_tree, struct tc_entry *tc)
2613 +olsr_spf_relax(struct olsrd_avl_tree *cand_tree, struct tc_entry *tc)
2614 {
2615 - struct avl_node *edge_node;
2616 + struct olsrd_avl_node *edge_node;
2617 olsr_linkcost new_cost;
2618
2619 #ifdef DEBUG
2620 @@ -207,7 +207,7 @@ olsr_spf_relax(struct avl_tree *cand_tre
2621 /*
2622 * loop through all edges of this vertex.
2623 */
2624 - for (edge_node = avl_walk_first(&tc->edge_tree); edge_node; edge_node = avl_walk_next(edge_node)) {
2625 + for (edge_node = olsrd_avl_walk_first(&tc->edge_tree); edge_node; edge_node = olsrd_avl_walk_next(edge_node)) {
2626
2627 struct tc_entry *new_tc;
2628 struct tc_edge_entry *tc_edge = edge_tree2tc_edge(edge_node);
2629 @@ -289,7 +289,7 @@ olsr_spf_relax(struct avl_tree *cand_tre
2630 * on the candidate tree.
2631 */
2632 static void
2633 -olsr_spf_run_full(struct avl_tree *cand_tree, struct list_node *path_list, int *path_count)
2634 +olsr_spf_run_full(struct olsrd_avl_tree *cand_tree, struct list_node *path_list, int *path_count)
2635 {
2636 struct tc_entry *tc;
2637
2638 @@ -335,8 +335,8 @@ olsr_calculate_routing_table(bool force)
2639 #ifdef SPF_PROFILING
2640 struct timespec t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
2641 #endif /* SPF_PROFILING */
2642 - struct avl_tree cand_tree;
2643 - struct avl_node *rtp_tree_node;
2644 + struct olsrd_avl_tree cand_tree;
2645 + struct olsrd_avl_node *rtp_tree_node;
2646 struct list_node path_list; /* head of the path_list */
2647 struct tc_entry *tc;
2648 struct rt_path *rtp;
2649 @@ -362,7 +362,7 @@ olsr_calculate_routing_table(bool force)
2650 /*
2651 * Prepare the candidate tree and result list.
2652 */
2653 - avl_init(&cand_tree, avl_comp_etx);
2654 + olsrd_avl_init(&cand_tree, olsrd_avl_comp_etx);
2655 list_head_init(&path_list);
2656 olsr_bump_routingtree_version();
2657
2658 @@ -493,7 +493,7 @@ olsr_calculate_routing_table(bool force)
2659 * If the prefix is already in the RIB, refresh the entry such
2660 * that olsr_delete_outdated_routes() does not purge it off.
2661 */
2662 - for (rtp_tree_node = avl_walk_first(&tc->prefix_tree); rtp_tree_node; rtp_tree_node = avl_walk_next(rtp_tree_node)) {
2663 + for (rtp_tree_node = olsrd_avl_walk_first(&tc->prefix_tree); rtp_tree_node; rtp_tree_node = olsrd_avl_walk_next(rtp_tree_node)) {
2664
2665 rtp = rtp_prefix_tree2rtp(rtp_tree_node);
2666
2667 --- a/src/process_routes.c
2668 +++ b/src/process_routes.c
2669 @@ -48,7 +48,7 @@
2670 #include "olsr.h"
2671 #include "log.h"
2672 #include "kernel_routes.h"
2673 -#include "common/avl.h"
2674 +#include "common/olsrd_avl.h"
2675 #include "net_olsr.h"
2676 #include "tc_set.h"
2677 #include "olsr_cookie.h"
2678 @@ -289,13 +289,13 @@ static void
2679 olsr_delete_outdated_routes(struct rt_entry *rt)
2680 {
2681 struct rt_path *rtp;
2682 - struct avl_node *rtp_tree_node, *next_rtp_tree_node;
2683 + struct olsrd_avl_node *rtp_tree_node, *next_rtp_tree_node;
2684
2685 - for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
2686 + for (rtp_tree_node = olsrd_avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
2687 /*
2688 * pre-fetch the next node before loosing context.
2689 */
2690 - next_rtp_tree_node = avl_walk_next(rtp_tree_node);
2691 + next_rtp_tree_node = olsrd_avl_walk_next(rtp_tree_node);
2692
2693 rtp = rtp_tree2rtp(rtp_tree_node);
2694
2695 @@ -305,7 +305,7 @@ olsr_delete_outdated_routes(struct rt_en
2696 */
2697 if (routingtree_version != rtp->rtp_version) {
2698 /* remove from the originator tree */
2699 - avl_delete(&rt->rt_path_tree, rtp_tree_node);
2700 + olsrd_avl_delete(&rt->rt_path_tree, rtp_tree_node);
2701 rtp->rtp_rt = NULL;
2702
2703 if (rt->rt_best == rtp) {
2704 @@ -341,7 +341,7 @@ olsr_update_rib_routes(void)
2705
2706 if (olsr_delete_kernel_route(rt) == 0) {
2707 /*only remove if deletion was successful*/
2708 - avl_delete(&routingtree, &rt->rt_tree_node);
2709 + olsrd_avl_delete(&routingtree, &rt->rt_tree_node);
2710 olsr_cookie_free(rt_mem_cookie, rt);
2711 }
2712
2713 @@ -370,21 +370,21 @@ olsr_delete_interface_routes(int if_inde
2714 OLSR_FOR_ALL_RT_ENTRIES(rt) {
2715 bool mightTrigger = false;
2716 struct rt_path *rtp;
2717 - struct avl_node *rtp_tree_node, *next_rtp_tree_node;
2718 + struct olsrd_avl_node *rtp_tree_node, *next_rtp_tree_node;
2719
2720 /* run through all routing paths of route */
2721 - for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
2722 + for (rtp_tree_node = olsrd_avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
2723 /*
2724 * pre-fetch the next node before loosing context.
2725 */
2726 - next_rtp_tree_node = avl_walk_next(rtp_tree_node);
2727 + next_rtp_tree_node = olsrd_avl_walk_next(rtp_tree_node);
2728
2729 rtp = rtp_tree2rtp(rtp_tree_node);
2730
2731 /* nexthop use lost interface ? */
2732 if (rtp->rtp_nexthop.iif_index == if_index) {
2733 /* remove from the originator tree */
2734 - avl_delete(&rt->rt_path_tree, rtp_tree_node);
2735 + olsrd_avl_delete(&rt->rt_path_tree, rtp_tree_node);
2736 rtp->rtp_rt = NULL;
2737
2738 if (rt->rt_best == rtp) {
2739 @@ -397,7 +397,7 @@ olsr_delete_interface_routes(int if_inde
2740 if (mightTrigger) {
2741 if (!rt->rt_path_tree.count) {
2742 /* oops, all routes are gone - flush the route head */
2743 - avl_delete(&routingtree, rt_tree_node);
2744 + olsrd_avl_delete(&routingtree, rt_tree_node);
2745
2746 /* do not dequeue route because they are already gone */
2747 }
2748 --- a/src/routing_table.c
2749 +++ b/src/routing_table.c
2750 @@ -52,7 +52,7 @@
2751 #include "neighbor_table.h"
2752 #include "olsr.h"
2753 #include "link_set.h"
2754 -#include "common/avl.h"
2755 +#include "common/olsrd_avl.h"
2756 #include "olsr_spf.h"
2757 #include "net_olsr.h"
2758
2759 @@ -72,7 +72,7 @@ struct olsr_cookie_info *rtp_mem_cookie
2760 static struct rt_path *current_inetgw = NULL;
2761
2762 /* Root of our RIB */
2763 -struct avl_tree routingtree;
2764 +struct olsrd_avl_tree routingtree;
2765
2766 /*
2767 * Keep a version number for detecting outdated elements
2768 @@ -95,7 +95,7 @@ olsr_bump_routingtree_version(void)
2769 }
2770
2771 /**
2772 - * avl_comp_ipv4_prefix
2773 + * olsrd_avl_comp_ipv4_prefix
2774 *
2775 * compare two ipv4 prefixes.
2776 * first compare the prefixes, then
2777 @@ -105,7 +105,7 @@ olsr_bump_routingtree_version(void)
2778 * -1 / +1 depending on being smaller or bigger.
2779 */
2780 int
2781 -avl_comp_ipv4_prefix(const void *prefix1, const void *prefix2)
2782 +olsrd_avl_comp_ipv4_prefix(const void *prefix1, const void *prefix2)
2783 {
2784 const struct olsr_ip_prefix *pfx1 = prefix1;
2785 const struct olsr_ip_prefix *pfx2 = prefix2;
2786 @@ -132,7 +132,7 @@ avl_comp_ipv4_prefix(const void *prefix1
2787 }
2788
2789 /**
2790 - * avl_comp_ipv6_prefix
2791 + * olsrd_avl_comp_ipv6_prefix
2792 *
2793 * compare two ipv6 prefixes.
2794 * first compare the prefixes, then
2795 @@ -142,7 +142,7 @@ avl_comp_ipv4_prefix(const void *prefix1
2796 * -1 / +1 depending on being smaller or bigger.
2797 */
2798 int
2799 -avl_comp_ipv6_prefix(const void *prefix1, const void *prefix2)
2800 +olsrd_avl_comp_ipv6_prefix(const void *prefix1, const void *prefix2)
2801 {
2802 int res;
2803 const struct olsr_ip_prefix *pfx1 = prefix1;
2804 @@ -173,7 +173,7 @@ olsr_init_routing_table(void)
2805 OLSR_PRINTF(5, "RIB: init routing tree\n");
2806
2807 /* the routing tree */
2808 - avl_init(&routingtree, avl_comp_prefix_default);
2809 + olsrd_avl_init(&routingtree, olsrd_avl_comp_prefix_default);
2810 routingtree_version = 0;
2811
2812 /*
2813 @@ -197,13 +197,13 @@ olsr_init_routing_table(void)
2814 struct rt_entry *
2815 olsr_lookup_routing_table(const union olsr_ip_addr *dst)
2816 {
2817 - struct avl_node *rt_tree_node;
2818 + struct olsrd_avl_node *rt_tree_node;
2819 struct olsr_ip_prefix prefix;
2820
2821 prefix.prefix = *dst;
2822 prefix.prefix_len = olsr_cnf->maxplen;
2823
2824 - rt_tree_node = avl_find(&routingtree, &prefix);
2825 + rt_tree_node = olsrd_avl_find(&routingtree, &prefix);
2826
2827 return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
2828 }
2829 @@ -248,10 +248,10 @@ olsr_alloc_rt_entry(struct olsr_ip_prefi
2830 rt->rt_dst = *prefix;
2831
2832 rt->rt_tree_node.key = &rt->rt_dst;
2833 - avl_insert(&routingtree, &rt->rt_tree_node, AVL_DUP_NO);
2834 + olsrd_avl_insert(&routingtree, &rt->rt_tree_node, OLSRD_AVL_DUP_NO);
2835
2836 /* init the originator subtree */
2837 - avl_init(&rt->rt_path_tree, avl_comp_default);
2838 + olsrd_avl_init(&rt->rt_path_tree, olsrd_avl_comp_default);
2839
2840 return rt;
2841 }
2842 @@ -276,7 +276,7 @@ olsr_alloc_rt_path(struct tc_entry *tc,
2843 rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
2844
2845 /* insert to the tc prefix tree */
2846 - avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
2847 + olsrd_avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, OLSRD_AVL_DUP_NO);
2848 olsr_lock_tc_entry(tc);
2849
2850 /* backlink to the owning tc entry */
2851 @@ -296,7 +296,7 @@ void
2852 olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
2853 {
2854 struct rt_entry *rt;
2855 - struct avl_node *node;
2856 + struct olsrd_avl_node *node;
2857
2858 /*
2859 * no unreachable routes please.
2860 @@ -315,7 +315,7 @@ olsr_insert_rt_path(struct rt_path *rtp,
2861 /*
2862 * first check if there is a route_entry for the prefix.
2863 */
2864 - node = avl_find(&routingtree, &rtp->rtp_dst);
2865 + node = olsrd_avl_find(&routingtree, &rtp->rtp_dst);
2866
2867 if (!node) {
2868
2869 @@ -337,7 +337,7 @@ olsr_insert_rt_path(struct rt_path *rtp,
2870 rtp->rtp_tree_node.key = &rtp->rtp_originator;
2871
2872 /* insert to the route entry originator tree */
2873 - avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
2874 + olsrd_avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, OLSRD_AVL_DUP_NO);
2875
2876 /* backlink to the owning route entry */
2877 rtp->rtp_rt = rt;
2878 @@ -356,13 +356,13 @@ olsr_delete_rt_path(struct rt_path *rtp)
2879
2880 /* remove from the originator tree */
2881 if (rtp->rtp_rt) {
2882 - avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
2883 + olsrd_avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
2884 rtp->rtp_rt = NULL;
2885 }
2886
2887 /* remove from the tc prefix tree */
2888 if (rtp->rtp_tc) {
2889 - avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
2890 + olsrd_avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
2891 olsr_unlock_tc_entry(rtp->rtp_tc);
2892 rtp->rtp_tc = NULL;
2893 }
2894 @@ -498,14 +498,14 @@ void
2895 olsr_rt_best(struct rt_entry *rt)
2896 {
2897 /* grab the first entry */
2898 - struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
2899 + struct olsrd_avl_node *node = olsrd_avl_walk_first(&rt->rt_path_tree);
2900
2901 assert(node != 0); /* should not happen */
2902
2903 rt->rt_best = rtp_tree2rtp(node);
2904
2905 /* walk all remaining originator entries */
2906 - while ((node = avl_walk_next(node))) {
2907 + while ((node = olsrd_avl_walk_next(node))) {
2908 struct rt_path *rtp = rtp_tree2rtp(node);
2909
2910 if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
2911 @@ -541,7 +541,7 @@ olsr_insert_routing_table(union olsr_ip_
2912 #endif /* DEBUG */
2913 struct tc_entry *tc;
2914 struct rt_path *rtp;
2915 - struct avl_node *node;
2916 + struct olsrd_avl_node *node;
2917 struct olsr_ip_prefix prefix;
2918
2919 /*
2920 @@ -567,7 +567,7 @@ olsr_insert_routing_table(union olsr_ip_
2921 prefix.prefix = *dst;
2922 prefix.prefix_len = plen;
2923
2924 - node = avl_find(&tc->prefix_tree, &prefix);
2925 + node = olsrd_avl_find(&tc->prefix_tree, &prefix);
2926
2927 if (!node) {
2928
2929 @@ -604,7 +604,7 @@ olsr_delete_routing_table(union olsr_ip_
2930
2931 struct tc_entry *tc;
2932 struct rt_path *rtp;
2933 - struct avl_node *node;
2934 + struct olsrd_avl_node *node;
2935 struct olsr_ip_prefix prefix;
2936
2937 /*
2938 @@ -625,7 +625,7 @@ olsr_delete_routing_table(union olsr_ip_
2939 prefix.prefix = *dst;
2940 prefix.prefix_len = plen;
2941
2942 - node = avl_find(&tc->prefix_tree, &prefix);
2943 + node = olsrd_avl_find(&tc->prefix_tree, &prefix);
2944
2945 if (node) {
2946 rtp = rtp_prefix_tree2rtp(node);
2947 @@ -682,16 +682,16 @@ olsr_rtp_to_string(const struct rt_path
2948 */
2949 #ifndef NODEBUG
2950 void
2951 -olsr_print_routing_table(struct avl_tree *tree)
2952 +olsr_print_routing_table(struct olsrd_avl_tree *tree)
2953 {
2954 /* The whole function makes no sense without it. */
2955 - struct avl_node *rt_tree_node;
2956 + struct olsrd_avl_node *rt_tree_node;
2957 struct lqtextbuffer lqbuffer;
2958
2959 OLSR_PRINTF(6, "ROUTING TABLE\n");
2960
2961 - for (rt_tree_node = avl_walk_first(tree); rt_tree_node != NULL; rt_tree_node = avl_walk_next(rt_tree_node)) {
2962 - struct avl_node *rtp_tree_node;
2963 + for (rt_tree_node = olsrd_avl_walk_first(tree); rt_tree_node != NULL; rt_tree_node = olsrd_avl_walk_next(rt_tree_node)) {
2964 + struct olsrd_avl_node *rtp_tree_node;
2965 struct ipaddr_str prefixstr, origstr, gwstr;
2966 struct rt_entry *rt = rt_tree2rt(rt_tree_node);
2967
2968 @@ -700,7 +700,7 @@ olsr_print_routing_table(struct avl_tree
2969 olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway), olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
2970
2971 /* walk the per-originator path tree of routes */
2972 - for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = avl_walk_next(rtp_tree_node)) {
2973 + for (rtp_tree_node = olsrd_avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = olsrd_avl_walk_next(rtp_tree_node)) {
2974 struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
2975 OLSR_PRINTF(6, "\tfrom %s, cost %s, metric %u, via %s, %s, v %u\n", olsr_ip_to_string(&origstr, &rtp->rtp_originator),
2976 get_linkcost_text(rtp->rtp_metric.cost, true, &lqbuffer), rtp->rtp_metric.hops, olsr_ip_to_string(&gwstr,
2977 --- a/src/routing_table.h
2978 +++ b/src/routing_table.h
2979 @@ -54,7 +54,7 @@
2980 #include "hna_set.h"
2981 #include "link_set.h"
2982 #include "olsr_cookie.h"
2983 -#include "common/avl.h"
2984 +#include "common/olsrd_avl.h"
2985 #include "common/list.h"
2986
2987 #define NETMASK_HOST 0xffffffff
2988 @@ -81,15 +81,15 @@ struct rt_nexthop {
2989 */
2990 struct rt_entry {
2991 struct olsr_ip_prefix rt_dst;
2992 - struct avl_node rt_tree_node;
2993 + struct olsrd_avl_node rt_tree_node;
2994 struct rt_path *rt_best; /* shortcut to the best path */
2995 struct rt_nexthop rt_nexthop; /* nexthop of FIB route */
2996 struct rt_metric rt_metric; /* metric of FIB route */
2997 - struct avl_tree rt_path_tree;
2998 + struct olsrd_avl_tree rt_path_tree;
2999 struct list_node rt_change_node; /* queue for kernel FIB add/chg/del */
3000 };
3001
3002 -AVLNODE2STRUCT(rt_tree2rt, struct rt_entry, rt_tree_node);
3003 +OLSRD_AVLNODE2STRUCT(rt_tree2rt, struct rt_entry, rt_tree_node);
3004 LISTNODE2STRUCT(changelist2rt, struct rt_entry, rt_change_node);
3005
3006 /*
3007 @@ -105,16 +105,16 @@ struct rt_path {
3008 struct tc_entry *rtp_tc; /* backpointer to owning tc entry */
3009 struct rt_nexthop rtp_nexthop;
3010 struct rt_metric rtp_metric;
3011 - struct avl_node rtp_tree_node; /* global rtp node */
3012 + struct olsrd_avl_node rtp_tree_node; /* global rtp node */
3013 union olsr_ip_addr rtp_originator; /* originator of the route */
3014 - struct avl_node rtp_prefix_tree_node; /* tc entry rtp node */
3015 + struct olsrd_avl_node rtp_prefix_tree_node; /* tc entry rtp node */
3016 struct olsr_ip_prefix rtp_dst; /* the prefix */
3017 uint32_t rtp_version; /* for detection of outdated rt_paths */
3018 uint8_t rtp_origin; /* internal, MID or HNA */
3019 };
3020
3021 -AVLNODE2STRUCT(rtp_tree2rtp, struct rt_path, rtp_tree_node);
3022 -AVLNODE2STRUCT(rtp_prefix_tree2rtp, struct rt_path, rtp_prefix_tree_node);
3023 +OLSRD_AVLNODE2STRUCT(rtp_tree2rtp, struct rt_path, rtp_tree_node);
3024 +OLSRD_AVLNODE2STRUCT(rtp_prefix_tree2rtp, struct rt_path, rtp_prefix_tree_node);
3025
3026 /*
3027 * In olsrd we have three different route types.
3028 @@ -143,10 +143,10 @@ enum olsr_rt_origin {
3029 */
3030 #define OLSR_FOR_ALL_RT_ENTRIES(rt) \
3031 { \
3032 - struct avl_node *rt_tree_node, *next_rt_tree_node; \
3033 - for (rt_tree_node = avl_walk_first(&routingtree); \
3034 + struct olsrd_avl_node *rt_tree_node, *next_rt_tree_node; \
3035 + for (rt_tree_node = olsrd_avl_walk_first(&routingtree); \
3036 rt_tree_node; rt_tree_node = next_rt_tree_node) { \
3037 - next_rt_tree_node = avl_walk_next(rt_tree_node); \
3038 + next_rt_tree_node = olsrd_avl_walk_next(rt_tree_node); \
3039 rt = rt_tree2rt(rt_tree_node);
3040 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
3041
3042 @@ -164,10 +164,10 @@ enum olsr_rt_origin {
3043 */
3044 #define OLSR_FOR_ALL_HNA_RT_ENTRIES(rt) \
3045 { \
3046 - struct avl_node *rt_tree_node, *next_rt_tree_node; \
3047 - for (rt_tree_node = avl_walk_first(&routingtree); \
3048 + struct olsrd_avl_node *rt_tree_node, *next_rt_tree_node; \
3049 + for (rt_tree_node = olsrd_avl_walk_first(&routingtree); \
3050 rt_tree_node; rt_tree_node = next_rt_tree_node) { \
3051 - next_rt_tree_node = avl_walk_next(rt_tree_node); \
3052 + next_rt_tree_node = olsrd_avl_walk_next(rt_tree_node); \
3053 rt = rt_tree2rt(rt_tree_node); \
3054 if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
3055 continue;
3056 @@ -190,7 +190,7 @@ union olsr_kernel_route {
3057 } v6;
3058 };
3059
3060 -extern struct avl_tree routingtree;
3061 +extern struct olsrd_avl_tree routingtree;
3062 extern unsigned int routingtree_version;
3063 extern struct olsr_cookie_info *rt_mem_cookie;
3064
3065 @@ -198,8 +198,8 @@ void olsr_init_routing_table(void);
3066
3067 unsigned int olsr_bump_routingtree_version(void);
3068
3069 -int avl_comp_ipv4_prefix(const void *, const void *);
3070 -int avl_comp_ipv6_prefix(const void *, const void *);
3071 +int olsrd_avl_comp_ipv4_prefix(const void *, const void *);
3072 +int olsrd_avl_comp_ipv6_prefix(const void *, const void *);
3073
3074 void olsr_rt_best(struct rt_entry *);
3075 bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
3076 @@ -210,7 +210,7 @@ uint8_t olsr_fib_metric(const struct rt_
3077 char *olsr_rt_to_string(const struct rt_entry *);
3078 char *olsr_rtp_to_string(const struct rt_path *);
3079 #ifndef NODEBUG
3080 -void olsr_print_routing_table(struct avl_tree *);
3081 +void olsr_print_routing_table(struct olsrd_avl_tree *);
3082 #else
3083 #define olsr_print_routing_table(x) do { } while(0)
3084 #endif
3085 --- a/src/scheduler.c
3086 +++ b/src/scheduler.c
3087 @@ -51,7 +51,7 @@
3088 #include "net_os.h"
3089 #include "mpr_selector_set.h"
3090 #include "olsr_random.h"
3091 -#include "common/avl.h"
3092 +#include "common/olsrd_avl.h"
3093
3094 #include <sys/times.h>
3095
3096 @@ -89,29 +89,29 @@ static void poll_sockets(void);
3097 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
3098 static void olsr_cleanup_timer(struct timer_entry *timer);
3099
3100 -struct avl_tree timer_cleanup_tree;
3101 +struct olsrd_avl_tree timer_cleanup_tree;
3102
3103 struct timer_cleanup_entry {
3104 - struct avl_node avl;
3105 + struct olsrd_avl_node olsrd_avl;
3106 struct timer_entry * timer;
3107 };
3108
3109 -/* static INLINE struct timer_cleanup_entry * node2timercleanup(struct avl_node *ptr) */
3110 -AVLNODE2STRUCT(node2timercleanup, struct timer_cleanup_entry, avl);
3111 +/* static INLINE struct timer_cleanup_entry * node2timercleanup(struct olsrd_avl_node *ptr) */
3112 +OLSRD_AVLNODE2STRUCT(node2timercleanup, struct timer_cleanup_entry, olsrd_avl);
3113
3114 /**
3115 * Loop over all timer cleanup entries and put the iterated entry in timer
3116 */
3117 #define OLSR_FOR_ALL_TIMERS_CLEANUP(timer) \
3118 { \
3119 - struct avl_node *timer_avl_node, *timer_avl_node_next; \
3120 - for (timer_avl_node = avl_walk_first(&timer_cleanup_tree); \
3121 - timer_avl_node; timer_avl_node = timer_avl_node_next) { \
3122 - timer_avl_node_next = avl_walk_next(timer_avl_node); \
3123 - timer = node2timercleanup(timer_avl_node);
3124 + struct olsrd_avl_node *timer_olsrd_avl_node, *timer_olsrd_avl_node_next; \
3125 + for (timer_olsrd_avl_node = olsrd_avl_walk_first(&timer_cleanup_tree); \
3126 + timer_olsrd_avl_node; timer_olsrd_avl_node = timer_olsrd_avl_node_next) { \
3127 + timer_olsrd_avl_node_next = olsrd_avl_walk_next(timer_olsrd_avl_node); \
3128 + timer = node2timercleanup(timer_olsrd_avl_node);
3129 #define OLSR_FOR_ALL_TIMER_CLEANUP_END(timer) }}
3130
3131 -static int avl_comp_timer(const void *entry1, const void *entry2) {
3132 +static int olsrd_avl_comp_timer(const void *entry1, const void *entry2) {
3133 if (entry1 < entry2) {
3134 return -1;
3135 }
3136 @@ -638,7 +638,7 @@ olsr_init_timers(void)
3137 last_tv = first_tv;
3138 now_times = olsr_times();
3139
3140 - avl_init(&timer_cleanup_tree, avl_comp_timer);
3141 + olsrd_avl_init(&timer_cleanup_tree, olsrd_avl_comp_timer);
3142
3143 for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
3144 list_head_init(&timer_wheel[idx]);
3145 @@ -760,7 +760,7 @@ static void walk_timers_cleanup(void) {
3146
3147 OLSR_FOR_ALL_TIMERS_CLEANUP(timer) {
3148 olsr_cleanup_timer(timer->timer);
3149 - avl_delete(&timer_cleanup_tree, &timer->avl);
3150 + olsrd_avl_delete(&timer_cleanup_tree, &timer->olsrd_avl);
3151 free(timer);
3152 } OLSR_FOR_ALL_TIMER_CLEANUP_END(slot)
3153 }
3154 @@ -969,9 +969,9 @@ olsr_stop_timer(struct timer_entry *time
3155
3156 {
3157 struct timer_cleanup_entry * node = olsr_malloc(sizeof(struct timer_cleanup_entry), "timer cleanup entry");
3158 - node->avl.key = timer;
3159 + node->olsrd_avl.key = timer;
3160 node->timer = timer;
3161 - if (avl_insert(&timer_cleanup_tree, &node->avl, AVL_DUP_NO) == -1) {
3162 + if (olsrd_avl_insert(&timer_cleanup_tree, &node->olsrd_avl, OLSRD_AVL_DUP_NO) == -1) {
3163 /* duplicate */
3164 free(node);
3165 }
3166 --- a/src/tc_set.c
3167 +++ b/src/tc_set.c
3168 @@ -50,7 +50,7 @@
3169 #include "olsr.h"
3170 #include "scheduler.h"
3171 #include "olsr_spf.h"
3172 -#include "common/avl.h"
3173 +#include "common/olsrd_avl.h"
3174 #include "lq_packet.h"
3175 #include "net_olsr.h"
3176 #include "lq_plugin.h"
3177 @@ -61,7 +61,7 @@
3178 #include <assert.h>
3179
3180 /* Root of the link state database */
3181 -struct avl_tree tc_tree;
3182 +struct olsrd_avl_tree tc_tree;
3183 struct tc_entry *tc_myself; /* Shortcut to ourselves */
3184
3185 /* Some cookies for stats keeping */
3186 @@ -165,14 +165,14 @@ olsr_add_tc_entry(union olsr_ip_addr *ad
3187 /*
3188 * Insert into the global tc tree.
3189 */
3190 - avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
3191 + olsrd_avl_insert(&tc_tree, &tc->vertex_node, OLSRD_AVL_DUP_NO);
3192 olsr_lock_tc_entry(tc);
3193
3194 /*
3195 * Initialize subtrees for edges and prefixes.
3196 */
3197 - avl_init(&tc->edge_tree, avl_comp_default);
3198 - avl_init(&tc->prefix_tree, avl_comp_prefix_default);
3199 + olsrd_avl_init(&tc->edge_tree, olsrd_avl_comp_default);
3200 + olsrd_avl_init(&tc->prefix_tree, olsrd_avl_comp_prefix_default);
3201
3202 /*
3203 * Add a rt_path for ourselves.
3204 @@ -191,7 +191,7 @@ olsr_init_tc(void)
3205 {
3206 OLSR_PRINTF(5, "TC: init topo\n");
3207
3208 - avl_init(&tc_tree, avl_comp_default);
3209 + olsrd_avl_init(&tc_tree, olsrd_avl_comp_default);
3210
3211 /*
3212 * Get some cookies for getting stats to ease troubleshooting.
3213 @@ -308,7 +308,7 @@ olsr_delete_tc_entry(struct tc_entry *tc
3214 olsr_stop_timer(tc->validity_timer);
3215 tc->validity_timer = NULL;
3216
3217 - avl_delete(&tc_tree, &tc->vertex_node);
3218 + olsrd_avl_delete(&tc_tree, &tc->vertex_node);
3219 olsr_unlock_tc_entry(tc);
3220 }
3221
3222 @@ -321,9 +321,9 @@ olsr_delete_tc_entry(struct tc_entry *tc
3223 struct tc_entry *
3224 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
3225 {
3226 - struct avl_node *node;
3227 + struct olsrd_avl_node *node;
3228
3229 - node = avl_find(&tc_tree, adr);
3230 + node = olsrd_avl_find(&tc_tree, adr);
3231
3232 return (node ? vertex_tree2tc(node) : NULL);
3233 }
3234 @@ -454,7 +454,7 @@ olsr_add_tc_edge_entry(struct tc_entry *
3235 /*
3236 * Insert into the edge tree.
3237 */
3238 - avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
3239 + olsrd_avl_insert(&tc->edge_tree, &tc_edge->edge_node, OLSRD_AVL_DUP_NO);
3240 olsr_lock_tc_entry(tc);
3241
3242 /*
3243 @@ -515,7 +515,7 @@ olsr_delete_tc_edge_entry(struct tc_edge
3244 #endif /* DEBUG */
3245
3246 tc = tc_edge->tc;
3247 - avl_delete(&tc->edge_tree, &tc_edge->edge_node);
3248 + olsrd_avl_delete(&tc->edge_tree, &tc_edge->edge_node);
3249 olsr_unlock_tc_entry(tc);
3250
3251 /*
3252 @@ -572,7 +572,7 @@ olsr_delete_revoked_tc_edges(struct tc_e
3253
3254 OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
3255 if (!passedLowerBorder) {
3256 - if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
3257 + if (olsrd_avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
3258 passedLowerBorder = true;
3259 } else {
3260 continue;
3261 @@ -580,7 +580,7 @@ olsr_delete_revoked_tc_edges(struct tc_e
3262 }
3263
3264 if (passedLowerBorder) {
3265 - if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
3266 + if (olsrd_avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
3267 break;
3268 }
3269 }
3270 @@ -680,9 +680,9 @@ olsr_tc_update_edge(struct tc_entry *tc,
3271 struct tc_edge_entry *
3272 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
3273 {
3274 - struct avl_node *edge_node;
3275 + struct olsrd_avl_node *edge_node;
3276
3277 - edge_node = avl_find(&tc->edge_tree, edge_addr);
3278 + edge_node = olsrd_avl_find(&tc->edge_tree, edge_addr);
3279
3280 return (edge_node ? edge_tree2tc_edge(edge_node) : NULL);
3281 }
3282 --- a/src/tc_set.h
3283 +++ b/src/tc_set.h
3284 @@ -48,7 +48,7 @@
3285
3286 #include "defs.h"
3287 #include "packet.h"
3288 -#include "common/avl.h"
3289 +#include "common/olsrd_avl.h"
3290 #include "common/list.h"
3291 #include "scheduler.h"
3292
3293 @@ -60,7 +60,7 @@
3294 */
3295
3296 struct tc_edge_entry {
3297 - struct avl_node edge_node; /* edge_tree node in tc_entry */
3298 + struct olsrd_avl_node edge_node; /* edge_tree node in tc_entry */
3299 union olsr_ip_addr T_dest_addr; /* edge_node key */
3300 struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
3301 struct tc_entry *tc; /* backpointer to owning tc entry */
3302 @@ -69,16 +69,16 @@ struct tc_edge_entry {
3303 uint32_t linkquality[0];
3304 };
3305
3306 -AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
3307 +OLSRD_AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
3308
3309 struct tc_entry {
3310 - struct avl_node vertex_node; /* node keyed by ip address */
3311 + struct olsrd_avl_node vertex_node; /* node keyed by ip address */
3312 union olsr_ip_addr addr; /* vertex_node key */
3313 - struct avl_node cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
3314 + struct olsrd_avl_node cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
3315 olsr_linkcost path_cost; /* SPF calculated distance, cand_tree_node key */
3316 struct list_node path_list_node; /* SPF result list */
3317 - struct avl_tree edge_tree; /* subtree for edges */
3318 - struct avl_tree prefix_tree; /* subtree for prefixes */
3319 + struct olsrd_avl_tree edge_tree; /* subtree for edges */
3320 + struct olsrd_avl_tree prefix_tree; /* subtree for prefixes */
3321 struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
3322 struct timer_entry *edge_gc_timer; /* used for edge garbage collection */
3323 struct timer_entry *validity_timer; /* tc validity time */
3324 @@ -102,8 +102,8 @@ struct tc_entry {
3325
3326 #define OLSR_TC_VTIME_JITTER 5 /* percent */
3327
3328 -AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
3329 -AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
3330 +OLSRD_AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
3331 +OLSRD_AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
3332 LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
3333
3334 /*
3335 @@ -116,32 +116,32 @@ LISTNODE2STRUCT(pathlist2tc, struct tc_e
3336 */
3337 #define OLSR_FOR_ALL_TC_ENTRIES(tc) \
3338 { \
3339 - struct avl_node *tc_tree_node, *next_tc_tree_node; \
3340 - for (tc_tree_node = avl_walk_first(&tc_tree); \
3341 + struct olsrd_avl_node *tc_tree_node, *next_tc_tree_node; \
3342 + for (tc_tree_node = olsrd_avl_walk_first(&tc_tree); \
3343 tc_tree_node; tc_tree_node = next_tc_tree_node) { \
3344 - next_tc_tree_node = avl_walk_next(tc_tree_node); \
3345 + next_tc_tree_node = olsrd_avl_walk_next(tc_tree_node); \
3346 tc = vertex_tree2tc(tc_tree_node);
3347 #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
3348
3349 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
3350 { \
3351 - struct avl_node *tc_edge_node, *next_tc_edge_node; \
3352 - for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
3353 + struct olsrd_avl_node *tc_edge_node, *next_tc_edge_node; \
3354 + for (tc_edge_node = olsrd_avl_walk_first(&tc->edge_tree); \
3355 tc_edge_node; tc_edge_node = next_tc_edge_node) { \
3356 - next_tc_edge_node = avl_walk_next(tc_edge_node); \
3357 + next_tc_edge_node = olsrd_avl_walk_next(tc_edge_node); \
3358 tc_edge = edge_tree2tc_edge(tc_edge_node);
3359 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
3360
3361 #define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) \
3362 { \
3363 - struct avl_node *rtp_node, *next_rtp_node; \
3364 - for (rtp_node = avl_walk_first(&tc->prefix_tree); \
3365 + struct olsrd_avl_node *rtp_node, *next_rtp_node; \
3366 + for (rtp_node = olsrd_avl_walk_first(&tc->prefix_tree); \
3367 rtp_node; rtp_node = next_rtp_node) { \
3368 - next_rtp_node = avl_walk_next(rtp_node); \
3369 + next_rtp_node = olsrd_avl_walk_next(rtp_node); \
3370 rtp = rtp_prefix_tree2rtp(rtp_node);
3371 #define OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp) }}
3372
3373 -extern struct avl_tree tc_tree;
3374 +extern struct olsrd_avl_tree tc_tree;
3375 extern struct tc_entry *tc_myself;
3376
3377 void olsr_init_tc(void);
Mirror of routing feed