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