|
Packit |
6c4009 |
/* C string table handling.
|
|
Packit |
6c4009 |
Copyright (C) 2000-2018 Free Software Foundation, Inc.
|
|
Packit |
6c4009 |
Written by Ulrich Drepper <drepper@redhat.com>, 2000.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
This program is free software; you can redistribute it and/or modify
|
|
Packit |
6c4009 |
it under the terms of the GNU General Public License as published by
|
|
Packit |
6c4009 |
the Free Software Foundation; either version 2, or (at your option)
|
|
Packit |
6c4009 |
any later version.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
This program is distributed in the hope that it will be useful,
|
|
Packit |
6c4009 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
6c4009 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit |
6c4009 |
GNU General Public License for more details.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
You should have received a copy of the GNU General Public License
|
|
Packit |
6c4009 |
along with this program; if not, see <http://www.gnu.org/licenses/>. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef HAVE_CONFIG_H
|
|
Packit |
6c4009 |
# include <config.h>
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <assert.h>
|
|
Packit |
6c4009 |
#include <inttypes.h>
|
|
Packit |
6c4009 |
#include <stddef.h>
|
|
Packit |
6c4009 |
#include <stdlib.h>
|
|
Packit |
6c4009 |
#include <string.h>
|
|
Packit |
6c4009 |
#include <unistd.h>
|
|
Packit |
6c4009 |
#include <sys/cdefs.h>
|
|
Packit |
6c4009 |
#include <sys/param.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
struct Strent
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
const char *string;
|
|
Packit |
6c4009 |
size_t len;
|
|
Packit |
6c4009 |
struct Strent *next;
|
|
Packit |
6c4009 |
struct Strent *left;
|
|
Packit |
6c4009 |
struct Strent *right;
|
|
Packit |
6c4009 |
size_t offset;
|
|
Packit |
6c4009 |
char reverse[0];
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
struct memoryblock
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct memoryblock *next;
|
|
Packit |
6c4009 |
char memory[0];
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
struct Strtab
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct Strent *root;
|
|
Packit |
6c4009 |
struct memoryblock *memory;
|
|
Packit |
6c4009 |
char *backp;
|
|
Packit |
6c4009 |
size_t left;
|
|
Packit |
6c4009 |
size_t total;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
struct Strent null;
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Cache for the pagesize. We correct this value a bit so that `malloc'
|
|
Packit |
6c4009 |
is not allocating more than a page. */
|
|
Packit |
6c4009 |
static size_t ps;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <programs/xmalloc.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Prototypes for our functions that are used from iconvconfig.c. If
|
|
Packit |
6c4009 |
you change these, change also iconvconfig.c. */
|
|
Packit |
6c4009 |
/* Create new C string table object in memory. */
|
|
Packit |
6c4009 |
extern struct Strtab *strtabinit (void);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Free resources allocated for C string table ST. */
|
|
Packit |
6c4009 |
extern void strtabfree (struct Strtab *st);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Add string STR (length LEN is != 0) to C string table ST. */
|
|
Packit |
6c4009 |
extern struct Strent *strtabadd (struct Strtab *st, const char *str,
|
|
Packit |
6c4009 |
size_t len);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Finalize string table ST and store size in *SIZE and return a pointer. */
|
|
Packit |
6c4009 |
extern void *strtabfinalize (struct Strtab *st, size_t *size);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Get offset in string table for string associated with SE. */
|
|
Packit |
6c4009 |
extern size_t strtaboffset (struct Strent *se);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
struct Strtab *
|
|
Packit |
6c4009 |
strtabinit (void)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct Strtab *ret;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (ps == 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
|
|
Packit |
6c4009 |
assert (sizeof (struct memoryblock) < ps);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
ret = (struct Strtab *) calloc (1, sizeof (struct Strtab));
|
|
Packit |
6c4009 |
if (ret != NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
ret->null.len = 1;
|
|
Packit |
6c4009 |
ret->null.string = "";
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
return ret;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
morememory (struct Strtab *st, size_t len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct memoryblock *newmem;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (len < ps)
|
|
Packit |
6c4009 |
len = ps;
|
|
Packit |
6c4009 |
newmem = (struct memoryblock *) malloc (len);
|
|
Packit |
6c4009 |
if (newmem == NULL)
|
|
Packit |
6c4009 |
abort ();
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
newmem->next = st->memory;
|
|
Packit |
6c4009 |
st->memory = newmem;
|
|
Packit |
6c4009 |
st->backp = newmem->memory;
|
|
Packit |
6c4009 |
st->left = len - offsetof (struct memoryblock, memory);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
void
|
|
Packit |
6c4009 |
strtabfree (struct Strtab *st)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct memoryblock *mb = st->memory;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
while (mb != NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
void *old = mb;
|
|
Packit |
6c4009 |
mb = mb->next;
|
|
Packit |
6c4009 |
free (old);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
free (st);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static struct Strent *
|
|
Packit |
6c4009 |
newstring (struct Strtab *st, const char *str, size_t len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct Strent *newstr;
|
|
Packit |
6c4009 |
size_t align;
|
|
Packit |
6c4009 |
int i;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Compute the amount of padding needed to make the structure aligned. */
|
|
Packit |
6c4009 |
align = ((__alignof__ (struct Strent)
|
|
Packit |
6c4009 |
- (((uintptr_t) st->backp)
|
|
Packit |
6c4009 |
& (__alignof__ (struct Strent) - 1)))
|
|
Packit |
6c4009 |
& (__alignof__ (struct Strent) - 1));
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Make sure there is enough room in the memory block. */
|
|
Packit |
6c4009 |
if (st->left < align + sizeof (struct Strent) + len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
morememory (st, sizeof (struct Strent) + len);
|
|
Packit |
6c4009 |
align = 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Create the reserved string. */
|
|
Packit |
6c4009 |
newstr = (struct Strent *) (st->backp + align);
|
|
Packit |
6c4009 |
newstr->string = str;
|
|
Packit |
6c4009 |
newstr->len = len;
|
|
Packit |
6c4009 |
newstr->next = NULL;
|
|
Packit |
6c4009 |
newstr->left = NULL;
|
|
Packit |
6c4009 |
newstr->right = NULL;
|
|
Packit |
6c4009 |
newstr->offset = 0;
|
|
Packit |
6c4009 |
for (i = len - 2; i >= 0; --i)
|
|
Packit |
6c4009 |
newstr->reverse[i] = str[len - 2 - i];
|
|
Packit |
6c4009 |
newstr->reverse[len - 1] = '\0';
|
|
Packit |
6c4009 |
st->backp += align + sizeof (struct Strent) + len;
|
|
Packit |
6c4009 |
st->left -= align + sizeof (struct Strent) + len;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return newstr;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* XXX This function should definitely be rewritten to use a balancing
|
|
Packit |
6c4009 |
tree algorithm (AVL, red-black trees). For now a simple, correct
|
|
Packit |
6c4009 |
implementation is enough. */
|
|
Packit |
6c4009 |
static struct Strent **
|
|
Packit |
6c4009 |
searchstring (struct Strent **sep, struct Strent *newstr)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
int cmpres;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* More strings? */
|
|
Packit |
6c4009 |
if (*sep == NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
*sep = newstr;
|
|
Packit |
6c4009 |
return sep;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Compare the strings. */
|
|
Packit |
6c4009 |
cmpres = memcmp ((*sep)->reverse, newstr->reverse,
|
|
Packit |
6c4009 |
MIN ((*sep)->len, newstr->len) - 1);
|
|
Packit |
6c4009 |
if (cmpres == 0)
|
|
Packit |
6c4009 |
/* We found a matching string. */
|
|
Packit |
6c4009 |
return sep;
|
|
Packit |
6c4009 |
else if (cmpres > 0)
|
|
Packit |
6c4009 |
return searchstring (&(*sep)->left, newstr);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
return searchstring (&(*sep)->right, newstr);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Add new string. The actual string is assumed to be permanent. */
|
|
Packit |
6c4009 |
struct Strent *
|
|
Packit |
6c4009 |
strtabadd (struct Strtab *st, const char *str, size_t len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct Strent *newstr;
|
|
Packit |
6c4009 |
struct Strent **sep;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Compute the string length if the caller doesn't know it. */
|
|
Packit |
6c4009 |
if (len == 0)
|
|
Packit |
6c4009 |
len = strlen (str) + 1;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Make sure all "" strings get offset 0. */
|
|
Packit |
6c4009 |
if (len == 1)
|
|
Packit |
6c4009 |
return &st->null;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Allocate memory for the new string and its associated information. */
|
|
Packit |
6c4009 |
newstr = newstring (st, str, len);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Search in the array for the place to insert the string. If there
|
|
Packit |
6c4009 |
is no string with matching prefix and no string with matching
|
|
Packit |
6c4009 |
leading substring, create a new entry. */
|
|
Packit |
6c4009 |
sep = searchstring (&st->root, newstr);
|
|
Packit |
6c4009 |
if (*sep != newstr)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* This is not the same entry. This means we have a prefix match. */
|
|
Packit |
6c4009 |
if ((*sep)->len > newstr->len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct Strent *subs;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
for (subs = (*sep)->next; subs; subs = subs->next)
|
|
Packit |
6c4009 |
if (subs->len == newstr->len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* We have an exact match with a substring. Free the memory
|
|
Packit |
6c4009 |
we allocated. */
|
|
Packit |
6c4009 |
st->left += st->backp - (char *) newstr;
|
|
Packit |
6c4009 |
st->backp = (char *) newstr;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return subs;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* We have a new substring. This means we don't need the reverse
|
|
Packit |
6c4009 |
string of this entry anymore. */
|
|
Packit |
6c4009 |
st->backp -= newstr->len;
|
|
Packit |
6c4009 |
st->left += newstr->len;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
newstr->next = (*sep)->next;
|
|
Packit |
6c4009 |
(*sep)->next = newstr;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else if ((*sep)->len != newstr->len)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* When we get here it means that the string we are about to
|
|
Packit |
6c4009 |
add has a common prefix with a string we already have but
|
|
Packit |
6c4009 |
it is longer. In this case we have to put it first. */
|
|
Packit |
6c4009 |
st->total += newstr->len - (*sep)->len;
|
|
Packit |
6c4009 |
newstr->next = *sep;
|
|
Packit |
6c4009 |
newstr->left = (*sep)->left;
|
|
Packit |
6c4009 |
newstr->right = (*sep)->right;
|
|
Packit |
6c4009 |
*sep = newstr;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* We have an exact match. Free the memory we allocated. */
|
|
Packit |
6c4009 |
st->left += st->backp - (char *) newstr;
|
|
Packit |
6c4009 |
st->backp = (char *) newstr;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
newstr = *sep;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
st->total += newstr->len;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return newstr;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
copystrings (struct Strent *nodep, char **freep, size_t *offsetp)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct Strent *subs;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (nodep->left != NULL)
|
|
Packit |
6c4009 |
copystrings (nodep->left, freep, offsetp);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Process the current node. */
|
|
Packit |
6c4009 |
nodep->offset = *offsetp;
|
|
Packit |
6c4009 |
*freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
|
|
Packit |
6c4009 |
*offsetp += nodep->len;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
for (subs = nodep->next; subs != NULL; subs = subs->next)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
assert (subs->len < nodep->len);
|
|
Packit |
6c4009 |
subs->offset = nodep->offset + nodep->len - subs->len;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (nodep->right != NULL)
|
|
Packit |
6c4009 |
copystrings (nodep->right, freep, offsetp);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
void *
|
|
Packit |
6c4009 |
strtabfinalize (struct Strtab *st, size_t *size)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
size_t copylen;
|
|
Packit |
6c4009 |
char *endp;
|
|
Packit |
6c4009 |
char *retval;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Fill in the information. */
|
|
Packit |
6c4009 |
endp = retval = (char *) xmalloc (st->total + 1);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Always put an empty string at the beginning so that a zero offset
|
|
Packit |
6c4009 |
can mean error. */
|
|
Packit |
6c4009 |
*endp++ = '\0';
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Now run through the tree and add all the string while also updating
|
|
Packit |
6c4009 |
the offset members of the elfstrent records. */
|
|
Packit |
6c4009 |
copylen = 1;
|
|
Packit |
6c4009 |
copystrings (st->root, &endp, ©len);
|
|
Packit |
6c4009 |
assert (copylen == st->total + 1);
|
|
Packit |
6c4009 |
assert (endp == retval + st->total + 1);
|
|
Packit |
6c4009 |
*size = copylen;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return retval;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
size_t
|
|
Packit |
6c4009 |
strtaboffset (struct Strent *se)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
return se->offset;
|
|
Packit |
6c4009 |
}
|