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