bfd/hash.c

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