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