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