avl.c

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

Generated on Sat Oct 24 03:25:19 2009 for GRASS Programmer's Manual by  doxygen 1.6.1