hash.c revision 218822
1215976Sjmallett/* hash.c -- hash table routines for BFD 2232812Sjmallett Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005, 3215976Sjmallett 2006, 2007 Free Software Foundation, Inc. 4215976Sjmallett Written by Steve Chamberlain <sac@cygnus.com> 5215976Sjmallett 6215976Sjmallett This file is part of BFD, the Binary File Descriptor library. 7215976Sjmallett 8215976Sjmallett This program is free software; you can redistribute it and/or modify 9215976Sjmallett it under the terms of the GNU General Public License as published by 10215976Sjmallett the Free Software Foundation; either version 2 of the License, or 11215976Sjmallett (at your option) any later version. 12215976Sjmallett 13215976Sjmallett This program is distributed in the hope that it will be useful, 14215976Sjmallett but WITHOUT ANY WARRANTY; without even the implied warranty of 15215976Sjmallett MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16215976Sjmallett GNU General Public License for more details. 17215976Sjmallett 18232812Sjmallett You should have received a copy of the GNU General Public License 19215976Sjmallett along with this program; if not, write to the Free Software 20215976Sjmallett Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 21215976Sjmallett 22215976Sjmallett#include "sysdep.h" 23215976Sjmallett#include "bfd.h" 24215976Sjmallett#include "libbfd.h" 25215976Sjmallett#include "objalloc.h" 26215976Sjmallett#include "libiberty.h" 27215976Sjmallett 28215976Sjmallett/* 29232812SjmallettSECTION 30215976Sjmallett Hash Tables 31215976Sjmallett 32215976Sjmallett@cindex Hash tables 33215976Sjmallett BFD provides a simple set of hash table functions. Routines 34215976Sjmallett are provided to initialize a hash table, to free a hash table, 35215976Sjmallett to look up a string in a hash table and optionally create an 36215976Sjmallett entry for it, and to traverse a hash table. There is 37215976Sjmallett currently no routine to delete an string from a hash table. 38215976Sjmallett 39215976Sjmallett The basic hash table does not permit any data to be stored 40215976Sjmallett with a string. However, a hash table is designed to present a 41215976Sjmallett base class from which other types of hash tables may be 42215976Sjmallett derived. These derived types may store additional information 43215976Sjmallett with the string. Hash tables were implemented in this way, 44215976Sjmallett rather than simply providing a data pointer in a hash table 45215976Sjmallett entry, because they were designed for use by the linker back 46215976Sjmallett ends. The linker may create thousands of hash table entries, 47215976Sjmallett and the overhead of allocating private data and storing and 48215976Sjmallett following pointers becomes noticeable. 49215976Sjmallett 50215976Sjmallett The basic hash table code is in <<hash.c>>. 51215976Sjmallett 52232812Sjmallett@menu 53232812Sjmallett@* Creating and Freeing a Hash Table:: 54215976Sjmallett@* Looking Up or Entering a String:: 55215976Sjmallett@* Traversing a Hash Table:: 56215976Sjmallett@* Deriving a New Hash Table Type:: 57232812Sjmallett@end menu 58232812Sjmallett 59232812SjmallettINODE 60232812SjmallettCreating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 61232812SjmallettSUBSECTION 62232812Sjmallett Creating and freeing a hash table 63232812Sjmallett 64232812Sjmallett@findex bfd_hash_table_init 65232812Sjmallett@findex bfd_hash_table_init_n 66232812Sjmallett To create a hash table, create an instance of a <<struct 67232812Sjmallett bfd_hash_table>> (defined in <<bfd.h>>) and call 68232812Sjmallett <<bfd_hash_table_init>> (if you know approximately how many 69232812Sjmallett entries you will need, the function <<bfd_hash_table_init_n>>, 70232812Sjmallett which takes a @var{size} argument, may be used). 71232812Sjmallett <<bfd_hash_table_init>> returns <<FALSE>> if some sort of 72232812Sjmallett error occurs. 73232812Sjmallett 74232812Sjmallett@findex bfd_hash_newfunc 75232812Sjmallett The function <<bfd_hash_table_init>> take as an argument a 76215976Sjmallett function to use to create new entries. For a basic hash 77215976Sjmallett table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 78215976Sjmallett a New Hash Table Type}, for why you would want to use a 79232812Sjmallett different value for this argument. 80232812Sjmallett 81232812Sjmallett@findex bfd_hash_allocate 82232812Sjmallett <<bfd_hash_table_init>> will create an objalloc which will be 83232812Sjmallett used to allocate new entries. You may allocate memory on this 84232812Sjmallett objalloc using <<bfd_hash_allocate>>. 85232812Sjmallett 86232812Sjmallett@findex bfd_hash_table_free 87232812Sjmallett Use <<bfd_hash_table_free>> to free up all the memory that has 88232812Sjmallett been allocated for a hash table. This will not free up the 89232812Sjmallett <<struct bfd_hash_table>> itself, which you must provide. 90232812Sjmallett 91232812Sjmallett@findex bfd_hash_set_default_size 92232812Sjmallett Use <<bfd_hash_set_default_size>> to set the default size of 93232812Sjmallett hash table to use. 94232812Sjmallett 95232812SjmallettINODE 96232812SjmallettLooking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 97232812SjmallettSUBSECTION 98215976Sjmallett Looking up or entering a string 99215976Sjmallett 100215976Sjmallett@findex bfd_hash_lookup 101232812Sjmallett The function <<bfd_hash_lookup>> is used both to look up a 102232812Sjmallett string in the hash table and to create a new entry. 103232812Sjmallett 104232812Sjmallett If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>> 105232812Sjmallett will look up a string. If the string is found, it will 106232812Sjmallett returns a pointer to a <<struct bfd_hash_entry>>. If the 107232812Sjmallett string is not found in the table <<bfd_hash_lookup>> will 108232812Sjmallett return <<NULL>>. You should not modify any of the fields in 109232812Sjmallett the returns <<struct bfd_hash_entry>>. 110232812Sjmallett 111232812Sjmallett If the @var{create} argument is <<TRUE>>, the string will be 112232812Sjmallett entered into the hash table if it is not already there. 113232812Sjmallett Either way a pointer to a <<struct bfd_hash_entry>> will be 114232812Sjmallett returned, either to the existing structure or to a newly 115232812Sjmallett created one. In this case, a <<NULL>> return means that an 116232812Sjmallett error occurred. 117232812Sjmallett 118232812Sjmallett If the @var{create} argument is <<TRUE>>, and a new entry is 119232812Sjmallett created, the @var{copy} argument is used to decide whether to 120215976Sjmallett copy the string onto the hash table objalloc or not. If 121215976Sjmallett @var{copy} is passed as <<FALSE>>, you must be careful not to 122215976Sjmallett deallocate or modify the string as long as the hash table 123232812Sjmallett exists. 124232812Sjmallett 125232812SjmallettINODE 126232812SjmallettTraversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 127232812SjmallettSUBSECTION 128232812Sjmallett Traversing a hash table 129232812Sjmallett 130232812Sjmallett@findex bfd_hash_traverse 131232812Sjmallett The function <<bfd_hash_traverse>> may be used to traverse a 132232812Sjmallett hash table, calling a function on each element. The traversal 133232812Sjmallett is done in a random order. 134232812Sjmallett 135232812Sjmallett <<bfd_hash_traverse>> takes as arguments a function and a 136232812Sjmallett generic <<void *>> pointer. The function is called with a 137232812Sjmallett hash table entry (a <<struct bfd_hash_entry *>>) and the 138232812Sjmallett generic pointer passed to <<bfd_hash_traverse>>. The function 139232812Sjmallett must return a <<boolean>> value, which indicates whether to 140232812Sjmallett continue traversing the hash table. If the function returns 141232812Sjmallett <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and 142215976Sjmallett return immediately. 143215976Sjmallett 144215976SjmallettINODE 145232812SjmallettDeriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 146232812SjmallettSUBSECTION 147232812Sjmallett Deriving a new hash table type 148232812Sjmallett 149232812Sjmallett Many uses of hash tables want to store additional information 150232812Sjmallett which each entry in the hash table. Some also find it 151232812Sjmallett convenient to store additional information with the hash table 152232812Sjmallett itself. This may be done using a derived hash table. 153232812Sjmallett 154232812Sjmallett Since C is not an object oriented language, creating a derived 155232812Sjmallett hash table requires sticking together some boilerplate 156232812Sjmallett routines with a few differences specific to the type of hash 157232812Sjmallett table you want to create. 158232812Sjmallett 159232812Sjmallett An example of a derived hash table is the linker hash table. 160232812Sjmallett The structures for this are defined in <<bfdlink.h>>. The 161232812Sjmallett functions are in <<linker.c>>. 162232812Sjmallett 163232812Sjmallett You may also derive a hash table from an already derived hash 164215976Sjmallett table. For example, the a.out linker backend code uses a hash 165215976Sjmallett table derived from the linker hash table. 166215976Sjmallett 167232812Sjmallett@menu 168232812Sjmallett@* Define the Derived Structures:: 169232812Sjmallett@* Write the Derived Creation Routine:: 170232812Sjmallett@* Write Other Derived Routines:: 171232812Sjmallett@end menu 172232812Sjmallett 173232812SjmallettINODE 174232812SjmallettDefine the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 175232812SjmallettSUBSUBSECTION 176232812Sjmallett Define the derived structures 177232812Sjmallett 178232812Sjmallett You must define a structure for an entry in the hash table, 179232812Sjmallett and a structure for the hash table itself. 180232812Sjmallett 181232812Sjmallett The first field in the structure for an entry in the hash 182232812Sjmallett table must be of the type used for an entry in the hash table 183232812Sjmallett you are deriving from. If you are deriving from a basic hash 184232812Sjmallett table this is <<struct bfd_hash_entry>>, which is defined in 185232812Sjmallett <<bfd.h>>. The first field in the structure for the hash 186215976Sjmallett table itself must be of the type of the hash table you are 187215976Sjmallett deriving from itself. If you are deriving from a basic hash 188215976Sjmallett table, this is <<struct bfd_hash_table>>. 189232812Sjmallett 190232812Sjmallett For example, the linker hash table defines <<struct 191232812Sjmallett bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 192232812Sjmallett <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 193232812Sjmallett the first field in <<struct bfd_link_hash_table>>, <<table>>, 194232812Sjmallett is of type <<struct bfd_hash_table>>. 195232812Sjmallett 196232812SjmallettINODE 197232812SjmallettWrite the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 198232812SjmallettSUBSUBSECTION 199232812Sjmallett Write the derived creation routine 200232812Sjmallett 201232812Sjmallett You must write a routine which will create and initialize an 202232812Sjmallett entry in the hash table. This routine is passed as the 203232812Sjmallett function argument to <<bfd_hash_table_init>>. 204232812Sjmallett 205232812Sjmallett In order to permit other hash tables to be derived from the 206232812Sjmallett hash table you are creating, this routine must be written in a 207232812Sjmallett standard way. 208215976Sjmallett 209215976Sjmallett The first argument to the creation routine is a pointer to a 210215976Sjmallett hash table entry. This may be <<NULL>>, in which case the 211232812Sjmallett routine should allocate the right amount of space. Otherwise 212232812Sjmallett the space has already been allocated by a hash table type 213232812Sjmallett derived from this one. 214232812Sjmallett 215232812Sjmallett After allocating space, the creation routine must call the 216232812Sjmallett creation routine of the hash table type it is derived from, 217232812Sjmallett passing in a pointer to the space it just allocated. This 218232812Sjmallett will initialize any fields used by the base hash table. 219232812Sjmallett 220232812Sjmallett Finally the creation routine must initialize any local fields 221232812Sjmallett for the new hash table type. 222232812Sjmallett 223232812Sjmallett Here is a boilerplate example of a creation routine. 224232812Sjmallett @var{function_name} is the name of the routine. 225232812Sjmallett @var{entry_type} is the type of an entry in the hash table you 226232812Sjmallett are creating. @var{base_newfunc} is the name of the creation 227232812Sjmallett routine of the hash table type your hash table is derived 228232812Sjmallett from. 229232812Sjmallett 230215976SjmallettEXAMPLE 231215976Sjmallett 232215976Sjmallett.struct bfd_hash_entry * 233232812Sjmallett.@var{function_name} (struct bfd_hash_entry *entry, 234232812Sjmallett. struct bfd_hash_table *table, 235232812Sjmallett. const char *string) 236232812Sjmallett.{ 237232812Sjmallett. struct @var{entry_type} *ret = (@var{entry_type} *) entry; 238232812Sjmallett. 239232812Sjmallett. {* Allocate the structure if it has not already been allocated by a 240232812Sjmallett. derived class. *} 241232812Sjmallett. if (ret == NULL) 242232812Sjmallett. { 243232812Sjmallett. ret = bfd_hash_allocate (table, sizeof (* ret)); 244232812Sjmallett. if (ret == NULL) 245232812Sjmallett. return NULL; 246232812Sjmallett. } 247232812Sjmallett. 248232812Sjmallett. {* Call the allocation method of the base class. *} 249232812Sjmallett. ret = ((@var{entry_type} *) 250232812Sjmallett. @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 251232812Sjmallett. 252215976Sjmallett. {* Initialize the local fields here. *} 253215976Sjmallett. 254215976Sjmallett. return (struct bfd_hash_entry *) ret; 255232812Sjmallett.} 256232812Sjmallett 257232812SjmallettDESCRIPTION 258232812Sjmallett The creation routine for the linker hash table, which is in 259232812Sjmallett <<linker.c>>, looks just like this example. 260232812Sjmallett @var{function_name} is <<_bfd_link_hash_newfunc>>. 261232812Sjmallett @var{entry_type} is <<struct bfd_link_hash_entry>>. 262232812Sjmallett @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 263232812Sjmallett routine for a basic hash table. 264232812Sjmallett 265232812Sjmallett <<_bfd_link_hash_newfunc>> also initializes the local fields 266232812Sjmallett in a linker hash table entry: <<type>>, <<written>> and 267232812Sjmallett <<next>>. 268232812Sjmallett 269232812SjmallettINODE 270232812SjmallettWrite Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 271232812SjmallettSUBSUBSECTION 272232812Sjmallett Write other derived routines 273232812Sjmallett 274215976Sjmallett You will want to write other routines for your new hash table, 275215976Sjmallett as well. 276215976Sjmallett 277232812Sjmallett You will want an initialization routine which calls the 278232812Sjmallett initialization routine of the hash table you are deriving from 279232812Sjmallett and initializes any other local fields. For the linker hash 280232812Sjmallett table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 281232812Sjmallett 282232812Sjmallett You will want a lookup routine which calls the lookup routine 283232812Sjmallett of the hash table you are deriving from and casts the result. 284232812Sjmallett The linker hash table uses <<bfd_link_hash_lookup>> in 285232812Sjmallett <<linker.c>> (this actually takes an additional argument which 286232812Sjmallett it uses to decide how to return the looked up value). 287232812Sjmallett 288232812Sjmallett You may want a traversal routine. This should just call the 289232812Sjmallett traversal routine of the hash table you are deriving from with 290232812Sjmallett appropriate casts. The linker hash table uses 291232812Sjmallett <<bfd_link_hash_traverse>> in <<linker.c>>. 292232812Sjmallett 293232812Sjmallett These routines may simply be defined as macros. For example, 294232812Sjmallett the a.out backend linker hash table, which is derived from the 295232812Sjmallett linker hash table, uses macros for the lookup and traversal 296215976Sjmallett routines. These are <<aout_link_hash_lookup>> and 297215976Sjmallett <<aout_link_hash_traverse>> in aoutx.h. 298215976Sjmallett*/ 299232812Sjmallett 300232812Sjmallett/* The default number of entries to use when creating a hash table. */ 301232812Sjmallett#define DEFAULT_SIZE 4051 302232812Sjmallett 303232812Sjmallett/* The following function returns a nearest prime number which is 304232812Sjmallett greater than N, and near a power of two. Copied from libiberty. 305232812Sjmallett Returns zero for ridiculously large N to signify an error. */ 306232812Sjmallett 307232812Sjmallettstatic unsigned long 308232812Sjmalletthigher_prime_number (unsigned long n) 309232812Sjmallett{ 310232812Sjmallett /* These are primes that are near, but slightly smaller than, a 311232812Sjmallett power of two. */ 312232812Sjmallett static const unsigned long primes[] = { 313232812Sjmallett (unsigned long) 127, 314232812Sjmallett (unsigned long) 2039, 315232812Sjmallett (unsigned long) 32749, 316232812Sjmallett (unsigned long) 65521, 317232812Sjmallett (unsigned long) 131071, 318215976Sjmallett (unsigned long) 262139, 319215976Sjmallett (unsigned long) 524287, 320215976Sjmallett (unsigned long) 1048573, 321232812Sjmallett (unsigned long) 2097143, 322232812Sjmallett (unsigned long) 4194301, 323232812Sjmallett (unsigned long) 8388593, 324232812Sjmallett (unsigned long) 16777213, 325232812Sjmallett (unsigned long) 33554393, 326232812Sjmallett (unsigned long) 67108859, 327232812Sjmallett (unsigned long) 134217689, 328232812Sjmallett (unsigned long) 268435399, 329232812Sjmallett (unsigned long) 536870909, 330232812Sjmallett (unsigned long) 1073741789, 331232812Sjmallett (unsigned long) 2147483647, 332232812Sjmallett /* 4294967291L */ 333232812Sjmallett ((unsigned long) 2147483647) + ((unsigned long) 2147483644), 334232812Sjmallett }; 335232812Sjmallett 336232812Sjmallett const unsigned long *low = &primes[0]; 337232812Sjmallett const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; 338232812Sjmallett 339232812Sjmallett while (low != high) 340215976Sjmallett { 341215976Sjmallett const unsigned long *mid = low + (high - low) / 2; 342215976Sjmallett if (n >= *mid) 343232812Sjmallett low = mid + 1; 344232812Sjmallett else 345232812Sjmallett high = mid; 346232812Sjmallett } 347232812Sjmallett 348232812Sjmallett if (n >= *low) 349232812Sjmallett return 0; 350232812Sjmallett 351232812Sjmallett return *low; 352232812Sjmallett} 353232812Sjmallett 354232812Sjmallettstatic size_t bfd_default_hash_table_size = DEFAULT_SIZE; 355232812Sjmallett 356232812Sjmallett/* Create a new hash table, given a number of entries. */ 357232812Sjmallett 358232812Sjmallettbfd_boolean 359232812Sjmallettbfd_hash_table_init_n (struct bfd_hash_table *table, 360232812Sjmallett struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 361232812Sjmallett struct bfd_hash_table *, 362215976Sjmallett const char *), 363215976Sjmallett unsigned int entsize, 364215976Sjmallett unsigned int size) 365232812Sjmallett{ 366232812Sjmallett unsigned int alloc; 367232812Sjmallett 368232812Sjmallett alloc = size * sizeof (struct bfd_hash_entry *); 369232812Sjmallett 370232812Sjmallett table->memory = (void *) objalloc_create (); 371232812Sjmallett if (table->memory == NULL) 372232812Sjmallett { 373232812Sjmallett bfd_set_error (bfd_error_no_memory); 374232812Sjmallett return FALSE; 375232812Sjmallett } 376232812Sjmallett table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc); 377232812Sjmallett if (table->table == NULL) 378232812Sjmallett { 379232812Sjmallett bfd_set_error (bfd_error_no_memory); 380232812Sjmallett return FALSE; 381232812Sjmallett } 382232812Sjmallett memset ((void *) table->table, 0, alloc); 383232812Sjmallett table->size = size; 384215976Sjmallett table->entsize = entsize; 385215976Sjmallett table->count = 0; 386215976Sjmallett table->frozen = 0; 387215976Sjmallett table->newfunc = newfunc; 388215976Sjmallett return TRUE; 389215976Sjmallett} 390215976Sjmallett 391215976Sjmallett/* Create a new hash table with the default number of entries. */ 392232812Sjmallett 393215976Sjmallettbfd_boolean 394232812Sjmallettbfd_hash_table_init (struct bfd_hash_table *table, 395232812Sjmallett struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 396215976Sjmallett struct bfd_hash_table *, 397215976Sjmallett const char *), 398215976Sjmallett unsigned int entsize) 399215976Sjmallett{ 400215976Sjmallett return bfd_hash_table_init_n (table, newfunc, entsize, 401215976Sjmallett bfd_default_hash_table_size); 402215976Sjmallett} 403215976Sjmallett 404215976Sjmallett/* Free a hash table. */ 405215976Sjmallett 406215976Sjmallettvoid 407215976Sjmallettbfd_hash_table_free (struct bfd_hash_table *table) 408215976Sjmallett{ 409215976Sjmallett objalloc_free (table->memory); 410215976Sjmallett table->memory = NULL; 411215976Sjmallett} 412215976Sjmallett 413215976Sjmallett/* Look up a string in a hash table. */ 414215976Sjmallett 415215976Sjmallettstruct bfd_hash_entry * 416215976Sjmallettbfd_hash_lookup (struct bfd_hash_table *table, 417215976Sjmallett const char *string, 418215976Sjmallett bfd_boolean create, 419232812Sjmallett bfd_boolean copy) 420215976Sjmallett{ 421215976Sjmallett const unsigned char *s; 422232812Sjmallett unsigned long hash; 423232812Sjmallett unsigned int c; 424232812Sjmallett struct bfd_hash_entry *hashp; 425215976Sjmallett unsigned int len; 426215976Sjmallett unsigned int index; 427215976Sjmallett 428215976Sjmallett hash = 0; 429215976Sjmallett len = 0; 430215976Sjmallett s = (const unsigned char *) string; 431215976Sjmallett while ((c = *s++) != '\0') 432215976Sjmallett { 433215976Sjmallett hash += c + (c << 17); 434215976Sjmallett hash ^= hash >> 2; 435215976Sjmallett } 436215976Sjmallett len = (s - (const unsigned char *) string) - 1; 437215976Sjmallett hash += len + (len << 17); 438215976Sjmallett hash ^= hash >> 2; 439232812Sjmallett 440215976Sjmallett index = hash % table->size; 441232812Sjmallett for (hashp = table->table[index]; 442232812Sjmallett hashp != NULL; 443215976Sjmallett hashp = hashp->next) 444215976Sjmallett { 445215976Sjmallett if (hashp->hash == hash 446215976Sjmallett && strcmp (hashp->string, string) == 0) 447215976Sjmallett return hashp; 448215976Sjmallett } 449215976Sjmallett 450215976Sjmallett if (! create) 451215976Sjmallett return NULL; 452215976Sjmallett 453215976Sjmallett hashp = (*table->newfunc) (NULL, table, string); 454215976Sjmallett if (hashp == NULL) 455232812Sjmallett return NULL; 456215976Sjmallett if (copy) 457215976Sjmallett { 458232812Sjmallett char *new; 459232812Sjmallett 460232812Sjmallett new = objalloc_alloc ((struct objalloc *) table->memory, len + 1); 461215976Sjmallett if (!new) 462215976Sjmallett { 463215976Sjmallett bfd_set_error (bfd_error_no_memory); 464215976Sjmallett return NULL; 465215976Sjmallett } 466215976Sjmallett memcpy (new, string, len + 1); 467215976Sjmallett string = new; 468215976Sjmallett } 469215976Sjmallett hashp->string = string; 470215976Sjmallett hashp->hash = hash; 471215976Sjmallett hashp->next = table->table[index]; 472232812Sjmallett table->table[index] = hashp; 473215976Sjmallett table->count++; 474232812Sjmallett 475232812Sjmallett if (!table->frozen && table->count > table->size * 3 / 4) 476215976Sjmallett { 477215976Sjmallett unsigned long newsize = higher_prime_number (table->size); 478215976Sjmallett struct bfd_hash_entry **newtable; 479215976Sjmallett unsigned int hi; 480215976Sjmallett unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *); 481215976Sjmallett 482215976Sjmallett /* If we can't find a higher prime, or we can't possibly alloc 483215976Sjmallett that much memory, don't try to grow the table. */ 484215976Sjmallett if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize) 485215976Sjmallett { 486215976Sjmallett table->frozen = 1; 487215976Sjmallett return hashp; 488215976Sjmallett } 489215976Sjmallett 490215976Sjmallett newtable = ((struct bfd_hash_entry **) 491215976Sjmallett objalloc_alloc ((struct objalloc *) table->memory, alloc)); 492215976Sjmallett memset ((PTR) newtable, 0, alloc); 493232812Sjmallett 494215976Sjmallett for (hi = 0; hi < table->size; hi ++) 495215976Sjmallett while (table->table[hi]) 496232812Sjmallett { 497232812Sjmallett struct bfd_hash_entry *chain = table->table[hi]; 498232812Sjmallett struct bfd_hash_entry *chain_end = chain; 499215976Sjmallett int index; 500215976Sjmallett 501215976Sjmallett while (chain_end->next && chain_end->next->hash == chain->hash) 502215976Sjmallett chain_end = chain_end->next; 503215976Sjmallett 504215976Sjmallett table->table[hi] = chain_end->next; 505215976Sjmallett index = chain->hash % newsize; 506215976Sjmallett chain_end->next = newtable[index]; 507215976Sjmallett newtable[index] = chain; 508215976Sjmallett } 509215976Sjmallett table->table = newtable; 510215976Sjmallett table->size = newsize; 511215976Sjmallett } 512215976Sjmallett 513215976Sjmallett return hashp; 514215976Sjmallett} 515215976Sjmallett 516232812Sjmallett/* Replace an entry in a hash table. */ 517215976Sjmallett 518232812Sjmallettvoid 519232812Sjmallettbfd_hash_replace (struct bfd_hash_table *table, 520215976Sjmallett struct bfd_hash_entry *old, 521215976Sjmallett struct bfd_hash_entry *nw) 522215976Sjmallett{ 523215976Sjmallett unsigned int index; 524215976Sjmallett struct bfd_hash_entry **pph; 525215976Sjmallett 526215976Sjmallett index = old->hash % table->size; 527215976Sjmallett for (pph = &table->table[index]; 528215976Sjmallett (*pph) != NULL; 529215976Sjmallett pph = &(*pph)->next) 530215976Sjmallett { 531215976Sjmallett if (*pph == old) 532215976Sjmallett { 533215976Sjmallett *pph = nw; 534215976Sjmallett return; 535215976Sjmallett } 536215976Sjmallett } 537215976Sjmallett 538215976Sjmallett abort (); 539215976Sjmallett} 540215976Sjmallett 541215976Sjmallett/* Allocate space in a hash table. */ 542215976Sjmallett 543215976Sjmallettvoid * 544215976Sjmallettbfd_hash_allocate (struct bfd_hash_table *table, 545215976Sjmallett unsigned int size) 546215976Sjmallett{ 547215976Sjmallett void * ret; 548215976Sjmallett 549215976Sjmallett ret = objalloc_alloc ((struct objalloc *) table->memory, size); 550215976Sjmallett if (ret == NULL && size != 0) 551215976Sjmallett bfd_set_error (bfd_error_no_memory); 552215976Sjmallett return ret; 553215976Sjmallett} 554232812Sjmallett 555215976Sjmallett/* Base method for creating a new hash table entry. */ 556215976Sjmallett 557232812Sjmallettstruct bfd_hash_entry * 558232812Sjmallettbfd_hash_newfunc (struct bfd_hash_entry *entry, 559232812Sjmallett struct bfd_hash_table *table, 560215976Sjmallett const char *string ATTRIBUTE_UNUSED) 561215976Sjmallett{ 562215976Sjmallett if (entry == NULL) 563215976Sjmallett entry = bfd_hash_allocate (table, sizeof (* entry)); 564215976Sjmallett return entry; 565215976Sjmallett} 566215976Sjmallett 567215976Sjmallett/* Traverse a hash table. */ 568215976Sjmallett 569232812Sjmallettvoid 570215976Sjmallettbfd_hash_traverse (struct bfd_hash_table *table, 571232812Sjmallett bfd_boolean (*func) (struct bfd_hash_entry *, void *), 572232812Sjmallett void * info) 573215976Sjmallett{ 574215976Sjmallett unsigned int i; 575215976Sjmallett 576215976Sjmallett table->frozen = 1; 577215976Sjmallett for (i = 0; i < table->size; i++) 578215976Sjmallett { 579215976Sjmallett struct bfd_hash_entry *p; 580215976Sjmallett 581215976Sjmallett for (p = table->table[i]; p != NULL; p = p->next) 582215976Sjmallett if (! (*func) (p, info)) 583215976Sjmallett goto out; 584232812Sjmallett } 585215976Sjmallett out: 586215976Sjmallett table->frozen = 0; 587232812Sjmallett} 588232812Sjmallett 589232812Sjmallettvoid 590215976Sjmallettbfd_hash_set_default_size (bfd_size_type hash_size) 591215976Sjmallett{ 592215976Sjmallett /* Extend this prime list if you want more granularity of hash table size. */ 593215976Sjmallett static const bfd_size_type hash_size_primes[] = 594215976Sjmallett { 595215976Sjmallett 251, 509, 1021, 2039, 4051, 8599, 16699, 32749 596215976Sjmallett }; 597215976Sjmallett size_t index; 598215976Sjmallett 599215976Sjmallett /* Work out best prime number near the hash_size. */ 600215976Sjmallett for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index) 601215976Sjmallett if (hash_size <= hash_size_primes[index]) 602215976Sjmallett break; 603215976Sjmallett 604232812Sjmallett bfd_default_hash_table_size = hash_size_primes[index]; 605215976Sjmallett} 606232812Sjmallett 607232812Sjmallett/* A few different object file formats (a.out, COFF, ELF) use a string 608215976Sjmallett table. These functions support adding strings to a string table, 609215976Sjmallett returning the byte offset, and writing out the table. 610215976Sjmallett 611215976Sjmallett Possible improvements: 612215976Sjmallett + look for strings matching trailing substrings of other strings 613215976Sjmallett + better data structures? balanced trees? 614215976Sjmallett + look at reducing memory use elsewhere -- maybe if we didn't have 615215976Sjmallett to construct the entire symbol table at once, we could get by 616215976Sjmallett with smaller amounts of VM? (What effect does that have on the 617215976Sjmallett string table reductions?) */ 618215976Sjmallett 619215976Sjmallett/* An entry in the strtab hash table. */ 620215976Sjmallett 621215976Sjmallettstruct strtab_hash_entry 622215976Sjmallett{ 623215976Sjmallett struct bfd_hash_entry root; 624215976Sjmallett /* Index in string table. */ 625215976Sjmallett bfd_size_type index; 626215976Sjmallett /* Next string in strtab. */ 627232812Sjmallett struct strtab_hash_entry *next; 628232812Sjmallett}; 629215976Sjmallett 630215976Sjmallett/* The strtab hash table. */ 631215976Sjmallett 632215976Sjmallettstruct bfd_strtab_hash 633215976Sjmallett{ 634215976Sjmallett struct bfd_hash_table table; 635215976Sjmallett /* Size of strtab--also next available index. */ 636215976Sjmallett bfd_size_type size; 637215976Sjmallett /* First string in strtab. */ 638215976Sjmallett struct strtab_hash_entry *first; 639215976Sjmallett /* Last string in strtab. */ 640215976Sjmallett struct strtab_hash_entry *last; 641215976Sjmallett /* Whether to precede strings with a two byte length, as in the 642215976Sjmallett XCOFF .debug section. */ 643215976Sjmallett bfd_boolean xcoff; 644215976Sjmallett}; 645215976Sjmallett 646215976Sjmallett/* Routine to create an entry in a strtab. */ 647215976Sjmallett 648215976Sjmallettstatic struct bfd_hash_entry * 649232812Sjmallettstrtab_hash_newfunc (struct bfd_hash_entry *entry, 650215976Sjmallett struct bfd_hash_table *table, 651215976Sjmallett const char *string) 652232812Sjmallett{ 653232812Sjmallett struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 654232812Sjmallett 655215976Sjmallett /* Allocate the structure if it has not already been allocated by a 656215976Sjmallett subclass. */ 657215976Sjmallett if (ret == NULL) 658215976Sjmallett ret = bfd_hash_allocate (table, sizeof (* ret)); 659215976Sjmallett if (ret == NULL) 660215976Sjmallett return NULL; 661215976Sjmallett 662215976Sjmallett /* Call the allocation method of the superclass. */ 663215976Sjmallett ret = (struct strtab_hash_entry *) 664232812Sjmallett bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 665215976Sjmallett 666232812Sjmallett if (ret) 667232812Sjmallett { 668215976Sjmallett /* Initialize the local fields. */ 669215976Sjmallett ret->index = (bfd_size_type) -1; 670215976Sjmallett ret->next = NULL; 671215976Sjmallett } 672215976Sjmallett 673215976Sjmallett return (struct bfd_hash_entry *) ret; 674215976Sjmallett} 675215976Sjmallett 676215976Sjmallett/* Look up an entry in an strtab. */ 677215976Sjmallett 678215976Sjmallett#define strtab_hash_lookup(t, string, create, copy) \ 679215976Sjmallett ((struct strtab_hash_entry *) \ 680215976Sjmallett bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 681215976Sjmallett 682215976Sjmallett/* Create a new strtab. */ 683215976Sjmallett 684215976Sjmallettstruct bfd_strtab_hash * 685215976Sjmallett_bfd_stringtab_init (void) 686215976Sjmallett{ 687215976Sjmallett struct bfd_strtab_hash *table; 688232812Sjmallett bfd_size_type amt = sizeof (* table); 689232812Sjmallett 690215976Sjmallett table = bfd_malloc (amt); 691215976Sjmallett if (table == NULL) 692215976Sjmallett return NULL; 693215976Sjmallett 694215976Sjmallett if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 695215976Sjmallett sizeof (struct strtab_hash_entry))) 696215976Sjmallett { 697215976Sjmallett free (table); 698215976Sjmallett return NULL; 699215976Sjmallett } 700215976Sjmallett 701215976Sjmallett table->size = 0; 702215976Sjmallett table->first = NULL; 703215976Sjmallett table->last = NULL; 704215976Sjmallett table->xcoff = FALSE; 705215976Sjmallett 706215976Sjmallett return table; 707215976Sjmallett} 708215976Sjmallett 709215976Sjmallett/* Create a new strtab in which the strings are output in the format 710215976Sjmallett used in the XCOFF .debug section: a two byte length precedes each 711232812Sjmallett string. */ 712215976Sjmallett 713215976Sjmallettstruct bfd_strtab_hash * 714232812Sjmallett_bfd_xcoff_stringtab_init (void) 715232812Sjmallett{ 716232812Sjmallett struct bfd_strtab_hash *ret; 717215976Sjmallett 718215976Sjmallett ret = _bfd_stringtab_init (); 719215976Sjmallett if (ret != NULL) 720215976Sjmallett ret->xcoff = TRUE; 721215976Sjmallett return ret; 722215976Sjmallett} 723215976Sjmallett 724215976Sjmallett/* Free a strtab. */ 725215976Sjmallett 726232812Sjmallettvoid 727215976Sjmallett_bfd_stringtab_free (struct bfd_strtab_hash *table) 728232812Sjmallett{ 729232812Sjmallett bfd_hash_table_free (&table->table); 730215976Sjmallett free (table); 731215976Sjmallett} 732215976Sjmallett 733215976Sjmallett/* Get the index of a string in a strtab, adding it if it is not 734215976Sjmallett already present. If HASH is FALSE, we don't really use the hash 735215976Sjmallett table, and we don't eliminate duplicate strings. */ 736215976Sjmallett 737215976Sjmallettbfd_size_type 738215976Sjmallett_bfd_stringtab_add (struct bfd_strtab_hash *tab, 739215976Sjmallett const char *str, 740215976Sjmallett bfd_boolean hash, 741215976Sjmallett bfd_boolean copy) 742215976Sjmallett{ 743215976Sjmallett struct strtab_hash_entry *entry; 744215976Sjmallett 745215976Sjmallett if (hash) 746215976Sjmallett { 747215976Sjmallett entry = strtab_hash_lookup (tab, str, TRUE, copy); 748215976Sjmallett if (entry == NULL) 749215976Sjmallett return (bfd_size_type) -1; 750215976Sjmallett } 751215976Sjmallett else 752215976Sjmallett { 753215976Sjmallett entry = bfd_hash_allocate (&tab->table, sizeof (* entry)); 754215976Sjmallett if (entry == NULL) 755215976Sjmallett return (bfd_size_type) -1; 756215976Sjmallett if (! copy) 757215976Sjmallett entry->root.string = str; 758215976Sjmallett else 759215976Sjmallett { 760215976Sjmallett char *n; 761232812Sjmallett 762215976Sjmallett n = bfd_hash_allocate (&tab->table, strlen (str) + 1); 763215976Sjmallett if (n == NULL) 764232812Sjmallett return (bfd_size_type) -1; 765232812Sjmallett entry->root.string = n; 766232812Sjmallett } 767215976Sjmallett entry->index = (bfd_size_type) -1; 768215976Sjmallett entry->next = NULL; 769215976Sjmallett } 770215976Sjmallett 771215976Sjmallett if (entry->index == (bfd_size_type) -1) 772215976Sjmallett { 773215976Sjmallett entry->index = tab->size; 774215976Sjmallett tab->size += strlen (str) + 1; 775215976Sjmallett if (tab->xcoff) 776215976Sjmallett { 777215976Sjmallett entry->index += 2; 778215976Sjmallett tab->size += 2; 779215976Sjmallett } 780215976Sjmallett if (tab->first == NULL) 781215976Sjmallett tab->first = entry; 782215976Sjmallett else 783232812Sjmallett tab->last->next = entry; 784215976Sjmallett tab->last = entry; 785232812Sjmallett } 786232812Sjmallett 787215976Sjmallett return entry->index; 788215976Sjmallett} 789215976Sjmallett 790215976Sjmallett/* Get the number of bytes in a strtab. */ 791215976Sjmallett 792215976Sjmallettbfd_size_type 793215976Sjmallett_bfd_stringtab_size (struct bfd_strtab_hash *tab) 794215976Sjmallett{ 795215976Sjmallett return tab->size; 796215976Sjmallett} 797215976Sjmallett 798215976Sjmallett/* Write out a strtab. ABFD must already be at the right location in 799215976Sjmallett the file. */ 800215976Sjmallett 801215976Sjmallettbfd_boolean 802215976Sjmallett_bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 803215976Sjmallett{ 804215976Sjmallett bfd_boolean xcoff; 805215976Sjmallett struct strtab_hash_entry *entry; 806215976Sjmallett 807215976Sjmallett xcoff = tab->xcoff; 808232812Sjmallett 809215976Sjmallett for (entry = tab->first; entry != NULL; entry = entry->next) 810215976Sjmallett { 811232812Sjmallett const char *str; 812232812Sjmallett size_t len; 813232812Sjmallett 814215976Sjmallett str = entry->root.string; 815215976Sjmallett len = strlen (str) + 1; 816215976Sjmallett 817215976Sjmallett if (xcoff) 818215976Sjmallett { 819215976Sjmallett bfd_byte buf[2]; 820215976Sjmallett 821215976Sjmallett /* The output length includes the null byte. */ 822215976Sjmallett bfd_put_16 (abfd, (bfd_vma) len, buf); 823232812Sjmallett if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 824215976Sjmallett return FALSE; 825232812Sjmallett } 826232812Sjmallett 827215976Sjmallett if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 828215976Sjmallett return FALSE; 829215976Sjmallett } 830215976Sjmallett 831215976Sjmallett return TRUE; 832215976Sjmallett} 833215976Sjmallett