Update the address and phone number of the FSF organization in the GPL notices
[external/binutils.git] / bfd / elf-strtab.c
1 /* ELF strtab with GC and suffix merging support.
2    Copyright 2001, 2002, 2003, 2005 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., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 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.  This includes the zero terminator.  */
34   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 < 0).  */
40     struct elf_strtab_hash_entry *suffix;
41   } u;
42 };
43
44 /* The strtab hash table.  */
45
46 struct elf_strtab_hash
47 {
48   struct bfd_hash_table table;
49   /* Next available index.  */
50   bfd_size_type size;
51   /* Number of array entries alloced.  */
52   bfd_size_type alloced;
53   /* Final strtab size.  */
54   bfd_size_type sec_size;
55   /* Array of pointers to strtab entries.  */
56   struct elf_strtab_hash_entry **array;
57 };
58
59 /* Routine to create an entry in a section merge hashtab.  */
60
61 static struct bfd_hash_entry *
62 elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
63                          struct bfd_hash_table *table,
64                          const char *string)
65 {
66   /* Allocate the structure if it has not already been allocated by a
67      subclass.  */
68   if (entry == NULL)
69     entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
70   if (entry == NULL)
71     return NULL;
72
73   /* Call the allocation method of the superclass.  */
74   entry = bfd_hash_newfunc (entry, table, string);
75
76   if (entry)
77     {
78       /* Initialize the local fields.  */
79       struct elf_strtab_hash_entry *ret;
80
81       ret = (struct elf_strtab_hash_entry *) entry;
82       ret->u.index = -1;
83       ret->refcount = 0;
84       ret->len = 0;
85     }
86
87   return entry;
88 }
89
90 /* Create a new hash table.  */
91
92 struct elf_strtab_hash *
93 _bfd_elf_strtab_init (void)
94 {
95   struct elf_strtab_hash *table;
96   bfd_size_type amt = sizeof (struct elf_strtab_hash);
97
98   table = bfd_malloc (amt);
99   if (table == NULL)
100     return NULL;
101
102   if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
103     {
104       free (table);
105       return NULL;
106     }
107
108   table->sec_size = 0;
109   table->size = 1;
110   table->alloced = 64;
111   amt = sizeof (struct elf_strtab_hasn_entry *);
112   table->array = bfd_malloc (table->alloced * amt);
113   if (table->array == NULL)
114     {
115       free (table);
116       return NULL;
117     }
118
119   table->array[0] = NULL;
120
121   return table;
122 }
123
124 /* Free a strtab.  */
125
126 void
127 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
128 {
129   bfd_hash_table_free (&tab->table);
130   free (tab->array);
131   free (tab);
132 }
133
134 /* Get the index of an entity in a hash table, adding it if it is not
135    already present.  */
136
137 bfd_size_type
138 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
139                      const char *str,
140                      bfd_boolean copy)
141 {
142   register struct elf_strtab_hash_entry *entry;
143
144   /* We handle this specially, since we don't want to do refcounting
145      on it.  */
146   if (*str == '\0')
147     return 0;
148
149   BFD_ASSERT (tab->sec_size == 0);
150   entry = (struct elf_strtab_hash_entry *)
151           bfd_hash_lookup (&tab->table, str, TRUE, copy);
152
153   if (entry == NULL)
154     return (bfd_size_type) -1;
155
156   entry->refcount++;
157   if (entry->len == 0)
158     {
159       entry->len = strlen (str) + 1;
160       /* 2G strings lose.  */
161       BFD_ASSERT (entry->len > 0);
162       if (tab->size == tab->alloced)
163         {
164           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
165           tab->alloced *= 2;
166           tab->array = bfd_realloc (tab->array, tab->alloced * amt);
167           if (tab->array == NULL)
168             return (bfd_size_type) -1;
169         }
170
171       entry->u.index = tab->size++;
172       tab->array[entry->u.index] = entry;
173     }
174   return entry->u.index;
175 }
176
177 void
178 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
179 {
180   if (idx == 0 || idx == (bfd_size_type) -1)
181     return;
182   BFD_ASSERT (tab->sec_size == 0);
183   BFD_ASSERT (idx < tab->size);
184   ++tab->array[idx]->refcount;
185 }
186
187 void
188 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
189 {
190   if (idx == 0 || idx == (bfd_size_type) -1)
191     return;
192   BFD_ASSERT (tab->sec_size == 0);
193   BFD_ASSERT (idx < tab->size);
194   BFD_ASSERT (tab->array[idx]->refcount > 0);
195   --tab->array[idx]->refcount;
196 }
197
198 void
199 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
200 {
201   bfd_size_type idx;
202
203   for (idx = 1; idx < tab->size; ++idx)
204     tab->array[idx]->refcount = 0;
205 }
206
207 bfd_size_type
208 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
209 {
210   return tab->sec_size ? tab->sec_size : tab->size;
211 }
212
213 bfd_size_type
214 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
215 {
216   struct elf_strtab_hash_entry *entry;
217
218   if (idx == 0)
219     return 0;
220   BFD_ASSERT (idx < tab->size);
221   BFD_ASSERT (tab->sec_size);
222   entry = tab->array[idx];
223   BFD_ASSERT (entry->refcount > 0);
224   entry->refcount--;
225   return tab->array[idx]->u.index;
226 }
227
228 bfd_boolean
229 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
230 {
231   bfd_size_type off = 1, i;
232
233   if (bfd_bwrite ("", 1, abfd) != 1)
234     return FALSE;
235
236   for (i = 1; i < tab->size; ++i)
237     {
238       register const char *str;
239       register unsigned int len;
240
241       BFD_ASSERT (tab->array[i]->refcount == 0);
242       len = tab->array[i]->len;
243       if ((int) len < 0)
244         continue;
245
246       str = tab->array[i]->root.string;
247       if (bfd_bwrite (str, len, abfd) != len)
248         return FALSE;
249
250       off += len;
251     }
252
253   BFD_ASSERT (off == tab->sec_size);
254   return TRUE;
255 }
256
257 /* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
258
259 static int
260 strrevcmp (const void *a, const void *b)
261 {
262   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
263   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
264   unsigned int lenA = A->len;
265   unsigned int lenB = B->len;
266   const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
267   const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
268   int l = lenA < lenB ? lenA : lenB;
269
270   while (l)
271     {
272       if (*s != *t)
273         return (int) *s - (int) *t;
274       s--;
275       t--;
276       l--;
277     }
278   return lenA - lenB;
279 }
280
281 static inline int
282 is_suffix (const struct elf_strtab_hash_entry *A,
283            const struct elf_strtab_hash_entry *B)
284 {
285   if (A->len <= B->len)
286     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
287        not to be equal by the hash table.  */
288     return 0;
289
290   return memcmp (A->root.string + (A->len - B->len),
291                  B->root.string, B->len - 1) == 0;
292 }
293
294 /* This function assigns final string table offsets for used strings,
295    merging strings matching suffixes of longer strings if possible.  */
296
297 void
298 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
299 {
300   struct elf_strtab_hash_entry **array, **a, *e;
301   bfd_size_type size, amt;
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   /* Sort the strings by suffix and length.  */
310   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
311   array = bfd_malloc (amt);
312   if (array == NULL)
313     goto alloc_failure;
314
315   for (i = 1, a = array; i < tab->size; ++i)
316     {
317       e = tab->array[i];
318       if (e->refcount)
319         {
320           *a++ = e;
321           /* Adjust the length to not include the zero terminator.  */
322           e->len -= 1;
323         }
324       else
325         e->len = 0;
326     }
327
328   size = a - array;
329   if (size != 0)
330     {
331       qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
332
333       /* Loop over the sorted array and merge suffixes.  Start from the
334          end because we want eg.
335
336          s1 -> "d"
337          s2 -> "bcd"
338          s3 -> "abcd"
339
340          to end up as
341
342          s3 -> "abcd"
343          s2 _____^
344          s1 _______^
345
346          ie. we don't want s1 pointing into the old s2.  */
347       e = *--a;
348       e->len += 1;
349       while (--a >= array)
350         {
351           struct elf_strtab_hash_entry *cmp = *a;
352
353           cmp->len += 1;
354           if (is_suffix (e, cmp))
355             {
356               cmp->u.suffix = e;
357               cmp->len = -cmp->len;
358             }
359           else
360             e = cmp;
361         }
362     }
363
364 alloc_failure:
365   if (array)
366     free (array);
367
368   /* Assign positions to the strings we want to keep.  */
369   size = 1;
370   for (i = 1; i < tab->size; ++i)
371     {
372       e = tab->array[i];
373       if (e->refcount && e->len > 0)
374         {
375           e->u.index = size;
376           size += e->len;
377         }
378     }
379
380   tab->sec_size = size;
381
382   /* Adjust the rest.  */
383   for (i = 1; i < tab->size; ++i)
384     {
385       e = tab->array[i];
386       if (e->refcount && e->len < 0)
387         e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
388     }
389 }