avl.h

   1 /*
   2  * PacketBB handler library (see RFC 5444)
   3  * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
   4  * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  * * Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in
  15  *   the documentation and/or other materials provided with the
  16  *   distribution.
  17  * * Neither the name of olsr.org, olsrd nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Visit http://www.olsr.org/git for more information.
  35  *
  36  * If you find this software useful feel free to make a donation
  37  * to the project. For more information see the website or contact
  38  * the copyright holders.
  39  */
  40
  41 #ifndef _AVL_H
  42 #define _AVL_H
  43
  44 #include <stddef.h>
  45 #include <stdbool.h>
  46
  47 #include "list.h"
  48 #include "list_compat.h"
  49
  50 /* Support for OLSR.org linker symbol export */
  51 #define EXPORT(sym) sym
  52
  53 /**
  54  * This element is a member of a avl-tree. It must be contained in all
  55  * larger structs that should be put into a tree.
  56  */
  57 struct avl_node {
  58   /**
  59    * Linked list node for supporting easy iteration and multiple
  60    * elments with the same key.
  61    *
  62    * this must be the first element of an avl_node to
  63    * make casting for lists easier
  64    */
  65   struct list_entity list;
  66
  67   /**
  68    * Pointer to parent node in tree, NULL if root node
  69    */
  70   struct avl_node *parent;
  71
  72   /**
  73    * Pointer to left child
  74    */
  75   struct avl_node *left;
  76
  77   /**
  78    * Pointer to right child
  79    */
  80   struct avl_node *right;
  81
  82   /**
  83    * pointer to key of node
  84    */
  85   void *key;
  86
  87   /**
  88    * balance state of AVL tree (0,-1,+1)
  89    */
  90   signed char balance;
  91
  92   /**
  93    * true if first of a series of nodes with same key
  94    */
  95   bool leader;
  96 };
  97
  98 /**
  99  * Prototype for avl comparators
 100  * @param k1 first key
 101  * @param k2 second key
 102  * @param ptr custom data for tree comparator
 103  * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
 104  */
 105 typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
 106
 107 /**
 108  * This struct is the central management part of an avl tree.
 109  * One of them is necessary for each avl_tree.
 110  */
 111 struct avl_tree {
 112   /**
 113    * Head of linked list node for supporting easy iteration
 114    * and multiple elments with the same key.
 115    */
 116   struct list_entity list_head;
 117
 118   /**
 119    * pointer to the root node of the avl tree, NULL if tree is empty
 120    */
 121   struct avl_node *root;
 122
 123   /**
 124    * number of nodes in the avl tree
 125    */
 126   unsigned int count;
 127
 128   /**
 129    * true if multiple nodes with the same key are
 130    * allowed in the tree, false otherwise
 131    */
 132   bool allow_dups;
 133
 134   /**
 135    * pointer to the tree comparator
 136    *
 137    * First two parameters are keys to compare,
 138    * third parameter is a copy of cmp_ptr
 139    */
 140   avl_tree_comp comp;
 141
 142   /**
 143    * custom pointer delivered to the tree comparator
 144    */
 145   void *cmp_ptr;
 146 };
 147
 148 /**
 149  * internal enum for avl_find_... macros
 150  */
 151 enum avl_find_mode {
 152   AVL_FIND_EQUAL,
 153   AVL_FIND_LESSEQUAL,
 154   AVL_FIND_GREATEREQUAL
 155 };
 156
 157 void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
 158 struct avl_node *EXPORT(avl_find)(struct avl_tree *, const void *);
 159 struct avl_node *EXPORT(avl_find_greaterequal)(struct avl_tree *tree, const void *key);
 160 struct avl_node *EXPORT(avl_find_lessequal)(struct avl_tree *tree, const void *key);
 161 int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
 162 void EXPORT(avl_delete)(struct avl_tree *, struct avl_node *);
 163 void *EXPORT(__avl_find_element)(struct avl_tree *tree, const void *key,
 164     size_t offset, enum avl_find_mode mode);
 165
 166 /**
 167  * @param tree pointer to avl-tree
 168  * @param node pointer to node of the tree
 169  * @return true if node is the first one of the tree, false otherwise
 170  */
 171 static inline bool
 172 avl_is_first(struct avl_tree *tree, struct avl_node *node) {
 173   return tree->list_head.next == &node->list;
 174 }
 175
 176 /**
 177  * @param tree pointer to avl-tree
 178  * @param node pointer to node of the tree
 179  * @return true if node is the last one of the tree, false otherwise
 180  */
 181 static inline bool
 182 avl_is_last(struct avl_tree *tree, struct avl_node *node) {
 183   return tree->list_head.prev == &node->list;
 184 }
 185
 186 /**
 187  * @param tree pointer to avl-tree
 188  * @return true if the tree is empty, false otherwise
 189  */
 190 static inline bool
 191 avl_is_empty(struct avl_tree *tree) {
 192   return tree->count == 0;
 193 }
 194
 195 /**
 196  * @param tree pointer to avl-tree
 197  * @param key pointer to key
 198  * @param element pointer to a node element
 199  *    (don't need to be initialized)
 200  * @param node_element name of the avl_node element inside the
 201  *    larger struct
 202  * @return pointer to tree element with the specified key,
 203  *    NULL if no element was found
 204  */
 205 #define avl_find_element(tree, key, element, node_element) \
 206   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
 207
 208 /**
 209  * @param tree pointer to avl-tree
 210  * @param key pointer to specified key
 211  * @param element pointer to a node element
 212  *    (don't need to be initialized)
 213  * @param node_element name of the avl_node element inside the
 214  *    larger struct
 215  * return pointer to last tree element with less or equal key than specified key,
 216  *    NULL if no element was found
 217  */
 218 #define avl_find_le_element(tree, key, element, node_element) \
 219   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
 220
 221 /**
 222  * @param tree pointer to avl-tree
 223  * @param key pointer to specified key
 224  * @param element pointer to a node element
 225  *    (don't need to be initialized)
 226  * @param node_element name of the avl_node element inside the
 227  *    larger struct
 228  * return pointer to first tree element with greater or equal key than specified key,
 229  *    NULL if no element was found
 230  */
 231 #define avl_find_ge_element(tree, key, element, node_element) \
 232   ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
 233
 234 /**
 235  * This function must not be called for an empty tree
 236  *
 237  * @param tree pointer to avl-tree
 238  * @param element pointer to a node element
 239  *    (don't need to be initialized)
 240  * @param node_member name of the avl_node element inside the
 241  *    larger struct
 242  * @return pointer to the first element of the avl_tree
 243  *    (automatically converted to type 'element')
 244  */
 245 #define avl_first_element(tree, element, node_member) \
 246   container_of((tree)->list_head.next, typeof(*(element)), node_member)
 247
 248 /**
 249  * @param tree pointer to tree
 250  * @param element pointer to a node struct that contains the avl_node
 251  *    (don't need to be initialized)
 252  * @param node_member name of the avl_node element inside the
 253  *    larger struct
 254  * @return pointer to the last element of the avl_tree
 255  *    (automatically converted to type 'element')
 256  */
 257 #define avl_last_element(tree, element, node_member) \
 258   container_of((tree)->list_head.prev, typeof(*(element)), node_member)
 259
 260 /**
 261  * This function must not be called for the last element of
 262  * an avl tree
 263  *
 264  * @param element pointer to a node of the tree
 265  * @param node_member name of the avl_node element inside the
 266  *    larger struct
 267  * @return pointer to the node after 'element'
 268  *    (automatically converted to type 'element')
 269  */
 270 #define avl_next_element(element, node_member) \
 271   container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
 272
 273 /**
 274  * This function must not be called for the first element of
 275  * an avl tree
 276  *
 277  * @param element pointer to a node of the tree
 278  * @param node_member name of the avl_node element inside the
 279  *    larger struct
 280  * @return pointer to the node before 'element'
 281  *    (automatically converted to type 'element')
 282  */
 283 #define avl_prev_element(element, node_member) \
 284   container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
 285
 286 /**
 287  * Loop over a block of elements of a tree, used similar to a for() command.
 288  * This loop should not be used if elements are removed from the tree during
 289  * the loop.
 290  *
 291  * @param first pointer to first element of loop
 292  * @param last pointer to last element of loop
 293  * @param element pointer to a node of the tree, this element will
 294  *    contain the current node of the list during the loop
 295  * @param node_member name of the avl_node element inside the
 296  *    larger struct
 297  */
 298 #define avl_for_element_range(first, last, element, node_member) \
 299   for (element = (first); \
 300        element->node_member.list.prev != &(last)->node_member.list; \
 301        element = avl_next_element(element, node_member))
 302
 303 /**
 304  * Loop over a block of elements of a tree backwards, used similar to a for() command.
 305  * This loop should not be used if elements are removed from the tree during
 306  * the loop.
 307  *
 308  * @param first pointer to first element of loop
 309  * @param last pointer to last element of loop
 310  * @param element pointer to a node of the tree, this element will
 311  *    contain the current node of the list during the loop
 312  * @param node_member name of the avl_node element inside the
 313  *    larger struct
 314  */
 315 #define avl_for_element_range_reverse(first, last, element, node_member) \
 316   for (element = (last); \
 317        element->node_member.list.next != &(first)->node_member.list; \
 318        element = avl_prev_element(element, node_member))
 319
 320 /**
 321  * Loop over all elements of an avl_tree, used similar to a for() command.
 322  * This loop should not be used if elements are removed from the tree during
 323  * the loop.
 324  *
 325  * @param tree pointer to avl-tree
 326  * @param element pointer to a node of the tree, this element will
 327  *    contain the current node of the tree during the loop
 328  * @param node_member name of the avl_node element inside the
 329  *    larger struct
 330  */
 331 #define avl_for_each_element(tree, element, node_member) \
 332   avl_for_element_range(avl_first_element(tree, element, node_member), \
 333                         avl_last_element(tree, element,  node_member), \
 334                         element, node_member)
 335
 336 /**
 337  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
 338  * This loop should not be used if elements are removed from the tree during
 339  * the loop.
 340  *
 341  * @param tree pointer to avl-tree
 342  * @param element pointer to a node of the tree, this element will
 343  *    contain the current node of the tree during the loop
 344  * @param node_member name of the avl_node element inside the
 345  *    larger struct
 346  */
 347 #define avl_for_each_element_reverse(tree, element, node_member) \
 348   avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
 349                                 avl_last_element(tree, element,  node_member), \
 350                                 element, node_member)
 351
 352 /**
 353  * Loop over a block of elements of a tree, used similar to a for() command.
 354  * This loop should not be used if elements are removed from the tree during
 355  * the loop.
 356  * The loop runs from the element 'first' to the end of the tree.
 357  *
 358  * @param tree pointer to avl-tree
 359  * @param first pointer to first element of loop
 360  * @param element pointer to a node of the tree, this element will
 361  *    contain the current node of the list during the loop
 362  * @param node_member name of the avl_node element inside the
 363  *    larger struct
 364  */
 365 #define avl_for_element_to_last(tree, first, element, node_member) \
 366   avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
 367
 368
 369 /**
 370  * Loop over a block of elements of a tree backwards, used similar to a for() command.
 371  * This loop should not be used if elements are removed from the tree during
 372  * the loop.
 373  * The loop runs from the element 'first' to the end of the tree.
 374  *
 375  * @param tree pointer to avl-tree
 376  * @param first pointer to first element of loop
 377  * @param element pointer to a node of the tree, this element will
 378  *    contain the current node of the list during the loop
 379  * @param node_member name of the avl_node element inside the
 380  *    larger struct
 381  */
 382 #define avl_for_element_to_last_reverse(tree, first, element, node_member) \
 383   avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
 384
 385 /**
 386  * Loop over a block of elements of a tree, used similar to a for() command.
 387  * This loop should not be used if elements are removed from the tree during
 388  * the loop.
 389  * The loop runs from the start of the tree to the element 'last'.
 390  *
 391  * @param tree pointer to avl-tree
 392  * @param last pointer to last element of loop
 393  * @param element pointer to a node of the tree, this element will
 394  *    contain the current node of the list during the loop
 395  * @param node_member name of the avl_node element inside the
 396  *    larger struct
 397  */
 398 #define avl_for_first_to_element(tree, last, element, node_member) \
 399   avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
 400
 401
 402 /**
 403  * Loop over a block of elements of a tree backwards, used similar to a for() command.
 404  * This loop should not be used if elements are removed from the tree during
 405  * the loop.
 406  * The loop runs from the start of the tree to the element 'last'.
 407  *
 408  * @param tree pointer to avl-tree
 409  * @param last pointer to last element of loop
 410  * @param element pointer to a node of the tree, this element will
 411  *    contain the current node of the list during the loop
 412  * @param node_member name of the avl_node element inside the
 413  *    larger struct
 414  */
 415 #define avl_for_first_to_element_reverse(tree, last, element, node_member) \
 416   avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
 417
 418 /**
 419  * Loop over a block of nodes of a tree, used similar to a for() command.
 420  * This loop can be used if the current element might be removed from
 421  * the tree during the loop. Other elements should not be removed during
 422  * the loop.
 423  *
 424  * @param first_element first element of loop
 425  * @param last_element last element of loop
 426  * @param element iterator pointer to tree element struct
 427  * @param node_member name of avl_node within tree element struct
 428  * @param ptr pointer to tree element struct which is used to store
 429  *    the next node during the loop
 430  */
 431 #define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
 432   for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
 433        element->node_member.list.prev != &(last_element)->node_member.list; \
 434        element = ptr, ptr = avl_next_element(ptr, node_member))
 435
 436 /**
 437  * Loop over a block of elements of a tree backwards, used similar to a for() command.
 438  * This loop can be used if the current element might be removed from
 439  * the tree during the loop. Other elements should not be removed during
 440  * the loop.
 441  *
 442  * @param first_element first element of range (will be last returned by the loop)
 443  * @param last_element last element of range (will be first returned by the loop)
 444  * @param element iterator pointer to node element struct
 445  * @param node_member name of avl_node within node element struct
 446  * @param ptr pointer to node element struct which is used to store
 447  *    the previous node during the loop
 448  */
 449 #define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
 450   for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
 451        element->node_member.list.next != &(first_element)->node_member.list; \
 452        element = ptr, ptr = avl_prev_element(ptr, node_member))
 453
 454 /**
 455  * Loop over all elements of an avl_tree, used similar to a for() command.
 456  * This loop can be used if the current element might be removed from
 457  * the tree during the loop. Other elements should not be removed during
 458  * the loop.
 459  *
 460  * @param tree pointer to avl-tree
 461  * @param element pointer to a node of the tree, this element will
 462  *    contain the current node of the tree during the loop
 463  * @param node_member name of the avl_node element inside the
 464  *    larger struct
 465  * @param ptr pointer to a tree element which is used to store
 466  *    the next node during the loop
 467  */
 468 #define avl_for_each_element_safe(tree, element, node_member, ptr) \
 469   avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
 470                              avl_last_element(tree, element, node_member), \
 471                              element, node_member, ptr)
 472
 473 /**
 474  * Loop over all elements of an avl_tree backwards, used similar to a for() command.
 475  * This loop can be used if the current element might be removed from
 476  * the tree during the loop. Other elements should not be removed during
 477  * the loop.
 478  *
 479  * @param tree pointer to avl-tree
 480  * @param element pointer to a node of the tree, this element will
 481  *    contain the current node of the tree during the loop
 482  * @param node_member name of the avl_node element inside the
 483  *    larger struct
 484  * @param ptr pointer to a tree element which is used to store
 485  *    the next node during the loop
 486  */
 487 #define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \
 488   avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
 489                                      avl_last_element(tree, element, node_member), \
 490                                      element, node_member, ptr)
 491
 492 /**
 493  * A special loop that removes all elements of the tree and cleans up the tree
 494  * root. The loop body is responsible to free the node elements of the tree.
 495  *
 496  * This loop is much faster than a normal one for clearing the tree because it
 497  * does not rebalance the tree after each removal. Do NOT use a break command
 498  * inside.
 499  * You can free the memory of the elements within the loop.
 500  * Do NOT call avl_delete() on the elements within the loop,
 501  *
 502  * @param tree pointer to avl-tree
 503  * @param element pointer to a node of the tree, this element will
 504  *    contain the current node of the tree during the loop
 505  * @param node_member name of the avl_node element inside the
 506  *    larger struct
 507  * @param ptr pointer to a tree element which is used to store
 508  *    the next node during the loop
 509  */
 510 #define avl_remove_all_elements(tree, element, node_member, ptr) \
 511   for (element = avl_first_element(tree, element, node_member), \
 512        ptr = avl_next_element(element, node_member), \
 513        list_init_head(&(tree)->list_head), \
 514        (tree)->root = NULL; \
 515        (tree)->count > 0; \
 516        element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
 517
 518 #endif /* _AVL_H */
 519
 520 /*
 521  * Local Variables:
 522  * c-basic-offset: 2
 523  * indent-tabs-mode: nil
 524  * End:
 525  */