Back to index

glibc  2.9
strtab.c
Go to the documentation of this file.
00001 /* C string table handling.
00002    Copyright (C) 2000, 2001, 2005 Free Software Foundation, Inc.
00003    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
00004 
00005    This program is free software; you can redistribute it and/or modify
00006    it under the terms of the GNU General Public License as published by
00007    the Free Software Foundation; either version 2, or (at your option)
00008    any later version.
00009 
00010    This program is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013    GNU General Public License for more details.
00014 
00015    You should have received a copy of the GNU General Public License
00016    along with this program; if not, write to the Free Software Foundation,
00017    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
00018 
00019 #ifdef HAVE_CONFIG_H
00020 # include <config.h>
00021 #endif
00022 
00023 #include <assert.h>
00024 #include <inttypes.h>
00025 #include <stddef.h>
00026 #include <stdlib.h>
00027 #include <string.h>
00028 #include <unistd.h>
00029 #include <sys/cdefs.h>
00030 #include <sys/param.h>
00031 
00032 
00033 struct Strent
00034 {
00035   const char *string;
00036   size_t len;
00037   struct Strent *next;
00038   struct Strent *left;
00039   struct Strent *right;
00040   size_t offset;
00041   char reverse[0];
00042 };
00043 
00044 
00045 struct memoryblock
00046 {
00047   struct memoryblock *next;
00048   char memory[0];
00049 };
00050 
00051 
00052 struct Strtab
00053 {
00054   struct Strent *root;
00055   struct memoryblock *memory;
00056   char *backp;
00057   size_t left;
00058   size_t total;
00059 
00060   struct Strent null;
00061 };
00062 
00063 
00064 /* Cache for the pagesize.  We correct this value a bit so that `malloc'
00065    is not allocating more than a page.  */
00066 static size_t ps;
00067 
00068 
00069 extern void *xmalloc (size_t n) __attribute_malloc__;
00070 
00071 /* Prototypes for our functions that are used from iconvconfig.c.  If
00072    you change these, change also iconvconfig.c.  */
00073 /* Create new C string table object in memory.  */
00074 extern struct Strtab *strtabinit (void);
00075 
00076 /* Free resources allocated for C string table ST.  */
00077 extern void strtabfree (struct Strtab *st);
00078 
00079 /* Add string STR (length LEN is != 0) to C string table ST.  */
00080 extern struct Strent *strtabadd (struct Strtab *st, const char *str,
00081                              size_t len);
00082 
00083 /* Finalize string table ST and store size in *SIZE and return a pointer.  */
00084 extern void *strtabfinalize (struct Strtab *st, size_t *size);
00085 
00086 /* Get offset in string table for string associated with SE.  */
00087 extern size_t strtaboffset (struct Strent *se);
00088 
00089 
00090 struct Strtab *
00091 strtabinit (void)
00092 {
00093   struct Strtab *ret;
00094 
00095   if (ps == 0)
00096     {
00097       ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
00098       assert (sizeof (struct memoryblock) < ps);
00099     }
00100 
00101   ret = (struct Strtab *) calloc (1, sizeof (struct Strtab));
00102   if (ret != NULL)
00103     {
00104       ret->null.len = 1;
00105       ret->null.string = "";
00106     }
00107   return ret;
00108 }
00109 
00110 
00111 static void
00112 morememory (struct Strtab *st, size_t len)
00113 {
00114   struct memoryblock *newmem;
00115 
00116   if (len < ps)
00117     len = ps;
00118   newmem = (struct memoryblock *) malloc (len);
00119   if (newmem == NULL)
00120     abort ();
00121 
00122   newmem->next = st->memory;
00123   st->memory = newmem;
00124   st->backp = newmem->memory;
00125   st->left = len - offsetof (struct memoryblock, memory);
00126 }
00127 
00128 
00129 void
00130 strtabfree (struct Strtab *st)
00131 {
00132   struct memoryblock *mb = st->memory;
00133 
00134   while (mb != NULL)
00135     {
00136       void *old = mb;
00137       mb = mb->next;
00138       free (old);
00139     }
00140 
00141   free (st);
00142 }
00143 
00144 
00145 static struct Strent *
00146 newstring (struct Strtab *st, const char *str, size_t len)
00147 {
00148   struct Strent *newstr;
00149   size_t align;
00150   int i;
00151 
00152   /* Compute the amount of padding needed to make the structure aligned.  */
00153   align = ((__alignof__ (struct Strent)
00154            - (((uintptr_t) st->backp)
00155               & (__alignof__ (struct Strent) - 1)))
00156           & (__alignof__ (struct Strent) - 1));
00157 
00158   /* Make sure there is enough room in the memory block.  */
00159   if (st->left < align + sizeof (struct Strent) + len)
00160     {
00161       morememory (st, sizeof (struct Strent) + len);
00162       align = 0;
00163     }
00164 
00165   /* Create the reserved string.  */
00166   newstr = (struct Strent *) (st->backp + align);
00167   newstr->string = str;
00168   newstr->len = len;
00169   newstr->next = NULL;
00170   newstr->left = NULL;
00171   newstr->right = NULL;
00172   newstr->offset = 0;
00173   for (i = len - 2; i >= 0; --i)
00174     newstr->reverse[i] = str[len - 2 - i];
00175   newstr->reverse[len - 1] = '\0';
00176   st->backp += align + sizeof (struct Strent) + len;
00177   st->left -= align + sizeof (struct Strent) + len;
00178 
00179   return newstr;
00180 }
00181 
00182 
00183 /* XXX This function should definitely be rewritten to use a balancing
00184    tree algorith (AVL, red-black trees).  For now a simple, correct
00185    implementation is enough.  */
00186 static struct Strent **
00187 searchstring (struct Strent **sep, struct Strent *newstr)
00188 {
00189   int cmpres;
00190 
00191   /* More strings?  */
00192   if (*sep == NULL)
00193     {
00194       *sep = newstr;
00195       return sep;
00196     }
00197 
00198   /* Compare the strings.  */
00199   cmpres = memcmp ((*sep)->reverse, newstr->reverse,
00200                  MIN ((*sep)->len, newstr->len) - 1);
00201   if (cmpres == 0)
00202     /* We found a matching string.  */
00203     return sep;
00204   else if (cmpres > 0)
00205     return searchstring (&(*sep)->left, newstr);
00206   else
00207     return searchstring (&(*sep)->right, newstr);
00208 }
00209 
00210 
00211 /* Add new string.  The actual string is assumed to be permanent.  */
00212 struct Strent *
00213 strtabadd (struct Strtab *st, const char *str, size_t len)
00214 {
00215   struct Strent *newstr;
00216   struct Strent **sep;
00217 
00218   /* Compute the string length if the caller doesn't know it.  */
00219   if (len == 0)
00220     len = strlen (str) + 1;
00221 
00222   /* Make sure all "" strings get offset 0.  */
00223   if (len == 1)
00224     return &st->null;
00225 
00226   /* Allocate memory for the new string and its associated information.  */
00227   newstr = newstring (st, str, len);
00228 
00229   /* Search in the array for the place to insert the string.  If there
00230      is no string with matching prefix and no string with matching
00231      leading substring, create a new entry.  */
00232   sep = searchstring (&st->root, newstr);
00233   if (*sep != newstr)
00234     {
00235       /* This is not the same entry.  This means we have a prefix match.  */
00236       if ((*sep)->len > newstr->len)
00237        {
00238          struct Strent *subs;
00239 
00240          for (subs = (*sep)->next; subs; subs = subs->next)
00241            if (subs->len == newstr->len)
00242              {
00243               /* We have an exact match with a substring.  Free the memory
00244                  we allocated.  */
00245               st->left += st->backp - (char *) newstr;
00246               st->backp = (char *) newstr;
00247 
00248               return subs;
00249              }
00250 
00251          /* We have a new substring.  This means we don't need the reverse
00252             string of this entry anymore.  */
00253          st->backp -= newstr->len;
00254          st->left += newstr->len;
00255 
00256          newstr->next = (*sep)->next;
00257          (*sep)->next = newstr;
00258        }
00259       else if ((*sep)->len != newstr->len)
00260        {
00261          /* When we get here it means that the string we are about to
00262             add has a common prefix with a string we already have but
00263             it is longer.  In this case we have to put it first.  */
00264          st->total += newstr->len - (*sep)->len;
00265          newstr->next = *sep;
00266          newstr->left = (*sep)->left;
00267          newstr->right = (*sep)->right;
00268          *sep = newstr;
00269        }
00270       else
00271        {
00272          /* We have an exact match.  Free the memory we allocated.  */
00273          st->left += st->backp - (char *) newstr;
00274          st->backp = (char *) newstr;
00275 
00276          newstr = *sep;
00277        }
00278     }
00279   else
00280     st->total += newstr->len;
00281 
00282   return newstr;
00283 }
00284 
00285 
00286 static void
00287 copystrings (struct Strent *nodep, char **freep, size_t *offsetp)
00288 {
00289   struct Strent *subs;
00290 
00291   if (nodep->left != NULL)
00292     copystrings (nodep->left, freep, offsetp);
00293 
00294   /* Process the current node.  */
00295   nodep->offset = *offsetp;
00296   *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
00297   *offsetp += nodep->len;
00298 
00299   for (subs = nodep->next; subs != NULL; subs = subs->next)
00300     {
00301       assert (subs->len < nodep->len);
00302       subs->offset = nodep->offset + nodep->len - subs->len;
00303     }
00304 
00305   if (nodep->right != NULL)
00306     copystrings (nodep->right, freep, offsetp);
00307 }
00308 
00309 
00310 void *
00311 strtabfinalize (struct Strtab *st, size_t *size)
00312 {
00313   size_t copylen;
00314   char *endp;
00315   char *retval;
00316 
00317   /* Fill in the information.  */
00318   endp = retval = (char *) xmalloc (st->total + 1);
00319 
00320   /* Always put an empty string at the beginning so that a zero offset
00321      can mean error.  */
00322   *endp++ = '\0';
00323 
00324   /* Now run through the tree and add all the string while also updating
00325      the offset members of the elfstrent records.  */
00326   copylen = 1;
00327   copystrings (st->root, &endp, &copylen);
00328   assert (copylen == st->total + 1);
00329   assert (endp == retval + st->total + 1);
00330   *size = copylen;
00331 
00332   return retval;
00333 }
00334 
00335 
00336 size_t
00337 strtaboffset (struct Strent *se)
00338 {
00339   return se->offset;
00340 }