bfd/
[binutils.git] / bfd / elf-strtab.c
bloba0ce1d79ea8e7f3e99ad679af4e9688f7eaf71c6
1 /* ELF strtab with GC and suffix merging support.
2 Copyright 2001, 2002, 2003, 2005, 2006 Free Software Foundation, Inc.
3 Written by Jakub Jelinek <jakub@redhat.com>.
5 This file is part of BFD, the Binary File Descriptor library.
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.
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.
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. */
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"
28 /* An entry in the strtab hash table. */
30 struct elf_strtab_hash_entry
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;
44 /* The strtab hash table. */
46 struct elf_strtab_hash
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;
59 /* Routine to create an entry in a section merge hashtab. */
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)
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;
73 /* Call the allocation method of the superclass. */
74 entry = bfd_hash_newfunc (entry, table, string);
76 if (entry)
78 /* Initialize the local fields. */
79 struct elf_strtab_hash_entry *ret;
81 ret = (struct elf_strtab_hash_entry *) entry;
82 ret->u.index = -1;
83 ret->refcount = 0;
84 ret->len = 0;
87 return entry;
90 /* Create a new hash table. */
92 struct elf_strtab_hash *
93 _bfd_elf_strtab_init (void)
95 struct elf_strtab_hash *table;
96 bfd_size_type amt = sizeof (struct elf_strtab_hash);
98 table = bfd_malloc (amt);
99 if (table == NULL)
100 return NULL;
102 if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
103 sizeof (struct elf_strtab_hash_entry)))
105 free (table);
106 return NULL;
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)
116 free (table);
117 return NULL;
120 table->array[0] = NULL;
122 return table;
125 /* Free a strtab. */
127 void
128 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
130 bfd_hash_table_free (&tab->table);
131 free (tab->array);
132 free (tab);
135 /* Get the index of an entity in a hash table, adding it if it is not
136 already present. */
138 bfd_size_type
139 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
140 const char *str,
141 bfd_boolean copy)
143 register struct elf_strtab_hash_entry *entry;
145 /* We handle this specially, since we don't want to do refcounting
146 on it. */
147 if (*str == '\0')
148 return 0;
150 BFD_ASSERT (tab->sec_size == 0);
151 entry = (struct elf_strtab_hash_entry *)
152 bfd_hash_lookup (&tab->table, str, TRUE, copy);
154 if (entry == NULL)
155 return (bfd_size_type) -1;
157 entry->refcount++;
158 if (entry->len == 0)
160 entry->len = strlen (str) + 1;
161 /* 2G strings lose. */
162 BFD_ASSERT (entry->len > 0);
163 if (tab->size == tab->alloced)
165 bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
166 tab->alloced *= 2;
167 tab->array = bfd_realloc (tab->array, tab->alloced * amt);
168 if (tab->array == NULL)
169 return (bfd_size_type) -1;
172 entry->u.index = tab->size++;
173 tab->array[entry->u.index] = entry;
175 return entry->u.index;
178 void
179 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
181 if (idx == 0 || idx == (bfd_size_type) -1)
182 return;
183 BFD_ASSERT (tab->sec_size == 0);
184 BFD_ASSERT (idx < tab->size);
185 ++tab->array[idx]->refcount;
188 void
189 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
191 if (idx == 0 || idx == (bfd_size_type) -1)
192 return;
193 BFD_ASSERT (tab->sec_size == 0);
194 BFD_ASSERT (idx < tab->size);
195 BFD_ASSERT (tab->array[idx]->refcount > 0);
196 --tab->array[idx]->refcount;
199 void
200 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
202 bfd_size_type idx;
204 for (idx = 1; idx < tab->size; ++idx)
205 tab->array[idx]->refcount = 0;
208 bfd_size_type
209 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
211 return tab->sec_size ? tab->sec_size : tab->size;
214 bfd_size_type
215 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
217 struct elf_strtab_hash_entry *entry;
219 if (idx == 0)
220 return 0;
221 BFD_ASSERT (idx < tab->size);
222 BFD_ASSERT (tab->sec_size);
223 entry = tab->array[idx];
224 BFD_ASSERT (entry->refcount > 0);
225 entry->refcount--;
226 return tab->array[idx]->u.index;
229 bfd_boolean
230 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
232 bfd_size_type off = 1, i;
234 if (bfd_bwrite ("", 1, abfd) != 1)
235 return FALSE;
237 for (i = 1; i < tab->size; ++i)
239 register const char *str;
240 register unsigned int len;
242 BFD_ASSERT (tab->array[i]->refcount == 0);
243 len = tab->array[i]->len;
244 if ((int) len < 0)
245 continue;
247 str = tab->array[i]->root.string;
248 if (bfd_bwrite (str, len, abfd) != len)
249 return FALSE;
251 off += len;
254 BFD_ASSERT (off == tab->sec_size);
255 return TRUE;
258 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */
260 static int
261 strrevcmp (const void *a, const void *b)
263 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
264 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
265 unsigned int lenA = A->len;
266 unsigned int lenB = B->len;
267 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
268 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
269 int l = lenA < lenB ? lenA : lenB;
271 while (l)
273 if (*s != *t)
274 return (int) *s - (int) *t;
275 s--;
276 t--;
277 l--;
279 return lenA - lenB;
282 static inline int
283 is_suffix (const struct elf_strtab_hash_entry *A,
284 const struct elf_strtab_hash_entry *B)
286 if (A->len <= B->len)
287 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
288 not to be equal by the hash table. */
289 return 0;
291 return memcmp (A->root.string + (A->len - B->len),
292 B->root.string, B->len - 1) == 0;
295 /* This function assigns final string table offsets for used strings,
296 merging strings matching suffixes of longer strings if possible. */
298 void
299 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
301 struct elf_strtab_hash_entry **array, **a, *e;
302 bfd_size_type size, amt;
304 /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
305 a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
306 Besides, indexing with a long long wouldn't give anything but extra
307 cycles. */
308 size_t i;
310 /* Sort the strings by suffix and length. */
311 amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
312 array = bfd_malloc (amt);
313 if (array == NULL)
314 goto alloc_failure;
316 for (i = 1, a = array; i < tab->size; ++i)
318 e = tab->array[i];
319 if (e->refcount)
321 *a++ = e;
322 /* Adjust the length to not include the zero terminator. */
323 e->len -= 1;
325 else
326 e->len = 0;
329 size = a - array;
330 if (size != 0)
332 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
334 /* Loop over the sorted array and merge suffixes. Start from the
335 end because we want eg.
337 s1 -> "d"
338 s2 -> "bcd"
339 s3 -> "abcd"
341 to end up as
343 s3 -> "abcd"
344 s2 _____^
345 s1 _______^
347 ie. we don't want s1 pointing into the old s2. */
348 e = *--a;
349 e->len += 1;
350 while (--a >= array)
352 struct elf_strtab_hash_entry *cmp = *a;
354 cmp->len += 1;
355 if (is_suffix (e, cmp))
357 cmp->u.suffix = e;
358 cmp->len = -cmp->len;
360 else
361 e = cmp;
365 alloc_failure:
366 if (array)
367 free (array);
369 /* Assign positions to the strings we want to keep. */
370 size = 1;
371 for (i = 1; i < tab->size; ++i)
373 e = tab->array[i];
374 if (e->refcount && e->len > 0)
376 e->u.index = size;
377 size += e->len;
381 tab->sec_size = size;
383 /* Adjust the rest. */
384 for (i = 1; i < tab->size; ++i)
386 e = tab->array[i];
387 if (e->refcount && e->len < 0)
388 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);