2 * PacketBB handler library (see RFC 5444)
3 * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
4 * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
34 * Visit http://www.olsr.org/git for more information.
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
51 * internal type save inline function to calculate the maximum of
52 * to integers without macro implementation.
54 * @param x first parameter of maximum function
55 * @param y second parameter of maximum function
56 * @return largest integer of both parameters
58 static inline int avl_max(int x, int y) {
63 * internal type save inline function to calculate the minimum of
64 * to integers without macro implementation.
66 * @param x first parameter of minimum function
67 * @param y second parameter of minimum function
68 * @return smallest integer of both parameters
70 static inline int avl_min(int x, int y) {
74 static struct avl_node *
75 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
76 static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
77 static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
78 static void post_insert(struct avl_tree *tree, struct avl_node *node);
79 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
80 static void avl_remove(struct avl_tree *tree, struct avl_node *node);
83 * Initialize a new avl_tree struct
84 * @param tree pointer to avl-tree
85 * @param comp pointer to comparator for the tree
86 * @param allow_dups true if the tree allows multiple
87 * elements with the same
88 * @param ptr custom parameter for comparator
91 avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
93 INIT_LIST_HEAD(&tree->list_head);
97 tree->allow_dups = allow_dups;
101 static inline struct avl_node *avl_next(struct avl_node *node)
103 return list_entry(node->list.next, struct avl_node, list);
107 * Finds a node in an avl-tree with a certain key
108 * @param tree pointer to avl-tree
109 * @param key pointer to key
110 * @return pointer to avl-node with key, NULL if no node with
114 avl_find(const struct avl_tree *tree, const void *key)
116 struct avl_node *node;
119 if (tree->root == NULL)
122 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
124 return diff == 0 ? node : NULL;
128 * Finds the last node in an avl-tree with a key less or equal
129 * than the specified key
130 * @param tree pointer to avl-tree
131 * @param key pointer to specified key
132 * @return pointer to avl-node, NULL if no node with
133 * key less or equal specified key exists.
136 avl_find_lessequal(const struct avl_tree *tree, const void *key) {
137 struct avl_node *node, *next;
140 if (tree->root == NULL)
143 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
145 /* go left as long as key<node.key */
147 if (list_is_first(&node->list, &tree->list_head)) {
151 node = (struct avl_node *)node->list.prev;
152 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
155 /* go right as long as key>=next_node.key */
159 if (list_is_last(&node->list, &tree->list_head)) {
163 next = (struct avl_node *)node->list.next;
164 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
170 * Finds the first node in an avl-tree with a key greater or equal
171 * than the specified key
172 * @param tree pointer to avl-tree
173 * @param key pointer to specified key
174 * @return pointer to avl-node, NULL if no node with
175 * key greater or equal specified key exists.
178 avl_find_greaterequal(const struct avl_tree *tree, const void *key) {
179 struct avl_node *node, *next;
182 if (tree->root == NULL)
185 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
187 /* go right as long as key>node.key */
189 if (list_is_last(&node->list, &tree->list_head)) {
193 node = (struct avl_node *)node->list.next;
194 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
197 /* go left as long as key<=next_node.key */
201 if (list_is_first(&node->list, &tree->list_head)) {
205 next = (struct avl_node *)node->list.prev;
206 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
212 * Inserts an avl_node into a tree
213 * @param tree pointer to tree
214 * @param new pointer to node
215 * @return 0 if node was inserted successfully, -1 if it was not inserted
216 * because of a key collision
219 avl_insert(struct avl_tree *tree, struct avl_node *new)
221 struct avl_node *node, *next, *last;
232 if (tree->root == NULL) {
233 list_add(&new->list, &tree->list_head);
239 node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
243 while (!list_is_last(&last->list, &tree->list_head)) {
244 next = avl_next(last);
251 diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
254 if (!tree->allow_dups)
259 avl_insert_after(tree, last, new);
263 if (node->balance == 1) {
264 avl_insert_before(tree, node, new);
272 if (node->balance == -1) {
273 avl_insert_after(tree, last, new);
282 avl_insert_before(tree, node, new);
287 post_insert(tree, node);
291 avl_insert_after(tree, last, new);
296 post_insert(tree, node);
301 * Remove a node from an avl tree
302 * @param tree pointer to tree
303 * @param node pointer to node
306 avl_delete(struct avl_tree *tree, struct avl_node *node)
308 struct avl_node *next;
309 struct avl_node *parent;
310 struct avl_node *left;
311 struct avl_node *right;
314 && !list_is_last(&node->list, &tree->list_head)
315 && !(next = avl_next(node))->leader) {
317 next->balance = node->balance;
319 parent = node->parent;
323 next->parent = parent;
331 if (node == parent->left)
335 parent->right = next;
342 right->parent = next;
346 avl_delete_worker(tree, node);
349 avl_remove(tree, node);
352 static struct avl_node *
353 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
357 diff = (*comp) (key, node->key, cmp_ptr);
361 if (node->left != NULL)
362 return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
368 if (node->right != NULL)
369 return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
378 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
380 struct avl_node *left, *parent;
383 parent = node->parent;
385 left->parent = parent;
392 if (parent->left == node)
396 parent->right = left;
399 node->left = left->right;
402 if (node->left != NULL)
403 node->left->parent = node;
405 node->balance += 1 - avl_min(left->balance, 0);
406 left->balance += 1 + avl_max(node->balance, 0);
410 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
412 struct avl_node *right, *parent;
415 parent = node->parent;
417 right->parent = parent;
418 node->parent = right;
424 if (parent->left == node)
425 parent->left = right;
428 parent->right = right;
431 node->right = right->left;
434 if (node->right != NULL)
435 node->right->parent = node;
437 node->balance -= 1 + avl_max(right->balance, 0);
438 right->balance -= 1 - avl_min(node->balance, 0);
442 post_insert(struct avl_tree *tree, struct avl_node *node)
444 struct avl_node *parent = node->parent;
449 if (node == parent->left) {
452 if (parent->balance == 0)
455 if (parent->balance == -1) {
456 post_insert(tree, parent);
460 if (node->balance == -1) {
461 avl_rotate_right(tree, parent);
465 avl_rotate_left(tree, node);
466 avl_rotate_right(tree, node->parent->parent);
472 if (parent->balance == 0)
475 if (parent->balance == 1) {
476 post_insert(tree, parent);
480 if (node->balance == 1) {
481 avl_rotate_left(tree, parent);
485 avl_rotate_right(tree, node);
486 avl_rotate_left(tree, node->parent->parent);
490 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
492 list_add_tail(&node->list, &pos_node->list);
497 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
499 list_add(&node->list, &pos_node->list);
504 avl_remove(struct avl_tree *tree, struct avl_node *node)
506 list_del(&node->list);
511 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
513 struct avl_node *parent;
515 if ((parent = node->parent) == NULL)
518 if (node == parent->left) {
521 if (parent->balance == 0) {
522 avl_post_delete(tree, parent);
526 if (parent->balance == 1)
529 if (parent->right->balance == 0) {
530 avl_rotate_left(tree, parent);
534 if (parent->right->balance == 1) {
535 avl_rotate_left(tree, parent);
536 avl_post_delete(tree, parent->parent);
540 avl_rotate_right(tree, parent->right);
541 avl_rotate_left(tree, parent);
542 avl_post_delete(tree, parent->parent);
548 if (parent->balance == 0) {
549 avl_post_delete(tree, parent);
553 if (parent->balance == -1)
556 if (parent->left->balance == 0) {
557 avl_rotate_right(tree, parent);
561 if (parent->left->balance == -1) {
562 avl_rotate_right(tree, parent);
563 avl_post_delete(tree, parent->parent);
567 avl_rotate_left(tree, parent->left);
568 avl_rotate_right(tree, parent);
569 avl_post_delete(tree, parent->parent);
572 static struct avl_node *
573 avl_local_min(struct avl_node *node)
575 while (node->left != NULL)
582 static struct avl_node *
583 avl_local_max(struct avl_node *node)
585 while (node->right != NULL)
593 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
595 struct avl_node *parent, *min;
597 parent = node->parent;
599 if (node->left == NULL && node->right == NULL) {
600 if (parent == NULL) {
605 if (parent->left == node) {
609 if (parent->balance == 1)
612 if (parent->balance == 0) {
613 avl_post_delete(tree, parent);
617 if (parent->right->balance == 0) {
618 avl_rotate_left(tree, parent);
622 if (parent->right->balance == 1) {
623 avl_rotate_left(tree, parent);
624 avl_post_delete(tree, parent->parent);
628 avl_rotate_right(tree, parent->right);
629 avl_rotate_left(tree, parent);
630 avl_post_delete(tree, parent->parent);
634 if (parent->right == node) {
635 parent->right = NULL;
638 if (parent->balance == -1)
641 if (parent->balance == 0) {
642 avl_post_delete(tree, parent);
646 if (parent->left->balance == 0) {
647 avl_rotate_right(tree, parent);
651 if (parent->left->balance == -1) {
652 avl_rotate_right(tree, parent);
653 avl_post_delete(tree, parent->parent);
657 avl_rotate_left(tree, parent->left);
658 avl_rotate_right(tree, parent);
659 avl_post_delete(tree, parent->parent);
664 if (node->left == NULL) {
665 if (parent == NULL) {
666 tree->root = node->right;
667 node->right->parent = NULL;
671 node->right->parent = parent;
673 if (parent->left == node)
674 parent->left = node->right;
677 parent->right = node->right;
679 avl_post_delete(tree, node->right);
683 if (node->right == NULL) {
684 if (parent == NULL) {
685 tree->root = node->left;
686 node->left->parent = NULL;
690 node->left->parent = parent;
692 if (parent->left == node)
693 parent->left = node->left;
696 parent->right = node->left;
698 avl_post_delete(tree, node->left);
702 min = avl_local_min(node->right);
703 avl_delete_worker(tree, min);
704 parent = node->parent;
706 min->balance = node->balance;
707 min->parent = parent;
708 min->left = node->left;
709 min->right = node->right;
711 if (min->left != NULL)
712 min->left->parent = min;
714 if (min->right != NULL)
715 min->right->parent = min;
717 if (parent == NULL) {
722 if (parent->left == node) {
733 * indent-tabs-mode: nil