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

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5