1 /* ELF strtab with GC and suffix merging support.
2 Copyright 2001 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. */
27 /* An entry in the strtab hash table. */
29 struct elf_strtab_hash_entry
31 struct bfd_hash_entry root
;
32 /* Length of this entry. */
34 unsigned int refcount
;
36 /* Index within the merged section. */
38 /* Entry this is a suffix of (if len is 0). */
39 struct elf_strtab_hash_entry
*suffix
;
40 struct elf_strtab_hash_entry
*next
;
44 /* The strtab hash table. */
46 struct elf_strtab_hash
48 struct bfd_hash_table table
;
49 /* Next available index. */
51 /* Number of array entries alloced. */
52 bfd_size_type alloced
;
53 /* Final strtab size. */
54 bfd_size_type sec_size
;
55 /* Array of pointers to strtab entries. */
56 struct elf_strtab_hash_entry
**array
;
59 static struct bfd_hash_entry
*elf_strtab_hash_newfunc
60 PARAMS ((struct bfd_hash_entry
*, struct bfd_hash_table
*, const char *));
61 static int cmplengthentry
PARAMS ((const PTR
, const PTR
));
62 static int last4_eq
PARAMS ((const PTR
, const PTR
));
64 /* Routine to create an entry in a section merge hashtab. */
66 static struct bfd_hash_entry
*
67 elf_strtab_hash_newfunc (entry
, table
, string
)
68 struct bfd_hash_entry
*entry
;
69 struct bfd_hash_table
*table
;
72 struct elf_strtab_hash_entry
*ret
= (struct elf_strtab_hash_entry
*) entry
;
74 /* Allocate the structure if it has not already been allocated by a
76 if (ret
== (struct elf_strtab_hash_entry
*) NULL
)
77 ret
= ((struct elf_strtab_hash_entry
*)
78 bfd_hash_allocate (table
, sizeof (struct elf_strtab_hash_entry
)));
79 if (ret
== (struct elf_strtab_hash_entry
*) NULL
)
82 /* Call the allocation method of the superclass. */
83 ret
= ((struct elf_strtab_hash_entry
*)
84 bfd_hash_newfunc ((struct bfd_hash_entry
*) ret
, table
, string
));
88 /* Initialize the local fields. */
94 return (struct bfd_hash_entry
*)ret
;
97 /* Create a new hash table. */
99 struct elf_strtab_hash
*
100 _bfd_elf_strtab_init ()
102 struct elf_strtab_hash
*table
;
103 bfd_size_type amt
= sizeof (struct elf_strtab_hash
);
105 table
= (struct elf_strtab_hash
*) bfd_malloc (amt
);
109 if (! bfd_hash_table_init (&table
->table
, elf_strtab_hash_newfunc
))
118 amt
= sizeof (struct elf_strtab_hasn_entry
*);
119 table
->array
= (struct elf_strtab_hash_entry
**)
120 bfd_malloc (table
->alloced
* amt
);
121 if (table
->array
== NULL
)
127 table
->array
[0] = NULL
;
135 _bfd_elf_strtab_free (tab
)
136 struct elf_strtab_hash
*tab
;
138 bfd_hash_table_free (&tab
->table
);
143 /* Get the index of an entity in a hash table, adding it if it is not
147 _bfd_elf_strtab_add (tab
, str
, copy
)
148 struct elf_strtab_hash
*tab
;
152 register struct elf_strtab_hash_entry
*entry
;
154 /* We handle this specially, since we don't want to do refcounting
159 BFD_ASSERT (tab
->sec_size
== 0);
160 entry
= (struct elf_strtab_hash_entry
*)
161 bfd_hash_lookup (&tab
->table
, str
, true, copy
);
164 return (bfd_size_type
) -1;
169 entry
->len
= strlen (str
) + 1;
170 if (tab
->size
== tab
->alloced
)
172 bfd_size_type amt
= sizeof (struct elf_strtab_hash_entry
*);
174 tab
->array
= (struct elf_strtab_hash_entry
**)
175 bfd_realloc (tab
->array
, tab
->alloced
* amt
);
176 if (tab
->array
== NULL
)
177 return (bfd_size_type
) -1;
180 entry
->u
.index
= tab
->size
++;
181 tab
->array
[entry
->u
.index
] = entry
;
183 return entry
->u
.index
;
187 _bfd_elf_strtab_addref (tab
, idx
)
188 struct elf_strtab_hash
*tab
;
191 if (idx
== 0 || idx
== (bfd_size_type
) -1)
193 BFD_ASSERT (tab
->sec_size
== 0);
194 BFD_ASSERT (idx
< tab
->size
);
195 ++tab
->array
[idx
]->refcount
;
199 _bfd_elf_strtab_delref (tab
, idx
)
200 struct elf_strtab_hash
*tab
;
203 if (idx
== 0 || idx
== (bfd_size_type
) -1)
205 BFD_ASSERT (tab
->sec_size
== 0);
206 BFD_ASSERT (idx
< tab
->size
);
207 BFD_ASSERT (tab
->array
[idx
]->refcount
> 0);
208 --tab
->array
[idx
]->refcount
;
212 _bfd_elf_strtab_clear_all_refs (tab
)
213 struct elf_strtab_hash
*tab
;
217 for (idx
= 1; idx
< tab
->size
; ++idx
)
218 tab
->array
[idx
]->refcount
= 0;
222 _bfd_elf_strtab_size (tab
)
223 struct elf_strtab_hash
*tab
;
225 return tab
->sec_size
? tab
->sec_size
: tab
->size
;
229 _bfd_elf_strtab_offset (tab
, idx
)
230 struct elf_strtab_hash
*tab
;
233 struct elf_strtab_hash_entry
*entry
;
237 BFD_ASSERT (idx
< tab
->size
);
238 BFD_ASSERT (tab
->sec_size
);
239 entry
= tab
->array
[idx
];
240 BFD_ASSERT (entry
->refcount
> 0);
242 return tab
->array
[idx
]->u
.index
;
246 _bfd_elf_strtab_emit (abfd
, tab
)
248 struct elf_strtab_hash
*tab
;
250 bfd_size_type off
= 1, i
;
252 if (bfd_bwrite ("", 1, abfd
) != 1)
255 for (i
= 1; i
< tab
->size
; ++i
)
257 register const char *str
;
260 str
= tab
->array
[i
]->root
.string
;
261 len
= tab
->array
[i
]->len
;
262 BFD_ASSERT (tab
->array
[i
]->refcount
== 0);
266 if (bfd_bwrite ((PTR
) str
, (bfd_size_type
) len
, abfd
) != len
)
272 BFD_ASSERT (off
== tab
->sec_size
);
276 /* Compare two elf_strtab_hash_entry structures. This is called via qsort. */
279 cmplengthentry (a
, b
)
283 struct elf_strtab_hash_entry
* A
= *(struct elf_strtab_hash_entry
**) a
;
284 struct elf_strtab_hash_entry
* B
= *(struct elf_strtab_hash_entry
**) b
;
288 else if (A
->len
> B
->len
)
291 return memcmp (A
->root
.string
, B
->root
.string
, A
->len
);
299 struct elf_strtab_hash_entry
* A
= (struct elf_strtab_hash_entry
*) a
;
300 struct elf_strtab_hash_entry
* B
= (struct elf_strtab_hash_entry
*) b
;
302 if (memcmp (A
->root
.string
+ A
->len
- 5, B
->root
.string
+ B
->len
- 5, 4)
304 /* This was a hashtable collision. */
307 if (A
->len
<= B
->len
)
308 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
309 not to be equal by the hash table. */
312 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
313 B
->root
.string
, B
->len
- 5) == 0;
316 /* This function assigns final string table offsets for used strings,
317 merging strings matching suffixes of longer strings if possible. */
320 _bfd_elf_strtab_finalize (tab
)
321 struct elf_strtab_hash
*tab
;
323 struct elf_strtab_hash_entry
**array
, **a
, **end
, *e
;
324 htab_t last4tab
= NULL
;
325 bfd_size_type size
, amt
;
326 struct elf_strtab_hash_entry
*last
[256], **last_ptr
[256];
328 /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
329 a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
330 Besides, indexing with a long long wouldn't give anything but extra
334 /* Now sort the strings by length, longest first. */
336 amt
= tab
->size
* sizeof (struct elf_strtab_hash_entry
*);
337 array
= (struct elf_strtab_hash_entry
**) bfd_malloc (amt
);
341 memset (last
, 0, sizeof (last
));
342 for (i
= 0; i
< 256; ++i
)
343 last_ptr
[i
] = &last
[i
];
344 for (i
= 1, a
= array
; i
< tab
->size
; ++i
)
345 if (tab
->array
[i
]->refcount
)
346 *a
++ = tab
->array
[i
];
348 tab
->array
[i
]->len
= 0;
352 qsort (array
, size
, sizeof (struct elf_strtab_hash_entry
*), cmplengthentry
);
354 last4tab
= htab_create (size
* 4, NULL
, last4_eq
, NULL
);
355 if (last4tab
== NULL
)
358 /* Now insert the strings into hash tables (strings with last 4 characters
359 and strings with last character equal), look for longer strings which
361 for (a
= array
, end
= array
+ size
; a
< end
; a
++)
363 register hashval_t hash
;
366 const unsigned char *s
;
372 s
= e
->root
.string
+ e
->len
- 1;
374 for (j
= 0; j
< 4; j
++)
377 hash
+= c
+ (c
<< 17);
380 p
= htab_find_slot_with_hash (last4tab
, e
, hash
, INSERT
);
385 struct elf_strtab_hash_entry
*ent
;
387 ent
= (struct elf_strtab_hash_entry
*) *p
;
397 struct elf_strtab_hash_entry
*tem
;
399 c
= e
->root
.string
[e
->len
- 2] & 0xff;
401 for (tem
= last
[c
]; tem
; tem
= tem
->u
.next
)
402 if (tem
->len
> e
->len
403 && memcmp (tem
->root
.string
+ (tem
->len
- e
->len
),
404 e
->root
.string
, e
->len
- 1) == 0)
414 c
= e
->root
.string
[e
->len
- 2] & 0xff;
415 /* Put longest strings first. */
417 last_ptr
[c
] = &e
->u
.next
;
425 htab_delete (last4tab
);
427 /* Now assign positions to the strings we want to keep. */
429 for (i
= 1; i
< tab
->size
; ++i
)
432 if (e
->refcount
&& e
->len
)
439 tab
->sec_size
= size
;
441 /* And now adjust the rest. */
442 for (i
= 1; i
< tab
->size
; ++i
)
445 if (e
->refcount
&& ! e
->len
)
446 e
->u
.index
= e
->u
.suffix
->u
.index
447 + (e
->u
.suffix
->len
- strlen (e
->root
.string
) - 1);
This page took 0.037757 seconds and 4 git commands to generate.