bfd/hash.c

   1 /* hash.c -- hash table routines for BFD
   2    Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004
   3    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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 @* Changing the default Hash Table Size::
  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} (entry, table, string)
 235 .     struct bfd_hash_entry *entry;
 236 .     struct bfd_hash_table *table;
 237 .     const char *string;
 238 .{
 239 .  struct @var{entry_type} *ret = (@var{entry_type} *) entry;
 240 .
 241 . {* Allocate the structure if it has not already been allocated by a
 242 .    derived class.  *}
 243 .  if (ret == (@var{entry_type} *) NULL)
 244 .    {
 245 .      ret = ((@var{entry_type} *)
 246 .             bfd_hash_allocate (table, sizeof (@var{entry_type})));
 247 .      if (ret == (@var{entry_type} *) NULL)
 248 .        return NULL;
 249 .    }
 250 .
 251 . {* Call the allocation method of the base class.  *}
 252 .  ret = ((@var{entry_type} *)
 253 .        @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
 254 .
 255 . {* Initialize the local fields here.  *}
 256 .
 257 .  return (struct bfd_hash_entry *) ret;
 258 .}
 259
 260 DESCRIPTION
 261         The creation routine for the linker hash table, which is in
 262         <<linker.c>>, looks just like this example.
 263         @var{function_name} is <<_bfd_link_hash_newfunc>>.
 264         @var{entry_type} is <<struct bfd_link_hash_entry>>.
 265         @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
 266         routine for a basic hash table.
 267
 268         <<_bfd_link_hash_newfunc>> also initializes the local fields
 269         in a linker hash table entry: <<type>>, <<written>> and
 270         <<next>>.
 271
 272 INODE
 273 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
 274 SUBSUBSECTION
 275         Write other derived routines
 276
 277         You will want to write other routines for your new hash table,
 278         as well.
 279
 280         You will want an initialization routine which calls the
 281         initialization routine of the hash table you are deriving from
 282         and initializes any other local fields.  For the linker hash
 283         table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
 284
 285         You will want a lookup routine which calls the lookup routine
 286         of the hash table you are deriving from and casts the result.
 287         The linker hash table uses <<bfd_link_hash_lookup>> in
 288         <<linker.c>> (this actually takes an additional argument which
 289         it uses to decide how to return the looked up value).
 290
 291         You may want a traversal routine.  This should just call the
 292         traversal routine of the hash table you are deriving from with
 293         appropriate casts.  The linker hash table uses
 294         <<bfd_link_hash_traverse>> in <<linker.c>>.
 295
 296         These routines may simply be defined as macros.  For example,
 297         the a.out backend linker hash table, which is derived from the
 298         linker hash table, uses macros for the lookup and traversal
 299         routines.  These are <<aout_link_hash_lookup>> and
 300         <<aout_link_hash_traverse>> in aoutx.h.
 301 */
 302
 303 /* The default number of entries to use when creating a hash table.  */
 304 #define DEFAULT_SIZE 4051
 305 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
 306
 307 /* Create a new hash table, given a number of entries.  */
 308
 309 bfd_boolean
 310 bfd_hash_table_init_n (table, newfunc, size)
 311      struct bfd_hash_table *table;
 312      struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
 313                                                 struct bfd_hash_table *,
 314                                                 const char *));
 315      unsigned int size;
 316 {
 317   unsigned int alloc;
 318
 319   alloc = size * sizeof (struct bfd_hash_entry *);
 320
 321   table->memory = (PTR) objalloc_create ();
 322   if (table->memory == NULL)
 323     {
 324       bfd_set_error (bfd_error_no_memory);
 325       return FALSE;
 326     }
 327   table->table = ((struct bfd_hash_entry **)
 328                   objalloc_alloc ((struct objalloc *) table->memory, alloc));
 329   if (table->table == NULL)
 330     {
 331       bfd_set_error (bfd_error_no_memory);
 332       return FALSE;
 333     }
 334   memset ((PTR) table->table, 0, alloc);
 335   table->size = size;
 336   table->newfunc = newfunc;
 337   return TRUE;
 338 }
 339
 340 /* Create a new hash table with the default number of entries.  */
 341
 342 bfd_boolean
 343 bfd_hash_table_init (table, newfunc)
 344      struct bfd_hash_table *table;
 345      struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
 346                                                 struct bfd_hash_table *,
 347                                                 const char *));
 348 {
 349   return bfd_hash_table_init_n (table, newfunc, bfd_default_hash_table_size);
 350 }
 351
 352 /* Free a hash table.  */
 353
 354 void
 355 bfd_hash_table_free (table)
 356      struct bfd_hash_table *table;
 357 {
 358   objalloc_free ((struct objalloc *) table->memory);
 359   table->memory = NULL;
 360 }
 361
 362 /* Look up a string in a hash table.  */
 363
 364 struct bfd_hash_entry *
 365 bfd_hash_lookup (table, string, create, copy)
 366      struct bfd_hash_table *table;
 367      const char *string;
 368      bfd_boolean create;
 369      bfd_boolean copy;
 370 {
 371   register const unsigned char *s;
 372   register unsigned long hash;
 373   register unsigned int c;
 374   struct bfd_hash_entry *hashp;
 375   unsigned int len;
 376   unsigned int index;
 377
 378   hash = 0;
 379   len = 0;
 380   s = (const unsigned char *) string;
 381   while ((c = *s++) != '\0')
 382     {
 383       hash += c + (c << 17);
 384       hash ^= hash >> 2;
 385     }
 386   len = (s - (const unsigned char *) string) - 1;
 387   hash += len + (len << 17);
 388   hash ^= hash >> 2;
 389
 390   index = hash % table->size;
 391   for (hashp = table->table[index];
 392        hashp != (struct bfd_hash_entry *) NULL;
 393        hashp = hashp->next)
 394     {
 395       if (hashp->hash == hash
 396           && strcmp (hashp->string, string) == 0)
 397         return hashp;
 398     }
 399
 400   if (! create)
 401     return (struct bfd_hash_entry *) NULL;
 402
 403   hashp = (*table->newfunc) ((struct bfd_hash_entry *) NULL, table, string);
 404   if (hashp == (struct bfd_hash_entry *) NULL)
 405     return (struct bfd_hash_entry *) NULL;
 406   if (copy)
 407     {
 408       char *new;
 409
 410       new = (char *) objalloc_alloc ((struct objalloc *) table->memory,
 411                                      len + 1);
 412       if (!new)
 413         {
 414           bfd_set_error (bfd_error_no_memory);
 415           return (struct bfd_hash_entry *) NULL;
 416         }
 417       memcpy (new, string, len + 1);
 418       string = new;
 419     }
 420   hashp->string = string;
 421   hashp->hash = hash;
 422   hashp->next = table->table[index];
 423   table->table[index] = hashp;
 424
 425   return hashp;
 426 }
 427
 428 /* Replace an entry in a hash table.  */
 429
 430 void
 431 bfd_hash_replace (table, old, nw)
 432      struct bfd_hash_table *table;
 433      struct bfd_hash_entry *old;
 434      struct bfd_hash_entry *nw;
 435 {
 436   unsigned int index;
 437   struct bfd_hash_entry **pph;
 438
 439   index = old->hash % table->size;
 440   for (pph = &table->table[index];
 441        (*pph) != (struct bfd_hash_entry *) NULL;
 442        pph = &(*pph)->next)
 443     {
 444       if (*pph == old)
 445         {
 446           *pph = nw;
 447           return;
 448         }
 449     }
 450
 451   abort ();
 452 }
 453
 454 /* Base method for creating a new hash table entry.  */
 455
 456 struct bfd_hash_entry *
 457 bfd_hash_newfunc (entry, table, string)
 458      struct bfd_hash_entry *entry;
 459      struct bfd_hash_table *table;
 460      const char *string ATTRIBUTE_UNUSED;
 461 {
 462   if (entry == (struct bfd_hash_entry *) NULL)
 463     entry = ((struct bfd_hash_entry *)
 464              bfd_hash_allocate (table, sizeof (struct bfd_hash_entry)));
 465   return entry;
 466 }
 467
 468 /* Allocate space in a hash table.  */
 469
 470 PTR
 471 bfd_hash_allocate (table, size)
 472      struct bfd_hash_table *table;
 473      unsigned int size;
 474 {
 475   PTR ret;
 476
 477   ret = objalloc_alloc ((struct objalloc *) table->memory, size);
 478   if (ret == NULL && size != 0)
 479     bfd_set_error (bfd_error_no_memory);
 480   return ret;
 481 }
 482
 483 /* Traverse a hash table.  */
 484
 485 void
 486 bfd_hash_traverse (table, func, info)
 487      struct bfd_hash_table *table;
 488      bfd_boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR));
 489      PTR info;
 490 {
 491   unsigned int i;
 492
 493   for (i = 0; i < table->size; i++)
 494     {
 495       struct bfd_hash_entry *p;
 496
 497       for (p = table->table[i]; p != NULL; p = p->next)
 498         {
 499           if (! (*func) (p, info))
 500             return;
 501         }
 502     }
 503 }
 504 \f
 505 void
 506 bfd_hash_set_default_size (bfd_size_type hash_size)
 507 {
 508   int index;
 509   /* Extend this prime list if you want more granularity of hash table size.  */
 510   static bfd_size_type hash_size_primes[] =
 511     {
 512       1021, 4051, 8599, 16699
 513     };
 514
 515   /* Work out best prime number near the hash_size.  */
 516   for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
 517     if (hash_size <= hash_size_primes[index])
 518       break;
 519
 520   bfd_default_hash_table_size = hash_size_primes[index];
 521 }
 522 \f
 523 /* A few different object file formats (a.out, COFF, ELF) use a string
 524    table.  These functions support adding strings to a string table,
 525    returning the byte offset, and writing out the table.
 526
 527    Possible improvements:
 528    + look for strings matching trailing substrings of other strings
 529    + better data structures?  balanced trees?
 530    + look at reducing memory use elsewhere -- maybe if we didn't have
 531      to construct the entire symbol table at once, we could get by
 532      with smaller amounts of VM?  (What effect does that have on the
 533      string table reductions?)  */
 534
 535 /* An entry in the strtab hash table.  */
 536
 537 struct strtab_hash_entry
 538 {
 539   struct bfd_hash_entry root;
 540   /* Index in string table.  */
 541   bfd_size_type index;
 542   /* Next string in strtab.  */
 543   struct strtab_hash_entry *next;
 544 };
 545
 546 /* The strtab hash table.  */
 547
 548 struct bfd_strtab_hash
 549 {
 550   struct bfd_hash_table table;
 551   /* Size of strtab--also next available index.  */
 552   bfd_size_type size;
 553   /* First string in strtab.  */
 554   struct strtab_hash_entry *first;
 555   /* Last string in strtab.  */
 556   struct strtab_hash_entry *last;
 557   /* Whether to precede strings with a two byte length, as in the
 558      XCOFF .debug section.  */
 559   bfd_boolean xcoff;
 560 };
 561
 562 static struct bfd_hash_entry *strtab_hash_newfunc
 563   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
 564
 565 /* Routine to create an entry in a strtab.  */
 566
 567 static struct bfd_hash_entry *
 568 strtab_hash_newfunc (entry, table, string)
 569      struct bfd_hash_entry *entry;
 570      struct bfd_hash_table *table;
 571      const char *string;
 572 {
 573   struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
 574
 575   /* Allocate the structure if it has not already been allocated by a
 576      subclass.  */
 577   if (ret == (struct strtab_hash_entry *) NULL)
 578     ret = ((struct strtab_hash_entry *)
 579            bfd_hash_allocate (table, sizeof (struct strtab_hash_entry)));
 580   if (ret == (struct strtab_hash_entry *) NULL)
 581     return NULL;
 582
 583   /* Call the allocation method of the superclass.  */
 584   ret = ((struct strtab_hash_entry *)
 585          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
 586
 587   if (ret)
 588     {
 589       /* Initialize the local fields.  */
 590       ret->index = (bfd_size_type) -1;
 591       ret->next = NULL;
 592     }
 593
 594   return (struct bfd_hash_entry *) ret;
 595 }
 596
 597 /* Look up an entry in an strtab.  */
 598
 599 #define strtab_hash_lookup(t, string, create, copy) \
 600   ((struct strtab_hash_entry *) \
 601    bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
 602
 603 /* Create a new strtab.  */
 604
 605 struct bfd_strtab_hash *
 606 _bfd_stringtab_init ()
 607 {
 608   struct bfd_strtab_hash *table;
 609   bfd_size_type amt = sizeof (struct bfd_strtab_hash);
 610
 611   table = (struct bfd_strtab_hash *) bfd_malloc (amt);
 612   if (table == NULL)
 613     return NULL;
 614
 615   if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc))
 616     {
 617       free (table);
 618       return NULL;
 619     }
 620
 621   table->size = 0;
 622   table->first = NULL;
 623   table->last = NULL;
 624   table->xcoff = FALSE;
 625
 626   return table;
 627 }
 628
 629 /* Create a new strtab in which the strings are output in the format
 630    used in the XCOFF .debug section: a two byte length precedes each
 631    string.  */
 632
 633 struct bfd_strtab_hash *
 634 _bfd_xcoff_stringtab_init ()
 635 {
 636   struct bfd_strtab_hash *ret;
 637
 638   ret = _bfd_stringtab_init ();
 639   if (ret != NULL)
 640     ret->xcoff = TRUE;
 641   return ret;
 642 }
 643
 644 /* Free a strtab.  */
 645
 646 void
 647 _bfd_stringtab_free (table)
 648      struct bfd_strtab_hash *table;
 649 {
 650   bfd_hash_table_free (&table->table);
 651   free (table);
 652 }
 653
 654 /* Get the index of a string in a strtab, adding it if it is not
 655    already present.  If HASH is FALSE, we don't really use the hash
 656    table, and we don't eliminate duplicate strings.  */
 657
 658 bfd_size_type
 659 _bfd_stringtab_add (tab, str, hash, copy)
 660      struct bfd_strtab_hash *tab;
 661      const char *str;
 662      bfd_boolean hash;
 663      bfd_boolean copy;
 664 {
 665   register struct strtab_hash_entry *entry;
 666
 667   if (hash)
 668     {
 669       entry = strtab_hash_lookup (tab, str, TRUE, copy);
 670       if (entry == NULL)
 671         return (bfd_size_type) -1;
 672     }
 673   else
 674     {
 675       entry = ((struct strtab_hash_entry *)
 676                bfd_hash_allocate (&tab->table,
 677                                   sizeof (struct strtab_hash_entry)));
 678       if (entry == NULL)
 679         return (bfd_size_type) -1;
 680       if (! copy)
 681         entry->root.string = str;
 682       else
 683         {
 684           char *n;
 685
 686           n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1);
 687           if (n == NULL)
 688             return (bfd_size_type) -1;
 689           entry->root.string = n;
 690         }
 691       entry->index = (bfd_size_type) -1;
 692       entry->next = NULL;
 693     }
 694
 695   if (entry->index == (bfd_size_type) -1)
 696     {
 697       entry->index = tab->size;
 698       tab->size += strlen (str) + 1;
 699       if (tab->xcoff)
 700         {
 701           entry->index += 2;
 702           tab->size += 2;
 703         }
 704       if (tab->first == NULL)
 705         tab->first = entry;
 706       else
 707         tab->last->next = entry;
 708       tab->last = entry;
 709     }
 710
 711   return entry->index;
 712 }
 713
 714 /* Get the number of bytes in a strtab.  */
 715
 716 bfd_size_type
 717 _bfd_stringtab_size (tab)
 718      struct bfd_strtab_hash *tab;
 719 {
 720   return tab->size;
 721 }
 722
 723 /* Write out a strtab.  ABFD must already be at the right location in
 724    the file.  */
 725
 726 bfd_boolean
 727 _bfd_stringtab_emit (abfd, tab)
 728      register bfd *abfd;
 729      struct bfd_strtab_hash *tab;
 730 {
 731   register bfd_boolean xcoff;
 732   register struct strtab_hash_entry *entry;
 733
 734   xcoff = tab->xcoff;
 735
 736   for (entry = tab->first; entry != NULL; entry = entry->next)
 737     {
 738       const char *str;
 739       size_t len;
 740
 741       str = entry->root.string;
 742       len = strlen (str) + 1;
 743
 744       if (xcoff)
 745         {
 746           bfd_byte buf[2];
 747
 748           /* The output length includes the null byte.  */
 749           bfd_put_16 (abfd, (bfd_vma) len, buf);
 750           if (bfd_bwrite ((PTR) buf, (bfd_size_type) 2, abfd) != 2)
 751             return FALSE;
 752         }
 753
 754       if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
 755         return FALSE;
 756     }
 757
 758   return TRUE;
 759 }