git.tinc-vpn.org Git - tinc/blob - 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         int r = 1;
  57
  58         if(!u) {
  59                 return 0;
  60         }
  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
  86         return r;
  87 }
  88 #endif
  89
  90 /* Internal helper functions */
  91
  92 static int avl_check_balance(const avl_node_t *node) {
  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
 113         if(pl < 2 || r >> pl - 2) {
 114                 return 0;
 115         }
 116
 117         return -1;
 118 #endif
 119 }
 120
 121 static void avl_rebalance(avl_tree_t *tree, avl_node_t *node) {
 122         avl_node_t *child;
 123         avl_node_t *gchild;
 124         avl_node_t *parent;
 125         avl_node_t **superparent;
 126
 127         while(node) {
 128                 parent = node->parent;
 129
 130                 superparent =
 131                         parent ? node ==
 132                         parent->left ? &parent->left : &parent->right : &tree->root;
 133
 134                 switch(avl_check_balance(node)) {
 135                 case -1:
 136                         child = node->left;
 137 #ifdef AVL_DEPTH
 138
 139                         if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
 140 #else
 141
 142                         if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
 143 #endif
 144                                 node->left = child->right;
 145
 146                                 if(node->left) {
 147                                         node->left->parent = node;
 148                                 }
 149
 150                                 child->right = node;
 151                                 node->parent = child;
 152                                 *superparent = child;
 153                                 child->parent = parent;
 154 #ifdef AVL_COUNT
 155                                 node->count = AVL_CALC_COUNT(node);
 156                                 child->count = AVL_CALC_COUNT(child);
 157 #endif
 158 #ifdef AVL_DEPTH
 159                                 node->depth = AVL_CALC_DEPTH(node);
 160                                 child->depth = AVL_CALC_DEPTH(child);
 161 #endif
 162                         } else {
 163                                 gchild = child->right;
 164                                 node->left = gchild->right;
 165
 166                                 if(node->left) {
 167                                         node->left->parent = node;
 168                                 }
 169
 170                                 child->right = gchild->left;
 171
 172                                 if(child->right) {
 173                                         child->right->parent = child;
 174                                 }
 175
 176                                 gchild->right = node;
 177
 178                                 gchild->right->parent = gchild;
 179                                 gchild->left = child;
 180
 181                                 gchild->left->parent = gchild;
 182
 183                                 *superparent = gchild;
 184                                 gchild->parent = parent;
 185 #ifdef AVL_COUNT
 186                                 node->count = AVL_CALC_COUNT(node);
 187                                 child->count = AVL_CALC_COUNT(child);
 188                                 gchild->count = AVL_CALC_COUNT(gchild);
 189 #endif
 190 #ifdef AVL_DEPTH
 191                                 node->depth = AVL_CALC_DEPTH(node);
 192                                 child->depth = AVL_CALC_DEPTH(child);
 193                                 gchild->depth = AVL_CALC_DEPTH(gchild);
 194 #endif
 195                         }
 196
 197                         break;
 198
 199                 case 1:
 200                         child = node->right;
 201 #ifdef AVL_DEPTH
 202
 203                         if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
 204 #else
 205
 206                         if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
 207 #endif
 208                                 node->right = child->left;
 209
 210                                 if(node->right) {
 211                                         node->right->parent = node;
 212                                 }
 213
 214                                 child->left = node;
 215                                 node->parent = child;
 216                                 *superparent = child;
 217                                 child->parent = parent;
 218 #ifdef AVL_COUNT
 219                                 node->count = AVL_CALC_COUNT(node);
 220                                 child->count = AVL_CALC_COUNT(child);
 221 #endif
 222 #ifdef AVL_DEPTH
 223                                 node->depth = AVL_CALC_DEPTH(node);
 224                                 child->depth = AVL_CALC_DEPTH(child);
 225 #endif
 226                         } else {
 227                                 gchild = child->left;
 228                                 node->right = gchild->left;
 229
 230                                 if(node->right) {
 231                                         node->right->parent = node;
 232                                 }
 233
 234                                 child->left = gchild->right;
 235
 236                                 if(child->left) {
 237                                         child->left->parent = child;
 238                                 }
 239
 240                                 gchild->left = node;
 241
 242                                 gchild->left->parent = gchild;
 243                                 gchild->right = child;
 244
 245                                 gchild->right->parent = gchild;
 246
 247                                 *superparent = gchild;
 248                                 gchild->parent = parent;
 249 #ifdef AVL_COUNT
 250                                 node->count = AVL_CALC_COUNT(node);
 251                                 child->count = AVL_CALC_COUNT(child);
 252                                 gchild->count = AVL_CALC_COUNT(gchild);
 253 #endif
 254 #ifdef AVL_DEPTH
 255                                 node->depth = AVL_CALC_DEPTH(node);
 256                                 child->depth = AVL_CALC_DEPTH(child);
 257                                 gchild->depth = AVL_CALC_DEPTH(gchild);
 258 #endif
 259                         }
 260
 261                         break;
 262
 263                 default:
 264 #ifdef AVL_COUNT
 265                         node->count = AVL_CALC_COUNT(node);
 266 #endif
 267 #ifdef AVL_DEPTH
 268                         node->depth = AVL_CALC_DEPTH(node);
 269 #endif
 270                 }
 271
 272                 node = parent;
 273         }
 274 }
 275
 276 /* (De)constructors */
 277
 278 avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete) {
 279         avl_tree_t *tree;
 280
 281         tree = xmalloc_and_zero(sizeof(avl_tree_t));
 282         tree->compare = compare;
 283         tree->delete = delete;
 284
 285         return tree;
 286 }
 287
 288 void avl_free_tree(avl_tree_t *tree) {
 289         free(tree);
 290 }
 291
 292 avl_node_t *avl_alloc_node(void) {
 293         return xmalloc_and_zero(sizeof(avl_node_t));
 294 }
 295
 296 void avl_free_node(avl_tree_t *tree, avl_node_t *node) {
 297         if(node->data && tree->delete) {
 298                 tree->delete(node->data);
 299         }
 300
 301         free(node);
 302 }
 303
 304 /* Searching */
 305
 306 void *avl_search(const avl_tree_t *tree, const void *data) {
 307         avl_node_t *node;
 308
 309         node = avl_search_node(tree, data);
 310
 311         return node ? node->data : NULL;
 312 }
 313
 314 void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result) {
 315         avl_node_t *node;
 316
 317         node = avl_search_closest_node(tree, data, result);
 318
 319         return node ? node->data : NULL;
 320 }
 321
 322 void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data) {
 323         avl_node_t *node;
 324
 325         node = avl_search_closest_smaller_node(tree, data);
 326
 327         return node ? node->data : NULL;
 328 }
 329
 330 void *avl_search_closest_greater(const avl_tree_t *tree, const void *data) {
 331         avl_node_t *node;
 332
 333         node = avl_search_closest_greater_node(tree, data);
 334
 335         return node ? node->data : NULL;
 336 }
 337
 338 avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) {
 339         avl_node_t *node;
 340         int result;
 341
 342         node = avl_search_closest_node(tree, data, &result);
 343
 344         return result ? NULL : node;
 345 }
 346
 347 avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
 348                                     int *result) {
 349         avl_node_t *node;
 350         int c;
 351
 352         node = tree->root;
 353
 354         if(!node) {
 355                 if(result) {
 356                         *result = 0;
 357                 }
 358
 359                 return NULL;
 360         }
 361
 362         for(;;) {
 363                 c = tree->compare(data, node->data);
 364
 365                 if(c < 0) {
 366                         if(node->left) {
 367                                 node = node->left;
 368                         } else {
 369                                 if(result) {
 370                                         *result = -1;
 371                                 }
 372
 373                                 break;
 374                         }
 375                 } else if(c > 0) {
 376                         if(node->right) {
 377                                 node = node->right;
 378                         } else {
 379                                 if(result) {
 380                                         *result = 1;
 381                                 }
 382
 383                                 break;
 384                         }
 385                 } else {
 386                         if(result) {
 387                                 *result = 0;
 388                         }
 389
 390                         break;
 391                 }
 392         }
 393
 394         return node;
 395 }
 396
 397 avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree,
 398                 const void *data) {
 399         avl_node_t *node;
 400         int result;
 401
 402         node = avl_search_closest_node(tree, data, &result);
 403
 404         if(result < 0) {
 405                 node = node->prev;
 406         }
 407
 408         return node;
 409 }
 410
 411 avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree,
 412                 const void *data) {
 413         avl_node_t *node;
 414         int result;
 415
 416         node = avl_search_closest_node(tree, data, &result);
 417
 418         if(result > 0) {
 419                 node = node->next;
 420         }
 421
 422         return node;
 423 }
 424
 425 /* Insertion and deletion */
 426
 427 avl_node_t *avl_insert(avl_tree_t *tree, void *data) {
 428         avl_node_t *closest, *new;
 429         int result;
 430
 431         if(!tree->root) {
 432                 new = avl_alloc_node();
 433                 new->data = data;
 434                 avl_insert_top(tree, new);
 435         } else {
 436                 closest = avl_search_closest_node(tree, data, &result);
 437
 438                 switch(result) {
 439                 case -1:
 440                         new = avl_alloc_node();
 441                         new->data = data;
 442                         avl_insert_before(tree, closest, new);
 443                         break;
 444
 445                 case 1:
 446                         new = avl_alloc_node();
 447                         new->data = data;
 448                         avl_insert_after(tree, closest, new);
 449                         break;
 450
 451                 default:
 452                         return NULL;
 453                 }
 454         }
 455
 456 #ifdef AVL_COUNT
 457         new->count = 1;
 458 #endif
 459 #ifdef AVL_DEPTH
 460         new->depth = 1;
 461 #endif
 462
 463         return new;
 464 }
 465
 466 avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) {
 467         avl_node_t *closest;
 468         int result;
 469
 470         if(!tree->root) {
 471                 avl_insert_top(tree, node);
 472         } else {
 473                 closest = avl_search_closest_node(tree, node->data, &result);
 474
 475                 switch(result) {
 476                 case -1:
 477                         avl_insert_before(tree, closest, node);
 478                         break;
 479
 480                 case 1:
 481                         avl_insert_after(tree, closest, node);
 482                         break;
 483
 484                 case 0:
 485                         return NULL;
 486                 }
 487         }
 488
 489 #ifdef AVL_COUNT
 490         node->count = 1;
 491 #endif
 492 #ifdef AVL_DEPTH
 493         node->depth = 1;
 494 #endif
 495
 496         return node;
 497 }
 498
 499 void avl_insert_top(avl_tree_t *tree, avl_node_t *node) {
 500         node->prev = node->next = node->parent = NULL;
 501         tree->head = tree->tail = tree->root = node;
 502 }
 503
 504 void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
 505                        avl_node_t *node) {
 506         if(!before) {
 507                 if(tree->tail) {
 508                         avl_insert_after(tree, tree->tail, node);
 509                 } else {
 510                         avl_insert_top(tree, node);
 511                 }
 512
 513                 return;
 514         }
 515
 516         node->next = before;
 517         node->parent = before;
 518         node->prev = before->prev;
 519
 520         if(before->left) {
 521                 avl_insert_after(tree, before->prev, node);
 522                 return;
 523         }
 524
 525         if(before->prev) {
 526                 before->prev->next = node;
 527         } else {
 528                 tree->head = node;
 529         }
 530
 531         before->prev = node;
 532         before->left = node;
 533
 534         avl_rebalance(tree, before);
 535 }
 536
 537 void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) {
 538         if(!after) {
 539                 if(tree->head) {
 540                         avl_insert_before(tree, tree->head, node);
 541                 } else {
 542                         avl_insert_top(tree, node);
 543                 }
 544
 545                 return;
 546         }
 547
 548         if(after->right) {
 549                 avl_insert_before(tree, after->next, node);
 550                 return;
 551         }
 552
 553         node->prev = after;
 554         node->parent = after;
 555         node->next = after->next;
 556
 557         if(after->next) {
 558                 after->next->prev = node;
 559         } else {
 560                 tree->tail = node;
 561         }
 562
 563         after->next = node;
 564         after->right = node;
 565
 566         avl_rebalance(tree, after);
 567 }
 568
 569 avl_node_t *avl_unlink(avl_tree_t *tree, void *data) {
 570         avl_node_t *node;
 571
 572         node = avl_search_node(tree, data);
 573
 574         if(node) {
 575                 avl_unlink_node(tree, node);
 576         }
 577
 578         return node;
 579 }
 580
 581 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) {
 582         avl_node_t *parent;
 583         avl_node_t **superparent;
 584         avl_node_t *subst, *left, *right;
 585         avl_node_t *balnode;
 586
 587         if(node->prev) {
 588                 node->prev->next = node->next;
 589         } else {
 590                 tree->head = node->next;
 591         }
 592
 593         if(node->next) {
 594                 node->next->prev = node->prev;
 595         } else {
 596                 tree->tail = node->prev;
 597         }
 598
 599         parent = node->parent;
 600
 601         superparent =
 602                 parent ? node ==
 603                 parent->left ? &parent->left : &parent->right : &tree->root;
 604
 605         left = node->left;
 606         right = node->right;
 607
 608         if(!left) {
 609                 *superparent = right;
 610
 611                 if(right) {
 612                         right->parent = parent;
 613                 }
 614
 615                 balnode = parent;
 616         } else if(!right) {
 617                 *superparent = left;
 618                 left->parent = parent;
 619                 balnode = parent;
 620         } else {
 621                 subst = node->prev;
 622
 623                 if(!subst) { // This only happens if node is not actually in a tree at all.
 624                         abort();
 625                 }
 626
 627                 if(subst == left) {
 628                         balnode = subst;
 629                 } else {
 630                         balnode = subst->parent;
 631                         balnode->right = subst->left;
 632
 633                         if(balnode->right) {
 634                                 balnode->right->parent = balnode;
 635                         }
 636
 637                         subst->left = left;
 638                         left->parent = subst;
 639                 }
 640
 641                 subst->right = right;
 642                 subst->parent = parent;
 643                 right->parent = subst;
 644                 *superparent = subst;
 645         }
 646
 647         avl_rebalance(tree, balnode);
 648
 649         node->next = node->prev = node->parent = node->left = node->right = NULL;
 650
 651 #ifdef AVL_COUNT
 652         node->count = 0;
 653 #endif
 654 #ifdef AVL_DEPTH
 655         node->depth = 0;
 656 #endif
 657 }
 658
 659 void avl_delete_node(avl_tree_t *tree, avl_node_t *node) {
 660         avl_unlink_node(tree, node);
 661         avl_free_node(tree, node);
 662 }
 663
 664 void avl_delete(avl_tree_t *tree, void *data) {
 665         avl_node_t *node;
 666
 667         node = avl_search_node(tree, data);
 668
 669         if(node) {
 670                 avl_delete_node(tree, node);
 671         }
 672 }
 673
 674 /* Fast tree cleanup */
 675
 676 void avl_delete_tree(avl_tree_t *tree) {
 677         avl_node_t *node, *next;
 678
 679         for(node = tree->head; node; node = next) {
 680                 next = node->next;
 681                 avl_free_node(tree, node);
 682         }
 683
 684         avl_free_tree(tree);
 685 }
 686
 687 /* Tree walking */
 688
 689 void avl_foreach(const avl_tree_t *tree, avl_action_t action) {
 690         avl_node_t *node, *next;
 691
 692         for(node = tree->head; node; node = next) {
 693                 next = node->next;
 694                 action(node->data);
 695         }
 696 }
 697
 698 void avl_foreach_node(const avl_tree_t *tree, avl_action_t action) {
 699         avl_node_t *node, *next;
 700
 701         for(node = tree->head; node; node = next) {
 702                 next = node->next;
 703                 action(node);
 704         }
 705 }
 706
 707 /* Indexing */
 708
 709 #ifdef AVL_COUNT
 710 unsigned int avl_count(const avl_tree_t *tree) {
 711         return AVL_NODE_COUNT(tree->root);
 712 }
 713
 714 avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index) {
 715         avl_node_t *node;
 716         unsigned int c;
 717
 718         node = tree->root;
 719
 720         while(node) {
 721                 c = AVL_L_COUNT(node);
 722
 723                 if(index < c) {
 724                         node = node->left;
 725                 } else if(index > c) {
 726                         node = node->right;
 727                         index -= c + 1;
 728                 } else {
 729                         return node;
 730                 }
 731         }
 732
 733         return NULL;
 734 }
 735
 736 unsigned int avl_index(const avl_node_t *node) {
 737         avl_node_t *next;
 738         unsigned int index;
 739
 740         index = AVL_L_COUNT(node);
 741
 742         while((next = node->parent)) {
 743                 if(node == next->right) {
 744                         index += AVL_L_COUNT(next) + 1;
 745                 }
 746
 747                 node = next;
 748         }
 749
 750         return index;
 751 }
 752 #endif
 753 #ifdef AVL_DEPTH
 754 unsigned int avl_depth(const avl_tree_t *tree) {
 755         return AVL_NODE_DEPTH(tree->root);
 756 }
 757 #endif