bfd/hash.c

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