1 /* hash.c -- hash table routines for BFD
2 Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
3 2006 Free Software Foundation, Inc.
4 Written by Steve Chamberlain <sac@cygnus.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 2 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, MA 02110-1301, USA. */
26 #include "libiberty.h"
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.
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.
50 The basic hash table code is in <<hash.c>>.
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::
60 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
62 Creating and freeing a hash table
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
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.
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>>.
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.
91 @findex bfd_hash_set_default_size
92 Use <<bfd_hash_set_default_size>> to set the default size of
96 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
98 Looking up or entering a string
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.
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>>.
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
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
126 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
128 Traversing a hash table
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.
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
145 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
147 Deriving a new hash table type
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.
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.
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>>.
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.
168 @* Define the Derived Structures::
169 @* Write the Derived Creation Routine::
170 @* Write Other Derived Routines::
174 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
176 Define the derived structures
178 You must define a structure for an entry in the hash table,
179 and a structure for the hash table itself.
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>>.
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>>.
197 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
199 Write the derived creation routine
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>>.
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
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.
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.
220 Finally the creation routine must initialize any local fields
221 for the new hash table type.
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
232 .struct bfd_hash_entry *
233 .@var{function_name} (struct bfd_hash_entry *entry,
234 . struct bfd_hash_table *table,
235 . const char *string)
237 . struct @var{entry_type} *ret = (@var{entry_type} *) entry;
239 . {* Allocate the structure if it has not already been allocated by a
243 . ret = bfd_hash_allocate (table, sizeof (* ret));
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));
252 . {* Initialize the local fields here. *}
254 . return (struct bfd_hash_entry *) ret;
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.
265 <<_bfd_link_hash_newfunc>> also initializes the local fields
266 in a linker hash table entry: <<type>>, <<written>> and
270 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
272 Write other derived routines
274 You will want to write other routines for your new hash table,
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>>.
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).
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>>.
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.
300 /* The default number of entries to use when creating a hash table. */
301 #define DEFAULT_SIZE 4051
303 /* The following function returns a nearest prime number which is
304 greater than N, and near a power of two. Copied from libiberty.
305 Returns zero for ridiculously large N to signify an error. */
308 higher_prime_number (unsigned long n)
310 /* These are primes that are near, but slightly smaller than, a
312 static const unsigned long primes[] = {
314 (unsigned long) 2039,
315 (unsigned long) 32749,
316 (unsigned long) 65521,
317 (unsigned long) 131071,
318 (unsigned long) 262139,
319 (unsigned long) 524287,
320 (unsigned long) 1048573,
321 (unsigned long) 2097143,
322 (unsigned long) 4194301,
323 (unsigned long) 8388593,
324 (unsigned long) 16777213,
325 (unsigned long) 33554393,
326 (unsigned long) 67108859,
327 (unsigned long) 134217689,
328 (unsigned long) 268435399,
329 (unsigned long) 536870909,
330 (unsigned long) 1073741789,
331 (unsigned long) 2147483647,
333 ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
336 const unsigned long *low = &primes[0];
337 const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
341 const unsigned long *mid = low + (high - low) / 2;
354 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
356 /* Create a new hash table, given a number of entries. */
359 bfd_hash_table_init_n (struct bfd_hash_table *table,
360 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
361 struct bfd_hash_table *,
363 unsigned int entsize,
368 alloc = size * sizeof (struct bfd_hash_entry *);
370 table->memory = (void *) objalloc_create ();
371 if (table->memory == NULL)
373 bfd_set_error (bfd_error_no_memory);
376 table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
377 if (table->table == NULL)
379 bfd_set_error (bfd_error_no_memory);
382 memset ((void *) table->table, 0, alloc);
384 table->entsize = entsize;
386 table->newfunc = newfunc;
390 /* Create a new hash table with the default number of entries. */
393 bfd_hash_table_init (struct bfd_hash_table *table,
394 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
395 struct bfd_hash_table *,
397 unsigned int entsize)
399 return bfd_hash_table_init_n (table, newfunc, entsize,
400 bfd_default_hash_table_size);
403 /* Free a hash table. */
406 bfd_hash_table_free (struct bfd_hash_table *table)
408 objalloc_free (table->memory);
409 table->memory = NULL;
412 /* Look up a string in a hash table. */
414 struct bfd_hash_entry *
415 bfd_hash_lookup (struct bfd_hash_table *table,
420 const unsigned char *s;
423 struct bfd_hash_entry *hashp;
429 s = (const unsigned char *) string;
430 while ((c = *s++) != '\0')
432 hash += c + (c << 17);
435 len = (s - (const unsigned char *) string) - 1;
436 hash += len + (len << 17);
439 index = hash % table->size;
440 for (hashp = table->table[index];
444 if (hashp->hash == hash
445 && strcmp (hashp->string, string) == 0)
452 hashp = (*table->newfunc) (NULL, table, string);
459 new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
462 bfd_set_error (bfd_error_no_memory);
465 memcpy (new, string, len + 1);
468 hashp->string = string;
470 hashp->next = table->table[index];
471 table->table[index] = hashp;
474 if (table->count > table->size * 3 / 4)
476 unsigned long newsize = higher_prime_number (table->size);
477 struct bfd_hash_entry **newtable;
479 unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
481 /* If we can't find a higher prime, or we can't possibly alloc
482 that much memory, don't try to grow the table. */
483 if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
485 /* Lie. Stops us trying to grow again for a while. */
490 newtable = ((struct bfd_hash_entry **)
491 objalloc_alloc ((struct objalloc *) table->memory, alloc));
492 memset ((PTR) newtable, 0, alloc);
494 for (hi = 0; hi < table->size; hi ++)
495 while (table->table[hi])
497 struct bfd_hash_entry *chain = table->table[hi];
498 struct bfd_hash_entry *chain_end = chain;
501 while (chain_end->next && chain_end->next->hash == chain->hash)
502 chain_end = chain_end->next;
504 table->table[hi] = chain_end->next;
505 index = chain->hash % newsize;
506 chain_end->next = newtable[index];
507 newtable[index] = chain;
509 table->table = newtable;
510 table->size = newsize;
516 /* Replace an entry in a hash table. */
519 bfd_hash_replace (struct bfd_hash_table *table,
520 struct bfd_hash_entry *old,
521 struct bfd_hash_entry *nw)
524 struct bfd_hash_entry **pph;
526 index = old->hash % table->size;
527 for (pph = &table->table[index];
541 /* Allocate space in a hash table. */
544 bfd_hash_allocate (struct bfd_hash_table *table,
549 ret = objalloc_alloc ((struct objalloc *) table->memory, size);
550 if (ret == NULL && size != 0)
551 bfd_set_error (bfd_error_no_memory);
555 /* Base method for creating a new hash table entry. */
557 struct bfd_hash_entry *
558 bfd_hash_newfunc (struct bfd_hash_entry *entry,
559 struct bfd_hash_table *table,
560 const char *string ATTRIBUTE_UNUSED)
563 entry = bfd_hash_allocate (table, sizeof (* entry));
567 /* Traverse a hash table. */
570 bfd_hash_traverse (struct bfd_hash_table *table,
571 bfd_boolean (*func) (struct bfd_hash_entry *, void *),
576 for (i = 0; i < table->size; i++)
578 struct bfd_hash_entry *p;
580 for (p = table->table[i]; p != NULL; p = p->next)
581 if (! (*func) (p, info))
587 bfd_hash_set_default_size (bfd_size_type hash_size)
589 /* Extend this prime list if you want more granularity of hash table size. */
590 static const bfd_size_type hash_size_primes[] =
592 251, 509, 1021, 2039, 4051, 8599, 16699, 32749
596 /* Work out best prime number near the hash_size. */
597 for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
598 if (hash_size <= hash_size_primes[index])
601 bfd_default_hash_table_size = hash_size_primes[index];
604 /* A few different object file formats (a.out, COFF, ELF) use a string
605 table. These functions support adding strings to a string table,
606 returning the byte offset, and writing out the table.
608 Possible improvements:
609 + look for strings matching trailing substrings of other strings
610 + better data structures? balanced trees?
611 + look at reducing memory use elsewhere -- maybe if we didn't have
612 to construct the entire symbol table at once, we could get by
613 with smaller amounts of VM? (What effect does that have on the
614 string table reductions?) */
616 /* An entry in the strtab hash table. */
618 struct strtab_hash_entry
620 struct bfd_hash_entry root;
621 /* Index in string table. */
623 /* Next string in strtab. */
624 struct strtab_hash_entry *next;
627 /* The strtab hash table. */
629 struct bfd_strtab_hash
631 struct bfd_hash_table table;
632 /* Size of strtab--also next available index. */
634 /* First string in strtab. */
635 struct strtab_hash_entry *first;
636 /* Last string in strtab. */
637 struct strtab_hash_entry *last;
638 /* Whether to precede strings with a two byte length, as in the
639 XCOFF .debug section. */
643 /* Routine to create an entry in a strtab. */
645 static struct bfd_hash_entry *
646 strtab_hash_newfunc (struct bfd_hash_entry *entry,
647 struct bfd_hash_table *table,
650 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
652 /* Allocate the structure if it has not already been allocated by a
655 ret = bfd_hash_allocate (table, sizeof (* ret));
659 /* Call the allocation method of the superclass. */
660 ret = (struct strtab_hash_entry *)
661 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
665 /* Initialize the local fields. */
666 ret->index = (bfd_size_type) -1;
670 return (struct bfd_hash_entry *) ret;
673 /* Look up an entry in an strtab. */
675 #define strtab_hash_lookup(t, string, create, copy) \
676 ((struct strtab_hash_entry *) \
677 bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
679 /* Create a new strtab. */
681 struct bfd_strtab_hash *
682 _bfd_stringtab_init (void)
684 struct bfd_strtab_hash *table;
685 bfd_size_type amt = sizeof (* table);
687 table = bfd_malloc (amt);
691 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
692 sizeof (struct strtab_hash_entry)))
701 table->xcoff = FALSE;
706 /* Create a new strtab in which the strings are output in the format
707 used in the XCOFF .debug section: a two byte length precedes each
710 struct bfd_strtab_hash *
711 _bfd_xcoff_stringtab_init (void)
713 struct bfd_strtab_hash *ret;
715 ret = _bfd_stringtab_init ();
724 _bfd_stringtab_free (struct bfd_strtab_hash *table)
726 bfd_hash_table_free (&table->table);
730 /* Get the index of a string in a strtab, adding it if it is not
731 already present. If HASH is FALSE, we don't really use the hash
732 table, and we don't eliminate duplicate strings. */
735 _bfd_stringtab_add (struct bfd_strtab_hash *tab,
740 struct strtab_hash_entry *entry;
744 entry = strtab_hash_lookup (tab, str, TRUE, copy);
746 return (bfd_size_type) -1;
750 entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
752 return (bfd_size_type) -1;
754 entry->root.string = str;
759 n = bfd_hash_allocate (&tab->table, strlen (str) + 1);
761 return (bfd_size_type) -1;
762 entry->root.string = n;
764 entry->index = (bfd_size_type) -1;
768 if (entry->index == (bfd_size_type) -1)
770 entry->index = tab->size;
771 tab->size += strlen (str) + 1;
777 if (tab->first == NULL)
780 tab->last->next = entry;
787 /* Get the number of bytes in a strtab. */
790 _bfd_stringtab_size (struct bfd_strtab_hash *tab)
795 /* Write out a strtab. ABFD must already be at the right location in
799 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
802 struct strtab_hash_entry *entry;
806 for (entry = tab->first; entry != NULL; entry = entry->next)
811 str = entry->root.string;
812 len = strlen (str) + 1;
818 /* The output length includes the null byte. */
819 bfd_put_16 (abfd, (bfd_vma) len, buf);
820 if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
824 if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)