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