usock: add helper waiting for socket to be ready
[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  */