Back to index

cell-binutils  2.17cvs20070401
hash.c
Go to the documentation of this file.
00001 /* hash.c -- hash table routines for BFD
00002    Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
00003    2006 Free Software Foundation, Inc.
00004    Written by Steve Chamberlain <sac@cygnus.com>
00005 
00006    This file is part of BFD, the Binary File Descriptor library.
00007 
00008    This program is free software; you can redistribute it and/or modify
00009    it under the terms of the GNU General Public License as published by
00010    the Free Software Foundation; either version 2 of the License, or
00011    (at your option) any later version.
00012 
00013    This program is distributed in the hope that it will be useful,
00014    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016    GNU General Public License for more details.
00017 
00018    You should have received a copy of the GNU General Public License
00019    along with this program; if not, write to the Free Software
00020    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.  */
00021 
00022 #include "bfd.h"
00023 #include "sysdep.h"
00024 #include "libbfd.h"
00025 #include "objalloc.h"
00026 #include "libiberty.h"
00027 
00028 /*
00029 SECTION
00030        Hash Tables
00031 
00032 @cindex Hash tables
00033        BFD provides a simple set of hash table functions.  Routines
00034        are provided to initialize a hash table, to free a hash table,
00035        to look up a string in a hash table and optionally create an
00036        entry for it, and to traverse a hash table.  There is
00037        currently no routine to delete an string from a hash table.
00038 
00039        The basic hash table does not permit any data to be stored
00040        with a string.  However, a hash table is designed to present a
00041        base class from which other types of hash tables may be
00042        derived.  These derived types may store additional information
00043        with the string.  Hash tables were implemented in this way,
00044        rather than simply providing a data pointer in a hash table
00045        entry, because they were designed for use by the linker back
00046        ends.  The linker may create thousands of hash table entries,
00047        and the overhead of allocating private data and storing and
00048        following pointers becomes noticeable.
00049 
00050        The basic hash table code is in <<hash.c>>.
00051 
00052 @menu
00053 @* Creating and Freeing a Hash Table::
00054 @* Looking Up or Entering a String::
00055 @* Traversing a Hash Table::
00056 @* Deriving a New Hash Table Type::
00057 @end menu
00058 
00059 INODE
00060 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
00061 SUBSECTION
00062        Creating and freeing a hash table
00063 
00064 @findex bfd_hash_table_init
00065 @findex bfd_hash_table_init_n
00066        To create a hash table, create an instance of a <<struct
00067        bfd_hash_table>> (defined in <<bfd.h>>) and call
00068        <<bfd_hash_table_init>> (if you know approximately how many
00069        entries you will need, the function <<bfd_hash_table_init_n>>,
00070        which takes a @var{size} argument, may be used).
00071        <<bfd_hash_table_init>> returns <<FALSE>> if some sort of
00072        error occurs.
00073 
00074 @findex bfd_hash_newfunc
00075        The function <<bfd_hash_table_init>> take as an argument a
00076        function to use to create new entries.  For a basic hash
00077        table, use the function <<bfd_hash_newfunc>>.  @xref{Deriving
00078        a New Hash Table Type}, for why you would want to use a
00079        different value for this argument.
00080 
00081 @findex bfd_hash_allocate
00082        <<bfd_hash_table_init>> will create an objalloc which will be
00083        used to allocate new entries.  You may allocate memory on this
00084        objalloc using <<bfd_hash_allocate>>.
00085 
00086 @findex bfd_hash_table_free
00087        Use <<bfd_hash_table_free>> to free up all the memory that has
00088        been allocated for a hash table.  This will not free up the
00089        <<struct bfd_hash_table>> itself, which you must provide.
00090 
00091 @findex bfd_hash_set_default_size
00092        Use <<bfd_hash_set_default_size>> to set the default size of
00093        hash table to use.
00094 
00095 INODE
00096 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
00097 SUBSECTION
00098        Looking up or entering a string
00099 
00100 @findex bfd_hash_lookup
00101        The function <<bfd_hash_lookup>> is used both to look up a
00102        string in the hash table and to create a new entry.
00103 
00104        If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>>
00105        will look up a string.  If the string is found, it will
00106        returns a pointer to a <<struct bfd_hash_entry>>.  If the
00107        string is not found in the table <<bfd_hash_lookup>> will
00108        return <<NULL>>.  You should not modify any of the fields in
00109        the returns <<struct bfd_hash_entry>>.
00110 
00111        If the @var{create} argument is <<TRUE>>, the string will be
00112        entered into the hash table if it is not already there.
00113        Either way a pointer to a <<struct bfd_hash_entry>> will be
00114        returned, either to the existing structure or to a newly
00115        created one.  In this case, a <<NULL>> return means that an
00116        error occurred.
00117 
00118        If the @var{create} argument is <<TRUE>>, and a new entry is
00119        created, the @var{copy} argument is used to decide whether to
00120        copy the string onto the hash table objalloc or not.  If
00121        @var{copy} is passed as <<FALSE>>, you must be careful not to
00122        deallocate or modify the string as long as the hash table
00123        exists.
00124 
00125 INODE
00126 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
00127 SUBSECTION
00128        Traversing a hash table
00129 
00130 @findex bfd_hash_traverse
00131        The function <<bfd_hash_traverse>> may be used to traverse a
00132        hash table, calling a function on each element.  The traversal
00133        is done in a random order.
00134 
00135        <<bfd_hash_traverse>> takes as arguments a function and a
00136        generic <<void *>> pointer.  The function is called with a
00137        hash table entry (a <<struct bfd_hash_entry *>>) and the
00138        generic pointer passed to <<bfd_hash_traverse>>.  The function
00139        must return a <<boolean>> value, which indicates whether to
00140        continue traversing the hash table.  If the function returns
00141        <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and
00142        return immediately.
00143 
00144 INODE
00145 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
00146 SUBSECTION
00147        Deriving a new hash table type
00148 
00149        Many uses of hash tables want to store additional information
00150        which each entry in the hash table.  Some also find it
00151        convenient to store additional information with the hash table
00152        itself.  This may be done using a derived hash table.
00153 
00154        Since C is not an object oriented language, creating a derived
00155        hash table requires sticking together some boilerplate
00156        routines with a few differences specific to the type of hash
00157        table you want to create.
00158 
00159        An example of a derived hash table is the linker hash table.
00160        The structures for this are defined in <<bfdlink.h>>.  The
00161        functions are in <<linker.c>>.
00162 
00163        You may also derive a hash table from an already derived hash
00164        table.  For example, the a.out linker backend code uses a hash
00165        table derived from the linker hash table.
00166 
00167 @menu
00168 @* Define the Derived Structures::
00169 @* Write the Derived Creation Routine::
00170 @* Write Other Derived Routines::
00171 @end menu
00172 
00173 INODE
00174 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
00175 SUBSUBSECTION
00176        Define the derived structures
00177 
00178        You must define a structure for an entry in the hash table,
00179        and a structure for the hash table itself.
00180 
00181        The first field in the structure for an entry in the hash
00182        table must be of the type used for an entry in the hash table
00183        you are deriving from.  If you are deriving from a basic hash
00184        table this is <<struct bfd_hash_entry>>, which is defined in
00185        <<bfd.h>>.  The first field in the structure for the hash
00186        table itself must be of the type of the hash table you are
00187        deriving from itself.  If you are deriving from a basic hash
00188        table, this is <<struct bfd_hash_table>>.
00189 
00190        For example, the linker hash table defines <<struct
00191        bfd_link_hash_entry>> (in <<bfdlink.h>>).  The first field,
00192        <<root>>, is of type <<struct bfd_hash_entry>>.  Similarly,
00193        the first field in <<struct bfd_link_hash_table>>, <<table>>,
00194        is of type <<struct bfd_hash_table>>.
00195 
00196 INODE
00197 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
00198 SUBSUBSECTION
00199        Write the derived creation routine
00200 
00201        You must write a routine which will create and initialize an
00202        entry in the hash table.  This routine is passed as the
00203        function argument to <<bfd_hash_table_init>>.
00204 
00205        In order to permit other hash tables to be derived from the
00206        hash table you are creating, this routine must be written in a
00207        standard way.
00208 
00209        The first argument to the creation routine is a pointer to a
00210        hash table entry.  This may be <<NULL>>, in which case the
00211        routine should allocate the right amount of space.  Otherwise
00212        the space has already been allocated by a hash table type
00213        derived from this one.
00214 
00215        After allocating space, the creation routine must call the
00216        creation routine of the hash table type it is derived from,
00217        passing in a pointer to the space it just allocated.  This
00218        will initialize any fields used by the base hash table.
00219 
00220        Finally the creation routine must initialize any local fields
00221        for the new hash table type.
00222 
00223        Here is a boilerplate example of a creation routine.
00224        @var{function_name} is the name of the routine.
00225        @var{entry_type} is the type of an entry in the hash table you
00226        are creating.  @var{base_newfunc} is the name of the creation
00227        routine of the hash table type your hash table is derived
00228        from.
00229 
00230 EXAMPLE
00231 
00232 .struct bfd_hash_entry *
00233 .@var{function_name} (struct bfd_hash_entry *entry,
00234 .                     struct bfd_hash_table *table,
00235 .                     const char *string)
00236 .{
00237 .  struct @var{entry_type} *ret = (@var{entry_type} *) entry;
00238 .
00239 . {* Allocate the structure if it has not already been allocated by a
00240 .    derived class.  *}
00241 .  if (ret == NULL)
00242 .    {
00243 .      ret = bfd_hash_allocate (table, sizeof (* ret));
00244 .      if (ret == NULL)
00245 .        return NULL;
00246 .    }
00247 .
00248 . {* Call the allocation method of the base class.  *}
00249 .  ret = ((@var{entry_type} *)
00250 .       @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
00251 .
00252 . {* Initialize the local fields here.  *}
00253 .
00254 .  return (struct bfd_hash_entry *) ret;
00255 .}
00256 
00257 DESCRIPTION
00258        The creation routine for the linker hash table, which is in
00259        <<linker.c>>, looks just like this example.
00260        @var{function_name} is <<_bfd_link_hash_newfunc>>.
00261        @var{entry_type} is <<struct bfd_link_hash_entry>>.
00262        @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
00263        routine for a basic hash table.
00264 
00265        <<_bfd_link_hash_newfunc>> also initializes the local fields
00266        in a linker hash table entry: <<type>>, <<written>> and
00267        <<next>>.
00268 
00269 INODE
00270 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
00271 SUBSUBSECTION
00272        Write other derived routines
00273 
00274        You will want to write other routines for your new hash table,
00275        as well.
00276 
00277        You will want an initialization routine which calls the
00278        initialization routine of the hash table you are deriving from
00279        and initializes any other local fields.  For the linker hash
00280        table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
00281 
00282        You will want a lookup routine which calls the lookup routine
00283        of the hash table you are deriving from and casts the result.
00284        The linker hash table uses <<bfd_link_hash_lookup>> in
00285        <<linker.c>> (this actually takes an additional argument which
00286        it uses to decide how to return the looked up value).
00287 
00288        You may want a traversal routine.  This should just call the
00289        traversal routine of the hash table you are deriving from with
00290        appropriate casts.  The linker hash table uses
00291        <<bfd_link_hash_traverse>> in <<linker.c>>.
00292 
00293        These routines may simply be defined as macros.  For example,
00294        the a.out backend linker hash table, which is derived from the
00295        linker hash table, uses macros for the lookup and traversal
00296        routines.  These are <<aout_link_hash_lookup>> and
00297        <<aout_link_hash_traverse>> in aoutx.h.
00298 */
00299 
00300 /* The default number of entries to use when creating a hash table.  */
00301 #define DEFAULT_SIZE 4051
00302 
00303 /* The following function returns a nearest prime number which is
00304    greater than N, and near a power of two.  Copied from libiberty.
00305    Returns zero for ridiculously large N to signify an error.  */
00306 
00307 static unsigned long
00308 higher_prime_number (unsigned long n)
00309 {
00310   /* These are primes that are near, but slightly smaller than, a
00311      power of two.  */
00312   static const unsigned long primes[] = {
00313     (unsigned long) 127,
00314     (unsigned long) 2039,
00315     (unsigned long) 32749,
00316     (unsigned long) 65521,
00317     (unsigned long) 131071,
00318     (unsigned long) 262139,
00319     (unsigned long) 524287,
00320     (unsigned long) 1048573,
00321     (unsigned long) 2097143,
00322     (unsigned long) 4194301,
00323     (unsigned long) 8388593,
00324     (unsigned long) 16777213,
00325     (unsigned long) 33554393,
00326     (unsigned long) 67108859,
00327     (unsigned long) 134217689,
00328     (unsigned long) 268435399,
00329     (unsigned long) 536870909,
00330     (unsigned long) 1073741789,
00331     (unsigned long) 2147483647,
00332                                    /* 4294967291L */
00333     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
00334   };
00335 
00336   const unsigned long *low = &primes[0];
00337   const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
00338 
00339   while (low != high)
00340     {
00341       const unsigned long *mid = low + (high - low) / 2;
00342       if (n >= *mid)
00343        low = mid + 1;
00344       else
00345        high = mid;
00346     }
00347 
00348   if (n >= *low)
00349     return 0;
00350 
00351   return *low;
00352 }
00353 
00354 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
00355 
00356 /* Create a new hash table, given a number of entries.  */
00357 
00358 bfd_boolean
00359 bfd_hash_table_init_n (struct bfd_hash_table *table,
00360                      struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
00361                                                    struct bfd_hash_table *,
00362                                                    const char *),
00363                      unsigned int entsize,
00364                      unsigned int size)
00365 {
00366   unsigned int alloc;
00367 
00368   alloc = size * sizeof (struct bfd_hash_entry *);
00369 
00370   table->memory = (void *) objalloc_create ();
00371   if (table->memory == NULL)
00372     {
00373       bfd_set_error (bfd_error_no_memory);
00374       return FALSE;
00375     }
00376   table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
00377   if (table->table == NULL)
00378     {
00379       bfd_set_error (bfd_error_no_memory);
00380       return FALSE;
00381     }
00382   memset ((void *) table->table, 0, alloc);
00383   table->size = size;
00384   table->entsize = entsize;
00385   table->count = 0;
00386   table->frozen = 0;
00387   table->newfunc = newfunc;
00388   return TRUE;
00389 }
00390 
00391 /* Create a new hash table with the default number of entries.  */
00392 
00393 bfd_boolean
00394 bfd_hash_table_init (struct bfd_hash_table *table,
00395                    struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
00396                                                  struct bfd_hash_table *,
00397                                                  const char *),
00398                    unsigned int entsize)
00399 {
00400   return bfd_hash_table_init_n (table, newfunc, entsize,
00401                             bfd_default_hash_table_size);
00402 }
00403 
00404 /* Free a hash table.  */
00405 
00406 void
00407 bfd_hash_table_free (struct bfd_hash_table *table)
00408 {
00409   objalloc_free (table->memory);
00410   table->memory = NULL;
00411 }
00412 
00413 /* Look up a string in a hash table.  */
00414 
00415 struct bfd_hash_entry *
00416 bfd_hash_lookup (struct bfd_hash_table *table,
00417                const char *string,
00418                bfd_boolean create,
00419                bfd_boolean copy)
00420 {
00421   const unsigned char *s;
00422   unsigned long hash;
00423   unsigned int c;
00424   struct bfd_hash_entry *hashp;
00425   unsigned int len;
00426   unsigned int index;
00427 
00428   hash = 0;
00429   len = 0;
00430   s = (const unsigned char *) string;
00431   while ((c = *s++) != '\0')
00432     {
00433       hash += c + (c << 17);
00434       hash ^= hash >> 2;
00435     }
00436   len = (s - (const unsigned char *) string) - 1;
00437   hash += len + (len << 17);
00438   hash ^= hash >> 2;
00439 
00440   index = hash % table->size;
00441   for (hashp = table->table[index];
00442        hashp != NULL;
00443        hashp = hashp->next)
00444     {
00445       if (hashp->hash == hash
00446          && strcmp (hashp->string, string) == 0)
00447        return hashp;
00448     }
00449 
00450   if (! create)
00451     return NULL;
00452 
00453   hashp = (*table->newfunc) (NULL, table, string);
00454   if (hashp == NULL)
00455     return NULL;
00456   if (copy)
00457     {
00458       char *new;
00459 
00460       new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
00461       if (!new)
00462        {
00463          bfd_set_error (bfd_error_no_memory);
00464          return NULL;
00465        }
00466       memcpy (new, string, len + 1);
00467       string = new;
00468     }
00469   hashp->string = string;
00470   hashp->hash = hash;
00471   hashp->next = table->table[index];
00472   table->table[index] = hashp;
00473   table->count++;
00474 
00475   if (!table->frozen && table->count > table->size * 3 / 4)
00476     {
00477       unsigned long newsize = higher_prime_number (table->size);
00478       struct bfd_hash_entry **newtable;
00479       unsigned int hi;
00480       unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
00481 
00482       /* If we can't find a higher prime, or we can't possibly alloc
00483         that much memory, don't try to grow the table.  */
00484       if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
00485        {
00486          table->frozen = 1;
00487          return hashp;
00488        }
00489 
00490       newtable = ((struct bfd_hash_entry **)
00491                 objalloc_alloc ((struct objalloc *) table->memory, alloc));
00492       memset ((PTR) newtable, 0, alloc);
00493 
00494       for (hi = 0; hi < table->size; hi ++)
00495        while (table->table[hi])
00496          {
00497            struct bfd_hash_entry *chain = table->table[hi];
00498            struct bfd_hash_entry *chain_end = chain;
00499            int index;
00500 
00501            while (chain_end->next && chain_end->next->hash == chain->hash)
00502              chain_end = chain_end->next;
00503 
00504            table->table[hi] = chain_end->next;
00505            index = chain->hash % newsize;
00506            chain_end->next = newtable[index];
00507            newtable[index] = chain;
00508          }
00509       table->table = newtable;
00510       table->size = newsize;
00511     }
00512 
00513   return hashp;
00514 }
00515 
00516 /* Replace an entry in a hash table.  */
00517 
00518 void
00519 bfd_hash_replace (struct bfd_hash_table *table,
00520                 struct bfd_hash_entry *old,
00521                 struct bfd_hash_entry *nw)
00522 {
00523   unsigned int index;
00524   struct bfd_hash_entry **pph;
00525 
00526   index = old->hash % table->size;
00527   for (pph = &table->table[index];
00528        (*pph) != NULL;
00529        pph = &(*pph)->next)
00530     {
00531       if (*pph == old)
00532        {
00533          *pph = nw;
00534          return;
00535        }
00536     }
00537 
00538   abort ();
00539 }
00540 
00541 /* Allocate space in a hash table.  */
00542 
00543 void *
00544 bfd_hash_allocate (struct bfd_hash_table *table,
00545                  unsigned int size)
00546 {
00547   void * ret;
00548 
00549   ret = objalloc_alloc ((struct objalloc *) table->memory, size);
00550   if (ret == NULL && size != 0)
00551     bfd_set_error (bfd_error_no_memory);
00552   return ret;
00553 }
00554 
00555 /* Base method for creating a new hash table entry.  */
00556 
00557 struct bfd_hash_entry *
00558 bfd_hash_newfunc (struct bfd_hash_entry *entry,
00559                 struct bfd_hash_table *table,
00560                 const char *string ATTRIBUTE_UNUSED)
00561 {
00562   if (entry == NULL)
00563     entry = bfd_hash_allocate (table, sizeof (* entry));
00564   return entry;
00565 }
00566 
00567 /* Traverse a hash table.  */
00568 
00569 void
00570 bfd_hash_traverse (struct bfd_hash_table *table,
00571                  bfd_boolean (*func) (struct bfd_hash_entry *, void *),
00572                  void * info)
00573 {
00574   unsigned int i;
00575 
00576   table->frozen = 1;
00577   for (i = 0; i < table->size; i++)
00578     {
00579       struct bfd_hash_entry *p;
00580 
00581       for (p = table->table[i]; p != NULL; p = p->next)
00582        if (! (*func) (p, info))
00583          goto out;
00584     }
00585  out:
00586   table->frozen = 0;
00587 }
00588 
00589 void
00590 bfd_hash_set_default_size (bfd_size_type hash_size)
00591 {
00592   /* Extend this prime list if you want more granularity of hash table size.  */
00593   static const bfd_size_type hash_size_primes[] =
00594     {
00595       251, 509, 1021, 2039, 4051, 8599, 16699, 32749
00596     };
00597   size_t index;
00598 
00599   /* Work out best prime number near the hash_size.  */
00600   for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
00601     if (hash_size <= hash_size_primes[index])
00602       break;
00603 
00604   bfd_default_hash_table_size = hash_size_primes[index];
00605 }
00606 
00607 /* A few different object file formats (a.out, COFF, ELF) use a string
00608    table.  These functions support adding strings to a string table,
00609    returning the byte offset, and writing out the table.
00610 
00611    Possible improvements:
00612    + look for strings matching trailing substrings of other strings
00613    + better data structures?  balanced trees?
00614    + look at reducing memory use elsewhere -- maybe if we didn't have
00615      to construct the entire symbol table at once, we could get by
00616      with smaller amounts of VM?  (What effect does that have on the
00617      string table reductions?)  */
00618 
00619 /* An entry in the strtab hash table.  */
00620 
00621 struct strtab_hash_entry
00622 {
00623   struct bfd_hash_entry root;
00624   /* Index in string table.  */
00625   bfd_size_type index;
00626   /* Next string in strtab.  */
00627   struct strtab_hash_entry *next;
00628 };
00629 
00630 /* The strtab hash table.  */
00631 
00632 struct bfd_strtab_hash
00633 {
00634   struct bfd_hash_table table;
00635   /* Size of strtab--also next available index.  */
00636   bfd_size_type size;
00637   /* First string in strtab.  */
00638   struct strtab_hash_entry *first;
00639   /* Last string in strtab.  */
00640   struct strtab_hash_entry *last;
00641   /* Whether to precede strings with a two byte length, as in the
00642      XCOFF .debug section.  */
00643   bfd_boolean xcoff;
00644 };
00645 
00646 /* Routine to create an entry in a strtab.  */
00647 
00648 static struct bfd_hash_entry *
00649 strtab_hash_newfunc (struct bfd_hash_entry *entry,
00650                    struct bfd_hash_table *table,
00651                    const char *string)
00652 {
00653   struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
00654 
00655   /* Allocate the structure if it has not already been allocated by a
00656      subclass.  */
00657   if (ret == NULL)
00658     ret = bfd_hash_allocate (table, sizeof (* ret));
00659   if (ret == NULL)
00660     return NULL;
00661 
00662   /* Call the allocation method of the superclass.  */
00663   ret = (struct strtab_hash_entry *)
00664         bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
00665 
00666   if (ret)
00667     {
00668       /* Initialize the local fields.  */
00669       ret->index = (bfd_size_type) -1;
00670       ret->next = NULL;
00671     }
00672 
00673   return (struct bfd_hash_entry *) ret;
00674 }
00675 
00676 /* Look up an entry in an strtab.  */
00677 
00678 #define strtab_hash_lookup(t, string, create, copy) \
00679   ((struct strtab_hash_entry *) \
00680    bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
00681 
00682 /* Create a new strtab.  */
00683 
00684 struct bfd_strtab_hash *
00685 _bfd_stringtab_init (void)
00686 {
00687   struct bfd_strtab_hash *table;
00688   bfd_size_type amt = sizeof (* table);
00689 
00690   table = bfd_malloc (amt);
00691   if (table == NULL)
00692     return NULL;
00693 
00694   if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
00695                          sizeof (struct strtab_hash_entry)))
00696     {
00697       free (table);
00698       return NULL;
00699     }
00700 
00701   table->size = 0;
00702   table->first = NULL;
00703   table->last = NULL;
00704   table->xcoff = FALSE;
00705 
00706   return table;
00707 }
00708 
00709 /* Create a new strtab in which the strings are output in the format
00710    used in the XCOFF .debug section: a two byte length precedes each
00711    string.  */
00712 
00713 struct bfd_strtab_hash *
00714 _bfd_xcoff_stringtab_init (void)
00715 {
00716   struct bfd_strtab_hash *ret;
00717 
00718   ret = _bfd_stringtab_init ();
00719   if (ret != NULL)
00720     ret->xcoff = TRUE;
00721   return ret;
00722 }
00723 
00724 /* Free a strtab.  */
00725 
00726 void
00727 _bfd_stringtab_free (struct bfd_strtab_hash *table)
00728 {
00729   bfd_hash_table_free (&table->table);
00730   free (table);
00731 }
00732 
00733 /* Get the index of a string in a strtab, adding it if it is not
00734    already present.  If HASH is FALSE, we don't really use the hash
00735    table, and we don't eliminate duplicate strings.  */
00736 
00737 bfd_size_type
00738 _bfd_stringtab_add (struct bfd_strtab_hash *tab,
00739                   const char *str,
00740                   bfd_boolean hash,
00741                   bfd_boolean copy)
00742 {
00743   struct strtab_hash_entry *entry;
00744 
00745   if (hash)
00746     {
00747       entry = strtab_hash_lookup (tab, str, TRUE, copy);
00748       if (entry == NULL)
00749        return (bfd_size_type) -1;
00750     }
00751   else
00752     {
00753       entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
00754       if (entry == NULL)
00755        return (bfd_size_type) -1;
00756       if (! copy)
00757        entry->root.string = str;
00758       else
00759        {
00760          char *n;
00761 
00762          n = bfd_hash_allocate (&tab->table, strlen (str) + 1);
00763          if (n == NULL)
00764            return (bfd_size_type) -1;
00765          entry->root.string = n;
00766        }
00767       entry->index = (bfd_size_type) -1;
00768       entry->next = NULL;
00769     }
00770 
00771   if (entry->index == (bfd_size_type) -1)
00772     {
00773       entry->index = tab->size;
00774       tab->size += strlen (str) + 1;
00775       if (tab->xcoff)
00776        {
00777          entry->index += 2;
00778          tab->size += 2;
00779        }
00780       if (tab->first == NULL)
00781        tab->first = entry;
00782       else
00783        tab->last->next = entry;
00784       tab->last = entry;
00785     }
00786 
00787   return entry->index;
00788 }
00789 
00790 /* Get the number of bytes in a strtab.  */
00791 
00792 bfd_size_type
00793 _bfd_stringtab_size (struct bfd_strtab_hash *tab)
00794 {
00795   return tab->size;
00796 }
00797 
00798 /* Write out a strtab.  ABFD must already be at the right location in
00799    the file.  */
00800 
00801 bfd_boolean
00802 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
00803 {
00804   bfd_boolean xcoff;
00805   struct strtab_hash_entry *entry;
00806 
00807   xcoff = tab->xcoff;
00808 
00809   for (entry = tab->first; entry != NULL; entry = entry->next)
00810     {
00811       const char *str;
00812       size_t len;
00813 
00814       str = entry->root.string;
00815       len = strlen (str) + 1;
00816 
00817       if (xcoff)
00818        {
00819          bfd_byte buf[2];
00820 
00821          /* The output length includes the null byte.  */
00822          bfd_put_16 (abfd, (bfd_vma) len, buf);
00823          if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
00824            return FALSE;
00825        }
00826 
00827       if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
00828        return FALSE;
00829     }
00830 
00831   return TRUE;
00832 }