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.
50 #define list_merge(_head, _list) list_merge(_list, _head)
51 #define list_is_last(_head, _list) list_is_last(_list, _head)
52 #define list_is_first(_head, _list) list_is_first(_list, _head)
55 * internal type save inline function to calculate the maximum of
56 * to integers without macro implementation.
58 * @param x first parameter of maximum function
59 * @param y second parameter of maximum function
60 * @return largest integer of both parameters
62 static inline int avl_max(int x, int y) {
67 * internal type save inline function to calculate the minimum of
68 * to integers without macro implementation.
70 * @param x first parameter of minimum function
71 * @param y second parameter of minimum function
72 * @return smallest integer of both parameters
74 static inline int avl_min(int x, int y) {
78 static struct avl_node *
79 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
80 static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
81 static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
82 static void post_insert(struct avl_tree *tree, struct avl_node *node);
83 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
84 static void avl_remove(struct avl_tree *tree, struct avl_node *node);
87 * Initialize a new avl_tree struct
88 * @param tree pointer to avl-tree
89 * @param comp pointer to comparator for the tree
90 * @param allow_dups true if the tree allows multiple
91 * elements with the same
92 * @param ptr custom parameter for comparator
95 avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
97 list_init_head(&tree->list_head);
101 tree->allow_dups = allow_dups;
106 * Finds a node in an avl-tree with a certain key
107 * @param tree pointer to avl-tree
108 * @param key pointer to key
109 * @return pointer to avl-node with key, NULL if no node with
113 avl_find(const struct avl_tree *tree, const void *key)
115 struct avl_node *node;
118 if (tree->root == NULL)
121 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
123 return diff == 0 ? node : NULL;
127 * Finds the last node in an avl-tree with a key less or equal
128 * than the specified key
129 * @param tree pointer to avl-tree
130 * @param key pointer to specified key
131 * @return pointer to avl-node, NULL if no node with
132 * key less or equal specified key exists.
135 avl_find_lessequal(const struct avl_tree *tree, const void *key) {
136 struct avl_node *node, *next;
139 if (tree->root == NULL)
142 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
144 /* go left as long as key<node.key */
146 if (list_is_first(&tree->list_head, &node->list)) {
150 node = (struct avl_node *)node->list.prev;
151 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
154 /* go right as long as key>=next_node.key */
158 if (list_is_last(&tree->list_head, &node->list)) {
162 next = (struct avl_node *)node->list.next;
163 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
169 * Finds the first node in an avl-tree with a key greater or equal
170 * than the specified key
171 * @param tree pointer to avl-tree
172 * @param key pointer to specified key
173 * @return pointer to avl-node, NULL if no node with
174 * key greater or equal specified key exists.
177 avl_find_greaterequal(const struct avl_tree *tree, const void *key) {
178 struct avl_node *node, *next;
181 if (tree->root == NULL)
184 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
186 /* go right as long as key>node.key */
188 if (list_is_last(&tree->list_head, &node->list)) {
192 node = (struct avl_node *)node->list.next;
193 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
196 /* go left as long as key<=next_node.key */
200 if (list_is_first(&tree->list_head, &node->list)) {
204 next = (struct avl_node *)node->list.prev;
205 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
211 * Inserts an avl_node into a tree
212 * @param tree pointer to tree
213 * @param new pointer to node
214 * @return 0 if node was inserted successfully, -1 if it was not inserted
215 * because of a key collision
218 avl_insert(struct avl_tree *tree, struct avl_node *new)
220 struct avl_node *node, *next, *last;
231 if (tree->root == NULL) {
232 list_add_head(&tree->list_head, &new->list);
238 node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
242 while (!list_is_last(&tree->list_head, &last->list)) {
243 next = list_next_element(last, list);
250 diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
253 if (!tree->allow_dups)
258 avl_insert_after(tree, last, new);
262 if (node->balance == 1) {
263 avl_insert_before(tree, node, new);
271 if (node->balance == -1) {
272 avl_insert_after(tree, last, new);
281 avl_insert_before(tree, node, new);
286 post_insert(tree, node);
290 avl_insert_after(tree, last, new);
295 post_insert(tree, node);
300 * Remove a node from an avl tree
301 * @param tree pointer to tree
302 * @param node pointer to node
305 avl_delete(struct avl_tree *tree, struct avl_node *node)
307 struct avl_node *next;
308 struct avl_node *parent;
309 struct avl_node *left;
310 struct avl_node *right;
313 && !list_is_last(&tree->list_head, &node->list)
314 && !(next = list_next_element(node, list))->leader) {
316 next->balance = node->balance;
318 parent = node->parent;
322 next->parent = parent;
330 if (node == parent->left)
334 parent->right = next;
341 right->parent = next;
345 avl_delete_worker(tree, node);
348 avl_remove(tree, node);
351 static struct avl_node *
352 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
356 diff = (*comp) (key, node->key, cmp_ptr);
360 if (node->left != NULL)
361 return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
367 if (node->right != NULL)
368 return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
377 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
379 struct avl_node *left, *parent;
382 parent = node->parent;
384 left->parent = parent;
391 if (parent->left == node)
395 parent->right = left;
398 node->left = left->right;
401 if (node->left != NULL)
402 node->left->parent = node;
404 node->balance += 1 - avl_min(left->balance, 0);
405 left->balance += 1 + avl_max(node->balance, 0);
409 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
411 struct avl_node *right, *parent;
414 parent = node->parent;
416 right->parent = parent;
417 node->parent = right;
423 if (parent->left == node)
424 parent->left = right;
427 parent->right = right;
430 node->right = right->left;
433 if (node->right != NULL)
434 node->right->parent = node;
436 node->balance -= 1 + avl_max(right->balance, 0);
437 right->balance -= 1 - avl_min(node->balance, 0);
441 post_insert(struct avl_tree *tree, struct avl_node *node)
443 struct avl_node *parent = node->parent;
448 if (node == parent->left) {
451 if (parent->balance == 0)
454 if (parent->balance == -1) {
455 post_insert(tree, parent);
459 if (node->balance == -1) {
460 avl_rotate_right(tree, parent);
464 avl_rotate_left(tree, node);
465 avl_rotate_right(tree, node->parent->parent);
471 if (parent->balance == 0)
474 if (parent->balance == 1) {
475 post_insert(tree, parent);
479 if (node->balance == 1) {
480 avl_rotate_left(tree, parent);
484 avl_rotate_right(tree, node);
485 avl_rotate_left(tree, node->parent->parent);
489 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
491 list_add_before(&pos_node->list, &node->list);
496 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
498 list_add_after(&pos_node->list, &node->list);
503 avl_remove(struct avl_tree *tree, struct avl_node *node)
505 list_remove(&node->list);
510 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
512 struct avl_node *parent;
514 if ((parent = node->parent) == NULL)
517 if (node == parent->left) {
520 if (parent->balance == 0) {
521 avl_post_delete(tree, parent);
525 if (parent->balance == 1)
528 if (parent->right->balance == 0) {
529 avl_rotate_left(tree, parent);
533 if (parent->right->balance == 1) {
534 avl_rotate_left(tree, parent);
535 avl_post_delete(tree, parent->parent);
539 avl_rotate_right(tree, parent->right);
540 avl_rotate_left(tree, parent);
541 avl_post_delete(tree, parent->parent);
547 if (parent->balance == 0) {
548 avl_post_delete(tree, parent);
552 if (parent->balance == -1)
555 if (parent->left->balance == 0) {
556 avl_rotate_right(tree, parent);
560 if (parent->left->balance == -1) {
561 avl_rotate_right(tree, parent);
562 avl_post_delete(tree, parent->parent);
566 avl_rotate_left(tree, parent->left);
567 avl_rotate_right(tree, parent);
568 avl_post_delete(tree, parent->parent);
571 static struct avl_node *
572 avl_local_min(struct avl_node *node)
574 while (node->left != NULL)
581 static struct avl_node *
582 avl_local_max(struct avl_node *node)
584 while (node->right != NULL)
592 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
594 struct avl_node *parent, *min;
596 parent = node->parent;
598 if (node->left == NULL && node->right == NULL) {
599 if (parent == NULL) {
604 if (parent->left == node) {
608 if (parent->balance == 1)
611 if (parent->balance == 0) {
612 avl_post_delete(tree, parent);
616 if (parent->right->balance == 0) {
617 avl_rotate_left(tree, parent);
621 if (parent->right->balance == 1) {
622 avl_rotate_left(tree, parent);
623 avl_post_delete(tree, parent->parent);
627 avl_rotate_right(tree, parent->right);
628 avl_rotate_left(tree, parent);
629 avl_post_delete(tree, parent->parent);
633 if (parent->right == node) {
634 parent->right = NULL;
637 if (parent->balance == -1)
640 if (parent->balance == 0) {
641 avl_post_delete(tree, parent);
645 if (parent->left->balance == 0) {
646 avl_rotate_right(tree, parent);
650 if (parent->left->balance == -1) {
651 avl_rotate_right(tree, parent);
652 avl_post_delete(tree, parent->parent);
656 avl_rotate_left(tree, parent->left);
657 avl_rotate_right(tree, parent);
658 avl_post_delete(tree, parent->parent);
663 if (node->left == NULL) {
664 if (parent == NULL) {
665 tree->root = node->right;
666 node->right->parent = NULL;
670 node->right->parent = parent;
672 if (parent->left == node)
673 parent->left = node->right;
676 parent->right = node->right;
678 avl_post_delete(tree, node->right);
682 if (node->right == NULL) {
683 if (parent == NULL) {
684 tree->root = node->left;
685 node->left->parent = NULL;
689 node->left->parent = parent;
691 if (parent->left == node)
692 parent->left = node->left;
695 parent->right = node->left;
697 avl_post_delete(tree, node->left);
701 min = avl_local_min(node->right);
702 avl_delete_worker(tree, min);
703 parent = node->parent;
705 min->balance = node->balance;
706 min->parent = parent;
707 min->left = node->left;
708 min->right = node->right;
710 if (min->left != NULL)
711 min->left->parent = min;
713 if (min->right != NULL)
714 min->right->parent = min;
716 if (parent == NULL) {
721 if (parent->left == node) {
732 * indent-tabs-mode: nil