libubox: tests: add more blobmsg/json test cases
[project/libubox.git] / avl.h
1 /*
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>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
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
16 * distribution.
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.
20 *
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.
33 *
34 * Visit http://www.olsr.org/git for more information.
35 *
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.
39 */
40
41 #ifndef _AVL_H
42 #define _AVL_H
43
44 #include <stddef.h>
45 #include <stdbool.h>
46
47 #include "list.h"
48
49 /* Support for OLSR.org linker symbol export */
50 #define EXPORT(sym) sym
51
52 /**
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.
55 */
56 struct avl_node {
57 /**
58 * Linked list node for supporting easy iteration and multiple
59 * elments with the same key.
60 *
61 * this must be the first element of an avl_node to
62 * make casting for lists easier
63 */
64 struct list_head list;
65
66 /**
67 * Pointer to parent node in tree, NULL if root node
68 */
69 struct avl_node *parent;
70
71 /**
72 * Pointer to left child
73 */
74 struct avl_node *left;
75
76 /**
77 * Pointer to right child
78 */
79 struct avl_node *right;
80
81 /**
82 * pointer to key of node
83 */
84 const void *key;
85
86 /**
87 * balance state of AVL tree (0,-1,+1)
88 */
89 signed char balance;
90
91 /**
92 * true if first of a series of nodes with same key
93 */
94 bool leader;
95 };
96
97 /**
98 * Prototype for avl comparators
99 * @param k1 first key
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
103 */
104 typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
105
106 /**
107 * This struct is the central management part of an avl tree.
108 * One of them is necessary for each avl_tree.
109 */
110 struct avl_tree {
111 /**
112 * Head of linked list node for supporting easy iteration
113 * and multiple elments with the same key.
114 */
115 struct list_head list_head;
116
117 /**
118 * pointer to the root node of the avl tree, NULL if tree is empty
119 */
120 struct avl_node *root;
121
122 /**
123 * number of nodes in the avl tree
124 */
125 unsigned int count;
126
127 /**
128 * true if multiple nodes with the same key are
129 * allowed in the tree, false otherwise
130 */
131 bool allow_dups;
132
133 /**
134 * pointer to the tree comparator
135 *
136 * First two parameters are keys to compare,
137 * third parameter is a copy of cmp_ptr
138 */
139 avl_tree_comp comp;
140
141 /**
142 * custom pointer delivered to the tree comparator
143 */
144 void *cmp_ptr;
145 };
146
147 /**
148 * internal enum for avl_find_... macros
149 */
150 enum avl_find_mode {
151 AVL_FIND_EQUAL,
152 AVL_FIND_LESSEQUAL,
153 AVL_FIND_GREATEREQUAL
154 };
155
156 #define AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr) \
157 { \
158 .list_head = LIST_HEAD_INIT(_name.list_head), \
159 .comp = _comp, \
160 .allow_dups = _allow_dups, \
161 .cmp_ptr = _cmp_ptr \
162 }
163
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)
167
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 *);
174
175 /**
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
179 */
180 static inline bool
181 avl_is_first(struct avl_tree *tree, struct avl_node *node) {
182 return tree->list_head.next == &node->list;
183 }
184
185 /**
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
189 */
190 static inline bool
191 avl_is_last(struct avl_tree *tree, struct avl_node *node) {
192 return tree->list_head.prev == &node->list;
193 }
194
195 /**
196 * @param tree pointer to avl-tree
197 * @return true if the tree is empty, false otherwise
198 */
199 static inline bool
200 avl_is_empty(struct avl_tree *tree) {
201 return tree->count == 0;
202 }
203
204 /**
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
211 */
212 static inline void *
213 __avl_find_element(const struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) {
214 void *node = NULL;
215
216 switch (mode) {
217 case AVL_FIND_EQUAL:
218 node = avl_find(tree, key);
219 break;
220 case AVL_FIND_LESSEQUAL:
221 node = avl_find_lessequal(tree, key);
222 break;
223 case AVL_FIND_GREATEREQUAL:
224 node = avl_find_greaterequal(tree, key);
225 break;
226 }
227 return node == NULL ? NULL : (((char *)node) - offset);
228 }
229
230 /**
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
236 * larger struct
237 * @return pointer to tree element with the specified key,
238 * NULL if no element was found
239 */
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))
242
243 /**
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
249 * larger struct
250 * return pointer to last tree element with less or equal key than specified key,
251 * NULL if no element was found
252 */
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))
255
256 /**
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
262 * larger struct
263 * return pointer to first tree element with greater or equal key than specified key,
264 * NULL if no element was found
265 */
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))
268
269 /**
270 * This function must not be called for an empty tree
271 *
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
276 * larger struct
277 * @return pointer to the first element of the avl_tree
278 * (automatically converted to type 'element')
279 */
280 #define avl_first_element(tree, element, node_member) \
281 container_of((tree)->list_head.next, __typeof__(*(element)), node_member.list)
282
283 /**
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
288 * larger struct
289 * @return pointer to the last element of the avl_tree
290 * (automatically converted to type 'element')
291 */
292 #define avl_last_element(tree, element, node_member) \
293 container_of((tree)->list_head.prev, __typeof__(*(element)), node_member.list)
294
295 /**
296 * This function must not be called for the last element of
297 * an avl tree
298 *
299 * @param element pointer to a node of the tree
300 * @param node_member name of the avl_node element inside the
301 * larger struct
302 * @return pointer to the node after 'element'
303 * (automatically converted to type 'element')
304 */
305 #define avl_next_element(element, node_member) \
306 container_of((&(element)->node_member.list)->next, __typeof__(*(element)), node_member.list)
307
308 /**
309 * This function must not be called for the first element of
310 * an avl tree
311 *
312 * @param element pointer to a node of the tree
313 * @param node_member name of the avl_node element inside the
314 * larger struct
315 * @return pointer to the node before 'element'
316 * (automatically converted to type 'element')
317 */
318 #define avl_prev_element(element, node_member) \
319 container_of((&(element)->node_member.list)->prev, __typeof__(*(element)), node_member.list)
320
321 /**
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
324 * the loop.
325 *
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
331 * larger struct
332 */
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))
337
338 /**
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
341 * the loop.
342 *
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
348 * larger struct
349 */
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))
354
355 /**
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
358 * the loop.
359 *
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
364 * larger struct
365 */
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)
370
371 /**
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
374 * the loop.
375 *
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
380 * larger struct
381 */
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)
386
387 /**
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
390 * the loop.
391 * The loop runs from the element 'first' to the end of the tree.
392 *
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
398 * larger struct
399 */
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)
402
403
404 /**
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
407 * the loop.
408 * The loop runs from the element 'first' to the end of the tree.
409 *
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
415 * larger struct
416 */
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)
419
420 /**
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
423 * the loop.
424 * The loop runs from the start of the tree to the element 'last'.
425 *
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
431 * larger struct
432 */
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)
435
436
437 /**
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
440 * the loop.
441 * The loop runs from the start of the tree to the element 'last'.
442 *
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
448 * larger struct
449 */
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)
452
453 /**
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
457 * the loop.
458 *
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
465 */
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))
470
471 /**
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
475 * the loop.
476 *
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
483 */
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))
488
489 /**
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
493 * the loop.
494 *
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
499 * larger struct
500 * @param ptr pointer to a tree element which is used to store
501 * the next node during the loop
502 */
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)
507
508 /**
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
512 * the loop.
513 *
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
518 * larger struct
519 * @param ptr pointer to a tree element which is used to store
520 * the next node during the loop
521 */
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)
526
527 /**
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.
530 *
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
533 * inside.
534 * You can free the memory of the elements within the loop.
535 * Do NOT call avl_delete() on the elements within the loop,
536 *
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
541 * larger struct
542 * @param ptr pointer to a tree element which is used to store
543 * the next node during the loop
544 */
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; \
550 (tree)->count > 0; \
551 element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
552
553 #endif /* _AVL_H */
554
555 /*
556 * Local Variables:
557 * c-basic-offset: 2
558 * indent-tabs-mode: nil
559 * End:
560 */