/* Generic string table handling.
Copyright (C) 2000, 2001, 2002 Red Hat, Inc.
Written by Ulrich Drepper <drepper@redhat.com>, 2000.
This program is Open Source software; you can redistribute it and/or
modify it under the terms of the Open Software License version 1.0 as
published by the Open Source Initiative.
You should have received a copy of the Open Software License along
with this program; if not, you may obtain a copy of the Open Software
License version 1.0 from http://www.opensource.org/licenses/osl.php or
by writing the Open Source Initiative c/o Lawrence Rosen, Esq.,
3001 King Ranch Road, Ukiah, CA 95482. */
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
#include <assert.h>
#include <inttypes.h>
#include <libelf.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/param.h>
#include "libebl.h"
#ifndef MIN
# define MIN(a, b) ((a) < (b) ? (a) : (b))
#endif
struct Ebl_GStrent
{
const char *string;
size_t len;
struct Ebl_GStrent *next;
struct Ebl_GStrent *left;
struct Ebl_GStrent *right;
size_t offset;
unsigned int width;
char reverse[0];
};
struct memoryblock
{
struct memoryblock *next;
char memory[0];
};
struct Ebl_GStrtab
{
struct Ebl_GStrent *root;
struct memoryblock *memory;
char *backp;
size_t left;
size_t total;
unsigned int width;
bool nullstr;
struct Ebl_GStrent null;
};
/* Cache for the pagesize. We correct this value a bit so that `malloc'
is not allocating more than a page. */
static size_t ps;
struct Ebl_GStrtab *
ebl_gstrtabinit (unsigned int width, bool nullstr)
{
struct Ebl_GStrtab *ret;
if (ps == 0)
{
ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
assert (sizeof (struct memoryblock) < ps);
}
ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab));
if (ret != NULL)
{
ret->width = width;
ret->nullstr = nullstr;
if (nullstr)
{
ret->null.len = 1;
ret->null.string = (char *) calloc (1, width);
}
}
return ret;
}
static void
morememory (struct Ebl_GStrtab *st, size_t len)
{
struct memoryblock *newmem;
if (len < ps)
len = ps;
newmem = (struct memoryblock *) malloc (len);
if (newmem == NULL)
abort ();
newmem->next = st->memory;
st->memory = newmem;
st->backp = newmem->memory;
st->left = len - offsetof (struct memoryblock, memory);
}
void
ebl_gstrtabfree (struct Ebl_GStrtab *st)
{
struct memoryblock *mb = st->memory;
while (mb != NULL)
{
void *old = mb;
mb = mb->next;
free (old);
}
if (st->null.string != NULL)
free ((char *) st->null.string);
free (st);
}
static struct Ebl_GStrent *
newstring (struct Ebl_GStrtab *st, const char *str, size_t len)
{
struct Ebl_GStrent *newstr;
size_t align;
size_t i;
size_t j;
/* Compute the amount of padding needed to make the structure aligned. */
align = ((__alignof__ (struct Ebl_GStrent)
- (((uintptr_t) st->backp)
& (__alignof__ (struct Ebl_GStrent) - 1)))
& (__alignof__ (struct Ebl_GStrent) - 1));
/* Make sure there is enough room in the memory block. */
if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width)
{
morememory (st, sizeof (struct Ebl_GStrent) + len * st->width);
align = 0;
}
/* Create the reserved string. */
newstr = (struct Ebl_GStrent *) (st->backp + align);
newstr->string = str;
newstr->len = len;
newstr->width = st->width;
newstr->next = NULL;
newstr->left = NULL;
newstr->right = NULL;
newstr->offset = 0;
for (i = len - 2; i >= 0; --i)
for (j = st->width - 1; j >= 0; --j)
newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j];
for (j = 0; j < st->width; ++j)
newstr->reverse[(len - 1) * st->width + j] = '\0';
st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width;
st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width;
return newstr;
}
/* XXX This function should definitely be rewritten to use a balancing
tree algorith (AVL, red-black trees). For now a simple, correct
implementation is enough. */
static struct Ebl_GStrent **
searchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr)
{
int cmpres;
/* More strings? */
if (*sep == NULL)
{
*sep = newstr;
return sep;
}
/* Compare the strings. */
cmpres = memcmp ((*sep)->reverse, newstr->reverse,
(MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width);
if (cmpres == 0)
/* We found a matching string. */
return sep;
else if (cmpres > 0)
return searchstring (&(*sep)->left, newstr);
else
return searchstring (&(*sep)->right, newstr);
}
/* Add new string. The actual string is assumed to be permanent. */
struct Ebl_GStrent *
ebl_gstrtabadd (struct Ebl_GStrtab *st, const char *str, size_t len)
{
struct Ebl_GStrent *newstr;
struct Ebl_GStrent **sep;
/* Compute the string length if the caller doesn't know it. */
if (len == 0)
{
size_t j;
do
for (j = 0; j < st->width; ++j)
if (str[len * st->width + j] != '\0')
break;
while (j == st->width && ++len);
}
/* Make sure all "" strings get offset 0 but only if the table was
created with a special null entry in mind. */
if (len == 1 && st->null.string != NULL)
return &st->null;
/* Allocate memory for the new string and its associated information. */
newstr = newstring (st, str, len);
/* Search in the array for the place to insert the string. If there
is no string with matching prefix and no string with matching
leading substring, create a new entry. */
sep = searchstring (&st->root, newstr);
if (*sep != newstr)
{
/* This is not the same entry. This means we have a prefix match. */
if ((*sep)->len > newstr->len)
{
struct Ebl_GStrent *subs;
/* Check whether we already know this string. */
for (subs = (*sep)->next; subs != NULL; subs = subs->next)
if (subs->len == newstr->len)
{
/* We have an exact match with a substring. Free the memory
we allocated. */
st->left += (st->backp - (char *) newstr) * st->width;
st->backp = (char *) newstr;
return subs;
}
/* We have a new substring. This means we don't need the reverse
string of this entry anymore. */
st->backp -= newstr->len;
st->left += newstr->len;
newstr->next = (*sep)->next;
(*sep)->next = newstr;
}
else if ((*sep)->len != newstr->len)
{
/* When we get here it means that the string we are about to
add has a common prefix with a string we already have but
it is longer. In this case we have to put it first. */
st->total += newstr->len - (*sep)->len;
newstr->next = *sep;
newstr->left = (*sep)->left;
newstr->right = (*sep)->right;
*sep = newstr;
}
else
{
/* We have an exact match. Free the memory we allocated. */
st->left += (st->backp - (char *) newstr) * st->width;
st->backp = (char *) newstr;
newstr = *sep;
}
}
else
st->total += newstr->len;
return newstr;
}
static void
copystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp)
{
struct Ebl_GStrent *subs;
if (nodep->left != NULL)
copystrings (nodep->left, freep, offsetp);
/* Process the current node. */
nodep->offset = *offsetp;
*freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width);
*offsetp += nodep->len * nodep->width;
for (subs = nodep->next; subs != NULL; subs = subs->next)
{
assert (subs->len < nodep->len);
subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width;
assert (subs->offset != 0 || subs->string[0] == '\0');
}
if (nodep->right != NULL)
copystrings (nodep->right, freep, offsetp);
}
void
ebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data)
{
size_t copylen;
char *endp;
size_t nulllen = st->nullstr ? st->width : 0;
/* Fill in the information. */
data->d_buf = malloc (st->total + nulllen);
if (data->d_buf == NULL)
abort ();
/* The first byte must always be zero if we created the table with a
null string. */
if (st->nullstr)
memset (data->d_buf, '\0', st->width);
data->d_type = ELF_T_BYTE;
data->d_size = st->total + nulllen;
data->d_off = 0;
data->d_align = 1;
data->d_version = EV_CURRENT;
/* Now run through the tree and add all the string while also updating
the offset members of the elfstrent records. */
endp = (char *) data->d_buf + nulllen;
copylen = nulllen;
copystrings (st->root, &endp, ©len);
assert (copylen == st->total * st->width + nulllen);
}
size_t
ebl_gstrtaboffset (struct Ebl_GStrent *se)
{
return se->offset;
}