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,2001 Ivo Timmermans <ivo@o2w.nl>,
   5                   2000,2001 Guus Sliepen <guus@sliepen.eu.org>
   6                   2000,2001 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.13 2003/06/11 19:39:02 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 int lg(unsigned int u)
  57 {
  58         int r = 1;
  59
  60         if(!u)
  61                 return 0;
  62
  63         if(u & 0xffff0000) {
  64                 u >>= 16;
  65                 r += 16;
  66         }
  67
  68         if(u & 0x0000ff00) {
  69                 u >>= 8;
  70                 r += 8;
  71         }
  72
  73         if(u & 0x000000f0) {
  74                 u >>= 4;
  75                 r += 4;
  76         }
  77
  78         if(u & 0x0000000c) {
  79                 u >>= 2;
  80                 r += 2;
  81         }
  82
  83         if(u & 0x00000002)
  84                 r++;
  85
  86         return r;
  87 }
  88 #endif
  89
  90 /* Internal helper functions */
  91
  92 int avl_check_balance(avl_node_t *node)
  93 {
  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 void avl_rebalance(avl_tree_t *tree, avl_node_t *node)
 121 {
 122         avl_node_t *child;
 123         avl_node_t *gchild;
 124         avl_node_t *parent;
 125         avl_node_t **superparent;
 126
 127         parent = node;
 128
 129         while(node) {
 130                 parent = node->parent;
 131
 132                 superparent =
 133                         parent ? node ==
 134                         parent->left ? &parent->left : &parent->right : &tree->root;
 135
 136                 switch (avl_check_balance(node)) {
 137                         case -1:
 138                                 child = node->left;
 139 #ifdef AVL_DEPTH
 140                                 if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
 141 #else
 142                                 if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
 143 #endif
 144                                         node->left = child->right;
 145                                         if(node->left)
 146                                                 node->left->parent = node;
 147
 148                                         child->right = node;
 149                                         node->parent = child;
 150                                         *superparent = child;
 151                                         child->parent = parent;
 152 #ifdef AVL_COUNT
 153                                         node->count = AVL_CALC_COUNT(node);
 154                                         child->count = AVL_CALC_COUNT(child);
 155 #endif
 156 #ifdef AVL_DEPTH
 157                                         node->depth = AVL_CALC_DEPTH(node);
 158                                         child->depth = AVL_CALC_DEPTH(child);
 159 #endif
 160                                 } else {
 161                                         gchild = child->right;
 162                                         node->left = gchild->right;
 163
 164                                         if(node->left)
 165                                                 node->left->parent = node;
 166                                         child->right = gchild->left;
 167
 168                                         if(child->right)
 169                                                 child->right->parent = child;
 170                                         gchild->right = node;
 171
 172                                         if(gchild->right)
 173                                                 gchild->right->parent = gchild;
 174                                         gchild->left = child;
 175
 176                                         if(gchild->left)
 177                                                 gchild->left->parent = gchild;
 178                                         *superparent = gchild;
 179
 180                                         gchild->parent = parent;
 181 #ifdef AVL_COUNT
 182                                         node->count = AVL_CALC_COUNT(node);
 183                                         child->count = AVL_CALC_COUNT(child);
 184                                         gchild->count = AVL_CALC_COUNT(gchild);
 185 #endif
 186 #ifdef AVL_DEPTH
 187                                         node->depth = AVL_CALC_DEPTH(node);
 188                                         child->depth = AVL_CALC_DEPTH(child);
 189                                         gchild->depth = AVL_CALC_DEPTH(gchild);
 190 #endif
 191                                 }
 192                                 break;
 193
 194                         case 1:
 195                                 child = node->right;
 196 #ifdef AVL_DEPTH
 197                                 if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
 198 #else
 199                                 if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
 200 #endif
 201                                         node->right = child->left;
 202                                         if(node->right)
 203                                                 node->right->parent = node;
 204                                         child->left = node;
 205                                         node->parent = child;
 206                                         *superparent = child;
 207                                         child->parent = parent;
 208 #ifdef AVL_COUNT
 209                                         node->count = AVL_CALC_COUNT(node);
 210                                         child->count = AVL_CALC_COUNT(child);
 211 #endif
 212 #ifdef AVL_DEPTH
 213                                         node->depth = AVL_CALC_DEPTH(node);
 214                                         child->depth = AVL_CALC_DEPTH(child);
 215 #endif
 216                                 } else {
 217                                         gchild = child->left;
 218                                         node->right = gchild->left;
 219
 220                                         if(node->right)
 221                                                 node->right->parent = node;
 222                                         child->left = gchild->right;
 223
 224                                         if(child->left)
 225                                                 child->left->parent = child;
 226                                         gchild->left = node;
 227
 228                                         if(gchild->left)
 229                                                 gchild->left->parent = gchild;
 230                                         gchild->right = child;
 231
 232                                         if(gchild->right)
 233                                                 gchild->right->parent = gchild;
 234
 235                                         *superparent = gchild;
 236                                         gchild->parent = parent;
 237 #ifdef AVL_COUNT
 238                                         node->count = AVL_CALC_COUNT(node);
 239                                         child->count = AVL_CALC_COUNT(child);
 240                                         gchild->count = AVL_CALC_COUNT(gchild);
 241 #endif
 242 #ifdef AVL_DEPTH
 243                                         node->depth = AVL_CALC_DEPTH(node);
 244                                         child->depth = AVL_CALC_DEPTH(child);
 245                                         gchild->depth = AVL_CALC_DEPTH(gchild);
 246 #endif
 247                                 }
 248                                 break;
 249
 250                         default:
 251 #ifdef AVL_COUNT
 252                                 node->count = AVL_CALC_COUNT(node);
 253 #endif
 254 #ifdef AVL_DEPTH
 255                                 node->depth = AVL_CALC_DEPTH(node);
 256 #endif
 257                 }
 258                 node = parent;
 259         }
 260 }
 261
 262 /* (De)constructors */
 263
 264 avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete)
 265 {
 266         avl_tree_t *tree;
 267
 268         tree = xmalloc_and_zero(sizeof(avl_tree_t));
 269         tree->compare = compare;
 270         tree->delete = delete;
 271
 272         return tree;
 273 }
 274
 275 void avl_free_tree(avl_tree_t *tree)
 276 {
 277         free(tree);
 278 }
 279
 280 avl_node_t *avl_alloc_node(void)
 281 {
 282         return (avl_node_t *)xmalloc_and_zero(sizeof(avl_node_t));
 283 }
 284
 285 void avl_free_node(avl_tree_t *tree, avl_node_t *node)
 286 {
 287         if(node->data && tree->delete)
 288                 tree->delete(node->data);
 289
 290         free(node);
 291 }
 292
 293 /* Searching */
 294
 295 void *avl_search(const avl_tree_t *tree, const void *data)
 296 {
 297         avl_node_t *node;
 298
 299         node = avl_search_node(tree, data);
 300
 301         return node ? node->data : NULL;
 302 }
 303
 304 void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result)
 305 {
 306         avl_node_t *node;
 307
 308         node = avl_search_closest_node(tree, data, result);
 309
 310         return node ? node->data : NULL;
 311 }
 312
 313 void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data)
 314 {
 315         avl_node_t *node;
 316
 317         node = avl_search_closest_smaller_node(tree, data);
 318
 319         return node ? node->data : NULL;
 320 }
 321
 322 void *avl_search_closest_greater(const avl_tree_t *tree, const void *data)
 323 {
 324         avl_node_t *node;
 325
 326         node = avl_search_closest_greater_node(tree, data);
 327
 328         return node ? node->data : NULL;
 329 }
 330
 331 avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data)
 332 {
 333         avl_node_t *node;
 334         int result;
 335
 336         node = avl_search_closest_node(tree, data, &result);
 337
 338         return result ? NULL : node;
 339 }
 340
 341 avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
 342                                                                         int *result)
 343 {
 344         avl_node_t *node;
 345         int c;
 346
 347         node = tree->root;
 348
 349         if(!node) {
 350                 if(result)
 351                         *result = 0;
 352                 return NULL;
 353         }
 354
 355         for(;;) {
 356                 c = tree->compare(data, node->data);
 357
 358                 if(c < 0) {
 359                         if(node->left)
 360                                 node = node->left;
 361                         else {
 362                                 if(result)
 363                                         *result = -1;
 364                                 break;
 365                         }
 366                 } else if(c > 0) {
 367                         if(node->right)
 368                                 node = node->right;
 369                         else {
 370                                 if(result)
 371                                         *result = 1;
 372                                 break;
 373                         }
 374                 } else {
 375                         if(result)
 376                                 *result = 0;
 377                         break;
 378                 }
 379         }
 380
 381         return node;
 382 }
 383
 384 avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree,
 385                                                                                         const void *data)
 386 {
 387         avl_node_t *node;
 388         int result;
 389
 390         node = avl_search_closest_node(tree, data, &result);
 391
 392         if(result < 0)
 393                 node = node->prev;
 394
 395         return node;
 396 }
 397
 398 avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree,
 399                                                                                         const void *data)
 400 {
 401         avl_node_t *node;
 402         int result;
 403
 404         node = avl_search_closest_node(tree, data, &result);
 405
 406         if(result > 0)
 407                 node = node->next;
 408
 409         return node;
 410 }
 411
 412 /* Insertion and deletion */
 413
 414 avl_node_t *avl_insert(avl_tree_t *tree, void *data)
 415 {
 416         avl_node_t *closest, *new;
 417         int result;
 418
 419         if(!tree->root) {
 420                 new = avl_alloc_node();
 421                 new->data = data;
 422                 avl_insert_top(tree, new);
 423         } else {
 424                 closest = avl_search_closest_node(tree, data, &result);
 425
 426                 switch (result) {
 427                         case -1:
 428                                 new = avl_alloc_node();
 429                                 new->data = data;
 430                                 avl_insert_before(tree, closest, new);
 431                                 break;
 432
 433                         case 1:
 434                                 new = avl_alloc_node();
 435                                 new->data = data;
 436                                 avl_insert_after(tree, closest, new);
 437                                 break;
 438
 439                         default:
 440                                 return NULL;
 441                 }
 442         }
 443
 444 #ifdef AVL_COUNT
 445         new->count = 1;
 446 #endif
 447 #ifdef AVL_DEPTH
 448         new->depth = 1;
 449 #endif
 450
 451         return new;
 452 }
 453
 454 avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
 455 {
 456         avl_node_t *closest;
 457         int result;
 458
 459         if(!tree->root)
 460                 avl_insert_top(tree, node);
 461         else {
 462                 closest = avl_search_closest_node(tree, node->data, &result);
 463
 464                 switch (result) {
 465                         case -1:
 466                                 avl_insert_before(tree, closest, node);
 467                                 break;
 468
 469                         case 1:
 470                                 avl_insert_after(tree, closest, node);
 471                                 break;
 472
 473                         case 0:
 474                                 return NULL;
 475                 }
 476         }
 477
 478 #ifdef AVL_COUNT
 479         node->count = 1;
 480 #endif
 481 #ifdef AVL_DEPTH
 482         node->depth = 1;
 483 #endif
 484
 485         return node;
 486 }
 487
 488 void avl_insert_top(avl_tree_t *tree, avl_node_t *node)
 489 {
 490         node->prev = node->next = node->parent = NULL;
 491         tree->head = tree->tail = tree->root = node;
 492 }
 493
 494 void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
 495                                            avl_node_t *node)
 496 {
 497         if(!before) {
 498                 if(tree->tail)
 499                         avl_insert_after(tree, tree->tail, node);
 500                 else
 501                         avl_insert_top(tree, node);
 502                 return;
 503         }
 504
 505         node->next = before;
 506         node->parent = before;
 507         node->prev = before->prev;
 508
 509         if(before->left) {
 510                 avl_insert_after(tree, before->prev, node);
 511                 return;
 512         }
 513
 514         if(before->prev)
 515                 before->prev->next = node;
 516         else
 517                 tree->head = node;
 518
 519         before->prev = node;
 520         before->left = node;
 521
 522         avl_rebalance(tree, before);
 523 }
 524
 525 void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
 526 {
 527         if(!after) {
 528                 if(tree->head)
 529                         avl_insert_before(tree, tree->head, node);
 530                 else
 531                         avl_insert_top(tree, node);
 532                 return;
 533         }
 534
 535         if(after->right) {
 536                 avl_insert_before(tree, after->next, node);
 537                 return;
 538         }
 539
 540         node->prev = after;
 541         node->parent = after;
 542         node->next = after->next;
 543
 544         if(after->next)
 545                 after->next->prev = node;
 546         else
 547                 tree->tail = node;
 548
 549         after->next = node;
 550         after->right = node;
 551
 552         avl_rebalance(tree, after);
 553 }
 554
 555 avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
 556 {
 557         avl_node_t *node;
 558
 559         node = avl_search_node(tree, data);
 560
 561         if(node)
 562                 avl_unlink_node(tree, node);
 563
 564         return node;
 565 }
 566
 567 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
 568 {
 569         avl_node_t *parent;
 570         avl_node_t **superparent;
 571         avl_node_t *subst, *left, *right;
 572         avl_node_t *balnode;
 573
 574         if(node->prev)
 575                 node->prev->next = node->next;
 576         else
 577                 tree->head = node->next;
 578         if(node->next)
 579                 node->next->prev = node->prev;
 580         else
 581                 tree->tail = node->prev;
 582
 583         parent = node->parent;
 584
 585         superparent =
 586                 parent ? node ==
 587                 parent->left ? &parent->left : &parent->right : &tree->root;
 588
 589         left = node->left;
 590         right = node->right;
 591         if(!left) {
 592                 *superparent = right;
 593
 594                 if(right)
 595                         right->parent = parent;
 596
 597                 balnode = parent;
 598         } else if(!right) {
 599                 *superparent = left;
 600                 left->parent = parent;
 601                 balnode = parent;
 602         } else {
 603                 subst = node->prev;
 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->root; 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(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(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(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(avl_tree_t *tree)
 737 {
 738         return AVL_NODE_DEPTH(tree->root);
 739 }
 740 #endif