bfd/hash.c

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