c_cpp/readsdedump/prb.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 "prb.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 prb_table *
  36 prb_create (prb_comparison_func *compare, void *param,
  37             struct libavl_allocator *allocator)
  38 {
  39   struct prb_table *tree;
  40
  41   assert (compare != NULL);
  42
  43   if (allocator == NULL)
  44     allocator = &prb_allocator_default;
  45
  46   tree = allocator->libavl_malloc (allocator, sizeof *tree);
  47   if (tree == NULL)
  48     return NULL;
  49
  50   tree->prb_root = NULL;
  51   tree->prb_compare = compare;
  52   tree->prb_param = param;
  53   tree->prb_alloc = allocator;
  54   tree->prb_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 prb_find (const struct prb_table *tree, const void *item)
  63 {
  64   const struct prb_node *p;
  65
  66   assert (tree != NULL && item != NULL);
  67   for (p = tree->prb_root; p != NULL; )
  68     {
  69       int cmp = tree->prb_compare (item, p->prb_data, tree->prb_param);
  70
  71       if (cmp < 0)
  72         p = p->prb_link[0];
  73       else if (cmp > 0)
  74         p = p->prb_link[1];
  75       else /* |cmp == 0| */
  76         return p->prb_data;
  77     }
  78
  79   return NULL;
  80 }
  81
  82 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
  83    If a duplicate item is found in the tree,
  84    returns a pointer to the duplicate without inserting |item|.
  85    Returns |NULL| in case of memory allocation failure. */
  86 void **
  87 prb_probe (struct prb_table *tree, void *item)
  88 {
  89   struct prb_node *p; /* Traverses tree looking for insertion point. */
  90   struct prb_node *q; /* Parent of |p|; node at which we are rebalancing. */
  91   struct prb_node *n; /* Newly inserted node. */
  92   int dir;            /* Side of |q| on which |n| is inserted. */
  93
  94   assert (tree != NULL && item != NULL);
  95
  96   for (q = NULL, p = tree->prb_root; p != NULL; q = p, p = p->prb_link[dir])
  97     {
  98       int cmp = tree->prb_compare (item, p->prb_data, tree->prb_param);
  99       if (cmp == 0)
 100         return &p->prb_data;
 101       dir = cmp > 0;
 102     }
 103
 104   n = tree->prb_alloc->libavl_malloc (tree->prb_alloc, sizeof *p);
 105   if (n == NULL)
 106     return NULL;
 107
 108   tree->prb_count++;
 109   n->prb_link[0] = n->prb_link[1] = NULL;
 110   n->prb_parent = q;
 111   n->prb_data = item;
 112   if (q != NULL)
 113     q->prb_link[dir] = n;
 114   else
 115     tree->prb_root = n;
 116   n->prb_color = PRB_RED;
 117
 118   q = n;
 119   for (;;)
 120     {
 121       struct prb_node *f; /* Parent of |q|. */
 122       struct prb_node *g; /* Grandparent of |q|. */
 123
 124       f = q->prb_parent;
 125       if (f == NULL || f->prb_color == PRB_BLACK)
 126         break;
 127
 128       g = f->prb_parent;
 129       if (g == NULL)
 130         break;
 131
 132       if (g->prb_link[0] == f)
 133         {
 134           struct prb_node *y = g->prb_link[1];
 135           if (y != NULL && y->prb_color == PRB_RED)
 136             {
 137               f->prb_color = y->prb_color = PRB_BLACK;
 138               g->prb_color = PRB_RED;
 139               q = g;
 140             }
 141           else
 142             {
 143               struct prb_node *h; /* Great-grandparent of |q|. */
 144
 145               h = g->prb_parent;
 146               if (h == NULL)
 147                 h = (struct prb_node *) &tree->prb_root;
 148
 149               if (f->prb_link[1] == q)
 150                 {
 151                   f->prb_link[1] = q->prb_link[0];
 152                   q->prb_link[0] = f;
 153                   g->prb_link[0] = q;
 154                   f->prb_parent = q;
 155                   if (f->prb_link[1] != NULL)
 156                     f->prb_link[1]->prb_parent = f;
 157
 158                   f = q;
 159                 }
 160
 161               g->prb_color = PRB_RED;
 162               f->prb_color = PRB_BLACK;
 163
 164               g->prb_link[0] = f->prb_link[1];
 165               f->prb_link[1] = g;
 166               h->prb_link[h->prb_link[0] != g] = f;
 167
 168               f->prb_parent = g->prb_parent;
 169               g->prb_parent = f;
 170               if (g->prb_link[0] != NULL)
 171                 g->prb_link[0]->prb_parent = g;
 172               break;
 173             }
 174         }
 175       else
 176         {
 177           struct prb_node *y = g->prb_link[0];
 178           if (y != NULL && y->prb_color == PRB_RED)
 179             {
 180               f->prb_color = y->prb_color = PRB_BLACK;
 181               g->prb_color = PRB_RED;
 182               q = g;
 183             }
 184           else
 185             {
 186               struct prb_node *h; /* Great-grandparent of |q|. */
 187
 188               h = g->prb_parent;
 189               if (h == NULL)
 190                 h = (struct prb_node *) &tree->prb_root;
 191
 192               if (f->prb_link[0] == q)
 193                 {
 194                   f->prb_link[0] = q->prb_link[1];
 195                   q->prb_link[1] = f;
 196                   g->prb_link[1] = q;
 197                   f->prb_parent = q;
 198                   if (f->prb_link[0] != NULL)
 199                     f->prb_link[0]->prb_parent = f;
 200
 201                   f = q;
 202                 }
 203
 204               g->prb_color = PRB_RED;
 205               f->prb_color = PRB_BLACK;
 206
 207               g->prb_link[1] = f->prb_link[0];
 208               f->prb_link[0] = g;
 209               h->prb_link[h->prb_link[0] != g] = f;
 210
 211               f->prb_parent = g->prb_parent;
 212               g->prb_parent = f;
 213               if (g->prb_link[1] != NULL)
 214                 g->prb_link[1]->prb_parent = g;
 215               break;
 216             }
 217         }
 218     }
 219   tree->prb_root->prb_color = PRB_BLACK;
 220
 221   return &n->prb_data;
 222 }
 223
 224 /* Inserts |item| into |table|.
 225    Returns |NULL| if |item| was successfully inserted
 226    or if a memory allocation error occurred.
 227    Otherwise, returns the duplicate item. */
 228 void *
 229 prb_insert (struct prb_table *table, void *item)
 230 {
 231   void **p = prb_probe (table, item);
 232   return p == NULL || *p == item ? NULL : *p;
 233 }
 234
 235 /* Inserts |item| into |table|, replacing any duplicate item.
 236    Returns |NULL| if |item| was inserted without replacing a duplicate,
 237    or if a memory allocation error occurred.
 238    Otherwise, returns the item that was replaced. */
 239 void *
 240 prb_replace (struct prb_table *table, void *item)
 241 {
 242   void **p = prb_probe (table, item);
 243   if (p == NULL || *p == item)
 244     return NULL;
 245   else
 246     {
 247       void *r = *p;
 248       *p = item;
 249       return r;
 250     }
 251 }
 252
 253 /* Deletes from |tree| and returns an item matching |item|.
 254    Returns a null pointer if no matching item found. */
 255 void *
 256 prb_delete (struct prb_table *tree, const void *item)
 257 {
 258   struct prb_node *p; /* Node to delete. */
 259   struct prb_node *q; /* Parent of |p|. */
 260   struct prb_node *f; /* Node at which we are rebalancing. */
 261   int dir;            /* Side of |q| on which |p| is a child;
 262                          side of |f| from which node was deleted. */
 263
 264   assert (tree != NULL && item != NULL);
 265
 266   if (tree->prb_root == NULL)
 267     return NULL;
 268
 269   p = tree->prb_root;
 270   for (;;)
 271     {
 272       int cmp = tree->prb_compare (item, p->prb_data, tree->prb_param);
 273       if (cmp == 0)
 274         break;
 275
 276       dir = cmp > 0;
 277       p = p->prb_link[dir];
 278       if (p == NULL)
 279         return NULL;
 280     }
 281   item = p->prb_data;
 282
 283   q = p->prb_parent;
 284   if (q == NULL)
 285     {
 286       q = (struct prb_node *) &tree->prb_root;
 287       dir = 0;
 288     }
 289
 290   if (p->prb_link[1] == NULL)
 291     {
 292       q->prb_link[dir] = p->prb_link[0];
 293       if (q->prb_link[dir] != NULL)
 294         q->prb_link[dir]->prb_parent = p->prb_parent;
 295
 296       f = q;
 297     }
 298   else
 299     {
 300       enum prb_color t;
 301       struct prb_node *r = p->prb_link[1];
 302
 303       if (r->prb_link[0] == NULL)
 304         {
 305           r->prb_link[0] = p->prb_link[0];
 306           q->prb_link[dir] = r;
 307           r->prb_parent = p->prb_parent;
 308           if (r->prb_link[0] != NULL)
 309             r->prb_link[0]->prb_parent = r;
 310
 311           t = p->prb_color;
 312           p->prb_color = r->prb_color;
 313           r->prb_color = t;
 314
 315           f = r;
 316           dir = 1;
 317         }
 318       else
 319         {
 320           struct prb_node *s = r->prb_link[0];
 321           while (s->prb_link[0] != NULL)
 322             s = s->prb_link[0];
 323           r = s->prb_parent;
 324           r->prb_link[0] = s->prb_link[1];
 325           s->prb_link[0] = p->prb_link[0];
 326           s->prb_link[1] = p->prb_link[1];
 327           q->prb_link[dir] = s;
 328           if (s->prb_link[0] != NULL)
 329             s->prb_link[0]->prb_parent = s;
 330           s->prb_link[1]->prb_parent = s;
 331           s->prb_parent = p->prb_parent;
 332           if (r->prb_link[0] != NULL)
 333             r->prb_link[0]->prb_parent = r;
 334
 335           t = p->prb_color;
 336           p->prb_color = s->prb_color;
 337           s->prb_color = t;
 338
 339           f = r;
 340           dir = 0;
 341         }
 342     }
 343
 344   if (p->prb_color == PRB_BLACK)
 345     {
 346       for (;;)
 347         {
 348           struct prb_node *x; /* Node we want to recolor black if possible. */
 349           struct prb_node *g; /* Parent of |f|. */
 350           struct prb_node *t; /* Temporary for use in finding parent. */
 351
 352           x = f->prb_link[dir];
 353           if (x != NULL && x->prb_color == PRB_RED)
 354             {
 355               x->prb_color = PRB_BLACK;
 356               break;
 357             }
 358
 359           if (f == (struct prb_node *) &tree->prb_root)
 360             break;
 361
 362           g = f->prb_parent;
 363           if (g == NULL)
 364             g = (struct prb_node *) &tree->prb_root;
 365
 366           if (dir == 0)
 367             {
 368               struct prb_node *w = f->prb_link[1];
 369
 370               if (w->prb_color == PRB_RED)
 371                 {
 372                   w->prb_color = PRB_BLACK;
 373                   f->prb_color = PRB_RED;
 374
 375                   f->prb_link[1] = w->prb_link[0];
 376                   w->prb_link[0] = f;
 377                   g->prb_link[g->prb_link[0] != f] = w;
 378
 379                   w->prb_parent = f->prb_parent;
 380                   f->prb_parent = w;
 381
 382                   g = w;
 383                   w = f->prb_link[1];
 384
 385                   w->prb_parent = f;
 386                 }
 387
 388               if ((w->prb_link[0] == NULL
 389                    || w->prb_link[0]->prb_color == PRB_BLACK)
 390                   && (w->prb_link[1] == NULL
 391                       || w->prb_link[1]->prb_color == PRB_BLACK))
 392                 {
 393                   w->prb_color = PRB_RED;
 394                 }
 395               else
 396                 {
 397                   if (w->prb_link[1] == NULL
 398                       || w->prb_link[1]->prb_color == PRB_BLACK)
 399                     {
 400                       struct prb_node *y = w->prb_link[0];
 401                       y->prb_color = PRB_BLACK;
 402                       w->prb_color = PRB_RED;
 403                       w->prb_link[0] = y->prb_link[1];
 404                       y->prb_link[1] = w;
 405                       if (w->prb_link[0] != NULL)
 406                         w->prb_link[0]->prb_parent = w;
 407                       w = f->prb_link[1] = y;
 408                       w->prb_link[1]->prb_parent = w;
 409                     }
 410
 411                   w->prb_color = f->prb_color;
 412                   f->prb_color = PRB_BLACK;
 413                   w->prb_link[1]->prb_color = PRB_BLACK;
 414
 415                   f->prb_link[1] = w->prb_link[0];
 416                   w->prb_link[0] = f;
 417                   g->prb_link[g->prb_link[0] != f] = w;
 418
 419                   w->prb_parent = f->prb_parent;
 420                   f->prb_parent = w;
 421                   if (f->prb_link[1] != NULL)
 422                     f->prb_link[1]->prb_parent = f;
 423                   break;
 424                 }
 425             }
 426           else
 427             {
 428               struct prb_node *w = f->prb_link[0];
 429
 430               if (w->prb_color == PRB_RED)
 431                 {
 432                   w->prb_color = PRB_BLACK;
 433                   f->prb_color = PRB_RED;
 434
 435                   f->prb_link[0] = w->prb_link[1];
 436                   w->prb_link[1] = f;
 437                   g->prb_link[g->prb_link[0] != f] = w;
 438
 439                   w->prb_parent = f->prb_parent;
 440                   f->prb_parent = w;
 441
 442                   g = w;
 443                   w = f->prb_link[0];
 444
 445                   w->prb_parent = f;
 446                 }
 447
 448               if ((w->prb_link[0] == NULL
 449                    || w->prb_link[0]->prb_color == PRB_BLACK)
 450                   && (w->prb_link[1] == NULL
 451                       || w->prb_link[1]->prb_color == PRB_BLACK))
 452                 {
 453                   w->prb_color = PRB_RED;
 454                 }
 455               else
 456                 {
 457                   if (w->prb_link[0] == NULL
 458                       || w->prb_link[0]->prb_color == PRB_BLACK)
 459                     {
 460                       struct prb_node *y = w->prb_link[1];
 461                       y->prb_color = PRB_BLACK;
 462                       w->prb_color = PRB_RED;
 463                       w->prb_link[1] = y->prb_link[0];
 464                       y->prb_link[0] = w;
 465                       if (w->prb_link[1] != NULL)
 466                         w->prb_link[1]->prb_parent = w;
 467                       w = f->prb_link[0] = y;
 468                       w->prb_link[0]->prb_parent = w;
 469                     }
 470
 471                   w->prb_color = f->prb_color;
 472                   f->prb_color = PRB_BLACK;
 473                   w->prb_link[0]->prb_color = PRB_BLACK;
 474
 475                   f->prb_link[0] = w->prb_link[1];
 476                   w->prb_link[1] = f;
 477                   g->prb_link[g->prb_link[0] != f] = w;
 478
 479                   w->prb_parent = f->prb_parent;
 480                   f->prb_parent = w;
 481                   if (f->prb_link[0] != NULL)
 482                     f->prb_link[0]->prb_parent = f;
 483                   break;
 484                 }
 485             }
 486
 487           t = f;
 488           f = f->prb_parent;
 489           if (f == NULL)
 490             f = (struct prb_node *) &tree->prb_root;
 491           dir = f->prb_link[0] != t;
 492         }
 493     }
 494
 495   tree->prb_alloc->libavl_free (tree->prb_alloc, p);
 496   tree->prb_count--;
 497   return (void *) item;
 498 }
 499
 500 /* Initializes |trav| for use with |tree|
 501    and selects the null node. */
 502 void
 503 prb_t_init (struct prb_traverser *trav, struct prb_table *tree)
 504 {
 505   trav->prb_table = tree;
 506   trav->prb_node = NULL;
 507 }
 508
 509 /* Initializes |trav| for |tree|.
 510    Returns data item in |tree| with the least value,
 511    or |NULL| if |tree| is empty. */
 512 void *
 513 prb_t_first (struct prb_traverser *trav, struct prb_table *tree)
 514 {
 515   assert (tree != NULL && trav != NULL);
 516
 517   trav->prb_table = tree;
 518   trav->prb_node = tree->prb_root;
 519   if (trav->prb_node != NULL)
 520     {
 521       while (trav->prb_node->prb_link[0] != NULL)
 522         trav->prb_node = trav->prb_node->prb_link[0];
 523       return trav->prb_node->prb_data;
 524     }
 525   else
 526     return NULL;
 527 }
 528
 529 /* Initializes |trav| for |tree|.
 530    Returns data item in |tree| with the greatest value,
 531    or |NULL| if |tree| is empty. */
 532 void *
 533 prb_t_last (struct prb_traverser *trav, struct prb_table *tree)
 534 {
 535   assert (tree != NULL && trav != NULL);
 536
 537   trav->prb_table = tree;
 538   trav->prb_node = tree->prb_root;
 539   if (trav->prb_node != NULL)
 540     {
 541       while (trav->prb_node->prb_link[1] != NULL)
 542         trav->prb_node = trav->prb_node->prb_link[1];
 543       return trav->prb_node->prb_data;
 544     }
 545   else
 546     return NULL;
 547 }
 548
 549 /* Searches for |item| in |tree|.
 550    If found, initializes |trav| to the item found and returns the item
 551    as well.
 552    If there is no matching item, initializes |trav| to the null item
 553    and returns |NULL|. */
 554 void *
 555 prb_t_find (struct prb_traverser *trav, struct prb_table *tree, void *item)
 556 {
 557   struct prb_node *p;
 558   int dir;
 559
 560   assert (trav != NULL && tree != NULL && item != NULL);
 561
 562   trav->prb_table = tree;
 563   for (p = tree->prb_root; p != NULL; p = p->prb_link[dir])
 564     {
 565       int cmp = tree->prb_compare (item, p->prb_data, tree->prb_param);
 566       if (cmp == 0)
 567         {
 568           trav->prb_node = p;
 569           return p->prb_data;
 570         }
 571
 572       dir = cmp > 0;
 573     }
 574
 575   trav->prb_node = NULL;
 576   return NULL;
 577 }
 578
 579 /* Attempts to insert |item| into |tree|.
 580    If |item| is inserted successfully, it is returned and |trav| is
 581    initialized to its location.
 582    If a duplicate is found, it is returned and |trav| is initialized to
 583    its location.  No replacement of the item occurs.
 584    If a memory allocation failure occurs, |NULL| is returned and |trav|
 585    is initialized to the null item. */
 586 void *
 587 prb_t_insert (struct prb_traverser *trav,
 588                struct prb_table *tree, void *item)
 589 {
 590   void **p;
 591
 592   assert (trav != NULL && tree != NULL && item != NULL);
 593
 594   p = prb_probe (tree, item);
 595   if (p != NULL)
 596     {
 597       trav->prb_table = tree;
 598       trav->prb_node =
 599         ((struct prb_node *)
 600          ((char *) p - offsetof (struct prb_node, prb_data)));
 601       return *p;
 602     }
 603   else
 604     {
 605       prb_t_init (trav, tree);
 606       return NULL;
 607     }
 608 }
 609
 610 /* Initializes |trav| to have the same current node as |src|. */
 611 void *
 612 prb_t_copy (struct prb_traverser *trav, const struct prb_traverser *src)
 613 {
 614   assert (trav != NULL && src != NULL);
 615
 616   trav->prb_table = src->prb_table;
 617   trav->prb_node = src->prb_node;
 618
 619   return trav->prb_node != NULL ? trav->prb_node->prb_data : NULL;
 620 }
 621
 622 /* Returns the next data item in inorder
 623    within the tree being traversed with |trav|,
 624    or if there are no more data items returns |NULL|. */
 625 void *
 626 prb_t_next (struct prb_traverser *trav)
 627 {
 628   assert (trav != NULL);
 629
 630   if (trav->prb_node == NULL)
 631     return prb_t_first (trav, trav->prb_table);
 632   else if (trav->prb_node->prb_link[1] == NULL)
 633     {
 634       struct prb_node *q, *p; /* Current node and its child. */
 635       for (p = trav->prb_node, q = p->prb_parent; ;
 636            p = q, q = q->prb_parent)
 637         if (q == NULL || p == q->prb_link[0])
 638           {
 639             trav->prb_node = q;
 640             return trav->prb_node != NULL ? trav->prb_node->prb_data : NULL;
 641           }
 642     }
 643   else
 644     {
 645       trav->prb_node = trav->prb_node->prb_link[1];
 646       while (trav->prb_node->prb_link[0] != NULL)
 647         trav->prb_node = trav->prb_node->prb_link[0];
 648       return trav->prb_node->prb_data;
 649     }
 650 }
 651
 652 /* Returns the previous data item in inorder
 653    within the tree being traversed with |trav|,
 654    or if there are no more data items returns |NULL|. */
 655 void *
 656 prb_t_prev (struct prb_traverser *trav)
 657 {
 658   assert (trav != NULL);
 659
 660   if (trav->prb_node == NULL)
 661     return prb_t_last (trav, trav->prb_table);
 662   else if (trav->prb_node->prb_link[0] == NULL)
 663     {
 664       struct prb_node *q, *p; /* Current node and its child. */
 665       for (p = trav->prb_node, q = p->prb_parent; ;
 666            p = q, q = q->prb_parent)
 667         if (q == NULL || p == q->prb_link[1])
 668           {
 669             trav->prb_node = q;
 670             return trav->prb_node != NULL ? trav->prb_node->prb_data : NULL;
 671           }
 672     }
 673   else
 674     {
 675       trav->prb_node = trav->prb_node->prb_link[0];
 676       while (trav->prb_node->prb_link[1] != NULL)
 677         trav->prb_node = trav->prb_node->prb_link[1];
 678       return trav->prb_node->prb_data;
 679     }
 680 }
 681
 682 /* Returns |trav|'s current item. */
 683 void *
 684 prb_t_cur (struct prb_traverser *trav)
 685 {
 686   assert (trav != NULL);
 687
 688   return trav->prb_node != NULL ? trav->prb_node->prb_data : NULL;
 689 }
 690
 691 /* Replaces the current item in |trav| by |new| and returns the item replaced.
 692    |trav| must not have the null item selected.
 693    The new item must not upset the ordering of the tree. */
 694 void *
 695 prb_t_replace (struct prb_traverser *trav, void *new)
 696 {
 697   void *old;
 698
 699   assert (trav != NULL && trav->prb_node != NULL && new != NULL);
 700   old = trav->prb_node->prb_data;
 701   trav->prb_node->prb_data = new;
 702   return old;
 703 }
 704
 705 /* Destroys |new| with |prb_destroy (new, destroy)|,
 706    first initializing right links in |new| that have
 707    not yet been initialized at time of call. */
 708 static void
 709 copy_error_recovery (struct prb_node *q,
 710                      struct prb_table *new, prb_item_func *destroy)
 711 {
 712   assert (q != NULL && new != NULL);
 713
 714   for (;;)
 715     {
 716       struct prb_node *p = q;
 717       q = q->prb_parent;
 718       if (q == NULL)
 719         break;
 720
 721       if (p == q->prb_link[0])
 722         q->prb_link[1] = NULL;
 723     }
 724
 725   prb_destroy (new, destroy);
 726 }
 727
 728 /* Copies |org| to a newly created tree, which is returned.
 729    If |copy != NULL|, each data item in |org| is first passed to |copy|,
 730    and the return values are inserted into the tree;
 731    |NULL| return values are taken as indications of failure.
 732    On failure, destroys the partially created new tree,
 733    applying |destroy|, if non-null, to each item in the new tree so far,
 734    and returns |NULL|.
 735    If |allocator != NULL|, it is used for allocation in the new tree.
 736    Otherwise, the same allocator used for |org| is used. */
 737 struct prb_table *
 738 prb_copy (const struct prb_table *org, prb_copy_func *copy,
 739            prb_item_func *destroy, struct libavl_allocator *allocator)
 740 {
 741   struct prb_table *new;
 742   const struct prb_node *x;
 743   struct prb_node *y;
 744
 745   assert (org != NULL);
 746   new = prb_create (org->prb_compare, org->prb_param,
 747                     allocator != NULL ? allocator : org->prb_alloc);
 748   if (new == NULL)
 749     return NULL;
 750   new->prb_count = org->prb_count;
 751   if (new->prb_count == 0)
 752     return new;
 753
 754   x = (const struct prb_node *) &org->prb_root;
 755   y = (struct prb_node *) &new->prb_root;
 756   for (;;)
 757     {
 758       while (x->prb_link[0] != NULL)
 759         {
 760           y->prb_link[0] =
 761             new->prb_alloc->libavl_malloc (new->prb_alloc,
 762                                             sizeof *y->prb_link[0]);
 763           if (y->prb_link[0] == NULL)
 764             {
 765               if (y != (struct prb_node *) &new->prb_root)
 766                 {
 767                   y->prb_data = NULL;
 768                   y->prb_link[1] = NULL;
 769                 }
 770
 771               copy_error_recovery (y, new, destroy);
 772               return NULL;
 773             }
 774           y->prb_link[0]->prb_parent = y;
 775
 776           x = x->prb_link[0];
 777           y = y->prb_link[0];
 778         }
 779       y->prb_link[0] = NULL;
 780
 781       for (;;)
 782         {
 783           y->prb_color = x->prb_color;
 784           if (copy == NULL)
 785             y->prb_data = x->prb_data;
 786           else
 787             {
 788               y->prb_data = copy (x->prb_data, org->prb_param);
 789               if (y->prb_data == NULL)
 790                 {
 791                   y->prb_link[1] = NULL;
 792                   copy_error_recovery (y, new, destroy);
 793                   return NULL;
 794                 }
 795             }
 796
 797           if (x->prb_link[1] != NULL)
 798             {
 799               y->prb_link[1] =
 800                 new->prb_alloc->libavl_malloc (new->prb_alloc,
 801                                                sizeof *y->prb_link[1]);
 802               if (y->prb_link[1] == NULL)
 803                 {
 804                   copy_error_recovery (y, new, destroy);
 805                   return NULL;
 806                 }
 807               y->prb_link[1]->prb_parent = y;
 808
 809               x = x->prb_link[1];
 810               y = y->prb_link[1];
 811               break;
 812             }
 813           else
 814             y->prb_link[1] = NULL;
 815
 816           for (;;)
 817             {
 818               const struct prb_node *w = x;
 819               x = x->prb_parent;
 820               if (x == NULL)
 821                 {
 822                   new->prb_root->prb_parent = NULL;
 823                   return new;
 824                 }
 825               y = y->prb_parent;
 826
 827               if (w == x->prb_link[0])
 828                 break;
 829             }
 830         }
 831     }
 832 }
 833
 834 /* Frees storage allocated for |tree|.
 835    If |destroy != NULL|, applies it to each data item in inorder. */
 836 void
 837 prb_destroy (struct prb_table *tree, prb_item_func *destroy)
 838 {
 839   struct prb_node *p, *q;
 840
 841   assert (tree != NULL);
 842
 843   for (p = tree->prb_root; p != NULL; p = q)
 844     if (p->prb_link[0] == NULL)
 845       {
 846         q = p->prb_link[1];
 847         if (destroy != NULL && p->prb_data != NULL)
 848           destroy (p->prb_data, tree->prb_param);
 849         tree->prb_alloc->libavl_free (tree->prb_alloc, p);
 850       }
 851     else
 852       {
 853         q = p->prb_link[0];
 854         p->prb_link[0] = q->prb_link[1];
 855         q->prb_link[1] = p;
 856       }
 857
 858   tree->prb_alloc->libavl_free (tree->prb_alloc, tree);
 859 }
 860
 861 /* Allocates |size| bytes of space using |malloc()|.
 862    Returns a null pointer if allocation fails. */
 863 void *
 864 prb_malloc (struct libavl_allocator *allocator, size_t size)
 865 {
 866   assert (allocator != NULL && size > 0);
 867   return malloc (size);
 868 }
 869
 870 /* Frees |block|. */
 871 void
 872 prb_free (struct libavl_allocator *allocator, void *block)
 873 {
 874   assert (allocator != NULL && block != NULL);
 875   free (block);
 876 }
 877
 878 /* Default memory allocator that uses |malloc()| and |free()|. */
 879 struct libavl_allocator prb_allocator_default =
 880   {
 881     prb_malloc,
 882     prb_free
 883   };
 884
 885 #undef NDEBUG
 886 #include <assert.h>
 887
 888 /* Asserts that |prb_insert()| succeeds at inserting |item| into |table|. */
 889 void
 890 (prb_assert_insert) (struct prb_table *table, void *item)
 891 {
 892   void **p = prb_probe (table, item);
 893   assert (p != NULL && *p == item);
 894 }
 895
 896 /* Asserts that |prb_delete()| really removes |item| from |table|,
 897    and returns the removed item. */
 898 void *
 899 (prb_assert_delete) (struct prb_table *table, void *item)
 900 {
 901   void *p = prb_delete (table, item);
 902   assert (p != NULL);
 903   return p;
 904 }
 905