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