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 */ 561
This page was automatically generated by LXR 0.3.1. • OpenWrt