1: /* C string table handling.
    2:    Copyright (C) 2000, 2001, 2005 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) __attribute_malloc__;
   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: }