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.
49 /* Support for OLSR.org linker symbol export */
50 #define EXPORT(sym) sym
53 * This element is a member of a avl-tree. It must be contained in all
54 * larger structs that should be put into a tree.
58 * Linked list node for supporting easy iteration and multiple
59 * elments with the same key.
61 * this must be the first element of an avl_node to
62 * make casting for lists easier
64 struct list_head list;
67 * Pointer to parent node in tree, NULL if root node
69 struct avl_node *parent;
72 * Pointer to left child
74 struct avl_node *left;
77 * Pointer to right child
79 struct avl_node *right;
82 * pointer to key of node
87 * balance state of AVL tree (0,-1,+1)
92 * true if first of a series of nodes with same key
98 * Prototype for avl comparators
100 * @param k2 second key
101 * @param ptr custom data for tree comparator
102 * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
104 typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
107 * This struct is the central management part of an avl tree.
108 * One of them is necessary for each avl_tree.
112 * Head of linked list node for supporting easy iteration
113 * and multiple elments with the same key.
115 struct list_head list_head;
118 * pointer to the root node of the avl tree, NULL if tree is empty
120 struct avl_node *root;
123 * number of nodes in the avl tree
128 * true if multiple nodes with the same key are
129 * allowed in the tree, false otherwise
134 * pointer to the tree comparator
136 * First two parameters are keys to compare,
137 * third parameter is a copy of cmp_ptr
142 * custom pointer delivered to the tree comparator
148 * internal enum for avl_find_... macros
153 AVL_FIND_GREATEREQUAL
156 #define AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr) \
158 .list_head = LIST_HEAD_INIT(_name.list_head), \
160 .allow_dups = _allow_dups, \
161 .cmp_ptr = _cmp_ptr \
164 #define AVL_TREE(_name, _comp, _allow_dups, _cmp_ptr) \
165 struct avl_tree _name = \
166 AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr)
168 void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
169 struct avl_node *EXPORT(avl_find)(const struct avl_tree *, const void *);
170 struct avl_node *EXPORT(avl_find_greaterequal)(const struct avl_tree *tree, const void *key);
171 struct avl_node *EXPORT(avl_find_lessequal)(const struct avl_tree *tree, const void *key);
172 int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
173 void EXPORT(avl_delete)(struct avl_tree *, struct avl_node *);
176 * @param tree pointer to avl-tree
177 * @param node pointer to node of the tree
178 * @return true if node is the first one of the tree, false otherwise
181 avl_is_first(struct avl_tree *tree, struct avl_node *node) {
182 return tree->list_head.next == &node->list;
186 * @param tree pointer to avl-tree
187 * @param node pointer to node of the tree
188 * @return true if node is the last one of the tree, false otherwise
191 avl_is_last(struct avl_tree *tree, struct avl_node *node) {
192 return tree->list_head.prev == &node->list;
196 * @param tree pointer to avl-tree
197 * @return true if the tree is empty, false otherwise
200 avl_is_empty(struct avl_tree *tree) {
201 return tree->count == 0;
205 * Internal function to support returning the element from a avl tree query
206 * @param tree pointer to avl tree
207 * @param key pointer to key
208 * @param offset offset of node inside the embedded struct
209 * @param mode mode of lookup operation (less equal, equal or greater equal)
210 * @param pointer to elemen, NULL if no fitting one was found
213 __avl_find_element(const struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) {
218 node = avl_find(tree, key);
220 case AVL_FIND_LESSEQUAL:
221 node = avl_find_lessequal(tree, key);
223 case AVL_FIND_GREATEREQUAL:
224 node = avl_find_greaterequal(tree, key);
227 return node == NULL ? NULL : (((char *)node) - offset);
231 * @param tree pointer to avl-tree
232 * @param key pointer to key
233 * @param element pointer to a node element
234 * (don't need to be initialized)
235 * @param node_element name of the avl_node element inside the
237 * @return pointer to tree element with the specified key,
238 * NULL if no element was found
240 #define avl_find_element(tree, key, element, node_element) \
241 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
244 * @param tree pointer to avl-tree
245 * @param key pointer to specified key
246 * @param element pointer to a node element
247 * (don't need to be initialized)
248 * @param node_element name of the avl_node element inside the
250 * return pointer to last tree element with less or equal key than specified key,
251 * NULL if no element was found
253 #define avl_find_le_element(tree, key, element, node_element) \
254 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
257 * @param tree pointer to avl-tree
258 * @param key pointer to specified key
259 * @param element pointer to a node element
260 * (don't need to be initialized)
261 * @param node_element name of the avl_node element inside the
263 * return pointer to first tree element with greater or equal key than specified key,
264 * NULL if no element was found
266 #define avl_find_ge_element(tree, key, element, node_element) \
267 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
270 * This function must not be called for an empty tree
272 * @param tree pointer to avl-tree
273 * @param element pointer to a node element
274 * (don't need to be initialized)
275 * @param node_member name of the avl_node element inside the
277 * @return pointer to the first element of the avl_tree
278 * (automatically converted to type 'element')
280 #define avl_first_element(tree, element, node_member) \
281 container_of((tree)->list_head.next, typeof(*(element)), node_member.list)
284 * @param tree pointer to tree
285 * @param element pointer to a node struct that contains the avl_node
286 * (don't need to be initialized)
287 * @param node_member name of the avl_node element inside the
289 * @return pointer to the last element of the avl_tree
290 * (automatically converted to type 'element')
292 #define avl_last_element(tree, element, node_member) \
293 container_of((tree)->list_head.prev, typeof(*(element)), node_member.list)
296 * This function must not be called for the last element of
299 * @param element pointer to a node of the tree
300 * @param node_member name of the avl_node element inside the
302 * @return pointer to the node after 'element'
303 * (automatically converted to type 'element')
305 #define avl_next_element(element, node_member) \
306 container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member.list)
309 * This function must not be called for the first element of
312 * @param element pointer to a node of the tree
313 * @param node_member name of the avl_node element inside the
315 * @return pointer to the node before 'element'
316 * (automatically converted to type 'element')
318 #define avl_prev_element(element, node_member) \
319 container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member.list)
322 * Loop over a block of elements of a tree, used similar to a for() command.
323 * This loop should not be used if elements are removed from the tree during
326 * @param first pointer to first element of loop
327 * @param last pointer to last element of loop
328 * @param element pointer to a node of the tree, this element will
329 * contain the current node of the list during the loop
330 * @param node_member name of the avl_node element inside the
333 #define avl_for_element_range(first, last, element, node_member) \
334 for (element = (first); \
335 element->node_member.list.prev != &(last)->node_member.list; \
336 element = avl_next_element(element, node_member))
339 * Loop over a block of elements of a tree backwards, used similar to a for() command.
340 * This loop should not be used if elements are removed from the tree during
343 * @param first pointer to first element of loop
344 * @param last pointer to last element of loop
345 * @param element pointer to a node of the tree, this element will
346 * contain the current node of the list during the loop
347 * @param node_member name of the avl_node element inside the
350 #define avl_for_element_range_reverse(first, last, element, node_member) \
351 for (element = (last); \
352 element->node_member.list.next != &(first)->node_member.list; \
353 element = avl_prev_element(element, node_member))
356 * Loop over all elements of an avl_tree, used similar to a for() command.
357 * This loop should not be used if elements are removed from the tree during
360 * @param tree pointer to avl-tree
361 * @param element pointer to a node of the tree, this element will
362 * contain the current node of the tree during the loop
363 * @param node_member name of the avl_node element inside the
366 #define avl_for_each_element(tree, element, node_member) \
367 avl_for_element_range(avl_first_element(tree, element, node_member), \
368 avl_last_element(tree, element, node_member), \
369 element, node_member)
372 * Loop over all elements of an avl_tree backwards, used similar to a for() command.
373 * This loop should not be used if elements are removed from the tree during
376 * @param tree pointer to avl-tree
377 * @param element pointer to a node of the tree, this element will
378 * contain the current node of the tree during the loop
379 * @param node_member name of the avl_node element inside the
382 #define avl_for_each_element_reverse(tree, element, node_member) \
383 avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
384 avl_last_element(tree, element, node_member), \
385 element, node_member)
388 * Loop over a block of elements of a tree, used similar to a for() command.
389 * This loop should not be used if elements are removed from the tree during
391 * The loop runs from the element 'first' to the end of the tree.
393 * @param tree pointer to avl-tree
394 * @param first pointer to first element of loop
395 * @param element pointer to a node of the tree, this element will
396 * contain the current node of the list during the loop
397 * @param node_member name of the avl_node element inside the
400 #define avl_for_element_to_last(tree, first, element, node_member) \
401 avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
405 * Loop over a block of elements of a tree backwards, used similar to a for() command.
406 * This loop should not be used if elements are removed from the tree during
408 * The loop runs from the element 'first' to the end of the tree.
410 * @param tree pointer to avl-tree
411 * @param first pointer to first element of loop
412 * @param element pointer to a node of the tree, this element will
413 * contain the current node of the list during the loop
414 * @param node_member name of the avl_node element inside the
417 #define avl_for_element_to_last_reverse(tree, first, element, node_member) \
418 avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
421 * Loop over a block of elements of a tree, used similar to a for() command.
422 * This loop should not be used if elements are removed from the tree during
424 * The loop runs from the start of the tree to the element 'last'.
426 * @param tree pointer to avl-tree
427 * @param last pointer to last element of loop
428 * @param element pointer to a node of the tree, this element will
429 * contain the current node of the list during the loop
430 * @param node_member name of the avl_node element inside the
433 #define avl_for_first_to_element(tree, last, element, node_member) \
434 avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
438 * Loop over a block of elements of a tree backwards, used similar to a for() command.
439 * This loop should not be used if elements are removed from the tree during
441 * The loop runs from the start of the tree to the element 'last'.
443 * @param tree pointer to avl-tree
444 * @param last pointer to last element of loop
445 * @param element pointer to a node of the tree, this element will
446 * contain the current node of the list during the loop
447 * @param node_member name of the avl_node element inside the
450 #define avl_for_first_to_element_reverse(tree, last, element, node_member) \
451 avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
454 * Loop over a block of nodes of a tree, used similar to a for() command.
455 * This loop can be used if the current element might be removed from
456 * the tree during the loop. Other elements should not be removed during
459 * @param first_element first element of loop
460 * @param last_element last element of loop
461 * @param element iterator pointer to tree element struct
462 * @param node_member name of avl_node within tree element struct
463 * @param ptr pointer to tree element struct which is used to store
464 * the next node during the loop
466 #define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
467 for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
468 element->node_member.list.prev != &(last_element)->node_member.list; \
469 element = ptr, ptr = avl_next_element(ptr, node_member))
472 * Loop over a block of elements of a tree backwards, used similar to a for() command.
473 * This loop can be used if the current element might be removed from
474 * the tree during the loop. Other elements should not be removed during
477 * @param first_element first element of range (will be last returned by the loop)
478 * @param last_element last element of range (will be first returned by the loop)
479 * @param element iterator pointer to node element struct
480 * @param node_member name of avl_node within node element struct
481 * @param ptr pointer to node element struct which is used to store
482 * the previous node during the loop
484 #define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
485 for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
486 element->node_member.list.next != &(first_element)->node_member.list; \
487 element = ptr, ptr = avl_prev_element(ptr, node_member))
490 * Loop over all elements of an avl_tree, used similar to a for() command.
491 * This loop can be used if the current element might be removed from
492 * the tree during the loop. Other elements should not be removed during
495 * @param tree pointer to avl-tree
496 * @param element pointer to a node of the tree, this element will
497 * contain the current node of the tree during the loop
498 * @param node_member name of the avl_node element inside the
500 * @param ptr pointer to a tree element which is used to store
501 * the next node during the loop
503 #define avl_for_each_element_safe(tree, element, node_member, ptr) \
504 avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
505 avl_last_element(tree, element, node_member), \
506 element, node_member, ptr)
509 * Loop over all elements of an avl_tree backwards, used similar to a for() command.
510 * This loop can be used if the current element might be removed from
511 * the tree during the loop. Other elements should not be removed during
514 * @param tree pointer to avl-tree
515 * @param element pointer to a node of the tree, this element will
516 * contain the current node of the tree during the loop
517 * @param node_member name of the avl_node element inside the
519 * @param ptr pointer to a tree element which is used to store
520 * the next node during the loop
522 #define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \
523 avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
524 avl_last_element(tree, element, node_member), \
525 element, node_member, ptr)
528 * A special loop that removes all elements of the tree and cleans up the tree
529 * root. The loop body is responsible to free the node elements of the tree.
531 * This loop is much faster than a normal one for clearing the tree because it
532 * does not rebalance the tree after each removal. Do NOT use a break command
534 * You can free the memory of the elements within the loop.
535 * Do NOT call avl_delete() on the elements within the loop,
537 * @param tree pointer to avl-tree
538 * @param element pointer to a node of the tree, this element will
539 * contain the current node of the tree during the loop
540 * @param node_member name of the avl_node element inside the
542 * @param ptr pointer to a tree element which is used to store
543 * the next node during the loop
545 #define avl_remove_all_elements(tree, element, node_member, ptr) \
546 for (element = avl_first_element(tree, element, node_member), \
547 ptr = avl_next_element(element, node_member), \
548 INIT_LIST_HEAD(&(tree)->list_head), \
549 (tree)->root = NULL; \
551 element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
558 * indent-tabs-mode: nil