binutils/bfd/hash.c

1 /* hash.c -- hash table routines for BFD
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
44 	rather than simply providing a data pointer in a hash table
46 	ends.  The linker may create thousands of hash table entries,
50 	The basic hash table code is in <<hash.c>>.
62 	Creating and freeing a hash table
66 	To create a hash table, create an instance of a <<struct
77 	table, use the function <<bfd_hash_newfunc>>.  @xref{Deriving
88 	been allocated for a hash table.  This will not free up the
93 	hash table to use.
102 	string in the hash table and to create a new entry.
107 	string is not found in the table <<bfd_hash_lookup>> will
112 	entered into the hash table if it is not already there.
120 	copy the string onto the hash table objalloc or not.  If
122 	deallocate or modify the string as long as the hash table
128 	Traversing a hash table
132 	hash table, calling a function on each element.  The traversal
137 	hash table entry (a <<struct bfd_hash_entry *>>) and the
140 	continue traversing the hash table.  If the function returns
147 	Deriving a new hash table type
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.
155 	hash table requires sticking together some boilerplate
157 	table you want to create.
159 	An example of a derived hash table is the linker hash table.
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.
178 	You must define a structure for an entry in the hash table,
179 	and a structure for the hash table itself.
182 	table must be of the type used for an entry in the hash table
184 	table this is <<struct bfd_hash_entry>>, which is defined in
186 	table itself must be of the type of the hash table you are
188 	table, this is <<struct bfd_hash_table>>.
190 	For example, the linker hash table defines <<struct
193 	the first field in <<struct bfd_link_hash_table>>, <<table>>,
202 	entry in the hash table.  This routine is passed as the
206 	hash table you are creating, this routine must be written in a
210 	hash table entry.  This may be <<NULL>>, in which case the
212 	the space has already been allocated by a hash table type
216 	creation routine of the hash table type it is derived from,
218 	will initialize any fields used by the base hash table.
221 	for the new hash table type.
225 	@var{entry_type} is the type of an entry in the hash table you
227 	routine of the hash table type your hash table is derived
234 .                     struct bfd_hash_table *table,
243 .      ret = bfd_hash_allocate (table, sizeof (* ret));
250 .	 @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
258 	The creation routine for the linker hash table, which is in
263 	routine for a basic hash table.
266 	in a linker hash table entry: <<type>>, <<written>> and
274 	You will want to write other routines for your new hash table,
278 	initialization routine of the hash table you are deriving from
280 	table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
283 	of the hash table you are deriving from and casts the result.
284 	The linker hash table uses <<bfd_link_hash_lookup>> in
289 	traversal routine of the hash table you are deriving from with
290 	appropriate casts.  The linker hash table uses
294 	the a.out backend linker hash table, which is derived from the
295 	linker hash table, uses macros for the lookup and traversal
300 /* The default number of entries to use when creating a hash table.  */
356 /* Create a new hash table, given a number of entries.  */
359 bfd_hash_table_init_n (struct bfd_hash_table *table,
370   table->memory = (void *) objalloc_create ();
371   if (table->memory == NULL)
376   table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
377   if (table->table == NULL)
382   memset ((void *) table->table, 0, alloc);
383   table->size = size;
384   table->entsize = entsize;
385   table->count = 0;
386   table->frozen = 0;
387   table->newfunc = newfunc;
391 /* Create a new hash table with the default number of entries.  */
394 bfd_hash_table_init (struct bfd_hash_table *table,
400   return bfd_hash_table_init_n (table, newfunc, entsize,
404 /* Free a hash table.  */
407 bfd_hash_table_free (struct bfd_hash_table *table)
409   objalloc_free (table->memory);
410   table->memory = NULL;
413 /* Look up a string in a hash table.  */
416 bfd_hash_lookup (struct bfd_hash_table *table,
440   index = hash % table->size;
441   for (hashp = table->table[index];
453   hashp = (*table->newfunc) (NULL, table, string);
460       new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
471   hashp->next = table->table[index];
472   table->table[index] = hashp;
473   table->count++;
475   if (!table->frozen && table->count > table->size * 3 / 4)
477       unsigned long newsize = higher_prime_number (table->size);
483 	 that much memory, don't try to grow the table.  */
486 	  table->frozen = 1;
491 		  objalloc_alloc ((struct objalloc *) table->memory, alloc));
494       for (hi = 0; hi < table->size; hi ++)
495 	while (table->table[hi])
497 	    struct bfd_hash_entry *chain = table->table[hi];
504 	    table->table[hi] = chain_end->next;
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,
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);
555 /* Base method for creating a new hash table entry.  */
559 		  struct bfd_hash_table *table,
563     entry = bfd_hash_allocate (table, sizeof (* entry));
567 /* Traverse a hash table.  */
570 bfd_hash_traverse (struct bfd_hash_table *table,
576   table->frozen = 1;
577   for (i = 0; i < table->size; i++)
581       for (p = table->table[i]; p != NULL; p = p->next)
586   table->frozen = 0;
593   /* Extend this prime list if you want more granularity of hash table size.  */
610    table.  These functions support adding strings to a string table,
611    returning the byte offset, and writing out the table.
617      to construct the entire symbol table at once, we could get by
619      string table reductions?)  */
621 /* An entry in the strtab hash table.  */
626   /* Index in string table.  */
632 /* The strtab hash table.  */
636   struct bfd_hash_table table;
652 		     struct bfd_hash_table *table,
660     ret = bfd_hash_allocate (table, sizeof (* ret));
666 	 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
682    bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
689   struct bfd_strtab_hash *table;
690   bfd_size_type amt = sizeof (* table);
692   table = bfd_malloc (amt);
693   if (table == NULL)
696   if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
699       free (table);
703   table->size = 0;
704   table->first = NULL;
705   table->last = NULL;
706   table->xcoff = FALSE;
708   return table;
729 _bfd_stringtab_free (struct bfd_strtab_hash *table)
731   bfd_hash_table_free (&table->table);
732   free (table);
737    table, and we don't eliminate duplicate strings.  */
755       entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
764 	  n = bfd_hash_allocate (&tab->table, strlen (str) + 1);