merge an avl list implementation (imported from PacketBB)
[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 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 */