1 /* hash.c -- hash table routines for BFD
2 Copyright (C) 1993-2023 Free Software Foundation, Inc.
3 Written by Steve Chamberlain <sac@cygnus.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 3 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., 51 Franklin Street - Fifth Floor, Boston,
20 MA 02110-1301, USA. */
21
22 #include "sysdep.h"
23 #include "bfd.h"
24 #include "libbfd.h"
25 #include "objalloc.h"
26 #include "libiberty.h"
27
28 /*
29 SECTION
30 Hash Tables
31
32 @cindex Hash tables
33 BFD provides a simple set of hash table functions. Routines
34 are provided to initialize a hash table, to free a hash table,
35 to look up a string in a hash table and optionally create an
36 entry for it, and to traverse a hash table. There is
37 currently no routine to delete an string from a hash table.
38
39 The basic hash table does not permit any data to be stored
40 with a string. However, a hash table is designed to present a
41 base class from which other types of hash tables may be
42 derived. These derived types may store additional information
43 with the string. Hash tables were implemented in this way,
44 rather than simply providing a data pointer in a hash table
45 entry, because they were designed for use by the linker back
46 ends. The linker may create thousands of hash table entries,
47 and the overhead of allocating private data and storing and
48 following pointers becomes noticeable.
49
50 The basic hash table code is in <<hash.c>>.
51
52 @menu
53 @* Creating and Freeing a Hash Table::
54 @* Looking Up or Entering a String::
55 @* Traversing a Hash Table::
56 @* Deriving a New Hash Table Type::
57 @end menu
58
59 INODE
60 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
61 SUBSECTION
62 Creating and freeing a hash table
63
64 @findex bfd_hash_table_init
65 @findex bfd_hash_table_init_n
66 To create a hash table, create an instance of a <<struct
67 bfd_hash_table>> (defined in <<bfd.h>>) and call
68 <<bfd_hash_table_init>> (if you know approximately how many
69 entries you will need, the function <<bfd_hash_table_init_n>>,
70 which takes a @var{size} argument, may be used).
71 <<bfd_hash_table_init>> returns <<FALSE>> if some sort of
72 error occurs.
73
74 @findex bfd_hash_newfunc
75 The function <<bfd_hash_table_init>> take as an argument a
76 function to use to create new entries. For a basic hash
77 table, use the function <<bfd_hash_newfunc>>. @xref{Deriving
78 a New Hash Table Type}, for why you would want to use a
79 different value for this argument.
80
81 @findex bfd_hash_allocate
82 <<bfd_hash_table_init>> will create an objalloc which will be
83 used to allocate new entries. You may allocate memory on this
84 objalloc using <<bfd_hash_allocate>>.
85
86 @findex bfd_hash_table_free
87 Use <<bfd_hash_table_free>> to free up all the memory that has
88 been allocated for a hash table. This will not free up the
89 <<struct bfd_hash_table>> itself, which you must provide.
90
91 @findex bfd_hash_set_default_size
92 Use <<bfd_hash_set_default_size>> to set the default size of
93 hash table to use.
94
95 INODE
96 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
97 SUBSECTION
98 Looking up or entering a string
99
100 @findex bfd_hash_lookup
101 The function <<bfd_hash_lookup>> is used both to look up a
102 string in the hash table and to create a new entry.
103
104 If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>>
105 will look up a string. If the string is found, it will
106 returns a pointer to a <<struct bfd_hash_entry>>. If the
107 string is not found in the table <<bfd_hash_lookup>> will
108 return <<NULL>>. You should not modify any of the fields in
109 the returns <<struct bfd_hash_entry>>.
110
111 If the @var{create} argument is <<TRUE>>, the string will be
112 entered into the hash table if it is not already there.
113 Either way a pointer to a <<struct bfd_hash_entry>> will be
114 returned, either to the existing structure or to a newly
115 created one. In this case, a <<NULL>> return means that an
116 error occurred.
117
118 If the @var{create} argument is <<TRUE>>, and a new entry is
119 created, the @var{copy} argument is used to decide whether to
120 copy the string onto the hash table objalloc or not. If
121 @var{copy} is passed as <<FALSE>>, you must be careful not to
122 deallocate or modify the string as long as the hash table
123 exists.
124
125 INODE
126 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
127 SUBSECTION
128 Traversing a hash table
129
130 @findex bfd_hash_traverse
131 The function <<bfd_hash_traverse>> may be used to traverse a
132 hash table, calling a function on each element. The traversal
133 is done in a random order.
134
135 <<bfd_hash_traverse>> takes as arguments a function and a
136 generic <<void *>> pointer. The function is called with a
137 hash table entry (a <<struct bfd_hash_entry *>>) and the
138 generic pointer passed to <<bfd_hash_traverse>>. The function
139 must return a <<boolean>> value, which indicates whether to
140 continue traversing the hash table. If the function returns
141 <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and
142 return immediately.
143
144 INODE
145 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
146 SUBSECTION
147 Deriving a new hash table type
148
149 Many uses of hash tables want to store additional information
150 which each entry in the hash table. Some also find it
151 convenient to store additional information with the hash table
152 itself. This may be done using a derived hash table.
153
154 Since C is not an object oriented language, creating a derived
155 hash table requires sticking together some boilerplate
156 routines with a few differences specific to the type of hash
157 table you want to create.
158
159 An example of a derived hash table is the linker hash table.
160 The structures for this are defined in <<bfdlink.h>>. The
161 functions are in <<linker.c>>.
162
163 You may also derive a hash table from an already derived hash
164 table. For example, the a.out linker backend code uses a hash
165 table derived from the linker hash table.
166
167 @menu
168 @* Define the Derived Structures::
169 @* Write the Derived Creation Routine::
170 @* Write Other Derived Routines::
171 @end menu
172
173 INODE
174 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
175 SUBSUBSECTION
176 Define the derived structures
177
178 You must define a structure for an entry in the hash table,
179 and a structure for the hash table itself.
180
181 The first field in the structure for an entry in the hash
182 table must be of the type used for an entry in the hash table
183 you are deriving from. If you are deriving from a basic hash
184 table this is <<struct bfd_hash_entry>>, which is defined in
185 <<bfd.h>>. The first field in the structure for the hash
186 table itself must be of the type of the hash table you are
187 deriving from itself. If you are deriving from a basic hash
188 table, this is <<struct bfd_hash_table>>.
189
190 For example, the linker hash table defines <<struct
191 bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field,
192 <<root>>, is of type <<struct bfd_hash_entry>>. Similarly,
193 the first field in <<struct bfd_link_hash_table>>, <<table>>,
194 is of type <<struct bfd_hash_table>>.
195
196 INODE
197 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
198 SUBSUBSECTION
199 Write the derived creation routine
200
201 You must write a routine which will create and initialize an
202 entry in the hash table. This routine is passed as the
203 function argument to <<bfd_hash_table_init>>.
204
205 In order to permit other hash tables to be derived from the
206 hash table you are creating, this routine must be written in a
207 standard way.
208
209 The first argument to the creation routine is a pointer to a
210 hash table entry. This may be <<NULL>>, in which case the
211 routine should allocate the right amount of space. Otherwise
212 the space has already been allocated by a hash table type
213 derived from this one.
214
215 After allocating space, the creation routine must call the
216 creation routine of the hash table type it is derived from,
217 passing in a pointer to the space it just allocated. This
218 will initialize any fields used by the base hash table.
219
220 Finally the creation routine must initialize any local fields
221 for the new hash table type.
222
223 Here is a boilerplate example of a creation routine.
224 @var{function_name} is the name of the routine.
225 @var{entry_type} is the type of an entry in the hash table you
226 are creating. @var{base_newfunc} is the name of the creation
227 routine of the hash table type your hash table is derived
228 from.
229
230 EXAMPLE
231
232 .struct bfd_hash_entry *
233 .@var{function_name} (struct bfd_hash_entry *entry,
234 . struct bfd_hash_table *table,
235 . const char *string)
236 .{
237 . struct @var{entry_type} *ret = (@var{entry_type} *) entry;
238 .
239 . {* Allocate the structure if it has not already been allocated by a
240 . derived class. *}
241 . if (ret == NULL)
242 . {
243 . ret = bfd_hash_allocate (table, sizeof (* ret));
244 . if (ret == NULL)
245 . return NULL;
246 . }
247 .
248 . {* Call the allocation method of the base class. *}
249 . ret = ((@var{entry_type} *)
250 . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
251 .
252 . {* Initialize the local fields here. *}
253 .
254 . return (struct bfd_hash_entry *) ret;
255 .}
256
257 DESCRIPTION
258 The creation routine for the linker hash table, which is in
259 <<linker.c>>, looks just like this example.
260 @var{function_name} is <<_bfd_link_hash_newfunc>>.
261 @var{entry_type} is <<struct bfd_link_hash_entry>>.
262 @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
263 routine for a basic hash table.
264
265 <<_bfd_link_hash_newfunc>> also initializes the local fields
266 in a linker hash table entry: <<type>>, <<written>> and
267 <<next>>.
268
269 INODE
270 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
271 SUBSUBSECTION
272 Write other derived routines
273
274 You will want to write other routines for your new hash table,
275 as well.
276
277 You will want an initialization routine which calls the
278 initialization routine of the hash table you are deriving from
279 and initializes any other local fields. For the linker hash
280 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
281
282 You will want a lookup routine which calls the lookup routine
283 of the hash table you are deriving from and casts the result.
284 The linker hash table uses <<bfd_link_hash_lookup>> in
285 <<linker.c>> (this actually takes an additional argument which
286 it uses to decide how to return the looked up value).
287
288 You may want a traversal routine. This should just call the
289 traversal routine of the hash table you are deriving from with
290 appropriate casts. The linker hash table uses
291 <<bfd_link_hash_traverse>> in <<linker.c>>.
292
293 These routines may simply be defined as macros. For example,
294 the a.out backend linker hash table, which is derived from the
295 linker hash table, uses macros for the lookup and traversal
296 routines. These are <<aout_link_hash_lookup>> and
297 <<aout_link_hash_traverse>> in aoutx.h.
298
299 EXTERNAL
300 .{* An element in the hash table. Most uses will actually use a larger
301 . structure, and an instance of this will be the first field. *}
302 .
303 .struct bfd_hash_entry
304 .{
305 . {* Next entry for this hash code. *}
306 . struct bfd_hash_entry *next;
307 . {* String being hashed. *}
308 . const char *string;
309 . {* Hash code. This is the full hash code, not the index into the
310 . table. *}
311 . unsigned long hash;
312 .};
313 .
314 .{* A hash table. *}
315 .
316 .struct bfd_hash_table
317 .{
318 . {* The hash array. *}
319 . struct bfd_hash_entry **table;
320 . {* A function used to create new elements in the hash table. The
321 . first entry is itself a pointer to an element. When this
322 . function is first invoked, this pointer will be NULL. However,
323 . having the pointer permits a hierarchy of method functions to be
324 . built each of which calls the function in the superclass. Thus
325 . each function should be written to allocate a new block of memory
326 . only if the argument is NULL. *}
327 . struct bfd_hash_entry *(*newfunc)
328 . (struct bfd_hash_entry *, struct bfd_hash_table *, const char *);
329 . {* An objalloc for this hash table. This is a struct objalloc *,
330 . but we use void * to avoid requiring the inclusion of objalloc.h. *}
331 . void *memory;
332 . {* The number of slots in the hash table. *}
333 . unsigned int size;
334 . {* The number of entries in the hash table. *}
335 . unsigned int count;
336 . {* The size of elements. *}
337 . unsigned int entsize;
338 . {* If non-zero, don't grow the hash table. *}
339 . unsigned int frozen:1;
340 .};
341 .
342 */
343
344 /* The default number of entries to use when creating a hash table. */
345 #define DEFAULT_SIZE 4051
346
347 /* The following function returns a nearest prime number which is
348 greater than N, and near a power of two. Copied from libiberty.
349 Returns zero for ridiculously large N to signify an error. */
350
351 static uint32_t
352 higher_prime_number (uint32_t n)
353 {
354 /* These are primes that are near, but slightly smaller than, a
355 power of two. */
356 static const uint32_t primes[] =
357 {
358 UINT32_C (31),
359 UINT32_C (61),
360 UINT32_C (127),
361 UINT32_C (251),
362 UINT32_C (509),
363 UINT32_C (1021),
364 UINT32_C (2039),
365 UINT32_C (4093),
366 UINT32_C (8191),
367 UINT32_C (16381),
368 UINT32_C (32749),
369 UINT32_C (65521),
370 UINT32_C (131071),
371 UINT32_C (262139),
372 UINT32_C (524287),
373 UINT32_C (1048573),
374 UINT32_C (2097143),
375 UINT32_C (4194301),
376 UINT32_C (8388593),
377 UINT32_C (16777213),
378 UINT32_C (33554393),
379 UINT32_C (67108859),
380 UINT32_C (134217689),
381 UINT32_C (268435399),
382 UINT32_C (536870909),
383 UINT32_C (1073741789),
384 UINT32_C (2147483647),
385 UINT32_C (4294967291)
386 };
387
388 const uint32_t *low = &primes[0];
389 const uint32_t *high = &primes[sizeof (primes) / sizeof (primes[0])];
390
391 while (low != high)
392 {
393 const uint32_t *mid = low + (high - low) / 2;
394 if (n >= *mid)
395 low = mid + 1;
396 else
397 high = mid;
398 }
399
400 if (n >= *low)
401 return 0;
402
403 return *low;
404 }
405
406 static unsigned int bfd_default_hash_table_size = DEFAULT_SIZE;
407
408 /*
409 FUNCTION
410 bfd_hash_table_init_n
411
412 SYNOPSIS
413 bool bfd_hash_table_init_n
414 (struct bfd_hash_table *,
415 struct bfd_hash_entry *(* {*newfunc*})
416 (struct bfd_hash_entry *, struct bfd_hash_table *, const char *),
417 unsigned int {*entsize*}, unsigned int {*size*});
418
419 DESCRIPTION
420 Create a new hash table, given a number of entries.
421 */
422
423 bool
424 bfd_hash_table_init_n (struct bfd_hash_table *table,
425 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
426 struct bfd_hash_table *,
427 const char *),
428 unsigned int entsize,
429 unsigned int size)
430 {
431 unsigned long alloc;
432
433 alloc = size;
434 alloc *= sizeof (struct bfd_hash_entry *);
435 if (alloc / sizeof (struct bfd_hash_entry *) != size)
436 {
437 bfd_set_error (bfd_error_no_memory);
438 return false;
439 }
440
441 table->memory = (void *) objalloc_create ();
442 if (table->memory == NULL)
443 {
444 bfd_set_error (bfd_error_no_memory);
445 return false;
446 }
447 table->table = (struct bfd_hash_entry **)
448 objalloc_alloc ((struct objalloc *) table->memory, alloc);
449 if (table->table == NULL)
450 {
451 bfd_hash_table_free (table);
452 bfd_set_error (bfd_error_no_memory);
453 return false;
454 }
455 memset ((void *) table->table, 0, alloc);
456 table->size = size;
457 table->entsize = entsize;
458 table->count = 0;
459 table->frozen = 0;
460 table->newfunc = newfunc;
461 return true;
462 }
463
464 /*
465 FUNCTION
466 bfd_hash_table_init
467
468 SYNOPSIS
469 bool bfd_hash_table_init
470 (struct bfd_hash_table *,
471 struct bfd_hash_entry *(* {*newfunc*})
472 (struct bfd_hash_entry *, struct bfd_hash_table *, const char *),
473 unsigned int {*entsize*});
474
475 DESCRIPTION
476 Create a new hash table with the default number of entries.
477 */
478
479 bool
480 bfd_hash_table_init (struct bfd_hash_table *table,
481 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
482 struct bfd_hash_table *,
483 const char *),
484 unsigned int entsize)
485 {
486 return bfd_hash_table_init_n (table, newfunc, entsize,
487 bfd_default_hash_table_size);
488 }
489
490 /*
491 FUNCTION
492 bfd_hash_table_free
493
494 SYNOPSIS
495 void bfd_hash_table_free (struct bfd_hash_table *);
496
497 DESCRIPTION
498 Free a hash table.
499 */
500
501 void
502 bfd_hash_table_free (struct bfd_hash_table *table)
503 {
504 objalloc_free ((struct objalloc *) table->memory);
505 table->memory = NULL;
506 }
507
508 static inline unsigned long
509 bfd_hash_hash (const char *string, unsigned int *lenp)
510 {
511 const unsigned char *s;
512 unsigned long hash;
513 unsigned int len;
514 unsigned int c;
515
516 BFD_ASSERT (string != NULL);
517 hash = 0;
518 len = 0;
519 s = (const unsigned char *) string;
520 while ((c = *s++) != '\0')
521 {
522 hash += c + (c << 17);
523 hash ^= hash >> 2;
524 }
525 len = (s - (const unsigned char *) string) - 1;
526 hash += len + (len << 17);
527 hash ^= hash >> 2;
528 if (lenp != NULL)
529 *lenp = len;
530 return hash;
531 }
532
533 /*
534 FUNCTION
535 bfd_hash_lookup
536
537 SYNOPSIS
538 struct bfd_hash_entry *bfd_hash_lookup
539 (struct bfd_hash_table *, const char *,
540 bool {*create*}, bool {*copy*});
541
542 DESCRIPTION
543 Look up a string in a hash table.
544 */
545
546 struct bfd_hash_entry *
547 bfd_hash_lookup (struct bfd_hash_table *table,
548 const char *string,
549 bool create,
550 bool copy)
551 {
552 unsigned long hash;
553 struct bfd_hash_entry *hashp;
554 unsigned int len;
555 unsigned int _index;
556
557 hash = bfd_hash_hash (string, &len);
558 _index = hash % table->size;
559 for (hashp = table->table[_index];
560 hashp != NULL;
561 hashp = hashp->next)
562 {
563 if (hashp->hash == hash
564 && strcmp (hashp->string, string) == 0)
565 return hashp;
566 }
567
568 if (! create)
569 return NULL;
570
571 if (copy)
572 {
573 char *new_string;
574
575 new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
576 len + 1);
577 if (!new_string)
578 {
579 bfd_set_error (bfd_error_no_memory);
580 return NULL;
581 }
582 memcpy (new_string, string, len + 1);
583 string = new_string;
584 }
585
586 return bfd_hash_insert (table, string, hash);
587 }
588
589 /*
590 FUNCTION
591 bfd_hash_insert
592
593 SYNOPSIS
594 struct bfd_hash_entry *bfd_hash_insert
595 (struct bfd_hash_table *,
596 const char *,
597 unsigned long {*hash*});
598
599 DESCRIPTION
600 Insert an entry in a hash table.
601 */
602
603 struct bfd_hash_entry *
604 bfd_hash_insert (struct bfd_hash_table *table,
605 const char *string,
606 unsigned long hash)
607 {
608 struct bfd_hash_entry *hashp;
609 unsigned int _index;
610
611 hashp = (*table->newfunc) (NULL, table, string);
612 if (hashp == NULL)
613 return NULL;
614 hashp->string = string;
615 hashp->hash = hash;
616 _index = hash % table->size;
617 hashp->next = table->table[_index];
618 table->table[_index] = hashp;
619 table->count++;
620
621 if (!table->frozen && table->count > table->size * 3 / 4)
622 {
623 unsigned long newsize = higher_prime_number (table->size);
624 struct bfd_hash_entry **newtable;
625 unsigned int hi;
626 unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
627
628 /* If we can't find a higher prime, or we can't possibly alloc
629 that much memory, don't try to grow the table. */
630 if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
631 {
632 table->frozen = 1;
633 return hashp;
634 }
635
636 newtable = ((struct bfd_hash_entry **)
637 objalloc_alloc ((struct objalloc *) table->memory, alloc));
638 if (newtable == NULL)
639 {
640 table->frozen = 1;
641 return hashp;
642 }
643 memset (newtable, 0, alloc);
644
645 for (hi = 0; hi < table->size; hi ++)
646 while (table->table[hi])
647 {
648 struct bfd_hash_entry *chain = table->table[hi];
649 struct bfd_hash_entry *chain_end = chain;
650
651 while (chain_end->next && chain_end->next->hash == chain->hash)
652 chain_end = chain_end->next;
653
654 table->table[hi] = chain_end->next;
655 _index = chain->hash % newsize;
656 chain_end->next = newtable[_index];
657 newtable[_index] = chain;
658 }
659 table->table = newtable;
660 table->size = newsize;
661 }
662
663 return hashp;
664 }
665
666 /*
667 FUNCTION
668 bfd_hash_rename
669
670 SYNOPSIS
671 void bfd_hash_rename (struct bfd_hash_table *,
672 const char *,
673 struct bfd_hash_entry *);
674
675 DESCRIPTION
676 Rename an entry in a hash table.
677 */
678
679 void
680 bfd_hash_rename (struct bfd_hash_table *table,
681 const char *string,
682 struct bfd_hash_entry *ent)
683 {
684 unsigned int _index;
685 struct bfd_hash_entry **pph;
686
687 _index = ent->hash % table->size;
688 for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
689 if (*pph == ent)
690 break;
691 if (*pph == NULL)
692 abort ();
693
694 *pph = ent->next;
695 ent->string = string;
696 ent->hash = bfd_hash_hash (string, NULL);
697 _index = ent->hash % table->size;
698 ent->next = table->table[_index];
699 table->table[_index] = ent;
700 }
701
702 /*
703 FUNCTION
704 bfd_hash_replace
705
706 SYNOPSIS
707 void bfd_hash_replace (struct bfd_hash_table *,
708 struct bfd_hash_entry * {*old*},
709 struct bfd_hash_entry * {*new*});
710
711 DESCRIPTION
712 Replace an entry in a hash table.
713 */
714
715 void
716 bfd_hash_replace (struct bfd_hash_table *table,
717 struct bfd_hash_entry *old,
718 struct bfd_hash_entry *nw)
719 {
720 unsigned int _index;
721 struct bfd_hash_entry **pph;
722
723 _index = old->hash % table->size;
724 for (pph = &table->table[_index];
725 (*pph) != NULL;
726 pph = &(*pph)->next)
727 {
728 if (*pph == old)
729 {
730 *pph = nw;
731 return;
732 }
733 }
734
735 abort ();
736 }
737
738 /*
739 FUNCTION
740 bfd_hash_allocate
741
742 SYNOPSIS
743 void *bfd_hash_allocate (struct bfd_hash_table *,
744 unsigned int {*size*});
745
746 DESCRIPTION
747 Allocate space in a hash table.
748 */
749
750 void *
751 bfd_hash_allocate (struct bfd_hash_table *table,
752 unsigned int size)
753 {
754 void * ret;
755
756 ret = objalloc_alloc ((struct objalloc *) table->memory, size);
757 if (ret == NULL && size != 0)
758 bfd_set_error (bfd_error_no_memory);
759 return ret;
760 }
761
762 /*
763 FUNCTION
764 bfd_hash_newfunc
765
766 SYNOPSIS
767 struct bfd_hash_entry *bfd_hash_newfunc
768 (struct bfd_hash_entry *,
769 struct bfd_hash_table *,
770 const char *);
771
772 DESCRIPTION
773 Base method for creating a new hash table entry.
774 */
775
776 struct bfd_hash_entry *
777 bfd_hash_newfunc (struct bfd_hash_entry *entry,
778 struct bfd_hash_table *table,
779 const char *string ATTRIBUTE_UNUSED)
780 {
781 if (entry == NULL)
782 entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
783 sizeof (* entry));
784 return entry;
785 }
786
787 /*
788 FUNCTION
789 bfd_hash_traverse
790
791 SYNOPSIS
792 void bfd_hash_traverse
793 (struct bfd_hash_table *,
794 bool (*) (struct bfd_hash_entry *, void *),
795 void *);
796
797 DESCRIPTION
798 Traverse a hash table.
799 */
800
801 void
802 bfd_hash_traverse (struct bfd_hash_table *table,
803 bool (*func) (struct bfd_hash_entry *, void *),
804 void *info)
805 {
806 unsigned int i;
807
808 table->frozen = 1;
809 for (i = 0; i < table->size; i++)
810 {
811 struct bfd_hash_entry *p;
812
813 for (p = table->table[i]; p != NULL; p = p->next)
814 if (! (*func) (p, info))
815 goto out;
816 }
817 out:
818 table->frozen = 0;
819 }
820
821 /*
822 FUNCTION
823 bfd_hash_set_default_size
824
825 SYNOPSIS
826 unsigned int bfd_hash_set_default_size (unsigned int);
827
828 DESCRIPTION
829 Set hash table default size.
830 */
831
832 unsigned int
833 bfd_hash_set_default_size (unsigned int hash_size)
834 {
835 /* These silly_size values result in around 1G and 32M of memory
836 being allocated for the table of pointers. Note that the number
837 of elements allocated will be almost twice the size of any power
838 of two chosen here. */
839 unsigned int silly_size = sizeof (size_t) > 4 ? 0x4000000 : 0x400000;
840 if (hash_size > silly_size)
841 hash_size = silly_size;
842 else if (hash_size != 0)
843 hash_size--;
844 hash_size = higher_prime_number (hash_size);
845 BFD_ASSERT (hash_size != 0);
846 bfd_default_hash_table_size = hash_size;
847 return bfd_default_hash_table_size;
848 }
849
850 /* A few different object file formats (a.out, COFF, ELF) use a string
851 table. These functions support adding strings to a string table,
852 returning the byte offset, and writing out the table.
853
854 Possible improvements:
855 + look for strings matching trailing substrings of other strings
856 + better data structures? balanced trees?
857 + look at reducing memory use elsewhere -- maybe if we didn't have
858 to construct the entire symbol table at once, we could get by
859 with smaller amounts of VM? (What effect does that have on the
860 string table reductions?) */
861
862 /* An entry in the strtab hash table. */
863
864 struct strtab_hash_entry
865 {
866 struct bfd_hash_entry root;
867 /* Index in string table. */
868 bfd_size_type index;
869 /* Next string in strtab. */
870 struct strtab_hash_entry *next;
871 };
872
873 /* The strtab hash table. */
874
875 struct bfd_strtab_hash
876 {
877 struct bfd_hash_table table;
878 /* Size of strtab--also next available index. */
879 bfd_size_type size;
880 /* First string in strtab. */
881 struct strtab_hash_entry *first;
882 /* Last string in strtab. */
883 struct strtab_hash_entry *last;
884 /* Whether to precede strings with a two or four byte length,
885 as in the XCOFF .debug section. */
886 char length_field_size;
887 };
888
889
890 /* Routine to create an entry in a strtab. */
891
892 static struct bfd_hash_entry *
893 strtab_hash_newfunc (struct bfd_hash_entry *entry,
894 struct bfd_hash_table *table,
895 const char *string)
896 {
897 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
898
899 /* Allocate the structure if it has not already been allocated by a
900 subclass. */
901 if (ret == NULL)
902 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
903 sizeof (* ret));
904 if (ret == NULL)
905 return NULL;
906
907 /* Call the allocation method of the superclass. */
908 ret = (struct strtab_hash_entry *)
909 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
910
911 if (ret)
912 {
913 /* Initialize the local fields. */
914 ret->index = (bfd_size_type) -1;
915 ret->next = NULL;
916 }
917
918 return (struct bfd_hash_entry *) ret;
919 }
920
921 /* Look up an entry in an strtab. */
922
923 #define strtab_hash_lookup(t, string, create, copy) \
924 ((struct strtab_hash_entry *) \
925 bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
926
927 /*
928 INTERNAL_FUNCTION
929 _bfd_stringtab_init
930
931 SYNOPSIS
932 struct bfd_strtab_hash *_bfd_stringtab_init (void);
933
934 DESCRIPTION
935 Create a new strtab.
936 */
937
938 struct bfd_strtab_hash *
939 _bfd_stringtab_init (void)
940 {
941 struct bfd_strtab_hash *table;
942 size_t amt = sizeof (* table);
943
944 table = (struct bfd_strtab_hash *) bfd_malloc (amt);
945 if (table == NULL)
946 return NULL;
947
948 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
949 sizeof (struct strtab_hash_entry)))
950 {
951 free (table);
952 return NULL;
953 }
954
955 table->size = 0;
956 table->first = NULL;
957 table->last = NULL;
958 table->length_field_size = 0;
959
960 return table;
961 }
962
963 /*
964 INTERNAL_FUNCTION
965 _bfd_xcoff_stringtab_init
966
967 SYNOPSIS
968 struct bfd_strtab_hash *_bfd_xcoff_stringtab_init
969 (bool {*isxcoff64*});
970
971 DESCRIPTION
972 Create a new strtab in which the strings are output in the format
973 used in the XCOFF .debug section: a two byte length precedes each
974 string.
975 */
976
977 struct bfd_strtab_hash *
978 _bfd_xcoff_stringtab_init (bool isxcoff64)
979 {
980 struct bfd_strtab_hash *ret;
981
982 ret = _bfd_stringtab_init ();
983 if (ret != NULL)
984 ret->length_field_size = isxcoff64 ? 4 : 2;
985 return ret;
986 }
987
988 /*
989 INTERNAL_FUNCTION
990 _bfd_stringtab_free
991
992 SYNOPSIS
993 void _bfd_stringtab_free (struct bfd_strtab_hash *);
994
995 DESCRIPTION
996 Free a strtab.
997 */
998
999 void
1000 _bfd_stringtab_free (struct bfd_strtab_hash *table)
1001 {
1002 bfd_hash_table_free (&table->table);
1003 free (table);
1004 }
1005
1006 /*
1007 INTERNAL_FUNCTION
1008 _bfd_stringtab_add
1009
1010 SYNOPSIS
1011 bfd_size_type _bfd_stringtab_add
1012 (struct bfd_strtab_hash *, const char *,
1013 bool {*hash*}, bool {*copy*});
1014
1015 DESCRIPTION
1016 Get the index of a string in a strtab, adding it if it is not
1017 already present. If HASH is FALSE, we don't really use the hash
1018 table, and we don't eliminate duplicate strings. If COPY is true
1019 then store a copy of STR if creating a new entry.
1020 */
1021
1022 bfd_size_type
1023 _bfd_stringtab_add (struct bfd_strtab_hash *tab,
1024 const char *str,
1025 bool hash,
1026 bool copy)
1027 {
1028 struct strtab_hash_entry *entry;
1029
1030 if (hash)
1031 {
1032 entry = strtab_hash_lookup (tab, str, true, copy);
1033 if (entry == NULL)
1034 return (bfd_size_type) -1;
1035 }
1036 else
1037 {
1038 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
1039 sizeof (* entry));
1040 if (entry == NULL)
1041 return (bfd_size_type) -1;
1042 if (! copy)
1043 entry->root.string = str;
1044 else
1045 {
1046 size_t len = strlen (str) + 1;
1047 char *n;
1048
1049 n = (char *) bfd_hash_allocate (&tab->table, len);
1050 if (n == NULL)
1051 return (bfd_size_type) -1;
1052 memcpy (n, str, len);
1053 entry->root.string = n;
1054 }
1055 entry->index = (bfd_size_type) -1;
1056 entry->next = NULL;
1057 }
1058
1059 if (entry->index == (bfd_size_type) -1)
1060 {
1061 entry->index = tab->size;
1062 tab->size += strlen (str) + 1;
1063 entry->index += tab->length_field_size;
1064 tab->size += tab->length_field_size;
1065 if (tab->first == NULL)
1066 tab->first = entry;
1067 else
1068 tab->last->next = entry;
1069 tab->last = entry;
1070 }
1071
1072 return entry->index;
1073 }
1074
1075 /*
1076 INTERNAL_FUNCTION
1077 _bfd_stringtab_size
1078
1079 SYNOPSIS
1080 bfd_size_type _bfd_stringtab_size (struct bfd_strtab_hash *);
1081
1082 DESCRIPTION
1083 Get the number of bytes in a strtab.
1084 */
1085
1086 bfd_size_type
1087 _bfd_stringtab_size (struct bfd_strtab_hash *tab)
1088 {
1089 return tab->size;
1090 }
1091
1092 /*
1093 INTERNAL_FUNCTION
1094 _bfd_stringtab_emit
1095
1096 SYNOPSIS
1097 bool _bfd_stringtab_emit (bfd *, struct bfd_strtab_hash *);
1098
1099 DESCRIPTION
1100 Write out a strtab. ABFD must already be at the right location in
1101 the file.
1102 */
1103
1104 bool
1105 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
1106 {
1107 struct strtab_hash_entry *entry;
1108
1109 for (entry = tab->first; entry != NULL; entry = entry->next)
1110 {
1111 const char *str;
1112 size_t len;
1113
1114 str = entry->root.string;
1115 len = strlen (str) + 1;
1116
1117 if (tab->length_field_size == 4)
1118 {
1119 bfd_byte buf[4];
1120
1121 /* The output length includes the null byte. */
1122 bfd_put_32 (abfd, (bfd_vma) len, buf);
1123 if (bfd_bwrite ((void *) buf, (bfd_size_type) 4, abfd) != 4)
1124 return false;
1125 }
1126 else if (tab->length_field_size == 2)
1127 {
1128 bfd_byte buf[2];
1129
1130 /* The output length includes the null byte. */
1131 bfd_put_16 (abfd, (bfd_vma) len, buf);
1132 if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
1133 return false;
1134 }
1135
1136 if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
1137 return false;
1138 }
1139
1140 return true;
1141 }