1 /* ELF strtab with GC and suffix merging support.
2 Copyright 2001, 2002 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
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. */
35 unsigned int refcount;
37 /* Index within the merged section. */
39 /* Entry this is a suffix of (if len is 0). */
40 struct elf_strtab_hash_entry *suffix;
41 struct elf_strtab_hash_entry *next;
45 /* The strtab hash table. */
47 struct elf_strtab_hash
49 struct bfd_hash_table table;
50 /* Next available index. */
52 /* Number of array entries alloced. */
53 bfd_size_type alloced;
54 /* Final strtab size. */
55 bfd_size_type sec_size;
56 /* Array of pointers to strtab entries. */
57 struct elf_strtab_hash_entry **array;
60 /* Routine to create an entry in a section merge hashtab. */
62 static struct bfd_hash_entry *
63 elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
64 struct bfd_hash_table *table,
67 /* Allocate the structure if it has not already been allocated by a
70 entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
74 /* Call the allocation method of the superclass. */
75 entry = bfd_hash_newfunc (entry, table, string);
79 /* Initialize the local fields. */
80 struct elf_strtab_hash_entry *ret;
82 ret = (struct elf_strtab_hash_entry *) entry;
91 /* Create a new hash table. */
93 struct elf_strtab_hash *
94 _bfd_elf_strtab_init (void)
96 struct elf_strtab_hash *table;
97 bfd_size_type amt = sizeof (struct elf_strtab_hash);
99 table = bfd_malloc (amt);
103 if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
112 amt = sizeof (struct elf_strtab_hasn_entry *);
113 table->array = bfd_malloc (table->alloced * amt);
114 if (table->array == NULL)
120 table->array[0] = NULL;
128 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
130 bfd_hash_table_free (&tab->table);
135 /* Get the index of an entity in a hash table, adding it if it is not
139 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
143 register struct elf_strtab_hash_entry *entry;
145 /* We handle this specially, since we don't want to do refcounting
150 BFD_ASSERT (tab->sec_size == 0);
151 entry = (struct elf_strtab_hash_entry *)
152 bfd_hash_lookup (&tab->table, str, TRUE, copy);
155 return (bfd_size_type) -1;
160 entry->len = strlen (str) + 1;
161 if (tab->size == tab->alloced)
163 bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
165 tab->array = bfd_realloc (tab->array, tab->alloced * amt);
166 if (tab->array == NULL)
167 return (bfd_size_type) -1;
170 entry->u.index = tab->size++;
171 tab->array[entry->u.index] = entry;
173 return entry->u.index;
177 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
179 if (idx == 0 || idx == (bfd_size_type) -1)
181 BFD_ASSERT (tab->sec_size == 0);
182 BFD_ASSERT (idx < tab->size);
183 ++tab->array[idx]->refcount;
187 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
189 if (idx == 0 || idx == (bfd_size_type) -1)
191 BFD_ASSERT (tab->sec_size == 0);
192 BFD_ASSERT (idx < tab->size);
193 BFD_ASSERT (tab->array[idx]->refcount > 0);
194 --tab->array[idx]->refcount;
198 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
202 for (idx = 1; idx < tab->size; ++idx)
203 tab->array[idx]->refcount = 0;
207 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
209 return tab->sec_size ? tab->sec_size : tab->size;
213 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
215 struct elf_strtab_hash_entry *entry;
219 BFD_ASSERT (idx < tab->size);
220 BFD_ASSERT (tab->sec_size);
221 entry = tab->array[idx];
222 BFD_ASSERT (entry->refcount > 0);
224 return tab->array[idx]->u.index;
228 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
230 bfd_size_type off = 1, i;
232 if (bfd_bwrite ("", 1, abfd) != 1)
235 for (i = 1; i < tab->size; ++i)
237 register const char *str;
240 str = tab->array[i]->root.string;
241 len = tab->array[i]->len;
242 BFD_ASSERT (tab->array[i]->refcount == 0);
246 if (bfd_bwrite (str, len, abfd) != len)
252 BFD_ASSERT (off == tab->sec_size);
256 /* Compare two elf_strtab_hash_entry structures. This is called via qsort. */
259 cmplengthentry (const void *a, const void *b)
261 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
262 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
266 else if (A->len > B->len)
269 return memcmp (A->root.string, B->root.string, A->len);
273 last4_eq (const void *a, const void *b)
275 const struct elf_strtab_hash_entry *A = a;
276 const struct elf_strtab_hash_entry *B = b;
278 if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
280 /* This was a hashtable collision. */
283 if (A->len <= B->len)
284 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
285 not to be equal by the hash table. */
288 return memcmp (A->root.string + (A->len - B->len),
289 B->root.string, B->len - 5) == 0;
292 /* This function assigns final string table offsets for used strings,
293 merging strings matching suffixes of longer strings if possible. */
296 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
298 struct elf_strtab_hash_entry **array, **a, **end, *e;
299 htab_t last4tab = NULL;
300 bfd_size_type size, amt;
301 struct elf_strtab_hash_entry *last[256], **last_ptr[256];
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
309 /* Now sort the strings by length, longest first. */
311 amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
312 array = bfd_malloc (amt);
316 memset (last, 0, sizeof (last));
317 for (i = 0; i < 256; ++i)
318 last_ptr[i] = &last[i];
319 for (i = 1, a = array; i < tab->size; ++i)
320 if (tab->array[i]->refcount)
321 *a++ = tab->array[i];
323 tab->array[i]->len = 0;
327 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
329 last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
330 if (last4tab == NULL)
333 /* Now insert the strings into hash tables (strings with last 4 characters
334 and strings with last character equal), look for longer strings which
336 for (a = array, end = array + size; a < end; a++)
338 register hashval_t hash;
341 const unsigned char *s;
347 s = e->root.string + e->len - 1;
349 for (j = 0; j < 4; j++)
352 hash += c + (c << 17);
355 p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
360 struct elf_strtab_hash_entry *ent;
372 struct elf_strtab_hash_entry *tem;
374 c = e->root.string[e->len - 2] & 0xff;
376 for (tem = last[c]; tem; tem = tem->u.next)
377 if (tem->len > e->len
378 && memcmp (tem->root.string + (tem->len - e->len),
379 e->root.string, e->len - 1) == 0)
389 c = e->root.string[e->len - 2] & 0xff;
390 /* Put longest strings first. */
392 last_ptr[c] = &e->u.next;
400 htab_delete (last4tab);
402 /* Now assign positions to the strings we want to keep. */
404 for (i = 1; i < tab->size; ++i)
407 if (e->refcount && e->len)
414 tab->sec_size = size;
416 /* And now adjust the rest. */
417 for (i = 1; i < tab->size; ++i)
420 if (e->refcount && ! e->len)
421 e->u.index = e->u.suffix->u.index
422 + (e->u.suffix->len - strlen (e->root.string) - 1);