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