source: trunk/debian/packages/libubox/trunk/avl.h @ 857

Last change on this file since 857 was 857, checked in by amain, 4 years ago

libubox: initial import / part 4

File size: 20.1 KB
Line 
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 */
56struct 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 */
104typedef 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 */
110struct 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 */
150enum 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
168void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
169struct avl_node *EXPORT(avl_find)(const struct avl_tree *, const void *);
170struct avl_node *EXPORT(avl_find_greaterequal)(const struct avl_tree *tree, const void *key);
171struct avl_node *EXPORT(avl_find_lessequal)(const struct avl_tree *tree, const void *key);
172int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
173void 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 */
180static inline bool
181avl_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 */
190static inline bool
191avl_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 */
199static inline bool
200avl_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 */
212static 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 */
Note: See TracBrowser for help on using the repository browser.