91b2bb87ac7f18f9be55791904a2b3ef5701e82d
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
;
102 * Finds a node in an avl-tree with a certain key
103 * @param tree pointer to avl-tree
104 * @param key pointer to key
105 * @return pointer to avl-node with key, NULL if no node with
109 avl_find(const struct avl_tree
*tree
, const void *key
)
111 struct avl_node
*node
;
114 if (tree
->root
== NULL
)
117 node
= avl_find_rec(tree
->root
, key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
119 return diff
== 0 ? node
: NULL
;
123 * Finds the last node in an avl-tree with a key less or equal
124 * than the specified key
125 * @param tree pointer to avl-tree
126 * @param key pointer to specified key
127 * @return pointer to avl-node, NULL if no node with
128 * key less or equal specified key exists.
131 avl_find_lessequal(const struct avl_tree
*tree
, const void *key
) {
132 struct avl_node
*node
, *next
;
135 if (tree
->root
== NULL
)
138 node
= avl_find_rec(tree
->root
, key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
140 /* go left as long as key<node.key */
142 if (list_is_first(&node
->list
, &tree
->list_head
)) {
146 node
= (struct avl_node
*)node
->list
.prev
;
147 diff
= (*tree
->comp
) (key
, node
->key
, tree
->cmp_ptr
);
150 /* go right as long as key>=next_node.key */
154 if (list_is_last(&node
->list
, &tree
->list_head
)) {
158 next
= (struct avl_node
*)node
->list
.next
;
159 diff
= (*tree
->comp
) (key
, next
->key
, tree
->cmp_ptr
);
165 * Finds the first node in an avl-tree with a key greater or equal
166 * than the specified key
167 * @param tree pointer to avl-tree
168 * @param key pointer to specified key
169 * @return pointer to avl-node, NULL if no node with
170 * key greater or equal specified key exists.
173 avl_find_greaterequal(const struct avl_tree
*tree
, const void *key
) {
174 struct avl_node
*node
, *next
;
177 if (tree
->root
== NULL
)
180 node
= avl_find_rec(tree
->root
, key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
182 /* go right as long as key>node.key */
184 if (list_is_last(&node
->list
, &tree
->list_head
)) {
188 node
= (struct avl_node
*)node
->list
.next
;
189 diff
= (*tree
->comp
) (key
, node
->key
, tree
->cmp_ptr
);
192 /* go left as long as key<=next_node.key */
196 if (list_is_first(&node
->list
, &tree
->list_head
)) {
200 next
= (struct avl_node
*)node
->list
.prev
;
201 diff
= (*tree
->comp
) (key
, next
->key
, tree
->cmp_ptr
);
207 * Inserts an avl_node into a tree
208 * @param tree pointer to tree
209 * @param new pointer to node
210 * @return 0 if node was inserted successfully, -1 if it was not inserted
211 * because of a key collision
214 avl_insert(struct avl_tree
*tree
, struct avl_node
*new)
216 struct avl_node
*node
, *next
, *last
;
227 if (tree
->root
== NULL
) {
228 list_add_head(&tree
->list_head
, &new->list
);
234 node
= avl_find_rec(tree
->root
, new->key
, tree
->comp
, tree
->cmp_ptr
, &diff
);
238 while (!list_is_last(&last
->list
, &tree
->list_head
)) {
239 next
= list_next_element(last
, list
);
246 diff
= (*tree
->comp
) (new->key
, node
->key
, tree
->cmp_ptr
);
249 if (!tree
->allow_dups
)
254 avl_insert_after(tree
, last
, new);
258 if (node
->balance
== 1) {
259 avl_insert_before(tree
, node
, new);
267 if (node
->balance
== -1) {
268 avl_insert_after(tree
, last
, new);
277 avl_insert_before(tree
, node
, new);
282 post_insert(tree
, node
);
286 avl_insert_after(tree
, last
, new);
291 post_insert(tree
, node
);
296 * Remove a node from an avl tree
297 * @param tree pointer to tree
298 * @param node pointer to node
301 avl_delete(struct avl_tree
*tree
, struct avl_node
*node
)
303 struct avl_node
*next
;
304 struct avl_node
*parent
;
305 struct avl_node
*left
;
306 struct avl_node
*right
;
309 && !list_is_last(&node
->list
, &tree
->list_head
)
310 && !(next
= list_next_element(node
, list
))->leader
) {
312 next
->balance
= node
->balance
;
314 parent
= node
->parent
;
318 next
->parent
= parent
;
326 if (node
== parent
->left
)
330 parent
->right
= next
;
337 right
->parent
= next
;
341 avl_delete_worker(tree
, node
);
344 avl_remove(tree
, node
);
347 static struct avl_node
*
348 avl_find_rec(struct avl_node
*node
, const void *key
, avl_tree_comp comp
, void *cmp_ptr
, int *cmp_result
)
352 diff
= (*comp
) (key
, node
->key
, cmp_ptr
);
356 if (node
->left
!= NULL
)
357 return avl_find_rec(node
->left
, key
, comp
, cmp_ptr
, cmp_result
);
363 if (node
->right
!= NULL
)
364 return avl_find_rec(node
->right
, key
, comp
, cmp_ptr
, cmp_result
);
373 avl_rotate_right(struct avl_tree
*tree
, struct avl_node
*node
)
375 struct avl_node
*left
, *parent
;
378 parent
= node
->parent
;
380 left
->parent
= parent
;
387 if (parent
->left
== node
)
391 parent
->right
= left
;
394 node
->left
= left
->right
;
397 if (node
->left
!= NULL
)
398 node
->left
->parent
= node
;
400 node
->balance
+= 1 - avl_min(left
->balance
, 0);
401 left
->balance
+= 1 + avl_max(node
->balance
, 0);
405 avl_rotate_left(struct avl_tree
*tree
, struct avl_node
*node
)
407 struct avl_node
*right
, *parent
;
410 parent
= node
->parent
;
412 right
->parent
= parent
;
413 node
->parent
= right
;
419 if (parent
->left
== node
)
420 parent
->left
= right
;
423 parent
->right
= right
;
426 node
->right
= right
->left
;
429 if (node
->right
!= NULL
)
430 node
->right
->parent
= node
;
432 node
->balance
-= 1 + avl_max(right
->balance
, 0);
433 right
->balance
-= 1 - avl_min(node
->balance
, 0);
437 post_insert(struct avl_tree
*tree
, struct avl_node
*node
)
439 struct avl_node
*parent
= node
->parent
;
444 if (node
== parent
->left
) {
447 if (parent
->balance
== 0)
450 if (parent
->balance
== -1) {
451 post_insert(tree
, parent
);
455 if (node
->balance
== -1) {
456 avl_rotate_right(tree
, parent
);
460 avl_rotate_left(tree
, node
);
461 avl_rotate_right(tree
, node
->parent
->parent
);
467 if (parent
->balance
== 0)
470 if (parent
->balance
== 1) {
471 post_insert(tree
, parent
);
475 if (node
->balance
== 1) {
476 avl_rotate_left(tree
, parent
);
480 avl_rotate_right(tree
, node
);
481 avl_rotate_left(tree
, node
->parent
->parent
);
485 avl_insert_before(struct avl_tree
*tree
, struct avl_node
*pos_node
, struct avl_node
*node
)
487 list_add_before(&pos_node
->list
, &node
->list
);
492 avl_insert_after(struct avl_tree
*tree
, struct avl_node
*pos_node
, struct avl_node
*node
)
494 list_add_after(&pos_node
->list
, &node
->list
);
499 avl_remove(struct avl_tree
*tree
, struct avl_node
*node
)
501 list_remove(&node
->list
);
506 avl_post_delete(struct avl_tree
*tree
, struct avl_node
*node
)
508 struct avl_node
*parent
;
510 if ((parent
= node
->parent
) == NULL
)
513 if (node
== parent
->left
) {
516 if (parent
->balance
== 0) {
517 avl_post_delete(tree
, parent
);
521 if (parent
->balance
== 1)
524 if (parent
->right
->balance
== 0) {
525 avl_rotate_left(tree
, parent
);
529 if (parent
->right
->balance
== 1) {
530 avl_rotate_left(tree
, parent
);
531 avl_post_delete(tree
, parent
->parent
);
535 avl_rotate_right(tree
, parent
->right
);
536 avl_rotate_left(tree
, parent
);
537 avl_post_delete(tree
, parent
->parent
);
543 if (parent
->balance
== 0) {
544 avl_post_delete(tree
, parent
);
548 if (parent
->balance
== -1)
551 if (parent
->left
->balance
== 0) {
552 avl_rotate_right(tree
, parent
);
556 if (parent
->left
->balance
== -1) {
557 avl_rotate_right(tree
, parent
);
558 avl_post_delete(tree
, parent
->parent
);
562 avl_rotate_left(tree
, parent
->left
);
563 avl_rotate_right(tree
, parent
);
564 avl_post_delete(tree
, parent
->parent
);
567 static struct avl_node
*
568 avl_local_min(struct avl_node
*node
)
570 while (node
->left
!= NULL
)
577 static struct avl_node
*
578 avl_local_max(struct avl_node
*node
)
580 while (node
->right
!= NULL
)
588 avl_delete_worker(struct avl_tree
*tree
, struct avl_node
*node
)
590 struct avl_node
*parent
, *min
;
592 parent
= node
->parent
;
594 if (node
->left
== NULL
&& node
->right
== NULL
) {
595 if (parent
== NULL
) {
600 if (parent
->left
== node
) {
604 if (parent
->balance
== 1)
607 if (parent
->balance
== 0) {
608 avl_post_delete(tree
, parent
);
612 if (parent
->right
->balance
== 0) {
613 avl_rotate_left(tree
, parent
);
617 if (parent
->right
->balance
== 1) {
618 avl_rotate_left(tree
, parent
);
619 avl_post_delete(tree
, parent
->parent
);
623 avl_rotate_right(tree
, parent
->right
);
624 avl_rotate_left(tree
, parent
);
625 avl_post_delete(tree
, parent
->parent
);
629 if (parent
->right
== node
) {
630 parent
->right
= NULL
;
633 if (parent
->balance
== -1)
636 if (parent
->balance
== 0) {
637 avl_post_delete(tree
, parent
);
641 if (parent
->left
->balance
== 0) {
642 avl_rotate_right(tree
, parent
);
646 if (parent
->left
->balance
== -1) {
647 avl_rotate_right(tree
, parent
);
648 avl_post_delete(tree
, parent
->parent
);
652 avl_rotate_left(tree
, parent
->left
);
653 avl_rotate_right(tree
, parent
);
654 avl_post_delete(tree
, parent
->parent
);
659 if (node
->left
== NULL
) {
660 if (parent
== NULL
) {
661 tree
->root
= node
->right
;
662 node
->right
->parent
= NULL
;
666 node
->right
->parent
= parent
;
668 if (parent
->left
== node
)
669 parent
->left
= node
->right
;
672 parent
->right
= node
->right
;
674 avl_post_delete(tree
, node
->right
);
678 if (node
->right
== NULL
) {
679 if (parent
== NULL
) {
680 tree
->root
= node
->left
;
681 node
->left
->parent
= NULL
;
685 node
->left
->parent
= parent
;
687 if (parent
->left
== node
)
688 parent
->left
= node
->left
;
691 parent
->right
= node
->left
;
693 avl_post_delete(tree
, node
->left
);
697 min
= avl_local_min(node
->right
);
698 avl_delete_worker(tree
, min
);
699 parent
= node
->parent
;
701 min
->balance
= node
->balance
;
702 min
->parent
= parent
;
703 min
->left
= node
->left
;
704 min
->right
= node
->right
;
706 if (min
->left
!= NULL
)
707 min
->left
->parent
= min
;
709 if (min
->right
!= NULL
)
710 min
->right
->parent
= min
;
712 if (parent
== NULL
) {
717 if (parent
->left
== node
) {
728 * indent-tabs-mode: nil