This commit was generated by cvs2svn to track changes on a CVS vendor
[external/binutils.git] / bfd / elf-strtab.c
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>.
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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.  */
34   unsigned 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 is 0).  */
40     struct elf_strtab_hash_entry *suffix;
41     struct elf_strtab_hash_entry *next;
42   } u;
43 };
44
45 /* The strtab hash table.  */
46
47 struct elf_strtab_hash
48 {
49   struct bfd_hash_table table;
50   /* Next available index.  */
51   bfd_size_type size;
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;
58 };
59
60 static struct bfd_hash_entry *elf_strtab_hash_newfunc
61   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
62 static int cmplengthentry PARAMS ((const PTR, const PTR));
63 static int last4_eq PARAMS ((const PTR, const PTR));
64
65 /* Routine to create an entry in a section merge hashtab.  */
66
67 static struct bfd_hash_entry *
68 elf_strtab_hash_newfunc (entry, table, string)
69      struct bfd_hash_entry *entry;
70      struct bfd_hash_table *table;
71      const char *string;
72 {
73   struct elf_strtab_hash_entry *ret = (struct elf_strtab_hash_entry *) entry;
74
75   /* Allocate the structure if it has not already been allocated by a
76      subclass.  */
77   if (ret == (struct elf_strtab_hash_entry *) NULL)
78     ret = ((struct elf_strtab_hash_entry *)
79            bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)));
80   if (ret == (struct elf_strtab_hash_entry *) NULL)
81     return NULL;
82
83   /* Call the allocation method of the superclass.  */
84   ret = ((struct elf_strtab_hash_entry *)
85          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
86
87   if (ret)
88     {
89       /* Initialize the local fields.  */
90       ret->u.index = -1;
91       ret->refcount = 0;
92       ret->len = 0;
93     }
94
95   return (struct bfd_hash_entry *)ret;
96 }
97
98 /* Create a new hash table.  */
99
100 struct elf_strtab_hash *
101 _bfd_elf_strtab_init ()
102 {
103   struct elf_strtab_hash *table;
104   bfd_size_type amt = sizeof (struct elf_strtab_hash);
105
106   table = (struct elf_strtab_hash *) bfd_malloc (amt);
107   if (table == NULL)
108     return NULL;
109
110   if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
111     {
112       free (table);
113       return NULL;
114     }
115
116   table->sec_size = 0;
117   table->size = 1;
118   table->alloced = 64;
119   amt = sizeof (struct elf_strtab_hasn_entry *);
120   table->array = (struct elf_strtab_hash_entry **)
121                  bfd_malloc (table->alloced * amt);
122   if (table->array == NULL)
123     {
124       free (table);
125       return NULL;
126     }
127
128   table->array[0] = NULL;
129
130   return table;
131 }
132
133 /* Free a strtab.  */
134
135 void
136 _bfd_elf_strtab_free (tab)
137      struct elf_strtab_hash *tab;
138 {
139   bfd_hash_table_free (&tab->table);
140   free (tab->array);
141   free (tab);
142 }
143
144 /* Get the index of an entity in a hash table, adding it if it is not
145    already present.  */
146
147 bfd_size_type
148 _bfd_elf_strtab_add (tab, str, copy)
149      struct elf_strtab_hash *tab;
150      const char *str;
151      boolean copy;
152 {
153   register struct elf_strtab_hash_entry *entry;
154
155   /* We handle this specially, since we don't want to do refcounting
156      on it.  */
157   if (*str == '\0')
158     return 0;
159
160   BFD_ASSERT (tab->sec_size == 0);
161   entry = (struct elf_strtab_hash_entry *)
162           bfd_hash_lookup (&tab->table, str, true, copy);
163
164   if (entry == NULL)
165     return (bfd_size_type) -1;
166
167   entry->refcount++;
168   if (entry->len == 0)
169     {
170       entry->len = strlen (str) + 1;
171       if (tab->size == tab->alloced)
172         {
173           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
174           tab->alloced *= 2;
175           tab->array = (struct elf_strtab_hash_entry **)
176                        bfd_realloc (tab->array, tab->alloced * amt);
177           if (tab->array == NULL)
178             return (bfd_size_type) -1;
179         }
180
181       entry->u.index = tab->size++;
182       tab->array[entry->u.index] = entry;
183     }
184   return entry->u.index;
185 }
186
187 void
188 _bfd_elf_strtab_addref (tab, idx)
189      struct elf_strtab_hash *tab;
190      bfd_size_type idx;
191 {
192   if (idx == 0 || idx == (bfd_size_type) -1)
193     return;
194   BFD_ASSERT (tab->sec_size == 0);
195   BFD_ASSERT (idx < tab->size);
196   ++tab->array[idx]->refcount;
197 }
198
199 void
200 _bfd_elf_strtab_delref (tab, idx)
201      struct elf_strtab_hash *tab;
202      bfd_size_type idx;
203 {
204   if (idx == 0 || idx == (bfd_size_type) -1)
205     return;
206   BFD_ASSERT (tab->sec_size == 0);
207   BFD_ASSERT (idx < tab->size);
208   BFD_ASSERT (tab->array[idx]->refcount > 0);
209   --tab->array[idx]->refcount;
210 }
211
212 void
213 _bfd_elf_strtab_clear_all_refs (tab)
214      struct elf_strtab_hash *tab;
215 {
216   bfd_size_type idx;
217
218   for (idx = 1; idx < tab->size; ++idx)
219     tab->array[idx]->refcount = 0;
220 }
221
222 bfd_size_type
223 _bfd_elf_strtab_size (tab)
224      struct elf_strtab_hash *tab;
225 {
226   return tab->sec_size ? tab->sec_size : tab->size;
227 }
228
229 bfd_size_type
230 _bfd_elf_strtab_offset (tab, idx)
231      struct elf_strtab_hash *tab;
232      bfd_size_type idx;
233 {
234   struct elf_strtab_hash_entry *entry;
235
236   if (idx == 0)
237     return 0;
238   BFD_ASSERT (idx < tab->size);
239   BFD_ASSERT (tab->sec_size);
240   entry = tab->array[idx];
241   BFD_ASSERT (entry->refcount > 0);
242   entry->refcount--;
243   return tab->array[idx]->u.index;
244 }
245
246 boolean
247 _bfd_elf_strtab_emit (abfd, tab)
248      register bfd *abfd;
249      struct elf_strtab_hash *tab;
250 {
251   bfd_size_type off = 1, i;
252
253   if (bfd_bwrite ("", 1, abfd) != 1)
254     return false;
255
256   for (i = 1; i < tab->size; ++i)
257     {
258       register const char *str;
259       register size_t len;
260
261       str = tab->array[i]->root.string;
262       len = tab->array[i]->len;
263       BFD_ASSERT (tab->array[i]->refcount == 0);
264       if (len == 0)
265         continue;
266
267       if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
268         return false;
269
270       off += len;
271     }
272
273   BFD_ASSERT (off == tab->sec_size);
274   return true;
275 }
276
277 /* Compare two elf_strtab_hash_entry structures.  This is called via qsort.  */
278
279 static int
280 cmplengthentry (a, b)
281      const PTR a;
282      const PTR b;
283 {
284   struct elf_strtab_hash_entry * A = *(struct elf_strtab_hash_entry **) a;
285   struct elf_strtab_hash_entry * B = *(struct elf_strtab_hash_entry **) b;
286
287   if (A->len < B->len)
288     return 1;
289   else if (A->len > B->len)
290     return -1;
291
292   return memcmp (A->root.string, B->root.string, A->len);
293 }
294
295 static int
296 last4_eq (a, b)
297      const PTR a;
298      const PTR b;
299 {
300   struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
301   struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
302
303   if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
304       != 0)
305     /* This was a hashtable collision.  */
306     return 0;
307
308   if (A->len <= B->len)
309     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
310        not to be equal by the hash table.  */
311     return 0;
312
313   return memcmp (A->root.string + (A->len - B->len),
314                  B->root.string, B->len - 5) == 0;
315 }
316
317 /* This function assigns final string table offsets for used strings,
318    merging strings matching suffixes of longer strings if possible.  */
319
320 void
321 _bfd_elf_strtab_finalize (tab)
322      struct elf_strtab_hash *tab;
323 {
324   struct elf_strtab_hash_entry **array, **a, **end, *e;
325   htab_t last4tab = NULL;
326   bfd_size_type size, amt;
327   struct elf_strtab_hash_entry *last[256], **last_ptr[256];
328
329   /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
330      a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
331      Besides, indexing with a long long wouldn't give anything but extra
332      cycles.  */
333   size_t i;
334
335   /* Now sort the strings by length, longest first.  */
336   array = NULL;
337   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
338   array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
339   if (array == NULL)
340     goto alloc_failure;
341
342   memset (last, 0, sizeof (last));
343   for (i = 0; i < 256; ++i)
344     last_ptr[i] = &last[i];
345   for (i = 1, a = array; i < tab->size; ++i)
346     if (tab->array[i]->refcount)
347       *a++ = tab->array[i];
348     else
349       tab->array[i]->len = 0;
350
351   size = a - array;
352
353   qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
354
355   last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
356   if (last4tab == NULL)
357     goto alloc_failure;
358
359   /* Now insert the strings into hash tables (strings with last 4 characters
360      and strings with last character equal), look for longer strings which
361      we're suffix of.  */
362   for (a = array, end = array + size; a < end; a++)
363     {
364       register hashval_t hash;
365       unsigned int c;
366       unsigned int j;
367       const unsigned char *s;
368       PTR *p;
369
370       e = *a;
371       if (e->len > 4)
372         {
373           s = e->root.string + e->len - 1;
374           hash = 0;
375           for (j = 0; j < 4; j++)
376             {
377               c = *--s;
378               hash += c + (c << 17);
379               hash ^= hash >> 2;
380             }
381           p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
382           if (p == NULL)
383             goto alloc_failure;
384           if (*p)
385             {
386               struct elf_strtab_hash_entry *ent;
387
388               ent = (struct elf_strtab_hash_entry *) *p;
389               e->u.suffix = ent;
390               e->len = 0;
391               continue;
392             }
393           else
394             *p = (PTR) e;
395         }
396       else
397         {
398           struct elf_strtab_hash_entry *tem;
399
400           c = e->root.string[e->len - 2] & 0xff;
401
402           for (tem = last[c]; tem; tem = tem->u.next)
403             if (tem->len > e->len
404                 && memcmp (tem->root.string + (tem->len - e->len),
405                            e->root.string, e->len - 1) == 0)
406               break;
407           if (tem)
408             {
409               e->u.suffix = tem;
410               e->len = 0;
411               continue;
412             }
413         }
414
415       c = e->root.string[e->len - 2] & 0xff;
416       /* Put longest strings first.  */
417       *last_ptr[c] = e;
418       last_ptr[c] = &e->u.next;
419       e->u.next = NULL;
420     }
421
422 alloc_failure:
423   if (array)
424     free (array);
425   if (last4tab)
426     htab_delete (last4tab);
427
428   /* Now assign positions to the strings we want to keep.  */
429   size = 1;
430   for (i = 1; i < tab->size; ++i)
431     {
432       e = tab->array[i];
433       if (e->refcount && e->len)
434         {
435           e->u.index = size;
436           size += e->len;
437         }
438     }
439
440   tab->sec_size = size;
441
442   /* And now adjust the rest.  */
443   for (i = 1; i < tab->size; ++i)
444     {
445       e = tab->array[i];
446       if (e->refcount && ! e->len)
447         e->u.index = e->u.suffix->u.index
448                      + (e->u.suffix->len - strlen (e->root.string) - 1);
449     }
450 }