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