Merge branch 'vendor/GCC50'
[dragonfly.git] / contrib / binutils-2.24 / bfd / elf-strtab.c
1 /* 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 = (struct bfd_hash_entry *)
72         bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
73   if (entry == NULL)
74     return NULL;
75
76   /* Call the allocation method of the superclass.  */
77   entry = bfd_hash_newfunc (entry, table, string);
78
79   if (entry)
80     {
81       /* Initialize the local fields.  */
82       struct elf_strtab_hash_entry *ret;
83
84       ret = (struct elf_strtab_hash_entry *) entry;
85       ret->u.index = -1;
86       ret->refcount = 0;
87       ret->len = 0;
88     }
89
90   return entry;
91 }
92
93 /* Create a new hash table.  */
94
95 struct elf_strtab_hash *
96 _bfd_elf_strtab_init (void)
97 {
98   struct elf_strtab_hash *table;
99   bfd_size_type amt = sizeof (struct elf_strtab_hash);
100
101   table = (struct elf_strtab_hash *) bfd_malloc (amt);
102   if (table == NULL)
103     return NULL;
104
105   if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
106                             sizeof (struct elf_strtab_hash_entry)))
107     {
108       free (table);
109       return NULL;
110     }
111
112   table->sec_size = 0;
113   table->size = 1;
114   table->alloced = 64;
115   amt = sizeof (struct elf_strtab_hasn_entry *);
116   table->array = (struct elf_strtab_hash_entry **)
117       bfd_malloc (table->alloced * amt);
118   if (table->array == NULL)
119     {
120       free (table);
121       return NULL;
122     }
123
124   table->array[0] = NULL;
125
126   return table;
127 }
128
129 /* Free a strtab.  */
130
131 void
132 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
133 {
134   bfd_hash_table_free (&tab->table);
135   free (tab->array);
136   free (tab);
137 }
138
139 /* Get the index of an entity in a hash table, adding it if it is not
140    already present.  */
141
142 bfd_size_type
143 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
144                      const char *str,
145                      bfd_boolean copy)
146 {
147   register struct elf_strtab_hash_entry *entry;
148
149   /* We handle this specially, since we don't want to do refcounting
150      on it.  */
151   if (*str == '\0')
152     return 0;
153
154   BFD_ASSERT (tab->sec_size == 0);
155   entry = (struct elf_strtab_hash_entry *)
156           bfd_hash_lookup (&tab->table, str, TRUE, copy);
157
158   if (entry == NULL)
159     return (bfd_size_type) -1;
160
161   entry->refcount++;
162   if (entry->len == 0)
163     {
164       entry->len = strlen (str) + 1;
165       /* 2G strings lose.  */
166       BFD_ASSERT (entry->len > 0);
167       if (tab->size == tab->alloced)
168         {
169           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
170           tab->alloced *= 2;
171           tab->array = (struct elf_strtab_hash_entry **)
172               bfd_realloc_or_free (tab->array, tab->alloced * amt);
173           if (tab->array == NULL)
174             return (bfd_size_type) -1;
175         }
176
177       entry->u.index = tab->size++;
178       tab->array[entry->u.index] = entry;
179     }
180   return entry->u.index;
181 }
182
183 void
184 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
185 {
186   if (idx == 0 || idx == (bfd_size_type) -1)
187     return;
188   BFD_ASSERT (tab->sec_size == 0);
189   BFD_ASSERT (idx < tab->size);
190   ++tab->array[idx]->refcount;
191 }
192
193 void
194 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
195 {
196   if (idx == 0 || idx == (bfd_size_type) -1)
197     return;
198   BFD_ASSERT (tab->sec_size == 0);
199   BFD_ASSERT (idx < tab->size);
200   BFD_ASSERT (tab->array[idx]->refcount > 0);
201   --tab->array[idx]->refcount;
202 }
203
204 unsigned int
205 _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, bfd_size_type idx)
206 {
207   return tab->array[idx]->refcount;
208 }
209
210 void
211 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
212 {
213   bfd_size_type idx;
214
215   for (idx = 1; idx < tab->size; idx++)
216     tab->array[idx]->refcount = 0;
217 }
218
219 /* Downsizes strtab.  Entries from IDX up to the current size are
220    removed from the array.  */
221 void
222 _bfd_elf_strtab_restore_size (struct elf_strtab_hash *tab, bfd_size_type idx)
223 {
224   bfd_size_type curr_size = tab->size;
225
226   BFD_ASSERT (tab->sec_size == 0);
227   BFD_ASSERT (idx <= curr_size);
228   tab->size = idx;
229   for (; idx < curr_size; ++idx)
230     {
231       /* We don't remove entries from the hash table, just set their
232          REFCOUNT to zero.  Setting LEN zero will result in the size
233          growing if the entry is added again.  See _bfd_elf_strtab_add.  */
234       tab->array[idx]->refcount = 0;
235       tab->array[idx]->len = 0;
236     }
237 }
238
239 bfd_size_type
240 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
241 {
242   return tab->sec_size ? tab->sec_size : tab->size;
243 }
244
245 bfd_size_type
246 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
247 {
248   struct elf_strtab_hash_entry *entry;
249
250   if (idx == 0)
251     return 0;
252   BFD_ASSERT (idx < tab->size);
253   BFD_ASSERT (tab->sec_size);
254   entry = tab->array[idx];
255   BFD_ASSERT (entry->refcount > 0);
256   entry->refcount--;
257   return tab->array[idx]->u.index;
258 }
259
260 bfd_boolean
261 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
262 {
263   bfd_size_type off = 1, i;
264
265   if (bfd_bwrite ("", 1, abfd) != 1)
266     return FALSE;
267
268   for (i = 1; i < tab->size; ++i)
269     {
270       register const char *str;
271       register unsigned int len;
272
273       BFD_ASSERT (tab->array[i]->refcount == 0);
274       len = tab->array[i]->len;
275       if ((int) len < 0)
276         continue;
277
278       str = tab->array[i]->root.string;
279       if (bfd_bwrite (str, len, abfd) != len)
280         return FALSE;
281
282       off += len;
283     }
284
285   BFD_ASSERT (off == tab->sec_size);
286   return TRUE;
287 }
288
289 /* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
290
291 static int
292 strrevcmp (const void *a, const void *b)
293 {
294   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
295   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
296   unsigned int lenA = A->len;
297   unsigned int lenB = B->len;
298   const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
299   const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
300   int l = lenA < lenB ? lenA : lenB;
301
302   while (l)
303     {
304       if (*s != *t)
305         return (int) *s - (int) *t;
306       s--;
307       t--;
308       l--;
309     }
310   return lenA - lenB;
311 }
312
313 static inline int
314 is_suffix (const struct elf_strtab_hash_entry *A,
315            const struct elf_strtab_hash_entry *B)
316 {
317   if (A->len <= B->len)
318     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
319        not to be equal by the hash table.  */
320     return 0;
321
322   return memcmp (A->root.string + (A->len - B->len),
323                  B->root.string, B->len - 1) == 0;
324 }
325
326 /* This function assigns final string table offsets for used strings,
327    merging strings matching suffixes of longer strings if possible.  */
328
329 void
330 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
331 {
332   struct elf_strtab_hash_entry **array, **a, *e;
333   bfd_size_type size, amt;
334
335   /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
336      a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
337      Besides, indexing with a long long wouldn't give anything but extra
338      cycles.  */
339   size_t i;
340
341   /* Sort the strings by suffix and length.  */
342   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
343   array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
344   if (array == NULL)
345     goto alloc_failure;
346
347   for (i = 1, a = array; i < tab->size; ++i)
348     {
349       e = tab->array[i];
350       if (e->refcount)
351         {
352           *a++ = e;
353           /* Adjust the length to not include the zero terminator.  */
354           e->len -= 1;
355         }
356       else
357         e->len = 0;
358     }
359
360   size = a - array;
361   if (size != 0)
362     {
363       qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
364
365       /* Loop over the sorted array and merge suffixes.  Start from the
366          end because we want eg.
367
368          s1 -> "d"
369          s2 -> "bcd"
370          s3 -> "abcd"
371
372          to end up as
373
374          s3 -> "abcd"
375          s2 _____^
376          s1 _______^
377
378          ie. we don't want s1 pointing into the old s2.  */
379       e = *--a;
380       e->len += 1;
381       while (--a >= array)
382         {
383           struct elf_strtab_hash_entry *cmp = *a;
384
385           cmp->len += 1;
386           if (is_suffix (e, cmp))
387             {
388               cmp->u.suffix = e;
389               cmp->len = -cmp->len;
390             }
391           else
392             e = cmp;
393         }
394     }
395
396 alloc_failure:
397   if (array)
398     free (array);
399
400   /* Assign positions to the strings we want to keep.  */
401   size = 1;
402   for (i = 1; i < tab->size; ++i)
403     {
404       e = tab->array[i];
405       if (e->refcount && e->len > 0)
406         {
407           e->u.index = size;
408           size += e->len;
409         }
410     }
411
412   tab->sec_size = size;
413
414   /* Adjust the rest.  */
415   for (i = 1; i < tab->size; ++i)
416     {
417       e = tab->array[i];
418       if (e->refcount && e->len < 0)
419         e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
420     }
421 }