133965Sjdp/* hash.c -- hash table routines for BFD 2218822Sdim Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005, 3218822Sdim 2006, 2007 Free Software Foundation, Inc. 433965Sjdp Written by Steve Chamberlain <sac@cygnus.com> 533965Sjdp 6218822Sdim This file is part of BFD, the Binary File Descriptor library. 733965Sjdp 8218822Sdim This program is free software; you can redistribute it and/or modify 9218822Sdim it under the terms of the GNU General Public License as published by 10218822Sdim the Free Software Foundation; either version 2 of the License, or 11218822Sdim (at your option) any later version. 1233965Sjdp 13218822Sdim This program is distributed in the hope that it will be useful, 14218822Sdim but WITHOUT ANY WARRANTY; without even the implied warranty of 15218822Sdim MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16218822Sdim GNU General Public License for more details. 1733965Sjdp 18218822Sdim You should have received a copy of the GNU General Public License 19218822Sdim along with this program; if not, write to the Free Software 20218822Sdim Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 2133965Sjdp 22218822Sdim#include "sysdep.h" 2333965Sjdp#include "bfd.h" 2433965Sjdp#include "libbfd.h" 2533965Sjdp#include "objalloc.h" 26218822Sdim#include "libiberty.h" 2733965Sjdp 2833965Sjdp/* 2933965SjdpSECTION 3033965Sjdp Hash Tables 3133965Sjdp 3233965Sjdp@cindex Hash tables 3333965Sjdp BFD provides a simple set of hash table functions. Routines 3433965Sjdp are provided to initialize a hash table, to free a hash table, 3533965Sjdp to look up a string in a hash table and optionally create an 3633965Sjdp entry for it, and to traverse a hash table. There is 3733965Sjdp currently no routine to delete an string from a hash table. 3833965Sjdp 3933965Sjdp The basic hash table does not permit any data to be stored 4033965Sjdp with a string. However, a hash table is designed to present a 4133965Sjdp base class from which other types of hash tables may be 4233965Sjdp derived. These derived types may store additional information 4333965Sjdp with the string. Hash tables were implemented in this way, 4433965Sjdp rather than simply providing a data pointer in a hash table 4533965Sjdp entry, because they were designed for use by the linker back 4633965Sjdp ends. The linker may create thousands of hash table entries, 4733965Sjdp and the overhead of allocating private data and storing and 4833965Sjdp following pointers becomes noticeable. 4933965Sjdp 5033965Sjdp The basic hash table code is in <<hash.c>>. 5133965Sjdp 5233965Sjdp@menu 5333965Sjdp@* Creating and Freeing a Hash Table:: 5433965Sjdp@* Looking Up or Entering a String:: 5533965Sjdp@* Traversing a Hash Table:: 5633965Sjdp@* Deriving a New Hash Table Type:: 5733965Sjdp@end menu 5833965Sjdp 5933965SjdpINODE 6033965SjdpCreating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 6133965SjdpSUBSECTION 6233965Sjdp Creating and freeing a hash table 6333965Sjdp 6433965Sjdp@findex bfd_hash_table_init 6533965Sjdp@findex bfd_hash_table_init_n 6633965Sjdp To create a hash table, create an instance of a <<struct 6733965Sjdp bfd_hash_table>> (defined in <<bfd.h>>) and call 6833965Sjdp <<bfd_hash_table_init>> (if you know approximately how many 6933965Sjdp entries you will need, the function <<bfd_hash_table_init_n>>, 7033965Sjdp which takes a @var{size} argument, may be used). 71130561Sobrien <<bfd_hash_table_init>> returns <<FALSE>> if some sort of 7233965Sjdp error occurs. 7333965Sjdp 7433965Sjdp@findex bfd_hash_newfunc 7533965Sjdp The function <<bfd_hash_table_init>> take as an argument a 7633965Sjdp function to use to create new entries. For a basic hash 7733965Sjdp table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 7860484Sobrien a New Hash Table Type}, for why you would want to use a 7933965Sjdp different value for this argument. 8033965Sjdp 8133965Sjdp@findex bfd_hash_allocate 8233965Sjdp <<bfd_hash_table_init>> will create an objalloc which will be 8333965Sjdp used to allocate new entries. You may allocate memory on this 8433965Sjdp objalloc using <<bfd_hash_allocate>>. 8533965Sjdp 8633965Sjdp@findex bfd_hash_table_free 8733965Sjdp Use <<bfd_hash_table_free>> to free up all the memory that has 8833965Sjdp been allocated for a hash table. This will not free up the 8933965Sjdp <<struct bfd_hash_table>> itself, which you must provide. 9033965Sjdp 91218822Sdim@findex bfd_hash_set_default_size 92218822Sdim Use <<bfd_hash_set_default_size>> to set the default size of 93218822Sdim hash table to use. 94218822Sdim 9533965SjdpINODE 9633965SjdpLooking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 9733965SjdpSUBSECTION 9833965Sjdp Looking up or entering a string 9933965Sjdp 10033965Sjdp@findex bfd_hash_lookup 10133965Sjdp The function <<bfd_hash_lookup>> is used both to look up a 10233965Sjdp string in the hash table and to create a new entry. 10333965Sjdp 104130561Sobrien If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>> 10533965Sjdp will look up a string. If the string is found, it will 10633965Sjdp returns a pointer to a <<struct bfd_hash_entry>>. If the 10733965Sjdp string is not found in the table <<bfd_hash_lookup>> will 10833965Sjdp return <<NULL>>. You should not modify any of the fields in 10933965Sjdp the returns <<struct bfd_hash_entry>>. 11033965Sjdp 111130561Sobrien If the @var{create} argument is <<TRUE>>, the string will be 11233965Sjdp entered into the hash table if it is not already there. 11333965Sjdp Either way a pointer to a <<struct bfd_hash_entry>> will be 11433965Sjdp returned, either to the existing structure or to a newly 11533965Sjdp created one. In this case, a <<NULL>> return means that an 11633965Sjdp error occurred. 11733965Sjdp 118130561Sobrien If the @var{create} argument is <<TRUE>>, and a new entry is 11933965Sjdp created, the @var{copy} argument is used to decide whether to 12033965Sjdp copy the string onto the hash table objalloc or not. If 121130561Sobrien @var{copy} is passed as <<FALSE>>, you must be careful not to 12233965Sjdp deallocate or modify the string as long as the hash table 12333965Sjdp exists. 12433965Sjdp 12533965SjdpINODE 12633965SjdpTraversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 12733965SjdpSUBSECTION 12833965Sjdp Traversing a hash table 12933965Sjdp 13033965Sjdp@findex bfd_hash_traverse 13133965Sjdp The function <<bfd_hash_traverse>> may be used to traverse a 13233965Sjdp hash table, calling a function on each element. The traversal 13333965Sjdp is done in a random order. 13433965Sjdp 13533965Sjdp <<bfd_hash_traverse>> takes as arguments a function and a 13633965Sjdp generic <<void *>> pointer. The function is called with a 13733965Sjdp hash table entry (a <<struct bfd_hash_entry *>>) and the 13833965Sjdp generic pointer passed to <<bfd_hash_traverse>>. The function 13933965Sjdp must return a <<boolean>> value, which indicates whether to 14033965Sjdp continue traversing the hash table. If the function returns 141130561Sobrien <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and 14233965Sjdp return immediately. 14333965Sjdp 14433965SjdpINODE 14533965SjdpDeriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 14633965SjdpSUBSECTION 14733965Sjdp Deriving a new hash table type 14833965Sjdp 14933965Sjdp Many uses of hash tables want to store additional information 15033965Sjdp which each entry in the hash table. Some also find it 15133965Sjdp convenient to store additional information with the hash table 15233965Sjdp itself. This may be done using a derived hash table. 15333965Sjdp 15433965Sjdp Since C is not an object oriented language, creating a derived 15533965Sjdp hash table requires sticking together some boilerplate 15633965Sjdp routines with a few differences specific to the type of hash 15733965Sjdp table you want to create. 15833965Sjdp 15933965Sjdp An example of a derived hash table is the linker hash table. 16033965Sjdp The structures for this are defined in <<bfdlink.h>>. The 16133965Sjdp functions are in <<linker.c>>. 16233965Sjdp 16333965Sjdp You may also derive a hash table from an already derived hash 16433965Sjdp table. For example, the a.out linker backend code uses a hash 16533965Sjdp table derived from the linker hash table. 16633965Sjdp 16733965Sjdp@menu 16833965Sjdp@* Define the Derived Structures:: 16933965Sjdp@* Write the Derived Creation Routine:: 17033965Sjdp@* Write Other Derived Routines:: 17133965Sjdp@end menu 17233965Sjdp 17333965SjdpINODE 17433965SjdpDefine the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 17533965SjdpSUBSUBSECTION 17633965Sjdp Define the derived structures 17733965Sjdp 17833965Sjdp You must define a structure for an entry in the hash table, 17933965Sjdp and a structure for the hash table itself. 18033965Sjdp 18133965Sjdp The first field in the structure for an entry in the hash 18233965Sjdp table must be of the type used for an entry in the hash table 18333965Sjdp you are deriving from. If you are deriving from a basic hash 18433965Sjdp table this is <<struct bfd_hash_entry>>, which is defined in 18533965Sjdp <<bfd.h>>. The first field in the structure for the hash 18633965Sjdp table itself must be of the type of the hash table you are 18733965Sjdp deriving from itself. If you are deriving from a basic hash 18833965Sjdp table, this is <<struct bfd_hash_table>>. 18933965Sjdp 19033965Sjdp For example, the linker hash table defines <<struct 19133965Sjdp bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 19233965Sjdp <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 19333965Sjdp the first field in <<struct bfd_link_hash_table>>, <<table>>, 19433965Sjdp is of type <<struct bfd_hash_table>>. 19533965Sjdp 19633965SjdpINODE 19733965SjdpWrite the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 19833965SjdpSUBSUBSECTION 19933965Sjdp Write the derived creation routine 20033965Sjdp 20133965Sjdp You must write a routine which will create and initialize an 20233965Sjdp entry in the hash table. This routine is passed as the 20333965Sjdp function argument to <<bfd_hash_table_init>>. 20433965Sjdp 20533965Sjdp In order to permit other hash tables to be derived from the 20633965Sjdp hash table you are creating, this routine must be written in a 20733965Sjdp standard way. 20833965Sjdp 20933965Sjdp The first argument to the creation routine is a pointer to a 21033965Sjdp hash table entry. This may be <<NULL>>, in which case the 21133965Sjdp routine should allocate the right amount of space. Otherwise 21233965Sjdp the space has already been allocated by a hash table type 21333965Sjdp derived from this one. 21433965Sjdp 21533965Sjdp After allocating space, the creation routine must call the 21633965Sjdp creation routine of the hash table type it is derived from, 21733965Sjdp passing in a pointer to the space it just allocated. This 21833965Sjdp will initialize any fields used by the base hash table. 21933965Sjdp 22033965Sjdp Finally the creation routine must initialize any local fields 22133965Sjdp for the new hash table type. 22233965Sjdp 22333965Sjdp Here is a boilerplate example of a creation routine. 22433965Sjdp @var{function_name} is the name of the routine. 22533965Sjdp @var{entry_type} is the type of an entry in the hash table you 22633965Sjdp are creating. @var{base_newfunc} is the name of the creation 22733965Sjdp routine of the hash table type your hash table is derived 22833965Sjdp from. 22933965Sjdp 23033965SjdpEXAMPLE 23133965Sjdp 23233965Sjdp.struct bfd_hash_entry * 233218822Sdim.@var{function_name} (struct bfd_hash_entry *entry, 234218822Sdim. struct bfd_hash_table *table, 235218822Sdim. const char *string) 23633965Sjdp.{ 23733965Sjdp. struct @var{entry_type} *ret = (@var{entry_type} *) entry; 23833965Sjdp. 23933965Sjdp. {* Allocate the structure if it has not already been allocated by a 24033965Sjdp. derived class. *} 241218822Sdim. if (ret == NULL) 24233965Sjdp. { 243218822Sdim. ret = bfd_hash_allocate (table, sizeof (* ret)); 244218822Sdim. if (ret == NULL) 24533965Sjdp. return NULL; 24633965Sjdp. } 24733965Sjdp. 24833965Sjdp. {* Call the allocation method of the base class. *} 24933965Sjdp. ret = ((@var{entry_type} *) 25033965Sjdp. @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 25133965Sjdp. 25233965Sjdp. {* Initialize the local fields here. *} 25333965Sjdp. 25433965Sjdp. return (struct bfd_hash_entry *) ret; 25533965Sjdp.} 25633965Sjdp 25733965SjdpDESCRIPTION 25833965Sjdp The creation routine for the linker hash table, which is in 25933965Sjdp <<linker.c>>, looks just like this example. 26033965Sjdp @var{function_name} is <<_bfd_link_hash_newfunc>>. 26133965Sjdp @var{entry_type} is <<struct bfd_link_hash_entry>>. 26233965Sjdp @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 26333965Sjdp routine for a basic hash table. 26433965Sjdp 26533965Sjdp <<_bfd_link_hash_newfunc>> also initializes the local fields 26633965Sjdp in a linker hash table entry: <<type>>, <<written>> and 26733965Sjdp <<next>>. 26833965Sjdp 26933965SjdpINODE 27033965SjdpWrite Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 27133965SjdpSUBSUBSECTION 27233965Sjdp Write other derived routines 27333965Sjdp 27433965Sjdp You will want to write other routines for your new hash table, 27577298Sobrien as well. 27633965Sjdp 27733965Sjdp You will want an initialization routine which calls the 27833965Sjdp initialization routine of the hash table you are deriving from 27933965Sjdp and initializes any other local fields. For the linker hash 28033965Sjdp table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 28133965Sjdp 28233965Sjdp You will want a lookup routine which calls the lookup routine 28333965Sjdp of the hash table you are deriving from and casts the result. 28433965Sjdp The linker hash table uses <<bfd_link_hash_lookup>> in 28533965Sjdp <<linker.c>> (this actually takes an additional argument which 28633965Sjdp it uses to decide how to return the looked up value). 28733965Sjdp 28833965Sjdp You may want a traversal routine. This should just call the 28933965Sjdp traversal routine of the hash table you are deriving from with 29033965Sjdp appropriate casts. The linker hash table uses 29133965Sjdp <<bfd_link_hash_traverse>> in <<linker.c>>. 29233965Sjdp 29333965Sjdp These routines may simply be defined as macros. For example, 29433965Sjdp the a.out backend linker hash table, which is derived from the 29533965Sjdp linker hash table, uses macros for the lookup and traversal 29633965Sjdp routines. These are <<aout_link_hash_lookup>> and 29733965Sjdp <<aout_link_hash_traverse>> in aoutx.h. 29833965Sjdp*/ 29933965Sjdp 30033965Sjdp/* The default number of entries to use when creating a hash table. */ 301218822Sdim#define DEFAULT_SIZE 4051 30233965Sjdp 303218822Sdim/* The following function returns a nearest prime number which is 304218822Sdim greater than N, and near a power of two. Copied from libiberty. 305218822Sdim Returns zero for ridiculously large N to signify an error. */ 306218822Sdim 307218822Sdimstatic unsigned long 308218822Sdimhigher_prime_number (unsigned long n) 309218822Sdim{ 310218822Sdim /* These are primes that are near, but slightly smaller than, a 311218822Sdim power of two. */ 312218822Sdim static const unsigned long primes[] = { 313218822Sdim (unsigned long) 127, 314218822Sdim (unsigned long) 2039, 315218822Sdim (unsigned long) 32749, 316218822Sdim (unsigned long) 65521, 317218822Sdim (unsigned long) 131071, 318218822Sdim (unsigned long) 262139, 319218822Sdim (unsigned long) 524287, 320218822Sdim (unsigned long) 1048573, 321218822Sdim (unsigned long) 2097143, 322218822Sdim (unsigned long) 4194301, 323218822Sdim (unsigned long) 8388593, 324218822Sdim (unsigned long) 16777213, 325218822Sdim (unsigned long) 33554393, 326218822Sdim (unsigned long) 67108859, 327218822Sdim (unsigned long) 134217689, 328218822Sdim (unsigned long) 268435399, 329218822Sdim (unsigned long) 536870909, 330218822Sdim (unsigned long) 1073741789, 331218822Sdim (unsigned long) 2147483647, 332218822Sdim /* 4294967291L */ 333218822Sdim ((unsigned long) 2147483647) + ((unsigned long) 2147483644), 334218822Sdim }; 335218822Sdim 336218822Sdim const unsigned long *low = &primes[0]; 337218822Sdim const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; 338218822Sdim 339218822Sdim while (low != high) 340218822Sdim { 341218822Sdim const unsigned long *mid = low + (high - low) / 2; 342218822Sdim if (n >= *mid) 343218822Sdim low = mid + 1; 344218822Sdim else 345218822Sdim high = mid; 346218822Sdim } 347218822Sdim 348218822Sdim if (n >= *low) 349218822Sdim return 0; 350218822Sdim 351218822Sdim return *low; 352218822Sdim} 353218822Sdim 354218822Sdimstatic size_t bfd_default_hash_table_size = DEFAULT_SIZE; 355218822Sdim 35633965Sjdp/* Create a new hash table, given a number of entries. */ 35733965Sjdp 358130561Sobrienbfd_boolean 359218822Sdimbfd_hash_table_init_n (struct bfd_hash_table *table, 360218822Sdim struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 361218822Sdim struct bfd_hash_table *, 362218822Sdim const char *), 363218822Sdim unsigned int entsize, 364218822Sdim unsigned int size) 36533965Sjdp{ 36633965Sjdp unsigned int alloc; 36733965Sjdp 36833965Sjdp alloc = size * sizeof (struct bfd_hash_entry *); 36933965Sjdp 370218822Sdim table->memory = (void *) objalloc_create (); 37133965Sjdp if (table->memory == NULL) 37233965Sjdp { 37333965Sjdp bfd_set_error (bfd_error_no_memory); 374130561Sobrien return FALSE; 37533965Sjdp } 376218822Sdim table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc); 37733965Sjdp if (table->table == NULL) 37833965Sjdp { 37933965Sjdp bfd_set_error (bfd_error_no_memory); 380130561Sobrien return FALSE; 38133965Sjdp } 382218822Sdim memset ((void *) table->table, 0, alloc); 38333965Sjdp table->size = size; 384218822Sdim table->entsize = entsize; 385218822Sdim table->count = 0; 386218822Sdim table->frozen = 0; 38733965Sjdp table->newfunc = newfunc; 388130561Sobrien return TRUE; 38933965Sjdp} 39033965Sjdp 39133965Sjdp/* Create a new hash table with the default number of entries. */ 39233965Sjdp 393130561Sobrienbfd_boolean 394218822Sdimbfd_hash_table_init (struct bfd_hash_table *table, 395218822Sdim struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 396218822Sdim struct bfd_hash_table *, 397218822Sdim const char *), 398218822Sdim unsigned int entsize) 39933965Sjdp{ 400218822Sdim return bfd_hash_table_init_n (table, newfunc, entsize, 401218822Sdim bfd_default_hash_table_size); 40233965Sjdp} 40333965Sjdp 40433965Sjdp/* Free a hash table. */ 40533965Sjdp 40633965Sjdpvoid 407218822Sdimbfd_hash_table_free (struct bfd_hash_table *table) 40833965Sjdp{ 409218822Sdim objalloc_free (table->memory); 41033965Sjdp table->memory = NULL; 41133965Sjdp} 41233965Sjdp 41333965Sjdp/* Look up a string in a hash table. */ 41433965Sjdp 41533965Sjdpstruct bfd_hash_entry * 416218822Sdimbfd_hash_lookup (struct bfd_hash_table *table, 417218822Sdim const char *string, 418218822Sdim bfd_boolean create, 419218822Sdim bfd_boolean copy) 42033965Sjdp{ 421218822Sdim const unsigned char *s; 422218822Sdim unsigned long hash; 423218822Sdim unsigned int c; 42433965Sjdp struct bfd_hash_entry *hashp; 42533965Sjdp unsigned int len; 42633965Sjdp unsigned int index; 42777298Sobrien 42833965Sjdp hash = 0; 42933965Sjdp len = 0; 43033965Sjdp s = (const unsigned char *) string; 43133965Sjdp while ((c = *s++) != '\0') 43233965Sjdp { 43333965Sjdp hash += c + (c << 17); 43433965Sjdp hash ^= hash >> 2; 43533965Sjdp } 436104834Sobrien len = (s - (const unsigned char *) string) - 1; 43733965Sjdp hash += len + (len << 17); 43833965Sjdp hash ^= hash >> 2; 43933965Sjdp 44033965Sjdp index = hash % table->size; 44133965Sjdp for (hashp = table->table[index]; 442218822Sdim hashp != NULL; 44333965Sjdp hashp = hashp->next) 44433965Sjdp { 44533965Sjdp if (hashp->hash == hash 44633965Sjdp && strcmp (hashp->string, string) == 0) 44733965Sjdp return hashp; 44833965Sjdp } 44933965Sjdp 45033965Sjdp if (! create) 451218822Sdim return NULL; 45233965Sjdp 453218822Sdim hashp = (*table->newfunc) (NULL, table, string); 454218822Sdim if (hashp == NULL) 455218822Sdim return NULL; 45633965Sjdp if (copy) 45733965Sjdp { 45833965Sjdp char *new; 45933965Sjdp 460218822Sdim new = objalloc_alloc ((struct objalloc *) table->memory, len + 1); 46133965Sjdp if (!new) 46233965Sjdp { 46333965Sjdp bfd_set_error (bfd_error_no_memory); 464218822Sdim return NULL; 46533965Sjdp } 466104834Sobrien memcpy (new, string, len + 1); 46733965Sjdp string = new; 46833965Sjdp } 46933965Sjdp hashp->string = string; 47033965Sjdp hashp->hash = hash; 47133965Sjdp hashp->next = table->table[index]; 47233965Sjdp table->table[index] = hashp; 473218822Sdim table->count++; 47433965Sjdp 475218822Sdim if (!table->frozen && table->count > table->size * 3 / 4) 476218822Sdim { 477218822Sdim unsigned long newsize = higher_prime_number (table->size); 478218822Sdim struct bfd_hash_entry **newtable; 479218822Sdim unsigned int hi; 480218822Sdim unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *); 481218822Sdim 482218822Sdim /* If we can't find a higher prime, or we can't possibly alloc 483218822Sdim that much memory, don't try to grow the table. */ 484218822Sdim if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize) 485218822Sdim { 486218822Sdim table->frozen = 1; 487218822Sdim return hashp; 488218822Sdim } 489218822Sdim 490218822Sdim newtable = ((struct bfd_hash_entry **) 491218822Sdim objalloc_alloc ((struct objalloc *) table->memory, alloc)); 492218822Sdim memset ((PTR) newtable, 0, alloc); 493218822Sdim 494218822Sdim for (hi = 0; hi < table->size; hi ++) 495218822Sdim while (table->table[hi]) 496218822Sdim { 497218822Sdim struct bfd_hash_entry *chain = table->table[hi]; 498218822Sdim struct bfd_hash_entry *chain_end = chain; 499218822Sdim int index; 500218822Sdim 501218822Sdim while (chain_end->next && chain_end->next->hash == chain->hash) 502218822Sdim chain_end = chain_end->next; 503218822Sdim 504218822Sdim table->table[hi] = chain_end->next; 505218822Sdim index = chain->hash % newsize; 506218822Sdim chain_end->next = newtable[index]; 507218822Sdim newtable[index] = chain; 508218822Sdim } 509218822Sdim table->table = newtable; 510218822Sdim table->size = newsize; 511218822Sdim } 512218822Sdim 51333965Sjdp return hashp; 51433965Sjdp} 51533965Sjdp 51633965Sjdp/* Replace an entry in a hash table. */ 51733965Sjdp 51833965Sjdpvoid 519218822Sdimbfd_hash_replace (struct bfd_hash_table *table, 520218822Sdim struct bfd_hash_entry *old, 521218822Sdim struct bfd_hash_entry *nw) 52233965Sjdp{ 52333965Sjdp unsigned int index; 52433965Sjdp struct bfd_hash_entry **pph; 52533965Sjdp 52633965Sjdp index = old->hash % table->size; 52733965Sjdp for (pph = &table->table[index]; 528218822Sdim (*pph) != NULL; 52933965Sjdp pph = &(*pph)->next) 53033965Sjdp { 53133965Sjdp if (*pph == old) 53233965Sjdp { 53333965Sjdp *pph = nw; 53433965Sjdp return; 53533965Sjdp } 53633965Sjdp } 53733965Sjdp 53833965Sjdp abort (); 53933965Sjdp} 54033965Sjdp 54133965Sjdp/* Allocate space in a hash table. */ 54233965Sjdp 543218822Sdimvoid * 544218822Sdimbfd_hash_allocate (struct bfd_hash_table *table, 545218822Sdim unsigned int size) 54633965Sjdp{ 547218822Sdim void * ret; 54833965Sjdp 54933965Sjdp ret = objalloc_alloc ((struct objalloc *) table->memory, size); 55033965Sjdp if (ret == NULL && size != 0) 55133965Sjdp bfd_set_error (bfd_error_no_memory); 55233965Sjdp return ret; 55333965Sjdp} 55433965Sjdp 555218822Sdim/* Base method for creating a new hash table entry. */ 556218822Sdim 557218822Sdimstruct bfd_hash_entry * 558218822Sdimbfd_hash_newfunc (struct bfd_hash_entry *entry, 559218822Sdim struct bfd_hash_table *table, 560218822Sdim const char *string ATTRIBUTE_UNUSED) 561218822Sdim{ 562218822Sdim if (entry == NULL) 563218822Sdim entry = bfd_hash_allocate (table, sizeof (* entry)); 564218822Sdim return entry; 565218822Sdim} 566218822Sdim 56733965Sjdp/* Traverse a hash table. */ 56833965Sjdp 56933965Sjdpvoid 570218822Sdimbfd_hash_traverse (struct bfd_hash_table *table, 571218822Sdim bfd_boolean (*func) (struct bfd_hash_entry *, void *), 572218822Sdim void * info) 57333965Sjdp{ 57433965Sjdp unsigned int i; 57533965Sjdp 576218822Sdim table->frozen = 1; 57733965Sjdp for (i = 0; i < table->size; i++) 57833965Sjdp { 57933965Sjdp struct bfd_hash_entry *p; 58033965Sjdp 58133965Sjdp for (p = table->table[i]; p != NULL; p = p->next) 582218822Sdim if (! (*func) (p, info)) 583218822Sdim goto out; 58433965Sjdp } 585218822Sdim out: 586218822Sdim table->frozen = 0; 58733965Sjdp} 58833965Sjdp 589218822Sdimvoid 590218822Sdimbfd_hash_set_default_size (bfd_size_type hash_size) 591218822Sdim{ 592218822Sdim /* Extend this prime list if you want more granularity of hash table size. */ 593218822Sdim static const bfd_size_type hash_size_primes[] = 594218822Sdim { 595218822Sdim 251, 509, 1021, 2039, 4051, 8599, 16699, 32749 596218822Sdim }; 597218822Sdim size_t index; 598218822Sdim 599218822Sdim /* Work out best prime number near the hash_size. */ 600218822Sdim for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index) 601218822Sdim if (hash_size <= hash_size_primes[index]) 602218822Sdim break; 603218822Sdim 604218822Sdim bfd_default_hash_table_size = hash_size_primes[index]; 605218822Sdim} 606218822Sdim 60733965Sjdp/* A few different object file formats (a.out, COFF, ELF) use a string 60833965Sjdp table. These functions support adding strings to a string table, 60933965Sjdp returning the byte offset, and writing out the table. 61033965Sjdp 61133965Sjdp Possible improvements: 61233965Sjdp + look for strings matching trailing substrings of other strings 61333965Sjdp + better data structures? balanced trees? 61433965Sjdp + look at reducing memory use elsewhere -- maybe if we didn't have 61533965Sjdp to construct the entire symbol table at once, we could get by 61633965Sjdp with smaller amounts of VM? (What effect does that have on the 61733965Sjdp string table reductions?) */ 61833965Sjdp 61933965Sjdp/* An entry in the strtab hash table. */ 62033965Sjdp 62133965Sjdpstruct strtab_hash_entry 62233965Sjdp{ 62333965Sjdp struct bfd_hash_entry root; 62433965Sjdp /* Index in string table. */ 62533965Sjdp bfd_size_type index; 62633965Sjdp /* Next string in strtab. */ 62733965Sjdp struct strtab_hash_entry *next; 62833965Sjdp}; 62933965Sjdp 63033965Sjdp/* The strtab hash table. */ 63133965Sjdp 63233965Sjdpstruct bfd_strtab_hash 63333965Sjdp{ 63433965Sjdp struct bfd_hash_table table; 63533965Sjdp /* Size of strtab--also next available index. */ 63633965Sjdp bfd_size_type size; 63733965Sjdp /* First string in strtab. */ 63833965Sjdp struct strtab_hash_entry *first; 63933965Sjdp /* Last string in strtab. */ 64033965Sjdp struct strtab_hash_entry *last; 64133965Sjdp /* Whether to precede strings with a two byte length, as in the 64233965Sjdp XCOFF .debug section. */ 643130561Sobrien bfd_boolean xcoff; 64433965Sjdp}; 64533965Sjdp 64633965Sjdp/* Routine to create an entry in a strtab. */ 64733965Sjdp 64833965Sjdpstatic struct bfd_hash_entry * 649218822Sdimstrtab_hash_newfunc (struct bfd_hash_entry *entry, 650218822Sdim struct bfd_hash_table *table, 651218822Sdim const char *string) 65233965Sjdp{ 65333965Sjdp struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 65433965Sjdp 65533965Sjdp /* Allocate the structure if it has not already been allocated by a 65633965Sjdp subclass. */ 657218822Sdim if (ret == NULL) 658218822Sdim ret = bfd_hash_allocate (table, sizeof (* ret)); 659218822Sdim if (ret == NULL) 66033965Sjdp return NULL; 66133965Sjdp 66233965Sjdp /* Call the allocation method of the superclass. */ 663218822Sdim ret = (struct strtab_hash_entry *) 664218822Sdim bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 66533965Sjdp 66633965Sjdp if (ret) 66733965Sjdp { 66833965Sjdp /* Initialize the local fields. */ 66933965Sjdp ret->index = (bfd_size_type) -1; 67033965Sjdp ret->next = NULL; 67133965Sjdp } 67233965Sjdp 67333965Sjdp return (struct bfd_hash_entry *) ret; 67433965Sjdp} 67533965Sjdp 67633965Sjdp/* Look up an entry in an strtab. */ 67733965Sjdp 67833965Sjdp#define strtab_hash_lookup(t, string, create, copy) \ 67933965Sjdp ((struct strtab_hash_entry *) \ 68033965Sjdp bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 68133965Sjdp 68233965Sjdp/* Create a new strtab. */ 68333965Sjdp 68433965Sjdpstruct bfd_strtab_hash * 685218822Sdim_bfd_stringtab_init (void) 68633965Sjdp{ 68733965Sjdp struct bfd_strtab_hash *table; 688218822Sdim bfd_size_type amt = sizeof (* table); 68933965Sjdp 690218822Sdim table = bfd_malloc (amt); 69133965Sjdp if (table == NULL) 69233965Sjdp return NULL; 69333965Sjdp 694218822Sdim if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 695218822Sdim sizeof (struct strtab_hash_entry))) 69633965Sjdp { 69733965Sjdp free (table); 69833965Sjdp return NULL; 69933965Sjdp } 70033965Sjdp 70133965Sjdp table->size = 0; 70233965Sjdp table->first = NULL; 70333965Sjdp table->last = NULL; 704130561Sobrien table->xcoff = FALSE; 70533965Sjdp 70633965Sjdp return table; 70733965Sjdp} 70833965Sjdp 70933965Sjdp/* Create a new strtab in which the strings are output in the format 71033965Sjdp used in the XCOFF .debug section: a two byte length precedes each 71133965Sjdp string. */ 71233965Sjdp 71333965Sjdpstruct bfd_strtab_hash * 714218822Sdim_bfd_xcoff_stringtab_init (void) 71533965Sjdp{ 71633965Sjdp struct bfd_strtab_hash *ret; 71733965Sjdp 71833965Sjdp ret = _bfd_stringtab_init (); 71933965Sjdp if (ret != NULL) 720130561Sobrien ret->xcoff = TRUE; 72133965Sjdp return ret; 72233965Sjdp} 72333965Sjdp 72433965Sjdp/* Free a strtab. */ 72533965Sjdp 72633965Sjdpvoid 727218822Sdim_bfd_stringtab_free (struct bfd_strtab_hash *table) 72833965Sjdp{ 72933965Sjdp bfd_hash_table_free (&table->table); 73033965Sjdp free (table); 73133965Sjdp} 73233965Sjdp 73333965Sjdp/* Get the index of a string in a strtab, adding it if it is not 734130561Sobrien already present. If HASH is FALSE, we don't really use the hash 73533965Sjdp table, and we don't eliminate duplicate strings. */ 73633965Sjdp 73733965Sjdpbfd_size_type 738218822Sdim_bfd_stringtab_add (struct bfd_strtab_hash *tab, 739218822Sdim const char *str, 740218822Sdim bfd_boolean hash, 741218822Sdim bfd_boolean copy) 74233965Sjdp{ 743218822Sdim struct strtab_hash_entry *entry; 74433965Sjdp 74533965Sjdp if (hash) 74633965Sjdp { 747130561Sobrien entry = strtab_hash_lookup (tab, str, TRUE, copy); 74833965Sjdp if (entry == NULL) 74933965Sjdp return (bfd_size_type) -1; 75033965Sjdp } 75133965Sjdp else 75233965Sjdp { 753218822Sdim entry = bfd_hash_allocate (&tab->table, sizeof (* entry)); 75433965Sjdp if (entry == NULL) 75533965Sjdp return (bfd_size_type) -1; 75633965Sjdp if (! copy) 75733965Sjdp entry->root.string = str; 75833965Sjdp else 75933965Sjdp { 76033965Sjdp char *n; 76133965Sjdp 762218822Sdim n = bfd_hash_allocate (&tab->table, strlen (str) + 1); 76333965Sjdp if (n == NULL) 76433965Sjdp return (bfd_size_type) -1; 76533965Sjdp entry->root.string = n; 76633965Sjdp } 76733965Sjdp entry->index = (bfd_size_type) -1; 76833965Sjdp entry->next = NULL; 76933965Sjdp } 77033965Sjdp 77133965Sjdp if (entry->index == (bfd_size_type) -1) 77233965Sjdp { 77333965Sjdp entry->index = tab->size; 77433965Sjdp tab->size += strlen (str) + 1; 77533965Sjdp if (tab->xcoff) 77633965Sjdp { 77733965Sjdp entry->index += 2; 77833965Sjdp tab->size += 2; 77933965Sjdp } 78033965Sjdp if (tab->first == NULL) 78133965Sjdp tab->first = entry; 78233965Sjdp else 78333965Sjdp tab->last->next = entry; 78433965Sjdp tab->last = entry; 78533965Sjdp } 78633965Sjdp 78733965Sjdp return entry->index; 78833965Sjdp} 78933965Sjdp 79033965Sjdp/* Get the number of bytes in a strtab. */ 79133965Sjdp 79233965Sjdpbfd_size_type 793218822Sdim_bfd_stringtab_size (struct bfd_strtab_hash *tab) 79433965Sjdp{ 79533965Sjdp return tab->size; 79633965Sjdp} 79733965Sjdp 79833965Sjdp/* Write out a strtab. ABFD must already be at the right location in 79933965Sjdp the file. */ 80033965Sjdp 801130561Sobrienbfd_boolean 802218822Sdim_bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 80333965Sjdp{ 804218822Sdim bfd_boolean xcoff; 805218822Sdim struct strtab_hash_entry *entry; 80633965Sjdp 80733965Sjdp xcoff = tab->xcoff; 80833965Sjdp 80933965Sjdp for (entry = tab->first; entry != NULL; entry = entry->next) 81033965Sjdp { 81189857Sobrien const char *str; 81289857Sobrien size_t len; 81333965Sjdp 81433965Sjdp str = entry->root.string; 81533965Sjdp len = strlen (str) + 1; 81633965Sjdp 81733965Sjdp if (xcoff) 81833965Sjdp { 81933965Sjdp bfd_byte buf[2]; 82033965Sjdp 82133965Sjdp /* The output length includes the null byte. */ 82289857Sobrien bfd_put_16 (abfd, (bfd_vma) len, buf); 823218822Sdim if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 824130561Sobrien return FALSE; 82533965Sjdp } 82633965Sjdp 827218822Sdim if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 828130561Sobrien return FALSE; 82933965Sjdp } 83033965Sjdp 831130561Sobrien return TRUE; 83233965Sjdp} 833