src/common/avl.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
   5  * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * * Redistributions of source code must retain the above copyright
  13  *   notice, this list of conditions and the following disclaimer.
  14  * * Redistributions in binary form must reproduce the above copyright
  15  *   notice, this list of conditions and the following disclaimer in
  16  *   the documentation and/or other materials provided with the
  17  *   distribution.
  18  * * Neither the name of olsr.org, olsrd nor the names of its
  19  *   contributors may be used to endorse or promote products derived
  20  *   from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  *
  35  * Visit http://www.olsr.org for more information.
  36  *
  37  * If you find this software useful feel free to make a donation
  38  * to the project. For more information see the website or contact
  39  * the copyright holders.
  40  *
  41  */
  42
  43 #include <stddef.h>
  44 #include <time.h>
  45 #include <string.h>
  46
  47 #include "ipcalc.h"
  48 #include "common/avl.h"
  49 #include "net_olsr.h"
  50
  51 /*
  52  * default comparison pointers
  53  * set to the respective compare function.
  54  * if avl_comp_default is set to zero, a fast
  55  * inline ipv4 comparison will be executed.
  56  */
  57 avl_tree_comp avl_comp_default = NULL;
  58 avl_tree_comp avl_comp_prefix_default;
  59
  60 int
  61 avl_comp_ipv4(const void *ip1, const void *ip2)
  62 {
  63   return ip4cmp(ip1, ip2);
  64 }
  65
  66 int
  67 avl_comp_ipv6(const void *ip1, const void *ip2)
  68 {
  69   return ip6cmp(ip1, ip2);
  70 }
  71
  72 int
  73 avl_comp_mac(const void *ip1, const void *ip2)
  74 {
  75   return memcmp(ip1, ip2, 6);
  76 }
  77
  78 void
  79 avl_init(struct avl_tree *tree, avl_tree_comp comp)
  80 {
  81   tree->root = NULL;
  82   tree->first = NULL;
  83   tree->last = NULL;
  84   tree->count = 0;
  85   tree->comp = comp;
  86 }
  87
  88 static struct avl_node *
  89 avl_find_rec_ipv4(struct avl_node *node, const void *key)
  90 {
  91   if (*(const unsigned int *)key < *(const unsigned int *)node->key) {
  92     if (node->left != NULL)
  93       return avl_find_rec_ipv4(node->left, key);
  94   }
  95
  96   else if (*(const unsigned int *)key > *(const unsigned int *)node->key) {
  97     if (node->right != NULL)
  98       return avl_find_rec_ipv4(node->right, key);
  99   }
 100
 101   return node;
 102 }
 103
 104 static struct avl_node *
 105 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp)
 106 {
 107   int diff;
 108
 109   if (NULL == comp)
 110     return avl_find_rec_ipv4(node, key);
 111
 112   diff = (*comp) (key, node->key);
 113
 114   if (diff < 0) {
 115     if (node->left != NULL)
 116       return avl_find_rec(node->left, key, comp);
 117
 118     return node;
 119   }
 120
 121   if (diff > 0) {
 122     if (node->right != NULL)
 123       return avl_find_rec(node->right, key, comp);
 124
 125     return node;
 126   }
 127
 128   return node;
 129 }
 130
 131 struct avl_node *
 132 avl_find(struct avl_tree *tree, const void *key)
 133 {
 134   struct avl_node *node;
 135
 136   if (tree->root == NULL)
 137     return NULL;
 138
 139   node = avl_find_rec(tree->root, key, tree->comp);
 140
 141   if (NULL == tree->comp) {
 142     if (0 != ip4cmp(node->key, key))
 143       return NULL;
 144   }
 145
 146   else {
 147     if ((*tree->comp) (node->key, key) != 0)
 148       return NULL;
 149   }
 150
 151   return node;
 152 }
 153
 154 static void
 155 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
 156 {
 157   struct avl_node *left, *parent;
 158
 159   left = node->left;
 160   parent = node->parent;
 161
 162   left->parent = parent;
 163   node->parent = left;
 164
 165   if (parent == NULL)
 166     tree->root = left;
 167
 168   else {
 169     if (parent->left == node)
 170       parent->left = left;
 171
 172     else
 173       parent->right = left;
 174   }
 175
 176   node->left = left->right;
 177   left->right = node;
 178
 179   if (node->left != NULL)
 180     node->left->parent = node;
 181
 182   node->balance += 1 - MIN(left->balance, 0);
 183   left->balance += 1 + MAX(node->balance, 0);
 184 }
 185
 186 static void
 187 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
 188 {
 189   struct avl_node *right, *parent;
 190
 191   right = node->right;
 192   parent = node->parent;
 193
 194   right->parent = parent;
 195   node->parent = right;
 196
 197   if (parent == NULL)
 198     tree->root = right;
 199
 200   else {
 201     if (parent->left == node)
 202       parent->left = right;
 203
 204     else
 205       parent->right = right;
 206   }
 207
 208   node->right = right->left;
 209   right->left = node;
 210
 211   if (node->right != NULL)
 212     node->right->parent = node;
 213
 214   node->balance -= 1 + MAX(right->balance, 0);
 215   right->balance -= 1 - MIN(node->balance, 0);
 216 }
 217
 218 static void
 219 post_insert(struct avl_tree *tree, struct avl_node *node)
 220 {
 221   struct avl_node *parent = node->parent;
 222
 223   if (parent == NULL)
 224     return;
 225
 226   if (node == parent->left) {
 227     parent->balance--;
 228
 229     if (parent->balance == 0)
 230       return;
 231
 232     if (parent->balance == -1) {
 233       post_insert(tree, parent);
 234       return;
 235     }
 236
 237     if (node->balance == -1) {
 238       avl_rotate_right(tree, parent);
 239       return;
 240     }
 241
 242     avl_rotate_left(tree, node);
 243     avl_rotate_right(tree, node->parent->parent);
 244     return;
 245   }
 246
 247   parent->balance++;
 248
 249   if (parent->balance == 0)
 250     return;
 251
 252   if (parent->balance == 1) {
 253     post_insert(tree, parent);
 254     return;
 255   }
 256
 257   if (node->balance == 1) {
 258     avl_rotate_left(tree, parent);
 259     return;
 260   }
 261
 262   avl_rotate_right(tree, node);
 263   avl_rotate_left(tree, node->parent->parent);
 264 }
 265
 266 static void
 267 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node,
 268                   struct avl_node *node)
 269 {
 270   if (pos_node->prev != NULL)
 271     pos_node->prev->next = node;
 272   else
 273     tree->first = node;
 274
 275   node->prev = pos_node->prev;
 276   node->next = pos_node;
 277
 278   pos_node->prev = node;
 279
 280   tree->count++;
 281 }
 282
 283 static void
 284 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node,
 285                  struct avl_node *node)
 286 {
 287   if (pos_node->next != NULL)
 288     pos_node->next->prev = node;
 289   else
 290     tree->last = node;
 291
 292   node->prev = pos_node;
 293   node->next = pos_node->next;
 294
 295   pos_node->next = node;
 296
 297   tree->count++;
 298 }
 299
 300 static void
 301 avl_remove(struct avl_tree *tree, struct avl_node *node)
 302 {
 303   if (node->prev != NULL)
 304     node->prev->next = node->next;
 305   else
 306     tree->first = node->next;
 307
 308   if (node->next != NULL)
 309     node->next->prev = node->prev;
 310   else
 311     tree->last = node->prev;
 312
 313   tree->count--;
 314 }
 315
 316 int
 317 avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
 318 {
 319   struct avl_node *node;
 320   struct avl_node *last;
 321   int diff;
 322
 323   new->parent = NULL;
 324
 325   new->left = NULL;
 326   new->right = NULL;
 327
 328   new->next = NULL;
 329   new->prev = NULL;
 330
 331   new->balance = 0;
 332   new->leader = 1;
 333
 334   if (tree->root == NULL) {
 335     tree->root = new;
 336     tree->first = new;
 337     tree->last = new;
 338     tree->count = 1;
 339     return 0;
 340   }
 341
 342   node = avl_find_rec(tree->root, new->key, tree->comp);
 343
 344   last = node;
 345
 346   while (last->next != NULL && last->next->leader == 0)
 347     last = last->next;
 348
 349   if (NULL == tree->comp)
 350     diff = ip4cmp(new->key, node->key);
 351
 352   else
 353     diff = (*tree->comp) (new->key, node->key);
 354
 355   if (diff == 0) {
 356     if (allow_duplicates == AVL_DUP_NO)
 357       return -1;
 358
 359     new->leader = 0;
 360
 361     avl_insert_after(tree, last, new);
 362     return 0;
 363   }
 364
 365   if (node->balance == 1) {
 366     avl_insert_before(tree, node, new);
 367
 368     node->balance = 0;
 369     new->parent = node;
 370     node->left = new;
 371     return 0;
 372   }
 373
 374   if (node->balance == -1) {
 375     avl_insert_after(tree, last, new);
 376
 377     node->balance = 0;
 378     new->parent = node;
 379     node->right = new;
 380     return 0;
 381   }
 382
 383   if (diff < 0) {
 384     avl_insert_before(tree, node, new);
 385
 386     node->balance = -1;
 387     new->parent = node;
 388     node->left = new;
 389     post_insert(tree, node);
 390     return 0;
 391   }
 392
 393   avl_insert_after(tree, last, new);
 394
 395   node->balance = 1;
 396   new->parent = node;
 397   node->right = new;
 398   post_insert(tree, node);
 399   return 0;
 400 }
 401
 402 static void
 403 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
 404 {
 405   struct avl_node *parent;
 406
 407   if ((parent = node->parent) == NULL)
 408     return;
 409
 410   if (node == parent->left) {
 411     parent->balance++;
 412
 413     if (parent->balance == 0) {
 414       avl_post_delete(tree, parent);
 415       return;
 416     }
 417
 418     if (parent->balance == 1)
 419       return;
 420
 421     if (parent->right->balance == 0) {
 422       avl_rotate_left(tree, parent);
 423       return;
 424     }
 425
 426     if (parent->right->balance == 1) {
 427       avl_rotate_left(tree, parent);
 428       avl_post_delete(tree, parent->parent);
 429       return;
 430     }
 431
 432     avl_rotate_right(tree, parent->right);
 433     avl_rotate_left(tree, parent);
 434     avl_post_delete(tree, parent->parent);
 435     return;
 436   }
 437
 438   parent->balance--;
 439
 440   if (parent->balance == 0) {
 441     avl_post_delete(tree, parent);
 442     return;
 443   }
 444
 445   if (parent->balance == -1)
 446     return;
 447
 448   if (parent->left->balance == 0) {
 449     avl_rotate_right(tree, parent);
 450     return;
 451   }
 452
 453   if (parent->left->balance == -1) {
 454     avl_rotate_right(tree, parent);
 455     avl_post_delete(tree, parent->parent);
 456     return;
 457   }
 458
 459   avl_rotate_left(tree, parent->left);
 460   avl_rotate_right(tree, parent);
 461   avl_post_delete(tree, parent->parent);
 462 }
 463
 464 static struct avl_node *
 465 avl_local_min(struct avl_node *node)
 466 {
 467   while (node->left != NULL)
 468     node = node->left;
 469
 470   return node;
 471 }
 472
 473 #if 0
 474 static struct avl_node *
 475 avl_local_max(struct avl_node *node)
 476 {
 477   while (node->right != NULL)
 478     node = node->right;
 479
 480   return node;
 481 }
 482 #endif
 483
 484 static void
 485 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
 486 {
 487   struct avl_node *parent, *min;
 488
 489   parent = node->parent;
 490
 491   if (node->left == NULL && node->right == NULL) {
 492     if (parent == NULL) {
 493       tree->root = NULL;
 494       return;
 495     }
 496
 497     if (parent->left == node) {
 498       parent->left = NULL;
 499       parent->balance++;
 500
 501       if (parent->balance == 1)
 502         return;
 503
 504       if (parent->balance == 0) {
 505         avl_post_delete(tree, parent);
 506         return;
 507       }
 508
 509       if (parent->right->balance == 0) {
 510         avl_rotate_left(tree, parent);
 511         return;
 512       }
 513
 514       if (parent->right->balance == 1) {
 515         avl_rotate_left(tree, parent);
 516         avl_post_delete(tree, parent->parent);
 517         return;
 518       }
 519
 520       avl_rotate_right(tree, parent->right);
 521       avl_rotate_left(tree, parent);
 522       avl_post_delete(tree, parent->parent);
 523       return;
 524     }
 525
 526     if (parent->right == node) {
 527       parent->right = NULL;
 528       parent->balance--;
 529
 530       if (parent->balance == -1)
 531         return;
 532
 533       if (parent->balance == 0) {
 534         avl_post_delete(tree, parent);
 535         return;
 536       }
 537
 538       if (parent->left->balance == 0) {
 539         avl_rotate_right(tree, parent);
 540         return;
 541       }
 542
 543       if (parent->left->balance == -1) {
 544         avl_rotate_right(tree, parent);
 545         avl_post_delete(tree, parent->parent);
 546         return;
 547       }
 548
 549       avl_rotate_left(tree, parent->left);
 550       avl_rotate_right(tree, parent);
 551       avl_post_delete(tree, parent->parent);
 552       return;
 553     }
 554   }
 555
 556   if (node->left == NULL) {
 557     if (parent == NULL) {
 558       tree->root = node->right;
 559       node->right->parent = NULL;
 560       return;
 561     }
 562
 563     node->right->parent = parent;
 564
 565     if (parent->left == node)
 566       parent->left = node->right;
 567
 568     else
 569       parent->right = node->right;
 570
 571     avl_post_delete(tree, node->right);
 572     return;
 573   }
 574
 575   if (node->right == NULL) {
 576     if (parent == NULL) {
 577       tree->root = node->left;
 578       node->left->parent = NULL;
 579       return;
 580     }
 581
 582     node->left->parent = parent;
 583
 584     if (parent->left == node)
 585       parent->left = node->left;
 586
 587     else
 588       parent->right = node->left;
 589
 590     avl_post_delete(tree, node->left);
 591     return;
 592   }
 593
 594   min = avl_local_min(node->right);
 595   avl_delete_worker(tree, min);
 596   parent = node->parent;
 597
 598   min->balance = node->balance;
 599   min->parent = parent;
 600   min->left = node->left;
 601   min->right = node->right;
 602
 603   if (min->left != NULL)
 604     min->left->parent = min;
 605
 606   if (min->right != NULL)
 607     min->right->parent = min;
 608
 609   if (parent == NULL) {
 610     tree->root = min;
 611     return;
 612   }
 613
 614   if (parent->left == node) {
 615     parent->left = min;
 616     return;
 617   }
 618
 619   parent->right = min;
 620 }
 621
 622 void
 623 avl_delete(struct avl_tree *tree, struct avl_node *node)
 624 {
 625   struct avl_node *next;
 626   struct avl_node *parent;
 627   struct avl_node *left;
 628   struct avl_node *right;
 629
 630   if (node->leader != 0) {
 631     next = node->next;
 632
 633     if (next != NULL && next->leader == 0) {
 634       next->leader = 1;
 635       next->balance = node->balance;
 636
 637       parent = node->parent;
 638       left = node->left;
 639       right = node->right;
 640
 641       next->parent = parent;
 642       next->left = left;
 643       next->right = right;
 644
 645       if (parent == NULL)
 646         tree->root = next;
 647
 648       else {
 649         if (node == parent->left)
 650           parent->left = next;
 651
 652         else
 653           parent->right = next;
 654       }
 655
 656       if (left != NULL)
 657         left->parent = next;
 658
 659       if (right != NULL)
 660         right->parent = next;
 661     }
 662
 663     else
 664       avl_delete_worker(tree, node);
 665   }
 666
 667   avl_remove(tree, node);
 668 }
 669
 670 /*
 671  * Local Variables:
 672  * c-basic-offset: 2
 673  * End:
 674  */