(_bfd_elf_compute_section_file_positions): Initialise strtab to avoid compile
[binutils.git] / bfd / hash.c
blob2b06b922ce3efff387eb065183646fcbfd0772bd
1 /* hash.c -- hash table routines for BFD
2 Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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} (entry, table, string)
234 . struct bfd_hash_entry *entry;
235 . struct bfd_hash_table *table;
236 . const char *string;
238 . struct @var{entry_type} *ret = (@var{entry_type} *) entry;
240 . {* Allocate the structure if it has not already been allocated by a
241 . derived class. *}
242 . if (ret == (@var{entry_type} *) NULL)
244 . ret = ((@var{entry_type} *)
245 . bfd_hash_allocate (table, sizeof (@var{entry_type})));
246 . if (ret == (@var{entry_type} *) NULL)
247 . return NULL;
250 . {* Call the allocation method of the base class. *}
251 . ret = ((@var{entry_type} *)
252 . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
254 . {* Initialize the local fields here. *}
256 . return (struct bfd_hash_entry *) ret;
259 DESCRIPTION
260 The creation routine for the linker hash table, which is in
261 <<linker.c>>, looks just like this example.
262 @var{function_name} is <<_bfd_link_hash_newfunc>>.
263 @var{entry_type} is <<struct bfd_link_hash_entry>>.
264 @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
265 routine for a basic hash table.
267 <<_bfd_link_hash_newfunc>> also initializes the local fields
268 in a linker hash table entry: <<type>>, <<written>> and
269 <<next>>.
271 INODE
272 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
273 SUBSUBSECTION
274 Write other derived routines
276 You will want to write other routines for your new hash table,
277 as well.
279 You will want an initialization routine which calls the
280 initialization routine of the hash table you are deriving from
281 and initializes any other local fields. For the linker hash
282 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
284 You will want a lookup routine which calls the lookup routine
285 of the hash table you are deriving from and casts the result.
286 The linker hash table uses <<bfd_link_hash_lookup>> in
287 <<linker.c>> (this actually takes an additional argument which
288 it uses to decide how to return the looked up value).
290 You may want a traversal routine. This should just call the
291 traversal routine of the hash table you are deriving from with
292 appropriate casts. The linker hash table uses
293 <<bfd_link_hash_traverse>> in <<linker.c>>.
295 These routines may simply be defined as macros. For example,
296 the a.out backend linker hash table, which is derived from the
297 linker hash table, uses macros for the lookup and traversal
298 routines. These are <<aout_link_hash_lookup>> and
299 <<aout_link_hash_traverse>> in aoutx.h.
302 /* The default number of entries to use when creating a hash table. */
303 #define DEFAULT_SIZE 4051
304 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
306 /* Create a new hash table, given a number of entries. */
308 bfd_boolean
309 bfd_hash_table_init_n (table, newfunc, size)
310 struct bfd_hash_table *table;
311 struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
312 struct bfd_hash_table *,
313 const char *));
314 unsigned int size;
316 unsigned int alloc;
318 alloc = size * sizeof (struct bfd_hash_entry *);
320 table->memory = (PTR) objalloc_create ();
321 if (table->memory == NULL)
323 bfd_set_error (bfd_error_no_memory);
324 return FALSE;
326 table->table = ((struct bfd_hash_entry **)
327 objalloc_alloc ((struct objalloc *) table->memory, alloc));
328 if (table->table == NULL)
330 bfd_set_error (bfd_error_no_memory);
331 return FALSE;
333 memset ((PTR) table->table, 0, alloc);
334 table->size = size;
335 table->newfunc = newfunc;
336 return TRUE;
339 /* Create a new hash table with the default number of entries. */
341 bfd_boolean
342 bfd_hash_table_init (table, newfunc)
343 struct bfd_hash_table *table;
344 struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
345 struct bfd_hash_table *,
346 const char *));
348 return bfd_hash_table_init_n (table, newfunc, bfd_default_hash_table_size);
351 /* Free a hash table. */
353 void
354 bfd_hash_table_free (table)
355 struct bfd_hash_table *table;
357 objalloc_free ((struct objalloc *) table->memory);
358 table->memory = NULL;
361 /* Look up a string in a hash table. */
363 struct bfd_hash_entry *
364 bfd_hash_lookup (table, string, create, copy)
365 struct bfd_hash_table *table;
366 const char *string;
367 bfd_boolean create;
368 bfd_boolean copy;
370 register const unsigned char *s;
371 register unsigned long hash;
372 register unsigned int c;
373 struct bfd_hash_entry *hashp;
374 unsigned int len;
375 unsigned int index;
377 hash = 0;
378 len = 0;
379 s = (const unsigned char *) string;
380 while ((c = *s++) != '\0')
382 hash += c + (c << 17);
383 hash ^= hash >> 2;
385 len = (s - (const unsigned char *) string) - 1;
386 hash += len + (len << 17);
387 hash ^= hash >> 2;
389 index = hash % table->size;
390 for (hashp = table->table[index];
391 hashp != (struct bfd_hash_entry *) NULL;
392 hashp = hashp->next)
394 if (hashp->hash == hash
395 && strcmp (hashp->string, string) == 0)
396 return hashp;
399 if (! create)
400 return (struct bfd_hash_entry *) NULL;
402 hashp = (*table->newfunc) ((struct bfd_hash_entry *) NULL, table, string);
403 if (hashp == (struct bfd_hash_entry *) NULL)
404 return (struct bfd_hash_entry *) NULL;
405 if (copy)
407 char *new;
409 new = (char *) objalloc_alloc ((struct objalloc *) table->memory,
410 len + 1);
411 if (!new)
413 bfd_set_error (bfd_error_no_memory);
414 return (struct bfd_hash_entry *) NULL;
416 memcpy (new, string, len + 1);
417 string = new;
419 hashp->string = string;
420 hashp->hash = hash;
421 hashp->next = table->table[index];
422 table->table[index] = hashp;
424 return hashp;
427 /* Replace an entry in a hash table. */
429 void
430 bfd_hash_replace (table, old, nw)
431 struct bfd_hash_table *table;
432 struct bfd_hash_entry *old;
433 struct bfd_hash_entry *nw;
435 unsigned int index;
436 struct bfd_hash_entry **pph;
438 index = old->hash % table->size;
439 for (pph = &table->table[index];
440 (*pph) != (struct bfd_hash_entry *) NULL;
441 pph = &(*pph)->next)
443 if (*pph == old)
445 *pph = nw;
446 return;
450 abort ();
453 /* Base method for creating a new hash table entry. */
455 struct bfd_hash_entry *
456 bfd_hash_newfunc (entry, table, string)
457 struct bfd_hash_entry *entry;
458 struct bfd_hash_table *table;
459 const char *string ATTRIBUTE_UNUSED;
461 if (entry == (struct bfd_hash_entry *) NULL)
462 entry = ((struct bfd_hash_entry *)
463 bfd_hash_allocate (table, sizeof (struct bfd_hash_entry)));
464 return entry;
467 /* Allocate space in a hash table. */
470 bfd_hash_allocate (table, size)
471 struct bfd_hash_table *table;
472 unsigned int size;
474 PTR ret;
476 ret = objalloc_alloc ((struct objalloc *) table->memory, size);
477 if (ret == NULL && size != 0)
478 bfd_set_error (bfd_error_no_memory);
479 return ret;
482 /* Traverse a hash table. */
484 void
485 bfd_hash_traverse (table, func, info)
486 struct bfd_hash_table *table;
487 bfd_boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR));
488 PTR info;
490 unsigned int i;
492 for (i = 0; i < table->size; i++)
494 struct bfd_hash_entry *p;
496 for (p = table->table[i]; p != NULL; p = p->next)
498 if (! (*func) (p, info))
499 return;
504 void
505 bfd_hash_set_default_size (bfd_size_type hash_size)
507 /* Extend this prime list if you want more granularity of hash table size. */
508 static const bfd_size_type hash_size_primes[] =
510 1021, 4051, 8599, 16699
512 size_t index;
514 /* Work out best prime number near the hash_size. */
515 for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
516 if (hash_size <= hash_size_primes[index])
517 break;
519 bfd_default_hash_table_size = hash_size_primes[index];
522 /* A few different object file formats (a.out, COFF, ELF) use a string
523 table. These functions support adding strings to a string table,
524 returning the byte offset, and writing out the table.
526 Possible improvements:
527 + look for strings matching trailing substrings of other strings
528 + better data structures? balanced trees?
529 + look at reducing memory use elsewhere -- maybe if we didn't have
530 to construct the entire symbol table at once, we could get by
531 with smaller amounts of VM? (What effect does that have on the
532 string table reductions?) */
534 /* An entry in the strtab hash table. */
536 struct strtab_hash_entry
538 struct bfd_hash_entry root;
539 /* Index in string table. */
540 bfd_size_type index;
541 /* Next string in strtab. */
542 struct strtab_hash_entry *next;
545 /* The strtab hash table. */
547 struct bfd_strtab_hash
549 struct bfd_hash_table table;
550 /* Size of strtab--also next available index. */
551 bfd_size_type size;
552 /* First string in strtab. */
553 struct strtab_hash_entry *first;
554 /* Last string in strtab. */
555 struct strtab_hash_entry *last;
556 /* Whether to precede strings with a two byte length, as in the
557 XCOFF .debug section. */
558 bfd_boolean xcoff;
561 static struct bfd_hash_entry *strtab_hash_newfunc
562 PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
564 /* Routine to create an entry in a strtab. */
566 static struct bfd_hash_entry *
567 strtab_hash_newfunc (entry, table, string)
568 struct bfd_hash_entry *entry;
569 struct bfd_hash_table *table;
570 const char *string;
572 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
574 /* Allocate the structure if it has not already been allocated by a
575 subclass. */
576 if (ret == (struct strtab_hash_entry *) NULL)
577 ret = ((struct strtab_hash_entry *)
578 bfd_hash_allocate (table, sizeof (struct strtab_hash_entry)));
579 if (ret == (struct strtab_hash_entry *) NULL)
580 return NULL;
582 /* Call the allocation method of the superclass. */
583 ret = ((struct strtab_hash_entry *)
584 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
586 if (ret)
588 /* Initialize the local fields. */
589 ret->index = (bfd_size_type) -1;
590 ret->next = NULL;
593 return (struct bfd_hash_entry *) ret;
596 /* Look up an entry in an strtab. */
598 #define strtab_hash_lookup(t, string, create, copy) \
599 ((struct strtab_hash_entry *) \
600 bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
602 /* Create a new strtab. */
604 struct bfd_strtab_hash *
605 _bfd_stringtab_init ()
607 struct bfd_strtab_hash *table;
608 bfd_size_type amt = sizeof (struct bfd_strtab_hash);
610 table = (struct bfd_strtab_hash *) bfd_malloc (amt);
611 if (table == NULL)
612 return NULL;
614 if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc))
616 free (table);
617 return NULL;
620 table->size = 0;
621 table->first = NULL;
622 table->last = NULL;
623 table->xcoff = FALSE;
625 return table;
628 /* Create a new strtab in which the strings are output in the format
629 used in the XCOFF .debug section: a two byte length precedes each
630 string. */
632 struct bfd_strtab_hash *
633 _bfd_xcoff_stringtab_init ()
635 struct bfd_strtab_hash *ret;
637 ret = _bfd_stringtab_init ();
638 if (ret != NULL)
639 ret->xcoff = TRUE;
640 return ret;
643 /* Free a strtab. */
645 void
646 _bfd_stringtab_free (table)
647 struct bfd_strtab_hash *table;
649 bfd_hash_table_free (&table->table);
650 free (table);
653 /* Get the index of a string in a strtab, adding it if it is not
654 already present. If HASH is FALSE, we don't really use the hash
655 table, and we don't eliminate duplicate strings. */
657 bfd_size_type
658 _bfd_stringtab_add (tab, str, hash, copy)
659 struct bfd_strtab_hash *tab;
660 const char *str;
661 bfd_boolean hash;
662 bfd_boolean copy;
664 register struct strtab_hash_entry *entry;
666 if (hash)
668 entry = strtab_hash_lookup (tab, str, TRUE, copy);
669 if (entry == NULL)
670 return (bfd_size_type) -1;
672 else
674 entry = ((struct strtab_hash_entry *)
675 bfd_hash_allocate (&tab->table,
676 sizeof (struct strtab_hash_entry)));
677 if (entry == NULL)
678 return (bfd_size_type) -1;
679 if (! copy)
680 entry->root.string = str;
681 else
683 char *n;
685 n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1);
686 if (n == NULL)
687 return (bfd_size_type) -1;
688 entry->root.string = n;
690 entry->index = (bfd_size_type) -1;
691 entry->next = NULL;
694 if (entry->index == (bfd_size_type) -1)
696 entry->index = tab->size;
697 tab->size += strlen (str) + 1;
698 if (tab->xcoff)
700 entry->index += 2;
701 tab->size += 2;
703 if (tab->first == NULL)
704 tab->first = entry;
705 else
706 tab->last->next = entry;
707 tab->last = entry;
710 return entry->index;
713 /* Get the number of bytes in a strtab. */
715 bfd_size_type
716 _bfd_stringtab_size (tab)
717 struct bfd_strtab_hash *tab;
719 return tab->size;
722 /* Write out a strtab. ABFD must already be at the right location in
723 the file. */
725 bfd_boolean
726 _bfd_stringtab_emit (abfd, tab)
727 register bfd *abfd;
728 struct bfd_strtab_hash *tab;
730 register bfd_boolean xcoff;
731 register struct strtab_hash_entry *entry;
733 xcoff = tab->xcoff;
735 for (entry = tab->first; entry != NULL; entry = entry->next)
737 const char *str;
738 size_t len;
740 str = entry->root.string;
741 len = strlen (str) + 1;
743 if (xcoff)
745 bfd_byte buf[2];
747 /* The output length includes the null byte. */
748 bfd_put_16 (abfd, (bfd_vma) len, buf);
749 if (bfd_bwrite ((PTR) buf, (bfd_size_type) 2, abfd) != 2)
750 return FALSE;
753 if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
754 return FALSE;
757 return TRUE;