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