src/avl_tree.c

   1 /*
   2     avl_tree.c -- avl_ tree and linked list convenience
   3     Copyright (C) 1998 Michael H. Buselli
   4                   2000-2005 Ivo Timmermans,
   5                   2000-2015 Guus Sliepen <guus@tinc-vpn.org>
   6                   2000-2005 Wessel Dankers <wsl@tinc-vpn.org>
   7
   8     This program is free software; you can redistribute it and/or modify
   9     it under the terms of the GNU General Public License as published by
  10     the Free Software Foundation; either version 2 of the License, or
  11     (at your option) any later version.
  12
  13     This program is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License along
  19     with this program; if not, write to the Free Software Foundation, Inc.,
  20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21
  22     Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
  23
  24     Modified 2000-11-28 by Wessel Dankers <wsl@tinc-vpn.org> to use counts
  25     instead of depths, to add the ->next and ->prev and to generally obfuscate
  26     the code. Mail me if you found a bug.
  27
  28     Cleaned up and incorporated some of the ideas from the red-black tree
  29     library for inclusion into tinc (https://www.tinc-vpn.org/) by
  30     Guus Sliepen <guus@tinc-vpn.org>.
  31 */
  32
  33 #include "system.h"
  34
  35 #include "avl_tree.h"
  36 #include "xalloc.h"
  37
  38 #ifdef AVL_COUNT
  39 #define AVL_NODE_COUNT(n)  ((n) ? (n)->count : 0)
  40 #define AVL_L_COUNT(n)     (AVL_NODE_COUNT((n)->left))
  41 #define AVL_R_COUNT(n)     (AVL_NODE_COUNT((n)->right))
  42 #define AVL_CALC_COUNT(n)  (AVL_L_COUNT(n) + AVL_R_COUNT(n) + 1)
  43 #endif
  44
  45 #ifdef AVL_DEPTH
  46 #define AVL_NODE_DEPTH(n)  ((n) ? (n)->depth : 0)
  47 #define L_AVL_DEPTH(n)     (AVL_NODE_DEPTH((n)->left))
  48 #define R_AVL_DEPTH(n)     (AVL_NODE_DEPTH((n)->right))
  49 #define AVL_CALC_DEPTH(n)  ((L_AVL_DEPTH(n)>R_AVL_DEPTH(n)?L_AVL_DEPTH(n):R_AVL_DEPTH(n)) + 1)
  50 #endif
  51
  52 #ifndef AVL_DEPTH
  53 static int lg(unsigned int u) __attribute__ ((__const__));
  54
  55 static int lg(unsigned int u)
  56 {
  57         int r = 1;
  58
  59         if(!u)
  60                 return 0;
  61
  62         if(u & 0xffff0000) {
  63                 u >>= 16;
  64                 r += 16;
  65         }
  66
  67         if(u & 0x0000ff00) {
  68                 u >>= 8;
  69                 r += 8;
  70         }
  71
  72         if(u & 0x000000f0) {
  73                 u >>= 4;
  74                 r += 4;
  75         }
  76
  77         if(u & 0x0000000c) {
  78                 u >>= 2;
  79                 r += 2;
  80         }
  81
  82         if(u & 0x00000002)
  83                 r++;
  84
  85         return r;
  86 }
  87 #endif
  88
  89 /* Internal helper functions */
  90
  91 static int avl_check_balance(const avl_node_t *node)
  92 {
  93 #ifdef AVL_DEPTH
  94         int d;
  95
  96         d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node);
  97
  98         return d < -1 ? -1 : d > 1 ? 1 : 0;
  99 #else
 100 /*      int d;
 101  *      d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node));
 102  *      d = d<-1?-1:d>1?1:0;
 103  */
 104         int pl, r;
 105
 106         pl = lg(AVL_L_COUNT(node));
 107         r = AVL_R_COUNT(node);
 108
 109         if(r >> pl + 1)
 110                 return 1;
 111
 112         if(pl < 2 || r >> pl - 2)
 113                 return 0;
 114
 115         return -1;
 116 #endif
 117 }
 118
 119 static void avl_rebalance(avl_tree_t *tree, avl_node_t *node)
 120 {
 121         avl_node_t *child;
 122         avl_node_t *gchild;
 123         avl_node_t *parent;
 124         avl_node_t **superparent;
 125
 126         while(node) {
 127                 parent = node->parent;
 128
 129                 superparent =
 130                         parent ? node ==
 131                         parent->left ? &parent->left : &parent->right : &tree->root;
 132
 133                 switch (avl_check_balance(node)) {
 134                         case -1:
 135                                 child = node->left;
 136 #ifdef AVL_DEPTH
 137                                 if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
 138 #else
 139                                 if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
 140 #endif
 141                                         node->left = child->right;
 142                                         if(node->left)
 143                                                 node->left->parent = node;
 144
 145                                         child->right = node;
 146                                         node->parent = child;
 147                                         *superparent = child;
 148                                         child->parent = parent;
 149 #ifdef AVL_COUNT
 150                                         node->count = AVL_CALC_COUNT(node);
 151                                         child->count = AVL_CALC_COUNT(child);
 152 #endif
 153 #ifdef AVL_DEPTH
 154                                         node->depth = AVL_CALC_DEPTH(node);
 155                                         child->depth = AVL_CALC_DEPTH(child);
 156 #endif
 157                                 } else {
 158                                         gchild = child->right;
 159                                         node->left = gchild->right;
 160
 161                                         if(node->left)
 162                                                 node->left->parent = node;
 163                                         child->right = gchild->left;
 164
 165                                         if(child->right)
 166                                                 child->right->parent = child;
 167                                         gchild->right = node;
 168
 169                                         gchild->right->parent = gchild;
 170                                         gchild->left = child;
 171
 172                                         gchild->left->parent = gchild;
 173
 174                                         *superparent = gchild;
 175                                         gchild->parent = parent;
 176 #ifdef AVL_COUNT
 177                                         node->count = AVL_CALC_COUNT(node);
 178                                         child->count = AVL_CALC_COUNT(child);
 179                                         gchild->count = AVL_CALC_COUNT(gchild);
 180 #endif
 181 #ifdef AVL_DEPTH
 182                                         node->depth = AVL_CALC_DEPTH(node);
 183                                         child->depth = AVL_CALC_DEPTH(child);
 184                                         gchild->depth = AVL_CALC_DEPTH(gchild);
 185 #endif
 186                                 }
 187                                 break;
 188
 189                         case 1:
 190                                 child = node->right;
 191 #ifdef AVL_DEPTH
 192                                 if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
 193 #else
 194                                 if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
 195 #endif
 196                                         node->right = child->left;
 197                                         if(node->right)
 198                                                 node->right->parent = node;
 199                                         child->left = node;
 200                                         node->parent = child;
 201                                         *superparent = child;
 202                                         child->parent = parent;
 203 #ifdef AVL_COUNT
 204                                         node->count = AVL_CALC_COUNT(node);
 205                                         child->count = AVL_CALC_COUNT(child);
 206 #endif
 207 #ifdef AVL_DEPTH
 208                                         node->depth = AVL_CALC_DEPTH(node);
 209                                         child->depth = AVL_CALC_DEPTH(child);
 210 #endif
 211                                 } else {
 212                                         gchild = child->left;
 213                                         node->right = gchild->left;
 214
 215                                         if(node->right)
 216                                                 node->right->parent = node;
 217                                         child->left = gchild->right;
 218
 219                                         if(child->left)
 220                                                 child->left->parent = child;
 221                                         gchild->left = node;
 222
 223                                         gchild->left->parent = gchild;
 224                                         gchild->right = child;
 225
 226                                         gchild->right->parent = gchild;
 227
 228                                         *superparent = gchild;
 229                                         gchild->parent = parent;
 230 #ifdef AVL_COUNT
 231                                         node->count = AVL_CALC_COUNT(node);
 232                                         child->count = AVL_CALC_COUNT(child);
 233                                         gchild->count = AVL_CALC_COUNT(gchild);
 234 #endif
 235 #ifdef AVL_DEPTH
 236                                         node->depth = AVL_CALC_DEPTH(node);
 237                                         child->depth = AVL_CALC_DEPTH(child);
 238                                         gchild->depth = AVL_CALC_DEPTH(gchild);
 239 #endif
 240                                 }
 241                                 break;
 242
 243                         default:
 244 #ifdef AVL_COUNT
 245                                 node->count = AVL_CALC_COUNT(node);
 246 #endif
 247 #ifdef AVL_DEPTH
 248                                 node->depth = AVL_CALC_DEPTH(node);
 249 #endif
 250                 }
 251                 node = parent;
 252         }
 253 }
 254
 255 /* (De)constructors */
 256
 257 avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete)
 258 {
 259         avl_tree_t *tree;
 260
 261         tree = xmalloc_and_zero(sizeof(avl_tree_t));
 262         tree->compare = compare;
 263         tree->delete = delete;
 264
 265         return tree;
 266 }
 267
 268 void avl_free_tree(avl_tree_t *tree)
 269 {
 270         free(tree);
 271 }
 272
 273 avl_node_t *avl_alloc_node(void)
 274 {
 275         return xmalloc_and_zero(sizeof(avl_node_t));
 276 }
 277
 278 void avl_free_node(avl_tree_t *tree, avl_node_t *node)
 279 {
 280         if(node->data && tree->delete)
 281                 tree->delete(node->data);
 282
 283         free(node);
 284 }
 285
 286 /* Searching */
 287
 288 void *avl_search(const avl_tree_t *tree, const void *data)
 289 {
 290         avl_node_t *node;
 291
 292         node = avl_search_node(tree, data);
 293
 294         return node ? node->data : NULL;
 295 }
 296
 297 void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result)
 298 {
 299         avl_node_t *node;
 300
 301         node = avl_search_closest_node(tree, data, result);
 302
 303         return node ? node->data : NULL;
 304 }
 305
 306 void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data)
 307 {
 308         avl_node_t *node;
 309
 310         node = avl_search_closest_smaller_node(tree, data);
 311
 312         return node ? node->data : NULL;
 313 }
 314
 315 void *avl_search_closest_greater(const avl_tree_t *tree, const void *data)
 316 {
 317         avl_node_t *node;
 318
 319         node = avl_search_closest_greater_node(tree, data);
 320
 321         return node ? node->data : NULL;
 322 }
 323
 324 avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data)
 325 {
 326         avl_node_t *node;
 327         int result;
 328
 329         node = avl_search_closest_node(tree, data, &result);
 330
 331         return result ? NULL : node;
 332 }
 333
 334 avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
 335                                                                         int *result)
 336 {
 337         avl_node_t *node;
 338         int c;
 339
 340         node = tree->root;
 341
 342         if(!node) {
 343                 if(result)
 344                         *result = 0;
 345                 return NULL;
 346         }
 347
 348         for(;;) {
 349                 c = tree->compare(data, node->data);
 350
 351                 if(c < 0) {
 352                         if(node->left)
 353                                 node = node->left;
 354                         else {
 355                                 if(result)
 356                                         *result = -1;
 357                                 break;
 358                         }
 359                 } else if(c > 0) {
 360                         if(node->right)
 361                                 node = node->right;
 362                         else {
 363                                 if(result)
 364                                         *result = 1;
 365                                 break;
 366                         }
 367                 } else {
 368                         if(result)
 369                                 *result = 0;
 370                         break;
 371                 }
 372         }
 373
 374         return node;
 375 }
 376
 377 avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree,
 378                                                                                         const void *data)
 379 {
 380         avl_node_t *node;
 381         int result;
 382
 383         node = avl_search_closest_node(tree, data, &result);
 384
 385         if(result < 0)
 386                 node = node->prev;
 387
 388         return node;
 389 }
 390
 391 avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree,
 392                                                                                         const void *data)
 393 {
 394         avl_node_t *node;
 395         int result;
 396
 397         node = avl_search_closest_node(tree, data, &result);
 398
 399         if(result > 0)
 400                 node = node->next;
 401
 402         return node;
 403 }
 404
 405 /* Insertion and deletion */
 406
 407 avl_node_t *avl_insert(avl_tree_t *tree, void *data)
 408 {
 409         avl_node_t *closest, *new;
 410         int result;
 411
 412         if(!tree->root) {
 413                 new = avl_alloc_node();
 414                 new->data = data;
 415                 avl_insert_top(tree, new);
 416         } else {
 417                 closest = avl_search_closest_node(tree, data, &result);
 418
 419                 switch (result) {
 420                         case -1:
 421                                 new = avl_alloc_node();
 422                                 new->data = data;
 423                                 avl_insert_before(tree, closest, new);
 424                                 break;
 425
 426                         case 1:
 427                                 new = avl_alloc_node();
 428                                 new->data = data;
 429                                 avl_insert_after(tree, closest, new);
 430                                 break;
 431
 432                         default:
 433                                 return NULL;
 434                 }
 435         }
 436
 437 #ifdef AVL_COUNT
 438         new->count = 1;
 439 #endif
 440 #ifdef AVL_DEPTH
 441         new->depth = 1;
 442 #endif
 443
 444         return new;
 445 }
 446
 447 avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
 448 {
 449         avl_node_t *closest;
 450         int result;
 451
 452         if(!tree->root)
 453                 avl_insert_top(tree, node);
 454         else {
 455                 closest = avl_search_closest_node(tree, node->data, &result);
 456
 457                 switch (result) {
 458                         case -1:
 459                                 avl_insert_before(tree, closest, node);
 460                                 break;
 461
 462                         case 1:
 463                                 avl_insert_after(tree, closest, node);
 464                                 break;
 465
 466                         case 0:
 467                                 return NULL;
 468                 }
 469         }
 470
 471 #ifdef AVL_COUNT
 472         node->count = 1;
 473 #endif
 474 #ifdef AVL_DEPTH
 475         node->depth = 1;
 476 #endif
 477
 478         return node;
 479 }
 480
 481 void avl_insert_top(avl_tree_t *tree, avl_node_t *node)
 482 {
 483         node->prev = node->next = node->parent = NULL;
 484         tree->head = tree->tail = tree->root = node;
 485 }
 486
 487 void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
 488                                            avl_node_t *node)
 489 {
 490         if(!before) {
 491                 if(tree->tail)
 492                         avl_insert_after(tree, tree->tail, node);
 493                 else
 494                         avl_insert_top(tree, node);
 495                 return;
 496         }
 497
 498         node->next = before;
 499         node->parent = before;
 500         node->prev = before->prev;
 501
 502         if(before->left) {
 503                 avl_insert_after(tree, before->prev, node);
 504                 return;
 505         }
 506
 507         if(before->prev)
 508                 before->prev->next = node;
 509         else
 510                 tree->head = node;
 511
 512         before->prev = node;
 513         before->left = node;
 514
 515         avl_rebalance(tree, before);
 516 }
 517
 518 void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
 519 {
 520         if(!after) {
 521                 if(tree->head)
 522                         avl_insert_before(tree, tree->head, node);
 523                 else
 524                         avl_insert_top(tree, node);
 525                 return;
 526         }
 527
 528         if(after->right) {
 529                 avl_insert_before(tree, after->next, node);
 530                 return;
 531         }
 532
 533         node->prev = after;
 534         node->parent = after;
 535         node->next = after->next;
 536
 537         if(after->next)
 538                 after->next->prev = node;
 539         else
 540                 tree->tail = node;
 541
 542         after->next = node;
 543         after->right = node;
 544
 545         avl_rebalance(tree, after);
 546 }
 547
 548 avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
 549 {
 550         avl_node_t *node;
 551
 552         node = avl_search_node(tree, data);
 553
 554         if(node)
 555                 avl_unlink_node(tree, node);
 556
 557         return node;
 558 }
 559
 560 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
 561 {
 562         avl_node_t *parent;
 563         avl_node_t **superparent;
 564         avl_node_t *subst, *left, *right;
 565         avl_node_t *balnode;
 566
 567         if(node->prev)
 568                 node->prev->next = node->next;
 569         else
 570                 tree->head = node->next;
 571         if(node->next)
 572                 node->next->prev = node->prev;
 573         else
 574                 tree->tail = node->prev;
 575
 576         parent = node->parent;
 577
 578         superparent =
 579                 parent ? node ==
 580                 parent->left ? &parent->left : &parent->right : &tree->root;
 581
 582         left = node->left;
 583         right = node->right;
 584         if(!left) {
 585                 *superparent = right;
 586
 587                 if(right)
 588                         right->parent = parent;
 589
 590                 balnode = parent;
 591         } else if(!right) {
 592                 *superparent = left;
 593                 left->parent = parent;
 594                 balnode = parent;
 595         } else {
 596                 subst = node->prev;
 597                 if(!subst) // This only happens if node is not actually in a tree at all.
 598                         abort();
 599
 600                 if(subst == left) {
 601                         balnode = subst;
 602                 } else {
 603                         balnode = subst->parent;
 604                         balnode->right = subst->left;
 605
 606                         if(balnode->right)
 607                                 balnode->right->parent = balnode;
 608
 609                         subst->left = left;
 610                         left->parent = subst;
 611                 }
 612
 613                 subst->right = right;
 614                 subst->parent = parent;
 615                 right->parent = subst;
 616                 *superparent = subst;
 617         }
 618
 619         avl_rebalance(tree, balnode);
 620
 621         node->next = node->prev = node->parent = node->left = node->right = NULL;
 622
 623 #ifdef AVL_COUNT
 624         node->count = 0;
 625 #endif
 626 #ifdef AVL_DEPTH
 627         node->depth = 0;
 628 #endif
 629 }
 630
 631 void avl_delete_node(avl_tree_t *tree, avl_node_t *node)
 632 {
 633         avl_unlink_node(tree, node);
 634         avl_free_node(tree, node);
 635 }
 636
 637 void avl_delete(avl_tree_t *tree, void *data)
 638 {
 639         avl_node_t *node;
 640
 641         node = avl_search_node(tree, data);
 642
 643         if(node)
 644                 avl_delete_node(tree, node);
 645 }
 646
 647 /* Fast tree cleanup */
 648
 649 void avl_delete_tree(avl_tree_t *tree)
 650 {
 651         avl_node_t *node, *next;
 652
 653         for(node = tree->head; node; node = next) {
 654                 next = node->next;
 655                 avl_free_node(tree, node);
 656         }
 657
 658         avl_free_tree(tree);
 659 }
 660
 661 /* Tree walking */
 662
 663 void avl_foreach(const avl_tree_t *tree, avl_action_t action)
 664 {
 665         avl_node_t *node, *next;
 666
 667         for(node = tree->head; node; node = next) {
 668                 next = node->next;
 669                 action(node->data);
 670         }
 671 }
 672
 673 void avl_foreach_node(const avl_tree_t *tree, avl_action_t action)
 674 {
 675         avl_node_t *node, *next;
 676
 677         for(node = tree->head; node; node = next) {
 678                 next = node->next;
 679                 action(node);
 680         }
 681 }
 682
 683 /* Indexing */
 684
 685 #ifdef AVL_COUNT
 686 unsigned int avl_count(const avl_tree_t *tree)
 687 {
 688         return AVL_NODE_COUNT(tree->root);
 689 }
 690
 691 avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index)
 692 {
 693         avl_node_t *node;
 694         unsigned int c;
 695
 696         node = tree->root;
 697
 698         while(node) {
 699                 c = AVL_L_COUNT(node);
 700
 701                 if(index < c) {
 702                         node = node->left;
 703                 } else if(index > c) {
 704                         node = node->right;
 705                         index -= c + 1;
 706                 } else {
 707                         return node;
 708                 }
 709         }
 710
 711         return NULL;
 712 }
 713
 714 unsigned int avl_index(const avl_node_t *node)
 715 {
 716         avl_node_t *next;
 717         unsigned int index;
 718
 719         index = AVL_L_COUNT(node);
 720
 721         while((next = node->parent)) {
 722                 if(node == next->right)
 723                         index += AVL_L_COUNT(next) + 1;
 724                 node = next;
 725         }
 726
 727         return index;
 728 }
 729 #endif
 730 #ifdef AVL_DEPTH
 731 unsigned int avl_depth(const avl_tree_t *tree)
 732 {
 733         return AVL_NODE_DEPTH(tree->root);
 734 }
 735 #endif