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