avl.c

   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  */