← Back to branch summary

~ubuntu-branches/ubuntu/hoary/binutils/hoary

« back to all changes in this revision

Viewing changes to bfd/elf-strtab.c

  • Committer: Bazaar Package Importer
  • Author(s): James Troup
  • Date: 2004-05-19 10:35:44 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20040519103544-17h3o6e8pwndydrg
Tags: 2.14.90.0.7-8
debian/rules: don't use gcc-2.95 on m68k.  Thanks to Adam Conrad for
pointing this out.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bfd/elf-strtab.c
 
1
/* ELF strtab with GC and suffix merging support.
 
2
   Copyright 2001, 2002 Free Software Foundation, Inc.
 
3
   Written by Jakub Jelinek <jakub@redhat.com>.
 
4
 
 
5
   This file is part of BFD, the Binary File Descriptor library.
 
6
 
 
7
   This program is free software; you can redistribute it and/or modify
 
8
   it under the terms of the GNU General Public License as published by
 
9
   the Free Software Foundation; either version 2 of the License, or
 
10
   (at your option) any later version.
 
11
 
 
12
   This program is distributed in the hope that it will be useful,
 
13
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
   GNU General Public License for more details.
 
16
 
 
17
   You should have received a copy of the GNU General Public License
 
18
   along with this program; if not, write to the Free Software
 
19
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
20
 
 
21
#include "bfd.h"
 
22
#include "sysdep.h"
 
23
#include "libbfd.h"
 
24
#include "elf-bfd.h"
 
25
#include "hashtab.h"
 
26
#include "libiberty.h"
 
27
 
 
28
/* An entry in the strtab hash table.  */
 
29
 
 
30
struct elf_strtab_hash_entry
 
31
{
 
32
  struct bfd_hash_entry root;
 
33
  /* Length of this entry.  */
 
34
  unsigned int len;
 
35
  unsigned int refcount;
 
36
  union {
 
37
    /* Index within the merged section.  */
 
38
    bfd_size_type index;
 
39
    /* Entry this is a suffix of (if len is 0).  */
 
40
    struct elf_strtab_hash_entry *suffix;
 
41
    struct elf_strtab_hash_entry *next;
 
42
  } u;
 
43
};
 
44
 
 
45
/* The strtab hash table.  */
 
46
 
 
47
struct elf_strtab_hash
 
48
{
 
49
  struct bfd_hash_table table;
 
50
  /* Next available index.  */
 
51
  bfd_size_type size;
 
52
  /* Number of array entries alloced.  */
 
53
  bfd_size_type alloced;
 
54
  /* Final strtab size.  */
 
55
  bfd_size_type sec_size;
 
56
  /* Array of pointers to strtab entries.  */
 
57
  struct elf_strtab_hash_entry **array;
 
58
};
 
59
 
 
60
/* Routine to create an entry in a section merge hashtab.  */
 
61
 
 
62
static struct bfd_hash_entry *
 
63
elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
 
64
                         struct bfd_hash_table *table,
 
65
                         const char *string)
 
66
{
 
67
  /* Allocate the structure if it has not already been allocated by a
 
68
     subclass.  */
 
69
  if (entry == NULL)
 
70
    entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
 
71
  if (entry == NULL)
 
72
    return NULL;
 
73
 
 
74
  /* Call the allocation method of the superclass.  */
 
75
  entry = bfd_hash_newfunc (entry, table, string);
 
76
 
 
77
  if (entry)
 
78
    {
 
79
      /* Initialize the local fields.  */
 
80
      struct elf_strtab_hash_entry *ret;
 
81
 
 
82
      ret = (struct elf_strtab_hash_entry *) entry;
 
83
      ret->u.index = -1;
 
84
      ret->refcount = 0;
 
85
      ret->len = 0;
 
86
    }
 
87
 
 
88
  return entry;
 
89
}
 
90
 
 
91
/* Create a new hash table.  */
 
92
 
 
93
struct elf_strtab_hash *
 
94
_bfd_elf_strtab_init (void)
 
95
{
 
96
  struct elf_strtab_hash *table;
 
97
  bfd_size_type amt = sizeof (struct elf_strtab_hash);
 
98
 
 
99
  table = bfd_malloc (amt);
 
100
  if (table == NULL)
 
101
    return NULL;
 
102
 
 
103
  if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
 
104
    {
 
105
      free (table);
 
106
      return NULL;
 
107
    }
 
108
 
 
109
  table->sec_size = 0;
 
110
  table->size = 1;
 
111
  table->alloced = 64;
 
112
  amt = sizeof (struct elf_strtab_hasn_entry *);
 
113
  table->array = bfd_malloc (table->alloced * amt);
 
114
  if (table->array == NULL)
 
115
    {
 
116
      free (table);
 
117
      return NULL;
 
118
    }
 
119
 
 
120
  table->array[0] = NULL;
 
121
 
 
122
  return table;
 
123
}
 
124
 
 
125
/* Free a strtab.  */
 
126
 
 
127
void
 
128
_bfd_elf_strtab_free (struct elf_strtab_hash *tab)
 
129
{
 
130
  bfd_hash_table_free (&tab->table);
 
131
  free (tab->array);
 
132
  free (tab);
 
133
}
 
134
 
 
135
/* Get the index of an entity in a hash table, adding it if it is not
 
136
   already present.  */
 
137
 
 
138
bfd_size_type
 
139
_bfd_elf_strtab_add (struct elf_strtab_hash *tab,
 
140
                     const char *str,
 
141
                     bfd_boolean copy)
 
142
{
 
143
  register struct elf_strtab_hash_entry *entry;
 
144
 
 
145
  /* We handle this specially, since we don't want to do refcounting
 
146
     on it.  */
 
147
  if (*str == '\0')
 
148
    return 0;
 
149
 
 
150
  BFD_ASSERT (tab->sec_size == 0);
 
151
  entry = (struct elf_strtab_hash_entry *)
 
152
          bfd_hash_lookup (&tab->table, str, TRUE, copy);
 
153
 
 
154
  if (entry == NULL)
 
155
    return (bfd_size_type) -1;
 
156
 
 
157
  entry->refcount++;
 
158
  if (entry->len == 0)
 
159
    {
 
160
      entry->len = strlen (str) + 1;
 
161
      if (tab->size == tab->alloced)
 
162
        {
 
163
          bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
 
164
          tab->alloced *= 2;
 
165
          tab->array = bfd_realloc (tab->array, tab->alloced * amt);
 
166
          if (tab->array == NULL)
 
167
            return (bfd_size_type) -1;
 
168
        }
 
169
 
 
170
      entry->u.index = tab->size++;
 
171
      tab->array[entry->u.index] = entry;
 
172
    }
 
173
  return entry->u.index;
 
174
}
 
175
 
 
176
void
 
177
_bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
 
178
{
 
179
  if (idx == 0 || idx == (bfd_size_type) -1)
 
180
    return;
 
181
  BFD_ASSERT (tab->sec_size == 0);
 
182
  BFD_ASSERT (idx < tab->size);
 
183
  ++tab->array[idx]->refcount;
 
184
}
 
185
 
 
186
void
 
187
_bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
 
188
{
 
189
  if (idx == 0 || idx == (bfd_size_type) -1)
 
190
    return;
 
191
  BFD_ASSERT (tab->sec_size == 0);
 
192
  BFD_ASSERT (idx < tab->size);
 
193
  BFD_ASSERT (tab->array[idx]->refcount > 0);
 
194
  --tab->array[idx]->refcount;
 
195
}
 
196
 
 
197
void
 
198
_bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
 
199
{
 
200
  bfd_size_type idx;
 
201
 
 
202
  for (idx = 1; idx < tab->size; ++idx)
 
203
    tab->array[idx]->refcount = 0;
 
204
}
 
205
 
 
206
bfd_size_type
 
207
_bfd_elf_strtab_size (struct elf_strtab_hash *tab)
 
208
{
 
209
  return tab->sec_size ? tab->sec_size : tab->size;
 
210
}
 
211
 
 
212
bfd_size_type
 
213
_bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
 
214
{
 
215
  struct elf_strtab_hash_entry *entry;
 
216
 
 
217
  if (idx == 0)
 
218
    return 0;
 
219
  BFD_ASSERT (idx < tab->size);
 
220
  BFD_ASSERT (tab->sec_size);
 
221
  entry = tab->array[idx];
 
222
  BFD_ASSERT (entry->refcount > 0);
 
223
  entry->refcount--;
 
224
  return tab->array[idx]->u.index;
 
225
}
 
226
 
 
227
bfd_boolean
 
228
_bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
 
229
{
 
230
  bfd_size_type off = 1, i;
 
231
 
 
232
  if (bfd_bwrite ("", 1, abfd) != 1)
 
233
    return FALSE;
 
234
 
 
235
  for (i = 1; i < tab->size; ++i)
 
236
    {
 
237
      register const char *str;
 
238
      register size_t len;
 
239
 
 
240
      str = tab->array[i]->root.string;
 
241
      len = tab->array[i]->len;
 
242
      BFD_ASSERT (tab->array[i]->refcount == 0);
 
243
      if (len == 0)
 
244
        continue;
 
245
 
 
246
      if (bfd_bwrite (str, len, abfd) != len)
 
247
        return FALSE;
 
248
 
 
249
      off += len;
 
250
    }
 
251
 
 
252
  BFD_ASSERT (off == tab->sec_size);
 
253
  return TRUE;
 
254
}
 
255
 
 
256
/* Compare two elf_strtab_hash_entry structures.  This is called via qsort.  */
 
257
 
 
258
static int
 
259
cmplengthentry (const void *a, const void *b)
 
260
{
 
261
  struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
 
262
  struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
 
263
 
 
264
  if (A->len < B->len)
 
265
    return 1;
 
266
  else if (A->len > B->len)
 
267
    return -1;
 
268
 
 
269
  return memcmp (A->root.string, B->root.string, A->len);
 
270
}
 
271
 
 
272
static int
 
273
last4_eq (const void *a, const void *b)
 
274
{
 
275
  const struct elf_strtab_hash_entry *A = a;
 
276
  const struct elf_strtab_hash_entry *B = b;
 
277
 
 
278
  if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
 
279
      != 0)
 
280
    /* This was a hashtable collision.  */
 
281
    return 0;
 
282
 
 
283
  if (A->len <= B->len)
 
284
    /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
 
285
       not to be equal by the hash table.  */
 
286
    return 0;
 
287
 
 
288
  return memcmp (A->root.string + (A->len - B->len),
 
289
                 B->root.string, B->len - 5) == 0;
 
290
}
 
291
 
 
292
/* This function assigns final string table offsets for used strings,
 
293
   merging strings matching suffixes of longer strings if possible.  */
 
294
 
 
295
void
 
296
_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
 
297
{
 
298
  struct elf_strtab_hash_entry **array, **a, **end, *e;
 
299
  htab_t last4tab = NULL;
 
300
  bfd_size_type size, amt;
 
301
  struct elf_strtab_hash_entry *last[256], **last_ptr[256];
 
302
 
 
303
  /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
 
304
     a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
 
305
     Besides, indexing with a long long wouldn't give anything but extra
 
306
     cycles.  */
 
307
  size_t i;
 
308
 
 
309
  /* Now sort the strings by length, longest first.  */
 
310
  array = NULL;
 
311
  amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
 
312
  array = bfd_malloc (amt);
 
313
  if (array == NULL)
 
314
    goto alloc_failure;
 
315
 
 
316
  memset (last, 0, sizeof (last));
 
317
  for (i = 0; i < 256; ++i)
 
318
    last_ptr[i] = &last[i];
 
319
  for (i = 1, a = array; i < tab->size; ++i)
 
320
    if (tab->array[i]->refcount)
 
321
      *a++ = tab->array[i];
 
322
    else
 
323
      tab->array[i]->len = 0;
 
324
 
 
325
  size = a - array;
 
326
 
 
327
  qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
 
328
 
 
329
  last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
 
330
  if (last4tab == NULL)
 
331
    goto alloc_failure;
 
332
 
 
333
  /* Now insert the strings into hash tables (strings with last 4 characters
 
334
     and strings with last character equal), look for longer strings which
 
335
     we're suffix of.  */
 
336
  for (a = array, end = array + size; a < end; a++)
 
337
    {
 
338
      register hashval_t hash;
 
339
      unsigned int c;
 
340
      unsigned int j;
 
341
      const unsigned char *s;
 
342
      void **p;
 
343
 
 
344
      e = *a;
 
345
      if (e->len > 4)
 
346
        {
 
347
          s = e->root.string + e->len - 1;
 
348
          hash = 0;
 
349
          for (j = 0; j < 4; j++)
 
350
            {
 
351
              c = *--s;
 
352
              hash += c + (c << 17);
 
353
              hash ^= hash >> 2;
 
354
            }
 
355
          p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
 
356
          if (p == NULL)
 
357
            goto alloc_failure;
 
358
          if (*p)
 
359
            {
 
360
              struct elf_strtab_hash_entry *ent;
 
361
 
 
362
              ent = *p;
 
363
              e->u.suffix = ent;
 
364
              e->len = 0;
 
365
              continue;
 
366
            }
 
367
          else
 
368
            *p = e;
 
369
        }
 
370
      else
 
371
        {
 
372
          struct elf_strtab_hash_entry *tem;
 
373
 
 
374
          c = e->root.string[e->len - 2] & 0xff;
 
375
 
 
376
          for (tem = last[c]; tem; tem = tem->u.next)
 
377
            if (tem->len > e->len
 
378
                && memcmp (tem->root.string + (tem->len - e->len),
 
379
                           e->root.string, e->len - 1) == 0)
 
380
              break;
 
381
          if (tem)
 
382
            {
 
383
              e->u.suffix = tem;
 
384
              e->len = 0;
 
385
              continue;
 
386
            }
 
387
        }
 
388
 
 
389
      c = e->root.string[e->len - 2] & 0xff;
 
390
      /* Put longest strings first.  */
 
391
      *last_ptr[c] = e;
 
392
      last_ptr[c] = &e->u.next;
 
393
      e->u.next = NULL;
 
394
    }
 
395
 
 
396
alloc_failure:
 
397
  if (array)
 
398
    free (array);
 
399
  if (last4tab)
 
400
    htab_delete (last4tab);
 
401
 
 
402
  /* Now assign positions to the strings we want to keep.  */
 
403
  size = 1;
 
404
  for (i = 1; i < tab->size; ++i)
 
405
    {
 
406
      e = tab->array[i];
 
407
      if (e->refcount && e->len)
 
408
        {
 
409
          e->u.index = size;
 
410
          size += e->len;
 
411
        }
 
412
    }
 
413
 
 
414
  tab->sec_size = size;
 
415
 
 
416
  /* And now adjust the rest.  */
 
417
  for (i = 1; i < tab->size; ++i)
 
418
    {
 
419
      e = tab->array[i];
 
420
      if (e->refcount && ! e->len)
 
421
        e->u.index = e->u.suffix->u.index
 
422
                     + (e->u.suffix->len - strlen (e->root.string) - 1);
 
423
    }
 
424
}