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.
48 #include "list_compat.h"
50 /* Support for OLSR.org linker symbol export */
51 #define EXPORT(sym) sym
54 * This element is a member of a avl-tree. It must be contained in all
55 * larger structs that should be put into a tree.
59 * Linked list node for supporting easy iteration and multiple
60 * elments with the same key.
62 * this must be the first element of an avl_node to
63 * make casting for lists easier
65 struct list_entity list
;
68 * Pointer to parent node in tree, NULL if root node
70 struct avl_node
*parent
;
73 * Pointer to left child
75 struct avl_node
*left
;
78 * Pointer to right child
80 struct avl_node
*right
;
83 * pointer to key of node
88 * balance state of AVL tree (0,-1,+1)
93 * true if first of a series of nodes with same key
99 * Prototype for avl comparators
100 * @param k1 first key
101 * @param k2 second key
102 * @param ptr custom data for tree comparator
103 * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
105 typedef int (*avl_tree_comp
) (const void *k1
, const void *k2
, void *ptr
);
108 * This struct is the central management part of an avl tree.
109 * One of them is necessary for each avl_tree.
113 * Head of linked list node for supporting easy iteration
114 * and multiple elments with the same key.
116 struct list_entity list_head
;
119 * pointer to the root node of the avl tree, NULL if tree is empty
121 struct avl_node
*root
;
124 * number of nodes in the avl tree
129 * true if multiple nodes with the same key are
130 * allowed in the tree, false otherwise
135 * pointer to the tree comparator
137 * First two parameters are keys to compare,
138 * third parameter is a copy of cmp_ptr
143 * custom pointer delivered to the tree comparator
149 * internal enum for avl_find_... macros
154 AVL_FIND_GREATEREQUAL
157 void EXPORT(avl_init
)(struct avl_tree
*, avl_tree_comp
, bool, void *);
158 struct avl_node
*EXPORT(avl_find
)(struct avl_tree
*, const void *);
159 struct avl_node
*EXPORT(avl_find_greaterequal
)(struct avl_tree
*tree
, const void *key
);
160 struct avl_node
*EXPORT(avl_find_lessequal
)(struct avl_tree
*tree
, const void *key
);
161 int EXPORT(avl_insert
)(struct avl_tree
*, struct avl_node
*);
162 void EXPORT(avl_delete
)(struct avl_tree
*, struct avl_node
*);
163 void *EXPORT(__avl_find_element
)(struct avl_tree
*tree
, const void *key
,
164 size_t offset
, enum avl_find_mode mode
);
167 * @param tree pointer to avl-tree
168 * @param node pointer to node of the tree
169 * @return true if node is the first one of the tree, false otherwise
172 avl_is_first(struct avl_tree
*tree
, struct avl_node
*node
) {
173 return tree
->list_head
.next
== &node
->list
;
177 * @param tree pointer to avl-tree
178 * @param node pointer to node of the tree
179 * @return true if node is the last one of the tree, false otherwise
182 avl_is_last(struct avl_tree
*tree
, struct avl_node
*node
) {
183 return tree
->list_head
.prev
== &node
->list
;
187 * @param tree pointer to avl-tree
188 * @return true if the tree is empty, false otherwise
191 avl_is_empty(struct avl_tree
*tree
) {
192 return tree
->count
== 0;
196 * @param tree pointer to avl-tree
197 * @param key pointer to key
198 * @param element pointer to a node element
199 * (don't need to be initialized)
200 * @param node_element name of the avl_node element inside the
202 * @return pointer to tree element with the specified key,
203 * NULL if no element was found
205 #define avl_find_element(tree, key, element, node_element) \
206 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
209 * @param tree pointer to avl-tree
210 * @param key pointer to specified key
211 * @param element pointer to a node element
212 * (don't need to be initialized)
213 * @param node_element name of the avl_node element inside the
215 * return pointer to last tree element with less or equal key than specified key,
216 * NULL if no element was found
218 #define avl_find_le_element(tree, key, element, node_element) \
219 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
222 * @param tree pointer to avl-tree
223 * @param key pointer to specified key
224 * @param element pointer to a node element
225 * (don't need to be initialized)
226 * @param node_element name of the avl_node element inside the
228 * return pointer to first tree element with greater or equal key than specified key,
229 * NULL if no element was found
231 #define avl_find_ge_element(tree, key, element, node_element) \
232 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
235 * This function must not be called for an empty tree
237 * @param tree pointer to avl-tree
238 * @param element pointer to a node element
239 * (don't need to be initialized)
240 * @param node_member name of the avl_node element inside the
242 * @return pointer to the first element of the avl_tree
243 * (automatically converted to type 'element')
245 #define avl_first_element(tree, element, node_member) \
246 container_of((tree)->list_head.next, typeof(*(element)), node_member)
249 * @param tree pointer to tree
250 * @param element pointer to a node struct that contains the avl_node
251 * (don't need to be initialized)
252 * @param node_member name of the avl_node element inside the
254 * @return pointer to the last element of the avl_tree
255 * (automatically converted to type 'element')
257 #define avl_last_element(tree, element, node_member) \
258 container_of((tree)->list_head.prev, typeof(*(element)), node_member)
261 * This function must not be called for the last element of
264 * @param element pointer to a node of the tree
265 * @param node_member name of the avl_node element inside the
267 * @return pointer to the node after 'element'
268 * (automatically converted to type 'element')
270 #define avl_next_element(element, node_member) \
271 container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
274 * This function must not be called for the first element of
277 * @param element pointer to a node of the tree
278 * @param node_member name of the avl_node element inside the
280 * @return pointer to the node before 'element'
281 * (automatically converted to type 'element')
283 #define avl_prev_element(element, node_member) \
284 container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
287 * Loop over a block of elements of a tree, used similar to a for() command.
288 * This loop should not be used if elements are removed from the tree during
291 * @param first pointer to first element of loop
292 * @param last pointer to last element of loop
293 * @param element pointer to a node of the tree, this element will
294 * contain the current node of the list during the loop
295 * @param node_member name of the avl_node element inside the
298 #define avl_for_element_range(first, last, element, node_member) \
299 for (element = (first); \
300 element->node_member.list.prev != &(last)->node_member.list; \
301 element = avl_next_element(element, node_member))
304 * Loop over a block of elements of a tree backwards, used similar to a for() command.
305 * This loop should not be used if elements are removed from the tree during
308 * @param first pointer to first element of loop
309 * @param last pointer to last element of loop
310 * @param element pointer to a node of the tree, this element will
311 * contain the current node of the list during the loop
312 * @param node_member name of the avl_node element inside the
315 #define avl_for_element_range_reverse(first, last, element, node_member) \
316 for (element = (last); \
317 element->node_member.list.next != &(first)->node_member.list; \
318 element = avl_prev_element(element, node_member))
321 * Loop over all elements of an avl_tree, used similar to a for() command.
322 * This loop should not be used if elements are removed from the tree during
325 * @param tree pointer to avl-tree
326 * @param element pointer to a node of the tree, this element will
327 * contain the current node of the tree during the loop
328 * @param node_member name of the avl_node element inside the
331 #define avl_for_each_element(tree, element, node_member) \
332 avl_for_element_range(avl_first_element(tree, element, node_member), \
333 avl_last_element(tree, element, node_member), \
334 element, node_member)
337 * Loop over all elements of an avl_tree backwards, used similar to a for() command.
338 * This loop should not be used if elements are removed from the tree during
341 * @param tree pointer to avl-tree
342 * @param element pointer to a node of the tree, this element will
343 * contain the current node of the tree during the loop
344 * @param node_member name of the avl_node element inside the
347 #define avl_for_each_element_reverse(tree, element, node_member) \
348 avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
349 avl_last_element(tree, element, node_member), \
350 element, node_member)
353 * Loop over a block of elements of a tree, used similar to a for() command.
354 * This loop should not be used if elements are removed from the tree during
356 * The loop runs from the element 'first' to the end of the tree.
358 * @param tree pointer to avl-tree
359 * @param first pointer to first element of loop
360 * @param element pointer to a node of the tree, this element will
361 * contain the current node of the list during the loop
362 * @param node_member name of the avl_node element inside the
365 #define avl_for_element_to_last(tree, first, element, node_member) \
366 avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
370 * Loop over a block of elements of a tree backwards, used similar to a for() command.
371 * This loop should not be used if elements are removed from the tree during
373 * The loop runs from the element 'first' to the end of the tree.
375 * @param tree pointer to avl-tree
376 * @param first pointer to first element of loop
377 * @param element pointer to a node of the tree, this element will
378 * contain the current node of the list during the loop
379 * @param node_member name of the avl_node element inside the
382 #define avl_for_element_to_last_reverse(tree, first, element, node_member) \
383 avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
386 * Loop over a block of elements of a tree, used similar to a for() command.
387 * This loop should not be used if elements are removed from the tree during
389 * The loop runs from the start of the tree to the element 'last'.
391 * @param tree pointer to avl-tree
392 * @param last pointer to last element of loop
393 * @param element pointer to a node of the tree, this element will
394 * contain the current node of the list during the loop
395 * @param node_member name of the avl_node element inside the
398 #define avl_for_first_to_element(tree, last, element, node_member) \
399 avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
403 * Loop over a block of elements of a tree backwards, used similar to a for() command.
404 * This loop should not be used if elements are removed from the tree during
406 * The loop runs from the start of the tree to the element 'last'.
408 * @param tree pointer to avl-tree
409 * @param last pointer to last element of loop
410 * @param element pointer to a node of the tree, this element will
411 * contain the current node of the list during the loop
412 * @param node_member name of the avl_node element inside the
415 #define avl_for_first_to_element_reverse(tree, last, element, node_member) \
416 avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
419 * Loop over a block of nodes of a tree, used similar to a for() command.
420 * This loop can be used if the current element might be removed from
421 * the tree during the loop. Other elements should not be removed during
424 * @param first_element first element of loop
425 * @param last_element last element of loop
426 * @param element iterator pointer to tree element struct
427 * @param node_member name of avl_node within tree element struct
428 * @param ptr pointer to tree element struct which is used to store
429 * the next node during the loop
431 #define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
432 for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
433 element->node_member.list.prev != &(last_element)->node_member.list; \
434 element = ptr, ptr = avl_next_element(ptr, node_member))
437 * Loop over a block of elements of a tree backwards, used similar to a for() command.
438 * This loop can be used if the current element might be removed from
439 * the tree during the loop. Other elements should not be removed during
442 * @param first_element first element of range (will be last returned by the loop)
443 * @param last_element last element of range (will be first returned by the loop)
444 * @param element iterator pointer to node element struct
445 * @param node_member name of avl_node within node element struct
446 * @param ptr pointer to node element struct which is used to store
447 * the previous node during the loop
449 #define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
450 for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
451 element->node_member.list.next != &(first_element)->node_member.list; \
452 element = ptr, ptr = avl_prev_element(ptr, node_member))
455 * Loop over all elements of an avl_tree, used similar to a for() command.
456 * This loop can be used if the current element might be removed from
457 * the tree during the loop. Other elements should not be removed during
460 * @param tree pointer to avl-tree
461 * @param element pointer to a node of the tree, this element will
462 * contain the current node of the tree during the loop
463 * @param node_member name of the avl_node element inside the
465 * @param ptr pointer to a tree element which is used to store
466 * the next node during the loop
468 #define avl_for_each_element_safe(tree, element, node_member, ptr) \
469 avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
470 avl_last_element(tree, element, node_member), \
471 element, node_member, ptr)
474 * Loop over all elements of an avl_tree backwards, used similar to a for() command.
475 * This loop can be used if the current element might be removed from
476 * the tree during the loop. Other elements should not be removed during
479 * @param tree pointer to avl-tree
480 * @param element pointer to a node of the tree, this element will
481 * contain the current node of the tree during the loop
482 * @param node_member name of the avl_node element inside the
484 * @param ptr pointer to a tree element which is used to store
485 * the next node during the loop
487 #define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \
488 avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
489 avl_last_element(tree, element, node_member), \
490 element, node_member, ptr)
493 * A special loop that removes all elements of the tree and cleans up the tree
494 * root. The loop body is responsible to free the node elements of the tree.
496 * This loop is much faster than a normal one for clearing the tree because it
497 * does not rebalance the tree after each removal. Do NOT use a break command
499 * You can free the memory of the elements within the loop.
500 * Do NOT call avl_delete() on the elements within the loop,
502 * @param tree pointer to avl-tree
503 * @param element pointer to a node of the tree, this element will
504 * contain the current node of the tree during the loop
505 * @param node_member name of the avl_node element inside the
507 * @param ptr pointer to a tree element which is used to store
508 * the next node during the loop
510 #define avl_remove_all_elements(tree, element, node_member, ptr) \
511 for (element = avl_first_element(tree, element, node_member), \
512 ptr = avl_next_element(element, node_member), \
513 list_init_head(&(tree)->list_head), \
514 (tree)->root = NULL; \
516 element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
523 * indent-tabs-mode: nil