hash.c revision 60484
133965Sjdp/* hash.c -- hash table routines for BFD 260484Sobrien Copyright (C) 1993, 94, 95, 97, 1999 Free Software Foundation, Inc. 333965Sjdp Written by Steve Chamberlain <sac@cygnus.com> 433965Sjdp 533965SjdpThis file is part of BFD, the Binary File Descriptor library. 633965Sjdp 733965SjdpThis program is free software; you can redistribute it and/or modify 833965Sjdpit under the terms of the GNU General Public License as published by 933965Sjdpthe Free Software Foundation; either version 2 of the License, or 1033965Sjdp(at your option) any later version. 1133965Sjdp 1233965SjdpThis program is distributed in the hope that it will be useful, 1333965Sjdpbut WITHOUT ANY WARRANTY; without even the implied warranty of 1433965SjdpMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1533965SjdpGNU General Public License for more details. 1633965Sjdp 1733965SjdpYou should have received a copy of the GNU General Public License 1833965Sjdpalong with this program; if not, write to the Free Software 1933965SjdpFoundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 2033965Sjdp 2133965Sjdp#include "bfd.h" 2233965Sjdp#include "sysdep.h" 2333965Sjdp#include "libbfd.h" 2433965Sjdp#include "objalloc.h" 2533965Sjdp 2633965Sjdp/* 2733965SjdpSECTION 2833965Sjdp Hash Tables 2933965Sjdp 3033965Sjdp@cindex Hash tables 3133965Sjdp BFD provides a simple set of hash table functions. Routines 3233965Sjdp are provided to initialize a hash table, to free a hash table, 3333965Sjdp to look up a string in a hash table and optionally create an 3433965Sjdp entry for it, and to traverse a hash table. There is 3533965Sjdp currently no routine to delete an string from a hash table. 3633965Sjdp 3733965Sjdp The basic hash table does not permit any data to be stored 3833965Sjdp with a string. However, a hash table is designed to present a 3933965Sjdp base class from which other types of hash tables may be 4033965Sjdp derived. These derived types may store additional information 4133965Sjdp with the string. Hash tables were implemented in this way, 4233965Sjdp rather than simply providing a data pointer in a hash table 4333965Sjdp entry, because they were designed for use by the linker back 4433965Sjdp ends. The linker may create thousands of hash table entries, 4533965Sjdp and the overhead of allocating private data and storing and 4633965Sjdp following pointers becomes noticeable. 4733965Sjdp 4833965Sjdp The basic hash table code is in <<hash.c>>. 4933965Sjdp 5033965Sjdp@menu 5133965Sjdp@* Creating and Freeing a Hash Table:: 5233965Sjdp@* Looking Up or Entering a String:: 5333965Sjdp@* Traversing a Hash Table:: 5433965Sjdp@* Deriving a New Hash Table Type:: 5533965Sjdp@end menu 5633965Sjdp 5733965SjdpINODE 5833965SjdpCreating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 5933965SjdpSUBSECTION 6033965Sjdp Creating and freeing a hash table 6133965Sjdp 6233965Sjdp@findex bfd_hash_table_init 6333965Sjdp@findex bfd_hash_table_init_n 6433965Sjdp To create a hash table, create an instance of a <<struct 6533965Sjdp bfd_hash_table>> (defined in <<bfd.h>>) and call 6633965Sjdp <<bfd_hash_table_init>> (if you know approximately how many 6733965Sjdp entries you will need, the function <<bfd_hash_table_init_n>>, 6833965Sjdp which takes a @var{size} argument, may be used). 6933965Sjdp <<bfd_hash_table_init>> returns <<false>> if some sort of 7033965Sjdp error occurs. 7133965Sjdp 7233965Sjdp@findex bfd_hash_newfunc 7333965Sjdp The function <<bfd_hash_table_init>> take as an argument a 7433965Sjdp function to use to create new entries. For a basic hash 7533965Sjdp table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 7660484Sobrien a New Hash Table Type}, for why you would want to use a 7733965Sjdp different value for this argument. 7833965Sjdp 7933965Sjdp@findex bfd_hash_allocate 8033965Sjdp <<bfd_hash_table_init>> will create an objalloc which will be 8133965Sjdp used to allocate new entries. You may allocate memory on this 8233965Sjdp objalloc using <<bfd_hash_allocate>>. 8333965Sjdp 8433965Sjdp@findex bfd_hash_table_free 8533965Sjdp Use <<bfd_hash_table_free>> to free up all the memory that has 8633965Sjdp been allocated for a hash table. This will not free up the 8733965Sjdp <<struct bfd_hash_table>> itself, which you must provide. 8833965Sjdp 8933965SjdpINODE 9033965SjdpLooking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 9133965SjdpSUBSECTION 9233965Sjdp Looking up or entering a string 9333965Sjdp 9433965Sjdp@findex bfd_hash_lookup 9533965Sjdp The function <<bfd_hash_lookup>> is used both to look up a 9633965Sjdp string in the hash table and to create a new entry. 9733965Sjdp 9833965Sjdp If the @var{create} argument is <<false>>, <<bfd_hash_lookup>> 9933965Sjdp will look up a string. If the string is found, it will 10033965Sjdp returns a pointer to a <<struct bfd_hash_entry>>. If the 10133965Sjdp string is not found in the table <<bfd_hash_lookup>> will 10233965Sjdp return <<NULL>>. You should not modify any of the fields in 10333965Sjdp the returns <<struct bfd_hash_entry>>. 10433965Sjdp 10533965Sjdp If the @var{create} argument is <<true>>, the string will be 10633965Sjdp entered into the hash table if it is not already there. 10733965Sjdp Either way a pointer to a <<struct bfd_hash_entry>> will be 10833965Sjdp returned, either to the existing structure or to a newly 10933965Sjdp created one. In this case, a <<NULL>> return means that an 11033965Sjdp error occurred. 11133965Sjdp 11233965Sjdp If the @var{create} argument is <<true>>, and a new entry is 11333965Sjdp created, the @var{copy} argument is used to decide whether to 11433965Sjdp copy the string onto the hash table objalloc or not. If 11533965Sjdp @var{copy} is passed as <<false>>, you must be careful not to 11633965Sjdp deallocate or modify the string as long as the hash table 11733965Sjdp exists. 11833965Sjdp 11933965SjdpINODE 12033965SjdpTraversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 12133965SjdpSUBSECTION 12233965Sjdp Traversing a hash table 12333965Sjdp 12433965Sjdp@findex bfd_hash_traverse 12533965Sjdp The function <<bfd_hash_traverse>> may be used to traverse a 12633965Sjdp hash table, calling a function on each element. The traversal 12733965Sjdp is done in a random order. 12833965Sjdp 12933965Sjdp <<bfd_hash_traverse>> takes as arguments a function and a 13033965Sjdp generic <<void *>> pointer. The function is called with a 13133965Sjdp hash table entry (a <<struct bfd_hash_entry *>>) and the 13233965Sjdp generic pointer passed to <<bfd_hash_traverse>>. The function 13333965Sjdp must return a <<boolean>> value, which indicates whether to 13433965Sjdp continue traversing the hash table. If the function returns 13533965Sjdp <<false>>, <<bfd_hash_traverse>> will stop the traversal and 13633965Sjdp return immediately. 13733965Sjdp 13833965SjdpINODE 13933965SjdpDeriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 14033965SjdpSUBSECTION 14133965Sjdp Deriving a new hash table type 14233965Sjdp 14333965Sjdp Many uses of hash tables want to store additional information 14433965Sjdp which each entry in the hash table. Some also find it 14533965Sjdp convenient to store additional information with the hash table 14633965Sjdp itself. This may be done using a derived hash table. 14733965Sjdp 14833965Sjdp Since C is not an object oriented language, creating a derived 14933965Sjdp hash table requires sticking together some boilerplate 15033965Sjdp routines with a few differences specific to the type of hash 15133965Sjdp table you want to create. 15233965Sjdp 15333965Sjdp An example of a derived hash table is the linker hash table. 15433965Sjdp The structures for this are defined in <<bfdlink.h>>. The 15533965Sjdp functions are in <<linker.c>>. 15633965Sjdp 15733965Sjdp You may also derive a hash table from an already derived hash 15833965Sjdp table. For example, the a.out linker backend code uses a hash 15933965Sjdp table derived from the linker hash table. 16033965Sjdp 16133965Sjdp@menu 16233965Sjdp@* Define the Derived Structures:: 16333965Sjdp@* Write the Derived Creation Routine:: 16433965Sjdp@* Write Other Derived Routines:: 16533965Sjdp@end menu 16633965Sjdp 16733965SjdpINODE 16833965SjdpDefine the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 16933965SjdpSUBSUBSECTION 17033965Sjdp Define the derived structures 17133965Sjdp 17233965Sjdp You must define a structure for an entry in the hash table, 17333965Sjdp and a structure for the hash table itself. 17433965Sjdp 17533965Sjdp The first field in the structure for an entry in the hash 17633965Sjdp table must be of the type used for an entry in the hash table 17733965Sjdp you are deriving from. If you are deriving from a basic hash 17833965Sjdp table this is <<struct bfd_hash_entry>>, which is defined in 17933965Sjdp <<bfd.h>>. The first field in the structure for the hash 18033965Sjdp table itself must be of the type of the hash table you are 18133965Sjdp deriving from itself. If you are deriving from a basic hash 18233965Sjdp table, this is <<struct bfd_hash_table>>. 18333965Sjdp 18433965Sjdp For example, the linker hash table defines <<struct 18533965Sjdp bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 18633965Sjdp <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 18733965Sjdp the first field in <<struct bfd_link_hash_table>>, <<table>>, 18833965Sjdp is of type <<struct bfd_hash_table>>. 18933965Sjdp 19033965SjdpINODE 19133965SjdpWrite the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 19233965SjdpSUBSUBSECTION 19333965Sjdp Write the derived creation routine 19433965Sjdp 19533965Sjdp You must write a routine which will create and initialize an 19633965Sjdp entry in the hash table. This routine is passed as the 19733965Sjdp function argument to <<bfd_hash_table_init>>. 19833965Sjdp 19933965Sjdp In order to permit other hash tables to be derived from the 20033965Sjdp hash table you are creating, this routine must be written in a 20133965Sjdp standard way. 20233965Sjdp 20333965Sjdp The first argument to the creation routine is a pointer to a 20433965Sjdp hash table entry. This may be <<NULL>>, in which case the 20533965Sjdp routine should allocate the right amount of space. Otherwise 20633965Sjdp the space has already been allocated by a hash table type 20733965Sjdp derived from this one. 20833965Sjdp 20933965Sjdp After allocating space, the creation routine must call the 21033965Sjdp creation routine of the hash table type it is derived from, 21133965Sjdp passing in a pointer to the space it just allocated. This 21233965Sjdp will initialize any fields used by the base hash table. 21333965Sjdp 21433965Sjdp Finally the creation routine must initialize any local fields 21533965Sjdp for the new hash table type. 21633965Sjdp 21733965Sjdp Here is a boilerplate example of a creation routine. 21833965Sjdp @var{function_name} is the name of the routine. 21933965Sjdp @var{entry_type} is the type of an entry in the hash table you 22033965Sjdp are creating. @var{base_newfunc} is the name of the creation 22133965Sjdp routine of the hash table type your hash table is derived 22233965Sjdp from. 22333965Sjdp 22433965SjdpEXAMPLE 22533965Sjdp 22633965Sjdp.struct bfd_hash_entry * 22733965Sjdp.@var{function_name} (entry, table, string) 22833965Sjdp. struct bfd_hash_entry *entry; 22933965Sjdp. struct bfd_hash_table *table; 23033965Sjdp. const char *string; 23133965Sjdp.{ 23233965Sjdp. struct @var{entry_type} *ret = (@var{entry_type} *) entry; 23333965Sjdp. 23433965Sjdp. {* Allocate the structure if it has not already been allocated by a 23533965Sjdp. derived class. *} 23633965Sjdp. if (ret == (@var{entry_type} *) NULL) 23733965Sjdp. { 23833965Sjdp. ret = ((@var{entry_type} *) 23933965Sjdp. bfd_hash_allocate (table, sizeof (@var{entry_type}))); 24033965Sjdp. if (ret == (@var{entry_type} *) NULL) 24133965Sjdp. return NULL; 24233965Sjdp. } 24333965Sjdp. 24433965Sjdp. {* Call the allocation method of the base class. *} 24533965Sjdp. ret = ((@var{entry_type} *) 24633965Sjdp. @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 24733965Sjdp. 24833965Sjdp. {* Initialize the local fields here. *} 24933965Sjdp. 25033965Sjdp. return (struct bfd_hash_entry *) ret; 25133965Sjdp.} 25233965Sjdp 25333965SjdpDESCRIPTION 25433965Sjdp The creation routine for the linker hash table, which is in 25533965Sjdp <<linker.c>>, looks just like this example. 25633965Sjdp @var{function_name} is <<_bfd_link_hash_newfunc>>. 25733965Sjdp @var{entry_type} is <<struct bfd_link_hash_entry>>. 25833965Sjdp @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 25933965Sjdp routine for a basic hash table. 26033965Sjdp 26133965Sjdp <<_bfd_link_hash_newfunc>> also initializes the local fields 26233965Sjdp in a linker hash table entry: <<type>>, <<written>> and 26333965Sjdp <<next>>. 26433965Sjdp 26533965SjdpINODE 26633965SjdpWrite Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 26733965SjdpSUBSUBSECTION 26833965Sjdp Write other derived routines 26933965Sjdp 27033965Sjdp You will want to write other routines for your new hash table, 27133965Sjdp as well. 27233965Sjdp 27333965Sjdp You will want an initialization routine which calls the 27433965Sjdp initialization routine of the hash table you are deriving from 27533965Sjdp and initializes any other local fields. For the linker hash 27633965Sjdp table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 27733965Sjdp 27833965Sjdp You will want a lookup routine which calls the lookup routine 27933965Sjdp of the hash table you are deriving from and casts the result. 28033965Sjdp The linker hash table uses <<bfd_link_hash_lookup>> in 28133965Sjdp <<linker.c>> (this actually takes an additional argument which 28233965Sjdp it uses to decide how to return the looked up value). 28333965Sjdp 28433965Sjdp You may want a traversal routine. This should just call the 28533965Sjdp traversal routine of the hash table you are deriving from with 28633965Sjdp appropriate casts. The linker hash table uses 28733965Sjdp <<bfd_link_hash_traverse>> in <<linker.c>>. 28833965Sjdp 28933965Sjdp These routines may simply be defined as macros. For example, 29033965Sjdp the a.out backend linker hash table, which is derived from the 29133965Sjdp linker hash table, uses macros for the lookup and traversal 29233965Sjdp routines. These are <<aout_link_hash_lookup>> and 29333965Sjdp <<aout_link_hash_traverse>> in aoutx.h. 29433965Sjdp*/ 29533965Sjdp 29633965Sjdp/* The default number of entries to use when creating a hash table. */ 29733965Sjdp#define DEFAULT_SIZE (4051) 29833965Sjdp 29933965Sjdp/* Create a new hash table, given a number of entries. */ 30033965Sjdp 30133965Sjdpboolean 30233965Sjdpbfd_hash_table_init_n (table, newfunc, size) 30333965Sjdp struct bfd_hash_table *table; 30433965Sjdp struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, 30533965Sjdp struct bfd_hash_table *, 30633965Sjdp const char *)); 30733965Sjdp unsigned int size; 30833965Sjdp{ 30933965Sjdp unsigned int alloc; 31033965Sjdp 31133965Sjdp alloc = size * sizeof (struct bfd_hash_entry *); 31233965Sjdp 31333965Sjdp table->memory = (PTR) objalloc_create (); 31433965Sjdp if (table->memory == NULL) 31533965Sjdp { 31633965Sjdp bfd_set_error (bfd_error_no_memory); 31733965Sjdp return false; 31833965Sjdp } 31933965Sjdp table->table = ((struct bfd_hash_entry **) 32033965Sjdp objalloc_alloc ((struct objalloc *) table->memory, alloc)); 32133965Sjdp if (table->table == NULL) 32233965Sjdp { 32333965Sjdp bfd_set_error (bfd_error_no_memory); 32433965Sjdp return false; 32533965Sjdp } 32633965Sjdp memset ((PTR) table->table, 0, alloc); 32733965Sjdp table->size = size; 32833965Sjdp table->newfunc = newfunc; 32933965Sjdp return true; 33033965Sjdp} 33133965Sjdp 33233965Sjdp/* Create a new hash table with the default number of entries. */ 33333965Sjdp 33433965Sjdpboolean 33533965Sjdpbfd_hash_table_init (table, newfunc) 33633965Sjdp struct bfd_hash_table *table; 33733965Sjdp struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, 33833965Sjdp struct bfd_hash_table *, 33933965Sjdp const char *)); 34033965Sjdp{ 34133965Sjdp return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE); 34233965Sjdp} 34333965Sjdp 34433965Sjdp/* Free a hash table. */ 34533965Sjdp 34633965Sjdpvoid 34733965Sjdpbfd_hash_table_free (table) 34833965Sjdp struct bfd_hash_table *table; 34933965Sjdp{ 35033965Sjdp objalloc_free ((struct objalloc *) table->memory); 35133965Sjdp table->memory = NULL; 35233965Sjdp} 35333965Sjdp 35433965Sjdp/* Look up a string in a hash table. */ 35533965Sjdp 35633965Sjdpstruct bfd_hash_entry * 35733965Sjdpbfd_hash_lookup (table, string, create, copy) 35833965Sjdp struct bfd_hash_table *table; 35933965Sjdp const char *string; 36033965Sjdp boolean create; 36133965Sjdp boolean copy; 36233965Sjdp{ 36333965Sjdp register const unsigned char *s; 36433965Sjdp register unsigned long hash; 36533965Sjdp register unsigned int c; 36633965Sjdp struct bfd_hash_entry *hashp; 36733965Sjdp unsigned int len; 36833965Sjdp unsigned int index; 36933965Sjdp 37033965Sjdp hash = 0; 37133965Sjdp len = 0; 37233965Sjdp s = (const unsigned char *) string; 37333965Sjdp while ((c = *s++) != '\0') 37433965Sjdp { 37533965Sjdp hash += c + (c << 17); 37633965Sjdp hash ^= hash >> 2; 37733965Sjdp ++len; 37833965Sjdp } 37933965Sjdp hash += len + (len << 17); 38033965Sjdp hash ^= hash >> 2; 38133965Sjdp 38233965Sjdp index = hash % table->size; 38333965Sjdp for (hashp = table->table[index]; 38433965Sjdp hashp != (struct bfd_hash_entry *) NULL; 38533965Sjdp hashp = hashp->next) 38633965Sjdp { 38733965Sjdp if (hashp->hash == hash 38833965Sjdp && strcmp (hashp->string, string) == 0) 38933965Sjdp return hashp; 39033965Sjdp } 39133965Sjdp 39233965Sjdp if (! create) 39333965Sjdp return (struct bfd_hash_entry *) NULL; 39433965Sjdp 39533965Sjdp hashp = (*table->newfunc) ((struct bfd_hash_entry *) NULL, table, string); 39633965Sjdp if (hashp == (struct bfd_hash_entry *) NULL) 39733965Sjdp return (struct bfd_hash_entry *) NULL; 39833965Sjdp if (copy) 39933965Sjdp { 40033965Sjdp char *new; 40133965Sjdp 40233965Sjdp new = (char *) objalloc_alloc ((struct objalloc *) table->memory, 40333965Sjdp len + 1); 40433965Sjdp if (!new) 40533965Sjdp { 40633965Sjdp bfd_set_error (bfd_error_no_memory); 40733965Sjdp return (struct bfd_hash_entry *) NULL; 40833965Sjdp } 40933965Sjdp strcpy (new, string); 41033965Sjdp string = new; 41133965Sjdp } 41233965Sjdp hashp->string = string; 41333965Sjdp hashp->hash = hash; 41433965Sjdp hashp->next = table->table[index]; 41533965Sjdp table->table[index] = hashp; 41633965Sjdp 41733965Sjdp return hashp; 41833965Sjdp} 41933965Sjdp 42033965Sjdp/* Replace an entry in a hash table. */ 42133965Sjdp 42233965Sjdpvoid 42333965Sjdpbfd_hash_replace (table, old, nw) 42433965Sjdp struct bfd_hash_table *table; 42533965Sjdp struct bfd_hash_entry *old; 42633965Sjdp struct bfd_hash_entry *nw; 42733965Sjdp{ 42833965Sjdp unsigned int index; 42933965Sjdp struct bfd_hash_entry **pph; 43033965Sjdp 43133965Sjdp index = old->hash % table->size; 43233965Sjdp for (pph = &table->table[index]; 43333965Sjdp (*pph) != (struct bfd_hash_entry *) NULL; 43433965Sjdp pph = &(*pph)->next) 43533965Sjdp { 43633965Sjdp if (*pph == old) 43733965Sjdp { 43833965Sjdp *pph = nw; 43933965Sjdp return; 44033965Sjdp } 44133965Sjdp } 44233965Sjdp 44333965Sjdp abort (); 44433965Sjdp} 44533965Sjdp 44633965Sjdp/* Base method for creating a new hash table entry. */ 44733965Sjdp 44833965Sjdp/*ARGSUSED*/ 44933965Sjdpstruct bfd_hash_entry * 45033965Sjdpbfd_hash_newfunc (entry, table, string) 45133965Sjdp struct bfd_hash_entry *entry; 45233965Sjdp struct bfd_hash_table *table; 45360484Sobrien const char *string ATTRIBUTE_UNUSED; 45433965Sjdp{ 45533965Sjdp if (entry == (struct bfd_hash_entry *) NULL) 45633965Sjdp entry = ((struct bfd_hash_entry *) 45733965Sjdp bfd_hash_allocate (table, sizeof (struct bfd_hash_entry))); 45833965Sjdp return entry; 45933965Sjdp} 46033965Sjdp 46133965Sjdp/* Allocate space in a hash table. */ 46233965Sjdp 46333965SjdpPTR 46433965Sjdpbfd_hash_allocate (table, size) 46533965Sjdp struct bfd_hash_table *table; 46633965Sjdp unsigned int size; 46733965Sjdp{ 46833965Sjdp PTR ret; 46933965Sjdp 47033965Sjdp ret = objalloc_alloc ((struct objalloc *) table->memory, size); 47133965Sjdp if (ret == NULL && size != 0) 47233965Sjdp bfd_set_error (bfd_error_no_memory); 47333965Sjdp return ret; 47433965Sjdp} 47533965Sjdp 47633965Sjdp/* Traverse a hash table. */ 47733965Sjdp 47833965Sjdpvoid 47933965Sjdpbfd_hash_traverse (table, func, info) 48033965Sjdp struct bfd_hash_table *table; 48133965Sjdp boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR)); 48233965Sjdp PTR info; 48333965Sjdp{ 48433965Sjdp unsigned int i; 48533965Sjdp 48633965Sjdp for (i = 0; i < table->size; i++) 48733965Sjdp { 48833965Sjdp struct bfd_hash_entry *p; 48933965Sjdp 49033965Sjdp for (p = table->table[i]; p != NULL; p = p->next) 49133965Sjdp { 49233965Sjdp if (! (*func) (p, info)) 49333965Sjdp return; 49433965Sjdp } 49533965Sjdp } 49633965Sjdp} 49733965Sjdp 49833965Sjdp/* A few different object file formats (a.out, COFF, ELF) use a string 49933965Sjdp table. These functions support adding strings to a string table, 50033965Sjdp returning the byte offset, and writing out the table. 50133965Sjdp 50233965Sjdp Possible improvements: 50333965Sjdp + look for strings matching trailing substrings of other strings 50433965Sjdp + better data structures? balanced trees? 50533965Sjdp + look at reducing memory use elsewhere -- maybe if we didn't have 50633965Sjdp to construct the entire symbol table at once, we could get by 50733965Sjdp with smaller amounts of VM? (What effect does that have on the 50833965Sjdp string table reductions?) */ 50933965Sjdp 51033965Sjdp/* An entry in the strtab hash table. */ 51133965Sjdp 51233965Sjdpstruct strtab_hash_entry 51333965Sjdp{ 51433965Sjdp struct bfd_hash_entry root; 51533965Sjdp /* Index in string table. */ 51633965Sjdp bfd_size_type index; 51733965Sjdp /* Next string in strtab. */ 51833965Sjdp struct strtab_hash_entry *next; 51933965Sjdp}; 52033965Sjdp 52133965Sjdp/* The strtab hash table. */ 52233965Sjdp 52333965Sjdpstruct bfd_strtab_hash 52433965Sjdp{ 52533965Sjdp struct bfd_hash_table table; 52633965Sjdp /* Size of strtab--also next available index. */ 52733965Sjdp bfd_size_type size; 52833965Sjdp /* First string in strtab. */ 52933965Sjdp struct strtab_hash_entry *first; 53033965Sjdp /* Last string in strtab. */ 53133965Sjdp struct strtab_hash_entry *last; 53233965Sjdp /* Whether to precede strings with a two byte length, as in the 53333965Sjdp XCOFF .debug section. */ 53433965Sjdp boolean xcoff; 53533965Sjdp}; 53633965Sjdp 53733965Sjdpstatic struct bfd_hash_entry *strtab_hash_newfunc 53833965Sjdp PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *)); 53933965Sjdp 54033965Sjdp/* Routine to create an entry in a strtab. */ 54133965Sjdp 54233965Sjdpstatic struct bfd_hash_entry * 54333965Sjdpstrtab_hash_newfunc (entry, table, string) 54433965Sjdp struct bfd_hash_entry *entry; 54533965Sjdp struct bfd_hash_table *table; 54633965Sjdp const char *string; 54733965Sjdp{ 54833965Sjdp struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 54933965Sjdp 55033965Sjdp /* Allocate the structure if it has not already been allocated by a 55133965Sjdp subclass. */ 55233965Sjdp if (ret == (struct strtab_hash_entry *) NULL) 55333965Sjdp ret = ((struct strtab_hash_entry *) 55433965Sjdp bfd_hash_allocate (table, sizeof (struct strtab_hash_entry))); 55533965Sjdp if (ret == (struct strtab_hash_entry *) NULL) 55633965Sjdp return NULL; 55733965Sjdp 55833965Sjdp /* Call the allocation method of the superclass. */ 55933965Sjdp ret = ((struct strtab_hash_entry *) 56033965Sjdp bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string)); 56133965Sjdp 56233965Sjdp if (ret) 56333965Sjdp { 56433965Sjdp /* Initialize the local fields. */ 56533965Sjdp ret->index = (bfd_size_type) -1; 56633965Sjdp ret->next = NULL; 56733965Sjdp } 56833965Sjdp 56933965Sjdp return (struct bfd_hash_entry *) ret; 57033965Sjdp} 57133965Sjdp 57233965Sjdp/* Look up an entry in an strtab. */ 57333965Sjdp 57433965Sjdp#define strtab_hash_lookup(t, string, create, copy) \ 57533965Sjdp ((struct strtab_hash_entry *) \ 57633965Sjdp bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 57733965Sjdp 57833965Sjdp/* Create a new strtab. */ 57933965Sjdp 58033965Sjdpstruct bfd_strtab_hash * 58133965Sjdp_bfd_stringtab_init () 58233965Sjdp{ 58333965Sjdp struct bfd_strtab_hash *table; 58433965Sjdp 58533965Sjdp table = ((struct bfd_strtab_hash *) 58633965Sjdp bfd_malloc (sizeof (struct bfd_strtab_hash))); 58733965Sjdp if (table == NULL) 58833965Sjdp return NULL; 58933965Sjdp 59033965Sjdp if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc)) 59133965Sjdp { 59233965Sjdp free (table); 59333965Sjdp return NULL; 59433965Sjdp } 59533965Sjdp 59633965Sjdp table->size = 0; 59733965Sjdp table->first = NULL; 59833965Sjdp table->last = NULL; 59933965Sjdp table->xcoff = false; 60033965Sjdp 60133965Sjdp return table; 60233965Sjdp} 60333965Sjdp 60433965Sjdp/* Create a new strtab in which the strings are output in the format 60533965Sjdp used in the XCOFF .debug section: a two byte length precedes each 60633965Sjdp string. */ 60733965Sjdp 60833965Sjdpstruct bfd_strtab_hash * 60933965Sjdp_bfd_xcoff_stringtab_init () 61033965Sjdp{ 61133965Sjdp struct bfd_strtab_hash *ret; 61233965Sjdp 61333965Sjdp ret = _bfd_stringtab_init (); 61433965Sjdp if (ret != NULL) 61533965Sjdp ret->xcoff = true; 61633965Sjdp return ret; 61733965Sjdp} 61833965Sjdp 61933965Sjdp/* Free a strtab. */ 62033965Sjdp 62133965Sjdpvoid 62233965Sjdp_bfd_stringtab_free (table) 62333965Sjdp struct bfd_strtab_hash *table; 62433965Sjdp{ 62533965Sjdp bfd_hash_table_free (&table->table); 62633965Sjdp free (table); 62733965Sjdp} 62833965Sjdp 62933965Sjdp/* Get the index of a string in a strtab, adding it if it is not 63033965Sjdp already present. If HASH is false, we don't really use the hash 63133965Sjdp table, and we don't eliminate duplicate strings. */ 63233965Sjdp 63333965Sjdpbfd_size_type 63433965Sjdp_bfd_stringtab_add (tab, str, hash, copy) 63533965Sjdp struct bfd_strtab_hash *tab; 63633965Sjdp const char *str; 63733965Sjdp boolean hash; 63833965Sjdp boolean copy; 63933965Sjdp{ 64033965Sjdp register struct strtab_hash_entry *entry; 64133965Sjdp 64233965Sjdp if (hash) 64333965Sjdp { 64433965Sjdp entry = strtab_hash_lookup (tab, str, true, copy); 64533965Sjdp if (entry == NULL) 64633965Sjdp return (bfd_size_type) -1; 64733965Sjdp } 64833965Sjdp else 64933965Sjdp { 65033965Sjdp entry = ((struct strtab_hash_entry *) 65133965Sjdp bfd_hash_allocate (&tab->table, 65233965Sjdp sizeof (struct strtab_hash_entry))); 65333965Sjdp if (entry == NULL) 65433965Sjdp return (bfd_size_type) -1; 65533965Sjdp if (! copy) 65633965Sjdp entry->root.string = str; 65733965Sjdp else 65833965Sjdp { 65933965Sjdp char *n; 66033965Sjdp 66133965Sjdp n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); 66233965Sjdp if (n == NULL) 66333965Sjdp return (bfd_size_type) -1; 66433965Sjdp entry->root.string = n; 66533965Sjdp } 66633965Sjdp entry->index = (bfd_size_type) -1; 66733965Sjdp entry->next = NULL; 66833965Sjdp } 66933965Sjdp 67033965Sjdp if (entry->index == (bfd_size_type) -1) 67133965Sjdp { 67233965Sjdp entry->index = tab->size; 67333965Sjdp tab->size += strlen (str) + 1; 67433965Sjdp if (tab->xcoff) 67533965Sjdp { 67633965Sjdp entry->index += 2; 67733965Sjdp tab->size += 2; 67833965Sjdp } 67933965Sjdp if (tab->first == NULL) 68033965Sjdp tab->first = entry; 68133965Sjdp else 68233965Sjdp tab->last->next = entry; 68333965Sjdp tab->last = entry; 68433965Sjdp } 68533965Sjdp 68633965Sjdp return entry->index; 68733965Sjdp} 68833965Sjdp 68933965Sjdp/* Get the number of bytes in a strtab. */ 69033965Sjdp 69133965Sjdpbfd_size_type 69233965Sjdp_bfd_stringtab_size (tab) 69333965Sjdp struct bfd_strtab_hash *tab; 69433965Sjdp{ 69533965Sjdp return tab->size; 69633965Sjdp} 69733965Sjdp 69833965Sjdp/* Write out a strtab. ABFD must already be at the right location in 69933965Sjdp the file. */ 70033965Sjdp 70133965Sjdpboolean 70233965Sjdp_bfd_stringtab_emit (abfd, tab) 70333965Sjdp register bfd *abfd; 70433965Sjdp struct bfd_strtab_hash *tab; 70533965Sjdp{ 70633965Sjdp register boolean xcoff; 70733965Sjdp register struct strtab_hash_entry *entry; 70833965Sjdp 70933965Sjdp xcoff = tab->xcoff; 71033965Sjdp 71133965Sjdp for (entry = tab->first; entry != NULL; entry = entry->next) 71233965Sjdp { 71333965Sjdp register const char *str; 71433965Sjdp register size_t len; 71533965Sjdp 71633965Sjdp str = entry->root.string; 71733965Sjdp len = strlen (str) + 1; 71833965Sjdp 71933965Sjdp if (xcoff) 72033965Sjdp { 72133965Sjdp bfd_byte buf[2]; 72233965Sjdp 72333965Sjdp /* The output length includes the null byte. */ 72433965Sjdp bfd_put_16 (abfd, len, buf); 72533965Sjdp if (bfd_write ((PTR) buf, 1, 2, abfd) != 2) 72633965Sjdp return false; 72733965Sjdp } 72833965Sjdp 72933965Sjdp if (bfd_write ((PTR) str, 1, len, abfd) != len) 73033965Sjdp return false; 73133965Sjdp } 73233965Sjdp 73333965Sjdp return true; 73433965Sjdp} 735