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 #include <stdbool.h> 42 #include <stddef.h> 43 #include <stdint.h> 44 #include <time.h> 45 #include <string.h> 46 47 #include "avl.h" 48 #include "assert.h" 49 #include "list.h" 50 51 /** 52 * internal type save inline function to calculate the maximum of 53 * to integers without macro implementation. 54 * 55 * @param x first parameter of maximum function 56 * @param y second parameter of maximum function 57 * @return largest integer of both parameters 58 */ 59 static inline int avl_max(int x, int y) { 60 return x > y ? x : y; 61 } 62 63 /** 64 * internal type save inline function to calculate the minimum of 65 * to integers without macro implementation. 66 * 67 * @param x first parameter of minimum function 68 * @param y second parameter of minimum function 69 * @return smallest integer of both parameters 70 */ 71 static inline int avl_min(int x, int y) { 72 return x < y ? x : y; 73 } 74 75 static struct avl_node * 76 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result); 77 static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node); 78 static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node); 79 static void post_insert(struct avl_tree *tree, struct avl_node *node); 80 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node); 81 static void avl_remove(struct avl_tree *tree, struct avl_node *node); 82 83 /** 84 * Initialize a new avl_tree struct 85 * @param tree pointer to avl-tree 86 * @param comp pointer to comparator for the tree 87 * @param allow_dups true if the tree allows multiple 88 * elements with the same 89 * @param ptr custom parameter for comparator 90 */ 91 void 92 avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr) 93 { 94 INIT_LIST_HEAD(&tree->list_head); 95 tree->root = NULL; 96 tree->count = 0; 97 tree->comp = comp; 98 tree->allow_dups = allow_dups; 99 tree->cmp_ptr = ptr; 100 } 101 102 static inline struct avl_node *avl_next(struct avl_node *node) 103 { 104 return list_entry(node->list.next, struct avl_node, list); 105 } 106 107 /** 108 * Finds a node in an avl-tree with a certain key 109 * @param tree pointer to avl-tree 110 * @param key pointer to key 111 * @return pointer to avl-node with key, NULL if no node with 112 * this key exists. 113 */ 114 struct avl_node * 115 avl_find(const struct avl_tree *tree, const void *key) 116 { 117 struct avl_node *node; 118 int diff; 119 120 if (tree->root == NULL) 121 return NULL; 122 123 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff); 124 125 return diff == 0 ? node : NULL; 126 } 127 128 /** 129 * Finds the last node in an avl-tree with a key less or equal 130 * than the specified key 131 * @param tree pointer to avl-tree 132 * @param key pointer to specified key 133 * @return pointer to avl-node, NULL if no node with 134 * key less or equal specified key exists. 135 */ 136 struct avl_node * 137 avl_find_lessequal(const struct avl_tree *tree, const void *key) { 138 struct avl_node *node, *next; 139 int diff; 140 141 if (tree->root == NULL) 142 return NULL; 143 144 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff); 145 146 /* go left as long as key<node.key */ 147 while (diff < 0) { 148 if (list_is_first(&node->list, &tree->list_head)) { 149 return NULL; 150 } 151 152 node = (struct avl_node *)node->list.prev; 153 diff = (*tree->comp) (key, node->key, tree->cmp_ptr); 154 } 155 156 /* go right as long as key>=next_node.key */ 157 next = node; 158 while (diff >= 0) { 159 node = next; 160 if (list_is_last(&node->list, &tree->list_head)) { 161 break; 162 } 163 164 next = (struct avl_node *)node->list.next; 165 diff = (*tree->comp) (key, next->key, tree->cmp_ptr); 166 } 167 return node; 168 } 169 170 /** 171 * Finds the first node in an avl-tree with a key greater or equal 172 * than the specified key 173 * @param tree pointer to avl-tree 174 * @param key pointer to specified key 175 * @return pointer to avl-node, NULL if no node with 176 * key greater or equal specified key exists. 177 */ 178 struct avl_node * 179 avl_find_greaterequal(const struct avl_tree *tree, const void *key) { 180 struct avl_node *node, *next; 181 int diff; 182 183 if (tree->root == NULL) 184 return NULL; 185 186 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff); 187 188 /* go right as long as key>node.key */ 189 while (diff > 0) { 190 if (list_is_last(&node->list, &tree->list_head)) { 191 return NULL; 192 } 193 194 node = (struct avl_node *)node->list.next; 195 diff = (*tree->comp) (key, node->key, tree->cmp_ptr); 196 } 197 198 /* go left as long as key<=next_node.key */ 199 next = node; 200 while (diff <= 0) { 201 node = next; 202 if (list_is_first(&node->list, &tree->list_head)) { 203 break; 204 } 205 206 next = (struct avl_node *)node->list.prev; 207 diff = (*tree->comp) (key, next->key, tree->cmp_ptr); 208 } 209 return node; 210 } 211 212 /** 213 * Inserts an avl_node into a tree 214 * @param tree pointer to tree 215 * @param new pointer to node 216 * @return 0 if node was inserted successfully, -1 if it was not inserted 217 * because of a key collision 218 */ 219 int 220 avl_insert(struct avl_tree *tree, struct avl_node *new) 221 { 222 struct avl_node *node, *next, *last; 223 int diff; 224 225 new->parent = NULL; 226 227 new->left = NULL; 228 new->right = NULL; 229 230 new->balance = 0; 231 new->leader = true; 232 233 if (tree->root == NULL) { 234 list_add(&new->list, &tree->list_head); 235 tree->root = new; 236 tree->count = 1; 237 return 0; 238 } 239 240 node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff); 241 242 last = node; 243 244 while (!list_is_last(&last->list, &tree->list_head)) { 245 next = avl_next(last); 246 if (next->leader) { 247 break; 248 } 249 last = next; 250 } 251 252 diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr); 253 254 if (diff == 0) { 255 if (!tree->allow_dups) 256 return -1; 257 258 new->leader = 0; 259 260 avl_insert_after(tree, last, new); 261 return 0; 262 } 263 264 if (node->balance == 1) { 265 avl_insert_before(tree, node, new); 266 267 node->balance = 0; 268 new->parent = node; 269 node->left = new; 270 return 0; 271 } 272 273 if (node->balance == -1) { 274 avl_insert_after(tree, last, new); 275 276 node->balance = 0; 277 new->parent = node; 278 node->right = new; 279 return 0; 280 } 281 282 if (diff < 0) { 283 avl_insert_before(tree, node, new); 284 285 node->balance = -1; 286 new->parent = node; 287 node->left = new; 288 post_insert(tree, node); 289 return 0; 290 } 291 292 avl_insert_after(tree, last, new); 293 294 node->balance = 1; 295 new->parent = node; 296 node->right = new; 297 post_insert(tree, node); 298 return 0; 299 } 300 301 /** 302 * Remove a node from an avl tree 303 * @param tree pointer to tree 304 * @param node pointer to node 305 */ 306 void 307 avl_delete(struct avl_tree *tree, struct avl_node *node) 308 { 309 struct avl_node *next; 310 struct avl_node *parent; 311 struct avl_node *left; 312 struct avl_node *right; 313 if (node->leader) { 314 if (tree->allow_dups 315 && !list_is_last(&node->list, &tree->list_head) 316 && !(next = avl_next(node))->leader) { 317 next->leader = true; 318 next->balance = node->balance; 319 320 parent = node->parent; 321 left = node->left; 322 right = node->right; 323 324 next->parent = parent; 325 next->left = left; 326 next->right = right; 327 328 if (parent == NULL) 329 tree->root = next; 330 331 else { 332 if (node == parent->left) 333 parent->left = next; 334 335 else 336 parent->right = next; 337 } 338 339 if (left != NULL) 340 left->parent = next; 341 342 if (right != NULL) 343 right->parent = next; 344 } 345 346 else 347 avl_delete_worker(tree, node); 348 } 349 350 avl_remove(tree, node); 351 } 352 353 static struct avl_node * 354 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result) 355 { 356 int diff; 357 358 diff = (*comp) (key, node->key, cmp_ptr); 359 *cmp_result = diff; 360 361 if (diff < 0) { 362 if (node->left != NULL) 363 return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result); 364 365 return node; 366 } 367 368 if (diff > 0) { 369 if (node->right != NULL) 370 return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result); 371 372 return node; 373 } 374 375 return node; 376 } 377 378 static void 379 avl_rotate_right(struct avl_tree *tree, struct avl_node *node) 380 { 381 struct avl_node *left, *parent; 382 383 left = node->left; 384 parent = node->parent; 385 386 left->parent = parent; 387 node->parent = left; 388 389 if (parent == NULL) 390 tree->root = left; 391 392 else { 393 if (parent->left == node) 394 parent->left = left; 395 396 else 397 parent->right = left; 398 } 399 400 node->left = left->right; 401 left->right = node; 402 403 if (node->left != NULL) 404 node->left->parent = node; 405 406 node->balance += 1 - avl_min(left->balance, 0); 407 left->balance += 1 + avl_max(node->balance, 0); 408 } 409 410 static void 411 avl_rotate_left(struct avl_tree *tree, struct avl_node *node) 412 { 413 struct avl_node *right, *parent; 414 415 right = node->right; 416 parent = node->parent; 417 418 right->parent = parent; 419 node->parent = right; 420 421 if (parent == NULL) 422 tree->root = right; 423 424 else { 425 if (parent->left == node) 426 parent->left = right; 427 428 else 429 parent->right = right; 430 } 431 432 node->right = right->left; 433 right->left = node; 434 435 if (node->right != NULL) 436 node->right->parent = node; 437 438 node->balance -= 1 + avl_max(right->balance, 0); 439 right->balance -= 1 - avl_min(node->balance, 0); 440 } 441 442 static void 443 post_insert(struct avl_tree *tree, struct avl_node *node) 444 { 445 struct avl_node *parent = node->parent; 446 447 if (parent == NULL) 448 return; 449 450 if (node == parent->left) { 451 parent->balance--; 452 453 if (parent->balance == 0) 454 return; 455 456 if (parent->balance == -1) { 457 post_insert(tree, parent); 458 return; 459 } 460 461 if (node->balance == -1) { 462 avl_rotate_right(tree, parent); 463 return; 464 } 465 466 avl_rotate_left(tree, node); 467 avl_rotate_right(tree, node->parent->parent); 468 return; 469 } 470 471 parent->balance++; 472 473 if (parent->balance == 0) 474 return; 475 476 if (parent->balance == 1) { 477 post_insert(tree, parent); 478 return; 479 } 480 481 if (node->balance == 1) { 482 avl_rotate_left(tree, parent); 483 return; 484 } 485 486 avl_rotate_right(tree, node); 487 avl_rotate_left(tree, node->parent->parent); 488 } 489 490 static void 491 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node) 492 { 493 list_add_tail(&node->list, &pos_node->list); 494 tree->count++; 495 } 496 497 static void 498 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node) 499 { 500 list_add(&node->list, &pos_node->list); 501 tree->count++; 502 } 503 504 static void 505 avl_remove(struct avl_tree *tree, struct avl_node *node) 506 { 507 list_del(&node->list); 508 tree->count--; 509 } 510 511 static void 512 avl_post_delete(struct avl_tree *tree, struct avl_node *node) 513 { 514 struct avl_node *parent; 515 516 if ((parent = node->parent) == NULL) 517 return; 518 519 if (node == parent->left) { 520 parent->balance++; 521 522 if (parent->balance == 0) { 523 avl_post_delete(tree, parent); 524 return; 525 } 526 527 if (parent->balance == 1) 528 return; 529 530 if (parent->right->balance == 0) { 531 avl_rotate_left(tree, parent); 532 return; 533 } 534 535 if (parent->right->balance == 1) { 536 avl_rotate_left(tree, parent); 537 avl_post_delete(tree, parent->parent); 538 return; 539 } 540 541 avl_rotate_right(tree, parent->right); 542 avl_rotate_left(tree, parent); 543 avl_post_delete(tree, parent->parent); 544 return; 545 } 546 547 parent->balance--; 548 549 if (parent->balance == 0) { 550 avl_post_delete(tree, parent); 551 return; 552 } 553 554 if (parent->balance == -1) 555 return; 556 557 if (parent->left->balance == 0) { 558 avl_rotate_right(tree, parent); 559 return; 560 } 561 562 if (parent->left->balance == -1) { 563 avl_rotate_right(tree, parent); 564 avl_post_delete(tree, parent->parent); 565 return; 566 } 567 568 avl_rotate_left(tree, parent->left); 569 avl_rotate_right(tree, parent); 570 avl_post_delete(tree, parent->parent); 571 } 572 573 static struct avl_node * 574 avl_local_min(struct avl_node *node) 575 { 576 while (node->left != NULL) 577 node = node->left; 578 579 return node; 580 } 581 582 #if 0 583 static struct avl_node * 584 avl_local_max(struct avl_node *node) 585 { 586 while (node->right != NULL) 587 node = node->right; 588 589 return node; 590 } 591 #endif 592 593 static void 594 avl_delete_worker(struct avl_tree *tree, struct avl_node *node) 595 { 596 struct avl_node *parent, *min; 597 598 parent = node->parent; 599 600 if (node->left == NULL && node->right == NULL) { 601 if (parent == NULL) { 602 tree->root = NULL; 603 return; 604 } 605 606 if (parent->left == node) { 607 parent->left = NULL; 608 parent->balance++; 609 610 if (parent->balance == 1) 611 return; 612 613 if (parent->balance == 0) { 614 avl_post_delete(tree, parent); 615 return; 616 } 617 618 if (parent->right->balance == 0) { 619 avl_rotate_left(tree, parent); 620 return; 621 } 622 623 if (parent->right->balance == 1) { 624 avl_rotate_left(tree, parent); 625 avl_post_delete(tree, parent->parent); 626 return; 627 } 628 629 avl_rotate_right(tree, parent->right); 630 avl_rotate_left(tree, parent); 631 avl_post_delete(tree, parent->parent); 632 return; 633 } 634 635 if (parent->right == node) { 636 parent->right = NULL; 637 parent->balance--; 638 639 if (parent->balance == -1) 640 return; 641 642 if (parent->balance == 0) { 643 avl_post_delete(tree, parent); 644 return; 645 } 646 647 if (parent->left->balance == 0) { 648 avl_rotate_right(tree, parent); 649 return; 650 } 651 652 if (parent->left->balance == -1) { 653 avl_rotate_right(tree, parent); 654 avl_post_delete(tree, parent->parent); 655 return; 656 } 657 658 avl_rotate_left(tree, parent->left); 659 avl_rotate_right(tree, parent); 660 avl_post_delete(tree, parent->parent); 661 return; 662 } 663 } 664 665 if (node->left == NULL) { 666 if (parent == NULL) { 667 tree->root = node->right; 668 node->right->parent = NULL; 669 return; 670 } 671 672 assert(node->right); 673 node->right->parent = parent; 674 675 if (parent->left == node) 676 parent->left = node->right; 677 678 else 679 parent->right = node->right; 680 681 avl_post_delete(tree, node->right); 682 return; 683 } 684 685 if (node->right == NULL) { 686 if (parent == NULL) { 687 tree->root = node->left; 688 node->left->parent = NULL; 689 return; 690 } 691 692 node->left->parent = parent; 693 694 if (parent->left == node) 695 parent->left = node->left; 696 697 else 698 parent->right = node->left; 699 700 avl_post_delete(tree, node->left); 701 return; 702 } 703 704 min = avl_local_min(node->right); 705 avl_delete_worker(tree, min); 706 parent = node->parent; 707 708 min->balance = node->balance; 709 min->parent = parent; 710 min->left = node->left; 711 min->right = node->right; 712 713 if (min->left != NULL) 714 min->left->parent = min; 715 716 if (min->right != NULL) 717 min->right->parent = min; 718 719 if (parent == NULL) { 720 tree->root = min; 721 return; 722 } 723 724 if (parent->left == node) { 725 parent->left = min; 726 return; 727 } 728 729 parent->right = min; 730 } 731 732 /* 733 * Local Variables: 734 * c-basic-offset: 2 735 * indent-tabs-mode: nil 736 * End: 737 */ 738
This page was automatically generated by LXR 0.3.1. • OpenWrt