iconv/strtab.c

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