src/avl.c

   1 /* libavl - manipulates AVL trees.
   2    Copyright (C) 1998-9, 2000 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  17    02111-1307, USA.
  18
  19    The author may be contacted at <pfaffben@pilot.msu.edu> on the
  20    Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
  21    through more mundane means. */
  22
  23 /* This is file avl.c in libavl. */
  24
  25 #if HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28 #if PSPP
  29 #include "pool.h"
  30 #define HAVE_XMALLOC 1
  31 #endif
  32 #if SELF_TEST
  33 #include <limits.h>
  34 #include <time.h>
  35 #endif
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <assert.h>
  39 #include "avl.h"
  40
  41 #if !PSPP && !__GCC__
  42 #define inline
  43 #endif
  44
  45 #if !PSPP
  46 #if __GNUC__ >= 2
  47 #define unused __attribute__ ((unused))
  48 #else
  49 #define unused
  50 #endif
  51 #endif
  52
  53 #ifdef HAVE_XMALLOC
  54 void *xmalloc (size_t);
  55 #else /* !HAVE_XMALLOC */
  56 /* Allocates SIZE bytes of space using malloc().  Aborts if out of
  57    memory. */
  58 static void *
  59 xmalloc (size_t size)
  60 {
  61   void *vp;
  62
  63   if (size == 0)
  64     return NULL;
  65   vp = malloc (size);
  66
  67   assert (vp != NULL);
  68   if (vp == NULL)
  69     {
  70       fprintf (stderr, "virtual memory exhausted\n");
  71       exit (EXIT_FAILURE);
  72     }
  73   return vp;
  74 }
  75 #endif /* !HAVE_XMALLOC */
  76
  77 /* Creates an AVL tree in POOL (which can be NULL).  POOL is owned by
  78    the caller, not by the AVL tree.  CMP is a order function for the
  79    data to be stored in the tree.  PARAM is arbitrary data that
  80    becomes an argument to the comparison function. */
  81 avl_tree *
  82 avl_create (MAYBE_POOL avl_comparison_func cmp, void *param)
  83 {
  84   avl_tree *tree;
  85
  86   assert (cmp != NULL);
  87 #if PSPP
  88   if (pool)
  89     tree = pool_alloc (pool, sizeof *tree);
  90   else
  91 #endif
  92     tree = xmalloc (sizeof *tree);
  93
  94 #if PSPP
  95   tree->pool = pool;
  96 #endif
  97   tree->root.link[0] = NULL;
  98   tree->root.link[1] = NULL;
  99   tree->cmp = cmp;
 100   tree->count = 0;
 101   tree->param = param;
 102
 103   return tree;
 104 }
 105
 106 /* Destroy tree TREE.  Function FREE_FUNC is called for every node in
 107    the tree as it is destroyed.
 108
 109    No effect if the tree has an pool owner and free_func is NULL.
 110    The caller owns the pool and must destroy it itself.
 111
 112    Do not attempt to reuse the tree after it has been freed.  Create a
 113    new one.  */
 114 void
 115 avl_destroy (avl_tree *tree, avl_node_func free_func)
 116 {
 117   assert (tree != NULL);
 118
 119 #if PSPP
 120   if (free_func || tree->pool == NULL)
 121 #endif
 122     {
 123       /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
 124          (postorder traversal). */
 125
 126       /* T1. */
 127       avl_node *an[AVL_MAX_HEIGHT];     /* Stack A: nodes. */
 128       char ab[AVL_MAX_HEIGHT];          /* Stack A: bits. */
 129       int ap = 0;                       /* Stack A: height. */
 130       avl_node *p = tree->root.link[0];
 131
 132       for (;;)
 133         {
 134           /* T2. */
 135           while (p != NULL)
 136             {
 137               /* T3. */
 138               ab[ap] = 0;
 139               an[ap++] = p;
 140               p = p->link[0];
 141             }
 142
 143           /* T4. */
 144           for (;;)
 145             {
 146               if (ap == 0)
 147                 goto done;
 148
 149               p = an[--ap];
 150               if (ab[ap] == 0)
 151                 {
 152                   ab[ap++] = 1;
 153                   p = p->link[1];
 154                   break;
 155                 }
 156
 157               if (free_func)
 158                 free_func (p->data, tree->param);
 159 #if PSPP
 160               if (tree->pool == NULL)
 161 #endif
 162                 free (p);
 163             }
 164         }
 165     }
 166
 167  done:
 168 #if PSPP
 169   if (tree->pool == NULL)
 170 #endif
 171     free (tree);
 172 }
 173
 174 /* avl_destroy() with FREE_FUNC hardcoded as free(). */
 175 void
 176 avl_free (avl_tree *tree)
 177 {
 178   avl_destroy (tree, (avl_node_func) free);
 179 }
 180
 181 /* Return the number of nodes in TREE. */
 182 int
 183 avl_count (const avl_tree *tree)
 184 {
 185   assert (tree != NULL);
 186   return tree->count;
 187 }
 188
 189 /* Allocates room for a new avl_node in POOL, or using xmalloc() if
 190    POOL is NULL. */
 191 #if PSPP
 192 static inline avl_node *
 193 new_node (struct pool *pool)
 194 {
 195   if (pool != NULL)
 196     return pool_alloc (pool, sizeof (avl_node));
 197   else
 198     return xmalloc (sizeof (avl_node));
 199 }
 200 #else
 201 static inline avl_node *
 202 new_node (void)
 203 {
 204   return xmalloc (sizeof (avl_node));
 205 }
 206
 207 #define new_node(POOL)                          \
 208         new_node ()
 209 #endif
 210
 211 /* Copy the contents of TREE to a new tree in POOL.  If COPY is
 212    non-NULL, then each data item is passed to function COPY, and the
 213    return values are inserted into the new tree; otherwise, the items
 214    are copied verbatim from the old tree to the new tree.  Returns the
 215    new tree. */
 216 avl_tree *
 217 avl_copy (MAYBE_POOL const avl_tree *tree, avl_copy_func copy)
 218 {
 219   /* This is a combination of Knuth's Algorithm 2.3.1C (copying a
 220      binary tree) and Algorithm 2.3.1T as modified by exercise 12
 221      (preorder traversal). */
 222
 223   avl_tree *new_tree;
 224
 225   /* PT1. */
 226   const avl_node *pa[AVL_MAX_HEIGHT];   /* Stack PA: nodes. */
 227   const avl_node **pp = pa;             /* Stack PA: stack pointer. */
 228   const avl_node *p = &tree->root;
 229
 230   /* QT1. */
 231   avl_node *qa[AVL_MAX_HEIGHT]; /* Stack QA: nodes. */
 232   avl_node **qp = qa;           /* Stack QA: stack pointer. */
 233   avl_node *q;
 234
 235   assert (tree != NULL);
 236 #if PSPP
 237   new_tree = avl_create (pool, tree->cmp, tree->param);
 238 #else
 239   new_tree = avl_create (tree->cmp, tree->param);
 240 #endif
 241   new_tree->count = tree->count;
 242   q = &new_tree->root;
 243
 244   for (;;)
 245     {
 246       /* C4. */
 247       if (p->link[0] != NULL)
 248         {
 249           avl_node *r = new_node (pool);
 250           r->link[0] = r->link[1] = NULL;
 251           q->link[0] = r;
 252         }
 253
 254       /* C5: Find preorder successors of P and Q.  */
 255       goto start;
 256       for (;;)
 257         {
 258           /* PT2. */
 259           while (p != NULL)
 260             {
 261               goto escape;
 262             start:
 263               /* PT3. */
 264               *pp++ = p;
 265               *qp++ = q;
 266               p = p->link[0];
 267               q = q->link[0];
 268             }
 269
 270           /* PT4. */
 271           if (pp == pa)
 272             {
 273               assert (qp == qa);
 274               return new_tree;
 275             }
 276
 277           p = *--pp;
 278           q = *--qp;
 279
 280           /* PT5. */
 281           p = p->link[1];
 282           q = q->link[1];
 283         }
 284     escape:
 285
 286       /* C2. */
 287       if (p->link[1])
 288         {
 289           avl_node *r = new_node (pool);
 290           r->link[0] = r->link[1] = NULL;
 291           q->link[1] = r;
 292         }
 293
 294       /* C3. */
 295       q->bal = p->bal;
 296       if (copy == NULL)
 297         q->data = p->data;
 298       else
 299         q->data = copy (p->data, tree->param);
 300     }
 301 }
 302
 303 /* Walk tree TREE in inorder, calling WALK_FUNC at each node.  Passes
 304    PARAM to WALK_FUNC.  */
 305 void
 306 avl_walk (const avl_tree *tree, avl_node_func walk_func, void *param)
 307 {
 308   /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
 309   assert (tree && walk_func);
 310
 311   {
 312     /* T1. */
 313     const avl_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
 314     const avl_node **ap = an;           /* Stack A: stack pointer. */
 315     const avl_node *p = tree->root.link[0];
 316
 317     for (;;)
 318       {
 319         /* T2. */
 320         while (p != NULL)
 321           {
 322             /* T3. */
 323             *ap++ = p;
 324             p = p->link[0];
 325           }
 326
 327         /* T4. */
 328         if (ap == an)
 329           return;
 330         p = *--ap;
 331
 332         /* T5. */
 333         walk_func (p->data, param);
 334         p = p->link[1];
 335       }
 336   }
 337 }
 338
 339 /* Each call to this function for a given TREE and TRAV return the
 340    next item in the tree in inorder.  Initialize the first element of
 341    TRAV (init) to 0 before calling the first time.  Returns NULL when
 342    out of elements.  */
 343 void *
 344 avl_traverse (const avl_tree *tree, avl_traverser *trav)
 345 {
 346   assert (tree && trav);
 347
 348   /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
 349   if (trav->init == 0)
 350     {
 351       /* T1. */
 352       trav->init = 1;
 353       trav->nstack = 0;
 354       trav->p = tree->root.link[0];
 355     }
 356   else
 357     /* T5. */
 358     trav->p = trav->p->link[1];
 359
 360   for (;;)
 361     {
 362       /* T2. */
 363       while (trav->p != NULL)
 364         {
 365           /* T3. */
 366           trav->stack[trav->nstack++] = trav->p;
 367           trav->p = trav->p->link[0];
 368         }
 369
 370       /* T4. */
 371       if (trav->nstack == 0)
 372         {
 373           trav->init = 0;
 374           return NULL;
 375         }
 376       trav->p = trav->stack[--trav->nstack];
 377
 378       /* T5. */
 379       return trav->p->data;
 380     }
 381 }
 382
 383 /* Search TREE for an item matching ITEM.  If found, returns a pointer
 384    to the address of the item.  If none is found, ITEM is inserted
 385    into the tree, and a pointer to the address of ITEM is returned.
 386    In either case, the pointer returned can be changed by the caller,
 387    or the returned data item can be directly edited, but the key data
 388    in the item must not be changed. */
 389 void **
 390 avl_probe (avl_tree *tree, void *item)
 391 {
 392   /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
 393      insertion), but caches results of comparisons.  In empirical
 394      tests this eliminates about 25% of the comparisons seen under
 395      random insertions.  */
 396
 397   /* A1. */
 398   avl_node *t;
 399   avl_node *s, *p, *q, *r;
 400
 401   assert (tree != NULL);
 402   t = &tree->root;
 403   s = p = t->link[0];
 404
 405   if (s == NULL)
 406     {
 407       tree->count++;
 408       assert (tree->count == 1);
 409       q = t->link[0] = new_node (tree->pool);
 410       q->data = item;
 411       q->link[0] = q->link[1] = NULL;
 412       q->bal = 0;
 413       return &q->data;
 414     }
 415
 416   for (;;)
 417     {
 418       /* A2. */
 419       int diff = tree->cmp (item, p->data, tree->param);
 420
 421       /* A3. */
 422       if (diff < 0)
 423         {
 424           p->cache = 0;
 425           q = p->link[0];
 426           if (q == NULL)
 427             {
 428               p->link[0] = q = new_node (tree->pool);
 429               break;
 430             }
 431         }
 432       /* A4. */
 433       else if (diff > 0)
 434         {
 435           p->cache = 1;
 436           q = p->link[1];
 437           if (q == NULL)
 438             {
 439               p->link[1] = q = new_node (tree->pool);
 440               break;
 441             }
 442         }
 443       else
 444         /* A2. */
 445         return &p->data;
 446
 447       /* A3, A4. */
 448       if (q->bal != 0)
 449         t = p, s = q;
 450       p = q;
 451     }
 452
 453   /* A5. */
 454   tree->count++;
 455   q->data = item;
 456   q->link[0] = q->link[1] = NULL;
 457   q->bal = 0;
 458
 459   /* A6. */
 460   r = p = s->link[(int) s->cache];
 461   while (p != q)
 462     {
 463       p->bal = p->cache * 2 - 1;
 464       p = p->link[(int) p->cache];
 465     }
 466
 467   /* A7. */
 468   if (s->cache == 0)
 469     {
 470       /* a = -1. */
 471       if (s->bal == 0)
 472         {
 473           s->bal = -1;
 474           return &q->data;
 475         }
 476       else if (s->bal == +1)
 477         {
 478           s->bal = 0;
 479           return &q->data;
 480         }
 481
 482       assert (s->bal == -1);
 483       if (r->bal == -1)
 484         {
 485           /* A8. */
 486           p = r;
 487           s->link[0] = r->link[1];
 488           r->link[1] = s;
 489           s->bal = r->bal = 0;
 490         }
 491       else
 492         {
 493           /* A9. */
 494           assert (r->bal == +1);
 495           p = r->link[1];
 496           r->link[1] = p->link[0];
 497           p->link[0] = r;
 498           s->link[0] = p->link[1];
 499           p->link[1] = s;
 500           if (p->bal == -1)
 501             s->bal = 1, r->bal = 0;
 502           else if (p->bal == 0)
 503             s->bal = r->bal = 0;
 504           else
 505             {
 506               assert (p->bal == +1);
 507               s->bal = 0, r->bal = -1;
 508             }
 509           p->bal = 0;
 510         }
 511     }
 512   else
 513     {
 514       /* a == +1. */
 515       if (s->bal == 0)
 516         {
 517           s->bal = 1;
 518           return &q->data;
 519         }
 520       else if (s->bal == -1)
 521         {
 522           s->bal = 0;
 523           return &q->data;
 524         }
 525
 526       assert (s->bal == +1);
 527       if (r->bal == +1)
 528         {
 529           /* A8. */
 530           p = r;
 531           s->link[1] = r->link[0];
 532           r->link[0] = s;
 533           s->bal = r->bal = 0;
 534         }
 535       else
 536         {
 537           /* A9. */
 538           assert (r->bal == -1);
 539           p = r->link[0];
 540           r->link[0] = p->link[1];
 541           p->link[1] = r;
 542           s->link[1] = p->link[0];
 543           p->link[0] = s;
 544           if (p->bal == +1)
 545             s->bal = -1, r->bal = 0;
 546           else if (p->bal == 0)
 547             s->bal = r->bal = 0;
 548           else
 549             {
 550               assert (p->bal == -1);
 551               s->bal = 0, r->bal = 1;
 552             }
 553           p->bal = 0;
 554         }
 555     }
 556
 557   /* A10. */
 558   if (t != &tree->root && s == t->link[1])
 559     t->link[1] = p;
 560   else
 561     t->link[0] = p;
 562
 563   return &q->data;
 564 }
 565
 566 /* Search TREE for an item matching ITEM, and return it if found. */
 567 void *
 568 avl_find (const avl_tree *tree, const void *item)
 569 {
 570   const avl_node *p;
 571
 572   assert (tree != NULL);
 573   for (p = tree->root.link[0]; p; )
 574     {
 575       int diff = tree->cmp (item, p->data, tree->param);
 576
 577       if (diff < 0)
 578         p = p->link[0];
 579       else if (diff > 0)
 580         p = p->link[1];
 581       else
 582         return p->data;
 583     }
 584
 585   return NULL;
 586 }
 587
 588 /* Searches AVL tree TREE for an item matching ITEM.  If found, the
 589    item is removed from the tree and the actual item found is returned
 590    to the caller.  If no item matching ITEM exists in the tree,
 591    returns NULL. */
 592 void *
 593 avl_delete (avl_tree *tree, const void *item)
 594 {
 595   /* Uses my Algorithm D, which can be found at
 596      http://www.msu.edu/user/pfaffben/avl.  Algorithm D is based on
 597      Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced
 598      tree search and insertion), as well as the notes on pages 465-466
 599      of Vol. 3. */
 600
 601   /* D1. */
 602   avl_node *pa[AVL_MAX_HEIGHT];         /* Stack P: Nodes. */
 603   char a[AVL_MAX_HEIGHT];               /* Stack P: Bits. */
 604   int k = 1;                            /* Stack P: Pointer. */
 605
 606   avl_node **q;
 607   avl_node *p;
 608
 609   assert (tree != NULL);
 610
 611   a[0] = 0;
 612   pa[0] = &tree->root;
 613   p = tree->root.link[0];
 614   for (;;)
 615     {
 616       /* D2. */
 617       int diff;
 618
 619       if (p == NULL)
 620         return NULL;
 621
 622       diff = tree->cmp (item, p->data, tree->param);
 623       if (diff == 0)
 624         break;
 625
 626       /* D3, D4. */
 627       pa[k] = p;
 628       if (diff < 0)
 629         {
 630           p = p->link[0];
 631           a[k] = 0;
 632         }
 633       else if (diff > 0)
 634         {
 635           p = p->link[1];
 636           a[k] = 1;
 637         }
 638       k++;
 639     }
 640   tree->count--;
 641
 642   item = p->data;
 643
 644   /* D5. */
 645   q = &pa[k - 1]->link[(int) a[k - 1]];
 646   if (p->link[1] == NULL)
 647     {
 648       *q = p->link[0];
 649       if (*q)
 650         (*q)->bal = 0;
 651     }
 652   else
 653     {
 654       /* D6. */
 655       avl_node *r = p->link[1];
 656       if (r->link[0] == NULL)
 657         {
 658           r->link[0] = p->link[0];
 659           *q = r;
 660           r->bal = p->bal;
 661           a[k] = 1;
 662           pa[k++] = r;
 663         }
 664       else
 665         {
 666           /* D7. */
 667           avl_node *s = r->link[0];
 668           int l = k++;
 669
 670           a[k] = 0;
 671           pa[k++] = r;
 672
 673           /* D8. */
 674           while (s->link[0] != NULL)
 675             {
 676               r = s;
 677               s = r->link[0];
 678               a[k] = 0;
 679               pa[k++] = r;
 680             }
 681
 682           /* D9. */
 683           a[l] = 1;
 684           pa[l] = s;
 685           s->link[0] = p->link[0];
 686           r->link[0] = s->link[1];
 687           s->link[1] = p->link[1];
 688           s->bal = p->bal;
 689           *q = s;
 690         }
 691     }
 692
 693 #if PSPP
 694   if (tree->pool == NULL)
 695 #endif
 696     free (p);
 697
 698   assert (k > 0);
 699   /* D10. */
 700   while (--k)
 701     {
 702       avl_node *s = pa[k], *r;
 703
 704       if (a[k] == 0)
 705         {
 706           /* D10. */
 707           if (s->bal == -1)
 708             {
 709               s->bal = 0;
 710               continue;
 711             }
 712           else if (s->bal == 0)
 713             {
 714               s->bal = 1;
 715               break;
 716             }
 717
 718           assert (s->bal == +1);
 719           r = s->link[1];
 720
 721           assert (r != NULL);
 722           if (r->bal == 0)
 723             {
 724               /* D11. */
 725               s->link[1] = r->link[0];
 726               r->link[0] = s;
 727               r->bal = -1;
 728               pa[k - 1]->link[(int) a[k - 1]] = r;
 729               break;
 730             }
 731           else if (r->bal == +1)
 732             {
 733               /* D12. */
 734               s->link[1] = r->link[0];
 735               r->link[0] = s;
 736               s->bal = r->bal = 0;
 737               pa[k - 1]->link[(int) a[k - 1]] = r;
 738             }
 739           else
 740             {
 741               /* D13. */
 742               assert (r->bal == -1);
 743               p = r->link[0];
 744               r->link[0] = p->link[1];
 745               p->link[1] = r;
 746               s->link[1] = p->link[0];
 747               p->link[0] = s;
 748               if (p->bal == +1)
 749                 s->bal = -1, r->bal = 0;
 750               else if (p->bal == 0)
 751                 s->bal = r->bal = 0;
 752               else
 753                 {
 754                   assert (p->bal == -1);
 755                   s->bal = 0, r->bal = +1;
 756                 }
 757               p->bal = 0;
 758               pa[k - 1]->link[(int) a[k - 1]] = p;
 759             }
 760         }
 761       else
 762         {
 763           assert (a[k] == 1);
 764
 765           /* D10. */
 766           if (s->bal == +1)
 767             {
 768               s->bal = 0;
 769               continue;
 770             }
 771           else if (s->bal == 0)
 772             {
 773               s->bal = -1;
 774               break;
 775             }
 776
 777           assert (s->bal == -1);
 778           r = s->link[0];
 779
 780           if (r == NULL || r->bal == 0)
 781             {
 782               /* D11. */
 783               s->link[0] = r->link[1];
 784               r->link[1] = s;
 785               r->bal = 1;
 786               pa[k - 1]->link[(int) a[k - 1]] = r;
 787               break;
 788             }
 789           else if (r->bal == -1)
 790             {
 791               /* D12. */
 792               s->link[0] = r->link[1];
 793               r->link[1] = s;
 794               s->bal = r->bal = 0;
 795               pa[k - 1]->link[(int) a[k - 1]] = r;
 796             }
 797           else if (r->bal == +1)
 798             {
 799               /* D13. */
 800               p = r->link[1];
 801               r->link[1] = p->link[0];
 802               p->link[0] = r;
 803               s->link[0] = p->link[1];
 804               p->link[1] = s;
 805               if (p->bal == -1)
 806                 s->bal = 1, r->bal = 0;
 807               else if (p->bal == 0)
 808                 s->bal = r->bal = 0;
 809               else
 810                 {
 811                   assert (p->bal == 1);
 812                   s->bal = 0, r->bal = -1;
 813                 }
 814               p->bal = 0;
 815               pa[k - 1]->link[(int) a[k - 1]] = p;
 816             }
 817         }
 818     }
 819
 820   return (void *) item;
 821 }
 822
 823 /* Inserts ITEM into TREE.  Returns NULL if the item was inserted,
 824    otherwise a pointer to the duplicate item. */
 825 void *
 826 avl_insert (avl_tree *tree, void *item)
 827 {
 828   void **p;
 829
 830   assert (tree != NULL);
 831
 832   p = avl_probe (tree, item);
 833   return (*p == item) ? NULL : *p;
 834 }
 835
 836 /* If ITEM does not exist in TREE, inserts it and returns NULL.  If a
 837    matching item does exist, it is replaced by ITEM and the item
 838    replaced is returned.  The caller is responsible for freeing the
 839    item returned. */
 840 void *
 841 avl_replace (avl_tree *tree, void *item)
 842 {
 843   void **p;
 844
 845   assert (tree != NULL);
 846
 847   p = avl_probe (tree, item);
 848   if (*p == item)
 849     return NULL;
 850   else
 851     {
 852       void *r = *p;
 853       *p = item;
 854       return r;
 855     }
 856 }
 857
 858 /* Delete ITEM from TREE when you know that ITEM must be in TREE.  For
 859    debugging purposes. */
 860 void *
 861 (avl_force_delete) (avl_tree *tree, void *item)
 862 {
 863   void *found = avl_delete (tree, item);
 864   assert (found != NULL);
 865   return found;
 866 }
 867 \f
 868 #if SELF_TEST
 869
 870 /* Used to flag delayed aborting. */
 871 int done = 0;
 872
 873 /* Print the structure of node NODE of an avl tree, which is LEVEL
 874    levels from the top of the tree.  Uses different delimiters to
 875    visually distinguish levels. */
 876 void
 877 print_structure (avl_node *node, int level)
 878 {
 879   char lc[] = "([{`/";
 880   char rc[] = ")]}'\\";
 881
 882   assert (level <= 10);
 883
 884   if (node == NULL)
 885     {
 886       printf (" nil");
 887       return;
 888     }
 889   printf (" %c%d", lc[level % 5], (int) node->data);
 890   if (node->link[0] || node->link[1])
 891     print_structure (node->link[0], level + 1);
 892   if (node->link[1])
 893     print_structure (node->link[1], level + 1);
 894   printf ("%c", rc[level % 5]);
 895 }
 896
 897 /* Compare two integers A and B and return a strcmp()-type result. */
 898 int
 899 compare_ints (const void *a, const void *b, void *param unused)
 900 {
 901   return ((int) a) - ((int) b);
 902 }
 903
 904 /* Print the value of integer A. */
 905 void
 906 print_int (void *a, void *param unused)
 907 {
 908   printf (" %d", (int) a);
 909 }
 910
 911 /* Linearly print contents of TREE. */
 912 void
 913 print_contents (avl_tree *tree)
 914 {
 915   avl_walk (tree, print_int, NULL);
 916   printf ("\n");
 917 }
 918
 919 /* Examine NODE in a avl tree.  *COUNT is increased by the number of
 920    nodes in the tree, including the current one.  If the node is the
 921    root of the tree, PARENT should be INT_MIN, otherwise it should be
 922    the parent node value.  DIR is the direction that the current node
 923    is linked from the parent: -1 for left child, +1 for right child;
 924    it is not used if PARENT is INT_MIN.  Returns the height of the
 925    tree rooted at NODE. */
 926 int
 927 recurse_tree (avl_node *node, int *count, int parent, int dir)
 928 {
 929   if (node)
 930     {
 931       int d = (int) node->data;
 932       int nl = node->link[0] ? recurse_tree (node->link[0], count, d, -1) : 0;
 933       int nr = node->link[1] ? recurse_tree (node->link[1], count, d, 1) : 0;
 934       (*count)++;
 935
 936       if (nr - nl != node->bal)
 937         {
 938           printf (" Node %d is unbalanced: right height=%d, left height=%d, "
 939                 "difference=%d, but balance factor=%d.\n",
 940                   d, nr, nl, nr - nl, node->bal);
 941           done = 1;
 942         }
 943
 944       if (parent != INT_MIN)
 945         {
 946           assert (dir == -1 || dir == +1);
 947           if (dir == -1 && d > parent)
 948             {
 949               printf (" Node %d is smaller than its left child %d.\n",
 950                       parent, d);
 951               done = 1;
 952             }
 953           else if (dir == +1 && d < parent)
 954             {
 955               printf (" Node %d is larger than its right child %d.\n",
 956                       parent, d);
 957               done = 1;
 958             }
 959         }
 960       assert (node->bal >= -1 && node->bal <= 1);
 961       return 1 + (nl > nr ? nl : nr);
 962     }
 963   else return 0;
 964 }
 965
 966 /* Check that everything about TREE is kosher. */
 967 void
 968 verify_tree (avl_tree *tree)
 969 {
 970   int count = 0;
 971   recurse_tree (tree->root.link[0], &count, INT_MIN, 0);
 972   if (count != tree->count)
 973     {
 974       printf (" Tree has %d nodes, but tree count is %d.\n",
 975               count, tree->count);
 976       done = 1;
 977     }
 978   if (done)
 979     abort ();
 980 }
 981
 982 /* Arrange the N elements of ARRAY in random order. */
 983 void
 984 shuffle (int *array, int n)
 985 {
 986   int i;
 987
 988   for (i = 0; i < n; i++)
 989     {
 990       int j = i + rand () % (n - i);
 991       int t = array[j];
 992       array[j] = array[i];
 993       array[i] = t;
 994     }
 995 }
 996
 997 /* Compares avl trees rooted at A and B, making sure that they are
 998    identical. */
 999 void
1000 compare_trees (avl_node *a, avl_node *b)
1001 {
1002   if (a == NULL || b == NULL)
1003     {
1004       assert (a == NULL && b == NULL);
1005       return;
1006     }
1007   if (a->data != b->data || a->bal != b->bal
1008       || ((a->link[0] != NULL) ^ (b->link[0] != NULL))
1009       || ((a->link[1] != NULL) ^ (b->link[1] != NULL)))
1010     {
1011       printf (" Copied nodes differ: %d b=%d a->bal=%d b->bal=%d a:",
1012               (int) a->data, (int) b->data, a->bal, b->bal);
1013       if (a->link[0])
1014         printf ("l");
1015       if (a->link[1])
1016         printf ("r");
1017       printf (" b:");
1018       if (b->link[0])
1019         printf ("l");
1020       if (b->link[1])
1021         printf ("r");
1022       printf ("\n");
1023       abort ();
1024     }
1025   if (a->link[0] != NULL)
1026     compare_trees (a->link[0], b->link[0]);
1027   if (a->link[1] != NULL)
1028     compare_trees (a->link[1], b->link[1]);
1029 }
1030
1031 /* Simple stress test procedure for the AVL tree routines.  Does the
1032    following:
1033
1034    * Generate a random number seed.  By default this is generated from
1035    the current time.  You can also pass a seed value on the command
1036    line if you want to test the same case.  The seed value is
1037    displayed.
1038
1039    * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
1040    into it, in random order.  Verify the tree structure after each
1041    insertion.
1042
1043    * Remove each integer from the tree, in a different random order.
1044    After each deletion, verify the tree structure; also, make a copy
1045    of the tree into a new tree, verify the copy and compare it to the
1046    original, then destroy the copy.
1047
1048    * Destroy the tree, increment the random seed value, and start over.
1049
1050    If you make any modifications to the avl tree routines, then you
1051    might want to insert some calls to print_structure() at strategic
1052    places in order to be able to see what's really going on.  Also,
1053    memory debuggers like Checker or Purify are very handy. */
1054 #define TREE_SIZE 1024
1055 #define N_ITERATIONS 16
1056 int
1057 main (int argc, char **argv)
1058 {
1059   int array[TREE_SIZE];
1060   int seed;
1061   int iteration;
1062
1063   if (argc == 2)
1064     seed = atoi (argv[1]);
1065   else
1066     seed = time (0) * 257 % 32768;
1067
1068   fputs ("Testing avl...\n", stdout);
1069
1070   for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
1071     {
1072       avl_tree *tree;
1073       int i;
1074
1075       printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
1076       fflush (stdout);
1077
1078       srand (seed++);
1079
1080       for (i = 0; i < TREE_SIZE; i++)
1081         array[i] = i;
1082       shuffle (array, TREE_SIZE);
1083
1084       tree = avl_create (compare_ints, NULL);
1085       for (i = 0; i < TREE_SIZE; i++)
1086         avl_force_insert (tree, (void *) (array[i]));
1087       verify_tree (tree);
1088
1089       shuffle (array, TREE_SIZE);
1090       for (i = 0; i < TREE_SIZE; i++)
1091         {
1092           avl_tree *copy;
1093
1094           avl_delete (tree, (void *) (array[i]));
1095           verify_tree (tree);
1096
1097           copy = avl_copy (tree, NULL);
1098           verify_tree (copy);
1099           compare_trees (tree->root.link[0], copy->root.link[0]);
1100           avl_destroy (copy, NULL);
1101
1102           if (i % 128 == 0)
1103             {
1104               putchar ('.');
1105               fflush (stdout);
1106             }
1107         }
1108       fputs (" good.\n", stdout);
1109
1110       avl_destroy (tree, NULL);
1111     }
1112
1113   return 0;
1114 }
1115 #endif /* SELF_TEST */
1116
1117 /*
1118   Local variables:
1119   compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avl-test avl.c"
1120   End:
1121 */
1122