Back to index

tetex-bin  3.0
avl.c
Go to the documentation of this file.
00001 /* Produced by texiweb from libavl.w on 2003/01/06 at 18:07. */
00002 
00003 /* libavl - library for manipulation of binary trees.
00004    Copyright (C) 1998-2002 Free Software Foundation, Inc.
00005 
00006    This program is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU General Public License as
00008    published by the Free Software Foundation; either version 2 of the
00009    License, or (at your option) any later version.
00010 
00011    This program is distributed in the hope that it will be useful, but
00012    WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00014    See the GNU General Public License for more details.
00015 
00016    You should have received a copy of the GNU General Public License
00017    along with this program; if not, write to the Free Software
00018    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
00019    02111-1307, USA.
00020 
00021    The author may be contacted at <blp@gnu.org> on the Internet, or
00022    write to Ben Pfaff, Stanford University, Computer Science Dept., 353
00023    Serra Mall, Stanford CA 94305, USA.
00024 */
00025 
00026 #include <assert.h>
00027 #include <stdio.h>
00028 #include <stdlib.h>
00029 #include <string.h>
00030 #include "avl.h"
00031 
00032 /* Creates and returns a new table
00033    with comparison function |compare| using parameter |param|
00034    and memory allocator |allocator|.
00035    Returns |NULL| if memory allocation failed. */
00036 struct avl_table *
00037 avl_create (avl_comparison_func *compare, void *param,
00038             struct libavl_allocator *allocator)
00039 {
00040   struct avl_table *tree;
00041 
00042   assert (compare != NULL);
00043 
00044   if (allocator == NULL)
00045     allocator = &avl_allocator_default;
00046 
00047   tree = allocator->libavl_malloc (allocator, sizeof *tree);
00048   if (tree == NULL)
00049     return NULL;
00050 
00051   tree->avl_root = NULL;
00052   tree->avl_compare = compare;
00053   tree->avl_param = param;
00054   tree->avl_alloc = allocator;
00055   tree->avl_count = 0;
00056   tree->avl_generation = 0;
00057 
00058   return tree;
00059 }
00060 
00061 /* Search |tree| for an item matching |item|, and return it if found.
00062    Otherwise return |NULL|. */
00063 void *
00064 avl_find (const struct avl_table *tree, const void *item)
00065 {
00066   const struct avl_node *p;
00067 
00068   assert (tree != NULL && item != NULL);
00069   for (p = tree->avl_root; p != NULL; )
00070     {
00071       int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param);
00072 
00073       if (cmp < 0)
00074         p = p->avl_link[0];
00075       else if (cmp > 0)
00076         p = p->avl_link[1];
00077       else /* |cmp == 0| */
00078         return p->avl_data;
00079     }
00080 
00081   return NULL;
00082 }
00083 
00084 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
00085    If a duplicate item is found in the tree,
00086    returns a pointer to the duplicate without inserting |item|.
00087    Returns |NULL| in case of memory allocation failure. */
00088 void **
00089 avl_probe (struct avl_table *tree, void *item)
00090 {
00091   struct avl_node *y, *z; /* Top node to update balance factor, and parent. */
00092   struct avl_node *p, *q; /* Iterator, and parent. */
00093   struct avl_node *n;     /* Newly inserted node. */
00094   struct avl_node *w;     /* New root of rebalanced subtree. */
00095   int dir;                /* Direction to descend. */
00096 
00097   unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
00098   int k = 0;              /* Number of cached results. */
00099 
00100   assert (tree != NULL && item != NULL);
00101 
00102   z = (struct avl_node *) &tree->avl_root;
00103   y = tree->avl_root;
00104   dir = 0;
00105   for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir])
00106     {
00107       int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param);
00108       if (cmp == 0)
00109         return &p->avl_data;
00110 
00111       if (p->avl_balance != 0)
00112         z = q, y = p, k = 0;
00113       da[k++] = dir = cmp > 0;
00114     }
00115 
00116   n = q->avl_link[dir] =
00117     tree->avl_alloc->libavl_malloc (tree->avl_alloc, sizeof *n);
00118   if (n == NULL)
00119     return NULL;
00120 
00121   tree->avl_count++;
00122   n->avl_data = item;
00123   n->avl_link[0] = n->avl_link[1] = NULL;
00124   n->avl_balance = 0;
00125   if (y == NULL)
00126     return &n->avl_data;
00127 
00128   for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
00129     if (da[k] == 0)
00130       p->avl_balance--;
00131     else
00132       p->avl_balance++;
00133 
00134   if (y->avl_balance == -2)
00135     {
00136       struct avl_node *x = y->avl_link[0];
00137       if (x->avl_balance == -1)
00138         {
00139           w = x;
00140           y->avl_link[0] = x->avl_link[1];
00141           x->avl_link[1] = y;
00142           x->avl_balance = y->avl_balance = 0;
00143         }
00144       else
00145         {
00146           assert (x->avl_balance == +1);
00147           w = x->avl_link[1];
00148           x->avl_link[1] = w->avl_link[0];
00149           w->avl_link[0] = x;
00150           y->avl_link[0] = w->avl_link[1];
00151           w->avl_link[1] = y;
00152           if (w->avl_balance == -1)
00153             x->avl_balance = 0, y->avl_balance = +1;
00154           else if (w->avl_balance == 0)
00155             x->avl_balance = y->avl_balance = 0;
00156           else /* |w->avl_balance == +1| */
00157             x->avl_balance = -1, y->avl_balance = 0;
00158           w->avl_balance = 0;
00159         }
00160     }
00161   else if (y->avl_balance == +2)
00162     {
00163       struct avl_node *x = y->avl_link[1];
00164       if (x->avl_balance == +1)
00165         {
00166           w = x;
00167           y->avl_link[1] = x->avl_link[0];
00168           x->avl_link[0] = y;
00169           x->avl_balance = y->avl_balance = 0;
00170         }
00171       else
00172         {
00173           assert (x->avl_balance == -1);
00174           w = x->avl_link[0];
00175           x->avl_link[0] = w->avl_link[1];
00176           w->avl_link[1] = x;
00177           y->avl_link[1] = w->avl_link[0];
00178           w->avl_link[0] = y;
00179           if (w->avl_balance == +1)
00180             x->avl_balance = 0, y->avl_balance = -1;
00181           else if (w->avl_balance == 0)
00182             x->avl_balance = y->avl_balance = 0;
00183           else /* |w->avl_balance == -1| */
00184             x->avl_balance = +1, y->avl_balance = 0;
00185           w->avl_balance = 0;
00186         }
00187     }
00188   else
00189     return &n->avl_data;
00190   z->avl_link[y != z->avl_link[0]] = w;
00191 
00192   tree->avl_generation++;
00193   return &n->avl_data;
00194 }
00195 
00196 /* Inserts |item| into |table|.
00197    Returns |NULL| if |item| was successfully inserted
00198    or if a memory allocation error occurred.
00199    Otherwise, returns the duplicate item. */
00200 void *
00201 avl_insert (struct avl_table *table, void *item)
00202 {
00203   void **p = avl_probe (table, item);
00204   return p == NULL || *p == item ? NULL : *p;
00205 }
00206 
00207 /* Inserts |item| into |table|, replacing any duplicate item.
00208    Returns |NULL| if |item| was inserted without replacing a duplicate,
00209    or if a memory allocation error occurred.
00210    Otherwise, returns the item that was replaced. */
00211 void *
00212 avl_replace (struct avl_table *table, void *item)
00213 {
00214   void **p = avl_probe (table, item);
00215   if (p == NULL || *p == item)
00216     return NULL;
00217   else
00218     {
00219       void *r = *p;
00220       *p = item;
00221       return r;
00222     }
00223 }
00224 
00225 /* Deletes from |tree| and returns an item matching |item|.
00226    Returns a null pointer if no matching item found. */
00227 void *
00228 avl_delete (struct avl_table *tree, const void *item)
00229 {
00230   /* Stack of nodes. */
00231   struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */
00232   unsigned char da[AVL_MAX_HEIGHT];    /* |avl_link[]| indexes. */
00233   int k;                               /* Stack pointer. */
00234 
00235   struct avl_node *p;   /* Traverses tree to find node to delete. */
00236   int cmp;              /* Result of comparison between |item| and |p|. */
00237 
00238   assert (tree != NULL && item != NULL);
00239 
00240   k = 0;
00241   p = (struct avl_node *) &tree->avl_root;
00242   for (cmp = -1; cmp != 0;
00243        cmp = tree->avl_compare (item, p->avl_data, tree->avl_param))
00244     {
00245       int dir = cmp > 0;
00246 
00247       pa[k] = p;
00248       da[k++] = dir;
00249 
00250       p = p->avl_link[dir];
00251       if (p == NULL)
00252         return NULL;
00253     }
00254   item = p->avl_data;
00255 
00256   if (p->avl_link[1] == NULL)
00257     pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
00258   else
00259     {
00260       struct avl_node *r = p->avl_link[1];
00261       if (r->avl_link[0] == NULL)
00262         {
00263           r->avl_link[0] = p->avl_link[0];
00264           r->avl_balance = p->avl_balance;
00265           pa[k - 1]->avl_link[da[k - 1]] = r;
00266           da[k] = 1;
00267           pa[k++] = r;
00268         }
00269       else
00270         {
00271           struct avl_node *s;
00272           int j = k++;
00273 
00274           for (;;)
00275             {
00276               da[k] = 0;
00277               pa[k++] = r;
00278               s = r->avl_link[0];
00279               if (s->avl_link[0] == NULL)
00280                 break;
00281 
00282               r = s;
00283             }
00284 
00285           s->avl_link[0] = p->avl_link[0];
00286           r->avl_link[0] = s->avl_link[1];
00287           s->avl_link[1] = p->avl_link[1];
00288           s->avl_balance = p->avl_balance;
00289 
00290           pa[j - 1]->avl_link[da[j - 1]] = s;
00291           da[j] = 1;
00292           pa[j] = s;
00293         }
00294     }
00295 
00296   tree->avl_alloc->libavl_free (tree->avl_alloc, p);
00297 
00298   assert (k > 0);
00299   while (--k > 0)
00300     {
00301       struct avl_node *y = pa[k];
00302 
00303       if (da[k] == 0)
00304         {
00305           y->avl_balance++;
00306           if (y->avl_balance == +1)
00307             break;
00308           else if (y->avl_balance == +2)
00309             {
00310               struct avl_node *x = y->avl_link[1];
00311               if (x->avl_balance == -1)
00312                 {
00313                   struct avl_node *w;
00314                   assert (x->avl_balance == -1);
00315                   w = x->avl_link[0];
00316                   x->avl_link[0] = w->avl_link[1];
00317                   w->avl_link[1] = x;
00318                   y->avl_link[1] = w->avl_link[0];
00319                   w->avl_link[0] = y;
00320                   if (w->avl_balance == +1)
00321                     x->avl_balance = 0, y->avl_balance = -1;
00322                   else if (w->avl_balance == 0)
00323                     x->avl_balance = y->avl_balance = 0;
00324                   else /* |w->avl_balance == -1| */
00325                     x->avl_balance = +1, y->avl_balance = 0;
00326                   w->avl_balance = 0;
00327                   pa[k - 1]->avl_link[da[k - 1]] = w;
00328                 }
00329               else
00330                 {
00331                   y->avl_link[1] = x->avl_link[0];
00332                   x->avl_link[0] = y;
00333                   pa[k - 1]->avl_link[da[k - 1]] = x;
00334                   if (x->avl_balance == 0)
00335                     {
00336                       x->avl_balance = -1;
00337                       y->avl_balance = +1;
00338                       break;
00339                     }
00340                   else
00341                     x->avl_balance = y->avl_balance = 0;
00342                 }
00343             }
00344         }
00345       else
00346         {
00347           y->avl_balance--;
00348           if (y->avl_balance == -1)
00349             break;
00350           else if (y->avl_balance == -2)
00351             {
00352               struct avl_node *x = y->avl_link[0];
00353               if (x->avl_balance == +1)
00354                 {
00355                   struct avl_node *w;
00356                   assert (x->avl_balance == +1);
00357                   w = x->avl_link[1];
00358                   x->avl_link[1] = w->avl_link[0];
00359                   w->avl_link[0] = x;
00360                   y->avl_link[0] = w->avl_link[1];
00361                   w->avl_link[1] = y;
00362                   if (w->avl_balance == -1)
00363                     x->avl_balance = 0, y->avl_balance = +1;
00364                   else if (w->avl_balance == 0)
00365                     x->avl_balance = y->avl_balance = 0;
00366                   else /* |w->avl_balance == +1| */
00367                     x->avl_balance = -1, y->avl_balance = 0;
00368                   w->avl_balance = 0;
00369                   pa[k - 1]->avl_link[da[k - 1]] = w;
00370                 }
00371               else
00372                 {
00373                   y->avl_link[0] = x->avl_link[1];
00374                   x->avl_link[1] = y;
00375                   pa[k - 1]->avl_link[da[k - 1]] = x;
00376                   if (x->avl_balance == 0)
00377                     {
00378                       x->avl_balance = +1;
00379                       y->avl_balance = -1;
00380                       break;
00381                     }
00382                   else
00383                     x->avl_balance = y->avl_balance = 0;
00384                 }
00385             }
00386         }
00387     }
00388 
00389   tree->avl_count--;
00390   tree->avl_generation++;
00391   return (void *) item;
00392 }
00393 
00394 /* Refreshes the stack of parent pointers in |trav|
00395    and updates its generation number. */
00396 static void
00397 trav_refresh (struct avl_traverser *trav)
00398 {
00399   assert (trav != NULL);
00400 
00401   trav->avl_generation = trav->avl_table->avl_generation;
00402 
00403   if (trav->avl_node != NULL)
00404     {
00405       avl_comparison_func *cmp = trav->avl_table->avl_compare;
00406       void *param = trav->avl_table->avl_param;
00407       struct avl_node *node = trav->avl_node;
00408       struct avl_node *i;
00409 
00410       trav->avl_height = 0;
00411       for (i = trav->avl_table->avl_root; i != node; )
00412         {
00413           assert (trav->avl_height < AVL_MAX_HEIGHT);
00414           assert (i != NULL);
00415 
00416           trav->avl_stack[trav->avl_height++] = i;
00417           i = i->avl_link[cmp (node->avl_data, i->avl_data, param) > 0];
00418         }
00419     }
00420 }
00421 
00422 /* Initializes |trav| for use with |tree|
00423    and selects the null node. */
00424 void
00425 avl_t_init (struct avl_traverser *trav, struct avl_table *tree)
00426 {
00427   trav->avl_table = tree;
00428   trav->avl_node = NULL;
00429   trav->avl_height = 0;
00430   trav->avl_generation = tree->avl_generation;
00431 }
00432 
00433 /* Initializes |trav| for |tree|
00434    and selects and returns a pointer to its least-valued item.
00435    Returns |NULL| if |tree| contains no nodes. */
00436 void *
00437 avl_t_first (struct avl_traverser *trav, struct avl_table *tree)
00438 {
00439   struct avl_node *x;
00440 
00441   assert (tree != NULL && trav != NULL);
00442 
00443   trav->avl_table = tree;
00444   trav->avl_height = 0;
00445   trav->avl_generation = tree->avl_generation;
00446 
00447   x = tree->avl_root;
00448   if (x != NULL)
00449     while (x->avl_link[0] != NULL)
00450       {
00451         assert (trav->avl_height < AVL_MAX_HEIGHT);
00452         trav->avl_stack[trav->avl_height++] = x;
00453         x = x->avl_link[0];
00454       }
00455   trav->avl_node = x;
00456 
00457   return x != NULL ? x->avl_data : NULL;
00458 }
00459 
00460 /* Initializes |trav| for |tree|
00461    and selects and returns a pointer to its greatest-valued item.
00462    Returns |NULL| if |tree| contains no nodes. */
00463 void *
00464 avl_t_last (struct avl_traverser *trav, struct avl_table *tree)
00465 {
00466   struct avl_node *x;
00467 
00468   assert (tree != NULL && trav != NULL);
00469 
00470   trav->avl_table = tree;
00471   trav->avl_height = 0;
00472   trav->avl_generation = tree->avl_generation;
00473 
00474   x = tree->avl_root;
00475   if (x != NULL)
00476     while (x->avl_link[1] != NULL)
00477       {
00478         assert (trav->avl_height < AVL_MAX_HEIGHT);
00479         trav->avl_stack[trav->avl_height++] = x;
00480         x = x->avl_link[1];
00481       }
00482   trav->avl_node = x;
00483 
00484   return x != NULL ? x->avl_data : NULL;
00485 }
00486 
00487 /* Searches for |item| in |tree|.
00488    If found, initializes |trav| to the item found and returns the item
00489    as well.
00490    If there is no matching item, initializes |trav| to the null item
00491    and returns |NULL|. */
00492 void *
00493 avl_t_find (struct avl_traverser *trav, struct avl_table *tree, void *item)
00494 {
00495   struct avl_node *p, *q;
00496 
00497   assert (trav != NULL && tree != NULL && item != NULL);
00498   trav->avl_table = tree;
00499   trav->avl_height = 0;
00500   trav->avl_generation = tree->avl_generation;
00501   for (p = tree->avl_root; p != NULL; p = q)
00502     {
00503       int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param);
00504 
00505       if (cmp < 0)
00506         q = p->avl_link[0];
00507       else if (cmp > 0)
00508         q = p->avl_link[1];
00509       else /* |cmp == 0| */
00510         {
00511           trav->avl_node = p;
00512           return p->avl_data;
00513         }
00514 
00515       assert (trav->avl_height < AVL_MAX_HEIGHT);
00516       trav->avl_stack[trav->avl_height++] = p;
00517     }
00518 
00519   trav->avl_height = 0;
00520   trav->avl_node = NULL;
00521   return NULL;
00522 }
00523 
00524 /* Attempts to insert |item| into |tree|.
00525    If |item| is inserted successfully, it is returned and |trav| is
00526    initialized to its location.
00527    If a duplicate is found, it is returned and |trav| is initialized to
00528    its location.  No replacement of the item occurs.
00529    If a memory allocation failure occurs, |NULL| is returned and |trav|
00530    is initialized to the null item. */
00531 void *
00532 avl_t_insert (struct avl_traverser *trav, struct avl_table *tree, void *item)
00533 {
00534   void **p;
00535 
00536   assert (trav != NULL && tree != NULL && item != NULL);
00537 
00538   p = avl_probe (tree, item);
00539   if (p != NULL)
00540     {
00541       trav->avl_table = tree;
00542       trav->avl_node =
00543         ((struct avl_node *)
00544          ((char *) p - offsetof (struct avl_node, avl_data)));
00545       trav->avl_generation = tree->avl_generation - 1;
00546       return *p;
00547     }
00548   else
00549     {
00550       avl_t_init (trav, tree);
00551       return NULL;
00552     }
00553 }
00554 
00555 /* Initializes |trav| to have the same current node as |src|. */
00556 void *
00557 avl_t_copy (struct avl_traverser *trav, const struct avl_traverser *src)
00558 {
00559   assert (trav != NULL && src != NULL);
00560 
00561   if (trav != src)
00562     {
00563       trav->avl_table = src->avl_table;
00564       trav->avl_node = src->avl_node;
00565       trav->avl_generation = src->avl_generation;
00566       if (trav->avl_generation == trav->avl_table->avl_generation)
00567         {
00568           trav->avl_height = src->avl_height;
00569           memcpy (trav->avl_stack, (const void *) src->avl_stack,
00570                   sizeof *trav->avl_stack * trav->avl_height);
00571         }
00572     }
00573 
00574   return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL;
00575 }
00576 
00577 /* Returns the next data item in inorder
00578    within the tree being traversed with |trav|,
00579    or if there are no more data items returns |NULL|. */
00580 void *
00581 avl_t_next (struct avl_traverser *trav)
00582 {
00583   struct avl_node *x;
00584 
00585   assert (trav != NULL);
00586 
00587   if (trav->avl_generation != trav->avl_table->avl_generation)
00588     trav_refresh (trav);
00589 
00590   x = trav->avl_node;
00591   if (x == NULL)
00592     {
00593       return avl_t_first (trav, trav->avl_table);
00594     }
00595   else if (x->avl_link[1] != NULL)
00596     {
00597       assert (trav->avl_height < AVL_MAX_HEIGHT);
00598       trav->avl_stack[trav->avl_height++] = x;
00599       x = x->avl_link[1];
00600 
00601       while (x->avl_link[0] != NULL)
00602         {
00603           assert (trav->avl_height < AVL_MAX_HEIGHT);
00604           trav->avl_stack[trav->avl_height++] = x;
00605           x = x->avl_link[0];
00606         }
00607     }
00608   else
00609     {
00610       struct avl_node *y;
00611 
00612       do
00613         {
00614           if (trav->avl_height == 0)
00615             {
00616               trav->avl_node = NULL;
00617               return NULL;
00618             }
00619 
00620           y = x;
00621           x = trav->avl_stack[--trav->avl_height];
00622         }
00623       while (y == x->avl_link[1]);
00624     }
00625   trav->avl_node = x;
00626 
00627   return x->avl_data;
00628 }
00629 
00630 /* Returns the previous data item in inorder
00631    within the tree being traversed with |trav|,
00632    or if there are no more data items returns |NULL|. */
00633 void *
00634 avl_t_prev (struct avl_traverser *trav)
00635 {
00636   struct avl_node *x;
00637 
00638   assert (trav != NULL);
00639 
00640   if (trav->avl_generation != trav->avl_table->avl_generation)
00641     trav_refresh (trav);
00642 
00643   x = trav->avl_node;
00644   if (x == NULL)
00645     {
00646       return avl_t_last (trav, trav->avl_table);
00647     }
00648   else if (x->avl_link[0] != NULL)
00649     {
00650       assert (trav->avl_height < AVL_MAX_HEIGHT);
00651       trav->avl_stack[trav->avl_height++] = x;
00652       x = x->avl_link[0];
00653 
00654       while (x->avl_link[1] != NULL)
00655         {
00656           assert (trav->avl_height < AVL_MAX_HEIGHT);
00657           trav->avl_stack[trav->avl_height++] = x;
00658           x = x->avl_link[1];
00659         }
00660     }
00661   else
00662     {
00663       struct avl_node *y;
00664 
00665       do
00666         {
00667           if (trav->avl_height == 0)
00668             {
00669               trav->avl_node = NULL;
00670               return NULL;
00671             }
00672 
00673           y = x;
00674           x = trav->avl_stack[--trav->avl_height];
00675         }
00676       while (y == x->avl_link[0]);
00677     }
00678   trav->avl_node = x;
00679 
00680   return x->avl_data;
00681 }
00682 
00683 /* Returns |trav|'s current item. */
00684 void *
00685 avl_t_cur (struct avl_traverser *trav)
00686 {
00687   assert (trav != NULL);
00688 
00689   return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL;
00690 }
00691 
00692 /* Replaces the current item in |trav| by |new| and returns the item replaced.
00693    |trav| must not have the null item selected.
00694    The new item must not upset the ordering of the tree. */
00695 void *
00696 avl_t_replace (struct avl_traverser *trav, void *new)
00697 {
00698   void *old;
00699 
00700   assert (trav != NULL && trav->avl_node != NULL && new != NULL);
00701   old = trav->avl_node->avl_data;
00702   trav->avl_node->avl_data = new;
00703   return old;
00704 }
00705 
00706 static void
00707 copy_error_recovery (struct avl_node **stack, int height,
00708                      struct avl_table *new, avl_item_func *destroy)
00709 {
00710   assert (stack != NULL && height >= 0 && new != NULL);
00711 
00712   for (; height > 2; height -= 2)
00713     stack[height - 1]->avl_link[1] = NULL;
00714   avl_destroy (new, destroy);
00715 }
00716 
00717 /* Copies |org| to a newly created tree, which is returned.
00718    If |copy != NULL|, each data item in |org| is first passed to |copy|,
00719    and the return values are inserted into the tree,
00720    with |NULL| return values taken as indications of failure.
00721    On failure, destroys the partially created new tree,
00722    applying |destroy|, if non-null, to each item in the new tree so far,
00723    and returns |NULL|.
00724    If |allocator != NULL|, it is used for allocation in the new tree.
00725    Otherwise, the same allocator used for |org| is used. */
00726 struct avl_table *
00727 avl_copy (const struct avl_table *org, avl_copy_func *copy,
00728           avl_item_func *destroy, struct libavl_allocator *allocator)
00729 {
00730   struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)];
00731   int height = 0;
00732 
00733   struct avl_table *new;
00734   const struct avl_node *x;
00735   struct avl_node *y;
00736 
00737   assert (org != NULL);
00738   new = avl_create (org->avl_compare, org->avl_param,
00739                     allocator != NULL ? allocator : org->avl_alloc);
00740   if (new == NULL)
00741     return NULL;
00742   new->avl_count = org->avl_count;
00743   if (new->avl_count == 0)
00744     return new;
00745 
00746   x = (const struct avl_node *) &org->avl_root;
00747   y = (struct avl_node *) &new->avl_root;
00748   for (;;)
00749     {
00750       while (x->avl_link[0] != NULL)
00751         {
00752           assert (height < 2 * (AVL_MAX_HEIGHT + 1));
00753 
00754           y->avl_link[0] =
00755             new->avl_alloc->libavl_malloc (new->avl_alloc,
00756                                            sizeof *y->avl_link[0]);
00757           if (y->avl_link[0] == NULL)
00758             {
00759               if (y != (struct avl_node *) &new->avl_root)
00760                 {
00761                   y->avl_data = NULL;
00762                   y->avl_link[1] = NULL;
00763                 }
00764 
00765               copy_error_recovery (stack, height, new, destroy);
00766               return NULL;
00767             }
00768 
00769           stack[height++] = (struct avl_node *) x;
00770           stack[height++] = y;
00771           x = x->avl_link[0];
00772           y = y->avl_link[0];
00773         }
00774       y->avl_link[0] = NULL;
00775 
00776       for (;;)
00777         {
00778           y->avl_balance = x->avl_balance;
00779           if (copy == NULL)
00780             y->avl_data = x->avl_data;
00781           else
00782             {
00783               y->avl_data = copy (x->avl_data, org->avl_param);
00784               if (y->avl_data == NULL)
00785                 {
00786                   y->avl_link[1] = NULL;
00787                   copy_error_recovery (stack, height, new, destroy);
00788                   return NULL;
00789                 }
00790             }
00791 
00792           if (x->avl_link[1] != NULL)
00793             {
00794               y->avl_link[1] =
00795                 new->avl_alloc->libavl_malloc (new->avl_alloc,
00796                                                sizeof *y->avl_link[1]);
00797               if (y->avl_link[1] == NULL)
00798                 {
00799                   copy_error_recovery (stack, height, new, destroy);
00800                   return NULL;
00801                 }
00802 
00803               x = x->avl_link[1];
00804               y = y->avl_link[1];
00805               break;
00806             }
00807           else
00808             y->avl_link[1] = NULL;
00809 
00810           if (height <= 2)
00811             return new;
00812 
00813           y = stack[--height];
00814           x = stack[--height];
00815         }
00816     }
00817 }
00818 
00819 /* Frees storage allocated for |tree|.
00820    If |destroy != NULL|, applies it to each data item in inorder. */
00821 void
00822 avl_destroy (struct avl_table *tree, avl_item_func *destroy)
00823 {
00824   struct avl_node *p, *q;
00825 
00826   assert (tree != NULL);
00827 
00828   for (p = tree->avl_root; p != NULL; p = q)
00829     if (p->avl_link[0] == NULL)
00830       {
00831         q = p->avl_link[1];
00832         if (destroy != NULL && p->avl_data != NULL)
00833           destroy (p->avl_data, tree->avl_param);
00834         tree->avl_alloc->libavl_free (tree->avl_alloc, p);
00835       }
00836     else
00837       {
00838         q = p->avl_link[0];
00839         p->avl_link[0] = q->avl_link[1];
00840         q->avl_link[1] = p;
00841       }
00842 
00843   tree->avl_alloc->libavl_free (tree->avl_alloc, tree);
00844 }
00845 
00846 /* Allocates |size| bytes of space using |malloc()|.
00847    Returns a null pointer if allocation fails. */
00848 void *
00849 avl_malloc (struct libavl_allocator *allocator, size_t size)
00850 {
00851   assert (allocator != NULL && size > 0);
00852   return malloc (size);
00853 }
00854 
00855 /* Frees |block|. */
00856 void
00857 avl_free (struct libavl_allocator *allocator, void *block)
00858 {
00859   assert (allocator != NULL && block != NULL);
00860   free (block);
00861 }
00862 
00863 /* Default memory allocator that uses |malloc()| and |free()|. */
00864 struct libavl_allocator avl_allocator_default =
00865   {
00866     avl_malloc,
00867     avl_free
00868   };
00869 
00870 #undef NDEBUG
00871 #include <assert.h>
00872 
00873 /* Asserts that |avl_insert()| succeeds at inserting |item| into |table|. */
00874 void
00875 (avl_assert_insert) (struct avl_table *table, void *item)
00876 {
00877   void **p = avl_probe (table, item);
00878   assert (p != NULL && *p == item);
00879 }
00880 
00881 /* Asserts that |avl_delete()| really removes |item| from |table|,
00882    and returns the removed item. */
00883 void *
00884 (avl_assert_delete) (struct avl_table *table, void *item)
00885 {
00886   void *p = avl_delete (table, item);
00887   assert (p != NULL);
00888   return p;
00889 }
00890