3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
5 * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
18 * * Neither the name of olsr.org, olsrd nor the names of its
19 * contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
35 * Visit http://www.olsr.org for more information.
37 * If you find this software useful feel free to make a donation
38 * to the project. For more information see the website or contact
39 * the copyright holders.
48 #include "common/avl.h"
52 * default comparison pointers
53 * set to the respective compare function.
54 * if avl_comp_default is set to zero, a fast
55 * inline ipv4 comparison will be executed.
57 avl_tree_comp avl_comp_default = NULL;
58 avl_tree_comp avl_comp_prefix_default;
61 avl_comp_ipv4(const void *ip1, const void *ip2)
63 return ip4cmp(ip1, ip2);
67 avl_comp_ipv6(const void *ip1, const void *ip2)
69 return ip6cmp(ip1, ip2);
73 avl_comp_mac(const void *ip1, const void *ip2)
75 return memcmp(ip1, ip2, 6);
79 avl_init(struct avl_tree *tree, avl_tree_comp comp)
88 static struct avl_node *
89 avl_find_rec_ipv4(struct avl_node *node, const void *key)
91 if (*(const unsigned int *)key < *(const unsigned int *)node->key) {
92 if (node->left != NULL)
93 return avl_find_rec_ipv4(node->left, key);
96 else if (*(const unsigned int *)key > *(const unsigned int *)node->key) {
97 if (node->right != NULL)
98 return avl_find_rec_ipv4(node->right, key);
104 static struct avl_node *
105 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp)
110 return avl_find_rec_ipv4(node, key);
112 diff = (*comp) (key, node->key);
115 if (node->left != NULL)
116 return avl_find_rec(node->left, key, comp);
122 if (node->right != NULL)
123 return avl_find_rec(node->right, key, comp);
132 avl_find(struct avl_tree *tree, const void *key)
134 struct avl_node *node;
136 if (tree->root == NULL)
139 node = avl_find_rec(tree->root, key, tree->comp);
141 if (NULL == tree->comp) {
142 if (0 != ip4cmp(node->key, key))
147 if ((*tree->comp) (node->key, key) != 0)
155 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
157 struct avl_node *left, *parent;
160 parent = node->parent;
162 left->parent = parent;
169 if (parent->left == node)
173 parent->right = left;
176 node->left = left->right;
179 if (node->left != NULL)
180 node->left->parent = node;
182 node->balance += 1 - MIN(left->balance, 0);
183 left->balance += 1 + MAX(node->balance, 0);
187 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
189 struct avl_node *right, *parent;
192 parent = node->parent;
194 right->parent = parent;
195 node->parent = right;
201 if (parent->left == node)
202 parent->left = right;
205 parent->right = right;
208 node->right = right->left;
211 if (node->right != NULL)
212 node->right->parent = node;
214 node->balance -= 1 + MAX(right->balance, 0);
215 right->balance -= 1 - MIN(node->balance, 0);
219 post_insert(struct avl_tree *tree, struct avl_node *node)
221 struct avl_node *parent = node->parent;
226 if (node == parent->left) {
229 if (parent->balance == 0)
232 if (parent->balance == -1) {
233 post_insert(tree, parent);
237 if (node->balance == -1) {
238 avl_rotate_right(tree, parent);
242 avl_rotate_left(tree, node);
243 avl_rotate_right(tree, node->parent->parent);
249 if (parent->balance == 0)
252 if (parent->balance == 1) {
253 post_insert(tree, parent);
257 if (node->balance == 1) {
258 avl_rotate_left(tree, parent);
262 avl_rotate_right(tree, node);
263 avl_rotate_left(tree, node->parent->parent);
267 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node,
268 struct avl_node *node)
270 if (pos_node->prev != NULL)
271 pos_node->prev->next = node;
275 node->prev = pos_node->prev;
276 node->next = pos_node;
278 pos_node->prev = node;
284 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node,
285 struct avl_node *node)
287 if (pos_node->next != NULL)
288 pos_node->next->prev = node;
292 node->prev = pos_node;
293 node->next = pos_node->next;
295 pos_node->next = node;
301 avl_remove(struct avl_tree *tree, struct avl_node *node)
303 if (node->prev != NULL)
304 node->prev->next = node->next;
306 tree->first = node->next;
308 if (node->next != NULL)
309 node->next->prev = node->prev;
311 tree->last = node->prev;
317 avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
319 struct avl_node *node;
320 struct avl_node *last;
334 if (tree->root == NULL) {
342 node = avl_find_rec(tree->root, new->key, tree->comp);
346 while (last->next != NULL && last->next->leader == 0)
349 if (NULL == tree->comp)
350 diff = ip4cmp(new->key, node->key);
353 diff = (*tree->comp) (new->key, node->key);
356 if (allow_duplicates == AVL_DUP_NO)
361 avl_insert_after(tree, last, new);
365 if (node->balance == 1) {
366 avl_insert_before(tree, node, new);
374 if (node->balance == -1) {
375 avl_insert_after(tree, last, new);
384 avl_insert_before(tree, node, new);
389 post_insert(tree, node);
393 avl_insert_after(tree, last, new);
398 post_insert(tree, node);
403 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
405 struct avl_node *parent;
407 if ((parent = node->parent) == NULL)
410 if (node == parent->left) {
413 if (parent->balance == 0) {
414 avl_post_delete(tree, parent);
418 if (parent->balance == 1)
421 if (parent->right->balance == 0) {
422 avl_rotate_left(tree, parent);
426 if (parent->right->balance == 1) {
427 avl_rotate_left(tree, parent);
428 avl_post_delete(tree, parent->parent);
432 avl_rotate_right(tree, parent->right);
433 avl_rotate_left(tree, parent);
434 avl_post_delete(tree, parent->parent);
440 if (parent->balance == 0) {
441 avl_post_delete(tree, parent);
445 if (parent->balance == -1)
448 if (parent->left->balance == 0) {
449 avl_rotate_right(tree, parent);
453 if (parent->left->balance == -1) {
454 avl_rotate_right(tree, parent);
455 avl_post_delete(tree, parent->parent);
459 avl_rotate_left(tree, parent->left);
460 avl_rotate_right(tree, parent);
461 avl_post_delete(tree, parent->parent);
464 static struct avl_node *
465 avl_local_min(struct avl_node *node)
467 while (node->left != NULL)
474 static struct avl_node *
475 avl_local_max(struct avl_node *node)
477 while (node->right != NULL)
485 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
487 struct avl_node *parent, *min;
489 parent = node->parent;
491 if (node->left == NULL && node->right == NULL) {
492 if (parent == NULL) {
497 if (parent->left == node) {
501 if (parent->balance == 1)
504 if (parent->balance == 0) {
505 avl_post_delete(tree, parent);
509 if (parent->right->balance == 0) {
510 avl_rotate_left(tree, parent);
514 if (parent->right->balance == 1) {
515 avl_rotate_left(tree, parent);
516 avl_post_delete(tree, parent->parent);
520 avl_rotate_right(tree, parent->right);
521 avl_rotate_left(tree, parent);
522 avl_post_delete(tree, parent->parent);
526 if (parent->right == node) {
527 parent->right = NULL;
530 if (parent->balance == -1)
533 if (parent->balance == 0) {
534 avl_post_delete(tree, parent);
538 if (parent->left->balance == 0) {
539 avl_rotate_right(tree, parent);
543 if (parent->left->balance == -1) {
544 avl_rotate_right(tree, parent);
545 avl_post_delete(tree, parent->parent);
549 avl_rotate_left(tree, parent->left);
550 avl_rotate_right(tree, parent);
551 avl_post_delete(tree, parent->parent);
556 if (node->left == NULL) {
557 if (parent == NULL) {
558 tree->root = node->right;
559 node->right->parent = NULL;
563 node->right->parent = parent;
565 if (parent->left == node)
566 parent->left = node->right;
569 parent->right = node->right;
571 avl_post_delete(tree, node->right);
575 if (node->right == NULL) {
576 if (parent == NULL) {
577 tree->root = node->left;
578 node->left->parent = NULL;
582 node->left->parent = parent;
584 if (parent->left == node)
585 parent->left = node->left;
588 parent->right = node->left;
590 avl_post_delete(tree, node->left);
594 min = avl_local_min(node->right);
595 avl_delete_worker(tree, min);
596 parent = node->parent;
598 min->balance = node->balance;
599 min->parent = parent;
600 min->left = node->left;
601 min->right = node->right;
603 if (min->left != NULL)
604 min->left->parent = min;
606 if (min->right != NULL)
607 min->right->parent = min;
609 if (parent == NULL) {
614 if (parent->left == node) {
623 avl_delete(struct avl_tree *tree, struct avl_node *node)
625 struct avl_node *next;
626 struct avl_node *parent;
627 struct avl_node *left;
628 struct avl_node *right;
630 if (node->leader != 0) {
633 if (next != NULL && next->leader == 0) {
635 next->balance = node->balance;
637 parent = node->parent;
641 next->parent = parent;
649 if (node == parent->left)
653 parent->right = next;
660 right->parent = next;
664 avl_delete_worker(tree, node);
667 avl_remove(tree, node);