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 void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
157 struct avl_node *EXPORT(avl_find)(const struct avl_tree *, const void *);
158 struct avl_node *EXPORT(avl_find_greaterequal)(const struct avl_tree *tree, const void *key);
159 struct avl_node *EXPORT(avl_find_lessequal)(const struct avl_tree *tree, const void *key);
160 int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
161 void EXPORT(avl_delete)(struct avl_tree *, struct avl_node *);
164 * @param tree pointer to avl-tree
165 * @param node pointer to node of the tree
166 * @return true if node is the first one of the tree, false otherwise
169 avl_is_first(struct avl_tree *tree, struct avl_node *node) {
170 return tree->list_head.next == &node->list;
174 * @param tree pointer to avl-tree
175 * @param node pointer to node of the tree
176 * @return true if node is the last one of the tree, false otherwise
179 avl_is_last(struct avl_tree *tree, struct avl_node *node) {
180 return tree->list_head.prev == &node->list;
184 * @param tree pointer to avl-tree
185 * @return true if the tree is empty, false otherwise
188 avl_is_empty(struct avl_tree *tree) {
189 return tree->count == 0;
193 * Internal function to support returning the element from a avl tree query
194 * @param tree pointer to avl tree
195 * @param key pointer to key
196 * @param offset offset of node inside the embedded struct
197 * @param mode mode of lookup operation (less equal, equal or greater equal)
198 * @param pointer to elemen, NULL if no fitting one was found
201 __avl_find_element(const struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) {
206 node = avl_find(tree, key);
208 case AVL_FIND_LESSEQUAL:
209 node = avl_find_lessequal(tree, key);
211 case AVL_FIND_GREATEREQUAL:
212 node = avl_find_greaterequal(tree, key);
215 return node == NULL ? NULL : (((char *)node) - offset);
219 * @param tree pointer to avl-tree
220 * @param key pointer to key
221 * @param element pointer to a node element
222 * (don't need to be initialized)
223 * @param node_element name of the avl_node element inside the
225 * @return pointer to tree element with the specified key,
226 * NULL if no element was found
228 #define avl_find_element(tree, key, element, node_element) \
229 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
232 * @param tree pointer to avl-tree
233 * @param key pointer to specified key
234 * @param element pointer to a node element
235 * (don't need to be initialized)
236 * @param node_element name of the avl_node element inside the
238 * return pointer to last tree element with less or equal key than specified key,
239 * NULL if no element was found
241 #define avl_find_le_element(tree, key, element, node_element) \
242 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
245 * @param tree pointer to avl-tree
246 * @param key pointer to specified key
247 * @param element pointer to a node element
248 * (don't need to be initialized)
249 * @param node_element name of the avl_node element inside the
251 * return pointer to first tree element with greater or equal key than specified key,
252 * NULL if no element was found
254 #define avl_find_ge_element(tree, key, element, node_element) \
255 ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
258 * This function must not be called for an empty tree
260 * @param tree pointer to avl-tree
261 * @param element pointer to a node element
262 * (don't need to be initialized)
263 * @param node_member name of the avl_node element inside the
265 * @return pointer to the first element of the avl_tree
266 * (automatically converted to type 'element')
268 #define avl_first_element(tree, element, node_member) \
269 container_of((tree)->list_head.next, typeof(*(element)), node_member.list)
272 * @param tree pointer to tree
273 * @param element pointer to a node struct that contains the avl_node
274 * (don't need to be initialized)
275 * @param node_member name of the avl_node element inside the
277 * @return pointer to the last element of the avl_tree
278 * (automatically converted to type 'element')
280 #define avl_last_element(tree, element, node_member) \
281 container_of((tree)->list_head.prev, typeof(*(element)), node_member.list)
284 * This function must not be called for the last element of
287 * @param element pointer to a node of the tree
288 * @param node_member name of the avl_node element inside the
290 * @return pointer to the node after 'element'
291 * (automatically converted to type 'element')
293 #define avl_next_element(element, node_member) \
294 container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member.list)
297 * This function must not be called for the first element of
300 * @param element pointer to a node of the tree
301 * @param node_member name of the avl_node element inside the
303 * @return pointer to the node before 'element'
304 * (automatically converted to type 'element')
306 #define avl_prev_element(element, node_member) \
307 container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member.list)
310 * Loop over a block of elements of a tree, used similar to a for() command.
311 * This loop should not be used if elements are removed from the tree during
314 * @param first pointer to first element of loop
315 * @param last pointer to last element of loop
316 * @param element pointer to a node of the tree, this element will
317 * contain the current node of the list during the loop
318 * @param node_member name of the avl_node element inside the
321 #define avl_for_element_range(first, last, element, node_member) \
322 for (element = (first); \
323 element->node_member.list.prev != &(last)->node_member.list; \
324 element = avl_next_element(element, node_member))
327 * Loop over a block of elements of a tree backwards, used similar to a for() command.
328 * This loop should not be used if elements are removed from the tree during
331 * @param first pointer to first element of loop
332 * @param last pointer to last element of loop
333 * @param element pointer to a node of the tree, this element will
334 * contain the current node of the list during the loop
335 * @param node_member name of the avl_node element inside the
338 #define avl_for_element_range_reverse(first, last, element, node_member) \
339 for (element = (last); \
340 element->node_member.list.next != &(first)->node_member.list; \
341 element = avl_prev_element(element, node_member))
344 * Loop over all elements of an avl_tree, used similar to a for() command.
345 * This loop should not be used if elements are removed from the tree during
348 * @param tree pointer to avl-tree
349 * @param element pointer to a node of the tree, this element will
350 * contain the current node of the tree during the loop
351 * @param node_member name of the avl_node element inside the
354 #define avl_for_each_element(tree, element, node_member) \
355 avl_for_element_range(avl_first_element(tree, element, node_member), \
356 avl_last_element(tree, element, node_member), \
357 element, node_member)
360 * Loop over all elements of an avl_tree backwards, used similar to a for() command.
361 * This loop should not be used if elements are removed from the tree during
364 * @param tree pointer to avl-tree
365 * @param element pointer to a node of the tree, this element will
366 * contain the current node of the tree during the loop
367 * @param node_member name of the avl_node element inside the
370 #define avl_for_each_element_reverse(tree, element, node_member) \
371 avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
372 avl_last_element(tree, element, node_member), \
373 element, node_member)
376 * Loop over a block of elements of a tree, used similar to a for() command.
377 * This loop should not be used if elements are removed from the tree during
379 * The loop runs from the element 'first' to the end of the tree.
381 * @param tree pointer to avl-tree
382 * @param first pointer to first element of loop
383 * @param element pointer to a node of the tree, this element will
384 * contain the current node of the list during the loop
385 * @param node_member name of the avl_node element inside the
388 #define avl_for_element_to_last(tree, first, element, node_member) \
389 avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
393 * Loop over a block of elements of a tree backwards, used similar to a for() command.
394 * This loop should not be used if elements are removed from the tree during
396 * The loop runs from the element 'first' to the end of the tree.
398 * @param tree pointer to avl-tree
399 * @param first pointer to first element of loop
400 * @param element pointer to a node of the tree, this element will
401 * contain the current node of the list during the loop
402 * @param node_member name of the avl_node element inside the
405 #define avl_for_element_to_last_reverse(tree, first, element, node_member) \
406 avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
409 * Loop over a block of elements of a tree, used similar to a for() command.
410 * This loop should not be used if elements are removed from the tree during
412 * The loop runs from the start of the tree to the element 'last'.
414 * @param tree pointer to avl-tree
415 * @param last pointer to last element of loop
416 * @param element pointer to a node of the tree, this element will
417 * contain the current node of the list during the loop
418 * @param node_member name of the avl_node element inside the
421 #define avl_for_first_to_element(tree, last, element, node_member) \
422 avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
426 * Loop over a block of elements of a tree backwards, used similar to a for() command.
427 * This loop should not be used if elements are removed from the tree during
429 * The loop runs from the start of the tree to the element 'last'.
431 * @param tree pointer to avl-tree
432 * @param last pointer to last element of loop
433 * @param element pointer to a node of the tree, this element will
434 * contain the current node of the list during the loop
435 * @param node_member name of the avl_node element inside the
438 #define avl_for_first_to_element_reverse(tree, last, element, node_member) \
439 avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
442 * Loop over a block of nodes of a tree, used similar to a for() command.
443 * This loop can be used if the current element might be removed from
444 * the tree during the loop. Other elements should not be removed during
447 * @param first_element first element of loop
448 * @param last_element last element of loop
449 * @param element iterator pointer to tree element struct
450 * @param node_member name of avl_node within tree element struct
451 * @param ptr pointer to tree element struct which is used to store
452 * the next node during the loop
454 #define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
455 for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
456 element->node_member.list.prev != &(last_element)->node_member.list; \
457 element = ptr, ptr = avl_next_element(ptr, node_member))
460 * Loop over a block of elements of a tree backwards, used similar to a for() command.
461 * This loop can be used if the current element might be removed from
462 * the tree during the loop. Other elements should not be removed during
465 * @param first_element first element of range (will be last returned by the loop)
466 * @param last_element last element of range (will be first returned by the loop)
467 * @param element iterator pointer to node element struct
468 * @param node_member name of avl_node within node element struct
469 * @param ptr pointer to node element struct which is used to store
470 * the previous node during the loop
472 #define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
473 for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
474 element->node_member.list.next != &(first_element)->node_member.list; \
475 element = ptr, ptr = avl_prev_element(ptr, node_member))
478 * Loop over all elements of an avl_tree, used similar to a for() command.
479 * This loop can be used if the current element might be removed from
480 * the tree during the loop. Other elements should not be removed during
483 * @param tree pointer to avl-tree
484 * @param element pointer to a node of the tree, this element will
485 * contain the current node of the tree during the loop
486 * @param node_member name of the avl_node element inside the
488 * @param ptr pointer to a tree element which is used to store
489 * the next node during the loop
491 #define avl_for_each_element_safe(tree, element, node_member, ptr) \
492 avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
493 avl_last_element(tree, element, node_member), \
494 element, node_member, ptr)
497 * Loop over all elements of an avl_tree backwards, used similar to a for() command.
498 * This loop can be used if the current element might be removed from
499 * the tree during the loop. Other elements should not be removed during
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_for_each_element_reverse_safe(tree, element, node_member, ptr) \
511 avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
512 avl_last_element(tree, element, node_member), \
513 element, node_member, ptr)
516 * A special loop that removes all elements of the tree and cleans up the tree
517 * root. The loop body is responsible to free the node elements of the tree.
519 * This loop is much faster than a normal one for clearing the tree because it
520 * does not rebalance the tree after each removal. Do NOT use a break command
522 * You can free the memory of the elements within the loop.
523 * Do NOT call avl_delete() on the elements within the loop,
525 * @param tree pointer to avl-tree
526 * @param element pointer to a node of the tree, this element will
527 * contain the current node of the tree during the loop
528 * @param node_member name of the avl_node element inside the
530 * @param ptr pointer to a tree element which is used to store
531 * the next node during the loop
533 #define avl_remove_all_elements(tree, element, node_member, ptr) \
534 for (element = avl_first_element(tree, element, node_member), \
535 ptr = avl_next_element(element, node_member), \
536 INIT_LIST_HEAD(&(tree)->list_head), \
537 (tree)->root = NULL; \
539 element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
546 * indent-tabs-mode: nil