GRASS Programmer's Manual 6.4.1(2011)
tavl.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 "tavl.h"
00030 
00031 /* Creates and returns a new table
00032    with comparison function |compare| using parameter |param|
00033    and memory allocator |allocator|.
00034    Returns |NULL| if memory allocation failed. */
00035 struct tavl_table *tavl_create(tavl_comparison_func * compare, void *param,
00036                                struct libavl_allocator *allocator)
00037 {
00038     struct tavl_table *tree;
00039 
00040     assert(compare != NULL);
00041 
00042     if (allocator == NULL)
00043         allocator = &tavl_allocator_default;
00044 
00045     tree = allocator->libavl_malloc(allocator, sizeof *tree);
00046     if (tree == NULL)
00047         return NULL;
00048 
00049     tree->tavl_root = NULL;
00050     tree->tavl_compare = compare;
00051     tree->tavl_param = param;
00052     tree->tavl_alloc = allocator;
00053     tree->tavl_count = 0;
00054 
00055     return tree;
00056 }
00057 
00058 /* Search |tree| for an item matching |item|, and return it if found.
00059    Otherwise return |NULL|. */
00060 void *tavl_find(const struct tavl_table *tree, const void *item)
00061 {
00062     const struct tavl_node *p;
00063 
00064     assert(tree != NULL && item != NULL);
00065 
00066     p = tree->tavl_root;
00067     if (p == NULL)
00068         return NULL;
00069 
00070     for (;;) {
00071         int cmp, dir;
00072 
00073         cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
00074         if (cmp == 0)
00075             return p->tavl_data;
00076 
00077         dir = cmp > 0;
00078         if (p->tavl_tag[dir] == TAVL_CHILD)
00079             p = p->tavl_link[dir];
00080         else
00081             return NULL;
00082     }
00083 }
00084 
00085 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
00086    If a duplicate item is found in the tree,
00087    returns a pointer to the duplicate without inserting |item|.
00088    Returns |NULL| in case of memory allocation failure. */
00089 void **tavl_probe(struct tavl_table *tree, void *item)
00090 {
00091     struct tavl_node *y, *z;    /* Top node to update balance factor, and parent. */
00092     struct tavl_node *p, *q;    /* Iterator, and parent. */
00093     struct tavl_node *n;        /* Newly inserted node. */
00094     struct tavl_node *w;        /* New root of rebalanced subtree. */
00095     int dir;                    /* Direction to descend. */
00096 
00097     unsigned char da[TAVL_MAX_HEIGHT];  /* Cached comparison results. */
00098     int k = 0;                  /* Number of cached results. */
00099 
00100     assert(tree != NULL && item != NULL);
00101 
00102     z = (struct tavl_node *)&tree->tavl_root;
00103     y = tree->tavl_root;
00104     if (y != NULL) {
00105         for (q = z, p = y;; q = p, p = p->tavl_link[dir]) {
00106             int cmp =
00107                 tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
00108             if (cmp == 0)
00109                 return &p->tavl_data;
00110 
00111             if (p->tavl_balance != 0)
00112                 z = q, y = p, k = 0;
00113             da[k++] = dir = cmp > 0;
00114 
00115             if (p->tavl_tag[dir] == TAVL_THREAD)
00116                 break;
00117         }
00118     }
00119     else {
00120         p = z;
00121         dir = 0;
00122     }
00123 
00124     n = tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *n);
00125     if (n == NULL)
00126         return NULL;
00127 
00128     tree->tavl_count++;
00129     n->tavl_data = item;
00130     n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD;
00131     n->tavl_link[dir] = p->tavl_link[dir];
00132     if (tree->tavl_root != NULL) {
00133         p->tavl_tag[dir] = TAVL_CHILD;
00134         n->tavl_link[!dir] = p;
00135     }
00136     else
00137         n->tavl_link[1] = NULL;
00138     p->tavl_link[dir] = n;
00139     n->tavl_balance = 0;
00140     if (tree->tavl_root == n)
00141         return &n->tavl_data;
00142 
00143     for (p = y, k = 0; p != n; p = p->tavl_link[da[k]], k++)
00144         if (da[k] == 0)
00145             p->tavl_balance--;
00146         else
00147             p->tavl_balance++;
00148 
00149     if (y->tavl_balance == -2) {
00150         struct tavl_node *x = y->tavl_link[0];
00151 
00152         if (x->tavl_balance == -1) {
00153             w = x;
00154             if (x->tavl_tag[1] == TAVL_THREAD) {
00155                 x->tavl_tag[1] = TAVL_CHILD;
00156                 y->tavl_tag[0] = TAVL_THREAD;
00157                 y->tavl_link[0] = x;
00158             }
00159             else
00160                 y->tavl_link[0] = x->tavl_link[1];
00161             x->tavl_link[1] = y;
00162             x->tavl_balance = y->tavl_balance = 0;
00163         }
00164         else {
00165             assert(x->tavl_balance == +1);
00166             w = x->tavl_link[1];
00167             x->tavl_link[1] = w->tavl_link[0];
00168             w->tavl_link[0] = x;
00169             y->tavl_link[0] = w->tavl_link[1];
00170             w->tavl_link[1] = y;
00171             if (w->tavl_balance == -1)
00172                 x->tavl_balance = 0, y->tavl_balance = +1;
00173             else if (w->tavl_balance == 0)
00174                 x->tavl_balance = y->tavl_balance = 0;
00175             else                /* |w->tavl_balance == +1| */
00176                 x->tavl_balance = -1, y->tavl_balance = 0;
00177             w->tavl_balance = 0;
00178             if (w->tavl_tag[0] == TAVL_THREAD) {
00179                 x->tavl_tag[1] = TAVL_THREAD;
00180                 x->tavl_link[1] = w;
00181                 w->tavl_tag[0] = TAVL_CHILD;
00182             }
00183             if (w->tavl_tag[1] == TAVL_THREAD) {
00184                 y->tavl_tag[0] = TAVL_THREAD;
00185                 y->tavl_link[0] = w;
00186                 w->tavl_tag[1] = TAVL_CHILD;
00187             }
00188         }
00189     }
00190     else if (y->tavl_balance == +2) {
00191         struct tavl_node *x = y->tavl_link[1];
00192 
00193         if (x->tavl_balance == +1) {
00194             w = x;
00195             if (x->tavl_tag[0] == TAVL_THREAD) {
00196                 x->tavl_tag[0] = TAVL_CHILD;
00197                 y->tavl_tag[1] = TAVL_THREAD;
00198                 y->tavl_link[1] = x;
00199             }
00200             else
00201                 y->tavl_link[1] = x->tavl_link[0];
00202             x->tavl_link[0] = y;
00203             x->tavl_balance = y->tavl_balance = 0;
00204         }
00205         else {
00206             assert(x->tavl_balance == -1);
00207             w = x->tavl_link[0];
00208             x->tavl_link[0] = w->tavl_link[1];
00209             w->tavl_link[1] = x;
00210             y->tavl_link[1] = w->tavl_link[0];
00211             w->tavl_link[0] = y;
00212             if (w->tavl_balance == +1)
00213                 x->tavl_balance = 0, y->tavl_balance = -1;
00214             else if (w->tavl_balance == 0)
00215                 x->tavl_balance = y->tavl_balance = 0;
00216             else                /* |w->tavl_balance == -1| */
00217                 x->tavl_balance = +1, y->tavl_balance = 0;
00218             w->tavl_balance = 0;
00219             if (w->tavl_tag[0] == TAVL_THREAD) {
00220                 y->tavl_tag[1] = TAVL_THREAD;
00221                 y->tavl_link[1] = w;
00222                 w->tavl_tag[0] = TAVL_CHILD;
00223             }
00224             if (w->tavl_tag[1] == TAVL_THREAD) {
00225                 x->tavl_tag[0] = TAVL_THREAD;
00226                 x->tavl_link[0] = w;
00227                 w->tavl_tag[1] = TAVL_CHILD;
00228             }
00229         }
00230     }
00231     else
00232         return &n->tavl_data;
00233     z->tavl_link[y != z->tavl_link[0]] = w;
00234 
00235     return &n->tavl_data;
00236 }
00237 
00238 /* Inserts |item| into |table|.
00239    Returns |NULL| if |item| was successfully inserted
00240    or if a memory allocation error occurred.
00241    Otherwise, returns the duplicate item. */
00242 void *tavl_insert(struct tavl_table *table, void *item)
00243 {
00244     void **p = tavl_probe(table, item);
00245 
00246     return p == NULL || *p == item ? NULL : *p;
00247 }
00248 
00249 /* Inserts |item| into |table|, replacing any duplicate item.
00250    Returns |NULL| if |item| was inserted without replacing a duplicate,
00251    or if a memory allocation error occurred.
00252    Otherwise, returns the item that was replaced. */
00253 void *tavl_replace(struct tavl_table *table, void *item)
00254 {
00255     void **p = tavl_probe(table, item);
00256 
00257     if (p == NULL || *p == item)
00258         return NULL;
00259     else {
00260         void *r = *p;
00261 
00262         *p = item;
00263         return r;
00264     }
00265 }
00266 
00267 /* Returns the parent of |node| within |tree|,
00268    or a pointer to |tavl_root| if |s| is the root of the tree. */
00269 static struct tavl_node *find_parent(struct tavl_table *tree,
00270                                      struct tavl_node *node)
00271 {
00272     if (node != tree->tavl_root) {
00273         struct tavl_node *x, *y;
00274 
00275         for (x = y = node;; x = x->tavl_link[0], y = y->tavl_link[1])
00276             if (y->tavl_tag[1] == TAVL_THREAD) {
00277                 struct tavl_node *p = y->tavl_link[1];
00278 
00279                 if (p == NULL || p->tavl_link[0] != node) {
00280                     while (x->tavl_tag[0] == TAVL_CHILD)
00281                         x = x->tavl_link[0];
00282                     p = x->tavl_link[0];
00283                 }
00284                 return p;
00285             }
00286             else if (x->tavl_tag[0] == TAVL_THREAD) {
00287                 struct tavl_node *p = x->tavl_link[0];
00288 
00289                 if (p == NULL || p->tavl_link[1] != node) {
00290                     while (y->tavl_tag[1] == TAVL_CHILD)
00291                         y = y->tavl_link[1];
00292                     p = y->tavl_link[1];
00293                 }
00294                 return p;
00295             }
00296     }
00297     else
00298         return (struct tavl_node *)&tree->tavl_root;
00299 }
00300 
00301 /* Deletes from |tree| and returns an item matching |item|.
00302    Returns a null pointer if no matching item found. */
00303 void *tavl_delete(struct tavl_table *tree, const void *item)
00304 {
00305     struct tavl_node *p;        /* Traverses tree to find node to delete. */
00306     struct tavl_node *q;        /* Parent of |p|. */
00307     int dir;                    /* Index into |q->tavl_link[]| to get |p|. */
00308     int cmp;                    /* Result of comparison between |item| and |p|. */
00309 
00310     assert(tree != NULL && item != NULL);
00311 
00312     if (tree->tavl_root == NULL)
00313         return NULL;
00314 
00315     p = (struct tavl_node *)&tree->tavl_root;
00316     for (cmp = -1; cmp != 0;
00317          cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param)) {
00318         dir = cmp > 0;
00319 
00320         q = p;
00321         if (p->tavl_tag[dir] == TAVL_THREAD)
00322             return NULL;
00323         p = p->tavl_link[dir];
00324     }
00325     item = p->tavl_data;
00326 
00327     if (p->tavl_tag[1] == TAVL_THREAD) {
00328         if (p->tavl_tag[0] == TAVL_CHILD) {
00329             struct tavl_node *t = p->tavl_link[0];
00330 
00331             while (t->tavl_tag[1] == TAVL_CHILD)
00332                 t = t->tavl_link[1];
00333             t->tavl_link[1] = p->tavl_link[1];
00334             q->tavl_link[dir] = p->tavl_link[0];
00335         }
00336         else {
00337             q->tavl_link[dir] = p->tavl_link[dir];
00338             if (q != (struct tavl_node *)&tree->tavl_root)
00339                 q->tavl_tag[dir] = TAVL_THREAD;
00340         }
00341     }
00342     else {
00343         struct tavl_node *r = p->tavl_link[1];
00344 
00345         if (r->tavl_tag[0] == TAVL_THREAD) {
00346             r->tavl_link[0] = p->tavl_link[0];
00347             r->tavl_tag[0] = p->tavl_tag[0];
00348             if (r->tavl_tag[0] == TAVL_CHILD) {
00349                 struct tavl_node *t = r->tavl_link[0];
00350 
00351                 while (t->tavl_tag[1] == TAVL_CHILD)
00352                     t = t->tavl_link[1];
00353                 t->tavl_link[1] = r;
00354             }
00355             q->tavl_link[dir] = r;
00356             r->tavl_balance = p->tavl_balance;
00357             q = r;
00358             dir = 1;
00359         }
00360         else {
00361             struct tavl_node *s;
00362 
00363             for (;;) {
00364                 s = r->tavl_link[0];
00365                 if (s->tavl_tag[0] == TAVL_THREAD)
00366                     break;
00367 
00368                 r = s;
00369             }
00370 
00371             if (s->tavl_tag[1] == TAVL_CHILD)
00372                 r->tavl_link[0] = s->tavl_link[1];
00373             else {
00374                 r->tavl_link[0] = s;
00375                 r->tavl_tag[0] = TAVL_THREAD;
00376             }
00377 
00378             s->tavl_link[0] = p->tavl_link[0];
00379             if (p->tavl_tag[0] == TAVL_CHILD) {
00380                 struct tavl_node *t = p->tavl_link[0];
00381 
00382                 while (t->tavl_tag[1] == TAVL_CHILD)
00383                     t = t->tavl_link[1];
00384                 t->tavl_link[1] = s;
00385 
00386                 s->tavl_tag[0] = TAVL_CHILD;
00387             }
00388 
00389             s->tavl_link[1] = p->tavl_link[1];
00390             s->tavl_tag[1] = TAVL_CHILD;
00391 
00392             q->tavl_link[dir] = s;
00393             s->tavl_balance = p->tavl_balance;
00394             q = r;
00395             dir = 0;
00396         }
00397     }
00398 
00399     tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);
00400 
00401     while (q != (struct tavl_node *)&tree->tavl_root) {
00402         struct tavl_node *y = q;
00403 
00404         q = find_parent(tree, y);
00405 
00406         if (dir == 0) {
00407             dir = q->tavl_link[0] != y;
00408             y->tavl_balance++;
00409             if (y->tavl_balance == +1)
00410                 break;
00411             else if (y->tavl_balance == +2) {
00412                 struct tavl_node *x = y->tavl_link[1];
00413 
00414                 assert(x != NULL);
00415                 if (x->tavl_balance == -1) {
00416                     struct tavl_node *w;
00417 
00418                     assert(x->tavl_balance == -1);
00419                     w = x->tavl_link[0];
00420                     x->tavl_link[0] = w->tavl_link[1];
00421                     w->tavl_link[1] = x;
00422                     y->tavl_link[1] = w->tavl_link[0];
00423                     w->tavl_link[0] = y;
00424                     if (w->tavl_balance == +1)
00425                         x->tavl_balance = 0, y->tavl_balance = -1;
00426                     else if (w->tavl_balance == 0)
00427                         x->tavl_balance = y->tavl_balance = 0;
00428                     else        /* |w->tavl_balance == -1| */
00429                         x->tavl_balance = +1, y->tavl_balance = 0;
00430                     w->tavl_balance = 0;
00431                     if (w->tavl_tag[0] == TAVL_THREAD) {
00432                         y->tavl_tag[1] = TAVL_THREAD;
00433                         y->tavl_link[1] = w;
00434                         w->tavl_tag[0] = TAVL_CHILD;
00435                     }
00436                     if (w->tavl_tag[1] == TAVL_THREAD) {
00437                         x->tavl_tag[0] = TAVL_THREAD;
00438                         x->tavl_link[0] = w;
00439                         w->tavl_tag[1] = TAVL_CHILD;
00440                     }
00441                     q->tavl_link[dir] = w;
00442                 }
00443                 else {
00444                     q->tavl_link[dir] = x;
00445 
00446                     if (x->tavl_balance == 0) {
00447                         y->tavl_link[1] = x->tavl_link[0];
00448                         x->tavl_link[0] = y;
00449                         x->tavl_balance = -1;
00450                         y->tavl_balance = +1;
00451                         break;
00452                     }
00453                     else {      /* |x->tavl_balance == +1| */
00454 
00455                         if (x->tavl_tag[0] == TAVL_CHILD)
00456                             y->tavl_link[1] = x->tavl_link[0];
00457                         else {
00458                             y->tavl_tag[1] = TAVL_THREAD;
00459                             x->tavl_tag[0] = TAVL_CHILD;
00460                         }
00461                         x->tavl_link[0] = y;
00462                         y->tavl_balance = x->tavl_balance = 0;
00463                     }
00464                 }
00465             }
00466         }
00467         else {
00468             dir = q->tavl_link[0] != y;
00469             y->tavl_balance--;
00470             if (y->tavl_balance == -1)
00471                 break;
00472             else if (y->tavl_balance == -2) {
00473                 struct tavl_node *x = y->tavl_link[0];
00474 
00475                 assert(x != NULL);
00476                 if (x->tavl_balance == +1) {
00477                     struct tavl_node *w;
00478 
00479                     assert(x->tavl_balance == +1);
00480                     w = x->tavl_link[1];
00481                     x->tavl_link[1] = w->tavl_link[0];
00482                     w->tavl_link[0] = x;
00483                     y->tavl_link[0] = w->tavl_link[1];
00484                     w->tavl_link[1] = y;
00485                     if (w->tavl_balance == -1)
00486                         x->tavl_balance = 0, y->tavl_balance = +1;
00487                     else if (w->tavl_balance == 0)
00488                         x->tavl_balance = y->tavl_balance = 0;
00489                     else        /* |w->tavl_balance == +1| */
00490                         x->tavl_balance = -1, y->tavl_balance = 0;
00491                     w->tavl_balance = 0;
00492                     if (w->tavl_tag[0] == TAVL_THREAD) {
00493                         x->tavl_tag[1] = TAVL_THREAD;
00494                         x->tavl_link[1] = w;
00495                         w->tavl_tag[0] = TAVL_CHILD;
00496                     }
00497                     if (w->tavl_tag[1] == TAVL_THREAD) {
00498                         y->tavl_tag[0] = TAVL_THREAD;
00499                         y->tavl_link[0] = w;
00500                         w->tavl_tag[1] = TAVL_CHILD;
00501                     }
00502                     q->tavl_link[dir] = w;
00503                 }
00504                 else {
00505                     q->tavl_link[dir] = x;
00506 
00507                     if (x->tavl_balance == 0) {
00508                         y->tavl_link[0] = x->tavl_link[1];
00509                         x->tavl_link[1] = y;
00510                         x->tavl_balance = +1;
00511                         y->tavl_balance = -1;
00512                         break;
00513                     }
00514                     else {      /* |x->tavl_balance == -1| */
00515 
00516                         if (x->tavl_tag[1] == TAVL_CHILD)
00517                             y->tavl_link[0] = x->tavl_link[1];
00518                         else {
00519                             y->tavl_tag[0] = TAVL_THREAD;
00520                             x->tavl_tag[1] = TAVL_CHILD;
00521                         }
00522                         x->tavl_link[1] = y;
00523                         y->tavl_balance = x->tavl_balance = 0;
00524                     }
00525                 }
00526             }
00527         }
00528     }
00529 
00530     tree->tavl_count--;
00531     return (void *)item;
00532 }
00533 
00534 /* Initializes |trav| for use with |tree|
00535    and selects the null node. */
00536 void tavl_t_init(struct tavl_traverser *trav, struct tavl_table *tree)
00537 {
00538     trav->tavl_table = tree;
00539     trav->tavl_node = NULL;
00540 }
00541 
00542 /* Initializes |trav| for |tree|.
00543    Returns data item in |tree| with the least value,
00544    or |NULL| if |tree| is empty. */
00545 void *tavl_t_first(struct tavl_traverser *trav, struct tavl_table *tree)
00546 {
00547     assert(tree != NULL && trav != NULL);
00548 
00549     trav->tavl_table = tree;
00550     trav->tavl_node = tree->tavl_root;
00551     if (trav->tavl_node != NULL) {
00552         while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
00553             trav->tavl_node = trav->tavl_node->tavl_link[0];
00554         return trav->tavl_node->tavl_data;
00555     }
00556     else
00557         return NULL;
00558 }
00559 
00560 /* Initializes |trav| for |tree|.
00561    Returns data item in |tree| with the greatest value,
00562    or |NULL| if |tree| is empty. */
00563 void *tavl_t_last(struct tavl_traverser *trav, struct tavl_table *tree)
00564 {
00565     assert(tree != NULL && trav != NULL);
00566 
00567     trav->tavl_table = tree;
00568     trav->tavl_node = tree->tavl_root;
00569     if (trav->tavl_node != NULL) {
00570         while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
00571             trav->tavl_node = trav->tavl_node->tavl_link[1];
00572         return trav->tavl_node->tavl_data;
00573     }
00574     else
00575         return NULL;
00576 }
00577 
00578 /* Searches for |item| in |tree|.
00579    If found, initializes |trav| to the item found and returns the item
00580    as well.
00581    If there is no matching item, initializes |trav| to the null item
00582    and returns |NULL|. */
00583 void *tavl_t_find(struct tavl_traverser *trav, struct tavl_table *tree,
00584                   void *item)
00585 {
00586     struct tavl_node *p;
00587 
00588     assert(trav != NULL && tree != NULL && item != NULL);
00589 
00590     trav->tavl_table = tree;
00591     trav->tavl_node = NULL;
00592 
00593     p = tree->tavl_root;
00594     if (p == NULL)
00595         return NULL;
00596 
00597     for (;;) {
00598         int cmp, dir;
00599 
00600         cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
00601         if (cmp == 0) {
00602             trav->tavl_node = p;
00603             return p->tavl_data;
00604         }
00605 
00606         dir = cmp > 0;
00607         if (p->tavl_tag[dir] == TAVL_CHILD)
00608             p = p->tavl_link[dir];
00609         else
00610             return NULL;
00611     }
00612 }
00613 
00614 /* Attempts to insert |item| into |tree|.
00615    If |item| is inserted successfully, it is returned and |trav| is
00616    initialized to its location.
00617    If a duplicate is found, it is returned and |trav| is initialized to
00618    its location.  No replacement of the item occurs.
00619    If a memory allocation failure occurs, |NULL| is returned and |trav|
00620    is initialized to the null item. */
00621 void *tavl_t_insert(struct tavl_traverser *trav,
00622                     struct tavl_table *tree, void *item)
00623 {
00624     void **p;
00625 
00626     assert(trav != NULL && tree != NULL && item != NULL);
00627 
00628     p = tavl_probe(tree, item);
00629     if (p != NULL) {
00630         trav->tavl_table = tree;
00631         trav->tavl_node = ((struct tavl_node *)
00632                            ((char *)p -
00633                             offsetof(struct tavl_node, tavl_data)));
00634         return *p;
00635     }
00636     else {
00637         tavl_t_init(trav, tree);
00638         return NULL;
00639     }
00640 }
00641 
00642 /* Initializes |trav| to have the same current node as |src|. */
00643 void *tavl_t_copy(struct tavl_traverser *trav,
00644                   const struct tavl_traverser *src)
00645 {
00646     assert(trav != NULL && src != NULL);
00647 
00648     trav->tavl_table = src->tavl_table;
00649     trav->tavl_node = src->tavl_node;
00650 
00651     return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00652 }
00653 
00654 /* Returns the next data item in inorder
00655    within the tree being traversed with |trav|,
00656    or if there are no more data items returns |NULL|. */
00657 void *tavl_t_next(struct tavl_traverser *trav)
00658 {
00659     assert(trav != NULL);
00660 
00661     if (trav->tavl_node == NULL)
00662         return tavl_t_first(trav, trav->tavl_table);
00663     else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD) {
00664         trav->tavl_node = trav->tavl_node->tavl_link[1];
00665         return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00666     }
00667     else {
00668         trav->tavl_node = trav->tavl_node->tavl_link[1];
00669         while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
00670             trav->tavl_node = trav->tavl_node->tavl_link[0];
00671         return trav->tavl_node->tavl_data;
00672     }
00673 }
00674 
00675 /* Returns the previous data item in inorder
00676    within the tree being traversed with |trav|,
00677    or if there are no more data items returns |NULL|. */
00678 void *tavl_t_prev(struct tavl_traverser *trav)
00679 {
00680     assert(trav != NULL);
00681 
00682     if (trav->tavl_node == NULL)
00683         return tavl_t_last(trav, trav->tavl_table);
00684     else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD) {
00685         trav->tavl_node = trav->tavl_node->tavl_link[0];
00686         return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00687     }
00688     else {
00689         trav->tavl_node = trav->tavl_node->tavl_link[0];
00690         while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
00691             trav->tavl_node = trav->tavl_node->tavl_link[1];
00692         return trav->tavl_node->tavl_data;
00693     }
00694 }
00695 
00696 /* Returns |trav|'s current item. */
00697 void *tavl_t_cur(struct tavl_traverser *trav)
00698 {
00699     assert(trav != NULL);
00700 
00701     return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00702 }
00703 
00704 /* Replaces the current item in |trav| by |new| and returns the item replaced.
00705    |trav| must not have the null item selected.
00706    The new item must not upset the ordering of the tree. */
00707 void *tavl_t_replace(struct tavl_traverser *trav, void *new)
00708 {
00709     struct tavl_node *old;
00710 
00711     assert(trav != NULL && trav->tavl_node != NULL && new != NULL);
00712     old = trav->tavl_node->tavl_data;
00713     trav->tavl_node->tavl_data = new;
00714     return old;
00715 }
00716 
00717 /* Creates a new node as a child of |dst| on side |dir|.
00718    Copies data and |tavl_balance| from |src| into the new node,
00719    applying |copy()|, if non-null.
00720    Returns nonzero only if fully successful.
00721    Regardless of success, integrity of the tree structure is assured,
00722    though failure may leave a null pointer in a |tavl_data| member. */
00723 static int
00724 copy_node(struct tavl_table *tree,
00725           struct tavl_node *dst, int dir,
00726           const struct tavl_node *src, tavl_copy_func * copy)
00727 {
00728     struct tavl_node *new =
00729         tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *new);
00730     if (new == NULL)
00731         return 0;
00732 
00733     new->tavl_link[dir] = dst->tavl_link[dir];
00734     new->tavl_tag[dir] = TAVL_THREAD;
00735     new->tavl_link[!dir] = dst;
00736     new->tavl_tag[!dir] = TAVL_THREAD;
00737     dst->tavl_link[dir] = new;
00738     dst->tavl_tag[dir] = TAVL_CHILD;
00739 
00740     new->tavl_balance = src->tavl_balance;
00741     if (copy == NULL)
00742         new->tavl_data = src->tavl_data;
00743     else {
00744         new->tavl_data = copy(src->tavl_data, tree->tavl_param);
00745         if (new->tavl_data == NULL)
00746             return 0;
00747     }
00748 
00749     return 1;
00750 }
00751 
00752 static void
00753 copy_error_recovery(struct tavl_node *p,
00754                     struct tavl_table *new, tavl_item_func * destroy)
00755 {
00756     new->tavl_root = p;
00757     if (p != NULL) {
00758         while (p->tavl_tag[1] == TAVL_CHILD)
00759             p = p->tavl_link[1];
00760         p->tavl_link[1] = NULL;
00761     }
00762     tavl_destroy(new, destroy);
00763 }
00764 
00765 /* Copies |org| to a newly created tree, which is returned.
00766    If |copy != NULL|, each data item in |org| is first passed to |copy|,
00767    and the return values are inserted into the tree,
00768    with |NULL| return values taken as indications of failure.
00769    On failure, destroys the partially created new tree,
00770    applying |destroy|, if non-null, to each item in the new tree so far,
00771    and returns |NULL|.
00772    If |allocator != NULL|, it is used for allocation in the new tree.
00773    Otherwise, the same allocator used for |org| is used. */
00774 struct tavl_table *tavl_copy(const struct tavl_table *org,
00775                              tavl_copy_func * copy, tavl_item_func * destroy,
00776                              struct libavl_allocator *allocator)
00777 {
00778     struct tavl_table *new;
00779 
00780     const struct tavl_node *p;
00781     struct tavl_node *q;
00782     struct tavl_node rp, rq;
00783 
00784     assert(org != NULL);
00785     new = tavl_create(org->tavl_compare, org->tavl_param,
00786                       allocator != NULL ? allocator : org->tavl_alloc);
00787     if (new == NULL)
00788         return NULL;
00789 
00790     new->tavl_count = org->tavl_count;
00791     if (new->tavl_count == 0)
00792         return new;
00793 
00794     p = &rp;
00795     rp.tavl_link[0] = org->tavl_root;
00796     rp.tavl_tag[0] = TAVL_CHILD;
00797 
00798     q = &rq;
00799     rq.tavl_link[0] = NULL;
00800     rq.tavl_tag[0] = TAVL_THREAD;
00801 
00802     for (;;) {
00803         if (p->tavl_tag[0] == TAVL_CHILD) {
00804             if (!copy_node(new, q, 0, p->tavl_link[0], copy)) {
00805                 copy_error_recovery(rq.tavl_link[0], new, destroy);
00806                 return NULL;
00807             }
00808 
00809             p = p->tavl_link[0];
00810             q = q->tavl_link[0];
00811         }
00812         else {
00813             while (p->tavl_tag[1] == TAVL_THREAD) {
00814                 p = p->tavl_link[1];
00815                 if (p == NULL) {
00816                     q->tavl_link[1] = NULL;
00817                     new->tavl_root = rq.tavl_link[0];
00818                     return new;
00819                 }
00820 
00821                 q = q->tavl_link[1];
00822             }
00823 
00824             p = p->tavl_link[1];
00825             q = q->tavl_link[1];
00826         }
00827 
00828         if (p->tavl_tag[1] == TAVL_CHILD)
00829             if (!copy_node(new, q, 1, p->tavl_link[1], copy)) {
00830                 copy_error_recovery(rq.tavl_link[0], new, destroy);
00831                 return NULL;
00832             }
00833     }
00834 }
00835 
00836 /* Frees storage allocated for |tree|.
00837    If |destroy != NULL|, applies it to each data item in inorder. */
00838 void tavl_destroy(struct tavl_table *tree, tavl_item_func * destroy)
00839 {
00840     struct tavl_node *p;        /* Current node. */
00841     struct tavl_node *n;        /* Next node. */
00842 
00843     p = tree->tavl_root;
00844     if (p != NULL)
00845         while (p->tavl_tag[0] == TAVL_CHILD)
00846             p = p->tavl_link[0];
00847 
00848     while (p != NULL) {
00849         n = p->tavl_link[1];
00850         if (p->tavl_tag[1] == TAVL_CHILD)
00851             while (n->tavl_tag[0] == TAVL_CHILD)
00852                 n = n->tavl_link[0];
00853 
00854         if (destroy != NULL && p->tavl_data != NULL)
00855             destroy(p->tavl_data, tree->tavl_param);
00856         tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);
00857 
00858         p = n;
00859     }
00860 
00861     tree->tavl_alloc->libavl_free(tree->tavl_alloc, tree);
00862 }
00863 
00864 /* Allocates |size| bytes of space using |malloc()|.
00865    Returns a null pointer if allocation fails. */
00866 void *tavl_malloc(struct libavl_allocator *allocator, size_t size)
00867 {
00868     assert(allocator != NULL && size > 0);
00869     return malloc(size);
00870 }
00871 
00872 /* Frees |block|. */
00873 void tavl_free(struct libavl_allocator *allocator, void *block)
00874 {
00875     assert(allocator != NULL && block != NULL);
00876     free(block);
00877 }
00878 
00879 /* Default memory allocator that uses |malloc()| and |free()|. */
00880 struct libavl_allocator tavl_allocator_default = {
00881     tavl_malloc,
00882     tavl_free
00883 };
00884 
00885 /* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
00886 void (tavl_assert_insert) (struct tavl_table * table, void *item)
00887 {
00888     void **p = tavl_probe(table, item);
00889 
00890     assert(p != NULL && *p == item);
00891 }
00892 
00893 /* Asserts that |tavl_delete()| really removes |item| from |table|,
00894    and returns the removed item. */
00895 void *(tavl_assert_delete) (struct tavl_table * table, void *item)
00896 {
00897     void *p = tavl_delete(table, item);
00898 
00899     assert(p != NULL);
00900     return p;
00901 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines