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