iconv/strtab.c

   1 /* C string table handling.
   2    Copyright (C) 2000-2013 Free Software Foundation, Inc.
   3    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #ifdef HAVE_CONFIG_H
  19 # include <config.h>
  20 #endif
  21
  22 #include <assert.h>
  23 #include <inttypes.h>
  24 #include <stddef.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include <sys/cdefs.h>
  29 #include <sys/param.h>
  30
  31
  32 struct Strent
  33 {
  34   const char *string;
  35   size_t len;
  36   struct Strent *next;
  37   struct Strent *left;
  38   struct Strent *right;
  39   size_t offset;
  40   char reverse[0];
  41 };
  42
  43
  44 struct memoryblock
  45 {
  46   struct memoryblock *next;
  47   char memory[0];
  48 };
  49
  50
  51 struct Strtab
  52 {
  53   struct Strent *root;
  54   struct memoryblock *memory;
  55   char *backp;
  56   size_t left;
  57   size_t total;
  58
  59   struct Strent null;
  60 };
  61
  62
  63 /* Cache for the pagesize.  We correct this value a bit so that `malloc'
  64    is not allocating more than a page.  */
  65 static size_t ps;
  66
  67
  68 extern void *xmalloc (size_t n)
  69   __attribute_malloc__ __attribute_alloc_size (1);
  70
  71 /* Prototypes for our functions that are used from iconvconfig.c.  If
  72    you change these, change also iconvconfig.c.  */
  73 /* Create new C string table object in memory.  */
  74 extern struct Strtab *strtabinit (void);
  75
  76 /* Free resources allocated for C string table ST.  */
  77 extern void strtabfree (struct Strtab *st);
  78
  79 /* Add string STR (length LEN is != 0) to C string table ST.  */
  80 extern struct Strent *strtabadd (struct Strtab *st, const char *str,
  81                                  size_t len);
  82
  83 /* Finalize string table ST and store size in *SIZE and return a pointer.  */
  84 extern void *strtabfinalize (struct Strtab *st, size_t *size);
  85
  86 /* Get offset in string table for string associated with SE.  */
  87 extern size_t strtaboffset (struct Strent *se);
  88
  89
  90 struct Strtab *
  91 strtabinit (void)
  92 {
  93   struct Strtab *ret;
  94
  95   if (ps == 0)
  96     {
  97       ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
  98       assert (sizeof (struct memoryblock) < ps);
  99     }
 100
 101   ret = (struct Strtab *) calloc (1, sizeof (struct Strtab));
 102   if (ret != NULL)
 103     {
 104       ret->null.len = 1;
 105       ret->null.string = "";
 106     }
 107   return ret;
 108 }
 109
 110
 111 static void
 112 morememory (struct Strtab *st, size_t len)
 113 {
 114   struct memoryblock *newmem;
 115
 116   if (len < ps)
 117     len = ps;
 118   newmem = (struct memoryblock *) malloc (len);
 119   if (newmem == NULL)
 120     abort ();
 121
 122   newmem->next = st->memory;
 123   st->memory = newmem;
 124   st->backp = newmem->memory;
 125   st->left = len - offsetof (struct memoryblock, memory);
 126 }
 127
 128
 129 void
 130 strtabfree (struct Strtab *st)
 131 {
 132   struct memoryblock *mb = st->memory;
 133
 134   while (mb != NULL)
 135     {
 136       void *old = mb;
 137       mb = mb->next;
 138       free (old);
 139     }
 140
 141   free (st);
 142 }
 143
 144
 145 static struct Strent *
 146 newstring (struct Strtab *st, const char *str, size_t len)
 147 {
 148   struct Strent *newstr;
 149   size_t align;
 150   int i;
 151
 152   /* Compute the amount of padding needed to make the structure aligned.  */
 153   align = ((__alignof__ (struct Strent)
 154             - (((uintptr_t) st->backp)
 155                & (__alignof__ (struct Strent) - 1)))
 156            & (__alignof__ (struct Strent) - 1));
 157
 158   /* Make sure there is enough room in the memory block.  */
 159   if (st->left < align + sizeof (struct Strent) + len)
 160     {
 161       morememory (st, sizeof (struct Strent) + len);
 162       align = 0;
 163     }
 164
 165   /* Create the reserved string.  */
 166   newstr = (struct Strent *) (st->backp + align);
 167   newstr->string = str;
 168   newstr->len = len;
 169   newstr->next = NULL;
 170   newstr->left = NULL;
 171   newstr->right = NULL;
 172   newstr->offset = 0;
 173   for (i = len - 2; i >= 0; --i)
 174     newstr->reverse[i] = str[len - 2 - i];
 175   newstr->reverse[len - 1] = '\0';
 176   st->backp += align + sizeof (struct Strent) + len;
 177   st->left -= align + sizeof (struct Strent) + len;
 178
 179   return newstr;
 180 }
 181
 182
 183 /* XXX This function should definitely be rewritten to use a balancing
 184    tree algorith (AVL, red-black trees).  For now a simple, correct
 185    implementation is enough.  */
 186 static struct Strent **
 187 searchstring (struct Strent **sep, struct Strent *newstr)
 188 {
 189   int cmpres;
 190
 191   /* More strings?  */
 192   if (*sep == NULL)
 193     {
 194       *sep = newstr;
 195       return sep;
 196     }
 197
 198   /* Compare the strings.  */
 199   cmpres = memcmp ((*sep)->reverse, newstr->reverse,
 200                    MIN ((*sep)->len, newstr->len) - 1);
 201   if (cmpres == 0)
 202     /* We found a matching string.  */
 203     return sep;
 204   else if (cmpres > 0)
 205     return searchstring (&(*sep)->left, newstr);
 206   else
 207     return searchstring (&(*sep)->right, newstr);
 208 }
 209
 210
 211 /* Add new string.  The actual string is assumed to be permanent.  */
 212 struct Strent *
 213 strtabadd (struct Strtab *st, const char *str, size_t len)
 214 {
 215   struct Strent *newstr;
 216   struct Strent **sep;
 217
 218   /* Compute the string length if the caller doesn't know it.  */
 219   if (len == 0)
 220     len = strlen (str) + 1;
 221
 222   /* Make sure all "" strings get offset 0.  */
 223   if (len == 1)
 224     return &st->null;
 225
 226   /* Allocate memory for the new string and its associated information.  */
 227   newstr = newstring (st, str, len);
 228
 229   /* Search in the array for the place to insert the string.  If there
 230      is no string with matching prefix and no string with matching
 231      leading substring, create a new entry.  */
 232   sep = searchstring (&st->root, newstr);
 233   if (*sep != newstr)
 234     {
 235       /* This is not the same entry.  This means we have a prefix match.  */
 236       if ((*sep)->len > newstr->len)
 237         {
 238           struct Strent *subs;
 239
 240           for (subs = (*sep)->next; subs; subs = subs->next)
 241             if (subs->len == newstr->len)
 242               {
 243                 /* We have an exact match with a substring.  Free the memory
 244                    we allocated.  */
 245                 st->left += st->backp - (char *) newstr;
 246                 st->backp = (char *) newstr;
 247
 248                 return subs;
 249               }
 250
 251           /* We have a new substring.  This means we don't need the reverse
 252              string of this entry anymore.  */
 253           st->backp -= newstr->len;
 254           st->left += newstr->len;
 255
 256           newstr->next = (*sep)->next;
 257           (*sep)->next = newstr;
 258         }
 259       else if ((*sep)->len != newstr->len)
 260         {
 261           /* When we get here it means that the string we are about to
 262              add has a common prefix with a string we already have but
 263              it is longer.  In this case we have to put it first.  */
 264           st->total += newstr->len - (*sep)->len;
 265           newstr->next = *sep;
 266           newstr->left = (*sep)->left;
 267           newstr->right = (*sep)->right;
 268           *sep = newstr;
 269         }
 270       else
 271         {
 272           /* We have an exact match.  Free the memory we allocated.  */
 273           st->left += st->backp - (char *) newstr;
 274           st->backp = (char *) newstr;
 275
 276           newstr = *sep;
 277         }
 278     }
 279   else
 280     st->total += newstr->len;
 281
 282   return newstr;
 283 }
 284
 285
 286 static void
 287 copystrings (struct Strent *nodep, char **freep, size_t *offsetp)
 288 {
 289   struct Strent *subs;
 290
 291   if (nodep->left != NULL)
 292     copystrings (nodep->left, freep, offsetp);
 293
 294   /* Process the current node.  */
 295   nodep->offset = *offsetp;
 296   *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
 297   *offsetp += nodep->len;
 298
 299   for (subs = nodep->next; subs != NULL; subs = subs->next)
 300     {
 301       assert (subs->len < nodep->len);
 302       subs->offset = nodep->offset + nodep->len - subs->len;
 303     }
 304
 305   if (nodep->right != NULL)
 306     copystrings (nodep->right, freep, offsetp);
 307 }
 308
 309
 310 void *
 311 strtabfinalize (struct Strtab *st, size_t *size)
 312 {
 313   size_t copylen;
 314   char *endp;
 315   char *retval;
 316
 317   /* Fill in the information.  */
 318   endp = retval = (char *) xmalloc (st->total + 1);
 319
 320   /* Always put an empty string at the beginning so that a zero offset
 321      can mean error.  */
 322   *endp++ = '\0';
 323
 324   /* Now run through the tree and add all the string while also updating
 325      the offset members of the elfstrent records.  */
 326   copylen = 1;
 327   copystrings (st->root, &endp, &copylen);
 328   assert (copylen == st->total + 1);
 329   assert (endp == retval + st->total + 1);
 330   *size = copylen;
 331
 332   return retval;
 333 }
 334
 335
 336 size_t
 337 strtaboffset (struct Strent *se)
 338 {
 339   return se->offset;
 340 }