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);
This page took 0.038568 seconds and 4 git commands to generate.