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