lib/avl_tree.c

   1 /*
   2     avl_tree.c -- avl_ tree and linked list convenience
   3     Copyright (C) 1998 Michael H. Buselli
   4                   2000 Ivo Timmermans <itimmermans@bigfoot.com>,
   5                   2000 Guus Sliepen <guus@sliepen.warande.net>
   6                   2000 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.2 2001/01/06 18:21:17 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 *node;
 410
 411   node = avl_alloc_node();
 412   node->data = data;
 413
 414   return avl_insert_node(tree, node);
 415 }
 416
 417 avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
 418 {
 419   avl_node_t *closest;
 420   int result;
 421
 422   if (!tree->root)
 423     avl_insert_top(tree, node);
 424   else
 425   {
 426     closest = avl_search_closest_node(tree, node->data, &result);
 427     switch(result)
 428     {
 429       case -1:
 430         avl_insert_before(tree, closest, node);
 431         break;
 432       case 1:
 433         avl_insert_after(tree, closest, node);
 434         break;
 435       case 0:
 436         return closest;
 437     }
 438   }
 439
 440 #ifdef AVL_COUNT
 441   node->count = 1;
 442 #endif
 443 #ifdef AVL_DEPTH
 444   node->depth = 1;
 445 #endif
 446
 447   return node;
 448 }
 449
 450 void avl_insert_top(avl_tree_t *tree, avl_node_t *node)
 451 {
 452   node->prev = node->next = node->parent = NULL;
 453   tree->head = tree->tail = tree->root = node;
 454 }
 455
 456 void avl_insert_before(avl_tree_t *tree, avl_node_t *before, avl_node_t *node)
 457 {
 458   if (!before)
 459     return tree->tail ? avl_insert_after(tree, tree->tail, node) : avl_insert_top(tree, node);
 460
 461   node->next = before;
 462   node->parent = before;
 463   node->prev = before->prev;
 464
 465   if (before->prev)
 466     before->prev->next = node;
 467   else
 468     tree->head = node;
 469
 470   before->prev = node;
 471   before->left = node;
 472
 473   avl_rebalance(tree, before->parent);
 474 }
 475
 476 void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
 477 {
 478   if (!after)
 479     return tree->head ? avl_insert_before(tree, tree->head, node) : avl_insert_top(tree, node);
 480
 481   node->prev = after;
 482   node->parent = after;
 483   node->next = after->next;
 484
 485   if (after->next)
 486     after->next->prev = node;
 487   else
 488     tree->tail = node;
 489
 490   after->next = node;
 491   after->right = node;
 492
 493   avl_rebalance(tree, after->parent);
 494 }
 495
 496 avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
 497 {
 498   avl_node_t *node;
 499
 500   node = avl_search_node(tree, data);
 501
 502   if(node)
 503     avl_unlink_node(tree, node);
 504
 505   return node;
 506 }
 507
 508 void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
 509 {
 510   avl_node_t *parent;
 511   avl_node_t **superparent;
 512   avl_node_t *subst, *left, *right;
 513   avl_node_t *balnode;
 514
 515   if (node->prev)
 516     node->prev->next = node->next;
 517   else
 518     tree->head = node->next;
 519   if (node->next)
 520     node->next->prev = node->prev;
 521   else
 522     tree->tail = node->prev;
 523
 524   parent = node->parent;
 525
 526   superparent = parent ? node == parent->left ? &parent->left : &parent->right : &tree->root;
 527
 528   left = node->left;
 529   right = node->right;
 530   if (!left)
 531   {
 532     *superparent = right;
 533     if (right)
 534       right->parent = parent;
 535     balnode = parent;
 536   } else if (!right)
 537   {
 538     *superparent = left;
 539     left->parent = parent;
 540     balnode = parent;
 541   } else
 542   {
 543     subst = node->prev;
 544     if (subst == left)
 545     {
 546       balnode = subst;
 547     } else
 548     {
 549       balnode = subst->parent;
 550       balnode->right = subst->left;
 551       if (balnode->right)
 552         balnode->right->parent = balnode;
 553       subst->left = left;
 554       left->parent = subst;
 555     }
 556     subst->right = right;
 557     subst->parent = parent;
 558     right->parent = subst;
 559     *superparent = subst;
 560   }
 561
 562   avl_rebalance(tree, balnode);
 563 }
 564
 565 void avl_delete_node(avl_tree_t *tree, avl_node_t *node)
 566 {
 567   avl_unlink_node(tree, node);
 568   avl_free_node(tree, node);
 569 }
 570
 571 void avl_delete(avl_tree_t *tree, void *data)
 572 {
 573   avl_node_t *node;
 574
 575   node = avl_search_node(tree, data);
 576
 577   if (node)
 578     avl_delete_node(tree, node);
 579 }
 580
 581 /* Fast tree cleanup */
 582
 583 void avl_delete_tree(avl_tree_t *tree)
 584 {
 585   avl_node_t *node, *next;
 586
 587   for(node = tree->root; node; node = next)
 588   {
 589     next = node->next;
 590     avl_free_node(tree, node);
 591   }
 592
 593   avl_free_tree(tree);
 594 }
 595
 596 /* Tree walking */
 597
 598 void avl_foreach(avl_tree_t *tree, avl_action_t action)
 599 {
 600   avl_node_t *node, *next;
 601
 602   for(node = tree->head; node; node = next)
 603     {
 604       next = node->next;
 605       action(node->data);
 606     }
 607 }
 608
 609 void avl_foreach_node(avl_tree_t *tree, avl_action_t action)
 610 {
 611   avl_node_t *node, *next;
 612
 613   for(node = tree->head; node; node = next)
 614     {
 615       next = node->next;
 616       action(node);
 617     }
 618 }
 619
 620 /* Indexing */
 621
 622 #ifdef AVL_COUNT
 623 unsigned int avl_count(avl_tree_t *tree)
 624 {
 625   return AVL_NODE_COUNT(tree->root);
 626 }
 627
 628 avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index)
 629 {
 630   avl_node_t *node;
 631   unsigned int c;
 632
 633   node = tree->root;
 634
 635   while (node)
 636   {
 637     c = AVL_L_COUNT(node);
 638
 639     if (index < c)
 640     {
 641       node = node->left;
 642     } else if (index > c)
 643     {
 644       node = node->right;
 645       index -= c + 1;
 646     } else
 647     {
 648       return node;
 649     }
 650   }
 651
 652   return NULL;
 653 }
 654
 655 unsigned int avl_index(const avl_node_t *node)
 656 {
 657   avl_node_t *next;
 658   unsigned int index;
 659
 660   index = AVL_L_COUNT(node);
 661
 662   while ((next = node->parent))
 663   {
 664     if (node == next->right)
 665       index += AVL_L_COUNT(next) + 1;
 666     node = next;
 667   }
 668
 669   return index;
 670 }
 671 #endif
 672 #ifdef AVL_DEPTH
 673 unsigned int avl_depth(avl_tree_t *tree)
 674 {
 675   return AVL_NODE_DEPTH(tree->root);
 676 }
 677 #endif