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. */
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. */
37 unsigned int refcount
;
39 /* Index within the merged section. */
41 /* Entry this is a suffix of (if len < 0). */
42 struct elf_strtab_hash_entry
*suffix
;
46 /* The strtab hash table. */
48 struct elf_strtab_hash
50 struct bfd_hash_table table
;
51 /* Next available index. */
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
,
68 /* Allocate the structure if it has not already been allocated by a
71 entry
= (struct bfd_hash_entry
*)
72 bfd_hash_allocate (table
, sizeof (struct elf_strtab_hash_entry
));
76 /* Call the allocation method of the superclass. */
77 entry
= bfd_hash_newfunc (entry
, table
, string
);
81 /* Initialize the local fields. */
82 struct elf_strtab_hash_entry
*ret
;
84 ret
= (struct elf_strtab_hash_entry
*) 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
);
105 if (!bfd_hash_table_init (&table
->table
, elf_strtab_hash_newfunc
,
106 sizeof (struct elf_strtab_hash_entry
)))
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
)
124 table
->array
[0] = NULL
;
132 _bfd_elf_strtab_free (struct elf_strtab_hash
*tab
)
134 bfd_hash_table_free (&tab
->table
);
139 /* Get the index of an entity in a hash table, adding it if it is not
143 _bfd_elf_strtab_add (struct elf_strtab_hash
*tab
,
147 register struct elf_strtab_hash_entry
*entry
;
149 /* We handle this specially, since we don't want to do refcounting
154 BFD_ASSERT (tab
->sec_size
== 0);
155 entry
= (struct elf_strtab_hash_entry
*)
156 bfd_hash_lookup (&tab
->table
, str
, TRUE
, copy
);
159 return (bfd_size_type
) -1;
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
*);
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
;
184 _bfd_elf_strtab_addref (struct elf_strtab_hash
*tab
, bfd_size_type idx
)
186 if (idx
== 0 || idx
== (bfd_size_type
) -1)
188 BFD_ASSERT (tab
->sec_size
== 0);
189 BFD_ASSERT (idx
< tab
->size
);
190 ++tab
->array
[idx
]->refcount
;
194 _bfd_elf_strtab_delref (struct elf_strtab_hash
*tab
, bfd_size_type idx
)
196 if (idx
== 0 || idx
== (bfd_size_type
) -1)
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
;
205 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash
*tab
)
209 for (idx
= 1; idx
< tab
->size
; ++idx
)
210 tab
->array
[idx
]->refcount
= 0;
214 _bfd_elf_strtab_size (struct elf_strtab_hash
*tab
)
216 return tab
->sec_size
? tab
->sec_size
: tab
->size
;
220 _bfd_elf_strtab_offset (struct elf_strtab_hash
*tab
, bfd_size_type idx
)
222 struct elf_strtab_hash_entry
*entry
;
226 BFD_ASSERT (idx
< tab
->size
);
227 BFD_ASSERT (tab
->sec_size
);
228 entry
= tab
->array
[idx
];
229 BFD_ASSERT (entry
->refcount
> 0);
231 return tab
->array
[idx
]->u
.index
;
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)
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
;
252 str
= tab
->array
[i
]->root
.string
;
253 if (bfd_bwrite (str
, len
, abfd
) != len
)
259 BFD_ASSERT (off
== tab
->sec_size
);
263 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */
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
;
279 return (int) *s
- (int) *t
;
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. */
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. */
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
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
);
321 for (i
= 1, a
= array
; i
< tab
->size
; ++i
)
327 /* Adjust the length to not include the zero terminator. */
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.
352 ie. we don't want s1 pointing into the old s2. */
357 struct elf_strtab_hash_entry
*cmp
= *a
;
360 if (is_suffix (e
, cmp
))
363 cmp
->len
= -cmp
->len
;
374 /* Assign positions to the strings we want to keep. */
376 for (i
= 1; i
< tab
->size
; ++i
)
379 if (e
->refcount
&& e
->len
> 0)
386 tab
->sec_size
= size
;
388 /* Adjust the rest. */
389 for (i
= 1; i
< tab
->size
; ++i
)
392 if (e
->refcount
&& e
->len
< 0)
393 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
+ e
->len
);
This page took 0.036533 seconds and 4 git commands to generate.