daily update
[binutils.git] / bfd / elf-strtab.c
blob7d2fad4e51762ecd052a3300db5ffd5e5656c112
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>.
6 This file is part of BFD, the Binary File Descriptor library.
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.
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.
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. */
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"
30 /* An entry in the strtab hash table. */
32 struct elf_strtab_hash_entry
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;
46 /* The strtab hash table. */
48 struct elf_strtab_hash
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;
61 /* Routine to create an entry in a section merge hashtab. */
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)
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;
76 /* Call the allocation method of the superclass. */
77 entry = bfd_hash_newfunc (entry, table, string);
79 if (entry)
81 /* Initialize the local fields. */
82 struct elf_strtab_hash_entry *ret;
84 ret = (struct elf_strtab_hash_entry *) entry;
85 ret->u.index = -1;
86 ret->refcount = 0;
87 ret->len = 0;
90 return entry;
93 /* Create a new hash table. */
95 struct elf_strtab_hash *
96 _bfd_elf_strtab_init (void)
98 struct elf_strtab_hash *table;
99 bfd_size_type amt = sizeof (struct elf_strtab_hash);
101 table = (struct elf_strtab_hash *) bfd_malloc (amt);
102 if (table == NULL)
103 return NULL;
105 if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
106 sizeof (struct elf_strtab_hash_entry)))
108 free (table);
109 return NULL;
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)
120 free (table);
121 return NULL;
124 table->array[0] = NULL;
126 return table;
129 /* Free a strtab. */
131 void
132 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
134 bfd_hash_table_free (&tab->table);
135 free (tab->array);
136 free (tab);
139 /* Get the index of an entity in a hash table, adding it if it is not
140 already present. */
142 bfd_size_type
143 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
144 const char *str,
145 bfd_boolean copy)
147 register struct elf_strtab_hash_entry *entry;
149 /* We handle this specially, since we don't want to do refcounting
150 on it. */
151 if (*str == '\0')
152 return 0;
154 BFD_ASSERT (tab->sec_size == 0);
155 entry = (struct elf_strtab_hash_entry *)
156 bfd_hash_lookup (&tab->table, str, TRUE, copy);
158 if (entry == NULL)
159 return (bfd_size_type) -1;
161 entry->refcount++;
162 if (entry->len == 0)
164 entry->len = strlen (str) + 1;
165 /* 2G strings lose. */
166 BFD_ASSERT (entry->len > 0);
167 if (tab->size == tab->alloced)
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;
177 entry->u.index = tab->size++;
178 tab->array[entry->u.index] = entry;
180 return entry->u.index;
183 void
184 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
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;
193 void
194 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
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;
204 void
205 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
207 bfd_size_type idx;
209 for (idx = 1; idx < tab->size; ++idx)
210 tab->array[idx]->refcount = 0;
213 bfd_size_type
214 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
216 return tab->sec_size ? tab->sec_size : tab->size;
219 bfd_size_type
220 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
222 struct elf_strtab_hash_entry *entry;
224 if (idx == 0)
225 return 0;
226 BFD_ASSERT (idx < tab->size);
227 BFD_ASSERT (tab->sec_size);
228 entry = tab->array[idx];
229 BFD_ASSERT (entry->refcount > 0);
230 entry->refcount--;
231 return tab->array[idx]->u.index;
234 bfd_boolean
235 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
237 bfd_size_type off = 1, i;
239 if (bfd_bwrite ("", 1, abfd) != 1)
240 return FALSE;
242 for (i = 1; i < tab->size; ++i)
244 register const char *str;
245 register unsigned int len;
247 BFD_ASSERT (tab->array[i]->refcount == 0);
248 len = tab->array[i]->len;
249 if ((int) len < 0)
250 continue;
252 str = tab->array[i]->root.string;
253 if (bfd_bwrite (str, len, abfd) != len)
254 return FALSE;
256 off += len;
259 BFD_ASSERT (off == tab->sec_size);
260 return TRUE;
263 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */
265 static int
266 strrevcmp (const void *a, const void *b)
268 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
269 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
270 unsigned int lenA = A->len;
271 unsigned int lenB = B->len;
272 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
273 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
274 int l = lenA < lenB ? lenA : lenB;
276 while (l)
278 if (*s != *t)
279 return (int) *s - (int) *t;
280 s--;
281 t--;
282 l--;
284 return lenA - lenB;
287 static inline int
288 is_suffix (const struct elf_strtab_hash_entry *A,
289 const struct elf_strtab_hash_entry *B)
291 if (A->len <= B->len)
292 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
293 not to be equal by the hash table. */
294 return 0;
296 return memcmp (A->root.string + (A->len - B->len),
297 B->root.string, B->len - 1) == 0;
300 /* This function assigns final string table offsets for used strings,
301 merging strings matching suffixes of longer strings if possible. */
303 void
304 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
306 struct elf_strtab_hash_entry **array, **a, *e;
307 bfd_size_type size, amt;
309 /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
310 a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
311 Besides, indexing with a long long wouldn't give anything but extra
312 cycles. */
313 size_t i;
315 /* Sort the strings by suffix and length. */
316 amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
317 array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
318 if (array == NULL)
319 goto alloc_failure;
321 for (i = 1, a = array; i < tab->size; ++i)
323 e = tab->array[i];
324 if (e->refcount)
326 *a++ = e;
327 /* Adjust the length to not include the zero terminator. */
328 e->len -= 1;
330 else
331 e->len = 0;
334 size = a - array;
335 if (size != 0)
337 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
339 /* Loop over the sorted array and merge suffixes. Start from the
340 end because we want eg.
342 s1 -> "d"
343 s2 -> "bcd"
344 s3 -> "abcd"
346 to end up as
348 s3 -> "abcd"
349 s2 _____^
350 s1 _______^
352 ie. we don't want s1 pointing into the old s2. */
353 e = *--a;
354 e->len += 1;
355 while (--a >= array)
357 struct elf_strtab_hash_entry *cmp = *a;
359 cmp->len += 1;
360 if (is_suffix (e, cmp))
362 cmp->u.suffix = e;
363 cmp->len = -cmp->len;
365 else
366 e = cmp;
370 alloc_failure:
371 if (array)
372 free (array);
374 /* Assign positions to the strings we want to keep. */
375 size = 1;
376 for (i = 1; i < tab->size; ++i)
378 e = tab->array[i];
379 if (e->refcount && e->len > 0)
381 e->u.index = size;
382 size += e->len;
386 tab->sec_size = size;
388 /* Adjust the rest. */
389 for (i = 1; i < tab->size; ++i)
391 e = tab->array[i];
392 if (e->refcount && e->len < 0)
393 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);