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