15796c8dcSSimon Schubert /* hash.c -- hash table routines for BFD 25796c8dcSSimon Schubert Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005, 3*c50c785cSJohn Marino 2006, 2007, 2009, 2010 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. */ 3135796c8dcSSimon Schubert static const unsigned long primes[] = { 3145796c8dcSSimon Schubert (unsigned long) 127, 3155796c8dcSSimon Schubert (unsigned long) 2039, 3165796c8dcSSimon Schubert (unsigned long) 32749, 3175796c8dcSSimon Schubert (unsigned long) 65521, 3185796c8dcSSimon Schubert (unsigned long) 131071, 3195796c8dcSSimon Schubert (unsigned long) 262139, 3205796c8dcSSimon Schubert (unsigned long) 524287, 3215796c8dcSSimon Schubert (unsigned long) 1048573, 3225796c8dcSSimon Schubert (unsigned long) 2097143, 3235796c8dcSSimon Schubert (unsigned long) 4194301, 3245796c8dcSSimon Schubert (unsigned long) 8388593, 3255796c8dcSSimon Schubert (unsigned long) 16777213, 3265796c8dcSSimon Schubert (unsigned long) 33554393, 3275796c8dcSSimon Schubert (unsigned long) 67108859, 3285796c8dcSSimon Schubert (unsigned long) 134217689, 3295796c8dcSSimon Schubert (unsigned long) 268435399, 3305796c8dcSSimon Schubert (unsigned long) 536870909, 3315796c8dcSSimon Schubert (unsigned long) 1073741789, 3325796c8dcSSimon Schubert (unsigned long) 2147483647, 3335796c8dcSSimon Schubert /* 4294967291L */ 3345796c8dcSSimon Schubert ((unsigned long) 2147483647) + ((unsigned long) 2147483644), 3355796c8dcSSimon Schubert }; 3365796c8dcSSimon Schubert 3375796c8dcSSimon Schubert const unsigned long *low = &primes[0]; 3385796c8dcSSimon Schubert const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; 3395796c8dcSSimon Schubert 3405796c8dcSSimon Schubert while (low != high) 3415796c8dcSSimon Schubert { 3425796c8dcSSimon Schubert const unsigned long *mid = low + (high - low) / 2; 3435796c8dcSSimon Schubert if (n >= *mid) 3445796c8dcSSimon Schubert low = mid + 1; 3455796c8dcSSimon Schubert else 3465796c8dcSSimon Schubert high = mid; 3475796c8dcSSimon Schubert } 3485796c8dcSSimon Schubert 3495796c8dcSSimon Schubert if (n >= *low) 3505796c8dcSSimon Schubert return 0; 3515796c8dcSSimon Schubert 3525796c8dcSSimon Schubert return *low; 3535796c8dcSSimon Schubert } 3545796c8dcSSimon Schubert 3555796c8dcSSimon Schubert static size_t bfd_default_hash_table_size = DEFAULT_SIZE; 3565796c8dcSSimon Schubert 3575796c8dcSSimon Schubert /* Create a new hash table, given a number of entries. */ 3585796c8dcSSimon Schubert 3595796c8dcSSimon Schubert bfd_boolean 3605796c8dcSSimon Schubert bfd_hash_table_init_n (struct bfd_hash_table *table, 3615796c8dcSSimon Schubert struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 3625796c8dcSSimon Schubert struct bfd_hash_table *, 3635796c8dcSSimon Schubert const char *), 3645796c8dcSSimon Schubert unsigned int entsize, 3655796c8dcSSimon Schubert unsigned int size) 3665796c8dcSSimon Schubert { 3675796c8dcSSimon Schubert unsigned int alloc; 3685796c8dcSSimon Schubert 3695796c8dcSSimon Schubert alloc = size * sizeof (struct bfd_hash_entry *); 3705796c8dcSSimon Schubert 3715796c8dcSSimon Schubert table->memory = (void *) objalloc_create (); 3725796c8dcSSimon Schubert if (table->memory == NULL) 3735796c8dcSSimon Schubert { 3745796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 3755796c8dcSSimon Schubert return FALSE; 3765796c8dcSSimon Schubert } 3775796c8dcSSimon Schubert table->table = (struct bfd_hash_entry **) 3785796c8dcSSimon Schubert objalloc_alloc ((struct objalloc *) table->memory, alloc); 3795796c8dcSSimon Schubert if (table->table == NULL) 3805796c8dcSSimon Schubert { 3815796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 3825796c8dcSSimon Schubert return FALSE; 3835796c8dcSSimon Schubert } 3845796c8dcSSimon Schubert memset ((void *) table->table, 0, alloc); 3855796c8dcSSimon Schubert table->size = size; 3865796c8dcSSimon Schubert table->entsize = entsize; 3875796c8dcSSimon Schubert table->count = 0; 3885796c8dcSSimon Schubert table->frozen = 0; 3895796c8dcSSimon Schubert table->newfunc = newfunc; 3905796c8dcSSimon Schubert return TRUE; 3915796c8dcSSimon Schubert } 3925796c8dcSSimon Schubert 3935796c8dcSSimon Schubert /* Create a new hash table with the default number of entries. */ 3945796c8dcSSimon Schubert 3955796c8dcSSimon Schubert bfd_boolean 3965796c8dcSSimon Schubert bfd_hash_table_init (struct bfd_hash_table *table, 3975796c8dcSSimon Schubert struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 3985796c8dcSSimon Schubert struct bfd_hash_table *, 3995796c8dcSSimon Schubert const char *), 4005796c8dcSSimon Schubert unsigned int entsize) 4015796c8dcSSimon Schubert { 4025796c8dcSSimon Schubert return bfd_hash_table_init_n (table, newfunc, entsize, 4035796c8dcSSimon Schubert bfd_default_hash_table_size); 4045796c8dcSSimon Schubert } 4055796c8dcSSimon Schubert 4065796c8dcSSimon Schubert /* Free a hash table. */ 4075796c8dcSSimon Schubert 4085796c8dcSSimon Schubert void 4095796c8dcSSimon Schubert bfd_hash_table_free (struct bfd_hash_table *table) 4105796c8dcSSimon Schubert { 4115796c8dcSSimon Schubert objalloc_free ((struct objalloc *) table->memory); 4125796c8dcSSimon Schubert table->memory = NULL; 4135796c8dcSSimon Schubert } 4145796c8dcSSimon Schubert 415*c50c785cSJohn Marino static inline unsigned long 416*c50c785cSJohn Marino bfd_hash_hash (const char *string, unsigned int *lenp) 4175796c8dcSSimon Schubert { 4185796c8dcSSimon Schubert const unsigned char *s; 4195796c8dcSSimon Schubert unsigned long hash; 4205796c8dcSSimon Schubert unsigned int len; 421*c50c785cSJohn Marino unsigned int c; 4225796c8dcSSimon Schubert 4235796c8dcSSimon Schubert hash = 0; 4245796c8dcSSimon Schubert len = 0; 4255796c8dcSSimon Schubert s = (const unsigned char *) string; 4265796c8dcSSimon Schubert while ((c = *s++) != '\0') 4275796c8dcSSimon Schubert { 4285796c8dcSSimon Schubert hash += c + (c << 17); 4295796c8dcSSimon Schubert hash ^= hash >> 2; 4305796c8dcSSimon Schubert } 4315796c8dcSSimon Schubert len = (s - (const unsigned char *) string) - 1; 4325796c8dcSSimon Schubert hash += len + (len << 17); 4335796c8dcSSimon Schubert hash ^= hash >> 2; 434*c50c785cSJohn Marino if (lenp != NULL) 435*c50c785cSJohn Marino *lenp = len; 436*c50c785cSJohn Marino return hash; 437*c50c785cSJohn Marino } 4385796c8dcSSimon Schubert 439*c50c785cSJohn Marino /* Look up a string in a hash table. */ 440*c50c785cSJohn Marino 441*c50c785cSJohn Marino struct bfd_hash_entry * 442*c50c785cSJohn Marino bfd_hash_lookup (struct bfd_hash_table *table, 443*c50c785cSJohn Marino const char *string, 444*c50c785cSJohn Marino bfd_boolean create, 445*c50c785cSJohn Marino bfd_boolean copy) 446*c50c785cSJohn Marino { 447*c50c785cSJohn Marino unsigned long hash; 448*c50c785cSJohn Marino struct bfd_hash_entry *hashp; 449*c50c785cSJohn Marino unsigned int len; 450*c50c785cSJohn Marino unsigned int _index; 451*c50c785cSJohn Marino 452*c50c785cSJohn Marino hash = bfd_hash_hash (string, &len); 453cf7f2e2dSJohn Marino _index = hash % table->size; 454cf7f2e2dSJohn Marino for (hashp = table->table[_index]; 4555796c8dcSSimon Schubert hashp != NULL; 4565796c8dcSSimon Schubert hashp = hashp->next) 4575796c8dcSSimon Schubert { 4585796c8dcSSimon Schubert if (hashp->hash == hash 4595796c8dcSSimon Schubert && strcmp (hashp->string, string) == 0) 4605796c8dcSSimon Schubert return hashp; 4615796c8dcSSimon Schubert } 4625796c8dcSSimon Schubert 4635796c8dcSSimon Schubert if (! create) 4645796c8dcSSimon Schubert return NULL; 4655796c8dcSSimon Schubert 4665796c8dcSSimon Schubert if (copy) 4675796c8dcSSimon Schubert { 4685796c8dcSSimon Schubert char *new_string; 4695796c8dcSSimon Schubert 4705796c8dcSSimon Schubert new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory, 4715796c8dcSSimon Schubert len + 1); 4725796c8dcSSimon Schubert if (!new_string) 4735796c8dcSSimon Schubert { 4745796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 4755796c8dcSSimon Schubert return NULL; 4765796c8dcSSimon Schubert } 4775796c8dcSSimon Schubert memcpy (new_string, string, len + 1); 4785796c8dcSSimon Schubert string = new_string; 4795796c8dcSSimon Schubert } 4805796c8dcSSimon Schubert 4815796c8dcSSimon Schubert return bfd_hash_insert (table, string, hash); 4825796c8dcSSimon Schubert } 4835796c8dcSSimon Schubert 4845796c8dcSSimon Schubert /* Insert an entry in a hash table. */ 4855796c8dcSSimon Schubert 4865796c8dcSSimon Schubert struct bfd_hash_entry * 4875796c8dcSSimon Schubert bfd_hash_insert (struct bfd_hash_table *table, 4885796c8dcSSimon Schubert const char *string, 4895796c8dcSSimon Schubert unsigned long hash) 4905796c8dcSSimon Schubert { 4915796c8dcSSimon Schubert struct bfd_hash_entry *hashp; 492cf7f2e2dSJohn Marino unsigned int _index; 4935796c8dcSSimon Schubert 4945796c8dcSSimon Schubert hashp = (*table->newfunc) (NULL, table, string); 4955796c8dcSSimon Schubert if (hashp == NULL) 4965796c8dcSSimon Schubert return NULL; 4975796c8dcSSimon Schubert hashp->string = string; 4985796c8dcSSimon Schubert hashp->hash = hash; 499cf7f2e2dSJohn Marino _index = hash % table->size; 500cf7f2e2dSJohn Marino hashp->next = table->table[_index]; 501cf7f2e2dSJohn Marino table->table[_index] = hashp; 5025796c8dcSSimon Schubert table->count++; 5035796c8dcSSimon Schubert 5045796c8dcSSimon Schubert if (!table->frozen && table->count > table->size * 3 / 4) 5055796c8dcSSimon Schubert { 5065796c8dcSSimon Schubert unsigned long newsize = higher_prime_number (table->size); 5075796c8dcSSimon Schubert struct bfd_hash_entry **newtable; 5085796c8dcSSimon Schubert unsigned int hi; 5095796c8dcSSimon Schubert unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *); 5105796c8dcSSimon Schubert 5115796c8dcSSimon Schubert /* If we can't find a higher prime, or we can't possibly alloc 5125796c8dcSSimon Schubert that much memory, don't try to grow the table. */ 5135796c8dcSSimon Schubert if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize) 5145796c8dcSSimon Schubert { 5155796c8dcSSimon Schubert table->frozen = 1; 5165796c8dcSSimon Schubert return hashp; 5175796c8dcSSimon Schubert } 5185796c8dcSSimon Schubert 5195796c8dcSSimon Schubert newtable = ((struct bfd_hash_entry **) 5205796c8dcSSimon Schubert objalloc_alloc ((struct objalloc *) table->memory, alloc)); 5215796c8dcSSimon Schubert if (newtable == NULL) 5225796c8dcSSimon Schubert { 5235796c8dcSSimon Schubert table->frozen = 1; 5245796c8dcSSimon Schubert return hashp; 5255796c8dcSSimon Schubert } 5265796c8dcSSimon Schubert memset ((PTR) newtable, 0, alloc); 5275796c8dcSSimon Schubert 5285796c8dcSSimon Schubert for (hi = 0; hi < table->size; hi ++) 5295796c8dcSSimon Schubert while (table->table[hi]) 5305796c8dcSSimon Schubert { 5315796c8dcSSimon Schubert struct bfd_hash_entry *chain = table->table[hi]; 5325796c8dcSSimon Schubert struct bfd_hash_entry *chain_end = chain; 5335796c8dcSSimon Schubert 5345796c8dcSSimon Schubert while (chain_end->next && chain_end->next->hash == chain->hash) 5355796c8dcSSimon Schubert chain_end = chain_end->next; 5365796c8dcSSimon Schubert 5375796c8dcSSimon Schubert table->table[hi] = chain_end->next; 538cf7f2e2dSJohn Marino _index = chain->hash % newsize; 539cf7f2e2dSJohn Marino chain_end->next = newtable[_index]; 540cf7f2e2dSJohn Marino newtable[_index] = chain; 5415796c8dcSSimon Schubert } 5425796c8dcSSimon Schubert table->table = newtable; 5435796c8dcSSimon Schubert table->size = newsize; 5445796c8dcSSimon Schubert } 5455796c8dcSSimon Schubert 5465796c8dcSSimon Schubert return hashp; 5475796c8dcSSimon Schubert } 5485796c8dcSSimon Schubert 549*c50c785cSJohn Marino /* Rename an entry in a hash table. */ 550*c50c785cSJohn Marino 551*c50c785cSJohn Marino void 552*c50c785cSJohn Marino bfd_hash_rename (struct bfd_hash_table *table, 553*c50c785cSJohn Marino const char *string, 554*c50c785cSJohn Marino struct bfd_hash_entry *ent) 555*c50c785cSJohn Marino { 556*c50c785cSJohn Marino unsigned int _index; 557*c50c785cSJohn Marino struct bfd_hash_entry **pph; 558*c50c785cSJohn Marino 559*c50c785cSJohn Marino _index = ent->hash % table->size; 560*c50c785cSJohn Marino for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next) 561*c50c785cSJohn Marino if (*pph == ent) 562*c50c785cSJohn Marino break; 563*c50c785cSJohn Marino if (*pph == NULL) 564*c50c785cSJohn Marino abort (); 565*c50c785cSJohn Marino 566*c50c785cSJohn Marino *pph = ent->next; 567*c50c785cSJohn Marino ent->string = string; 568*c50c785cSJohn Marino ent->hash = bfd_hash_hash (string, NULL); 569*c50c785cSJohn Marino _index = ent->hash % table->size; 570*c50c785cSJohn Marino ent->next = table->table[_index]; 571*c50c785cSJohn Marino table->table[_index] = ent; 572*c50c785cSJohn Marino } 573*c50c785cSJohn Marino 5745796c8dcSSimon Schubert /* Replace an entry in a hash table. */ 5755796c8dcSSimon Schubert 5765796c8dcSSimon Schubert void 5775796c8dcSSimon Schubert bfd_hash_replace (struct bfd_hash_table *table, 5785796c8dcSSimon Schubert struct bfd_hash_entry *old, 5795796c8dcSSimon Schubert struct bfd_hash_entry *nw) 5805796c8dcSSimon Schubert { 581cf7f2e2dSJohn Marino unsigned int _index; 5825796c8dcSSimon Schubert struct bfd_hash_entry **pph; 5835796c8dcSSimon Schubert 584cf7f2e2dSJohn Marino _index = old->hash % table->size; 585cf7f2e2dSJohn Marino for (pph = &table->table[_index]; 5865796c8dcSSimon Schubert (*pph) != NULL; 5875796c8dcSSimon Schubert pph = &(*pph)->next) 5885796c8dcSSimon Schubert { 5895796c8dcSSimon Schubert if (*pph == old) 5905796c8dcSSimon Schubert { 5915796c8dcSSimon Schubert *pph = nw; 5925796c8dcSSimon Schubert return; 5935796c8dcSSimon Schubert } 5945796c8dcSSimon Schubert } 5955796c8dcSSimon Schubert 5965796c8dcSSimon Schubert abort (); 5975796c8dcSSimon Schubert } 5985796c8dcSSimon Schubert 5995796c8dcSSimon Schubert /* Allocate space in a hash table. */ 6005796c8dcSSimon Schubert 6015796c8dcSSimon Schubert void * 6025796c8dcSSimon Schubert bfd_hash_allocate (struct bfd_hash_table *table, 6035796c8dcSSimon Schubert unsigned int size) 6045796c8dcSSimon Schubert { 6055796c8dcSSimon Schubert void * ret; 6065796c8dcSSimon Schubert 6075796c8dcSSimon Schubert ret = objalloc_alloc ((struct objalloc *) table->memory, size); 6085796c8dcSSimon Schubert if (ret == NULL && size != 0) 6095796c8dcSSimon Schubert bfd_set_error (bfd_error_no_memory); 6105796c8dcSSimon Schubert return ret; 6115796c8dcSSimon Schubert } 6125796c8dcSSimon Schubert 6135796c8dcSSimon Schubert /* Base method for creating a new hash table entry. */ 6145796c8dcSSimon Schubert 6155796c8dcSSimon Schubert struct bfd_hash_entry * 6165796c8dcSSimon Schubert bfd_hash_newfunc (struct bfd_hash_entry *entry, 6175796c8dcSSimon Schubert struct bfd_hash_table *table, 6185796c8dcSSimon Schubert const char *string ATTRIBUTE_UNUSED) 6195796c8dcSSimon Schubert { 6205796c8dcSSimon Schubert if (entry == NULL) 6215796c8dcSSimon Schubert entry = (struct bfd_hash_entry *) bfd_hash_allocate (table, 6225796c8dcSSimon Schubert sizeof (* entry)); 6235796c8dcSSimon Schubert return entry; 6245796c8dcSSimon Schubert } 6255796c8dcSSimon Schubert 6265796c8dcSSimon Schubert /* Traverse a hash table. */ 6275796c8dcSSimon Schubert 6285796c8dcSSimon Schubert void 6295796c8dcSSimon Schubert bfd_hash_traverse (struct bfd_hash_table *table, 6305796c8dcSSimon Schubert bfd_boolean (*func) (struct bfd_hash_entry *, void *), 6315796c8dcSSimon Schubert void * info) 6325796c8dcSSimon Schubert { 6335796c8dcSSimon Schubert unsigned int i; 6345796c8dcSSimon Schubert 6355796c8dcSSimon Schubert table->frozen = 1; 6365796c8dcSSimon Schubert for (i = 0; i < table->size; i++) 6375796c8dcSSimon Schubert { 6385796c8dcSSimon Schubert struct bfd_hash_entry *p; 6395796c8dcSSimon Schubert 6405796c8dcSSimon Schubert for (p = table->table[i]; p != NULL; p = p->next) 6415796c8dcSSimon Schubert if (! (*func) (p, info)) 6425796c8dcSSimon Schubert goto out; 6435796c8dcSSimon Schubert } 6445796c8dcSSimon Schubert out: 6455796c8dcSSimon Schubert table->frozen = 0; 6465796c8dcSSimon Schubert } 6475796c8dcSSimon Schubert 6485796c8dcSSimon Schubert void 6495796c8dcSSimon Schubert bfd_hash_set_default_size (bfd_size_type hash_size) 6505796c8dcSSimon Schubert { 6515796c8dcSSimon Schubert /* Extend this prime list if you want more granularity of hash table size. */ 6525796c8dcSSimon Schubert static const bfd_size_type hash_size_primes[] = 6535796c8dcSSimon Schubert { 6545796c8dcSSimon Schubert 251, 509, 1021, 2039, 4051, 8599, 16699, 32749 6555796c8dcSSimon Schubert }; 656cf7f2e2dSJohn Marino size_t _index; 6575796c8dcSSimon Schubert 6585796c8dcSSimon Schubert /* Work out best prime number near the hash_size. */ 659cf7f2e2dSJohn Marino for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index) 660cf7f2e2dSJohn Marino if (hash_size <= hash_size_primes[_index]) 6615796c8dcSSimon Schubert break; 6625796c8dcSSimon Schubert 663cf7f2e2dSJohn Marino bfd_default_hash_table_size = hash_size_primes[_index]; 6645796c8dcSSimon Schubert } 6655796c8dcSSimon Schubert 6665796c8dcSSimon Schubert /* A few different object file formats (a.out, COFF, ELF) use a string 6675796c8dcSSimon Schubert table. These functions support adding strings to a string table, 6685796c8dcSSimon Schubert returning the byte offset, and writing out the table. 6695796c8dcSSimon Schubert 6705796c8dcSSimon Schubert Possible improvements: 6715796c8dcSSimon Schubert + look for strings matching trailing substrings of other strings 6725796c8dcSSimon Schubert + better data structures? balanced trees? 6735796c8dcSSimon Schubert + look at reducing memory use elsewhere -- maybe if we didn't have 6745796c8dcSSimon Schubert to construct the entire symbol table at once, we could get by 6755796c8dcSSimon Schubert with smaller amounts of VM? (What effect does that have on the 6765796c8dcSSimon Schubert string table reductions?) */ 6775796c8dcSSimon Schubert 6785796c8dcSSimon Schubert /* An entry in the strtab hash table. */ 6795796c8dcSSimon Schubert 6805796c8dcSSimon Schubert struct strtab_hash_entry 6815796c8dcSSimon Schubert { 6825796c8dcSSimon Schubert struct bfd_hash_entry root; 6835796c8dcSSimon Schubert /* Index in string table. */ 6845796c8dcSSimon Schubert bfd_size_type index; 6855796c8dcSSimon Schubert /* Next string in strtab. */ 6865796c8dcSSimon Schubert struct strtab_hash_entry *next; 6875796c8dcSSimon Schubert }; 6885796c8dcSSimon Schubert 6895796c8dcSSimon Schubert /* The strtab hash table. */ 6905796c8dcSSimon Schubert 6915796c8dcSSimon Schubert struct bfd_strtab_hash 6925796c8dcSSimon Schubert { 6935796c8dcSSimon Schubert struct bfd_hash_table table; 6945796c8dcSSimon Schubert /* Size of strtab--also next available index. */ 6955796c8dcSSimon Schubert bfd_size_type size; 6965796c8dcSSimon Schubert /* First string in strtab. */ 6975796c8dcSSimon Schubert struct strtab_hash_entry *first; 6985796c8dcSSimon Schubert /* Last string in strtab. */ 6995796c8dcSSimon Schubert struct strtab_hash_entry *last; 7005796c8dcSSimon Schubert /* Whether to precede strings with a two byte length, as in the 7015796c8dcSSimon Schubert XCOFF .debug section. */ 7025796c8dcSSimon Schubert bfd_boolean xcoff; 7035796c8dcSSimon Schubert }; 7045796c8dcSSimon Schubert 7055796c8dcSSimon Schubert /* Routine to create an entry in a strtab. */ 7065796c8dcSSimon Schubert 7075796c8dcSSimon Schubert static struct bfd_hash_entry * 7085796c8dcSSimon Schubert strtab_hash_newfunc (struct bfd_hash_entry *entry, 7095796c8dcSSimon Schubert struct bfd_hash_table *table, 7105796c8dcSSimon Schubert const char *string) 7115796c8dcSSimon Schubert { 7125796c8dcSSimon Schubert struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 7135796c8dcSSimon Schubert 7145796c8dcSSimon Schubert /* Allocate the structure if it has not already been allocated by a 7155796c8dcSSimon Schubert subclass. */ 7165796c8dcSSimon Schubert if (ret == NULL) 7175796c8dcSSimon Schubert ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, 7185796c8dcSSimon Schubert sizeof (* ret)); 7195796c8dcSSimon Schubert if (ret == NULL) 7205796c8dcSSimon Schubert return NULL; 7215796c8dcSSimon Schubert 7225796c8dcSSimon Schubert /* Call the allocation method of the superclass. */ 7235796c8dcSSimon Schubert ret = (struct strtab_hash_entry *) 7245796c8dcSSimon Schubert bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 7255796c8dcSSimon Schubert 7265796c8dcSSimon Schubert if (ret) 7275796c8dcSSimon Schubert { 7285796c8dcSSimon Schubert /* Initialize the local fields. */ 7295796c8dcSSimon Schubert ret->index = (bfd_size_type) -1; 7305796c8dcSSimon Schubert ret->next = NULL; 7315796c8dcSSimon Schubert } 7325796c8dcSSimon Schubert 7335796c8dcSSimon Schubert return (struct bfd_hash_entry *) ret; 7345796c8dcSSimon Schubert } 7355796c8dcSSimon Schubert 7365796c8dcSSimon Schubert /* Look up an entry in an strtab. */ 7375796c8dcSSimon Schubert 7385796c8dcSSimon Schubert #define strtab_hash_lookup(t, string, create, copy) \ 7395796c8dcSSimon Schubert ((struct strtab_hash_entry *) \ 7405796c8dcSSimon Schubert bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 7415796c8dcSSimon Schubert 7425796c8dcSSimon Schubert /* Create a new strtab. */ 7435796c8dcSSimon Schubert 7445796c8dcSSimon Schubert struct bfd_strtab_hash * 7455796c8dcSSimon Schubert _bfd_stringtab_init (void) 7465796c8dcSSimon Schubert { 7475796c8dcSSimon Schubert struct bfd_strtab_hash *table; 7485796c8dcSSimon Schubert bfd_size_type amt = sizeof (* table); 7495796c8dcSSimon Schubert 7505796c8dcSSimon Schubert table = (struct bfd_strtab_hash *) bfd_malloc (amt); 7515796c8dcSSimon Schubert if (table == NULL) 7525796c8dcSSimon Schubert return NULL; 7535796c8dcSSimon Schubert 7545796c8dcSSimon Schubert if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 7555796c8dcSSimon Schubert sizeof (struct strtab_hash_entry))) 7565796c8dcSSimon Schubert { 7575796c8dcSSimon Schubert free (table); 7585796c8dcSSimon Schubert return NULL; 7595796c8dcSSimon Schubert } 7605796c8dcSSimon Schubert 7615796c8dcSSimon Schubert table->size = 0; 7625796c8dcSSimon Schubert table->first = NULL; 7635796c8dcSSimon Schubert table->last = NULL; 7645796c8dcSSimon Schubert table->xcoff = FALSE; 7655796c8dcSSimon Schubert 7665796c8dcSSimon Schubert return table; 7675796c8dcSSimon Schubert } 7685796c8dcSSimon Schubert 7695796c8dcSSimon Schubert /* Create a new strtab in which the strings are output in the format 7705796c8dcSSimon Schubert used in the XCOFF .debug section: a two byte length precedes each 7715796c8dcSSimon Schubert string. */ 7725796c8dcSSimon Schubert 7735796c8dcSSimon Schubert struct bfd_strtab_hash * 7745796c8dcSSimon Schubert _bfd_xcoff_stringtab_init (void) 7755796c8dcSSimon Schubert { 7765796c8dcSSimon Schubert struct bfd_strtab_hash *ret; 7775796c8dcSSimon Schubert 7785796c8dcSSimon Schubert ret = _bfd_stringtab_init (); 7795796c8dcSSimon Schubert if (ret != NULL) 7805796c8dcSSimon Schubert ret->xcoff = TRUE; 7815796c8dcSSimon Schubert return ret; 7825796c8dcSSimon Schubert } 7835796c8dcSSimon Schubert 7845796c8dcSSimon Schubert /* Free a strtab. */ 7855796c8dcSSimon Schubert 7865796c8dcSSimon Schubert void 7875796c8dcSSimon Schubert _bfd_stringtab_free (struct bfd_strtab_hash *table) 7885796c8dcSSimon Schubert { 7895796c8dcSSimon Schubert bfd_hash_table_free (&table->table); 7905796c8dcSSimon Schubert free (table); 7915796c8dcSSimon Schubert } 7925796c8dcSSimon Schubert 7935796c8dcSSimon Schubert /* Get the index of a string in a strtab, adding it if it is not 7945796c8dcSSimon Schubert already present. If HASH is FALSE, we don't really use the hash 7955796c8dcSSimon Schubert table, and we don't eliminate duplicate strings. */ 7965796c8dcSSimon Schubert 7975796c8dcSSimon Schubert bfd_size_type 7985796c8dcSSimon Schubert _bfd_stringtab_add (struct bfd_strtab_hash *tab, 7995796c8dcSSimon Schubert const char *str, 8005796c8dcSSimon Schubert bfd_boolean hash, 8015796c8dcSSimon Schubert bfd_boolean copy) 8025796c8dcSSimon Schubert { 8035796c8dcSSimon Schubert struct strtab_hash_entry *entry; 8045796c8dcSSimon Schubert 8055796c8dcSSimon Schubert if (hash) 8065796c8dcSSimon Schubert { 8075796c8dcSSimon Schubert entry = strtab_hash_lookup (tab, str, TRUE, copy); 8085796c8dcSSimon Schubert if (entry == NULL) 8095796c8dcSSimon Schubert return (bfd_size_type) -1; 8105796c8dcSSimon Schubert } 8115796c8dcSSimon Schubert else 8125796c8dcSSimon Schubert { 8135796c8dcSSimon Schubert entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, 8145796c8dcSSimon Schubert sizeof (* entry)); 8155796c8dcSSimon Schubert if (entry == NULL) 8165796c8dcSSimon Schubert return (bfd_size_type) -1; 8175796c8dcSSimon Schubert if (! copy) 8185796c8dcSSimon Schubert entry->root.string = str; 8195796c8dcSSimon Schubert else 8205796c8dcSSimon Schubert { 8215796c8dcSSimon Schubert char *n; 8225796c8dcSSimon Schubert 8235796c8dcSSimon Schubert n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); 8245796c8dcSSimon Schubert if (n == NULL) 8255796c8dcSSimon Schubert return (bfd_size_type) -1; 8265796c8dcSSimon Schubert entry->root.string = n; 8275796c8dcSSimon Schubert } 8285796c8dcSSimon Schubert entry->index = (bfd_size_type) -1; 8295796c8dcSSimon Schubert entry->next = NULL; 8305796c8dcSSimon Schubert } 8315796c8dcSSimon Schubert 8325796c8dcSSimon Schubert if (entry->index == (bfd_size_type) -1) 8335796c8dcSSimon Schubert { 8345796c8dcSSimon Schubert entry->index = tab->size; 8355796c8dcSSimon Schubert tab->size += strlen (str) + 1; 8365796c8dcSSimon Schubert if (tab->xcoff) 8375796c8dcSSimon Schubert { 8385796c8dcSSimon Schubert entry->index += 2; 8395796c8dcSSimon Schubert tab->size += 2; 8405796c8dcSSimon Schubert } 8415796c8dcSSimon Schubert if (tab->first == NULL) 8425796c8dcSSimon Schubert tab->first = entry; 8435796c8dcSSimon Schubert else 8445796c8dcSSimon Schubert tab->last->next = entry; 8455796c8dcSSimon Schubert tab->last = entry; 8465796c8dcSSimon Schubert } 8475796c8dcSSimon Schubert 8485796c8dcSSimon Schubert return entry->index; 8495796c8dcSSimon Schubert } 8505796c8dcSSimon Schubert 8515796c8dcSSimon Schubert /* Get the number of bytes in a strtab. */ 8525796c8dcSSimon Schubert 8535796c8dcSSimon Schubert bfd_size_type 8545796c8dcSSimon Schubert _bfd_stringtab_size (struct bfd_strtab_hash *tab) 8555796c8dcSSimon Schubert { 8565796c8dcSSimon Schubert return tab->size; 8575796c8dcSSimon Schubert } 8585796c8dcSSimon Schubert 8595796c8dcSSimon Schubert /* Write out a strtab. ABFD must already be at the right location in 8605796c8dcSSimon Schubert the file. */ 8615796c8dcSSimon Schubert 8625796c8dcSSimon Schubert bfd_boolean 8635796c8dcSSimon Schubert _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 8645796c8dcSSimon Schubert { 8655796c8dcSSimon Schubert bfd_boolean xcoff; 8665796c8dcSSimon Schubert struct strtab_hash_entry *entry; 8675796c8dcSSimon Schubert 8685796c8dcSSimon Schubert xcoff = tab->xcoff; 8695796c8dcSSimon Schubert 8705796c8dcSSimon Schubert for (entry = tab->first; entry != NULL; entry = entry->next) 8715796c8dcSSimon Schubert { 8725796c8dcSSimon Schubert const char *str; 8735796c8dcSSimon Schubert size_t len; 8745796c8dcSSimon Schubert 8755796c8dcSSimon Schubert str = entry->root.string; 8765796c8dcSSimon Schubert len = strlen (str) + 1; 8775796c8dcSSimon Schubert 8785796c8dcSSimon Schubert if (xcoff) 8795796c8dcSSimon Schubert { 8805796c8dcSSimon Schubert bfd_byte buf[2]; 8815796c8dcSSimon Schubert 8825796c8dcSSimon Schubert /* The output length includes the null byte. */ 8835796c8dcSSimon Schubert bfd_put_16 (abfd, (bfd_vma) len, buf); 8845796c8dcSSimon Schubert if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 8855796c8dcSSimon Schubert return FALSE; 8865796c8dcSSimon Schubert } 8875796c8dcSSimon Schubert 8885796c8dcSSimon Schubert if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 8895796c8dcSSimon Schubert return FALSE; 8905796c8dcSSimon Schubert } 8915796c8dcSSimon Schubert 8925796c8dcSSimon Schubert return TRUE; 8935796c8dcSSimon Schubert } 894