15796c8dcSSimon Schubert /* hash.c -- hash table routines for BFD
25796c8dcSSimon Schubert Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
3*ef5ccd6cSJohn Marino 2006, 2007, 2009, 2010, 2011, 2012 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
higher_prime_number(unsigned long n)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. */
313a45ae5f8SJohn Marino static const unsigned long primes[] =
314a45ae5f8SJohn Marino {
315a45ae5f8SJohn Marino (unsigned long) 31,
316a45ae5f8SJohn Marino (unsigned long) 61,
3175796c8dcSSimon Schubert (unsigned long) 127,
318a45ae5f8SJohn Marino (unsigned long) 251,
319a45ae5f8SJohn Marino (unsigned long) 509,
320a45ae5f8SJohn Marino (unsigned long) 1021,
3215796c8dcSSimon Schubert (unsigned long) 2039,
322a45ae5f8SJohn Marino (unsigned long) 4093,
323a45ae5f8SJohn Marino (unsigned long) 8191,
324a45ae5f8SJohn 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
364a45ae5f8SJohn 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
bfd_hash_table_init_n(struct bfd_hash_table * table,struct bfd_hash_entry * (* newfunc)(struct bfd_hash_entry *,struct bfd_hash_table *,const char *),unsigned int entsize,unsigned int size)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 {
376a45ae5f8SJohn Marino unsigned long alloc;
3775796c8dcSSimon Schubert
378a45ae5f8SJohn Marino alloc = size;
379a45ae5f8SJohn Marino alloc *= sizeof (struct bfd_hash_entry *);
380a45ae5f8SJohn Marino if (alloc / sizeof (struct bfd_hash_entry *) != size)
381a45ae5f8SJohn Marino {
382a45ae5f8SJohn Marino bfd_set_error (bfd_error_no_memory);
383a45ae5f8SJohn Marino return FALSE;
384a45ae5f8SJohn 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
bfd_hash_table_init(struct bfd_hash_table * table,struct bfd_hash_entry * (* newfunc)(struct bfd_hash_entry *,struct bfd_hash_table *,const char *),unsigned int entsize)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
bfd_hash_table_free(struct bfd_hash_table * table)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
bfd_hash_hash(const char * string,unsigned int * lenp)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 *
bfd_hash_lookup(struct bfd_hash_table * table,const char * string,bfd_boolean create,bfd_boolean copy)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 *
bfd_hash_insert(struct bfd_hash_table * table,const char * string,unsigned long hash)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 }
541*ef5ccd6cSJohn Marino memset (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
bfd_hash_rename(struct bfd_hash_table * table,const char * string,struct bfd_hash_entry * ent)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
bfd_hash_replace(struct bfd_hash_table * table,struct bfd_hash_entry * old,struct bfd_hash_entry * nw)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 *
bfd_hash_allocate(struct bfd_hash_table * table,unsigned int size)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 *
bfd_hash_newfunc(struct bfd_hash_entry * entry,struct bfd_hash_table * table,const char * string ATTRIBUTE_UNUSED)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
bfd_hash_traverse(struct bfd_hash_table * table,bfd_boolean (* func)(struct bfd_hash_entry *,void *),void * info)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
663a45ae5f8SJohn Marino unsigned long
bfd_hash_set_default_size(unsigned long hash_size)664a45ae5f8SJohn 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. */
667a45ae5f8SJohn Marino static const unsigned long hash_size_primes[] =
6685796c8dcSSimon Schubert {
669a45ae5f8SJohn Marino 31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537
6705796c8dcSSimon Schubert };
671a45ae5f8SJohn 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];
679a45ae5f8SJohn 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 *
strtab_hash_newfunc(struct bfd_hash_entry * entry,struct bfd_hash_table * table,const char * string)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 *
_bfd_stringtab_init(void)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 *
_bfd_xcoff_stringtab_init(void)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
_bfd_stringtab_free(struct bfd_strtab_hash * table)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
_bfd_stringtab_add(struct bfd_strtab_hash * tab,const char * str,bfd_boolean hash,bfd_boolean copy)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
_bfd_stringtab_size(struct bfd_strtab_hash * tab)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
_bfd_stringtab_emit(bfd * abfd,struct bfd_strtab_hash * tab)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