lib/avl_tree.c

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