OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [binutils-2.18.50/] [bfd/] [elf-strtab.c] - Blame information for rev 856

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.