source/texk/web2c/luatexdir/utils/avl.c

   1 /* Produced by texiweb from libavl.w. */
   2 /* *INDENT-OFF* */
   3
   4 /* libavl - library for manipulation of binary trees.
   5    Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc.
   6
   7    This program is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU General Public License as
   9    published by the Free Software Foundation; either version 2 of the
  10    License, or (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  15    See the GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, USA.
  21
  22    The author may be contacted at <blp@gnu.org> on the Internet, or
  23    write to Ben Pfaff, Stanford University, Computer Science Dept., 353
  24    Serra Mall, Stanford CA 94305, USA.
  25 */
  26
  27 #include <assert.h>
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include "avl.h"
  32
  33 /* Creates and returns a new table
  34    with comparison function |compare| using parameter |param|
  35    and memory allocator |allocator|.
  36    Returns |NULL| if memory allocation failed. */
  37 struct avl_table *avl_create(avl_comparison_func * compare, void *param,
  38                              struct libavl_allocator *allocator)
  39 {
  40     struct avl_table *tree;
  41
  42     assert(compare != NULL);
  43
  44     if (allocator == NULL)
  45         allocator = &avl_allocator_default;
  46
  47     tree = allocator->libavl_malloc(allocator, sizeof *tree);
  48     if (tree == NULL)
  49         return NULL;
  50
  51     tree->avl_root = NULL;
  52     tree->avl_compare = compare;
  53     tree->avl_param = param;
  54     tree->avl_alloc = allocator;
  55     tree->avl_count = 0;
  56     tree->avl_generation = 0;
  57
  58     return tree;
  59 }
  60
  61 /* Search |tree| for an item matching |item|, and return it if found.
  62    Otherwise return |NULL|. */
  63 void *avl_find(const struct avl_table *tree, const void *item)
  64 {
  65     const struct avl_node *p;
  66
  67     assert(tree != NULL && item != NULL);
  68     for (p = tree->avl_root; p != NULL;) {
  69         int cmp = tree->avl_compare(item, p->avl_data, tree->avl_param);
  70
  71         if (cmp < 0)
  72             p = p->avl_link[0];
  73         else if (cmp > 0)
  74             p = p->avl_link[1];
  75         else                    /* |cmp == 0| */
  76             return p->avl_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 **avl_probe(struct avl_table *tree, void *item)
  87 {
  88     struct avl_node *y, *z;     /* Top node to update balance factor, and parent. */
  89     struct avl_node *p, *q;     /* Iterator, and parent. */
  90     struct avl_node *n;         /* Newly inserted node. */
  91     struct avl_node *w;         /* New root of rebalanced subtree. */
  92     int dir;                    /* Direction to descend. */
  93
  94     unsigned char da[AVL_MAX_HEIGHT];   /* Cached comparison results. */
  95     int k = 0;                  /* Number of cached results. */
  96
  97     assert(tree != NULL && item != NULL);
  98
  99     z = (struct avl_node *) &tree->avl_root;
 100     y = tree->avl_root;
 101     dir = 0;
 102     for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) {
 103         int cmp = tree->avl_compare(item, p->avl_data, tree->avl_param);
 104         if (cmp == 0)
 105             return &p->avl_data;
 106
 107         if (p->avl_balance != 0)
 108             z = q, y = p, k = 0;
 109         dir = cmp > 0;
 110         da[k++] = (unsigned char)dir;
 111     }
 112
 113     n = q->avl_link[dir] =
 114         tree->avl_alloc->libavl_malloc(tree->avl_alloc, sizeof *n);
 115     if (n == NULL)
 116         return NULL;
 117
 118     tree->avl_count++;
 119     n->avl_data = item;
 120     n->avl_link[0] = n->avl_link[1] = NULL;
 121     n->avl_balance = 0;
 122     if (y == NULL)
 123         return &n->avl_data;
 124
 125     for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
 126         if (da[k] == 0)
 127             p->avl_balance--;
 128         else
 129             p->avl_balance++;
 130
 131     if (y->avl_balance == -2) {
 132         struct avl_node *x = y->avl_link[0];
 133         if (x->avl_balance == -1) {
 134             w = x;
 135             y->avl_link[0] = x->avl_link[1];
 136             x->avl_link[1] = y;
 137             x->avl_balance = y->avl_balance = 0;
 138         } else {
 139             assert(x->avl_balance == +1);
 140             w = x->avl_link[1];
 141             x->avl_link[1] = w->avl_link[0];
 142             w->avl_link[0] = x;
 143             y->avl_link[0] = w->avl_link[1];
 144             w->avl_link[1] = y;
 145             if (w->avl_balance == -1)
 146                 x->avl_balance = 0, y->avl_balance = +1;
 147             else if (w->avl_balance == 0)
 148                 x->avl_balance = y->avl_balance = 0;
 149             else                /* |w->avl_balance == +1| */
 150                 x->avl_balance = -1, y->avl_balance = 0;
 151             w->avl_balance = 0;
 152         }
 153     } else if (y->avl_balance == +2) {
 154         struct avl_node *x = y->avl_link[1];
 155         if (x->avl_balance == +1) {
 156             w = x;
 157             y->avl_link[1] = x->avl_link[0];
 158             x->avl_link[0] = y;
 159             x->avl_balance = y->avl_balance = 0;
 160         } else {
 161             assert(x->avl_balance == -1);
 162             w = x->avl_link[0];
 163             x->avl_link[0] = w->avl_link[1];
 164             w->avl_link[1] = x;
 165             y->avl_link[1] = w->avl_link[0];
 166             w->avl_link[0] = y;
 167             if (w->avl_balance == +1)
 168                 x->avl_balance = 0, y->avl_balance = -1;
 169             else if (w->avl_balance == 0)
 170                 x->avl_balance = y->avl_balance = 0;
 171             else                /* |w->avl_balance == -1| */
 172                 x->avl_balance = +1, y->avl_balance = 0;
 173             w->avl_balance = 0;
 174         }
 175     } else
 176         return &n->avl_data;
 177     z->avl_link[y != z->avl_link[0]] = w;
 178
 179     tree->avl_generation++;
 180     return &n->avl_data;
 181 }
 182
 183 /* Inserts |item| into |table|.
 184    Returns |NULL| if |item| was successfully inserted
 185    or if a memory allocation error occurred.
 186    Otherwise, returns the duplicate item. */
 187 void *avl_insert(struct avl_table *table, void *item)
 188 {
 189     void **p = avl_probe(table, item);
 190     return p == NULL || *p == item ? NULL : *p;
 191 }
 192
 193 /* Inserts |item| into |table|, replacing any duplicate item.
 194    Returns |NULL| if |item| was inserted without replacing a duplicate,
 195    or if a memory allocation error occurred.
 196    Otherwise, returns the item that was replaced. */
 197 void *avl_replace(struct avl_table *table, void *item)
 198 {
 199     void **p = avl_probe(table, item);
 200     if (p == NULL || *p == item)
 201         return NULL;
 202     else {
 203         void *r = *p;
 204         *p = item;
 205         return r;
 206     }
 207 }
 208
 209 /* Deletes from |tree| and returns an item matching |item|.
 210    Returns a null pointer if no matching item found. */
 211 void *avl_delete(struct avl_table *tree, const void *item)
 212 {
 213     /* Stack of nodes. */
 214     struct avl_node *pa[AVL_MAX_HEIGHT];        /* Nodes. */
 215     unsigned char da[AVL_MAX_HEIGHT];   /* |avl_link[]| indexes. */
 216     int k;                      /* Stack pointer. */
 217
 218     struct avl_node *p;         /* Traverses tree to find node to delete. */
 219     int cmp;                    /* Result of comparison between |item| and |p|. */
 220
 221     void *res;
 222
 223     assert(tree != NULL && item != NULL);
 224
 225     k = 0;
 226     p = (struct avl_node *) &tree->avl_root;
 227     for (cmp = -1; cmp != 0;
 228          cmp = tree->avl_compare(item, p->avl_data, tree->avl_param)) {
 229         int dir = cmp > 0;
 230
 231         pa[k] = p;
 232         da[k++] = (unsigned char)dir;
 233
 234         p = p->avl_link[dir];
 235         if (p == NULL)
 236             return NULL;
 237     }
 238     res = p->avl_data;
 239
 240     if (p->avl_link[1] == NULL)
 241         pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
 242     else {
 243         struct avl_node *r = p->avl_link[1];
 244         if (r->avl_link[0] == NULL) {
 245             r->avl_link[0] = p->avl_link[0];
 246             r->avl_balance = p->avl_balance;
 247             pa[k - 1]->avl_link[da[k - 1]] = r;
 248             da[k] = 1;
 249             pa[k++] = r;
 250         } else {
 251             struct avl_node *s;
 252             int j = k++;
 253
 254             for (;;) {
 255                 da[k] = 0;
 256                 pa[k++] = r;
 257                 s = r->avl_link[0];
 258                 if (s->avl_link[0] == NULL)
 259                     break;
 260
 261                 r = s;
 262             }
 263
 264             s->avl_link[0] = p->avl_link[0];
 265             r->avl_link[0] = s->avl_link[1];
 266             s->avl_link[1] = p->avl_link[1];
 267             s->avl_balance = p->avl_balance;
 268
 269             pa[j - 1]->avl_link[da[j - 1]] = s;
 270             da[j] = 1;
 271             pa[j] = s;
 272         }
 273     }
 274
 275     tree->avl_alloc->libavl_free(tree->avl_alloc, p);
 276
 277     assert(k > 0);
 278     while (--k > 0) {
 279         struct avl_node *y = pa[k];
 280
 281         if (da[k] == 0) {
 282             y->avl_balance++;
 283             if (y->avl_balance == +1)
 284                 break;
 285             else if (y->avl_balance == +2) {
 286                 struct avl_node *x = y->avl_link[1];
 287                 if (x->avl_balance == -1) {
 288                     struct avl_node *w;
 289                     assert(x->avl_balance == -1);
 290                     w = x->avl_link[0];
 291                     x->avl_link[0] = w->avl_link[1];
 292                     w->avl_link[1] = x;
 293                     y->avl_link[1] = w->avl_link[0];
 294                     w->avl_link[0] = y;
 295                     if (w->avl_balance == +1)
 296                         x->avl_balance = 0, y->avl_balance = -1;
 297                     else if (w->avl_balance == 0)
 298                         x->avl_balance = y->avl_balance = 0;
 299                     else        /* |w->avl_balance == -1| */
 300                         x->avl_balance = +1, y->avl_balance = 0;
 301                     w->avl_balance = 0;
 302                     pa[k - 1]->avl_link[da[k - 1]] = w;
 303                 } else {
 304                     y->avl_link[1] = x->avl_link[0];
 305                     x->avl_link[0] = y;
 306                     pa[k - 1]->avl_link[da[k - 1]] = x;
 307                     if (x->avl_balance == 0) {
 308                         x->avl_balance = -1;
 309                         y->avl_balance = +1;
 310                         break;
 311                     } else
 312                         x->avl_balance = y->avl_balance = 0;
 313                 }
 314             }
 315         } else {
 316             y->avl_balance--;
 317             if (y->avl_balance == -1)
 318                 break;
 319             else if (y->avl_balance == -2) {
 320                 struct avl_node *x = y->avl_link[0];
 321                 if (x->avl_balance == +1) {
 322                     struct avl_node *w;
 323                     assert(x->avl_balance == +1);
 324                     w = x->avl_link[1];
 325                     x->avl_link[1] = w->avl_link[0];
 326                     w->avl_link[0] = x;
 327                     y->avl_link[0] = w->avl_link[1];
 328                     w->avl_link[1] = y;
 329                     if (w->avl_balance == -1)
 330                         x->avl_balance = 0, y->avl_balance = +1;
 331                     else if (w->avl_balance == 0)
 332                         x->avl_balance = y->avl_balance = 0;
 333                     else        /* |w->avl_balance == +1| */
 334                         x->avl_balance = -1, y->avl_balance = 0;
 335                     w->avl_balance = 0;
 336                     pa[k - 1]->avl_link[da[k - 1]] = w;
 337                 } else {
 338                     y->avl_link[0] = x->avl_link[1];
 339                     x->avl_link[1] = y;
 340                     pa[k - 1]->avl_link[da[k - 1]] = x;
 341                     if (x->avl_balance == 0) {
 342                         x->avl_balance = +1;
 343                         y->avl_balance = -1;
 344                         break;
 345                     } else
 346                         x->avl_balance = y->avl_balance = 0;
 347                 }
 348             }
 349         }
 350     }
 351
 352     tree->avl_count--;
 353     tree->avl_generation++;
 354     return res;
 355 }
 356
 357 /* Refreshes the stack of parent pointers in |trav|
 358    and updates its generation number. */
 359 static void trav_refresh(struct avl_traverser *trav)
 360 {
 361     assert(trav != NULL);
 362
 363     trav->avl_generation = trav->avl_table->avl_generation;
 364
 365     if (trav->avl_node != NULL) {
 366         avl_comparison_func *cmp = trav->avl_table->avl_compare;
 367         void *param = trav->avl_table->avl_param;
 368         struct avl_node *node = trav->avl_node;
 369         struct avl_node *i;
 370
 371         trav->avl_height = 0;
 372         for (i = trav->avl_table->avl_root; i != node;) {
 373             assert(trav->avl_height < AVL_MAX_HEIGHT);
 374             assert(i != NULL);
 375
 376             trav->avl_stack[trav->avl_height++] = i;
 377             i = i->avl_link[cmp(node->avl_data, i->avl_data, param) > 0];
 378         }
 379     }
 380 }
 381
 382 /* Initializes |trav| for use with |tree|
 383    and selects the null node. */
 384 void avl_t_init(struct avl_traverser *trav, struct avl_table *tree)
 385 {
 386     trav->avl_table = tree;
 387     trav->avl_node = NULL;
 388     trav->avl_height = 0;
 389     trav->avl_generation = tree->avl_generation;
 390 }
 391
 392 /* Initializes |trav| for |tree|
 393    and selects and returns a pointer to its least-valued item.
 394    Returns |NULL| if |tree| contains no nodes. */
 395 void *avl_t_first(struct avl_traverser *trav, struct avl_table *tree)
 396 {
 397     struct avl_node *x;
 398
 399     assert(tree != NULL && trav != NULL);
 400
 401     trav->avl_table = tree;
 402     trav->avl_height = 0;
 403     trav->avl_generation = tree->avl_generation;
 404
 405     x = tree->avl_root;
 406     if (x != NULL)
 407         while (x->avl_link[0] != NULL) {
 408             assert(trav->avl_height < AVL_MAX_HEIGHT);
 409             trav->avl_stack[trav->avl_height++] = x;
 410             x = x->avl_link[0];
 411         }
 412     trav->avl_node = x;
 413
 414     return x != NULL ? x->avl_data : NULL;
 415 }
 416
 417 /* Initializes |trav| for |tree|
 418    and selects and returns a pointer to its greatest-valued item.
 419    Returns |NULL| if |tree| contains no nodes. */
 420 void *avl_t_last(struct avl_traverser *trav, struct avl_table *tree)
 421 {
 422     struct avl_node *x;
 423
 424     assert(tree != NULL && trav != NULL);
 425
 426     trav->avl_table = tree;
 427     trav->avl_height = 0;
 428     trav->avl_generation = tree->avl_generation;
 429
 430     x = tree->avl_root;
 431     if (x != NULL)
 432         while (x->avl_link[1] != NULL) {
 433             assert(trav->avl_height < AVL_MAX_HEIGHT);
 434             trav->avl_stack[trav->avl_height++] = x;
 435             x = x->avl_link[1];
 436         }
 437     trav->avl_node = x;
 438
 439     return x != NULL ? x->avl_data : NULL;
 440 }
 441
 442 /* Searches for |item| in |tree|.
 443    If found, initializes |trav| to the item found and returns the item
 444    as well.
 445    If there is no matching item, initializes |trav| to the null item
 446    and returns |NULL|. */
 447 void *avl_t_find(struct avl_traverser *trav, struct avl_table *tree, void *item)
 448 {
 449     struct avl_node *p, *q;
 450
 451     assert(trav != NULL && tree != NULL && item != NULL);
 452     trav->avl_table = tree;
 453     trav->avl_height = 0;
 454     trav->avl_generation = tree->avl_generation;
 455     for (p = tree->avl_root; p != NULL; p = q) {
 456         int cmp = tree->avl_compare(item, p->avl_data, tree->avl_param);
 457
 458         if (cmp < 0)
 459             q = p->avl_link[0];
 460         else if (cmp > 0)
 461             q = p->avl_link[1];
 462         else {                  /* |cmp == 0| */
 463
 464             trav->avl_node = p;
 465             return p->avl_data;
 466         }
 467
 468         assert(trav->avl_height < AVL_MAX_HEIGHT);
 469         trav->avl_stack[trav->avl_height++] = p;
 470     }
 471
 472     trav->avl_height = 0;
 473     trav->avl_node = NULL;
 474     return NULL;
 475 }
 476
 477 /* Attempts to insert |item| into |tree|.
 478    If |item| is inserted successfully, it is returned and |trav| is
 479    initialized to its location.
 480    If a duplicate is found, it is returned and |trav| is initialized to
 481    its location.  No replacement of the item occurs.
 482    If a memory allocation failure occurs, |NULL| is returned and |trav|
 483    is initialized to the null item. */
 484 void *avl_t_insert(struct avl_traverser *trav, struct avl_table *tree,
 485                    void *item)
 486 {
 487     void **p;
 488
 489     assert(trav != NULL && tree != NULL && item != NULL);
 490
 491     p = avl_probe(tree, item);
 492     if (p != NULL) {
 493         trav->avl_table = tree;
 494         trav->avl_node = ((struct avl_node *)
 495                           ((char *) p - offsetof(struct avl_node, avl_data)));
 496         trav->avl_generation = tree->avl_generation - 1;
 497         return *p;
 498     } else {
 499         avl_t_init(trav, tree);
 500         return NULL;
 501     }
 502 }
 503
 504 /* Initializes |trav| to have the same current node as |src|. */
 505 void *avl_t_copy(struct avl_traverser *trav, const struct avl_traverser *src)
 506 {
 507     assert(trav != NULL && src != NULL);
 508
 509     if (trav != src) {
 510         trav->avl_table = src->avl_table;
 511         trav->avl_node = src->avl_node;
 512         trav->avl_generation = src->avl_generation;
 513         if (trav->avl_generation == trav->avl_table->avl_generation) {
 514             trav->avl_height = src->avl_height;
 515             memcpy(trav->avl_stack, (const void *) src->avl_stack,
 516                    sizeof *trav->avl_stack * trav->avl_height);
 517         }
 518     }
 519
 520     return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL;
 521 }
 522
 523 /* Returns the next data item in inorder
 524    within the tree being traversed with |trav|,
 525    or if there are no more data items returns |NULL|. */
 526 void *avl_t_next(struct avl_traverser *trav)
 527 {
 528     struct avl_node *x;
 529
 530     assert(trav != NULL);
 531
 532     if (trav->avl_generation != trav->avl_table->avl_generation)
 533         trav_refresh(trav);
 534
 535     x = trav->avl_node;
 536     if (x == NULL) {
 537         return avl_t_first(trav, trav->avl_table);
 538     } else if (x->avl_link[1] != NULL) {
 539         assert(trav->avl_height < AVL_MAX_HEIGHT);
 540         trav->avl_stack[trav->avl_height++] = x;
 541         x = x->avl_link[1];
 542
 543         while (x->avl_link[0] != NULL) {
 544             assert(trav->avl_height < AVL_MAX_HEIGHT);
 545             trav->avl_stack[trav->avl_height++] = x;
 546             x = x->avl_link[0];
 547         }
 548     } else {
 549         struct avl_node *y;
 550
 551         do {
 552             if (trav->avl_height == 0) {
 553                 trav->avl_node = NULL;
 554                 return NULL;
 555             }
 556
 557             y = x;
 558             x = trav->avl_stack[--trav->avl_height];
 559         }
 560         while (y == x->avl_link[1]);
 561     }
 562     trav->avl_node = x;
 563
 564     return x->avl_data;
 565 }
 566
 567 /* Returns the previous data item in inorder
 568    within the tree being traversed with |trav|,
 569    or if there are no more data items returns |NULL|. */
 570 void *avl_t_prev(struct avl_traverser *trav)
 571 {
 572     struct avl_node *x;
 573
 574     assert(trav != NULL);
 575
 576     if (trav->avl_generation != trav->avl_table->avl_generation)
 577         trav_refresh(trav);
 578
 579     x = trav->avl_node;
 580     if (x == NULL) {
 581         return avl_t_last(trav, trav->avl_table);
 582     } else if (x->avl_link[0] != NULL) {
 583         assert(trav->avl_height < AVL_MAX_HEIGHT);
 584         trav->avl_stack[trav->avl_height++] = x;
 585         x = x->avl_link[0];
 586
 587         while (x->avl_link[1] != NULL) {
 588             assert(trav->avl_height < AVL_MAX_HEIGHT);
 589             trav->avl_stack[trav->avl_height++] = x;
 590             x = x->avl_link[1];
 591         }
 592     } else {
 593         struct avl_node *y;
 594
 595         do {
 596             if (trav->avl_height == 0) {
 597                 trav->avl_node = NULL;
 598                 return NULL;
 599             }
 600
 601             y = x;
 602             x = trav->avl_stack[--trav->avl_height];
 603         }
 604         while (y == x->avl_link[0]);
 605     }
 606     trav->avl_node = x;
 607
 608     return x->avl_data;
 609 }
 610
 611 /* Returns |trav|'s current item. */
 612 void *avl_t_cur(struct avl_traverser *trav)
 613 {
 614     assert(trav != NULL);
 615
 616     return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL;
 617 }
 618
 619 /* Replaces the current item in |trav| by |new| and returns the item replaced.
 620    |trav| must not have the null item selected.
 621    The new item must not upset the ordering of the tree. */
 622 void *avl_t_replace(struct avl_traverser *trav, void *new)
 623 {
 624     void *old;
 625
 626     assert(trav != NULL && trav->avl_node != NULL && new != NULL);
 627     old = trav->avl_node->avl_data;
 628     trav->avl_node->avl_data = new;
 629     return old;
 630 }
 631
 632 /* Destroys |new| with |avl_destroy (new, destroy)|,
 633    first setting right links of nodes in |stack| within |new|
 634    to null pointers to avoid touching uninitialized data. */
 635 static void
 636 copy_error_recovery(struct avl_node **stack, int height,
 637                     struct avl_table *new, avl_item_func * destroy)
 638 {
 639     assert(stack != NULL && height >= 0 && new != NULL);
 640
 641     for (; height > 2; height -= 2)
 642         stack[height - 1]->avl_link[1] = NULL;
 643     avl_destroy(new, destroy);
 644 }
 645
 646 /* Copies |org| to a newly created tree, which is returned.
 647    If |copy != NULL|, each data item in |org| is first passed to |copy|,
 648    and the return values are inserted into the tree,
 649    with |NULL| return values taken as indications of failure.
 650    On failure, destroys the partially created new tree,
 651    applying |destroy|, if non-null, to each item in the new tree so far,
 652    and returns |NULL|.
 653    If |allocator != NULL|, it is used for allocation in the new tree.
 654    Otherwise, the same allocator used for |org| is used. */
 655 struct avl_table *avl_copy(const struct avl_table *org, avl_copy_func * copy,
 656                            avl_item_func * destroy,
 657                            struct libavl_allocator *allocator)
 658 {
 659     struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)];
 660     int height = 0;
 661
 662     struct avl_table *new;
 663     struct avl_node org_head, *x, *y;
 664
 665     assert(org != NULL);
 666     new = avl_create(org->avl_compare, org->avl_param,
 667                      allocator != NULL ? allocator : org->avl_alloc);
 668     if (new == NULL)
 669         return NULL;
 670     new->avl_count = org->avl_count;
 671     if (new->avl_count == 0)
 672         return new;
 673
 674     org_head.avl_link[0] = (struct avl_node *) org->avl_root;
 675     x = &org_head;
 676     y = (struct avl_node *) &new->avl_root;
 677     for (;;) {
 678         while (x->avl_link[0] != NULL) {
 679             assert(height < 2 * (AVL_MAX_HEIGHT + 1));
 680
 681             y->avl_link[0] =
 682                 new->avl_alloc->libavl_malloc(new->avl_alloc,
 683                                               sizeof *y->avl_link[0]);
 684             if (y->avl_link[0] == NULL) {
 685                 if (y != (struct avl_node *) &new->avl_root) {
 686                     y->avl_data = NULL;
 687                     y->avl_link[1] = NULL;
 688                 }
 689
 690                 copy_error_recovery(stack, height, new, destroy);
 691                 return NULL;
 692             }
 693
 694             stack[height++] = x;
 695             stack[height++] = y;
 696             x = x->avl_link[0];
 697             y = y->avl_link[0];
 698         }
 699         y->avl_link[0] = NULL;
 700
 701         for (;;) {
 702             y->avl_balance = x->avl_balance;
 703             if (copy == NULL)
 704                 y->avl_data = x->avl_data;
 705             else {
 706                 y->avl_data = copy(x->avl_data, org->avl_param);
 707                 if (y->avl_data == NULL) {
 708                     y->avl_link[1] = NULL;
 709                     copy_error_recovery(stack, height, new, destroy);
 710                     return NULL;
 711                 }
 712             }
 713
 714             if (x->avl_link[1] != NULL) {
 715                 y->avl_link[1] =
 716                     new->avl_alloc->libavl_malloc(new->avl_alloc,
 717                                                   sizeof *y->avl_link[1]);
 718                 if (y->avl_link[1] == NULL) {
 719                     copy_error_recovery(stack, height, new, destroy);
 720                     return NULL;
 721                 }
 722
 723                 x = x->avl_link[1];
 724                 y = y->avl_link[1];
 725                 break;
 726             } else
 727                 y->avl_link[1] = NULL;
 728
 729             if (height <= 2)
 730                 return new;
 731
 732             y = stack[--height];
 733             x = stack[--height];
 734         }
 735     }
 736 }
 737
 738 /* Frees storage allocated for |tree|.
 739    If |destroy != NULL|, applies it to each data item in inorder. */
 740 void avl_destroy(struct avl_table *tree, avl_item_func * destroy)
 741 {
 742     struct avl_node *p, *q;
 743
 744     assert(tree != NULL);
 745
 746     for (p = tree->avl_root; p != NULL; p = q)
 747         if (p->avl_link[0] == NULL) {
 748             q = p->avl_link[1];
 749             if (destroy != NULL && p->avl_data != NULL)
 750                 destroy(p->avl_data, tree->avl_param);
 751             tree->avl_alloc->libavl_free(tree->avl_alloc, p);
 752         } else {
 753             q = p->avl_link[0];
 754             p->avl_link[0] = q->avl_link[1];
 755             q->avl_link[1] = p;
 756         }
 757
 758     tree->avl_alloc->libavl_free(tree->avl_alloc, tree);
 759 }
 760
 761 /* Allocates |size| bytes of space using |malloc()|.
 762    Returns a null pointer if allocation fails. */
 763 void *avl_malloc(struct libavl_allocator *allocator, size_t size)
 764 {
 765     assert(allocator != NULL && size > 0);
 766     return malloc(size);
 767 }
 768
 769 /* Frees |block|. */
 770 void avl_free(struct libavl_allocator *allocator, void *block)
 771 {
 772     assert(allocator != NULL && block != NULL);
 773     free(block);
 774 }
 775
 776 /* Default memory allocator that uses |malloc()| and |free()|. */
 777 struct libavl_allocator avl_allocator_default = {
 778     avl_malloc,
 779     avl_free
 780 };
 781
 782 #undef NDEBUG
 783 #include <assert.h>
 784
 785 /* Asserts that |avl_insert()| succeeds at inserting |item| into |table|. */
 786 void
 787  (avl_assert_insert) (struct avl_table * table, void *item) {
 788     void **p = avl_probe(table, item);
 789     assert(p != NULL && *p == item);
 790 }
 791
 792 /* Asserts that |avl_delete()| really removes |item| from |table|,
 793    and returns the removed item. */
 794 void *(avl_assert_delete) (struct avl_table * table, void *item) {
 795     void *p = avl_delete(table, item);
 796     assert(p != NULL);
 797     return p;
 798 }
 799 /* *INDENT-ON* */