sh/jshn.sh: fix json_get_var() and json_get_type() to not return cached values
[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 #include "list_compat.h"
49
50 /* Support for OLSR.org linker symbol export */
51 #define EXPORT(sym) sym
52
53 /**
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.
56  */
57 struct avl_node {
58   /**
59    * Linked list node for supporting easy iteration and multiple
60    * elments with the same key.
61    *
62    * this must be the first element of an avl_node to
63    * make casting for lists easier
64    */
65   struct list_entity list;
66
67   /**
68    * Pointer to parent node in tree, NULL if root node
69    */
70   struct avl_node *parent;
71
72   /**
73    * Pointer to left child
74    */
75   struct avl_node *left;
76
77   /**
78    * Pointer to right child
79    */
80   struct avl_node *right;
81
82   /**
83    * pointer to key of node
84    */
85   const void *key;
86
87   /**
88    * balance state of AVL tree (0,-1,+1)
89    */
90   signed char balance;
91
92   /**
93    * true if first of a series of nodes with same key
94    */
95   bool leader;
96 };
97
98 /**
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
104  */
105 typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
106
107 /**
108  * This struct is the central management part of an avl tree.
109  * One of them is necessary for each avl_tree.
110  */
111 struct avl_tree {
112   /**
113    * Head of linked list node for supporting easy iteration
114    * and multiple elments with the same key.
115    */
116   struct list_entity list_head;
117
118   /**
119    * pointer to the root node of the avl tree, NULL if tree is empty
120    */
121   struct avl_node *root;
122
123   /**
124    * number of nodes in the avl tree
125    */
126   unsigned int count;
127
128   /**
129    * true if multiple nodes with the same key are
130    * allowed in the tree, false otherwise
131    */
132   bool allow_dups;
133
134   /**
135    * pointer to the tree comparator
136    *
137    * First two parameters are keys to compare,
138    * third parameter is a copy of cmp_ptr
139    */
140   avl_tree_comp comp;
141
142   /**
143    * custom pointer delivered to the tree comparator
144    */
145   void *cmp_ptr;
146 };
147
148 /**
149  * internal enum for avl_find_... macros
150  */
151 enum avl_find_mode {
152   AVL_FIND_EQUAL,
153   AVL_FIND_LESSEQUAL,
154   AVL_FIND_GREATEREQUAL
155 };
156
157 void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
158 struct avl_node *EXPORT(avl_find)(const struct avl_tree *, const void *);
159 struct avl_node *EXPORT(avl_find_greaterequal)(const struct avl_tree *tree, const void *key);
160 struct avl_node *EXPORT(avl_find_lessequal)(const 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
164 /**
165  * @param tree pointer to avl-tree
166  * @param node pointer to node of the tree
167  * @return true if node is the first one of the tree, false otherwise
168  */
169 static inline bool
170 avl_is_first(struct avl_tree *tree, struct avl_node *node) {
171   return tree->list_head.next == &node->list;
172 }
173
174 /**
175  * @param tree pointer to avl-tree
176  * @param node pointer to node of the tree
177  * @return true if node is the last one of the tree, false otherwise
178  */
179 static inline bool
180 avl_is_last(struct avl_tree *tree, struct avl_node *node) {
181   return tree->list_head.prev == &node->list;
182 }
183
184 /**
185  * @param tree pointer to avl-tree
186  * @return true if the tree is empty, false otherwise
187  */
188 static inline bool
189 avl_is_empty(struct avl_tree *tree) {
190   return tree->count == 0;
191 }
192
193 /**
194  * Internal function to support returning the element from a avl tree query
195  * @param tree pointer to avl tree
196  * @param key pointer to key
197  * @param offset offset of node inside the embedded struct
198  * @param mode mode of lookup operation (less equal, equal or greater equal)
199  * @param pointer to elemen, NULL if no fitting one was found
200  */
201 static inline void *
202 __avl_find_element(const struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) {
203   void *node = NULL;
204
205   switch (mode) {
206     case AVL_FIND_EQUAL:
207       node = avl_find(tree, key);
208       break;
209     case AVL_FIND_LESSEQUAL:
210       node = avl_find_lessequal(tree, key);
211       break;
212     case AVL_FIND_GREATEREQUAL:
213       node = avl_find_greaterequal(tree, key);
214       break;
215   }
216   return node == NULL ? NULL : (((char *)node) - offset);
217 }
218
219 /**
220  * @param tree pointer to avl-tree
221  * @param key pointer to key
222  * @param element pointer to a node element
223  *    (don't need to be initialized)
224  * @param node_element name of the avl_node element inside the
225  *    larger struct
226  * @return pointer to tree element with the specified key,
227  *    NULL if no element was found
228  */
229 #define avl_find_element(tree, key, element, node_element) \
230   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
231
232 /**
233  * @param tree pointer to avl-tree
234  * @param key pointer to specified key
235  * @param element pointer to a node element
236  *    (don't need to be initialized)
237  * @param node_element name of the avl_node element inside the
238  *    larger struct
239  * return pointer to last tree element with less or equal key than specified key,
240  *    NULL if no element was found
241  */
242 #define avl_find_le_element(tree, key, element, node_element) \
243   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
244
245 /**
246  * @param tree pointer to avl-tree
247  * @param key pointer to specified key
248  * @param element pointer to a node element
249  *    (don't need to be initialized)
250  * @param node_element name of the avl_node element inside the
251  *    larger struct
252  * return pointer to first tree element with greater or equal key than specified key,
253  *    NULL if no element was found
254  */
255 #define avl_find_ge_element(tree, key, element, node_element) \
256   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
257
258 /**
259  * This function must not be called for an empty tree
260  *
261  * @param tree pointer to avl-tree
262  * @param element pointer to a node element
263  *    (don't need to be initialized)
264  * @param node_member name of the avl_node element inside the
265  *    larger struct
266  * @return pointer to the first element of the avl_tree
267  *    (automatically converted to type 'element')
268  */
269 #define avl_first_element(tree, element, node_member) \
270   container_of((tree)->list_head.next, typeof(*(element)), node_member)
271
272 /**
273  * @param tree pointer to tree
274  * @param element pointer to a node struct that contains the avl_node
275  *    (don't need to be initialized)
276  * @param node_member name of the avl_node element inside the
277  *    larger struct
278  * @return pointer to the last element of the avl_tree
279  *    (automatically converted to type 'element')
280  */
281 #define avl_last_element(tree, element, node_member) \
282   container_of((tree)->list_head.prev, typeof(*(element)), node_member)
283
284 /**
285  * This function must not be called for the last element of
286  * an avl tree
287  *
288  * @param element pointer to a node of the tree
289  * @param node_member name of the avl_node element inside the
290  *    larger struct
291  * @return pointer to the node after 'element'
292  *    (automatically converted to type 'element')
293  */
294 #define avl_next_element(element, node_member) \
295   container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
296
297 /**
298  * This function must not be called for the first element of
299  * an avl tree
300  *
301  * @param element pointer to a node of the tree
302  * @param node_member name of the avl_node element inside the
303  *    larger struct
304  * @return pointer to the node before 'element'
305  *    (automatically converted to type 'element')
306  */
307 #define avl_prev_element(element, node_member) \
308   container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
309
310 /**
311  * Loop over a block of elements of a tree, used similar to a for() command.
312  * This loop should not be used if elements are removed from the tree during
313  * the loop.
314  *
315  * @param first pointer to first element of loop
316  * @param last pointer to last element of loop
317  * @param element pointer to a node of the tree, this element will
318  *    contain the current node of the list during the loop
319  * @param node_member name of the avl_node element inside the
320  *    larger struct
321  */
322 #define avl_for_element_range(first, last, element, node_member) \
323   for (element = (first); \
324        element->node_member.list.prev != &(last)->node_member.list; \
325        element = avl_next_element(element, node_member))
326
327 /**
328  * Loop over a block of elements of a tree backwards, used similar to a for() command.
329  * This loop should not be used if elements are removed from the tree during
330  * the loop.
331  *
332  * @param first pointer to first element of loop
333  * @param last pointer to last element of loop
334  * @param element pointer to a node of the tree, this element will
335  *    contain the current node of the list during the loop
336  * @param node_member name of the avl_node element inside the
337  *    larger struct
338  */
339 #define avl_for_element_range_reverse(first, last, element, node_member) \
340   for (element = (last); \
341        element->node_member.list.next != &(first)->node_member.list; \
342        element = avl_prev_element(element, node_member))
343
344 /**
345  * Loop over all elements of an avl_tree, used similar to a for() command.
346  * This loop should not be used if elements are removed from the tree during
347  * the loop.
348  *
349  * @param tree pointer to avl-tree
350  * @param element pointer to a node of the tree, this element will
351  *    contain the current node of the tree during the loop
352  * @param node_member name of the avl_node element inside the
353  *    larger struct
354  */
355 #define avl_for_each_element(tree, element, node_member) \
356   avl_for_element_range(avl_first_element(tree, element, node_member), \
357                         avl_last_element(tree, element,  node_member), \
358                         element, node_member)
359
360 /**
361  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
362  * This loop should not be used if elements are removed from the tree during
363  * the loop.
364  *
365  * @param tree pointer to avl-tree
366  * @param element pointer to a node of the tree, this element will
367  *    contain the current node of the tree during the loop
368  * @param node_member name of the avl_node element inside the
369  *    larger struct
370  */
371 #define avl_for_each_element_reverse(tree, element, node_member) \
372   avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
373                                 avl_last_element(tree, element,  node_member), \
374                                 element, node_member)
375
376 /**
377  * Loop over a block of elements of a tree, used similar to a for() command.
378  * This loop should not be used if elements are removed from the tree during
379  * the loop.
380  * The loop runs from the element 'first' to the end of the tree.
381  *
382  * @param tree pointer to avl-tree
383  * @param first pointer to first element of loop
384  * @param element pointer to a node of the tree, this element will
385  *    contain the current node of the list during the loop
386  * @param node_member name of the avl_node element inside the
387  *    larger struct
388  */
389 #define avl_for_element_to_last(tree, first, element, node_member) \
390   avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
391
392
393 /**
394  * Loop over a block of elements of a tree backwards, used similar to a for() command.
395  * This loop should not be used if elements are removed from the tree during
396  * the loop.
397  * The loop runs from the element 'first' to the end of the tree.
398  *
399  * @param tree pointer to avl-tree
400  * @param first pointer to first element of loop
401  * @param element pointer to a node of the tree, this element will
402  *    contain the current node of the list during the loop
403  * @param node_member name of the avl_node element inside the
404  *    larger struct
405  */
406 #define avl_for_element_to_last_reverse(tree, first, element, node_member) \
407   avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
408
409 /**
410  * Loop over a block of elements of a tree, used similar to a for() command.
411  * This loop should not be used if elements are removed from the tree during
412  * the loop.
413  * The loop runs from the start of the tree to the element 'last'.
414  *
415  * @param tree pointer to avl-tree
416  * @param last pointer to last element of loop
417  * @param element pointer to a node of the tree, this element will
418  *    contain the current node of the list during the loop
419  * @param node_member name of the avl_node element inside the
420  *    larger struct
421  */
422 #define avl_for_first_to_element(tree, last, element, node_member) \
423   avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
424
425
426 /**
427  * Loop over a block of elements of a tree backwards, used similar to a for() command.
428  * This loop should not be used if elements are removed from the tree during
429  * the loop.
430  * The loop runs from the start of the tree to the element 'last'.
431  *
432  * @param tree pointer to avl-tree
433  * @param last pointer to last element of loop
434  * @param element pointer to a node of the tree, this element will
435  *    contain the current node of the list during the loop
436  * @param node_member name of the avl_node element inside the
437  *    larger struct
438  */
439 #define avl_for_first_to_element_reverse(tree, last, element, node_member) \
440   avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
441
442 /**
443  * Loop over a block of nodes of a tree, used similar to a for() command.
444  * This loop can be used if the current element might be removed from
445  * the tree during the loop. Other elements should not be removed during
446  * the loop.
447  *
448  * @param first_element first element of loop
449  * @param last_element last element of loop
450  * @param element iterator pointer to tree element struct
451  * @param node_member name of avl_node within tree element struct
452  * @param ptr pointer to tree element struct which is used to store
453  *    the next node during the loop
454  */
455 #define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
456   for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
457        element->node_member.list.prev != &(last_element)->node_member.list; \
458        element = ptr, ptr = avl_next_element(ptr, node_member))
459
460 /**
461  * Loop over a block of elements of a tree backwards, used similar to a for() command.
462  * This loop can be used if the current element might be removed from
463  * the tree during the loop. Other elements should not be removed during
464  * the loop.
465  *
466  * @param first_element first element of range (will be last returned by the loop)
467  * @param last_element last element of range (will be first returned by the loop)
468  * @param element iterator pointer to node element struct
469  * @param node_member name of avl_node within node element struct
470  * @param ptr pointer to node element struct which is used to store
471  *    the previous node during the loop
472  */
473 #define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
474   for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
475        element->node_member.list.next != &(first_element)->node_member.list; \
476        element = ptr, ptr = avl_prev_element(ptr, node_member))
477
478 /**
479  * Loop over all elements of an avl_tree, used similar to a for() command.
480  * This loop can be used if the current element might be removed from
481  * the tree during the loop. Other elements should not be removed during
482  * the loop.
483  *
484  * @param tree pointer to avl-tree
485  * @param element pointer to a node of the tree, this element will
486  *    contain the current node of the tree during the loop
487  * @param node_member name of the avl_node element inside the
488  *    larger struct
489  * @param ptr pointer to a tree element which is used to store
490  *    the next node during the loop
491  */
492 #define avl_for_each_element_safe(tree, element, node_member, ptr) \
493   avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
494                              avl_last_element(tree, element, node_member), \
495                              element, node_member, ptr)
496
497 /**
498  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
499  * This loop can be used if the current element might be removed from
500  * the tree during the loop. Other elements should not be removed during
501  * the loop.
502  *
503  * @param tree pointer to avl-tree
504  * @param element pointer to a node of the tree, this element will
505  *    contain the current node of the tree during the loop
506  * @param node_member name of the avl_node element inside the
507  *    larger struct
508  * @param ptr pointer to a tree element which is used to store
509  *    the next node during the loop
510  */
511 #define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \
512   avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
513                                      avl_last_element(tree, element, node_member), \
514                                      element, node_member, ptr)
515
516 /**
517  * A special loop that removes all elements of the tree and cleans up the tree
518  * root. The loop body is responsible to free the node elements of the tree.
519  *
520  * This loop is much faster than a normal one for clearing the tree because it
521  * does not rebalance the tree after each removal. Do NOT use a break command
522  * inside.
523  * You can free the memory of the elements within the loop.
524  * Do NOT call avl_delete() on the elements within the loop,
525  *
526  * @param tree pointer to avl-tree
527  * @param element pointer to a node of the tree, this element will
528  *    contain the current node of the tree during the loop
529  * @param node_member name of the avl_node element inside the
530  *    larger struct
531  * @param ptr pointer to a tree element which is used to store
532  *    the next node during the loop
533  */
534 #define avl_remove_all_elements(tree, element, node_member, ptr) \
535   for (element = avl_first_element(tree, element, node_member), \
536        ptr = avl_next_element(element, node_member), \
537        list_init_head(&(tree)->list_head), \
538        (tree)->root = NULL; \
539        (tree)->count > 0; \
540        element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
541
542 #endif /* _AVL_H */
543
544 /*
545  * Local Variables:
546  * c-basic-offset: 2
547  * indent-tabs-mode: nil
548  * End:
549  */