38168b6898b03adf2449070150c51c28dc199d17
[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 all elements of an avl_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 tree pointer to avl-tree
292  * @param element pointer to a node of the tree, this element will
293  *    contain the current node of the tree during the loop
294  * @param node_member name of the avl_node element inside the
295  *    larger struct
296  * @param loop_ptr pointer to an list_entity which is used as
297  *    the internal iterator
298  */
299 #define avl_for_each_element(tree, element, node_member, loop_ptr) \
300   list_for_each_element(&(tree)->list_head, element, node_member, loop_ptr)
301
302 /**
303  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
304  * This loop should not be used if elements are removed from the tree during
305  * the loop.
306  *
307  * @param tree pointer to avl-tree
308  * @param element pointer to a node of the tree, this element will
309  *    contain the current node of the tree during the loop
310  * @param node_member name of the avl_node element inside the
311  *    larger struct
312  * @param loop_ptr pointer to an list_entity which is used as
313  *    the internal iterator
314  */
315 #define avl_for_each_element_reverse(tree, element, node_member, loop_ptr) \
316   list_for_each_element_reverse(&(tree)->list_head, element, node_member, loop_ptr)
317
318 /**
319  * Loop over a block of elements of a tree, used similar to a for() command.
320  * This loop should not be used if elements are removed from the tree during
321  * the loop.
322  *
323  * @param first pointer to first element of loop
324  * @param last pointer to last element of loop
325  * @param element pointer to a node of the tree, this element will
326  *    contain the current node of the list during the loop
327  * @param node_member name of the avl_node element inside the
328  *    larger struct
329  * @param loop_ptr pointer to an list_entity which is used as the
330  *    internal iterator
331  */
332 #define avl_for_element_range(first, last, element, node_member, loop_ptr) \
333   __list_for_element_range(&(first)->node_member.list, &(last)->node_member.list, element, node_member, loop_ptr)
334
335 /**
336  * Loop over a block of elements of a tree backwards, used similar to a for() command.
337  * This loop should not be used if elements are removed from the tree during
338  * the loop.
339  *
340  * @param first pointer to first element of loop
341  * @param last pointer to last element of loop
342  * @param element pointer to a node of the tree, this element will
343  *    contain the current node of the list during the loop
344  * @param node_member name of the avl_node element inside the
345  *    larger struct
346  * @param loop_ptr pointer to an list_entity which is used as the
347  *    internal iterator
348  */
349 #define avl_for_element_range_reverse(first, last, element, node_member, loop_ptr) \
350   __list_for_element_range_reverse(&(first)->node_member.list, &(last)->node_member.list, element, node_member, loop_ptr)
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  * @param loop_ptr pointer to an list_entity which is used as the
365  *    internal iterator
366  */
367 #define avl_for_element_to_last(tree, first, element, node_member, loop_ptr) \
368   __list_for_element_range(&(first)->node_member.list, (tree)->list_head.prev, element, node_member, loop_ptr)
369
370 /**
371  * Loop over a block of elements of a tree backwards, used similar to a for() command.
372  * This loop should not be used if elements are removed from the tree during
373  * the loop.
374  * The loop runs from the element 'first' to the end of the tree.
375  *
376  * @param tree pointer to avl-tree
377  * @param first pointer to first element of loop
378  * @param element pointer to a node of the tree, this element will
379  *    contain the current node of the list during the loop
380  * @param node_member name of the avl_node element inside the
381  *    larger struct
382  * @param loop_ptr pointer to an list_entity which is used as the
383  *    internal iterator
384  */
385 #define avl_for_element_to_last_reverse(tree, first, element, node_member, loop_ptr) \
386   __list_for_element_range_reverse(&(first)->node_member.list, (tree)->list_head.prev, element, node_member, loop_ptr)
387
388 /**
389  * Loop over a block of elements of a tree, used similar to a for() command.
390  * This loop should not be used if elements are removed from the tree during
391  * the loop.
392  * The loop runs from the start of the tree to the element 'last'.
393  *
394  * @param tree pointer to avl-tree
395  * @param last pointer to last element of loop
396  * @param element pointer to a node of the tree, this element will
397  *    contain the current node of the list during the loop
398  * @param node_member name of the avl_node element inside the
399  *    larger struct
400  * @param loop_ptr pointer to an list_entity which is used as the
401  *    internal iterator
402  */
403 #define avl_for_first_to_element(tree, last, element, node_member, loop_ptr) \
404     __list_for_element_range((tree)->list_head.next, &(last)->node_member.list, element, node_member, loop_ptr)
405
406 /**
407  * Loop over a block of elements of a tree backwards, used similar to a for() command.
408  * This loop should not be used if elements are removed from the tree during
409  * the loop.
410  * The loop runs from the start of the tree to the element 'last'.
411  *
412  * @param tree pointer to avl-tree
413  * @param last pointer to last element of loop
414  * @param element pointer to a node of the tree, this element will
415  *    contain the current node of the list during the loop
416  * @param node_member name of the avl_node element inside the
417  *    larger struct
418  * @param loop_ptr pointer to an list_entity which is used as the
419  *    internal iterator
420  */
421 #define avl_for_first_to_element_reverse(tree, last, element, node_member, loop_ptr) \
422     __list_for_element_range_reverse((tree)->list_head.next, &(last)->node_member.list, element, node_member, loop_ptr)
423
424 /**
425  * Loop over all elements of an avl_tree, used similar to a for() command.
426  * This loop can be used if the current element might be removed from
427  * the tree during the loop. Other elements should not be removed during
428  * the loop.
429  *
430  * @param tree pointer to avl-tree
431  * @param element pointer to a node of the tree, this element will
432  *    contain the current node of the tree during the loop
433  * @param node_member name of the avl_node element inside the
434  *    larger struct
435  * @param loop_ptr pointer to an list_entity which is used as the
436  *    internal iterator for the loop
437  * @param safe_ptr pointer to an list_entity which is used to store
438  *    the next node during the loop
439  */
440 #define avl_for_each_element_safe(tree, element, node_member, loop_ptr, safe_ptr) \
441   list_for_each_element_safe(&(tree)->list_head, element, node_member, loop_ptr, safe_ptr)
442
443 /**
444  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
445  * This loop can be used if the current element might be removed from
446  * the tree during the loop. Other elements should not be removed during
447  * the loop.
448  *
449  * @param tree pointer to avl-tree
450  * @param element pointer to a node of the tree, this element will
451  *    contain the current node of the tree during the loop
452  * @param node_member name of the avl_node element inside the
453  *    larger struct
454  * @param loop_ptr pointer to an list_entity which is used as the
455  *    internal iterator for the loop
456  * @param safe_ptr pointer to an list_entity which is used to store
457  *    the next node during the loop
458  */
459 #define avl_for_each_element_reverse_safe(tree, element, node_member, loop_ptr, safe_ptr) \
460   list_for_each_element_reverse_safe(&(tree)->list_head, element, node_member, loop_ptr, safe_ptr)
461
462 /**
463  * A special loop that removes all elements of the tree and cleans up the tree
464  * root. The loop body is responsible to free the node elements of the tree.
465  *
466  * This loop is much faster than a normal one for clearing the tree because it
467  * does not rebalance the tree after each removal. Do NOT use a break command
468  * inside.
469  * You can free the memory of the elements within the loop.
470  * Do NOT call avl_delete() on the elements within the loop,
471  *
472  * @param tree pointer to avl-tree
473  * @param element pointer to a node of the tree, this element will
474  *    contain the current node of the tree during the loop
475  * @param node_member name of the avl_node element inside the
476  *    larger struct
477  * @param loop_ptr pointer to an list_entity which is used as the
478  *    internal iterator for the loop
479  * @param safe_ptr pointer to an list_entity which is used to store
480  *    the next node during the loop
481  */
482 #define avl_remove_all_elements(tree, element, node_member, loop_ptr, safe_ptr) \
483   for (loop_ptr = (tree)->list_head.next, safe_ptr = loop_ptr->next, \
484          element = container_of(loop_ptr, typeof(*(element)), node_member), \
485          list_init_head(&(tree)->list_head), \
486          (tree)->root = NULL, (tree)->count = 0; \
487        loop_ptr != &(tree)->list_head; \
488        loop_ptr = safe_ptr, safe_ptr = loop_ptr->next, \
489          element = container_of(loop_ptr, typeof(*(element)), node_member))
490
491 #endif /* _AVL_H */
492
493 /*
494  * Local Variables:
495  * c-basic-offset: 2
496  * indent-tabs-mode: nil
497  * End:
498  */