tavl.c

   1 /* Produced by texiweb from libavl.w. */
   2
   3 /* libavl - library for manipulation of binary trees.
   4    Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc.
   5
   6    This program is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU General Public License as
   8    published by the Free Software Foundation; either version 2 of the
   9    License, or (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful, but
  12    WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  14    See the GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19    02111-1307, USA.
  20
  21    The author may be contacted at <blp@gnu.org> on the Internet, or
  22    write to Ben Pfaff, Stanford University, Computer Science Dept., 353
  23    Serra Mall, Stanford CA 94305, USA.
  24 */
  25
  26 #include <assert.h>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include "tavl.h"
  30
  31 /* Creates and returns a new table
  32    with comparison function |compare| using parameter |param|
  33    and memory allocator |allocator|.
  34    Returns |NULL| if memory allocation failed. */
  35 struct tavl_table *
  36 tavl_create (tavl_comparison_func *compare, void *param,
  37             struct libavl_allocator *allocator)
  38 {
  39   struct tavl_table *tree;
  40
  41   assert (compare != NULL);
  42
  43   if (allocator == NULL)
  44     allocator = &tavl_allocator_default;
  45
  46   tree = allocator->libavl_malloc (allocator, sizeof *tree);
  47   if (tree == NULL)
  48     return NULL;
  49
  50   tree->tavl_root = NULL;
  51   tree->tavl_compare = compare;
  52   tree->tavl_param = param;
  53   tree->tavl_alloc = allocator;
  54   tree->tavl_count = 0;
  55
  56   return tree;
  57 }
  58
  59 /* Search |tree| for an item matching |item|, and return it if found.
  60    Otherwise return |NULL|. */
  61 void *
  62 tavl_find (const struct tavl_table *tree, const void *item)
  63 {
  64   const struct tavl_node *p;
  65
  66   assert (tree != NULL && item != NULL);
  67
  68   p = tree->tavl_root;
  69   if (p == NULL)
  70     return NULL;
  71
  72   for (;;)
  73     {
  74       int cmp, dir;
  75
  76       cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
  77       if (cmp == 0)
  78         return p->tavl_data;
  79
  80       dir = cmp > 0;
  81       if (p->tavl_tag[dir] == TAVL_CHILD)
  82         p = p->tavl_link[dir];
  83       else
  84         return NULL;
  85     }
  86 }
  87
  88 /* Search |tree| for an item matching |item|, and return it if found.
  89    Otherwise return |NULL| and set predecessor and successor to point to
  90    the relevant nodes. */
  91 void *
  92 tavl_bracket (const struct tavl_table *tree, const void *item, const void **predecessor, const void **successor)
  93 {
  94   const struct tavl_node *p;
  95
  96   assert (tree != NULL && item != NULL);
  97
  98   *predecessor = NULL;
  99   *successor = NULL;
 100   p = tree->tavl_root;
 101   if (p == NULL)
 102     return NULL;
 103
 104   for (;;)
 105     {
 106       int cmp, dir;
 107
 108       cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
 109       if (cmp == 0)
 110         return p->tavl_data;
 111
 112       dir = cmp > 0;
 113       if (p->tavl_tag[dir] == TAVL_CHILD)
 114         p = p->tavl_link[dir];
 115       else /* no match, bracket */
 116         {
 117           if (dir) /* match would have been above p */
 118             {
 119               *predecessor = p->tavl_data;
 120               p = p->tavl_link[dir]; /* follow thread up */
 121               if (p != NULL)
 122                 *successor = p->tavl_data;
 123             }
 124           else     /* match would have been below p */
 125             {
 126               *successor = p->tavl_data;
 127               p = p->tavl_link[dir]; /* follow thread down */
 128               if (p != NULL)
 129                 *predecessor = p->tavl_data;
 130             }
 131           return NULL;
 132         }
 133     }
 134 }
 135
 136 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
 137    If a duplicate item is found in the tree,
 138    returns a pointer to the duplicate without inserting |item|.
 139    Returns |NULL| in case of memory allocation failure. */
 140 void **
 141 tavl_probe (struct tavl_table *tree, void *item)
 142 {
 143   struct tavl_node *y, *z; /* Top node to update balance factor, and parent. */
 144   struct tavl_node *p, *q; /* Iterator, and parent. */
 145   struct tavl_node *n;     /* Newly inserted node. */
 146   struct tavl_node *w;     /* New root of rebalanced subtree. */
 147   int dir;                /* Direction to descend. */
 148
 149   unsigned char da[TAVL_MAX_HEIGHT]; /* Cached comparison results. */
 150   int k = 0;              /* Number of cached results. */
 151
 152   assert (tree != NULL && item != NULL);
 153
 154   z = (struct tavl_node *) &tree->tavl_root;
 155   y = tree->tavl_root;
 156   if (y != NULL)
 157     {
 158       for (q = z, p = y; ; q = p, p = p->tavl_link[dir])
 159         {
 160           int cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
 161           if (cmp == 0)
 162             return &p->tavl_data;
 163
 164           if (p->tavl_balance != 0)
 165             z = q, y = p, k = 0;
 166           da[k++] = dir = cmp > 0;
 167
 168           if (p->tavl_tag[dir] == TAVL_THREAD)
 169             break;
 170         }
 171     }
 172   else
 173     {
 174       p = z;
 175       dir = 0;
 176     }
 177
 178   n = tree->tavl_alloc->libavl_malloc (tree->tavl_alloc, sizeof *n);
 179   if (n == NULL)
 180     return NULL;
 181
 182   tree->tavl_count++;
 183   n->tavl_data = item;
 184   n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD;
 185   n->tavl_link[dir] = p->tavl_link[dir];
 186   if (tree->tavl_root != NULL)
 187     {
 188       p->tavl_tag[dir] = TAVL_CHILD;
 189       n->tavl_link[!dir] = p;
 190     }
 191   else
 192     n->tavl_link[1] = NULL;
 193   p->tavl_link[dir] = n;
 194   n->tavl_balance = 0;
 195   if (tree->tavl_root == n)
 196     return &n->tavl_data;
 197
 198   for (p = y, k = 0; p != n; p = p->tavl_link[da[k]], k++)
 199     if (da[k] == 0)
 200       p->tavl_balance--;
 201     else
 202       p->tavl_balance++;
 203
 204   if (y->tavl_balance == -2)
 205     {
 206       struct tavl_node *x = y->tavl_link[0];
 207       if (x->tavl_balance == -1)
 208         {
 209           w = x;
 210           if (x->tavl_tag[1] == TAVL_THREAD)
 211             {
 212               x->tavl_tag[1] = TAVL_CHILD;
 213               y->tavl_tag[0] = TAVL_THREAD;
 214               y->tavl_link[0] = x;
 215             }
 216           else
 217             y->tavl_link[0] = x->tavl_link[1];
 218           x->tavl_link[1] = y;
 219           x->tavl_balance = y->tavl_balance = 0;
 220         }
 221       else
 222         {
 223           assert (x->tavl_balance == +1);
 224           w = x->tavl_link[1];
 225           x->tavl_link[1] = w->tavl_link[0];
 226           w->tavl_link[0] = x;
 227           y->tavl_link[0] = w->tavl_link[1];
 228           w->tavl_link[1] = y;
 229           if (w->tavl_balance == -1)
 230             x->tavl_balance = 0, y->tavl_balance = +1;
 231           else if (w->tavl_balance == 0)
 232             x->tavl_balance = y->tavl_balance = 0;
 233           else /* |w->tavl_balance == +1| */
 234             x->tavl_balance = -1, y->tavl_balance = 0;
 235           w->tavl_balance = 0;
 236           if (w->tavl_tag[0] == TAVL_THREAD)
 237             {
 238               x->tavl_tag[1] = TAVL_THREAD;
 239               x->tavl_link[1] = w;
 240               w->tavl_tag[0] = TAVL_CHILD;
 241             }
 242           if (w->tavl_tag[1] == TAVL_THREAD)
 243             {
 244               y->tavl_tag[0] = TAVL_THREAD;
 245               y->tavl_link[0] = w;
 246               w->tavl_tag[1] = TAVL_CHILD;
 247             }
 248         }
 249     }
 250   else if (y->tavl_balance == +2)
 251     {
 252       struct tavl_node *x = y->tavl_link[1];
 253       if (x->tavl_balance == +1)
 254         {
 255           w = x;
 256           if (x->tavl_tag[0] == TAVL_THREAD)
 257             {
 258               x->tavl_tag[0] = TAVL_CHILD;
 259               y->tavl_tag[1] = TAVL_THREAD;
 260               y->tavl_link[1] = x;
 261             }
 262           else
 263             y->tavl_link[1] = x->tavl_link[0];
 264           x->tavl_link[0] = y;
 265           x->tavl_balance = y->tavl_balance = 0;
 266         }
 267       else
 268         {
 269           assert (x->tavl_balance == -1);
 270           w = x->tavl_link[0];
 271           x->tavl_link[0] = w->tavl_link[1];
 272           w->tavl_link[1] = x;
 273           y->tavl_link[1] = w->tavl_link[0];
 274           w->tavl_link[0] = y;
 275           if (w->tavl_balance == +1)
 276             x->tavl_balance = 0, y->tavl_balance = -1;
 277           else if (w->tavl_balance == 0)
 278             x->tavl_balance = y->tavl_balance = 0;
 279           else /* |w->tavl_balance == -1| */
 280             x->tavl_balance = +1, y->tavl_balance = 0;
 281           w->tavl_balance = 0;
 282           if (w->tavl_tag[0] == TAVL_THREAD)
 283             {
 284               y->tavl_tag[1] = TAVL_THREAD;
 285               y->tavl_link[1] = w;
 286               w->tavl_tag[0] = TAVL_CHILD;
 287             }
 288           if (w->tavl_tag[1] == TAVL_THREAD)
 289             {
 290               x->tavl_tag[0] = TAVL_THREAD;
 291               x->tavl_link[0] = w;
 292               w->tavl_tag[1] = TAVL_CHILD;
 293             }
 294         }
 295     }
 296   else
 297     return &n->tavl_data;
 298   z->tavl_link[y != z->tavl_link[0]] = w;
 299
 300   return &n->tavl_data;
 301 }
 302
 303 /* Inserts |item| into |table|.
 304    Returns |NULL| if |item| was successfully inserted
 305    or if a memory allocation error occurred.
 306    Otherwise, returns the duplicate item. */
 307 void *
 308 tavl_insert (struct tavl_table *table, void *item)
 309 {
 310   void **p = tavl_probe (table, item);
 311   return p == NULL || *p == item ? NULL : *p;
 312 }
 313
 314 /* Inserts |item| into |table|, replacing any duplicate item.
 315    Returns |NULL| if |item| was inserted without replacing a duplicate,
 316    or if a memory allocation error occurred.
 317    Otherwise, returns the item that was replaced. */
 318 void *
 319 tavl_replace (struct tavl_table *table, void *item)
 320 {
 321   void **p = tavl_probe (table, item);
 322   if (p == NULL || *p == item)
 323     return NULL;
 324   else
 325     {
 326       void *r = *p;
 327       *p = item;
 328       return r;
 329     }
 330 }
 331
 332 /* Returns the parent of |node| within |tree|,
 333    or a pointer to |tavl_root| if |s| is the root of the tree. */
 334 static struct tavl_node *
 335 find_parent (struct tavl_table *tree, struct tavl_node *node)
 336 {
 337   if (node != tree->tavl_root)
 338     {
 339       struct tavl_node *x, *y;
 340
 341       for (x = y = node; ; x = x->tavl_link[0], y = y->tavl_link[1])
 342         if (y->tavl_tag[1] == TAVL_THREAD)
 343           {
 344             struct tavl_node *p = y->tavl_link[1];
 345             if (p == NULL || p->tavl_link[0] != node)
 346               {
 347                 while (x->tavl_tag[0] == TAVL_CHILD)
 348                   x = x->tavl_link[0];
 349                 p = x->tavl_link[0];
 350               }
 351             return p;
 352           }
 353         else if (x->tavl_tag[0] == TAVL_THREAD)
 354           {
 355             struct tavl_node *p = x->tavl_link[0];
 356             if (p == NULL || p->tavl_link[1] != node)
 357               {
 358                 while (y->tavl_tag[1] == TAVL_CHILD)
 359                   y = y->tavl_link[1];
 360                 p = y->tavl_link[1];
 361               }
 362             return p;
 363           }
 364     }
 365   else
 366     return (struct tavl_node *) &tree->tavl_root;
 367 }
 368
 369 /* Deletes from |tree| and returns an item matching |item|.
 370    Returns a null pointer if no matching item found. */
 371 void *
 372 tavl_delete (struct tavl_table *tree, const void *item)
 373 {
 374   struct tavl_node *p; /* Traverses tree to find node to delete. */
 375   struct tavl_node *q; /* Parent of |p|. */
 376   int dir;             /* Index into |q->tavl_link[]| to get |p|. */
 377   int cmp;             /* Result of comparison between |item| and |p|. */
 378
 379   assert (tree != NULL && item != NULL);
 380
 381   if (tree->tavl_root == NULL)
 382     return NULL;
 383
 384   q = (struct tavl_node *) &tree->tavl_root;
 385   p = tree->tavl_root;
 386   dir = 0;
 387   for (;;)
 388     {
 389       cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
 390       if (cmp == 0)
 391         break;
 392       dir = cmp > 0;
 393
 394       q = p;
 395       if (p->tavl_tag[dir] == TAVL_THREAD)
 396         return NULL;
 397       p = p->tavl_link[dir];
 398     }
 399   item = p->tavl_data;
 400
 401   if (p->tavl_tag[1] == TAVL_THREAD)
 402     {
 403       if (p->tavl_tag[0] == TAVL_CHILD)
 404         {
 405           struct tavl_node *t = p->tavl_link[0];
 406           while (t->tavl_tag[1] == TAVL_CHILD)
 407             t = t->tavl_link[1];
 408           t->tavl_link[1] = p->tavl_link[1];
 409           q->tavl_link[dir] = p->tavl_link[0];
 410         }
 411       else
 412         {
 413           q->tavl_link[dir] = p->tavl_link[dir];
 414           if (q != (struct tavl_node *) &tree->tavl_root)
 415             q->tavl_tag[dir] = TAVL_THREAD;
 416         }
 417     }
 418   else
 419     {
 420       struct tavl_node *r = p->tavl_link[1];
 421       if (r->tavl_tag[0] == TAVL_THREAD)
 422         {
 423           r->tavl_link[0] = p->tavl_link[0];
 424           r->tavl_tag[0] = p->tavl_tag[0];
 425           if (r->tavl_tag[0] == TAVL_CHILD)
 426             {
 427               struct tavl_node *t = r->tavl_link[0];
 428               while (t->tavl_tag[1] == TAVL_CHILD)
 429                 t = t->tavl_link[1];
 430               t->tavl_link[1] = r;
 431             }
 432           q->tavl_link[dir] = r;
 433           r->tavl_balance = p->tavl_balance;
 434           q = r;
 435           dir = 1;
 436         }
 437       else
 438         {
 439           struct tavl_node *s;
 440
 441           for (;;)
 442             {
 443               s = r->tavl_link[0];
 444               if (s->tavl_tag[0] == TAVL_THREAD)
 445                 break;
 446
 447               r = s;
 448             }
 449
 450           if (s->tavl_tag[1] == TAVL_CHILD)
 451             r->tavl_link[0] = s->tavl_link[1];
 452           else
 453             {
 454               r->tavl_link[0] = s;
 455               r->tavl_tag[0] = TAVL_THREAD;
 456             }
 457
 458           s->tavl_link[0] = p->tavl_link[0];
 459           if (p->tavl_tag[0] == TAVL_CHILD)
 460             {
 461               struct tavl_node *t = p->tavl_link[0];
 462               while (t->tavl_tag[1] == TAVL_CHILD)
 463                 t = t->tavl_link[1];
 464               t->tavl_link[1] = s;
 465
 466               s->tavl_tag[0] = TAVL_CHILD;
 467             }
 468
 469           s->tavl_link[1] = p->tavl_link[1];
 470           s->tavl_tag[1] = TAVL_CHILD;
 471
 472           q->tavl_link[dir] = s;
 473           s->tavl_balance = p->tavl_balance;
 474           q = r;
 475           dir = 0;
 476         }
 477     }
 478
 479   tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);
 480
 481   while (q != (struct tavl_node *) &tree->tavl_root)
 482     {
 483       struct tavl_node *y = q;
 484
 485       q = find_parent (tree, y);
 486
 487       if (dir == 0)
 488         {
 489           dir = q->tavl_link[0] != y;
 490           y->tavl_balance++;
 491           if (y->tavl_balance == +1)
 492             break;
 493           else if (y->tavl_balance == +2)
 494             {
 495               struct tavl_node *x = y->tavl_link[1];
 496
 497               assert (x != NULL);
 498               if (x->tavl_balance == -1)
 499                 {
 500                   struct tavl_node *w;
 501
 502                   assert (x->tavl_balance == -1);
 503                   w = x->tavl_link[0];
 504                   x->tavl_link[0] = w->tavl_link[1];
 505                   w->tavl_link[1] = x;
 506                   y->tavl_link[1] = w->tavl_link[0];
 507                   w->tavl_link[0] = y;
 508                   if (w->tavl_balance == +1)
 509                     x->tavl_balance = 0, y->tavl_balance = -1;
 510                   else if (w->tavl_balance == 0)
 511                     x->tavl_balance = y->tavl_balance = 0;
 512                   else /* |w->tavl_balance == -1| */
 513                     x->tavl_balance = +1, y->tavl_balance = 0;
 514                   w->tavl_balance = 0;
 515                   if (w->tavl_tag[0] == TAVL_THREAD)
 516                     {
 517                       y->tavl_tag[1] = TAVL_THREAD;
 518                       y->tavl_link[1] = w;
 519                       w->tavl_tag[0] = TAVL_CHILD;
 520                     }
 521                   if (w->tavl_tag[1] == TAVL_THREAD)
 522                     {
 523                       x->tavl_tag[0] = TAVL_THREAD;
 524                       x->tavl_link[0] = w;
 525                       w->tavl_tag[1] = TAVL_CHILD;
 526                     }
 527                   q->tavl_link[dir] = w;
 528                 }
 529               else
 530                 {
 531                   q->tavl_link[dir] = x;
 532
 533                   if (x->tavl_balance == 0)
 534                     {
 535                       y->tavl_link[1] = x->tavl_link[0];
 536                       x->tavl_link[0] = y;
 537                       x->tavl_balance = -1;
 538                       y->tavl_balance = +1;
 539                       break;
 540                     }
 541                   else /* |x->tavl_balance == +1| */
 542                     {
 543                       if (x->tavl_tag[0] == TAVL_CHILD)
 544                         y->tavl_link[1] = x->tavl_link[0];
 545                       else
 546                         {
 547                           y->tavl_tag[1] = TAVL_THREAD;
 548                           x->tavl_tag[0] = TAVL_CHILD;
 549                         }
 550                       x->tavl_link[0] = y;
 551                       y->tavl_balance = x->tavl_balance = 0;
 552                     }
 553                 }
 554             }
 555         }
 556       else
 557         {
 558           dir = q->tavl_link[0] != y;
 559           y->tavl_balance--;
 560           if (y->tavl_balance == -1)
 561             break;
 562           else if (y->tavl_balance == -2)
 563             {
 564               struct tavl_node *x = y->tavl_link[0];
 565               assert (x != NULL);
 566               if (x->tavl_balance == +1)
 567                 {
 568                   struct tavl_node *w;
 569
 570                   assert (x->tavl_balance == +1);
 571                   w = x->tavl_link[1];
 572                   x->tavl_link[1] = w->tavl_link[0];
 573                   w->tavl_link[0] = x;
 574                   y->tavl_link[0] = w->tavl_link[1];
 575                   w->tavl_link[1] = y;
 576                   if (w->tavl_balance == -1)
 577                     x->tavl_balance = 0, y->tavl_balance = +1;
 578                   else if (w->tavl_balance == 0)
 579                     x->tavl_balance = y->tavl_balance = 0;
 580                   else /* |w->tavl_balance == +1| */
 581                     x->tavl_balance = -1, y->tavl_balance = 0;
 582                   w->tavl_balance = 0;
 583                   if (w->tavl_tag[0] == TAVL_THREAD)
 584                     {
 585                       x->tavl_tag[1] = TAVL_THREAD;
 586                       x->tavl_link[1] = w;
 587                       w->tavl_tag[0] = TAVL_CHILD;
 588                     }
 589                   if (w->tavl_tag[1] == TAVL_THREAD)
 590                     {
 591                       y->tavl_tag[0] = TAVL_THREAD;
 592                       y->tavl_link[0] = w;
 593                       w->tavl_tag[1] = TAVL_CHILD;
 594                     }
 595                   q->tavl_link[dir] = w;
 596                 }
 597               else
 598                 {
 599                   q->tavl_link[dir] = x;
 600
 601                   if (x->tavl_balance == 0)
 602                     {
 603                       y->tavl_link[0] = x->tavl_link[1];
 604                       x->tavl_link[1] = y;
 605                       x->tavl_balance = +1;
 606                       y->tavl_balance = -1;
 607                       break;
 608                     }
 609                   else /* |x->tavl_balance == -1| */
 610                     {
 611                       if (x->tavl_tag[1] == TAVL_CHILD)
 612                         y->tavl_link[0] = x->tavl_link[1];
 613                       else
 614                         {
 615                           y->tavl_tag[0] = TAVL_THREAD;
 616                           x->tavl_tag[1] = TAVL_CHILD;
 617                         }
 618                       x->tavl_link[1] = y;
 619                       y->tavl_balance = x->tavl_balance = 0;
 620                     }
 621                 }
 622             }
 623         }
 624     }
 625
 626   tree->tavl_count--;
 627   return (void *) item;
 628 }
 629
 630 /* Initializes |trav| for use with |tree|
 631    and selects the null node. */
 632 void
 633 tavl_t_init (struct tavl_traverser *trav, struct tavl_table *tree)
 634 {
 635   trav->tavl_table = tree;
 636   trav->tavl_node = NULL;
 637 }
 638
 639 /* Initializes |trav| for |tree|.
 640    Returns data item in |tree| with the least value,
 641    or |NULL| if |tree| is empty. */
 642 void *
 643 tavl_t_first (struct tavl_traverser *trav, struct tavl_table *tree)
 644 {
 645   assert (tree != NULL && trav != NULL);
 646
 647   trav->tavl_table = tree;
 648   trav->tavl_node = tree->tavl_root;
 649   if (trav->tavl_node != NULL)
 650     {
 651       while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
 652         trav->tavl_node = trav->tavl_node->tavl_link[0];
 653       return trav->tavl_node->tavl_data;
 654     }
 655   else
 656     return NULL;
 657 }
 658
 659 /* Initializes |trav| for |tree|.
 660    Returns data item in |tree| with the greatest value,
 661    or |NULL| if |tree| is empty. */
 662 void *
 663 tavl_t_last (struct tavl_traverser *trav, struct tavl_table *tree)
 664 {
 665   assert (tree != NULL && trav != NULL);
 666
 667   trav->tavl_table = tree;
 668   trav->tavl_node = tree->tavl_root;
 669   if (trav->tavl_node != NULL)
 670     {
 671       while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
 672         trav->tavl_node = trav->tavl_node->tavl_link[1];
 673       return trav->tavl_node->tavl_data;
 674     }
 675   else
 676     return NULL;
 677 }
 678
 679 /* Searches for |item| in |tree|.
 680    If found, initializes |trav| to the item found and returns the item
 681    as well.
 682    If there is no matching item, initializes |trav| to the null item
 683    and returns |NULL|. */
 684 void *
 685 tavl_t_find (struct tavl_traverser *trav, struct tavl_table *tree, void *item)
 686 {
 687   struct tavl_node *p;
 688
 689   assert (trav != NULL && tree != NULL && item != NULL);
 690
 691   trav->tavl_table = tree;
 692   trav->tavl_node = NULL;
 693
 694   p = tree->tavl_root;
 695   if (p == NULL)
 696     return NULL;
 697
 698   for (;;)
 699     {
 700       int cmp, dir;
 701
 702       cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
 703       if (cmp == 0)
 704         {
 705           trav->tavl_node = p;
 706           return p->tavl_data;
 707         }
 708
 709       dir = cmp > 0;
 710       if (p->tavl_tag[dir] == TAVL_CHILD)
 711         p = p->tavl_link[dir];
 712       else
 713         return NULL;
 714     }
 715 }
 716
 717 /* Attempts to insert |item| into |tree|.
 718    If |item| is inserted successfully, it is returned and |trav| is
 719    initialized to its location.
 720    If a duplicate is found, it is returned and |trav| is initialized to
 721    its location.  No replacement of the item occurs.
 722    If a memory allocation failure occurs, |NULL| is returned and |trav|
 723    is initialized to the null item. */
 724 void *
 725 tavl_t_insert (struct tavl_traverser *trav,
 726                struct tavl_table *tree, void *item)
 727 {
 728   void **p;
 729
 730   assert (trav != NULL && tree != NULL && item != NULL);
 731
 732   p = tavl_probe (tree, item);
 733   if (p != NULL)
 734     {
 735       trav->tavl_table = tree;
 736       trav->tavl_node =
 737         ((struct tavl_node *)
 738          ((char *) p - offsetof (struct tavl_node, tavl_data)));
 739       return *p;
 740     }
 741   else
 742     {
 743       tavl_t_init (trav, tree);
 744       return NULL;
 745     }
 746 }
 747
 748 /* Initializes |trav| to have the same current node as |src|. */
 749 void *
 750 tavl_t_copy (struct tavl_traverser *trav, const struct tavl_traverser *src)
 751 {
 752   assert (trav != NULL && src != NULL);
 753
 754   trav->tavl_table = src->tavl_table;
 755   trav->tavl_node = src->tavl_node;
 756
 757   return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
 758 }
 759
 760 /* Returns the next data item in inorder
 761    within the tree being traversed with |trav|,
 762    or if there are no more data items returns |NULL|. */
 763 void *
 764 tavl_t_next (struct tavl_traverser *trav)
 765 {
 766   assert (trav != NULL);
 767
 768   if (trav->tavl_node == NULL)
 769     return tavl_t_first (trav, trav->tavl_table);
 770   else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD)
 771     {
 772       trav->tavl_node = trav->tavl_node->tavl_link[1];
 773       return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
 774     }
 775   else
 776     {
 777       trav->tavl_node = trav->tavl_node->tavl_link[1];
 778       while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
 779         trav->tavl_node = trav->tavl_node->tavl_link[0];
 780       return trav->tavl_node->tavl_data;
 781     }
 782 }
 783
 784 /* Returns the previous data item in inorder
 785    within the tree being traversed with |trav|,
 786    or if there are no more data items returns |NULL|. */
 787 void *
 788 tavl_t_prev (struct tavl_traverser *trav)
 789 {
 790   assert (trav != NULL);
 791
 792   if (trav->tavl_node == NULL)
 793     return tavl_t_last (trav, trav->tavl_table);
 794   else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD)
 795     {
 796       trav->tavl_node = trav->tavl_node->tavl_link[0];
 797       return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
 798     }
 799   else
 800     {
 801       trav->tavl_node = trav->tavl_node->tavl_link[0];
 802       while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
 803         trav->tavl_node = trav->tavl_node->tavl_link[1];
 804       return trav->tavl_node->tavl_data;
 805     }
 806 }
 807
 808 /* Returns |trav|'s current item. */
 809 void *
 810 tavl_t_cur (struct tavl_traverser *trav)
 811 {
 812   assert (trav != NULL);
 813
 814   return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
 815 }
 816
 817 /* Replaces the current item in |trav| by |new| and returns the item replaced.
 818    |trav| must not have the null item selected.
 819    The new item must not upset the ordering of the tree. */
 820 void *
 821 tavl_t_replace (struct tavl_traverser *trav, void *new)
 822 {
 823   void *old;
 824
 825   assert (trav != NULL && trav->tavl_node != NULL && new != NULL);
 826   old = trav->tavl_node->tavl_data;
 827   trav->tavl_node->tavl_data = new;
 828   return old;
 829 }
 830
 831 /* Creates a new node as a child of |dst| on side |dir|.
 832    Copies data and |tavl_balance| from |src| into the new node,
 833    applying |copy()|, if non-null.
 834    Returns nonzero only if fully successful.
 835    Regardless of success, integrity of the tree structure is assured,
 836    though failure may leave a null pointer in a |tavl_data| member. */
 837 static int
 838 copy_node (struct tavl_table *tree,
 839            struct tavl_node *dst, int dir,
 840            const struct tavl_node *src, tavl_copy_func *copy)
 841 {
 842   struct tavl_node *new =
 843     tree->tavl_alloc->libavl_malloc (tree->tavl_alloc, sizeof *new);
 844   if (new == NULL)
 845     return 0;
 846
 847   new->tavl_link[dir] = dst->tavl_link[dir];
 848   new->tavl_tag[dir] = TAVL_THREAD;
 849   new->tavl_link[!dir] = dst;
 850   new->tavl_tag[!dir] = TAVL_THREAD;
 851   dst->tavl_link[dir] = new;
 852   dst->tavl_tag[dir] = TAVL_CHILD;
 853
 854   new->tavl_balance = src->tavl_balance;
 855   if (copy == NULL)
 856     new->tavl_data = src->tavl_data;
 857   else
 858     {
 859       new->tavl_data = copy (src->tavl_data, tree->tavl_param);
 860       if (new->tavl_data == NULL)
 861         return 0;
 862     }
 863
 864   return 1;
 865 }
 866
 867 /* Destroys |new| with |tavl_destroy (new, destroy)|,
 868    first initializing the right link in |new| that has
 869    not yet been initialized. */
 870 static void
 871 copy_error_recovery (struct tavl_node *p,
 872                      struct tavl_table *new, tavl_item_func *destroy)
 873 {
 874   new->tavl_root = p;
 875   if (p != NULL)
 876     {
 877       while (p->tavl_tag[1] == TAVL_CHILD)
 878         p = p->tavl_link[1];
 879       p->tavl_link[1] = NULL;
 880     }
 881   tavl_destroy (new, destroy);
 882 }
 883
 884 /* Copies |org| to a newly created tree, which is returned.
 885    If |copy != NULL|, each data item in |org| is first passed to |copy|,
 886    and the return values are inserted into the tree,
 887    with |NULL| return values taken as indications of failure.
 888    On failure, destroys the partially created new tree,
 889    applying |destroy|, if non-null, to each item in the new tree so far,
 890    and returns |NULL|.
 891    If |allocator != NULL|, it is used for allocation in the new tree.
 892    Otherwise, the same allocator used for |org| is used. */
 893 struct tavl_table *
 894 tavl_copy (const struct tavl_table *org, tavl_copy_func *copy,
 895           tavl_item_func *destroy, struct libavl_allocator *allocator)
 896 {
 897   struct tavl_table *new;
 898
 899   const struct tavl_node *p;
 900   struct tavl_node *q;
 901   struct tavl_node rp, rq;
 902
 903   assert (org != NULL);
 904   new = tavl_create (org->tavl_compare, org->tavl_param,
 905                      allocator != NULL ? allocator : org->tavl_alloc);
 906   if (new == NULL)
 907     return NULL;
 908
 909   new->tavl_count = org->tavl_count;
 910   if (new->tavl_count == 0)
 911     return new;
 912
 913   p = &rp;
 914   rp.tavl_link[0] = org->tavl_root;
 915   rp.tavl_tag[0] = TAVL_CHILD;
 916
 917   q = &rq;
 918   rq.tavl_link[0] = NULL;
 919   rq.tavl_tag[0] = TAVL_THREAD;
 920
 921   for (;;)
 922     {
 923       if (p->tavl_tag[0] == TAVL_CHILD)
 924         {
 925           if (!copy_node (new, q, 0, p->tavl_link[0], copy))
 926             {
 927               copy_error_recovery (rq.tavl_link[0], new, destroy);
 928               return NULL;
 929             }
 930
 931           p = p->tavl_link[0];
 932           q = q->tavl_link[0];
 933         }
 934       else
 935         {
 936           while (p->tavl_tag[1] == TAVL_THREAD)
 937             {
 938               p = p->tavl_link[1];
 939               if (p == NULL)
 940                 {
 941                   q->tavl_link[1] = NULL;
 942                   new->tavl_root = rq.tavl_link[0];
 943                   return new;
 944                 }
 945
 946               q = q->tavl_link[1];
 947             }
 948
 949           p = p->tavl_link[1];
 950           q = q->tavl_link[1];
 951         }
 952
 953       if (p->tavl_tag[1] == TAVL_CHILD)
 954         if (!copy_node (new, q, 1, p->tavl_link[1], copy))
 955           {
 956             copy_error_recovery (rq.tavl_link[0], new, destroy);
 957             return NULL;
 958           }
 959     }
 960 }
 961
 962 /* Frees storage allocated for |tree|.
 963    If |destroy != NULL|, applies it to each data item in inorder. */
 964 void
 965 tavl_destroy (struct tavl_table *tree, tavl_item_func *destroy)
 966 {
 967   struct tavl_node *p; /* Current node. */
 968   struct tavl_node *n; /* Next node. */
 969
 970   p = tree->tavl_root;
 971   if (p != NULL)
 972     while (p->tavl_tag[0] == TAVL_CHILD)
 973       p = p->tavl_link[0];
 974
 975   while (p != NULL)
 976     {
 977       n = p->tavl_link[1];
 978       if (p->tavl_tag[1] == TAVL_CHILD)
 979         while (n->tavl_tag[0] == TAVL_CHILD)
 980           n = n->tavl_link[0];
 981
 982       if (destroy != NULL && p->tavl_data != NULL)
 983         destroy (p->tavl_data, tree->tavl_param);
 984       tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);
 985
 986       p = n;
 987     }
 988
 989   tree->tavl_alloc->libavl_free (tree->tavl_alloc, tree);
 990 }
 991
 992 /* Allocates |size| bytes of space using |malloc()|.
 993    Returns a null pointer if allocation fails. */
 994 void *
 995 tavl_malloc (struct libavl_allocator *allocator, size_t size)
 996 {
 997   assert (allocator != NULL && size > 0);
 998   return malloc (size);
 999 }
1000
1001 /* Frees |block|. */
1002 void
1003 tavl_free (struct libavl_allocator *allocator, void *block)
1004 {
1005   assert (allocator != NULL && block != NULL);
1006   free (block);
1007 }
1008
1009 /* Default memory allocator that uses |malloc()| and |free()|. */
1010 struct libavl_allocator tavl_allocator_default =
1011   {
1012     tavl_malloc,
1013     tavl_free
1014   };
1015
1016 #undef NDEBUG
1017 #include <assert.h>
1018
1019 /* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
1020 void
1021 (tavl_assert_insert) (struct tavl_table *table, void *item)
1022 {
1023   void **p = tavl_probe (table, item);
1024   assert (p != NULL && *p == item);
1025 }
1026
1027 /* Asserts that |tavl_delete()| really removes |item| from |table|,
1028    and returns the removed item. */
1029 void *
1030 (tavl_assert_delete) (struct tavl_table *table, void *item)
1031 {
1032   void *p = tavl_delete (table, item);
1033   assert (p != NULL);
1034   return p;
1035 }
1036