bfd/hash.c

   1 /* hash.c -- hash table routines for BFD
   2    Copyright (C) 1993-2019 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
 300 /* The default number of entries to use when creating a hash table.  */
 301 #define DEFAULT_SIZE 4051
 302
 303 /* The following function returns a nearest prime number which is
 304    greater than N, and near a power of two.  Copied from libiberty.
 305    Returns zero for ridiculously large N to signify an error.  */
 306
 307 static unsigned long
 308 higher_prime_number (unsigned long n)
 309 {
 310   /* These are primes that are near, but slightly smaller than, a
 311      power of two.  */
 312   static const unsigned long primes[] =
 313     {
 314       (unsigned long) 31,
 315       (unsigned long) 61,
 316       (unsigned long) 127,
 317       (unsigned long) 251,
 318       (unsigned long) 509,
 319       (unsigned long) 1021,
 320       (unsigned long) 2039,
 321       (unsigned long) 4093,
 322       (unsigned long) 8191,
 323       (unsigned long) 16381,
 324       (unsigned long) 32749,
 325       (unsigned long) 65521,
 326       (unsigned long) 131071,
 327       (unsigned long) 262139,
 328       (unsigned long) 524287,
 329       (unsigned long) 1048573,
 330       (unsigned long) 2097143,
 331       (unsigned long) 4194301,
 332       (unsigned long) 8388593,
 333       (unsigned long) 16777213,
 334       (unsigned long) 33554393,
 335       (unsigned long) 67108859,
 336       (unsigned long) 134217689,
 337       (unsigned long) 268435399,
 338       (unsigned long) 536870909,
 339       (unsigned long) 1073741789,
 340       (unsigned long) 2147483647,
 341                                         /* 4294967291L */
 342       ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
 343   };
 344
 345   const unsigned long *low = &primes[0];
 346   const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
 347
 348   while (low != high)
 349     {
 350       const unsigned long *mid = low + (high - low) / 2;
 351       if (n >= *mid)
 352         low = mid + 1;
 353       else
 354         high = mid;
 355     }
 356
 357   if (n >= *low)
 358     return 0;
 359
 360   return *low;
 361 }
 362
 363 static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE;
 364
 365 /* Create a new hash table, given a number of entries.  */
 366
 367 bfd_boolean
 368 bfd_hash_table_init_n (struct bfd_hash_table *table,
 369                        struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
 370                                                           struct bfd_hash_table *,
 371                                                           const char *),
 372                        unsigned int entsize,
 373                        unsigned int size)
 374 {
 375   unsigned long alloc;
 376
 377   alloc = size;
 378   alloc *= sizeof (struct bfd_hash_entry *);
 379   if (alloc / sizeof (struct bfd_hash_entry *) != size)
 380     {
 381       bfd_set_error (bfd_error_no_memory);
 382       return FALSE;
 383     }
 384
 385   table->memory = (void *) objalloc_create ();
 386   if (table->memory == NULL)
 387     {
 388       bfd_set_error (bfd_error_no_memory);
 389       return FALSE;
 390     }
 391   table->table = (struct bfd_hash_entry **)
 392       objalloc_alloc ((struct objalloc *) table->memory, alloc);
 393   if (table->table == NULL)
 394     {
 395       bfd_hash_table_free (table);
 396       bfd_set_error (bfd_error_no_memory);
 397       return FALSE;
 398     }
 399   memset ((void *) table->table, 0, alloc);
 400   table->size = size;
 401   table->entsize = entsize;
 402   table->count = 0;
 403   table->frozen = 0;
 404   table->newfunc = newfunc;
 405   return TRUE;
 406 }
 407
 408 /* Create a new hash table with the default number of entries.  */
 409
 410 bfd_boolean
 411 bfd_hash_table_init (struct bfd_hash_table *table,
 412                      struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
 413                                                         struct bfd_hash_table *,
 414                                                         const char *),
 415                      unsigned int entsize)
 416 {
 417   return bfd_hash_table_init_n (table, newfunc, entsize,
 418                                 bfd_default_hash_table_size);
 419 }
 420
 421 /* Free a hash table.  */
 422
 423 void
 424 bfd_hash_table_free (struct bfd_hash_table *table)
 425 {
 426   objalloc_free ((struct objalloc *) table->memory);
 427   table->memory = NULL;
 428 }
 429
 430 static inline unsigned long
 431 bfd_hash_hash (const char *string, unsigned int *lenp)
 432 {
 433   const unsigned char *s;
 434   unsigned long hash;
 435   unsigned int len;
 436   unsigned int c;
 437
 438   BFD_ASSERT (string != NULL);
 439   hash = 0;
 440   len = 0;
 441   s = (const unsigned char *) string;
 442   while ((c = *s++) != '\0')
 443     {
 444       hash += c + (c << 17);
 445       hash ^= hash >> 2;
 446     }
 447   len = (s - (const unsigned char *) string) - 1;
 448   hash += len + (len << 17);
 449   hash ^= hash >> 2;
 450   if (lenp != NULL)
 451     *lenp = len;
 452   return hash;
 453 }
 454
 455 /* Look up a string in a hash table.  */
 456
 457 struct bfd_hash_entry *
 458 bfd_hash_lookup (struct bfd_hash_table *table,
 459                  const char *string,
 460                  bfd_boolean create,
 461                  bfd_boolean copy)
 462 {
 463   unsigned long hash;
 464   struct bfd_hash_entry *hashp;
 465   unsigned int len;
 466   unsigned int _index;
 467
 468   hash = bfd_hash_hash (string, &len);
 469   _index = hash % table->size;
 470   for (hashp = table->table[_index];
 471        hashp != NULL;
 472        hashp = hashp->next)
 473     {
 474       if (hashp->hash == hash
 475           && strcmp (hashp->string, string) == 0)
 476         return hashp;
 477     }
 478
 479   if (! create)
 480     return NULL;
 481
 482   if (copy)
 483     {
 484       char *new_string;
 485
 486       new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
 487                                             len + 1);
 488       if (!new_string)
 489         {
 490           bfd_set_error (bfd_error_no_memory);
 491           return NULL;
 492         }
 493       memcpy (new_string, string, len + 1);
 494       string = new_string;
 495     }
 496
 497   return bfd_hash_insert (table, string, hash);
 498 }
 499
 500 /* Insert an entry in a hash table.  */
 501
 502 struct bfd_hash_entry *
 503 bfd_hash_insert (struct bfd_hash_table *table,
 504                  const char *string,
 505                  unsigned long hash)
 506 {
 507   struct bfd_hash_entry *hashp;
 508   unsigned int _index;
 509
 510   hashp = (*table->newfunc) (NULL, table, string);
 511   if (hashp == NULL)
 512     return NULL;
 513   hashp->string = string;
 514   hashp->hash = hash;
 515   _index = hash % table->size;
 516   hashp->next = table->table[_index];
 517   table->table[_index] = hashp;
 518   table->count++;
 519
 520   if (!table->frozen && table->count > table->size * 3 / 4)
 521     {
 522       unsigned long newsize = higher_prime_number (table->size);
 523       struct bfd_hash_entry **newtable;
 524       unsigned int hi;
 525       unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
 526
 527       /* If we can't find a higher prime, or we can't possibly alloc
 528          that much memory, don't try to grow the table.  */
 529       if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
 530         {
 531           table->frozen = 1;
 532           return hashp;
 533         }
 534
 535       newtable = ((struct bfd_hash_entry **)
 536                   objalloc_alloc ((struct objalloc *) table->memory, alloc));
 537       if (newtable == NULL)
 538         {
 539           table->frozen = 1;
 540           return hashp;
 541         }
 542       memset (newtable, 0, alloc);
 543
 544       for (hi = 0; hi < table->size; hi ++)
 545         while (table->table[hi])
 546           {
 547             struct bfd_hash_entry *chain = table->table[hi];
 548             struct bfd_hash_entry *chain_end = chain;
 549
 550             while (chain_end->next && chain_end->next->hash == chain->hash)
 551               chain_end = chain_end->next;
 552
 553             table->table[hi] = chain_end->next;
 554             _index = chain->hash % newsize;
 555             chain_end->next = newtable[_index];
 556             newtable[_index] = chain;
 557           }
 558       table->table = newtable;
 559       table->size = newsize;
 560     }
 561
 562   return hashp;
 563 }
 564
 565 /* Rename an entry in a hash table.  */
 566
 567 void
 568 bfd_hash_rename (struct bfd_hash_table *table,
 569                  const char *string,
 570                  struct bfd_hash_entry *ent)
 571 {
 572   unsigned int _index;
 573   struct bfd_hash_entry **pph;
 574
 575   _index = ent->hash % table->size;
 576   for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
 577     if (*pph == ent)
 578       break;
 579   if (*pph == NULL)
 580     abort ();
 581
 582   *pph = ent->next;
 583   ent->string = string;
 584   ent->hash = bfd_hash_hash (string, NULL);
 585   _index = ent->hash % table->size;
 586   ent->next = table->table[_index];
 587   table->table[_index] = ent;
 588 }
 589
 590 /* Replace an entry in a hash table.  */
 591
 592 void
 593 bfd_hash_replace (struct bfd_hash_table *table,
 594                   struct bfd_hash_entry *old,
 595                   struct bfd_hash_entry *nw)
 596 {
 597   unsigned int _index;
 598   struct bfd_hash_entry **pph;
 599
 600   _index = old->hash % table->size;
 601   for (pph = &table->table[_index];
 602        (*pph) != NULL;
 603        pph = &(*pph)->next)
 604     {
 605       if (*pph == old)
 606         {
 607           *pph = nw;
 608           return;
 609         }
 610     }
 611
 612   abort ();
 613 }
 614
 615 /* Allocate space in a hash table.  */
 616
 617 void *
 618 bfd_hash_allocate (struct bfd_hash_table *table,
 619                    unsigned int size)
 620 {
 621   void * ret;
 622
 623   ret = objalloc_alloc ((struct objalloc *) table->memory, size);
 624   if (ret == NULL && size != 0)
 625     bfd_set_error (bfd_error_no_memory);
 626   return ret;
 627 }
 628
 629 /* Base method for creating a new hash table entry.  */
 630
 631 struct bfd_hash_entry *
 632 bfd_hash_newfunc (struct bfd_hash_entry *entry,
 633                   struct bfd_hash_table *table,
 634                   const char *string ATTRIBUTE_UNUSED)
 635 {
 636   if (entry == NULL)
 637     entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
 638                                                          sizeof (* entry));
 639   return entry;
 640 }
 641
 642 /* Traverse a hash table.  */
 643
 644 void
 645 bfd_hash_traverse (struct bfd_hash_table *table,
 646                    bfd_boolean (*func) (struct bfd_hash_entry *, void *),
 647                    void * info)
 648 {
 649   unsigned int i;
 650
 651   table->frozen = 1;
 652   for (i = 0; i < table->size; i++)
 653     {
 654       struct bfd_hash_entry *p;
 655
 656       for (p = table->table[i]; p != NULL; p = p->next)
 657         if (! (*func) (p, info))
 658           goto out;
 659     }
 660  out:
 661   table->frozen = 0;
 662 }
 663 \f
 664 unsigned long
 665 bfd_hash_set_default_size (unsigned long hash_size)
 666 {
 667   /* Extend this prime list if you want more granularity of hash table size.  */
 668   static const unsigned long hash_size_primes[] =
 669     {
 670       31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537
 671     };
 672   unsigned int _index;
 673
 674   /* Work out best prime number near the hash_size.  */
 675   for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index)
 676     if (hash_size <= hash_size_primes[_index])
 677       break;
 678
 679   bfd_default_hash_table_size = hash_size_primes[_index];
 680   return bfd_default_hash_table_size;
 681 }
 682 \f
 683 /* A few different object file formats (a.out, COFF, ELF) use a string
 684    table.  These functions support adding strings to a string table,
 685    returning the byte offset, and writing out the table.
 686
 687    Possible improvements:
 688    + look for strings matching trailing substrings of other strings
 689    + better data structures?  balanced trees?
 690    + look at reducing memory use elsewhere -- maybe if we didn't have
 691      to construct the entire symbol table at once, we could get by
 692      with smaller amounts of VM?  (What effect does that have on the
 693      string table reductions?)  */
 694
 695 /* An entry in the strtab hash table.  */
 696
 697 struct strtab_hash_entry
 698 {
 699   struct bfd_hash_entry root;
 700   /* Index in string table.  */
 701   bfd_size_type index;
 702   /* Next string in strtab.  */
 703   struct strtab_hash_entry *next;
 704 };
 705
 706 /* The strtab hash table.  */
 707
 708 struct bfd_strtab_hash
 709 {
 710   struct bfd_hash_table table;
 711   /* Size of strtab--also next available index.  */
 712   bfd_size_type size;
 713   /* First string in strtab.  */
 714   struct strtab_hash_entry *first;
 715   /* Last string in strtab.  */
 716   struct strtab_hash_entry *last;
 717   /* Whether to precede strings with a two byte length, as in the
 718      XCOFF .debug section.  */
 719   bfd_boolean xcoff;
 720 };
 721
 722 /* Routine to create an entry in a strtab.  */
 723
 724 static struct bfd_hash_entry *
 725 strtab_hash_newfunc (struct bfd_hash_entry *entry,
 726                      struct bfd_hash_table *table,
 727                      const char *string)
 728 {
 729   struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
 730
 731   /* Allocate the structure if it has not already been allocated by a
 732      subclass.  */
 733   if (ret == NULL)
 734     ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
 735                                                           sizeof (* ret));
 736   if (ret == NULL)
 737     return NULL;
 738
 739   /* Call the allocation method of the superclass.  */
 740   ret = (struct strtab_hash_entry *)
 741          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
 742
 743   if (ret)
 744     {
 745       /* Initialize the local fields.  */
 746       ret->index = (bfd_size_type) -1;
 747       ret->next = NULL;
 748     }
 749
 750   return (struct bfd_hash_entry *) ret;
 751 }
 752
 753 /* Look up an entry in an strtab.  */
 754
 755 #define strtab_hash_lookup(t, string, create, copy) \
 756   ((struct strtab_hash_entry *) \
 757    bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
 758
 759 /* Create a new strtab.  */
 760
 761 struct bfd_strtab_hash *
 762 _bfd_stringtab_init (void)
 763 {
 764   struct bfd_strtab_hash *table;
 765   bfd_size_type amt = sizeof (* table);
 766
 767   table = (struct bfd_strtab_hash *) bfd_malloc (amt);
 768   if (table == NULL)
 769     return NULL;
 770
 771   if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
 772                             sizeof (struct strtab_hash_entry)))
 773     {
 774       free (table);
 775       return NULL;
 776     }
 777
 778   table->size = 0;
 779   table->first = NULL;
 780   table->last = NULL;
 781   table->xcoff = FALSE;
 782
 783   return table;
 784 }
 785
 786 /* Create a new strtab in which the strings are output in the format
 787    used in the XCOFF .debug section: a two byte length precedes each
 788    string.  */
 789
 790 struct bfd_strtab_hash *
 791 _bfd_xcoff_stringtab_init (void)
 792 {
 793   struct bfd_strtab_hash *ret;
 794
 795   ret = _bfd_stringtab_init ();
 796   if (ret != NULL)
 797     ret->xcoff = TRUE;
 798   return ret;
 799 }
 800
 801 /* Free a strtab.  */
 802
 803 void
 804 _bfd_stringtab_free (struct bfd_strtab_hash *table)
 805 {
 806   bfd_hash_table_free (&table->table);
 807   free (table);
 808 }
 809
 810 /* Get the index of a string in a strtab, adding it if it is not
 811    already present.  If HASH is FALSE, we don't really use the hash
 812    table, and we don't eliminate duplicate strings.  If COPY is true
 813    then store a copy of STR if creating a new entry.  */
 814
 815 bfd_size_type
 816 _bfd_stringtab_add (struct bfd_strtab_hash *tab,
 817                     const char *str,
 818                     bfd_boolean hash,
 819                     bfd_boolean copy)
 820 {
 821   struct strtab_hash_entry *entry;
 822
 823   if (hash)
 824     {
 825       entry = strtab_hash_lookup (tab, str, TRUE, copy);
 826       if (entry == NULL)
 827         return (bfd_size_type) -1;
 828     }
 829   else
 830     {
 831       entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
 832                                                               sizeof (* entry));
 833       if (entry == NULL)
 834         return (bfd_size_type) -1;
 835       if (! copy)
 836         entry->root.string = str;
 837       else
 838         {
 839           size_t len = strlen (str) + 1;
 840           char *n;
 841
 842           n = (char *) bfd_hash_allocate (&tab->table, len);
 843           if (n == NULL)
 844             return (bfd_size_type) -1;
 845           memcpy (n, str, len);
 846           entry->root.string = n;
 847         }
 848       entry->index = (bfd_size_type) -1;
 849       entry->next = NULL;
 850     }
 851
 852   if (entry->index == (bfd_size_type) -1)
 853     {
 854       entry->index = tab->size;
 855       tab->size += strlen (str) + 1;
 856       if (tab->xcoff)
 857         {
 858           entry->index += 2;
 859           tab->size += 2;
 860         }
 861       if (tab->first == NULL)
 862         tab->first = entry;
 863       else
 864         tab->last->next = entry;
 865       tab->last = entry;
 866     }
 867
 868   return entry->index;
 869 }
 870
 871 /* Get the number of bytes in a strtab.  */
 872
 873 bfd_size_type
 874 _bfd_stringtab_size (struct bfd_strtab_hash *tab)
 875 {
 876   return tab->size;
 877 }
 878
 879 /* Write out a strtab.  ABFD must already be at the right location in
 880    the file.  */
 881
 882 bfd_boolean
 883 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
 884 {
 885   bfd_boolean xcoff;
 886   struct strtab_hash_entry *entry;
 887
 888   xcoff = tab->xcoff;
 889
 890   for (entry = tab->first; entry != NULL; entry = entry->next)
 891     {
 892       const char *str;
 893       size_t len;
 894
 895       str = entry->root.string;
 896       len = strlen (str) + 1;
 897
 898       if (xcoff)
 899         {
 900           bfd_byte buf[2];
 901
 902           /* The output length includes the null byte.  */
 903           bfd_put_16 (abfd, (bfd_vma) len, buf);
 904           if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
 905             return FALSE;
 906         }
 907
 908       if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
 909         return FALSE;
 910     }
 911
 912   return TRUE;
 913 }