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