git.tinc-vpn.org Git - tinc/blob - lib/avl_tree.c

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