15796c8dcSSimon Schubert /* hash.c -- hash table routines for BFD 25796c8dcSSimon Schubert Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005, 3*a45ae5f8SJohn Marino 2006, 2007, 2009, 2010, 2011 Free Software Foundation, Inc. 45796c8dcSSimon Schubert Written by Steve Chamberlain <sac@cygnus.com> 55796c8dcSSimon Schubert 65796c8dcSSimon Schubert This file is part of BFD, the Binary File Descriptor library. 75796c8dcSSimon Schubert 85796c8dcSSimon Schubert This program is free software; you can redistribute it and/or modify 95796c8dcSSimon Schubert it under the terms of the GNU General Public License as published by 105796c8dcSSimon Schubert the Free Software Foundation; either version 3 of the License, or 115796c8dcSSimon Schubert (at your option) any later version. 125796c8dcSSimon Schubert 135796c8dcSSimon Schubert This program is distributed in the hope that it will be useful, 145796c8dcSSimon Schubert but WITHOUT ANY WARRANTY; without even the implied warranty of 155796c8dcSSimon Schubert MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 165796c8dcSSimon Schubert GNU General Public License for more details. 175796c8dcSSimon Schubert 185796c8dcSSimon Schubert You should have received a copy of the GNU General Public License 195796c8dcSSimon Schubert along with this program; if not, write to the Free Software 205796c8dcSSimon Schubert Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 215796c8dcSSimon Schubert MA 02110-1301, USA. */ 225796c8dcSSimon Schubert 235796c8dcSSimon Schubert #include "sysdep.h" 245796c8dcSSimon Schubert #include "bfd.h" 255796c8dcSSimon Schubert #include "libbfd.h" 265796c8dcSSimon Schubert #include "objalloc.h" 275796c8dcSSimon Schubert #include "libiberty.h" 285796c8dcSSimon Schubert 295796c8dcSSimon Schubert /* 305796c8dcSSimon Schubert SECTION 315796c8dcSSimon Schubert Hash Tables 325796c8dcSSimon Schubert 335796c8dcSSimon Schubert @cindex Hash tables 345796c8dcSSimon Schubert BFD provides a simple set of hash table functions. Routines 355796c8dcSSimon Schubert are provided to initialize a hash table, to free a hash table, 365796c8dcSSimon Schubert to look up a string in a hash table and optionally create an 375796c8dcSSimon Schubert entry for it, and to traverse a hash table. There is 385796c8dcSSimon Schubert currently no routine to delete an string from a hash table. 395796c8dcSSimon Schubert 405796c8dcSSimon Schubert The basic hash table does not permit any data to be stored 415796c8dcSSimon Schubert with a string. However, a hash table is designed to present a 425796c8dcSSimon Schubert base class from which other types of hash tables may be 435796c8dcSSimon Schubert derived. These derived types may store additional information 445796c8dcSSimon Schubert with the string. Hash tables were implemented in this way, 455796c8dcSSimon Schubert rather than simply providing a data pointer in a hash table 465796c8dcSSimon Schubert entry, because they were designed for use by the linker back 475796c8dcSSimon Schubert ends. The linker may create thousands of hash table entries, 485796c8dcSSimon Schubert and the overhead of allocating private data and storing and 495796c8dcSSimon Schubert following pointers becomes noticeable. 505796c8dcSSimon Schubert 515796c8dcSSimon Schubert The basic hash table code is in <<hash.c>>. 525796c8dcSSimon Schubert 535796c8dcSSimon Schubert @menu 545796c8dcSSimon Schubert @* Creating and Freeing a Hash Table:: 555796c8dcSSimon Schubert @* Looking Up or Entering a String:: 565796c8dcSSimon Schubert @* Traversing a Hash Table:: 575796c8dcSSimon Schubert @* Deriving a New Hash Table Type:: 585796c8dcSSimon Schubert @end menu 595796c8dcSSimon Schubert 605796c8dcSSimon Schubert INODE 615796c8dcSSimon Schubert Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 625796c8dcSSimon Schubert SUBSECTION 635796c8dcSSimon Schubert Creating and freeing a hash table 645796c8dcSSimon Schubert 655796c8dcSSimon Schubert @findex bfd_hash_table_init 665796c8dcSSimon Schubert @findex bfd_hash_table_init_n 675796c8dcSSimon Schubert To create a hash table, create an instance of a <<struct 685796c8dcSSimon Schubert bfd_hash_table>> (defined in <<bfd.h>>) and call 695796c8dcSSimon Schubert <<bfd_hash_table_init>> (if you know approximately how many 705796c8dcSSimon Schubert entries you will need, the function <<bfd_hash_table_init_n>>, 715796c8dcSSimon Schubert which takes a @var{size} argument, may be used). 725796c8dcSSimon Schubert <<bfd_hash_table_init>> returns <<FALSE>> if some sort of 735796c8dcSSimon Schubert error occurs. 745796c8dcSSimon Schubert 755796c8dcSSimon Schubert @findex bfd_hash_newfunc 765796c8dcSSimon Schubert The function <<bfd_hash_table_init>> take as an argument a 775796c8dcSSimon Schubert function to use to create new entries. For a basic hash 785796c8dcSSimon Schubert table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 795796c8dcSSimon Schubert a New Hash Table Type}, for why you would want to use a 805796c8dcSSimon Schubert different value for this argument. 815796c8dcSSimon Schubert 825796c8dcSSimon Schubert @findex bfd_hash_allocate 835796c8dcSSimon Schubert <<bfd_hash_table_init>> will create an objalloc which will be 845796c8dcSSimon Schubert used to allocate new entries. You may allocate memory on this 855796c8dcSSimon Schubert objalloc using <<bfd_hash_allocate>>. 865796c8dcSSimon Schubert 875796c8dcSSimon Schubert @findex bfd_hash_table_free 885796c8dcSSimon Schubert Use <<bfd_hash_table_free>> to free up all the memory that has 895796c8dcSSimon Schubert been allocated for a hash table. This will not free up the 905796c8dcSSimon Schubert <<struct bfd_hash_table>> itself, which you must provide. 915796c8dcSSimon Schubert 925796c8dcSSimon Schubert @findex bfd_hash_set_default_size 935796c8dcSSimon Schubert Use <<bfd_hash_set_default_size>> to set the default size of 945796c8dcSSimon Schubert hash table to use. 955796c8dcSSimon Schubert 965796c8dcSSimon Schubert INODE 975796c8dcSSimon Schubert Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 985796c8dcSSimon Schubert SUBSECTION 995796c8dcSSimon Schubert Looking up or entering a string 1005796c8dcSSimon Schubert 1015796c8dcSSimon Schubert @findex bfd_hash_lookup 1025796c8dcSSimon Schubert The function <<bfd_hash_lookup>> is used both to look up a 1035796c8dcSSimon Schubert string in the hash table and to create a new entry. 1045796c8dcSSimon Schubert 1055796c8dcSSimon Schubert If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>> 1065796c8dcSSimon Schubert will look up a string. If the string is found, it will 1075796c8dcSSimon Schubert returns a pointer to a <<struct bfd_hash_entry>>. If the 1085796c8dcSSimon Schubert string is not found in the table <<bfd_hash_lookup>> will 1095796c8dcSSimon Schubert return <<NULL>>. You should not modify any of the fields in 1105796c8dcSSimon Schubert the returns <<struct bfd_hash_entry>>. 1115796c8dcSSimon Schubert 1125796c8dcSSimon Schubert If the @var{create} argument is <<TRUE>>, the string will be 1135796c8dcSSimon Schubert entered into the hash table if it is not already there. 1145796c8dcSSimon Schubert Either way a pointer to a <<struct bfd_hash_entry>> will be 1155796c8dcSSimon Schubert returned, either to the existing structure or to a newly 1165796c8dcSSimon Schubert created one. In this case, a <<NULL>> return means that an 1175796c8dcSSimon Schubert error occurred. 1185796c8dcSSimon Schubert 1195796c8dcSSimon Schubert If the @var{create} argument is <<TRUE>>, and a new entry is 1205796c8dcSSimon Schubert created, the @var{copy} argument is used to decide whether to 1215796c8dcSSimon Schubert copy the string onto the hash table objalloc or not. If 1225796c8dcSSimon Schubert @var{copy} is passed as <<FALSE>>, you must be careful not to 1235796c8dcSSimon Schubert deallocate or modify the string as long as the hash table 1245796c8dcSSimon Schubert exists. 1255796c8dcSSimon Schubert 1265796c8dcSSimon Schubert INODE 1275796c8dcSSimon Schubert Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 1285796c8dcSSimon Schubert SUBSECTION 1295796c8dcSSimon Schubert Traversing a hash table 1305796c8dcSSimon Schubert 1315796c8dcSSimon Schubert @findex bfd_hash_traverse 1325796c8dcSSimon Schubert The function <<bfd_hash_traverse>> may be used to traverse a 1335796c8dcSSimon Schubert hash table, calling a function on each element. The traversal 1345796c8dcSSimon Schubert is done in a random order. 1355796c8dcSSimon Schubert 1365796c8dcSSimon Schubert <<bfd_hash_traverse>> takes as arguments a function and a 1375796c8dcSSimon Schubert generic <<void *>> pointer. The function is called with a 1385796c8dcSSimon Schubert hash table entry (a <<struct bfd_hash_entry *>>) and the 1395796c8dcSSimon Schubert generic pointer passed to <<bfd_hash_traverse>>. The function 1405796c8dcSSimon Schubert must return a <<boolean>> value, which indicates whether to 1415796c8dcSSimon Schubert continue traversing the hash table. If the function returns 1425796c8dcSSimon Schubert <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and 1435796c8dcSSimon Schubert return immediately. 1445796c8dcSSimon Schubert 1455796c8dcSSimon Schubert INODE 1465796c8dcSSimon Schubert Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 1475796c8dcSSimon Schubert SUBSECTION 1485796c8dcSSimon Schubert Deriving a new hash table type 1495796c8dcSSimon Schubert 1505796c8dcSSimon Schubert Many uses of hash tables want to store additional information 1515796c8dcSSimon Schubert which each entry in the hash table. Some also find it 1525796c8dcSSimon Schubert convenient to store additional information with the hash table 1535796c8dcSSimon Schubert itself. This may be done using a derived hash table. 1545796c8dcSSimon Schubert 1555796c8dcSSimon Schubert Since C is not an object oriented language, creating a derived 1565796c8dcSSimon Schubert hash table requires sticking together some boilerplate 1575796c8dcSSimon Schubert routines with a few differences specific to the type of hash 1585796c8dcSSimon Schubert table you want to create. 1595796c8dcSSimon Schubert 1605796c8dcSSimon Schubert An example of a derived hash table is the linker hash table. 1615796c8dcSSimon Schubert The structures for this are defined in <<bfdlink.h>>. The 1625796c8dcSSimon Schubert functions are in <<linker.c>>. 1635796c8dcSSimon Schubert 1645796c8dcSSimon Schubert You may also derive a hash table from an already derived hash 1655796c8dcSSimon Schubert table. For example, the a.out linker backend code uses a hash 1665796c8dcSSimon Schubert table derived from the linker hash table. 1675796c8dcSSimon Schubert 1685796c8dcSSimon Schubert @menu 1695796c8dcSSimon Schubert @* Define the Derived Structures:: 1705796c8dcSSimon Schubert @* Write the Derived Creation Routine:: 1715796c8dcSSimon Schubert @* Write Other Derived Routines:: 1725796c8dcSSimon Schubert @end menu 1735796c8dcSSimon Schubert 1745796c8dcSSimon Schubert INODE 1755796c8dcSSimon Schubert Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 1765796c8dcSSimon Schubert SUBSUBSECTION 1775796c8dcSSimon Schubert Define the derived structures 1785796c8dcSSimon Schubert 1795796c8dcSSimon Schubert You must define a structure for an entry in the hash table, 1805796c8dcSSimon Schubert and a structure for the hash table itself. 1815796c8dcSSimon Schubert 1825796c8dcSSimon Schubert The first field in the structure for an entry in the hash 1835796c8dcSSimon Schubert table must be of the type used for an entry in the hash table 1845796c8dcSSimon Schubert you are deriving from. If you are deriving from a basic hash 1855796c8dcSSimon Schubert table this is <<struct bfd_hash_entry>>, which is defined in 1865796c8dcSSimon Schubert <<bfd.h>>. The first field in the structure for the hash 1875796c8dcSSimon Schubert table itself must be of the type of the hash table you are 1885796c8dcSSimon Schubert deriving from itself. If you are deriving from a basic hash 1895796c8dcSSimon Schubert table, this is <<struct bfd_hash_table>>. 1905796c8dcSSimon Schubert 1915796c8dcSSimon Schubert For example, the linker hash table defines <<struct 1925796c8dcSSimon Schubert bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 1935796c8dcSSimon Schubert <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 1945796c8dcSSimon Schubert the first field in <<struct bfd_link_hash_table>>, <<table>>, 1955796c8dcSSimon Schubert is of type <<struct bfd_hash_table>>. 1965796c8dcSSimon Schubert 1975796c8dcSSimon Schubert INODE 1985796c8dcSSimon Schubert Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 1995796c8dcSSimon Schubert SUBSUBSECTION 2005796c8dcSSimon Schubert Write the derived creation routine 2015796c8dcSSimon Schubert 2025796c8dcSSimon Schubert You must write a routine which will create and initialize an 2035796c8dcSSimon Schubert entry in the hash table. This routine is passed as the 2045796c8dcSSimon Schubert function argument to <<bfd_hash_table_init>>. 2055796c8dcSSimon Schubert 2065796c8dcSSimon Schubert In order to permit other hash tables to be derived from the 2075796c8dcSSimon Schubert hash table you are creating, this routine must be written in a 2085796c8dcSSimon Schubert standard way. 2095796c8dcSSimon Schubert 2105796c8dcSSimon Schubert The first argument to the creation routine is a pointer to a 2115796c8dcSSimon Schubert hash table entry. This may be <<NULL>>, in which case the 2125796c8dcSSimon Schubert routine should allocate the right amount of space. Otherwise 2135796c8dcSSimon Schubert the space has already been allocated by a hash table type 2145796c8dcSSimon Schubert derived from this one. 2155796c8dcSSimon Schubert 2165796c8dcSSimon Schubert After allocating space, the creation routine must call the 2175796c8dcSSimon Schubert creation routine of the hash table type it is derived from, 2185796c8dcSSimon Schubert passing in a pointer to the space it just allocated. This 2195796c8dcSSimon Schubert will initialize any fields used by the base hash table. 2205796c8dcSSimon Schubert 2215796c8dcSSimon Schubert Finally the creation routine must initialize any local fields 2225796c8dcSSimon Schubert for the new hash table type. 2235796c8dcSSimon Schubert 2245796c8dcSSimon Schubert Here is a boilerplate example of a creation routine. 2255796c8dcSSimon Schubert @var{function_name} is the name of the routine. 2265796c8dcSSimon Schubert @var{entry_type} is the type of an entry in the hash table you 2275796c8dcSSimon Schubert are creating. @var{base_newfunc} is the name of the creation 2285796c8dcSSimon Schubert routine of the hash table type your hash table is derived 2295796c8dcSSimon Schubert from. 2305796c8dcSSimon Schubert 2315796c8dcSSimon Schubert EXAMPLE 2325796c8dcSSimon Schubert 2335796c8dcSSimon Schubert .struct bfd_hash_entry * 2345796c8dcSSimon Schubert .@var{function_name} (struct bfd_hash_entry *entry, 2355796c8dcSSimon Schubert . struct bfd_hash_table *table, 2365796c8dcSSimon Schubert . const char *string) 2375796c8dcSSimon Schubert .{ 2385796c8dcSSimon Schubert . struct @var{entry_type} *ret = (@var{entry_type} *) entry; 2395796c8dcSSimon Schubert . 2405796c8dcSSimon Schubert . {* Allocate the structure if it has not already been allocated by a 2415796c8dcSSimon Schubert . derived class. *} 2425796c8dcSSimon Schubert . if (ret == NULL) 2435796c8dcSSimon Schubert . { 2445796c8dcSSimon Schubert . ret = bfd_hash_allocate (table, sizeof (* ret)); 2455796c8dcSSimon Schubert . if (ret == NULL) 2465796c8dcSSimon Schubert . return NULL; 2475796c8dcSSimon Schubert . } 2485796c8dcSSimon Schubert . 2495796c8dcSSimon Schubert . {* Call the allocation method of the base class. *} 2505796c8dcSSimon Schubert . ret = ((@var{entry_type} *) 2515796c8dcSSimon Schubert . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 2525796c8dcSSimon Schubert . 2535796c8dcSSimon Schubert . {* Initialize the local fields here. *} 2545796c8dcSSimon Schubert . 2555796c8dcSSimon Schubert . return (struct bfd_hash_entry *) ret; 2565796c8dcSSimon Schubert .} 2575796c8dcSSimon Schubert 2585796c8dcSSimon Schubert DESCRIPTION 2595796c8dcSSimon Schubert The creation routine for the linker hash table, which is in 2605796c8dcSSimon Schubert <<linker.c>>, looks just like this example. 2615796c8dcSSimon Schubert @var{function_name} is <<_bfd_link_hash_newfunc>>. 2625796c8dcSSimon Schubert @var{entry_type} is <<struct bfd_link_hash_entry>>. 2635796c8dcSSimon Schubert @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 2645796c8dcSSimon Schubert routine for a basic hash table. 2655796c8dcSSimon Schubert 2665796c8dcSSimon Schubert <<_bfd_link_hash_newfunc>> also initializes the local fields 2675796c8dcSSimon Schubert in a linker hash table entry: <<type>>, <<written>> and 2685796c8dcSSimon Schubert <<next>>. 2695796c8dcSSimon Schubert 2705796c8dcSSimon Schubert INODE 2715796c8dcSSimon Schubert Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 2725796c8dcSSimon Schubert SUBSUBSECTION 2735796c8dcSSimon Schubert Write other derived routines 2745796c8dcSSimon Schubert 2755796c8dcSSimon Schubert You will want to write other routines for your new hash table, 2765796c8dcSSimon Schubert as well. 2775796c8dcSSimon Schubert 2785796c8dcSSimon Schubert You will want an initialization routine which calls the 2795796c8dcSSimon Schubert initialization routine of the hash table you are deriving from 2805796c8dcSSimon Schubert and initializes any other local fields. For the linker hash 2815796c8dcSSimon Schubert table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 2825796c8dcSSimon Schubert 2835796c8dcSSimon Schubert You will want a lookup routine which calls the lookup routine 2845796c8dcSSimon Schubert of the hash table you are deriving from and casts the result. 2855796c8dcSSimon Schubert The linker hash table uses <<bfd_link_hash_lookup>> in 2865796c8dcSSimon Schubert <<linker.c>> (this actually takes an additional argument which 2875796c8dcSSimon Schubert it uses to decide how to return the looked up value). 2885796c8dcSSimon Schubert 2895796c8dcSSimon Schubert You may want a traversal routine. This should just call the 2905796c8dcSSimon Schubert traversal routine of the hash table you are deriving from with 2915796c8dcSSimon Schubert appropriate casts. The linker hash table uses 2925796c8dcSSimon Schubert <<bfd_link_hash_traverse>> in <<linker.c>>. 2935796c8dcSSimon Schubert 2945796c8dcSSimon Schubert These routines may simply be defined as macros. For example, 2955796c8dcSSimon Schubert the a.out backend linker hash table, which is derived from the 2965796c8dcSSimon Schubert linker hash table, uses macros for the lookup and traversal 2975796c8dcSSimon Schubert routines. These are <<aout_link_hash_lookup>> and 2985796c8dcSSimon Schubert <<aout_link_hash_traverse>> in aoutx.h. 2995796c8dcSSimon Schubert */ 3005796c8dcSSimon Schubert 3015796c8dcSSimon Schubert /* The default number of entries to use when creating a hash table. */ 3025796c8dcSSimon Schubert #define DEFAULT_SIZE 4051 3035796c8dcSSimon Schubert 3045796c8dcSSimon Schubert /* The following function returns a nearest prime number which is 3055796c8dcSSimon Schubert greater than N, and near a power of two. Copied from libiberty. 3065796c8dcSSimon Schubert Returns zero for ridiculously large N to signify an error. */ 3075796c8dcSSimon Schubert 3085796c8dcSSimon Schubert static unsigned long 3095796c8dcSSimon Schubert higher_prime_number (unsigned long n) 3105796c8dcSSimon Schubert { 3115796c8dcSSimon Schubert /* These are primes that are near, but slightly smaller than, a 3125796c8dcSSimon Schubert power of two. */ 313*a45ae5f8SJohn Marino static const unsigned long primes[] = 314*a45ae5f8SJohn Marino { 315*a45ae5f8SJohn Marino (unsigned long) 31, 316*a45ae5f8SJohn Marino (unsigned long) 61, 3175796c8dcSSimon Schubert (unsigned long) 127, 318*a45ae5f8SJohn Marino (unsigned long) 251, 319*a45ae5f8SJohn Marino (unsigned long) 509, 320*a45ae5f8SJohn Marino (unsigned long) 1021, 3215796c8dcSSimon Schubert (unsigned long) 2039, 322*a45ae5f8SJohn Marino (unsigned long) 4093, 323*a45ae5f8SJohn Marino (unsigned long) 8191, 324*a45ae5f8SJohn Marino (unsigned long) 16381, 3255796c8dcSSimon Schubert (unsigned long) 32749, 3265796c8dcSSimon Schubert (unsigned long) 65521, 3275796c8dcSSimon Schubert (unsigned long) 131071, 3285796c8dcSSimon Schubert (unsigned long) 262139, 3295796c8dcSSimon Schubert (unsigned long) 524287, 3305796c8dcSSimon Schubert (unsigned long) 1048573, 3315796c8dcSSimon Schubert (unsigned long) 2097143, 3325796c8dcSSimon Schubert (unsigned long) 4194301, 3335796c8dcSSimon Schubert (unsigned long) 8388593, 3345796c8dcSSimon Schubert (unsigned long) 16777213, 3355796c8dcSSimon Schubert (unsigned long) 33554393, 3365796c8dcSSimon Schubert (unsigned long) 67108859, 3375796c8dcSSimon Schubert (unsigned long) 134217689, 3385796c8dcSSimon Schubert (unsigned long) 268435399, 3395796c8dcSSimon Schubert (unsigned long) 536870909, 3405796c8dcSSimon Schubert (unsigned long) 1073741789, 3415796c8dcSSimon Schubert (unsigned long) 2147483647, 3425796c8dcSSimon Schubert /* 4294967291L */ 3435796c8dcSSimon Schubert ((unsigned long) 2147483647) + ((unsigned long) 2147483644), 3445796c8dcSSimon Schubert }; 3455796c8dcSSimon Schubert 3465796c8dcSSimon Schubert const unsigned long *low = &primes[0]; 3475796c8dcSSimon Schubert const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; 3485796c8dcSSimon Schubert 3495796c8dcSSimon Schubert while (low != high) 3505796c8dcSSimon Schubert { 3515796c8dcSSimon Schubert const unsigned long *mid = low + (high - low) / 2; 3525796c8dcSSimon Schubert if (n >= *mid) 3535796c8dcSSimon Schubert low = mid + 1; 3545796c8dcSSimon Schubert else 3555796c8dcSSimon Schubert high = mid; 3565796c8dcSSimon Schubert } 3575796c8dcSSimon Schubert 3585796c8dcSSimon Schubert if (n >= *low) 3595796c8dcSSimon Schubert return 0; 3605796c8dcSSimon Schubert 3615796c8dcSSimon Schubert return *low; 3625796c8dcSSimon Schubert } 3635796c8dcSSimon Schubert 364*a45ae5f8SJohn Marino static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE; 3655796c8dcSSimon Schubert 3665796c8dcSSimon Schubert /* Create a new hash table, given a number of entries. */ 3675796c8dcSSimon Schubert 3685796c8dcSSimon Schubert bfd_boolean 3695796c8dcSSimon Schubert bfd_hash_table_init_n (struct bfd_hash_table *table, 3705796c8dcSSimon Schubert struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 3715796c8dcSSimon Schubert struct bfd_hash_table *, 3725796c8dcSSimon Schubert const char *), 3735796c8dcSSimon Schubert unsigned int entsize, 3745796c8dcSSimon Schubert unsigned int size) 3755796c8dcSSimon Schubert { 376*a45ae5f8SJohn Marino unsigned long alloc; 3775796c8dcSSimon Schubert 378*a45ae5f8SJohn Marino alloc = size; 379*a45ae5f8SJohn Marino alloc *= sizeof (struct bfd_hash_entry *); 380*a45ae5f8SJohn Marino if (alloc / sizeof (struct bfd_hash_entry *) != size) 381*a45ae5f8SJohn Marino { 382*a45ae5f8SJohn Marino bfd_set_error (bfd_error_no_memory); 383*a45ae5f8SJohn Marino return FALSE; 384*a45ae5f8SJohn Marino } 3855796c8dcSSimon Schubert 3865796c8dcSSimon Schubert table->memory = (void *) objalloc_create (); 3875796c8dcSSimon Schubert if (table->memory == NULL) 3885796c8dcSSimon Schubert { 3895796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 3905796c8dcSSimon Schubert return FALSE; 3915796c8dcSSimon Schubert } 3925796c8dcSSimon Schubert table->table = (struct bfd_hash_entry **) 3935796c8dcSSimon Schubert objalloc_alloc ((struct objalloc *) table->memory, alloc); 3945796c8dcSSimon Schubert if (table->table == NULL) 3955796c8dcSSimon Schubert { 3965796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 3975796c8dcSSimon Schubert return FALSE; 3985796c8dcSSimon Schubert } 3995796c8dcSSimon Schubert memset ((void *) table->table, 0, alloc); 4005796c8dcSSimon Schubert table->size = size; 4015796c8dcSSimon Schubert table->entsize = entsize; 4025796c8dcSSimon Schubert table->count = 0; 4035796c8dcSSimon Schubert table->frozen = 0; 4045796c8dcSSimon Schubert table->newfunc = newfunc; 4055796c8dcSSimon Schubert return TRUE; 4065796c8dcSSimon Schubert } 4075796c8dcSSimon Schubert 4085796c8dcSSimon Schubert /* Create a new hash table with the default number of entries. */ 4095796c8dcSSimon Schubert 4105796c8dcSSimon Schubert bfd_boolean 4115796c8dcSSimon Schubert bfd_hash_table_init (struct bfd_hash_table *table, 4125796c8dcSSimon Schubert struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 4135796c8dcSSimon Schubert struct bfd_hash_table *, 4145796c8dcSSimon Schubert const char *), 4155796c8dcSSimon Schubert unsigned int entsize) 4165796c8dcSSimon Schubert { 4175796c8dcSSimon Schubert return bfd_hash_table_init_n (table, newfunc, entsize, 4185796c8dcSSimon Schubert bfd_default_hash_table_size); 4195796c8dcSSimon Schubert } 4205796c8dcSSimon Schubert 4215796c8dcSSimon Schubert /* Free a hash table. */ 4225796c8dcSSimon Schubert 4235796c8dcSSimon Schubert void 4245796c8dcSSimon Schubert bfd_hash_table_free (struct bfd_hash_table *table) 4255796c8dcSSimon Schubert { 4265796c8dcSSimon Schubert objalloc_free ((struct objalloc *) table->memory); 4275796c8dcSSimon Schubert table->memory = NULL; 4285796c8dcSSimon Schubert } 4295796c8dcSSimon Schubert 430c50c785cSJohn Marino static inline unsigned long 431c50c785cSJohn Marino bfd_hash_hash (const char *string, unsigned int *lenp) 4325796c8dcSSimon Schubert { 4335796c8dcSSimon Schubert const unsigned char *s; 4345796c8dcSSimon Schubert unsigned long hash; 4355796c8dcSSimon Schubert unsigned int len; 436c50c785cSJohn Marino unsigned int c; 4375796c8dcSSimon Schubert 4385796c8dcSSimon Schubert hash = 0; 4395796c8dcSSimon Schubert len = 0; 4405796c8dcSSimon Schubert s = (const unsigned char *) string; 4415796c8dcSSimon Schubert while ((c = *s++) != '\0') 4425796c8dcSSimon Schubert { 4435796c8dcSSimon Schubert hash += c + (c << 17); 4445796c8dcSSimon Schubert hash ^= hash >> 2; 4455796c8dcSSimon Schubert } 4465796c8dcSSimon Schubert len = (s - (const unsigned char *) string) - 1; 4475796c8dcSSimon Schubert hash += len + (len << 17); 4485796c8dcSSimon Schubert hash ^= hash >> 2; 449c50c785cSJohn Marino if (lenp != NULL) 450c50c785cSJohn Marino *lenp = len; 451c50c785cSJohn Marino return hash; 452c50c785cSJohn Marino } 4535796c8dcSSimon Schubert 454c50c785cSJohn Marino /* Look up a string in a hash table. */ 455c50c785cSJohn Marino 456c50c785cSJohn Marino struct bfd_hash_entry * 457c50c785cSJohn Marino bfd_hash_lookup (struct bfd_hash_table *table, 458c50c785cSJohn Marino const char *string, 459c50c785cSJohn Marino bfd_boolean create, 460c50c785cSJohn Marino bfd_boolean copy) 461c50c785cSJohn Marino { 462c50c785cSJohn Marino unsigned long hash; 463c50c785cSJohn Marino struct bfd_hash_entry *hashp; 464c50c785cSJohn Marino unsigned int len; 465c50c785cSJohn Marino unsigned int _index; 466c50c785cSJohn Marino 467c50c785cSJohn Marino hash = bfd_hash_hash (string, &len); 468cf7f2e2dSJohn Marino _index = hash % table->size; 469cf7f2e2dSJohn Marino for (hashp = table->table[_index]; 4705796c8dcSSimon Schubert hashp != NULL; 4715796c8dcSSimon Schubert hashp = hashp->next) 4725796c8dcSSimon Schubert { 4735796c8dcSSimon Schubert if (hashp->hash == hash 4745796c8dcSSimon Schubert && strcmp (hashp->string, string) == 0) 4755796c8dcSSimon Schubert return hashp; 4765796c8dcSSimon Schubert } 4775796c8dcSSimon Schubert 4785796c8dcSSimon Schubert if (! create) 4795796c8dcSSimon Schubert return NULL; 4805796c8dcSSimon Schubert 4815796c8dcSSimon Schubert if (copy) 4825796c8dcSSimon Schubert { 4835796c8dcSSimon Schubert char *new_string; 4845796c8dcSSimon Schubert 4855796c8dcSSimon Schubert new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory, 4865796c8dcSSimon Schubert len + 1); 4875796c8dcSSimon Schubert if (!new_string) 4885796c8dcSSimon Schubert { 4895796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 4905796c8dcSSimon Schubert return NULL; 4915796c8dcSSimon Schubert } 4925796c8dcSSimon Schubert memcpy (new_string, string, len + 1); 4935796c8dcSSimon Schubert string = new_string; 4945796c8dcSSimon Schubert } 4955796c8dcSSimon Schubert 4965796c8dcSSimon Schubert return bfd_hash_insert (table, string, hash); 4975796c8dcSSimon Schubert } 4985796c8dcSSimon Schubert 4995796c8dcSSimon Schubert /* Insert an entry in a hash table. */ 5005796c8dcSSimon Schubert 5015796c8dcSSimon Schubert struct bfd_hash_entry * 5025796c8dcSSimon Schubert bfd_hash_insert (struct bfd_hash_table *table, 5035796c8dcSSimon Schubert const char *string, 5045796c8dcSSimon Schubert unsigned long hash) 5055796c8dcSSimon Schubert { 5065796c8dcSSimon Schubert struct bfd_hash_entry *hashp; 507cf7f2e2dSJohn Marino unsigned int _index; 5085796c8dcSSimon Schubert 5095796c8dcSSimon Schubert hashp = (*table->newfunc) (NULL, table, string); 5105796c8dcSSimon Schubert if (hashp == NULL) 5115796c8dcSSimon Schubert return NULL; 5125796c8dcSSimon Schubert hashp->string = string; 5135796c8dcSSimon Schubert hashp->hash = hash; 514cf7f2e2dSJohn Marino _index = hash % table->size; 515cf7f2e2dSJohn Marino hashp->next = table->table[_index]; 516cf7f2e2dSJohn Marino table->table[_index] = hashp; 5175796c8dcSSimon Schubert table->count++; 5185796c8dcSSimon Schubert 5195796c8dcSSimon Schubert if (!table->frozen && table->count > table->size * 3 / 4) 5205796c8dcSSimon Schubert { 5215796c8dcSSimon Schubert unsigned long newsize = higher_prime_number (table->size); 5225796c8dcSSimon Schubert struct bfd_hash_entry **newtable; 5235796c8dcSSimon Schubert unsigned int hi; 5245796c8dcSSimon Schubert unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *); 5255796c8dcSSimon Schubert 5265796c8dcSSimon Schubert /* If we can't find a higher prime, or we can't possibly alloc 5275796c8dcSSimon Schubert that much memory, don't try to grow the table. */ 5285796c8dcSSimon Schubert if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize) 5295796c8dcSSimon Schubert { 5305796c8dcSSimon Schubert table->frozen = 1; 5315796c8dcSSimon Schubert return hashp; 5325796c8dcSSimon Schubert } 5335796c8dcSSimon Schubert 5345796c8dcSSimon Schubert newtable = ((struct bfd_hash_entry **) 5355796c8dcSSimon Schubert objalloc_alloc ((struct objalloc *) table->memory, alloc)); 5365796c8dcSSimon Schubert if (newtable == NULL) 5375796c8dcSSimon Schubert { 5385796c8dcSSimon Schubert table->frozen = 1; 5395796c8dcSSimon Schubert return hashp; 5405796c8dcSSimon Schubert } 5415796c8dcSSimon Schubert memset ((PTR) newtable, 0, alloc); 5425796c8dcSSimon Schubert 5435796c8dcSSimon Schubert for (hi = 0; hi < table->size; hi ++) 5445796c8dcSSimon Schubert while (table->table[hi]) 5455796c8dcSSimon Schubert { 5465796c8dcSSimon Schubert struct bfd_hash_entry *chain = table->table[hi]; 5475796c8dcSSimon Schubert struct bfd_hash_entry *chain_end = chain; 5485796c8dcSSimon Schubert 5495796c8dcSSimon Schubert while (chain_end->next && chain_end->next->hash == chain->hash) 5505796c8dcSSimon Schubert chain_end = chain_end->next; 5515796c8dcSSimon Schubert 5525796c8dcSSimon Schubert table->table[hi] = chain_end->next; 553cf7f2e2dSJohn Marino _index = chain->hash % newsize; 554cf7f2e2dSJohn Marino chain_end->next = newtable[_index]; 555cf7f2e2dSJohn Marino newtable[_index] = chain; 5565796c8dcSSimon Schubert } 5575796c8dcSSimon Schubert table->table = newtable; 5585796c8dcSSimon Schubert table->size = newsize; 5595796c8dcSSimon Schubert } 5605796c8dcSSimon Schubert 5615796c8dcSSimon Schubert return hashp; 5625796c8dcSSimon Schubert } 5635796c8dcSSimon Schubert 564c50c785cSJohn Marino /* Rename an entry in a hash table. */ 565c50c785cSJohn Marino 566c50c785cSJohn Marino void 567c50c785cSJohn Marino bfd_hash_rename (struct bfd_hash_table *table, 568c50c785cSJohn Marino const char *string, 569c50c785cSJohn Marino struct bfd_hash_entry *ent) 570c50c785cSJohn Marino { 571c50c785cSJohn Marino unsigned int _index; 572c50c785cSJohn Marino struct bfd_hash_entry **pph; 573c50c785cSJohn Marino 574c50c785cSJohn Marino _index = ent->hash % table->size; 575c50c785cSJohn Marino for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next) 576c50c785cSJohn Marino if (*pph == ent) 577c50c785cSJohn Marino break; 578c50c785cSJohn Marino if (*pph == NULL) 579c50c785cSJohn Marino abort (); 580c50c785cSJohn Marino 581c50c785cSJohn Marino *pph = ent->next; 582c50c785cSJohn Marino ent->string = string; 583c50c785cSJohn Marino ent->hash = bfd_hash_hash (string, NULL); 584c50c785cSJohn Marino _index = ent->hash % table->size; 585c50c785cSJohn Marino ent->next = table->table[_index]; 586c50c785cSJohn Marino table->table[_index] = ent; 587c50c785cSJohn Marino } 588c50c785cSJohn Marino 5895796c8dcSSimon Schubert /* Replace an entry in a hash table. */ 5905796c8dcSSimon Schubert 5915796c8dcSSimon Schubert void 5925796c8dcSSimon Schubert bfd_hash_replace (struct bfd_hash_table *table, 5935796c8dcSSimon Schubert struct bfd_hash_entry *old, 5945796c8dcSSimon Schubert struct bfd_hash_entry *nw) 5955796c8dcSSimon Schubert { 596cf7f2e2dSJohn Marino unsigned int _index; 5975796c8dcSSimon Schubert struct bfd_hash_entry **pph; 5985796c8dcSSimon Schubert 599cf7f2e2dSJohn Marino _index = old->hash % table->size; 600cf7f2e2dSJohn Marino for (pph = &table->table[_index]; 6015796c8dcSSimon Schubert (*pph) != NULL; 6025796c8dcSSimon Schubert pph = &(*pph)->next) 6035796c8dcSSimon Schubert { 6045796c8dcSSimon Schubert if (*pph == old) 6055796c8dcSSimon Schubert { 6065796c8dcSSimon Schubert *pph = nw; 6075796c8dcSSimon Schubert return; 6085796c8dcSSimon Schubert } 6095796c8dcSSimon Schubert } 6105796c8dcSSimon Schubert 6115796c8dcSSimon Schubert abort (); 6125796c8dcSSimon Schubert } 6135796c8dcSSimon Schubert 6145796c8dcSSimon Schubert /* Allocate space in a hash table. */ 6155796c8dcSSimon Schubert 6165796c8dcSSimon Schubert void * 6175796c8dcSSimon Schubert bfd_hash_allocate (struct bfd_hash_table *table, 6185796c8dcSSimon Schubert unsigned int size) 6195796c8dcSSimon Schubert { 6205796c8dcSSimon Schubert void * ret; 6215796c8dcSSimon Schubert 6225796c8dcSSimon Schubert ret = objalloc_alloc ((struct objalloc *) table->memory, size); 6235796c8dcSSimon Schubert if (ret == NULL && size != 0) 6245796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 6255796c8dcSSimon Schubert return ret; 6265796c8dcSSimon Schubert } 6275796c8dcSSimon Schubert 6285796c8dcSSimon Schubert /* Base method for creating a new hash table entry. */ 6295796c8dcSSimon Schubert 6305796c8dcSSimon Schubert struct bfd_hash_entry * 6315796c8dcSSimon Schubert bfd_hash_newfunc (struct bfd_hash_entry *entry, 6325796c8dcSSimon Schubert struct bfd_hash_table *table, 6335796c8dcSSimon Schubert const char *string ATTRIBUTE_UNUSED) 6345796c8dcSSimon Schubert { 6355796c8dcSSimon Schubert if (entry == NULL) 6365796c8dcSSimon Schubert entry = (struct bfd_hash_entry *) bfd_hash_allocate (table, 6375796c8dcSSimon Schubert sizeof (* entry)); 6385796c8dcSSimon Schubert return entry; 6395796c8dcSSimon Schubert } 6405796c8dcSSimon Schubert 6415796c8dcSSimon Schubert /* Traverse a hash table. */ 6425796c8dcSSimon Schubert 6435796c8dcSSimon Schubert void 6445796c8dcSSimon Schubert bfd_hash_traverse (struct bfd_hash_table *table, 6455796c8dcSSimon Schubert bfd_boolean (*func) (struct bfd_hash_entry *, void *), 6465796c8dcSSimon Schubert void * info) 6475796c8dcSSimon Schubert { 6485796c8dcSSimon Schubert unsigned int i; 6495796c8dcSSimon Schubert 6505796c8dcSSimon Schubert table->frozen = 1; 6515796c8dcSSimon Schubert for (i = 0; i < table->size; i++) 6525796c8dcSSimon Schubert { 6535796c8dcSSimon Schubert struct bfd_hash_entry *p; 6545796c8dcSSimon Schubert 6555796c8dcSSimon Schubert for (p = table->table[i]; p != NULL; p = p->next) 6565796c8dcSSimon Schubert if (! (*func) (p, info)) 6575796c8dcSSimon Schubert goto out; 6585796c8dcSSimon Schubert } 6595796c8dcSSimon Schubert out: 6605796c8dcSSimon Schubert table->frozen = 0; 6615796c8dcSSimon Schubert } 6625796c8dcSSimon Schubert 663*a45ae5f8SJohn Marino unsigned long 664*a45ae5f8SJohn Marino bfd_hash_set_default_size (unsigned long hash_size) 6655796c8dcSSimon Schubert { 6665796c8dcSSimon Schubert /* Extend this prime list if you want more granularity of hash table size. */ 667*a45ae5f8SJohn Marino static const unsigned long hash_size_primes[] = 6685796c8dcSSimon Schubert { 669*a45ae5f8SJohn Marino 31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537 6705796c8dcSSimon Schubert }; 671*a45ae5f8SJohn Marino unsigned int _index; 6725796c8dcSSimon Schubert 6735796c8dcSSimon Schubert /* Work out best prime number near the hash_size. */ 674cf7f2e2dSJohn Marino for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index) 675cf7f2e2dSJohn Marino if (hash_size <= hash_size_primes[_index]) 6765796c8dcSSimon Schubert break; 6775796c8dcSSimon Schubert 678cf7f2e2dSJohn Marino bfd_default_hash_table_size = hash_size_primes[_index]; 679*a45ae5f8SJohn Marino return bfd_default_hash_table_size; 6805796c8dcSSimon Schubert } 6815796c8dcSSimon Schubert 6825796c8dcSSimon Schubert /* A few different object file formats (a.out, COFF, ELF) use a string 6835796c8dcSSimon Schubert table. These functions support adding strings to a string table, 6845796c8dcSSimon Schubert returning the byte offset, and writing out the table. 6855796c8dcSSimon Schubert 6865796c8dcSSimon Schubert Possible improvements: 6875796c8dcSSimon Schubert + look for strings matching trailing substrings of other strings 6885796c8dcSSimon Schubert + better data structures? balanced trees? 6895796c8dcSSimon Schubert + look at reducing memory use elsewhere -- maybe if we didn't have 6905796c8dcSSimon Schubert to construct the entire symbol table at once, we could get by 6915796c8dcSSimon Schubert with smaller amounts of VM? (What effect does that have on the 6925796c8dcSSimon Schubert string table reductions?) */ 6935796c8dcSSimon Schubert 6945796c8dcSSimon Schubert /* An entry in the strtab hash table. */ 6955796c8dcSSimon Schubert 6965796c8dcSSimon Schubert struct strtab_hash_entry 6975796c8dcSSimon Schubert { 6985796c8dcSSimon Schubert struct bfd_hash_entry root; 6995796c8dcSSimon Schubert /* Index in string table. */ 7005796c8dcSSimon Schubert bfd_size_type index; 7015796c8dcSSimon Schubert /* Next string in strtab. */ 7025796c8dcSSimon Schubert struct strtab_hash_entry *next; 7035796c8dcSSimon Schubert }; 7045796c8dcSSimon Schubert 7055796c8dcSSimon Schubert /* The strtab hash table. */ 7065796c8dcSSimon Schubert 7075796c8dcSSimon Schubert struct bfd_strtab_hash 7085796c8dcSSimon Schubert { 7095796c8dcSSimon Schubert struct bfd_hash_table table; 7105796c8dcSSimon Schubert /* Size of strtab--also next available index. */ 7115796c8dcSSimon Schubert bfd_size_type size; 7125796c8dcSSimon Schubert /* First string in strtab. */ 7135796c8dcSSimon Schubert struct strtab_hash_entry *first; 7145796c8dcSSimon Schubert /* Last string in strtab. */ 7155796c8dcSSimon Schubert struct strtab_hash_entry *last; 7165796c8dcSSimon Schubert /* Whether to precede strings with a two byte length, as in the 7175796c8dcSSimon Schubert XCOFF .debug section. */ 7185796c8dcSSimon Schubert bfd_boolean xcoff; 7195796c8dcSSimon Schubert }; 7205796c8dcSSimon Schubert 7215796c8dcSSimon Schubert /* Routine to create an entry in a strtab. */ 7225796c8dcSSimon Schubert 7235796c8dcSSimon Schubert static struct bfd_hash_entry * 7245796c8dcSSimon Schubert strtab_hash_newfunc (struct bfd_hash_entry *entry, 7255796c8dcSSimon Schubert struct bfd_hash_table *table, 7265796c8dcSSimon Schubert const char *string) 7275796c8dcSSimon Schubert { 7285796c8dcSSimon Schubert struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 7295796c8dcSSimon Schubert 7305796c8dcSSimon Schubert /* Allocate the structure if it has not already been allocated by a 7315796c8dcSSimon Schubert subclass. */ 7325796c8dcSSimon Schubert if (ret == NULL) 7335796c8dcSSimon Schubert ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, 7345796c8dcSSimon Schubert sizeof (* ret)); 7355796c8dcSSimon Schubert if (ret == NULL) 7365796c8dcSSimon Schubert return NULL; 7375796c8dcSSimon Schubert 7385796c8dcSSimon Schubert /* Call the allocation method of the superclass. */ 7395796c8dcSSimon Schubert ret = (struct strtab_hash_entry *) 7405796c8dcSSimon Schubert bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 7415796c8dcSSimon Schubert 7425796c8dcSSimon Schubert if (ret) 7435796c8dcSSimon Schubert { 7445796c8dcSSimon Schubert /* Initialize the local fields. */ 7455796c8dcSSimon Schubert ret->index = (bfd_size_type) -1; 7465796c8dcSSimon Schubert ret->next = NULL; 7475796c8dcSSimon Schubert } 7485796c8dcSSimon Schubert 7495796c8dcSSimon Schubert return (struct bfd_hash_entry *) ret; 7505796c8dcSSimon Schubert } 7515796c8dcSSimon Schubert 7525796c8dcSSimon Schubert /* Look up an entry in an strtab. */ 7535796c8dcSSimon Schubert 7545796c8dcSSimon Schubert #define strtab_hash_lookup(t, string, create, copy) \ 7555796c8dcSSimon Schubert ((struct strtab_hash_entry *) \ 7565796c8dcSSimon Schubert bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 7575796c8dcSSimon Schubert 7585796c8dcSSimon Schubert /* Create a new strtab. */ 7595796c8dcSSimon Schubert 7605796c8dcSSimon Schubert struct bfd_strtab_hash * 7615796c8dcSSimon Schubert _bfd_stringtab_init (void) 7625796c8dcSSimon Schubert { 7635796c8dcSSimon Schubert struct bfd_strtab_hash *table; 7645796c8dcSSimon Schubert bfd_size_type amt = sizeof (* table); 7655796c8dcSSimon Schubert 7665796c8dcSSimon Schubert table = (struct bfd_strtab_hash *) bfd_malloc (amt); 7675796c8dcSSimon Schubert if (table == NULL) 7685796c8dcSSimon Schubert return NULL; 7695796c8dcSSimon Schubert 7705796c8dcSSimon Schubert if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 7715796c8dcSSimon Schubert sizeof (struct strtab_hash_entry))) 7725796c8dcSSimon Schubert { 7735796c8dcSSimon Schubert free (table); 7745796c8dcSSimon Schubert return NULL; 7755796c8dcSSimon Schubert } 7765796c8dcSSimon Schubert 7775796c8dcSSimon Schubert table->size = 0; 7785796c8dcSSimon Schubert table->first = NULL; 7795796c8dcSSimon Schubert table->last = NULL; 7805796c8dcSSimon Schubert table->xcoff = FALSE; 7815796c8dcSSimon Schubert 7825796c8dcSSimon Schubert return table; 7835796c8dcSSimon Schubert } 7845796c8dcSSimon Schubert 7855796c8dcSSimon Schubert /* Create a new strtab in which the strings are output in the format 7865796c8dcSSimon Schubert used in the XCOFF .debug section: a two byte length precedes each 7875796c8dcSSimon Schubert string. */ 7885796c8dcSSimon Schubert 7895796c8dcSSimon Schubert struct bfd_strtab_hash * 7905796c8dcSSimon Schubert _bfd_xcoff_stringtab_init (void) 7915796c8dcSSimon Schubert { 7925796c8dcSSimon Schubert struct bfd_strtab_hash *ret; 7935796c8dcSSimon Schubert 7945796c8dcSSimon Schubert ret = _bfd_stringtab_init (); 7955796c8dcSSimon Schubert if (ret != NULL) 7965796c8dcSSimon Schubert ret->xcoff = TRUE; 7975796c8dcSSimon Schubert return ret; 7985796c8dcSSimon Schubert } 7995796c8dcSSimon Schubert 8005796c8dcSSimon Schubert /* Free a strtab. */ 8015796c8dcSSimon Schubert 8025796c8dcSSimon Schubert void 8035796c8dcSSimon Schubert _bfd_stringtab_free (struct bfd_strtab_hash *table) 8045796c8dcSSimon Schubert { 8055796c8dcSSimon Schubert bfd_hash_table_free (&table->table); 8065796c8dcSSimon Schubert free (table); 8075796c8dcSSimon Schubert } 8085796c8dcSSimon Schubert 8095796c8dcSSimon Schubert /* Get the index of a string in a strtab, adding it if it is not 8105796c8dcSSimon Schubert already present. If HASH is FALSE, we don't really use the hash 8115796c8dcSSimon Schubert table, and we don't eliminate duplicate strings. */ 8125796c8dcSSimon Schubert 8135796c8dcSSimon Schubert bfd_size_type 8145796c8dcSSimon Schubert _bfd_stringtab_add (struct bfd_strtab_hash *tab, 8155796c8dcSSimon Schubert const char *str, 8165796c8dcSSimon Schubert bfd_boolean hash, 8175796c8dcSSimon Schubert bfd_boolean copy) 8185796c8dcSSimon Schubert { 8195796c8dcSSimon Schubert struct strtab_hash_entry *entry; 8205796c8dcSSimon Schubert 8215796c8dcSSimon Schubert if (hash) 8225796c8dcSSimon Schubert { 8235796c8dcSSimon Schubert entry = strtab_hash_lookup (tab, str, TRUE, copy); 8245796c8dcSSimon Schubert if (entry == NULL) 8255796c8dcSSimon Schubert return (bfd_size_type) -1; 8265796c8dcSSimon Schubert } 8275796c8dcSSimon Schubert else 8285796c8dcSSimon Schubert { 8295796c8dcSSimon Schubert entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, 8305796c8dcSSimon Schubert sizeof (* entry)); 8315796c8dcSSimon Schubert if (entry == NULL) 8325796c8dcSSimon Schubert return (bfd_size_type) -1; 8335796c8dcSSimon Schubert if (! copy) 8345796c8dcSSimon Schubert entry->root.string = str; 8355796c8dcSSimon Schubert else 8365796c8dcSSimon Schubert { 8375796c8dcSSimon Schubert char *n; 8385796c8dcSSimon Schubert 8395796c8dcSSimon Schubert n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); 8405796c8dcSSimon Schubert if (n == NULL) 8415796c8dcSSimon Schubert return (bfd_size_type) -1; 8425796c8dcSSimon Schubert entry->root.string = n; 8435796c8dcSSimon Schubert } 8445796c8dcSSimon Schubert entry->index = (bfd_size_type) -1; 8455796c8dcSSimon Schubert entry->next = NULL; 8465796c8dcSSimon Schubert } 8475796c8dcSSimon Schubert 8485796c8dcSSimon Schubert if (entry->index == (bfd_size_type) -1) 8495796c8dcSSimon Schubert { 8505796c8dcSSimon Schubert entry->index = tab->size; 8515796c8dcSSimon Schubert tab->size += strlen (str) + 1; 8525796c8dcSSimon Schubert if (tab->xcoff) 8535796c8dcSSimon Schubert { 8545796c8dcSSimon Schubert entry->index += 2; 8555796c8dcSSimon Schubert tab->size += 2; 8565796c8dcSSimon Schubert } 8575796c8dcSSimon Schubert if (tab->first == NULL) 8585796c8dcSSimon Schubert tab->first = entry; 8595796c8dcSSimon Schubert else 8605796c8dcSSimon Schubert tab->last->next = entry; 8615796c8dcSSimon Schubert tab->last = entry; 8625796c8dcSSimon Schubert } 8635796c8dcSSimon Schubert 8645796c8dcSSimon Schubert return entry->index; 8655796c8dcSSimon Schubert } 8665796c8dcSSimon Schubert 8675796c8dcSSimon Schubert /* Get the number of bytes in a strtab. */ 8685796c8dcSSimon Schubert 8695796c8dcSSimon Schubert bfd_size_type 8705796c8dcSSimon Schubert _bfd_stringtab_size (struct bfd_strtab_hash *tab) 8715796c8dcSSimon Schubert { 8725796c8dcSSimon Schubert return tab->size; 8735796c8dcSSimon Schubert } 8745796c8dcSSimon Schubert 8755796c8dcSSimon Schubert /* Write out a strtab. ABFD must already be at the right location in 8765796c8dcSSimon Schubert the file. */ 8775796c8dcSSimon Schubert 8785796c8dcSSimon Schubert bfd_boolean 8795796c8dcSSimon Schubert _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 8805796c8dcSSimon Schubert { 8815796c8dcSSimon Schubert bfd_boolean xcoff; 8825796c8dcSSimon Schubert struct strtab_hash_entry *entry; 8835796c8dcSSimon Schubert 8845796c8dcSSimon Schubert xcoff = tab->xcoff; 8855796c8dcSSimon Schubert 8865796c8dcSSimon Schubert for (entry = tab->first; entry != NULL; entry = entry->next) 8875796c8dcSSimon Schubert { 8885796c8dcSSimon Schubert const char *str; 8895796c8dcSSimon Schubert size_t len; 8905796c8dcSSimon Schubert 8915796c8dcSSimon Schubert str = entry->root.string; 8925796c8dcSSimon Schubert len = strlen (str) + 1; 8935796c8dcSSimon Schubert 8945796c8dcSSimon Schubert if (xcoff) 8955796c8dcSSimon Schubert { 8965796c8dcSSimon Schubert bfd_byte buf[2]; 8975796c8dcSSimon Schubert 8985796c8dcSSimon Schubert /* The output length includes the null byte. */ 8995796c8dcSSimon Schubert bfd_put_16 (abfd, (bfd_vma) len, buf); 9005796c8dcSSimon Schubert if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 9015796c8dcSSimon Schubert return FALSE; 9025796c8dcSSimon Schubert } 9035796c8dcSSimon Schubert 9045796c8dcSSimon Schubert if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 9055796c8dcSSimon Schubert return FALSE; 9065796c8dcSSimon Schubert } 9075796c8dcSSimon Schubert 9085796c8dcSSimon Schubert return TRUE; 9095796c8dcSSimon Schubert } 910