1*fae548d3Szrj /* hash.c -- hash table routines for BFD
2*fae548d3Szrj Copyright (C) 1993-2020 Free Software Foundation, Inc.
3*fae548d3Szrj Written by Steve Chamberlain <sac@cygnus.com>
4*fae548d3Szrj
5*fae548d3Szrj This file is part of BFD, the Binary File Descriptor library.
6*fae548d3Szrj
7*fae548d3Szrj This program is free software; you can redistribute it and/or modify
8*fae548d3Szrj it under the terms of the GNU General Public License as published by
9*fae548d3Szrj the Free Software Foundation; either version 3 of the License, or
10*fae548d3Szrj (at your option) any later version.
11*fae548d3Szrj
12*fae548d3Szrj This program is distributed in the hope that it will be useful,
13*fae548d3Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
14*fae548d3Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15*fae548d3Szrj GNU General Public License for more details.
16*fae548d3Szrj
17*fae548d3Szrj You should have received a copy of the GNU General Public License
18*fae548d3Szrj along with this program; if not, write to the Free Software
19*fae548d3Szrj Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
20*fae548d3Szrj MA 02110-1301, USA. */
21*fae548d3Szrj
22*fae548d3Szrj #include "sysdep.h"
23*fae548d3Szrj #include "bfd.h"
24*fae548d3Szrj #include "libbfd.h"
25*fae548d3Szrj #include "objalloc.h"
26*fae548d3Szrj #include "libiberty.h"
27*fae548d3Szrj
28*fae548d3Szrj /*
29*fae548d3Szrj SECTION
30*fae548d3Szrj Hash Tables
31*fae548d3Szrj
32*fae548d3Szrj @cindex Hash tables
33*fae548d3Szrj BFD provides a simple set of hash table functions. Routines
34*fae548d3Szrj are provided to initialize a hash table, to free a hash table,
35*fae548d3Szrj to look up a string in a hash table and optionally create an
36*fae548d3Szrj entry for it, and to traverse a hash table. There is
37*fae548d3Szrj currently no routine to delete an string from a hash table.
38*fae548d3Szrj
39*fae548d3Szrj The basic hash table does not permit any data to be stored
40*fae548d3Szrj with a string. However, a hash table is designed to present a
41*fae548d3Szrj base class from which other types of hash tables may be
42*fae548d3Szrj derived. These derived types may store additional information
43*fae548d3Szrj with the string. Hash tables were implemented in this way,
44*fae548d3Szrj rather than simply providing a data pointer in a hash table
45*fae548d3Szrj entry, because they were designed for use by the linker back
46*fae548d3Szrj ends. The linker may create thousands of hash table entries,
47*fae548d3Szrj and the overhead of allocating private data and storing and
48*fae548d3Szrj following pointers becomes noticeable.
49*fae548d3Szrj
50*fae548d3Szrj The basic hash table code is in <<hash.c>>.
51*fae548d3Szrj
52*fae548d3Szrj @menu
53*fae548d3Szrj @* Creating and Freeing a Hash Table::
54*fae548d3Szrj @* Looking Up or Entering a String::
55*fae548d3Szrj @* Traversing a Hash Table::
56*fae548d3Szrj @* Deriving a New Hash Table Type::
57*fae548d3Szrj @end menu
58*fae548d3Szrj
59*fae548d3Szrj INODE
60*fae548d3Szrj Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
61*fae548d3Szrj SUBSECTION
62*fae548d3Szrj Creating and freeing a hash table
63*fae548d3Szrj
64*fae548d3Szrj @findex bfd_hash_table_init
65*fae548d3Szrj @findex bfd_hash_table_init_n
66*fae548d3Szrj To create a hash table, create an instance of a <<struct
67*fae548d3Szrj bfd_hash_table>> (defined in <<bfd.h>>) and call
68*fae548d3Szrj <<bfd_hash_table_init>> (if you know approximately how many
69*fae548d3Szrj entries you will need, the function <<bfd_hash_table_init_n>>,
70*fae548d3Szrj which takes a @var{size} argument, may be used).
71*fae548d3Szrj <<bfd_hash_table_init>> returns <<FALSE>> if some sort of
72*fae548d3Szrj error occurs.
73*fae548d3Szrj
74*fae548d3Szrj @findex bfd_hash_newfunc
75*fae548d3Szrj The function <<bfd_hash_table_init>> take as an argument a
76*fae548d3Szrj function to use to create new entries. For a basic hash
77*fae548d3Szrj table, use the function <<bfd_hash_newfunc>>. @xref{Deriving
78*fae548d3Szrj a New Hash Table Type}, for why you would want to use a
79*fae548d3Szrj different value for this argument.
80*fae548d3Szrj
81*fae548d3Szrj @findex bfd_hash_allocate
82*fae548d3Szrj <<bfd_hash_table_init>> will create an objalloc which will be
83*fae548d3Szrj used to allocate new entries. You may allocate memory on this
84*fae548d3Szrj objalloc using <<bfd_hash_allocate>>.
85*fae548d3Szrj
86*fae548d3Szrj @findex bfd_hash_table_free
87*fae548d3Szrj Use <<bfd_hash_table_free>> to free up all the memory that has
88*fae548d3Szrj been allocated for a hash table. This will not free up the
89*fae548d3Szrj <<struct bfd_hash_table>> itself, which you must provide.
90*fae548d3Szrj
91*fae548d3Szrj @findex bfd_hash_set_default_size
92*fae548d3Szrj Use <<bfd_hash_set_default_size>> to set the default size of
93*fae548d3Szrj hash table to use.
94*fae548d3Szrj
95*fae548d3Szrj INODE
96*fae548d3Szrj Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
97*fae548d3Szrj SUBSECTION
98*fae548d3Szrj Looking up or entering a string
99*fae548d3Szrj
100*fae548d3Szrj @findex bfd_hash_lookup
101*fae548d3Szrj The function <<bfd_hash_lookup>> is used both to look up a
102*fae548d3Szrj string in the hash table and to create a new entry.
103*fae548d3Szrj
104*fae548d3Szrj If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>>
105*fae548d3Szrj will look up a string. If the string is found, it will
106*fae548d3Szrj returns a pointer to a <<struct bfd_hash_entry>>. If the
107*fae548d3Szrj string is not found in the table <<bfd_hash_lookup>> will
108*fae548d3Szrj return <<NULL>>. You should not modify any of the fields in
109*fae548d3Szrj the returns <<struct bfd_hash_entry>>.
110*fae548d3Szrj
111*fae548d3Szrj If the @var{create} argument is <<TRUE>>, the string will be
112*fae548d3Szrj entered into the hash table if it is not already there.
113*fae548d3Szrj Either way a pointer to a <<struct bfd_hash_entry>> will be
114*fae548d3Szrj returned, either to the existing structure or to a newly
115*fae548d3Szrj created one. In this case, a <<NULL>> return means that an
116*fae548d3Szrj error occurred.
117*fae548d3Szrj
118*fae548d3Szrj If the @var{create} argument is <<TRUE>>, and a new entry is
119*fae548d3Szrj created, the @var{copy} argument is used to decide whether to
120*fae548d3Szrj copy the string onto the hash table objalloc or not. If
121*fae548d3Szrj @var{copy} is passed as <<FALSE>>, you must be careful not to
122*fae548d3Szrj deallocate or modify the string as long as the hash table
123*fae548d3Szrj exists.
124*fae548d3Szrj
125*fae548d3Szrj INODE
126*fae548d3Szrj Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
127*fae548d3Szrj SUBSECTION
128*fae548d3Szrj Traversing a hash table
129*fae548d3Szrj
130*fae548d3Szrj @findex bfd_hash_traverse
131*fae548d3Szrj The function <<bfd_hash_traverse>> may be used to traverse a
132*fae548d3Szrj hash table, calling a function on each element. The traversal
133*fae548d3Szrj is done in a random order.
134*fae548d3Szrj
135*fae548d3Szrj <<bfd_hash_traverse>> takes as arguments a function and a
136*fae548d3Szrj generic <<void *>> pointer. The function is called with a
137*fae548d3Szrj hash table entry (a <<struct bfd_hash_entry *>>) and the
138*fae548d3Szrj generic pointer passed to <<bfd_hash_traverse>>. The function
139*fae548d3Szrj must return a <<boolean>> value, which indicates whether to
140*fae548d3Szrj continue traversing the hash table. If the function returns
141*fae548d3Szrj <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and
142*fae548d3Szrj return immediately.
143*fae548d3Szrj
144*fae548d3Szrj INODE
145*fae548d3Szrj Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
146*fae548d3Szrj SUBSECTION
147*fae548d3Szrj Deriving a new hash table type
148*fae548d3Szrj
149*fae548d3Szrj Many uses of hash tables want to store additional information
150*fae548d3Szrj which each entry in the hash table. Some also find it
151*fae548d3Szrj convenient to store additional information with the hash table
152*fae548d3Szrj itself. This may be done using a derived hash table.
153*fae548d3Szrj
154*fae548d3Szrj Since C is not an object oriented language, creating a derived
155*fae548d3Szrj hash table requires sticking together some boilerplate
156*fae548d3Szrj routines with a few differences specific to the type of hash
157*fae548d3Szrj table you want to create.
158*fae548d3Szrj
159*fae548d3Szrj An example of a derived hash table is the linker hash table.
160*fae548d3Szrj The structures for this are defined in <<bfdlink.h>>. The
161*fae548d3Szrj functions are in <<linker.c>>.
162*fae548d3Szrj
163*fae548d3Szrj You may also derive a hash table from an already derived hash
164*fae548d3Szrj table. For example, the a.out linker backend code uses a hash
165*fae548d3Szrj table derived from the linker hash table.
166*fae548d3Szrj
167*fae548d3Szrj @menu
168*fae548d3Szrj @* Define the Derived Structures::
169*fae548d3Szrj @* Write the Derived Creation Routine::
170*fae548d3Szrj @* Write Other Derived Routines::
171*fae548d3Szrj @end menu
172*fae548d3Szrj
173*fae548d3Szrj INODE
174*fae548d3Szrj Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
175*fae548d3Szrj SUBSUBSECTION
176*fae548d3Szrj Define the derived structures
177*fae548d3Szrj
178*fae548d3Szrj You must define a structure for an entry in the hash table,
179*fae548d3Szrj and a structure for the hash table itself.
180*fae548d3Szrj
181*fae548d3Szrj The first field in the structure for an entry in the hash
182*fae548d3Szrj table must be of the type used for an entry in the hash table
183*fae548d3Szrj you are deriving from. If you are deriving from a basic hash
184*fae548d3Szrj table this is <<struct bfd_hash_entry>>, which is defined in
185*fae548d3Szrj <<bfd.h>>. The first field in the structure for the hash
186*fae548d3Szrj table itself must be of the type of the hash table you are
187*fae548d3Szrj deriving from itself. If you are deriving from a basic hash
188*fae548d3Szrj table, this is <<struct bfd_hash_table>>.
189*fae548d3Szrj
190*fae548d3Szrj For example, the linker hash table defines <<struct
191*fae548d3Szrj bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field,
192*fae548d3Szrj <<root>>, is of type <<struct bfd_hash_entry>>. Similarly,
193*fae548d3Szrj the first field in <<struct bfd_link_hash_table>>, <<table>>,
194*fae548d3Szrj is of type <<struct bfd_hash_table>>.
195*fae548d3Szrj
196*fae548d3Szrj INODE
197*fae548d3Szrj Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
198*fae548d3Szrj SUBSUBSECTION
199*fae548d3Szrj Write the derived creation routine
200*fae548d3Szrj
201*fae548d3Szrj You must write a routine which will create and initialize an
202*fae548d3Szrj entry in the hash table. This routine is passed as the
203*fae548d3Szrj function argument to <<bfd_hash_table_init>>.
204*fae548d3Szrj
205*fae548d3Szrj In order to permit other hash tables to be derived from the
206*fae548d3Szrj hash table you are creating, this routine must be written in a
207*fae548d3Szrj standard way.
208*fae548d3Szrj
209*fae548d3Szrj The first argument to the creation routine is a pointer to a
210*fae548d3Szrj hash table entry. This may be <<NULL>>, in which case the
211*fae548d3Szrj routine should allocate the right amount of space. Otherwise
212*fae548d3Szrj the space has already been allocated by a hash table type
213*fae548d3Szrj derived from this one.
214*fae548d3Szrj
215*fae548d3Szrj After allocating space, the creation routine must call the
216*fae548d3Szrj creation routine of the hash table type it is derived from,
217*fae548d3Szrj passing in a pointer to the space it just allocated. This
218*fae548d3Szrj will initialize any fields used by the base hash table.
219*fae548d3Szrj
220*fae548d3Szrj Finally the creation routine must initialize any local fields
221*fae548d3Szrj for the new hash table type.
222*fae548d3Szrj
223*fae548d3Szrj Here is a boilerplate example of a creation routine.
224*fae548d3Szrj @var{function_name} is the name of the routine.
225*fae548d3Szrj @var{entry_type} is the type of an entry in the hash table you
226*fae548d3Szrj are creating. @var{base_newfunc} is the name of the creation
227*fae548d3Szrj routine of the hash table type your hash table is derived
228*fae548d3Szrj from.
229*fae548d3Szrj
230*fae548d3Szrj EXAMPLE
231*fae548d3Szrj
232*fae548d3Szrj .struct bfd_hash_entry *
233*fae548d3Szrj .@var{function_name} (struct bfd_hash_entry *entry,
234*fae548d3Szrj . struct bfd_hash_table *table,
235*fae548d3Szrj . const char *string)
236*fae548d3Szrj .{
237*fae548d3Szrj . struct @var{entry_type} *ret = (@var{entry_type} *) entry;
238*fae548d3Szrj .
239*fae548d3Szrj . {* Allocate the structure if it has not already been allocated by a
240*fae548d3Szrj . derived class. *}
241*fae548d3Szrj . if (ret == NULL)
242*fae548d3Szrj . {
243*fae548d3Szrj . ret = bfd_hash_allocate (table, sizeof (* ret));
244*fae548d3Szrj . if (ret == NULL)
245*fae548d3Szrj . return NULL;
246*fae548d3Szrj . }
247*fae548d3Szrj .
248*fae548d3Szrj . {* Call the allocation method of the base class. *}
249*fae548d3Szrj . ret = ((@var{entry_type} *)
250*fae548d3Szrj . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
251*fae548d3Szrj .
252*fae548d3Szrj . {* Initialize the local fields here. *}
253*fae548d3Szrj .
254*fae548d3Szrj . return (struct bfd_hash_entry *) ret;
255*fae548d3Szrj .}
256*fae548d3Szrj
257*fae548d3Szrj DESCRIPTION
258*fae548d3Szrj The creation routine for the linker hash table, which is in
259*fae548d3Szrj <<linker.c>>, looks just like this example.
260*fae548d3Szrj @var{function_name} is <<_bfd_link_hash_newfunc>>.
261*fae548d3Szrj @var{entry_type} is <<struct bfd_link_hash_entry>>.
262*fae548d3Szrj @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
263*fae548d3Szrj routine for a basic hash table.
264*fae548d3Szrj
265*fae548d3Szrj <<_bfd_link_hash_newfunc>> also initializes the local fields
266*fae548d3Szrj in a linker hash table entry: <<type>>, <<written>> and
267*fae548d3Szrj <<next>>.
268*fae548d3Szrj
269*fae548d3Szrj INODE
270*fae548d3Szrj Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
271*fae548d3Szrj SUBSUBSECTION
272*fae548d3Szrj Write other derived routines
273*fae548d3Szrj
274*fae548d3Szrj You will want to write other routines for your new hash table,
275*fae548d3Szrj as well.
276*fae548d3Szrj
277*fae548d3Szrj You will want an initialization routine which calls the
278*fae548d3Szrj initialization routine of the hash table you are deriving from
279*fae548d3Szrj and initializes any other local fields. For the linker hash
280*fae548d3Szrj table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
281*fae548d3Szrj
282*fae548d3Szrj You will want a lookup routine which calls the lookup routine
283*fae548d3Szrj of the hash table you are deriving from and casts the result.
284*fae548d3Szrj The linker hash table uses <<bfd_link_hash_lookup>> in
285*fae548d3Szrj <<linker.c>> (this actually takes an additional argument which
286*fae548d3Szrj it uses to decide how to return the looked up value).
287*fae548d3Szrj
288*fae548d3Szrj You may want a traversal routine. This should just call the
289*fae548d3Szrj traversal routine of the hash table you are deriving from with
290*fae548d3Szrj appropriate casts. The linker hash table uses
291*fae548d3Szrj <<bfd_link_hash_traverse>> in <<linker.c>>.
292*fae548d3Szrj
293*fae548d3Szrj These routines may simply be defined as macros. For example,
294*fae548d3Szrj the a.out backend linker hash table, which is derived from the
295*fae548d3Szrj linker hash table, uses macros for the lookup and traversal
296*fae548d3Szrj routines. These are <<aout_link_hash_lookup>> and
297*fae548d3Szrj <<aout_link_hash_traverse>> in aoutx.h.
298*fae548d3Szrj */
299*fae548d3Szrj
300*fae548d3Szrj /* The default number of entries to use when creating a hash table. */
301*fae548d3Szrj #define DEFAULT_SIZE 4051
302*fae548d3Szrj
303*fae548d3Szrj /* The following function returns a nearest prime number which is
304*fae548d3Szrj greater than N, and near a power of two. Copied from libiberty.
305*fae548d3Szrj Returns zero for ridiculously large N to signify an error. */
306*fae548d3Szrj
307*fae548d3Szrj static unsigned long
higher_prime_number(unsigned long n)308*fae548d3Szrj higher_prime_number (unsigned long n)
309*fae548d3Szrj {
310*fae548d3Szrj /* These are primes that are near, but slightly smaller than, a
311*fae548d3Szrj power of two. */
312*fae548d3Szrj static const unsigned long primes[] =
313*fae548d3Szrj {
314*fae548d3Szrj (unsigned long) 31,
315*fae548d3Szrj (unsigned long) 61,
316*fae548d3Szrj (unsigned long) 127,
317*fae548d3Szrj (unsigned long) 251,
318*fae548d3Szrj (unsigned long) 509,
319*fae548d3Szrj (unsigned long) 1021,
320*fae548d3Szrj (unsigned long) 2039,
321*fae548d3Szrj (unsigned long) 4093,
322*fae548d3Szrj (unsigned long) 8191,
323*fae548d3Szrj (unsigned long) 16381,
324*fae548d3Szrj (unsigned long) 32749,
325*fae548d3Szrj (unsigned long) 65521,
326*fae548d3Szrj (unsigned long) 131071,
327*fae548d3Szrj (unsigned long) 262139,
328*fae548d3Szrj (unsigned long) 524287,
329*fae548d3Szrj (unsigned long) 1048573,
330*fae548d3Szrj (unsigned long) 2097143,
331*fae548d3Szrj (unsigned long) 4194301,
332*fae548d3Szrj (unsigned long) 8388593,
333*fae548d3Szrj (unsigned long) 16777213,
334*fae548d3Szrj (unsigned long) 33554393,
335*fae548d3Szrj (unsigned long) 67108859,
336*fae548d3Szrj (unsigned long) 134217689,
337*fae548d3Szrj (unsigned long) 268435399,
338*fae548d3Szrj (unsigned long) 536870909,
339*fae548d3Szrj (unsigned long) 1073741789,
340*fae548d3Szrj (unsigned long) 2147483647,
341*fae548d3Szrj /* 4294967291L */
342*fae548d3Szrj ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
343*fae548d3Szrj };
344*fae548d3Szrj
345*fae548d3Szrj const unsigned long *low = &primes[0];
346*fae548d3Szrj const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
347*fae548d3Szrj
348*fae548d3Szrj while (low != high)
349*fae548d3Szrj {
350*fae548d3Szrj const unsigned long *mid = low + (high - low) / 2;
351*fae548d3Szrj if (n >= *mid)
352*fae548d3Szrj low = mid + 1;
353*fae548d3Szrj else
354*fae548d3Szrj high = mid;
355*fae548d3Szrj }
356*fae548d3Szrj
357*fae548d3Szrj if (n >= *low)
358*fae548d3Szrj return 0;
359*fae548d3Szrj
360*fae548d3Szrj return *low;
361*fae548d3Szrj }
362*fae548d3Szrj
363*fae548d3Szrj static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE;
364*fae548d3Szrj
365*fae548d3Szrj /* Create a new hash table, given a number of entries. */
366*fae548d3Szrj
367*fae548d3Szrj 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)368*fae548d3Szrj bfd_hash_table_init_n (struct bfd_hash_table *table,
369*fae548d3Szrj struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
370*fae548d3Szrj struct bfd_hash_table *,
371*fae548d3Szrj const char *),
372*fae548d3Szrj unsigned int entsize,
373*fae548d3Szrj unsigned int size)
374*fae548d3Szrj {
375*fae548d3Szrj unsigned long alloc;
376*fae548d3Szrj
377*fae548d3Szrj alloc = size;
378*fae548d3Szrj alloc *= sizeof (struct bfd_hash_entry *);
379*fae548d3Szrj if (alloc / sizeof (struct bfd_hash_entry *) != size)
380*fae548d3Szrj {
381*fae548d3Szrj bfd_set_error (bfd_error_no_memory);
382*fae548d3Szrj return FALSE;
383*fae548d3Szrj }
384*fae548d3Szrj
385*fae548d3Szrj table->memory = (void *) objalloc_create ();
386*fae548d3Szrj if (table->memory == NULL)
387*fae548d3Szrj {
388*fae548d3Szrj bfd_set_error (bfd_error_no_memory);
389*fae548d3Szrj return FALSE;
390*fae548d3Szrj }
391*fae548d3Szrj table->table = (struct bfd_hash_entry **)
392*fae548d3Szrj objalloc_alloc ((struct objalloc *) table->memory, alloc);
393*fae548d3Szrj if (table->table == NULL)
394*fae548d3Szrj {
395*fae548d3Szrj bfd_hash_table_free (table);
396*fae548d3Szrj bfd_set_error (bfd_error_no_memory);
397*fae548d3Szrj return FALSE;
398*fae548d3Szrj }
399*fae548d3Szrj memset ((void *) table->table, 0, alloc);
400*fae548d3Szrj table->size = size;
401*fae548d3Szrj table->entsize = entsize;
402*fae548d3Szrj table->count = 0;
403*fae548d3Szrj table->frozen = 0;
404*fae548d3Szrj table->newfunc = newfunc;
405*fae548d3Szrj return TRUE;
406*fae548d3Szrj }
407*fae548d3Szrj
408*fae548d3Szrj /* Create a new hash table with the default number of entries. */
409*fae548d3Szrj
410*fae548d3Szrj 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)411*fae548d3Szrj bfd_hash_table_init (struct bfd_hash_table *table,
412*fae548d3Szrj struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
413*fae548d3Szrj struct bfd_hash_table *,
414*fae548d3Szrj const char *),
415*fae548d3Szrj unsigned int entsize)
416*fae548d3Szrj {
417*fae548d3Szrj return bfd_hash_table_init_n (table, newfunc, entsize,
418*fae548d3Szrj bfd_default_hash_table_size);
419*fae548d3Szrj }
420*fae548d3Szrj
421*fae548d3Szrj /* Free a hash table. */
422*fae548d3Szrj
423*fae548d3Szrj void
bfd_hash_table_free(struct bfd_hash_table * table)424*fae548d3Szrj bfd_hash_table_free (struct bfd_hash_table *table)
425*fae548d3Szrj {
426*fae548d3Szrj objalloc_free ((struct objalloc *) table->memory);
427*fae548d3Szrj table->memory = NULL;
428*fae548d3Szrj }
429*fae548d3Szrj
430*fae548d3Szrj static inline unsigned long
bfd_hash_hash(const char * string,unsigned int * lenp)431*fae548d3Szrj bfd_hash_hash (const char *string, unsigned int *lenp)
432*fae548d3Szrj {
433*fae548d3Szrj const unsigned char *s;
434*fae548d3Szrj unsigned long hash;
435*fae548d3Szrj unsigned int len;
436*fae548d3Szrj unsigned int c;
437*fae548d3Szrj
438*fae548d3Szrj BFD_ASSERT (string != NULL);
439*fae548d3Szrj hash = 0;
440*fae548d3Szrj len = 0;
441*fae548d3Szrj s = (const unsigned char *) string;
442*fae548d3Szrj while ((c = *s++) != '\0')
443*fae548d3Szrj {
444*fae548d3Szrj hash += c + (c << 17);
445*fae548d3Szrj hash ^= hash >> 2;
446*fae548d3Szrj }
447*fae548d3Szrj len = (s - (const unsigned char *) string) - 1;
448*fae548d3Szrj hash += len + (len << 17);
449*fae548d3Szrj hash ^= hash >> 2;
450*fae548d3Szrj if (lenp != NULL)
451*fae548d3Szrj *lenp = len;
452*fae548d3Szrj return hash;
453*fae548d3Szrj }
454*fae548d3Szrj
455*fae548d3Szrj /* Look up a string in a hash table. */
456*fae548d3Szrj
457*fae548d3Szrj struct bfd_hash_entry *
bfd_hash_lookup(struct bfd_hash_table * table,const char * string,bfd_boolean create,bfd_boolean copy)458*fae548d3Szrj bfd_hash_lookup (struct bfd_hash_table *table,
459*fae548d3Szrj const char *string,
460*fae548d3Szrj bfd_boolean create,
461*fae548d3Szrj bfd_boolean copy)
462*fae548d3Szrj {
463*fae548d3Szrj unsigned long hash;
464*fae548d3Szrj struct bfd_hash_entry *hashp;
465*fae548d3Szrj unsigned int len;
466*fae548d3Szrj unsigned int _index;
467*fae548d3Szrj
468*fae548d3Szrj hash = bfd_hash_hash (string, &len);
469*fae548d3Szrj _index = hash % table->size;
470*fae548d3Szrj for (hashp = table->table[_index];
471*fae548d3Szrj hashp != NULL;
472*fae548d3Szrj hashp = hashp->next)
473*fae548d3Szrj {
474*fae548d3Szrj if (hashp->hash == hash
475*fae548d3Szrj && strcmp (hashp->string, string) == 0)
476*fae548d3Szrj return hashp;
477*fae548d3Szrj }
478*fae548d3Szrj
479*fae548d3Szrj if (! create)
480*fae548d3Szrj return NULL;
481*fae548d3Szrj
482*fae548d3Szrj if (copy)
483*fae548d3Szrj {
484*fae548d3Szrj char *new_string;
485*fae548d3Szrj
486*fae548d3Szrj new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
487*fae548d3Szrj len + 1);
488*fae548d3Szrj if (!new_string)
489*fae548d3Szrj {
490*fae548d3Szrj bfd_set_error (bfd_error_no_memory);
491*fae548d3Szrj return NULL;
492*fae548d3Szrj }
493*fae548d3Szrj memcpy (new_string, string, len + 1);
494*fae548d3Szrj string = new_string;
495*fae548d3Szrj }
496*fae548d3Szrj
497*fae548d3Szrj return bfd_hash_insert (table, string, hash);
498*fae548d3Szrj }
499*fae548d3Szrj
500*fae548d3Szrj /* Insert an entry in a hash table. */
501*fae548d3Szrj
502*fae548d3Szrj struct bfd_hash_entry *
bfd_hash_insert(struct bfd_hash_table * table,const char * string,unsigned long hash)503*fae548d3Szrj bfd_hash_insert (struct bfd_hash_table *table,
504*fae548d3Szrj const char *string,
505*fae548d3Szrj unsigned long hash)
506*fae548d3Szrj {
507*fae548d3Szrj struct bfd_hash_entry *hashp;
508*fae548d3Szrj unsigned int _index;
509*fae548d3Szrj
510*fae548d3Szrj hashp = (*table->newfunc) (NULL, table, string);
511*fae548d3Szrj if (hashp == NULL)
512*fae548d3Szrj return NULL;
513*fae548d3Szrj hashp->string = string;
514*fae548d3Szrj hashp->hash = hash;
515*fae548d3Szrj _index = hash % table->size;
516*fae548d3Szrj hashp->next = table->table[_index];
517*fae548d3Szrj table->table[_index] = hashp;
518*fae548d3Szrj table->count++;
519*fae548d3Szrj
520*fae548d3Szrj if (!table->frozen && table->count > table->size * 3 / 4)
521*fae548d3Szrj {
522*fae548d3Szrj unsigned long newsize = higher_prime_number (table->size);
523*fae548d3Szrj struct bfd_hash_entry **newtable;
524*fae548d3Szrj unsigned int hi;
525*fae548d3Szrj unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
526*fae548d3Szrj
527*fae548d3Szrj /* If we can't find a higher prime, or we can't possibly alloc
528*fae548d3Szrj that much memory, don't try to grow the table. */
529*fae548d3Szrj if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
530*fae548d3Szrj {
531*fae548d3Szrj table->frozen = 1;
532*fae548d3Szrj return hashp;
533*fae548d3Szrj }
534*fae548d3Szrj
535*fae548d3Szrj newtable = ((struct bfd_hash_entry **)
536*fae548d3Szrj objalloc_alloc ((struct objalloc *) table->memory, alloc));
537*fae548d3Szrj if (newtable == NULL)
538*fae548d3Szrj {
539*fae548d3Szrj table->frozen = 1;
540*fae548d3Szrj return hashp;
541*fae548d3Szrj }
542*fae548d3Szrj memset (newtable, 0, alloc);
543*fae548d3Szrj
544*fae548d3Szrj for (hi = 0; hi < table->size; hi ++)
545*fae548d3Szrj while (table->table[hi])
546*fae548d3Szrj {
547*fae548d3Szrj struct bfd_hash_entry *chain = table->table[hi];
548*fae548d3Szrj struct bfd_hash_entry *chain_end = chain;
549*fae548d3Szrj
550*fae548d3Szrj while (chain_end->next && chain_end->next->hash == chain->hash)
551*fae548d3Szrj chain_end = chain_end->next;
552*fae548d3Szrj
553*fae548d3Szrj table->table[hi] = chain_end->next;
554*fae548d3Szrj _index = chain->hash % newsize;
555*fae548d3Szrj chain_end->next = newtable[_index];
556*fae548d3Szrj newtable[_index] = chain;
557*fae548d3Szrj }
558*fae548d3Szrj table->table = newtable;
559*fae548d3Szrj table->size = newsize;
560*fae548d3Szrj }
561*fae548d3Szrj
562*fae548d3Szrj return hashp;
563*fae548d3Szrj }
564*fae548d3Szrj
565*fae548d3Szrj /* Rename an entry in a hash table. */
566*fae548d3Szrj
567*fae548d3Szrj void
bfd_hash_rename(struct bfd_hash_table * table,const char * string,struct bfd_hash_entry * ent)568*fae548d3Szrj bfd_hash_rename (struct bfd_hash_table *table,
569*fae548d3Szrj const char *string,
570*fae548d3Szrj struct bfd_hash_entry *ent)
571*fae548d3Szrj {
572*fae548d3Szrj unsigned int _index;
573*fae548d3Szrj struct bfd_hash_entry **pph;
574*fae548d3Szrj
575*fae548d3Szrj _index = ent->hash % table->size;
576*fae548d3Szrj for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
577*fae548d3Szrj if (*pph == ent)
578*fae548d3Szrj break;
579*fae548d3Szrj if (*pph == NULL)
580*fae548d3Szrj abort ();
581*fae548d3Szrj
582*fae548d3Szrj *pph = ent->next;
583*fae548d3Szrj ent->string = string;
584*fae548d3Szrj ent->hash = bfd_hash_hash (string, NULL);
585*fae548d3Szrj _index = ent->hash % table->size;
586*fae548d3Szrj ent->next = table->table[_index];
587*fae548d3Szrj table->table[_index] = ent;
588*fae548d3Szrj }
589*fae548d3Szrj
590*fae548d3Szrj /* Replace an entry in a hash table. */
591*fae548d3Szrj
592*fae548d3Szrj void
bfd_hash_replace(struct bfd_hash_table * table,struct bfd_hash_entry * old,struct bfd_hash_entry * nw)593*fae548d3Szrj bfd_hash_replace (struct bfd_hash_table *table,
594*fae548d3Szrj struct bfd_hash_entry *old,
595*fae548d3Szrj struct bfd_hash_entry *nw)
596*fae548d3Szrj {
597*fae548d3Szrj unsigned int _index;
598*fae548d3Szrj struct bfd_hash_entry **pph;
599*fae548d3Szrj
600*fae548d3Szrj _index = old->hash % table->size;
601*fae548d3Szrj for (pph = &table->table[_index];
602*fae548d3Szrj (*pph) != NULL;
603*fae548d3Szrj pph = &(*pph)->next)
604*fae548d3Szrj {
605*fae548d3Szrj if (*pph == old)
606*fae548d3Szrj {
607*fae548d3Szrj *pph = nw;
608*fae548d3Szrj return;
609*fae548d3Szrj }
610*fae548d3Szrj }
611*fae548d3Szrj
612*fae548d3Szrj abort ();
613*fae548d3Szrj }
614*fae548d3Szrj
615*fae548d3Szrj /* Allocate space in a hash table. */
616*fae548d3Szrj
617*fae548d3Szrj void *
bfd_hash_allocate(struct bfd_hash_table * table,unsigned int size)618*fae548d3Szrj bfd_hash_allocate (struct bfd_hash_table *table,
619*fae548d3Szrj unsigned int size)
620*fae548d3Szrj {
621*fae548d3Szrj void * ret;
622*fae548d3Szrj
623*fae548d3Szrj ret = objalloc_alloc ((struct objalloc *) table->memory, size);
624*fae548d3Szrj if (ret == NULL && size != 0)
625*fae548d3Szrj bfd_set_error (bfd_error_no_memory);
626*fae548d3Szrj return ret;
627*fae548d3Szrj }
628*fae548d3Szrj
629*fae548d3Szrj /* Base method for creating a new hash table entry. */
630*fae548d3Szrj
631*fae548d3Szrj struct bfd_hash_entry *
bfd_hash_newfunc(struct bfd_hash_entry * entry,struct bfd_hash_table * table,const char * string ATTRIBUTE_UNUSED)632*fae548d3Szrj bfd_hash_newfunc (struct bfd_hash_entry *entry,
633*fae548d3Szrj struct bfd_hash_table *table,
634*fae548d3Szrj const char *string ATTRIBUTE_UNUSED)
635*fae548d3Szrj {
636*fae548d3Szrj if (entry == NULL)
637*fae548d3Szrj entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
638*fae548d3Szrj sizeof (* entry));
639*fae548d3Szrj return entry;
640*fae548d3Szrj }
641*fae548d3Szrj
642*fae548d3Szrj /* Traverse a hash table. */
643*fae548d3Szrj
644*fae548d3Szrj void
bfd_hash_traverse(struct bfd_hash_table * table,bfd_boolean (* func)(struct bfd_hash_entry *,void *),void * info)645*fae548d3Szrj bfd_hash_traverse (struct bfd_hash_table *table,
646*fae548d3Szrj bfd_boolean (*func) (struct bfd_hash_entry *, void *),
647*fae548d3Szrj void * info)
648*fae548d3Szrj {
649*fae548d3Szrj unsigned int i;
650*fae548d3Szrj
651*fae548d3Szrj table->frozen = 1;
652*fae548d3Szrj for (i = 0; i < table->size; i++)
653*fae548d3Szrj {
654*fae548d3Szrj struct bfd_hash_entry *p;
655*fae548d3Szrj
656*fae548d3Szrj for (p = table->table[i]; p != NULL; p = p->next)
657*fae548d3Szrj if (! (*func) (p, info))
658*fae548d3Szrj goto out;
659*fae548d3Szrj }
660*fae548d3Szrj out:
661*fae548d3Szrj table->frozen = 0;
662*fae548d3Szrj }
663*fae548d3Szrj
664*fae548d3Szrj unsigned long
bfd_hash_set_default_size(unsigned long hash_size)665*fae548d3Szrj bfd_hash_set_default_size (unsigned long hash_size)
666*fae548d3Szrj {
667*fae548d3Szrj /* Extend this prime list if you want more granularity of hash table size. */
668*fae548d3Szrj static const unsigned long hash_size_primes[] =
669*fae548d3Szrj {
670*fae548d3Szrj 31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537
671*fae548d3Szrj };
672*fae548d3Szrj unsigned int _index;
673*fae548d3Szrj
674*fae548d3Szrj /* Work out best prime number near the hash_size. */
675*fae548d3Szrj for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index)
676*fae548d3Szrj if (hash_size <= hash_size_primes[_index])
677*fae548d3Szrj break;
678*fae548d3Szrj
679*fae548d3Szrj bfd_default_hash_table_size = hash_size_primes[_index];
680*fae548d3Szrj return bfd_default_hash_table_size;
681*fae548d3Szrj }
682*fae548d3Szrj
683*fae548d3Szrj /* A few different object file formats (a.out, COFF, ELF) use a string
684*fae548d3Szrj table. These functions support adding strings to a string table,
685*fae548d3Szrj returning the byte offset, and writing out the table.
686*fae548d3Szrj
687*fae548d3Szrj Possible improvements:
688*fae548d3Szrj + look for strings matching trailing substrings of other strings
689*fae548d3Szrj + better data structures? balanced trees?
690*fae548d3Szrj + look at reducing memory use elsewhere -- maybe if we didn't have
691*fae548d3Szrj to construct the entire symbol table at once, we could get by
692*fae548d3Szrj with smaller amounts of VM? (What effect does that have on the
693*fae548d3Szrj string table reductions?) */
694*fae548d3Szrj
695*fae548d3Szrj /* An entry in the strtab hash table. */
696*fae548d3Szrj
697*fae548d3Szrj struct strtab_hash_entry
698*fae548d3Szrj {
699*fae548d3Szrj struct bfd_hash_entry root;
700*fae548d3Szrj /* Index in string table. */
701*fae548d3Szrj bfd_size_type index;
702*fae548d3Szrj /* Next string in strtab. */
703*fae548d3Szrj struct strtab_hash_entry *next;
704*fae548d3Szrj };
705*fae548d3Szrj
706*fae548d3Szrj /* The strtab hash table. */
707*fae548d3Szrj
708*fae548d3Szrj struct bfd_strtab_hash
709*fae548d3Szrj {
710*fae548d3Szrj struct bfd_hash_table table;
711*fae548d3Szrj /* Size of strtab--also next available index. */
712*fae548d3Szrj bfd_size_type size;
713*fae548d3Szrj /* First string in strtab. */
714*fae548d3Szrj struct strtab_hash_entry *first;
715*fae548d3Szrj /* Last string in strtab. */
716*fae548d3Szrj struct strtab_hash_entry *last;
717*fae548d3Szrj /* Whether to precede strings with a two byte length, as in the
718*fae548d3Szrj XCOFF .debug section. */
719*fae548d3Szrj bfd_boolean xcoff;
720*fae548d3Szrj };
721*fae548d3Szrj
722*fae548d3Szrj /* Routine to create an entry in a strtab. */
723*fae548d3Szrj
724*fae548d3Szrj static struct bfd_hash_entry *
strtab_hash_newfunc(struct bfd_hash_entry * entry,struct bfd_hash_table * table,const char * string)725*fae548d3Szrj strtab_hash_newfunc (struct bfd_hash_entry *entry,
726*fae548d3Szrj struct bfd_hash_table *table,
727*fae548d3Szrj const char *string)
728*fae548d3Szrj {
729*fae548d3Szrj struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
730*fae548d3Szrj
731*fae548d3Szrj /* Allocate the structure if it has not already been allocated by a
732*fae548d3Szrj subclass. */
733*fae548d3Szrj if (ret == NULL)
734*fae548d3Szrj ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
735*fae548d3Szrj sizeof (* ret));
736*fae548d3Szrj if (ret == NULL)
737*fae548d3Szrj return NULL;
738*fae548d3Szrj
739*fae548d3Szrj /* Call the allocation method of the superclass. */
740*fae548d3Szrj ret = (struct strtab_hash_entry *)
741*fae548d3Szrj bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
742*fae548d3Szrj
743*fae548d3Szrj if (ret)
744*fae548d3Szrj {
745*fae548d3Szrj /* Initialize the local fields. */
746*fae548d3Szrj ret->index = (bfd_size_type) -1;
747*fae548d3Szrj ret->next = NULL;
748*fae548d3Szrj }
749*fae548d3Szrj
750*fae548d3Szrj return (struct bfd_hash_entry *) ret;
751*fae548d3Szrj }
752*fae548d3Szrj
753*fae548d3Szrj /* Look up an entry in an strtab. */
754*fae548d3Szrj
755*fae548d3Szrj #define strtab_hash_lookup(t, string, create, copy) \
756*fae548d3Szrj ((struct strtab_hash_entry *) \
757*fae548d3Szrj bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
758*fae548d3Szrj
759*fae548d3Szrj /* Create a new strtab. */
760*fae548d3Szrj
761*fae548d3Szrj struct bfd_strtab_hash *
_bfd_stringtab_init(void)762*fae548d3Szrj _bfd_stringtab_init (void)
763*fae548d3Szrj {
764*fae548d3Szrj struct bfd_strtab_hash *table;
765*fae548d3Szrj bfd_size_type amt = sizeof (* table);
766*fae548d3Szrj
767*fae548d3Szrj table = (struct bfd_strtab_hash *) bfd_malloc (amt);
768*fae548d3Szrj if (table == NULL)
769*fae548d3Szrj return NULL;
770*fae548d3Szrj
771*fae548d3Szrj if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
772*fae548d3Szrj sizeof (struct strtab_hash_entry)))
773*fae548d3Szrj {
774*fae548d3Szrj free (table);
775*fae548d3Szrj return NULL;
776*fae548d3Szrj }
777*fae548d3Szrj
778*fae548d3Szrj table->size = 0;
779*fae548d3Szrj table->first = NULL;
780*fae548d3Szrj table->last = NULL;
781*fae548d3Szrj table->xcoff = FALSE;
782*fae548d3Szrj
783*fae548d3Szrj return table;
784*fae548d3Szrj }
785*fae548d3Szrj
786*fae548d3Szrj /* Create a new strtab in which the strings are output in the format
787*fae548d3Szrj used in the XCOFF .debug section: a two byte length precedes each
788*fae548d3Szrj string. */
789*fae548d3Szrj
790*fae548d3Szrj struct bfd_strtab_hash *
_bfd_xcoff_stringtab_init(void)791*fae548d3Szrj _bfd_xcoff_stringtab_init (void)
792*fae548d3Szrj {
793*fae548d3Szrj struct bfd_strtab_hash *ret;
794*fae548d3Szrj
795*fae548d3Szrj ret = _bfd_stringtab_init ();
796*fae548d3Szrj if (ret != NULL)
797*fae548d3Szrj ret->xcoff = TRUE;
798*fae548d3Szrj return ret;
799*fae548d3Szrj }
800*fae548d3Szrj
801*fae548d3Szrj /* Free a strtab. */
802*fae548d3Szrj
803*fae548d3Szrj void
_bfd_stringtab_free(struct bfd_strtab_hash * table)804*fae548d3Szrj _bfd_stringtab_free (struct bfd_strtab_hash *table)
805*fae548d3Szrj {
806*fae548d3Szrj bfd_hash_table_free (&table->table);
807*fae548d3Szrj free (table);
808*fae548d3Szrj }
809*fae548d3Szrj
810*fae548d3Szrj /* Get the index of a string in a strtab, adding it if it is not
811*fae548d3Szrj already present. If HASH is FALSE, we don't really use the hash
812*fae548d3Szrj table, and we don't eliminate duplicate strings. If COPY is true
813*fae548d3Szrj then store a copy of STR if creating a new entry. */
814*fae548d3Szrj
815*fae548d3Szrj bfd_size_type
_bfd_stringtab_add(struct bfd_strtab_hash * tab,const char * str,bfd_boolean hash,bfd_boolean copy)816*fae548d3Szrj _bfd_stringtab_add (struct bfd_strtab_hash *tab,
817*fae548d3Szrj const char *str,
818*fae548d3Szrj bfd_boolean hash,
819*fae548d3Szrj bfd_boolean copy)
820*fae548d3Szrj {
821*fae548d3Szrj struct strtab_hash_entry *entry;
822*fae548d3Szrj
823*fae548d3Szrj if (hash)
824*fae548d3Szrj {
825*fae548d3Szrj entry = strtab_hash_lookup (tab, str, TRUE, copy);
826*fae548d3Szrj if (entry == NULL)
827*fae548d3Szrj return (bfd_size_type) -1;
828*fae548d3Szrj }
829*fae548d3Szrj else
830*fae548d3Szrj {
831*fae548d3Szrj entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
832*fae548d3Szrj sizeof (* entry));
833*fae548d3Szrj if (entry == NULL)
834*fae548d3Szrj return (bfd_size_type) -1;
835*fae548d3Szrj if (! copy)
836*fae548d3Szrj entry->root.string = str;
837*fae548d3Szrj else
838*fae548d3Szrj {
839*fae548d3Szrj size_t len = strlen (str) + 1;
840*fae548d3Szrj char *n;
841*fae548d3Szrj
842*fae548d3Szrj n = (char *) bfd_hash_allocate (&tab->table, len);
843*fae548d3Szrj if (n == NULL)
844*fae548d3Szrj return (bfd_size_type) -1;
845*fae548d3Szrj memcpy (n, str, len);
846*fae548d3Szrj entry->root.string = n;
847*fae548d3Szrj }
848*fae548d3Szrj entry->index = (bfd_size_type) -1;
849*fae548d3Szrj entry->next = NULL;
850*fae548d3Szrj }
851*fae548d3Szrj
852*fae548d3Szrj if (entry->index == (bfd_size_type) -1)
853*fae548d3Szrj {
854*fae548d3Szrj entry->index = tab->size;
855*fae548d3Szrj tab->size += strlen (str) + 1;
856*fae548d3Szrj if (tab->xcoff)
857*fae548d3Szrj {
858*fae548d3Szrj entry->index += 2;
859*fae548d3Szrj tab->size += 2;
860*fae548d3Szrj }
861*fae548d3Szrj if (tab->first == NULL)
862*fae548d3Szrj tab->first = entry;
863*fae548d3Szrj else
864*fae548d3Szrj tab->last->next = entry;
865*fae548d3Szrj tab->last = entry;
866*fae548d3Szrj }
867*fae548d3Szrj
868*fae548d3Szrj return entry->index;
869*fae548d3Szrj }
870*fae548d3Szrj
871*fae548d3Szrj /* Get the number of bytes in a strtab. */
872*fae548d3Szrj
873*fae548d3Szrj bfd_size_type
_bfd_stringtab_size(struct bfd_strtab_hash * tab)874*fae548d3Szrj _bfd_stringtab_size (struct bfd_strtab_hash *tab)
875*fae548d3Szrj {
876*fae548d3Szrj return tab->size;
877*fae548d3Szrj }
878*fae548d3Szrj
879*fae548d3Szrj /* Write out a strtab. ABFD must already be at the right location in
880*fae548d3Szrj the file. */
881*fae548d3Szrj
882*fae548d3Szrj bfd_boolean
_bfd_stringtab_emit(bfd * abfd,struct bfd_strtab_hash * tab)883*fae548d3Szrj _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
884*fae548d3Szrj {
885*fae548d3Szrj bfd_boolean xcoff;
886*fae548d3Szrj struct strtab_hash_entry *entry;
887*fae548d3Szrj
888*fae548d3Szrj xcoff = tab->xcoff;
889*fae548d3Szrj
890*fae548d3Szrj for (entry = tab->first; entry != NULL; entry = entry->next)
891*fae548d3Szrj {
892*fae548d3Szrj const char *str;
893*fae548d3Szrj size_t len;
894*fae548d3Szrj
895*fae548d3Szrj str = entry->root.string;
896*fae548d3Szrj len = strlen (str) + 1;
897*fae548d3Szrj
898*fae548d3Szrj if (xcoff)
899*fae548d3Szrj {
900*fae548d3Szrj bfd_byte buf[2];
901*fae548d3Szrj
902*fae548d3Szrj /* The output length includes the null byte. */
903*fae548d3Szrj bfd_put_16 (abfd, (bfd_vma) len, buf);
904*fae548d3Szrj if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
905*fae548d3Szrj return FALSE;
906*fae548d3Szrj }
907*fae548d3Szrj
908*fae548d3Szrj if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
909*fae548d3Szrj return FALSE;
910*fae548d3Szrj }
911*fae548d3Szrj
912*fae548d3Szrj return TRUE;
913*fae548d3Szrj }
914