libebl/eblgstrtab.c

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