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