iconv/strtab.c

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