← Back to branch summary

~ubuntu-branches/debian/lenny/elfutils/lenny

« back to all changes in this revision

Viewing changes to libebl/eblgstrtab.c

  • Committer: Bazaar Package Importer
  • Author(s): Kurt Roeckx
  • Date: 2006-08-27 15:48:23 UTC
  • Revision ID: james.westby@ubuntu.com-20060827154823-mjwd7ydlbxgwqn4u
Tags: upstream-0.123
Import upstream version 0.123

Show diffs side-by-side

added added

removed removed

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