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 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
));
65 /* Routine to create an entry in a section merge hashtab. */
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
;
73 struct elf_strtab_hash_entry
*ret
= (struct elf_strtab_hash_entry
*) entry
;
75 /* Allocate the structure if it has not already been allocated by a
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
)
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
));
89 /* Initialize the local fields. */
95 return (struct bfd_hash_entry
*)ret
;
98 /* Create a new hash table. */
100 struct elf_strtab_hash
*
101 _bfd_elf_strtab_init ()
103 struct elf_strtab_hash
*table
;
104 bfd_size_type amt
= sizeof (struct elf_strtab_hash
);
106 table
= (struct elf_strtab_hash
*) bfd_malloc (amt
);
110 if (! bfd_hash_table_init (&table
->table
, elf_strtab_hash_newfunc
))
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
)
128 table
->array
[0] = NULL
;
136 _bfd_elf_strtab_free (tab
)
137 struct elf_strtab_hash
*tab
;
139 bfd_hash_table_free (&tab
->table
);
144 /* Get the index of an entity in a hash table, adding it if it is not
148 _bfd_elf_strtab_add (tab
, str
, copy
)
149 struct elf_strtab_hash
*tab
;
153 register struct elf_strtab_hash_entry
*entry
;
155 /* We handle this specially, since we don't want to do refcounting
160 BFD_ASSERT (tab
->sec_size
== 0);
161 entry
= (struct elf_strtab_hash_entry
*)
162 bfd_hash_lookup (&tab
->table
, str
, TRUE
, copy
);
165 return (bfd_size_type
) -1;
170 entry
->len
= strlen (str
) + 1;
171 if (tab
->size
== tab
->alloced
)
173 bfd_size_type amt
= sizeof (struct elf_strtab_hash_entry
*);
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;
181 entry
->u
.index
= tab
->size
++;
182 tab
->array
[entry
->u
.index
] = entry
;
184 return entry
->u
.index
;
188 _bfd_elf_strtab_addref (tab
, idx
)
189 struct elf_strtab_hash
*tab
;
192 if (idx
== 0 || idx
== (bfd_size_type
) -1)
194 BFD_ASSERT (tab
->sec_size
== 0);
195 BFD_ASSERT (idx
< tab
->size
);
196 ++tab
->array
[idx
]->refcount
;
200 _bfd_elf_strtab_delref (tab
, idx
)
201 struct elf_strtab_hash
*tab
;
204 if (idx
== 0 || idx
== (bfd_size_type
) -1)
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
;
213 _bfd_elf_strtab_clear_all_refs (tab
)
214 struct elf_strtab_hash
*tab
;
218 for (idx
= 1; idx
< tab
->size
; ++idx
)
219 tab
->array
[idx
]->refcount
= 0;
223 _bfd_elf_strtab_size (tab
)
224 struct elf_strtab_hash
*tab
;
226 return tab
->sec_size
? tab
->sec_size
: tab
->size
;
230 _bfd_elf_strtab_offset (tab
, idx
)
231 struct elf_strtab_hash
*tab
;
234 struct elf_strtab_hash_entry
*entry
;
238 BFD_ASSERT (idx
< tab
->size
);
239 BFD_ASSERT (tab
->sec_size
);
240 entry
= tab
->array
[idx
];
241 BFD_ASSERT (entry
->refcount
> 0);
243 return tab
->array
[idx
]->u
.index
;
247 _bfd_elf_strtab_emit (abfd
, tab
)
249 struct elf_strtab_hash
*tab
;
251 bfd_size_type off
= 1, i
;
253 if (bfd_bwrite ("", 1, abfd
) != 1)
256 for (i
= 1; i
< tab
->size
; ++i
)
258 register const char *str
;
261 str
= tab
->array
[i
]->root
.string
;
262 len
= tab
->array
[i
]->len
;
263 BFD_ASSERT (tab
->array
[i
]->refcount
== 0);
267 if (bfd_bwrite ((PTR
) str
, (bfd_size_type
) len
, abfd
) != len
)
273 BFD_ASSERT (off
== tab
->sec_size
);
277 /* Compare two elf_strtab_hash_entry structures. This is called via qsort. */
280 cmplengthentry (a
, b
)
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
;
289 else if (A
->len
> B
->len
)
292 return memcmp (A
->root
.string
, B
->root
.string
, A
->len
);
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
;
303 if (memcmp (A
->root
.string
+ A
->len
- 5, B
->root
.string
+ B
->len
- 5, 4)
305 /* This was a hashtable collision. */
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. */
313 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
314 B
->root
.string
, B
->len
- 5) == 0;
317 /* This function assigns final string table offsets for used strings,
318 merging strings matching suffixes of longer strings if possible. */
321 _bfd_elf_strtab_finalize (tab
)
322 struct elf_strtab_hash
*tab
;
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];
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
335 /* Now sort the strings by length, longest first. */
337 amt
= tab
->size
* sizeof (struct elf_strtab_hash_entry
*);
338 array
= (struct elf_strtab_hash_entry
**) bfd_malloc (amt
);
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
];
349 tab
->array
[i
]->len
= 0;
353 qsort (array
, size
, sizeof (struct elf_strtab_hash_entry
*), cmplengthentry
);
355 last4tab
= htab_create_alloc (size
* 4, NULL
, last4_eq
, NULL
, calloc
, free
);
356 if (last4tab
== NULL
)
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
362 for (a
= array
, end
= array
+ size
; a
< end
; a
++)
364 register hashval_t hash
;
367 const unsigned char *s
;
373 s
= e
->root
.string
+ e
->len
- 1;
375 for (j
= 0; j
< 4; j
++)
378 hash
+= c
+ (c
<< 17);
381 p
= htab_find_slot_with_hash (last4tab
, e
, hash
, INSERT
);
386 struct elf_strtab_hash_entry
*ent
;
388 ent
= (struct elf_strtab_hash_entry
*) *p
;
398 struct elf_strtab_hash_entry
*tem
;
400 c
= e
->root
.string
[e
->len
- 2] & 0xff;
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)
415 c
= e
->root
.string
[e
->len
- 2] & 0xff;
416 /* Put longest strings first. */
418 last_ptr
[c
] = &e
->u
.next
;
426 htab_delete (last4tab
);
428 /* Now assign positions to the strings we want to keep. */
430 for (i
= 1; i
< tab
->size
; ++i
)
433 if (e
->refcount
&& e
->len
)
440 tab
->sec_size
= size
;
442 /* And now adjust the rest. */
443 for (i
= 1; i
< tab
->size
; ++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);
This page took 0.038136 seconds and 4 git commands to generate.