bde40b78cf5aefa1c63b4bcd504520f14c7157d4
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 * Internal function to support returning the element from a avl tree query
107 * @param tree pointer to avl tree
108 * @param key pointer to key
109 * @param offset offset of node inside the embedded struct
110 * @param mode mode of lookup operation (less equal, equal or greater equal)
111 * @param pointer to elemen, NULL if no fitting one was found
114 __avl_find_element(struct avl_tree
*tree
, const void *key
, size_t offset
, enum avl_find_mode mode
) {
119 node
= avl_find(tree
, key
);
121 case AVL_FIND_LESSEQUAL
:
122 node
= avl_find_lessequal(tree
, key
);
124 case AVL_FIND_GREATEREQUAL
:
125 node
= avl_find_greaterequal(tree
, key
);
128 return node
== NULL
? NULL
: (((char *)node
) - offset
);
132 * Finds a node in an avl-tree with a certain key
133 * @param tree pointer to avl-tree
134 * @param key pointer to key
135 * @return pointer to avl-node with key, NULL if no node with
139 avl_find(struct avl_tree
*tree
, const void *key
)
141 struct avl_node
*node
;
144 if (tree
->root
== NULL
)
147 node
= avl_find_rec(tree
->root
, key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
149 return diff
== 0 ? node
: NULL
;
153 * Finds the last node in an avl-tree with a key less or equal
154 * than the specified key
155 * @param tree pointer to avl-tree
156 * @param key pointer to specified key
157 * @return pointer to avl-node, NULL if no node with
158 * key less or equal specified key exists.
161 avl_find_lessequal(struct avl_tree
*tree
, const void *key
) {
162 struct avl_node
*node
, *next
;
165 if (tree
->root
== NULL
)
168 node
= avl_find_rec(tree
->root
, key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
170 /* go left as long as key<node.key */
172 if (list_is_first(&tree
->list_head
, &node
->list
)) {
176 node
= (struct avl_node
*)node
->list
.prev
;
177 diff
= (*tree
->comp
) (key
, node
->key
, tree
->cmp_ptr
);
180 /* go right as long as key>=next_node.key */
184 if (list_is_last(&tree
->list_head
, &node
->list
)) {
188 next
= (struct avl_node
*)node
->list
.next
;
189 diff
= (*tree
->comp
) (key
, next
->key
, tree
->cmp_ptr
);
195 * Finds the first node in an avl-tree with a key greater or equal
196 * than the specified key
197 * @param tree pointer to avl-tree
198 * @param key pointer to specified key
199 * @return pointer to avl-node, NULL if no node with
200 * key greater or equal specified key exists.
203 avl_find_greaterequal(struct avl_tree
*tree
, const void *key
) {
204 struct avl_node
*node
, *next
;
207 if (tree
->root
== NULL
)
210 node
= avl_find_rec(tree
->root
, key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
212 /* go right as long as key>node.key */
214 if (list_is_last(&tree
->list_head
, &node
->list
)) {
218 node
= (struct avl_node
*)node
->list
.next
;
219 diff
= (*tree
->comp
) (key
, node
->key
, tree
->cmp_ptr
);
222 /* go left as long as key<=next_node.key */
226 if (list_is_first(&tree
->list_head
, &node
->list
)) {
230 next
= (struct avl_node
*)node
->list
.prev
;
231 diff
= (*tree
->comp
) (key
, next
->key
, tree
->cmp_ptr
);
237 * Inserts an avl_node into a tree
238 * @param tree pointer to tree
239 * @param new pointer to node
240 * @return 0 if node was inserted successfully, -1 if it was not inserted
241 * because of a key collision
244 avl_insert(struct avl_tree
*tree
, struct avl_node
*new)
246 struct avl_node
*node
, *next
, *last
;
257 if (tree
->root
== NULL
) {
258 list_add_head(&tree
->list_head
, &new->list
);
264 node
= avl_find_rec(tree
->root
, new->key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
268 while (!list_is_last(&tree
->list_head
, &last
->list
)) {
269 next
= list_next_element(last
, list
);
276 diff
= (*tree
->comp
) (new->key
, node
->key
, tree
->cmp_ptr
);
279 if (!tree
->allow_dups
)
284 avl_insert_after(tree
, last
, new);
288 if (node
->balance
== 1) {
289 avl_insert_before(tree
, node
, new);
297 if (node
->balance
== -1) {
298 avl_insert_after(tree
, last
, new);
307 avl_insert_before(tree
, node
, new);
312 post_insert(tree
, node
);
316 avl_insert_after(tree
, last
, new);
321 post_insert(tree
, node
);
326 * Remove a node from an avl tree
327 * @param tree pointer to tree
328 * @param node pointer to node
331 avl_delete(struct avl_tree
*tree
, struct avl_node
*node
)
333 struct avl_node
*next
;
334 struct avl_node
*parent
;
335 struct avl_node
*left
;
336 struct avl_node
*right
;
339 && !list_is_last(&tree
->list_head
, &node
->list
)
340 && !(next
= list_next_element(node
, list
))->leader
) {
342 next
->balance
= node
->balance
;
344 parent
= node
->parent
;
348 next
->parent
= parent
;
356 if (node
== parent
->left
)
360 parent
->right
= next
;
367 right
->parent
= next
;
371 avl_delete_worker(tree
, node
);
374 avl_remove(tree
, node
);
377 static struct avl_node
*
378 avl_find_rec(struct avl_node
*node
, const void *key
, avl_tree_comp comp
, void *cmp_ptr
, int *cmp_result
)
382 diff
= (*comp
) (key
, node
->key
, cmp_ptr
);
386 if (node
->left
!= NULL
)
387 return avl_find_rec(node
->left
, key
, comp
, cmp_ptr
, cmp_result
);
393 if (node
->right
!= NULL
)
394 return avl_find_rec(node
->right
, key
, comp
, cmp_ptr
, cmp_result
);
403 avl_rotate_right(struct avl_tree
*tree
, struct avl_node
*node
)
405 struct avl_node
*left
, *parent
;
408 parent
= node
->parent
;
410 left
->parent
= parent
;
417 if (parent
->left
== node
)
421 parent
->right
= left
;
424 node
->left
= left
->right
;
427 if (node
->left
!= NULL
)
428 node
->left
->parent
= node
;
430 node
->balance
+= 1 - avl_min(left
->balance
, 0);
431 left
->balance
+= 1 + avl_max(node
->balance
, 0);
435 avl_rotate_left(struct avl_tree
*tree
, struct avl_node
*node
)
437 struct avl_node
*right
, *parent
;
440 parent
= node
->parent
;
442 right
->parent
= parent
;
443 node
->parent
= right
;
449 if (parent
->left
== node
)
450 parent
->left
= right
;
453 parent
->right
= right
;
456 node
->right
= right
->left
;
459 if (node
->right
!= NULL
)
460 node
->right
->parent
= node
;
462 node
->balance
-= 1 + avl_max(right
->balance
, 0);
463 right
->balance
-= 1 - avl_min(node
->balance
, 0);
467 post_insert(struct avl_tree
*tree
, struct avl_node
*node
)
469 struct avl_node
*parent
= node
->parent
;
474 if (node
== parent
->left
) {
477 if (parent
->balance
== 0)
480 if (parent
->balance
== -1) {
481 post_insert(tree
, parent
);
485 if (node
->balance
== -1) {
486 avl_rotate_right(tree
, parent
);
490 avl_rotate_left(tree
, node
);
491 avl_rotate_right(tree
, node
->parent
->parent
);
497 if (parent
->balance
== 0)
500 if (parent
->balance
== 1) {
501 post_insert(tree
, parent
);
505 if (node
->balance
== 1) {
506 avl_rotate_left(tree
, parent
);
510 avl_rotate_right(tree
, node
);
511 avl_rotate_left(tree
, node
->parent
->parent
);
515 avl_insert_before(struct avl_tree
*tree
, struct avl_node
*pos_node
, struct avl_node
*node
)
517 list_add_before(&pos_node
->list
, &node
->list
);
522 avl_insert_after(struct avl_tree
*tree
, struct avl_node
*pos_node
, struct avl_node
*node
)
524 list_add_after(&pos_node
->list
, &node
->list
);
529 avl_remove(struct avl_tree
*tree
, struct avl_node
*node
)
531 list_remove(&node
->list
);
536 avl_post_delete(struct avl_tree
*tree
, struct avl_node
*node
)
538 struct avl_node
*parent
;
540 if ((parent
= node
->parent
) == NULL
)
543 if (node
== parent
->left
) {
546 if (parent
->balance
== 0) {
547 avl_post_delete(tree
, parent
);
551 if (parent
->balance
== 1)
554 if (parent
->right
->balance
== 0) {
555 avl_rotate_left(tree
, parent
);
559 if (parent
->right
->balance
== 1) {
560 avl_rotate_left(tree
, parent
);
561 avl_post_delete(tree
, parent
->parent
);
565 avl_rotate_right(tree
, parent
->right
);
566 avl_rotate_left(tree
, parent
);
567 avl_post_delete(tree
, parent
->parent
);
573 if (parent
->balance
== 0) {
574 avl_post_delete(tree
, parent
);
578 if (parent
->balance
== -1)
581 if (parent
->left
->balance
== 0) {
582 avl_rotate_right(tree
, parent
);
586 if (parent
->left
->balance
== -1) {
587 avl_rotate_right(tree
, parent
);
588 avl_post_delete(tree
, parent
->parent
);
592 avl_rotate_left(tree
, parent
->left
);
593 avl_rotate_right(tree
, parent
);
594 avl_post_delete(tree
, parent
->parent
);
597 static struct avl_node
*
598 avl_local_min(struct avl_node
*node
)
600 while (node
->left
!= NULL
)
607 static struct avl_node
*
608 avl_local_max(struct avl_node
*node
)
610 while (node
->right
!= NULL
)
618 avl_delete_worker(struct avl_tree
*tree
, struct avl_node
*node
)
620 struct avl_node
*parent
, *min
;
622 parent
= node
->parent
;
624 if (node
->left
== NULL
&& node
->right
== NULL
) {
625 if (parent
== NULL
) {
630 if (parent
->left
== node
) {
634 if (parent
->balance
== 1)
637 if (parent
->balance
== 0) {
638 avl_post_delete(tree
, parent
);
642 if (parent
->right
->balance
== 0) {
643 avl_rotate_left(tree
, parent
);
647 if (parent
->right
->balance
== 1) {
648 avl_rotate_left(tree
, parent
);
649 avl_post_delete(tree
, parent
->parent
);
653 avl_rotate_right(tree
, parent
->right
);
654 avl_rotate_left(tree
, parent
);
655 avl_post_delete(tree
, parent
->parent
);
659 if (parent
->right
== node
) {
660 parent
->right
= NULL
;
663 if (parent
->balance
== -1)
666 if (parent
->balance
== 0) {
667 avl_post_delete(tree
, parent
);
671 if (parent
->left
->balance
== 0) {
672 avl_rotate_right(tree
, parent
);
676 if (parent
->left
->balance
== -1) {
677 avl_rotate_right(tree
, parent
);
678 avl_post_delete(tree
, parent
->parent
);
682 avl_rotate_left(tree
, parent
->left
);
683 avl_rotate_right(tree
, parent
);
684 avl_post_delete(tree
, parent
->parent
);
689 if (node
->left
== NULL
) {
690 if (parent
== NULL
) {
691 tree
->root
= node
->right
;
692 node
->right
->parent
= NULL
;
696 node
->right
->parent
= parent
;
698 if (parent
->left
== node
)
699 parent
->left
= node
->right
;
702 parent
->right
= node
->right
;
704 avl_post_delete(tree
, node
->right
);
708 if (node
->right
== NULL
) {
709 if (parent
== NULL
) {
710 tree
->root
= node
->left
;
711 node
->left
->parent
= NULL
;
715 node
->left
->parent
= parent
;
717 if (parent
->left
== node
)
718 parent
->left
= node
->left
;
721 parent
->right
= node
->left
;
723 avl_post_delete(tree
, node
->left
);
727 min
= avl_local_min(node
->right
);
728 avl_delete_worker(tree
, min
);
729 parent
= node
->parent
;
731 min
->balance
= node
->balance
;
732 min
->parent
= parent
;
733 min
->left
= node
->left
;
734 min
->right
= node
->right
;
736 if (min
->left
!= NULL
)
737 min
->left
->parent
= min
;
739 if (min
->right
!= NULL
)
740 min
->right
->parent
= min
;
742 if (parent
== NULL
) {
747 if (parent
->left
== node
) {
758 * indent-tabs-mode: nil