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 #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
 168 void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
 169 struct avl_node *EXPORT(avl_find)(const struct avl_tree *, const void *);
 170 struct avl_node *EXPORT(avl_find_greaterequal)(const struct avl_tree *tree, const void *key);
 171 struct avl_node *EXPORT(avl_find_lessequal)(const struct avl_tree *tree, const void *key);
 172 int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
 173 void 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  */
 180 static inline bool
 181 avl_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  */
 190 static inline bool
 191 avl_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  */
 199 static inline bool
 200 avl_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  */
 212 static 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  */