iconv/strtab.c

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