2005-10-05 Paolo Bonzini <bonzini@gnu.org>
[binutils.git] / bfd / hash.c
blobfc3177331b57de3b29a7b40411b650e726f011f5
1 /* hash.c -- hash table routines for BFD
2 Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005
3 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. */
22 #include "bfd.h"
23 #include "sysdep.h"
24 #include "libbfd.h"
25 #include "objalloc.h"
26 #include "libiberty.h"
29 SECTION
30 Hash Tables
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.
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>>.
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
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
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.
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
93 hash table to use.
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
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
116 error occurred.
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.
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
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
142 return immediately.
144 INODE
145 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
146 SUBSECTION
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.
167 @menu
168 @* Define the Derived Structures::
169 @* Write the Derived Creation Routine::
170 @* Write Other Derived Routines::
171 @end menu
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
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>>.
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
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
207 standard way.
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
228 from.
230 EXAMPLE
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
240 . derived class. *}
241 . if (ret == NULL)
243 . ret = bfd_hash_allocate (table, sizeof (* ret));
244 . if (ret == NULL)
245 . return NULL;
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;
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.
265 <<_bfd_link_hash_newfunc>> also initializes the local fields
266 in a linker hash table entry: <<type>>, <<written>> and
267 <<next>>.
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
274 You will want to write other routines for your new hash table,
275 as well.
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
302 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
304 /* Create a new hash table, given a number of entries. */
306 bfd_boolean
307 bfd_hash_table_init_n (struct bfd_hash_table *table,
308 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
309 struct bfd_hash_table *,
310 const char *),
311 unsigned int size)
313 unsigned int alloc;
315 alloc = size * sizeof (struct bfd_hash_entry *);
317 table->memory = (void *) objalloc_create ();
318 if (table->memory == NULL)
320 bfd_set_error (bfd_error_no_memory);
321 return FALSE;
323 table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
324 if (table->table == NULL)
326 bfd_set_error (bfd_error_no_memory);
327 return FALSE;
329 memset ((void *) table->table, 0, alloc);
330 table->size = size;
331 table->newfunc = newfunc;
332 return TRUE;
335 /* Create a new hash table with the default number of entries. */
337 bfd_boolean
338 bfd_hash_table_init (struct bfd_hash_table *table,
339 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
340 struct bfd_hash_table *,
341 const char *))
343 return bfd_hash_table_init_n (table, newfunc, bfd_default_hash_table_size);
346 /* Free a hash table. */
348 void
349 bfd_hash_table_free (struct bfd_hash_table *table)
351 objalloc_free (table->memory);
352 table->memory = NULL;
355 /* Look up a string in a hash table. */
357 struct bfd_hash_entry *
358 bfd_hash_lookup (struct bfd_hash_table *table,
359 const char *string,
360 bfd_boolean create,
361 bfd_boolean copy)
363 const unsigned char *s;
364 unsigned long hash;
365 unsigned int c;
366 struct bfd_hash_entry *hashp;
367 unsigned int len;
368 unsigned int index;
370 hash = 0;
371 len = 0;
372 s = (const unsigned char *) string;
373 while ((c = *s++) != '\0')
375 hash += c + (c << 17);
376 hash ^= hash >> 2;
378 len = (s - (const unsigned char *) string) - 1;
379 hash += len + (len << 17);
380 hash ^= hash >> 2;
382 index = hash % table->size;
383 for (hashp = table->table[index];
384 hashp != NULL;
385 hashp = hashp->next)
387 if (hashp->hash == hash
388 && strcmp (hashp->string, string) == 0)
389 return hashp;
392 if (! create)
393 return NULL;
395 hashp = (*table->newfunc) (NULL, table, string);
396 if (hashp == NULL)
397 return NULL;
398 if (copy)
400 char *new;
402 new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
403 if (!new)
405 bfd_set_error (bfd_error_no_memory);
406 return NULL;
408 memcpy (new, string, len + 1);
409 string = new;
411 hashp->string = string;
412 hashp->hash = hash;
413 hashp->next = table->table[index];
414 table->table[index] = hashp;
416 return hashp;
419 /* Replace an entry in a hash table. */
421 void
422 bfd_hash_replace (struct bfd_hash_table *table,
423 struct bfd_hash_entry *old,
424 struct bfd_hash_entry *nw)
426 unsigned int index;
427 struct bfd_hash_entry **pph;
429 index = old->hash % table->size;
430 for (pph = &table->table[index];
431 (*pph) != NULL;
432 pph = &(*pph)->next)
434 if (*pph == old)
436 *pph = nw;
437 return;
441 abort ();
444 /* Allocate space in a hash table. */
446 void *
447 bfd_hash_allocate (struct bfd_hash_table *table,
448 unsigned int size)
450 void * ret;
452 ret = objalloc_alloc ((struct objalloc *) table->memory, size);
453 if (ret == NULL && size != 0)
454 bfd_set_error (bfd_error_no_memory);
455 return ret;
458 /* Base method for creating a new hash table entry. */
460 struct bfd_hash_entry *
461 bfd_hash_newfunc (struct bfd_hash_entry *entry,
462 struct bfd_hash_table *table,
463 const char *string ATTRIBUTE_UNUSED)
465 if (entry == NULL)
466 entry = bfd_hash_allocate (table, sizeof (* entry));
467 return entry;
470 /* Traverse a hash table. */
472 void
473 bfd_hash_traverse (struct bfd_hash_table *table,
474 bfd_boolean (*func) (struct bfd_hash_entry *, void *),
475 void * info)
477 unsigned int i;
479 for (i = 0; i < table->size; i++)
481 struct bfd_hash_entry *p;
483 for (p = table->table[i]; p != NULL; p = p->next)
484 if (! (*func) (p, info))
485 return;
489 void
490 bfd_hash_set_default_size (bfd_size_type hash_size)
492 /* Extend this prime list if you want more granularity of hash table size. */
493 static const bfd_size_type hash_size_primes[] =
495 1021, 4051, 8599, 16699
497 size_t index;
499 /* Work out best prime number near the hash_size. */
500 for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
501 if (hash_size <= hash_size_primes[index])
502 break;
504 bfd_default_hash_table_size = hash_size_primes[index];
507 /* A few different object file formats (a.out, COFF, ELF) use a string
508 table. These functions support adding strings to a string table,
509 returning the byte offset, and writing out the table.
511 Possible improvements:
512 + look for strings matching trailing substrings of other strings
513 + better data structures? balanced trees?
514 + look at reducing memory use elsewhere -- maybe if we didn't have
515 to construct the entire symbol table at once, we could get by
516 with smaller amounts of VM? (What effect does that have on the
517 string table reductions?) */
519 /* An entry in the strtab hash table. */
521 struct strtab_hash_entry
523 struct bfd_hash_entry root;
524 /* Index in string table. */
525 bfd_size_type index;
526 /* Next string in strtab. */
527 struct strtab_hash_entry *next;
530 /* The strtab hash table. */
532 struct bfd_strtab_hash
534 struct bfd_hash_table table;
535 /* Size of strtab--also next available index. */
536 bfd_size_type size;
537 /* First string in strtab. */
538 struct strtab_hash_entry *first;
539 /* Last string in strtab. */
540 struct strtab_hash_entry *last;
541 /* Whether to precede strings with a two byte length, as in the
542 XCOFF .debug section. */
543 bfd_boolean xcoff;
546 /* Routine to create an entry in a strtab. */
548 static struct bfd_hash_entry *
549 strtab_hash_newfunc (struct bfd_hash_entry *entry,
550 struct bfd_hash_table *table,
551 const char *string)
553 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
555 /* Allocate the structure if it has not already been allocated by a
556 subclass. */
557 if (ret == NULL)
558 ret = bfd_hash_allocate (table, sizeof (* ret));
559 if (ret == NULL)
560 return NULL;
562 /* Call the allocation method of the superclass. */
563 ret = (struct strtab_hash_entry *)
564 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
566 if (ret)
568 /* Initialize the local fields. */
569 ret->index = (bfd_size_type) -1;
570 ret->next = NULL;
573 return (struct bfd_hash_entry *) ret;
576 /* Look up an entry in an strtab. */
578 #define strtab_hash_lookup(t, string, create, copy) \
579 ((struct strtab_hash_entry *) \
580 bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
582 /* Create a new strtab. */
584 struct bfd_strtab_hash *
585 _bfd_stringtab_init (void)
587 struct bfd_strtab_hash *table;
588 bfd_size_type amt = sizeof (* table);
590 table = bfd_malloc (amt);
591 if (table == NULL)
592 return NULL;
594 if (! bfd_hash_table_init (& table->table, strtab_hash_newfunc))
596 free (table);
597 return NULL;
600 table->size = 0;
601 table->first = NULL;
602 table->last = NULL;
603 table->xcoff = FALSE;
605 return table;
608 /* Create a new strtab in which the strings are output in the format
609 used in the XCOFF .debug section: a two byte length precedes each
610 string. */
612 struct bfd_strtab_hash *
613 _bfd_xcoff_stringtab_init (void)
615 struct bfd_strtab_hash *ret;
617 ret = _bfd_stringtab_init ();
618 if (ret != NULL)
619 ret->xcoff = TRUE;
620 return ret;
623 /* Free a strtab. */
625 void
626 _bfd_stringtab_free (struct bfd_strtab_hash *table)
628 bfd_hash_table_free (&table->table);
629 free (table);
632 /* Get the index of a string in a strtab, adding it if it is not
633 already present. If HASH is FALSE, we don't really use the hash
634 table, and we don't eliminate duplicate strings. */
636 bfd_size_type
637 _bfd_stringtab_add (struct bfd_strtab_hash *tab,
638 const char *str,
639 bfd_boolean hash,
640 bfd_boolean copy)
642 struct strtab_hash_entry *entry;
644 if (hash)
646 entry = strtab_hash_lookup (tab, str, TRUE, copy);
647 if (entry == NULL)
648 return (bfd_size_type) -1;
650 else
652 entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
653 if (entry == NULL)
654 return (bfd_size_type) -1;
655 if (! copy)
656 entry->root.string = str;
657 else
659 char *n;
661 n = bfd_hash_allocate (&tab->table, strlen (str) + 1);
662 if (n == NULL)
663 return (bfd_size_type) -1;
664 entry->root.string = n;
666 entry->index = (bfd_size_type) -1;
667 entry->next = NULL;
670 if (entry->index == (bfd_size_type) -1)
672 entry->index = tab->size;
673 tab->size += strlen (str) + 1;
674 if (tab->xcoff)
676 entry->index += 2;
677 tab->size += 2;
679 if (tab->first == NULL)
680 tab->first = entry;
681 else
682 tab->last->next = entry;
683 tab->last = entry;
686 return entry->index;
689 /* Get the number of bytes in a strtab. */
691 bfd_size_type
692 _bfd_stringtab_size (struct bfd_strtab_hash *tab)
694 return tab->size;
697 /* Write out a strtab. ABFD must already be at the right location in
698 the file. */
700 bfd_boolean
701 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
703 bfd_boolean xcoff;
704 struct strtab_hash_entry *entry;
706 xcoff = tab->xcoff;
708 for (entry = tab->first; entry != NULL; entry = entry->next)
710 const char *str;
711 size_t len;
713 str = entry->root.string;
714 len = strlen (str) + 1;
716 if (xcoff)
718 bfd_byte buf[2];
720 /* The output length includes the null byte. */
721 bfd_put_16 (abfd, (bfd_vma) len, buf);
722 if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
723 return FALSE;
726 if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
727 return FALSE;
730 return TRUE;