Update to new avl/list iteration macros
[olsrd.git] / src / common / 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 "container_of.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   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)(struct avl_tree *, const void *);
159 struct avl_node *EXPORT(avl_find_greaterequal)(struct avl_tree *tree, const void *key);
160 struct avl_node *EXPORT(avl_find_lessequal)(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 void *EXPORT(__avl_find_element)(struct avl_tree *tree, const void *key,
164     size_t offset, enum avl_find_mode mode);
165
166 /**
167  * @param tree pointer to avl-tree
168  * @param node pointer to node of the tree
169  * @return true if node is the first one of the tree, false otherwise
170  */
171 static inline bool
172 avl_is_first(struct avl_tree *tree, struct avl_node *node) {
173   return tree->list_head.next == &node->list;
174 }
175
176 /**
177  * @param tree pointer to avl-tree
178  * @param node pointer to node of the tree
179  * @return true if node is the last one of the tree, false otherwise
180  */
181 static inline bool
182 avl_is_last(struct avl_tree *tree, struct avl_node *node) {
183   return tree->list_head.prev == &node->list;
184 }
185
186 /**
187  * @param tree pointer to avl-tree
188  * @return true if the tree is empty, false otherwise
189  */
190 static inline bool
191 avl_is_empty(struct avl_tree *tree) {
192   return tree->count == 0;
193 }
194
195 /**
196  * @param tree pointer to avl-tree
197  * @param key pointer to key
198  * @param element pointer to a node element
199  *    (don't need to be initialized)
200  * @param node_element name of the avl_node element inside the
201  *    larger struct
202  * @return pointer to tree element with the specified key,
203  *    NULL if no element was found
204  */
205 #define avl_find_element(tree, key, element, node_element) \
206   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
207
208 /**
209  * @param tree pointer to avl-tree
210  * @param key pointer to specified key
211  * @param element pointer to a node element
212  *    (don't need to be initialized)
213  * @param node_element name of the avl_node element inside the
214  *    larger struct
215  * return pointer to last tree element with less or equal key than specified key,
216  *    NULL if no element was found
217  */
218 #define avl_find_le_element(tree, key, element, node_element) \
219   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
220
221 /**
222  * @param tree pointer to avl-tree
223  * @param key pointer to specified key
224  * @param element pointer to a node element
225  *    (don't need to be initialized)
226  * @param node_element name of the avl_node element inside the
227  *    larger struct
228  * return pointer to first tree element with greater or equal key than specified key,
229  *    NULL if no element was found
230  */
231 #define avl_find_ge_element(tree, key, element, node_element) \
232   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
233
234 /**
235  * This function must not be called for an empty tree
236  *
237  * @param tree pointer to avl-tree
238  * @param element pointer to a node element
239  *    (don't need to be initialized)
240  * @param node_member name of the avl_node element inside the
241  *    larger struct
242  * @return pointer to the first element of the avl_tree
243  *    (automatically converted to type 'element')
244  */
245 #define avl_first_element(tree, element, node_member) \
246   container_of((tree)->list_head.next, typeof(*(element)), node_member)
247
248 /**
249  * @param tree pointer to tree
250  * @param element pointer to a node struct that contains the avl_node
251  *    (don't need to be initialized)
252  * @param node_member name of the avl_node element inside the
253  *    larger struct
254  * @return pointer to the last element of the avl_tree
255  *    (automatically converted to type 'element')
256  */
257 #define avl_last_element(tree, element, node_member) \
258   container_of((tree)->list_head.prev, typeof(*(element)), node_member)
259
260 /**
261  * This function must not be called for the last element of
262  * an avl tree
263  *
264  * @param element pointer to a node of the tree
265  * @param node_member name of the avl_node element inside the
266  *    larger struct
267  * @return pointer to the node after 'element'
268  *    (automatically converted to type 'element')
269  */
270 #define avl_next_element(element, node_member) \
271   container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
272
273 /**
274  * This function must not be called for the first element of
275  * an avl tree
276  *
277  * @param element pointer to a node of the tree
278  * @param node_member name of the avl_node element inside the
279  *    larger struct
280  * @return pointer to the node before 'element'
281  *    (automatically converted to type 'element')
282  */
283 #define avl_prev_element(element, node_member) \
284   container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
285
286 /**
287  * Loop over a block of elements of a tree, used similar to a for() command.
288  * This loop should not be used if elements are removed from the tree during
289  * the loop.
290  *
291  * @param first pointer to first element of loop
292  * @param last pointer to last element of loop
293  * @param element pointer to a node of the tree, this element will
294  *    contain the current node of the list during the loop
295  * @param node_member name of the avl_node element inside the
296  *    larger struct
297  */
298 #define avl_for_element_range(first, last, element, node_member) \
299   for (element = (first); \
300        element->node_member.list.prev != &(last)->node_member.list; \
301        element = avl_next_element(element, node_member))
302
303 /**
304  * Loop over a block of elements of a tree backwards, used similar to a for() command.
305  * This loop should not be used if elements are removed from the tree during
306  * the loop.
307  *
308  * @param first pointer to first element of loop
309  * @param last pointer to last element of loop
310  * @param element pointer to a node of the tree, this element will
311  *    contain the current node of the list during the loop
312  * @param node_member name of the avl_node element inside the
313  *    larger struct
314  */
315 #define avl_for_element_range_reverse(first, last, element, node_member) \
316   for (element = (last); \
317        element->node_member.list.next != &(first)->node_member.list; \
318        element = avl_prev_element(element, node_member))
319
320 /**
321  * Loop over all elements of an avl_tree, used similar to a for() command.
322  * This loop should not be used if elements are removed from the tree during
323  * the loop.
324  *
325  * @param tree pointer to avl-tree
326  * @param element pointer to a node of the tree, this element will
327  *    contain the current node of the tree during the loop
328  * @param node_member name of the avl_node element inside the
329  *    larger struct
330  */
331 #define avl_for_each_element(tree, element, node_member) \
332   avl_for_element_range(avl_first_element(tree, element, node_member), \
333                         avl_last_element(tree, element,  node_member), \
334                         element, node_member)
335
336 /**
337  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
338  * This loop should not be used if elements are removed from the tree during
339  * the loop.
340  *
341  * @param tree pointer to avl-tree
342  * @param element pointer to a node of the tree, this element will
343  *    contain the current node of the tree during the loop
344  * @param node_member name of the avl_node element inside the
345  *    larger struct
346  */
347 #define avl_for_each_element_reverse(tree, element, node_member) \
348   avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
349                                 avl_last_element(tree, element,  node_member), \
350                                 element, node_member)
351
352 /**
353  * Loop over a block of elements of a tree, used similar to a for() command.
354  * This loop should not be used if elements are removed from the tree during
355  * the loop.
356  * The loop runs from the element 'first' to the end of the tree.
357  *
358  * @param tree pointer to avl-tree
359  * @param first pointer to first element of loop
360  * @param element pointer to a node of the tree, this element will
361  *    contain the current node of the list during the loop
362  * @param node_member name of the avl_node element inside the
363  *    larger struct
364  */
365 #define avl_for_element_to_last(tree, first, element, node_member) \
366   avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
367
368
369 /**
370  * Loop over a block of elements of a tree backwards, used similar to a for() command.
371  * This loop should not be used if elements are removed from the tree during
372  * the loop.
373  * The loop runs from the element 'first' to the end of the tree.
374  *
375  * @param tree pointer to avl-tree
376  * @param first pointer to first element of loop
377  * @param element pointer to a node of the tree, this element will
378  *    contain the current node of the list during the loop
379  * @param node_member name of the avl_node element inside the
380  *    larger struct
381  */
382 #define avl_for_element_to_last_reverse(tree, first, element, node_member) \
383   avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
384
385 /**
386  * Loop over a block of elements of a tree, used similar to a for() command.
387  * This loop should not be used if elements are removed from the tree during
388  * the loop.
389  * The loop runs from the start of the tree to the element 'last'.
390  *
391  * @param tree pointer to avl-tree
392  * @param last pointer to last element of loop
393  * @param element pointer to a node of the tree, this element will
394  *    contain the current node of the list during the loop
395  * @param node_member name of the avl_node element inside the
396  *    larger struct
397  */
398 #define avl_for_first_to_element(tree, last, element, node_member) \
399   avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
400
401
402 /**
403  * Loop over a block of elements of a tree backwards, used similar to a for() command.
404  * This loop should not be used if elements are removed from the tree during
405  * the loop.
406  * The loop runs from the start of the tree to the element 'last'.
407  *
408  * @param tree pointer to avl-tree
409  * @param last pointer to last element of loop
410  * @param element pointer to a node of the tree, this element will
411  *    contain the current node of the list during the loop
412  * @param node_member name of the avl_node element inside the
413  *    larger struct
414  */
415 #define avl_for_first_to_element_reverse(tree, last, element, node_member) \
416   avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
417
418 /**
419  * Loop over a block of nodes of a tree, used similar to a for() command.
420  * This loop can be used if the current element might be removed from
421  * the tree during the loop. Other elements should not be removed during
422  * the loop.
423  *
424  * @param first_element first element of loop
425  * @param last_element last element of loop
426  * @param element iterator pointer to tree element struct
427  * @param node_member name of avl_node within tree element struct
428  * @param ptr pointer to tree element struct which is used to store
429  *    the next node during the loop
430  */
431 #define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
432   for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
433        element->node_member.list.prev != &(last_element)->node_member.list; \
434        element = ptr, ptr = avl_next_element(ptr, node_member))
435
436 /**
437  * Loop over a block of elements of a tree backwards, used similar to a for() command.
438  * This loop can be used if the current element might be removed from
439  * the tree during the loop. Other elements should not be removed during
440  * the loop.
441  *
442  * @param first_element first element of range (will be last returned by the loop)
443  * @param last_element last element of range (will be first returned by the loop)
444  * @param element iterator pointer to node element struct
445  * @param node_member name of avl_node within node element struct
446  * @param ptr pointer to node element struct which is used to store
447  *    the previous node during the loop
448  */
449 #define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
450   for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
451        element->node_member.list.next != &(first_element)->node_member.list; \
452        element = ptr, ptr = avl_prev_element(ptr, node_member))
453
454 /**
455  * Loop over all elements of an avl_tree, used similar to a for() command.
456  * This loop can be used if the current element might be removed from
457  * the tree during the loop. Other elements should not be removed during
458  * the loop.
459  *
460  * @param tree pointer to avl-tree
461  * @param element pointer to a node of the tree, this element will
462  *    contain the current node of the tree during the loop
463  * @param node_member name of the avl_node element inside the
464  *    larger struct
465  * @param ptr pointer to a tree element which is used to store
466  *    the next node during the loop
467  */
468 #define avl_for_each_element_safe(tree, element, node_member, ptr) \
469   avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
470                              avl_last_element(tree, element, node_member), \
471                              element, node_member, ptr)
472
473 /**
474  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
475  * This loop can be used if the current element might be removed from
476  * the tree during the loop. Other elements should not be removed during
477  * the loop.
478  *
479  * @param tree pointer to avl-tree
480  * @param element pointer to a node of the tree, this element will
481  *    contain the current node of the tree during the loop
482  * @param node_member name of the avl_node element inside the
483  *    larger struct
484  * @param ptr pointer to a tree element which is used to store
485  *    the next node during the loop
486  */
487 #define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \
488   avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
489                                      avl_last_element(tree, element, node_member), \
490                                      element, node_member, ptr)
491
492 /**
493  * A special loop that removes all elements of the tree and cleans up the tree
494  * root. The loop body is responsible to free the node elements of the tree.
495  *
496  * This loop is much faster than a normal one for clearing the tree because it
497  * does not rebalance the tree after each removal. Do NOT use a break command
498  * inside.
499  * You can free the memory of the elements within the loop.
500  * Do NOT call avl_delete() on the elements within the loop,
501  *
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
506  *    larger struct
507  * @param ptr pointer to a tree element which is used to store
508  *    the next node during the loop
509  */
510 #define avl_remove_all_elements(tree, element, node_member, ptr) \
511   for (element = avl_first_element(tree, element, node_member), \
512        ptr = avl_next_element(element, node_member), \
513        list_init_head(&(tree)->list_head), \
514        (tree)->root = NULL; \
515        (tree)->count > 0; \
516        element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
517
518 #endif /* _AVL_H */
519
520 /*
521  * Local Variables:
522  * c-basic-offset: 2
523  * indent-tabs-mode: nil
524  * End:
525  */