src/avl.c

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