* hash.h: Neaten. Declare hash_traverse.

	* hash.c: Complete rewrite based on BFD hashing code.

1 files changed, 338 insertions, 765 deletions

diff --git a/gas/hash.c b/gas/hash.c
index dccd660754c..29066339c3a 100644
--- a/gas/hash.c
+++ b/gas/hash.c
@@ -1,5 +1,5 @@
-/* hash.c - hash table lookup strings -
-   Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 1998
+/* hash.c -- gas hash table code
+   Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 1999
    Free Software Foundation, Inc.
 
    This file is part of GAS, the GNU Assembler.
@@ -15,835 +15,408 @@
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with GAS; see the file COPYING.  If not, write to
-   the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
-
-/*
- * BUGS, GRIPES, APOLOGIA etc.
- *
- * A typical user doesn't need ALL this: I intend to make a library out
- * of it one day - Dean Elsner.
- * Also, I want to change the definition of a symbol to (address,length)
- * so I can put arbitrary binary in the names stored. [see hsh.c for that]
- *
- * This slime is common coupled inside the module. Com-coupling (and other
- * vandalism) was done to speed running time. The interfaces at the
- * module's edges are adequately clean.
- *
- * There is no way to (a) run a test script through this heap and (b)
- * compare results with previous scripts, to see if we have broken any
- * code. Use GNU (f)utilities to do this. A few commands assist test.
- * The testing is awkward: it tries to be both batch & interactive.
- * For now, interactive rules!
- */
-
-/*
- *  The idea is to implement a symbol table. A test jig is here.
- *  Symbols are arbitrary strings; they can't contain '\0'.
- *	[See hsh.c for a more general symbol flavour.]
- *  Each symbol is associated with a char*, which can point to anything
- *  you want, allowing an arbitrary property list for each symbol.
- *
- *  The basic operations are:
- *
- *    new                     creates symbol table, returns handle
- *    find (symbol)           returns char*
- *    insert (symbol,char*)   error if symbol already in table
- *    delete (symbol)         returns char* if symbol was in table
- *    apply                   so you can delete all symbols before die()
- *    die                     destroy symbol table (free up memory)
- *
- *  Supplementary functions include:
- *
- *    say                     how big? what % full?
- *    replace (symbol,newval) report previous value
- *    jam (symbol,value)      assert symbol:=value
- *
- *  You, the caller, have control over errors: this just reports them.
- *
- *  This package requires malloc(), free().
- *  Malloc(size) returns NULL or address of char[size].
- *  Free(address) frees same.
- */
-
-/*
- *  The code and its structures are re-enterent.
- *
- *  Before you do anything else, you must call hash_new() which will
- *  return the address of a hash-table-control-block.  You then use
- *  this address as a handle of the symbol table by passing it to all
- *  the other hash_...() functions.  The only approved way to recover
- *  the memory used by the symbol table is to call hash_die() with the
- *  handle of the symbol table.
- *
- *  Before you call hash_die() you normally delete anything pointed to
- *  by individual symbols. After hash_die() you can't use that symbol
- *  table again.
- *
- *  The char* you associate with a symbol may not be NULL (0) because
- *  NULL is returned whenever a symbol is not in the table. Any other
- *  value is OK, except DELETED, #defined below.
- *
- *  When you supply a symbol string for insertion, YOU MUST PRESERVE THE
- *  STRING until that symbol is deleted from the table. The reason is that
- *  only the address you supply, NOT the symbol string itself, is stored
- *  in the symbol table.
- *
- *  You may delete and add symbols arbitrarily.
- *  Any or all symbols may have the same 'value' (char *). In fact, these
- *  routines don't do anything with your symbol values.
- *
- *  You have no right to know where the symbol:char* mapping is stored,
- *  because it moves around in memory; also because we may change how it
- *  works and we don't want to break your code do we? However the handle
- *  (address of struct hash_control) is never changed in
- *  the life of the symbol table.
- *
- *  What you CAN find out about a symbol table is:
- *    how many slots are in the hash table?
- *    how many slots are filled with symbols?
- *    (total hashes,collisions) for (reads,writes) (*)
- *  All of the above values vary in time.
- *  (*) some of these numbers will not be meaningful if we change the
- *  internals. */
-
-/*
- *  I N T E R N A L
- *
- *  Hash table is an array of hash_entries; each entry is a pointer to a
- *  a string and a user-supplied value 1 char* wide.
- *
- *  The array always has 2 ** n elements, n>0, n integer.
- *  There is also a 'wall' entry after the array, which is always empty
- *  and acts as a sentinel to stop running off the end of the array.
- *  When the array gets too full, we create a new array twice as large
- *  and re-hash the symbols into the new array, then forget the old array.
- *  (Of course, we copy the values into the new array before we junk the
- *  old array!)
- *
- */
-
-#include <stdio.h>
-
-#ifndef FALSE
-#define FALSE	(0)
-#define TRUE	(!FALSE)
-#endif /* no FALSE yet */
-
-#include <ctype.h>
-#define min(a, b)	((a) < (b) ? (a) : (b))
+   along with GAS; see the file COPYING.  If not, write to the Free
+   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.  */
+
+/* This version of the hash table code is a wholescale replacement of
+   the old hash table code, which was fairly bad.  This is based on
+   the hash table code in BFD, but optimized slightly for the
+   asssembler.  The assembler does not need to derive structures that
+   are stored in the hash table.  Instead, it always stores a pointer.
+   The assembler uses the hash table mostly to store symbols, and we
+   don't need to confuse the symbol structure with a hash table
+   structure.  */
 
 #include "as.h"
+#include "obstack.h"
 
-#define error	as_fatal
-
-static char _deleted_[1];
-#define DELETED     ((PTR)_deleted_)	/* guarenteed unique address */
-#define START_POWER    (10)	/* power of two: size of new hash table */
-
-/* TRUE if a symbol is in entry @ ptr.  */
-#define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
-
-enum stat_enum {
-  /* Number of slots in hash table.  The wall does not count here.
-     We expect this is always a power of 2.  */
-  STAT_SIZE = 0,
-  /* Number of hash_ask calls.  */
-  STAT_ACCESS,
-  STAT_ACCESS_w,
-  /* Number of collisions (total).  This may exceed STAT_ACCESS if we
-     have lots of collisions/access.  */
-  STAT_COLLIDE,
-  STAT_COLLIDE_w,
-  /* Slots used right now.  */
-  STAT_USED,
-  /* How many string compares?  */
-  STAT_STRCMP,
-  STAT_STRCMP_w,
-  /* Size of statistics block... this must be last.  */
-  STATLENGTH
-};
-#define STAT__READ     (0)	/* reading */
-#define STAT__WRITE    (1)	/* writing */
+/* The default number of entries to use when creating a hash table.  */
 
-/* When we grow a hash table, by what power of two do we increase it?  */
-#define GROW_FACTOR 1
-/* When should we grow it?  */
-#define FULL_VALUE(N)	((N) / 2)
+#define DEFAULT_SIZE (4051)
 
-/* #define SUSPECT to do runtime checks */
-/* #define TEST to be a test jig for hash...() */
+/* An entry in a hash table.  */
 
-#ifdef TEST
-/* TEST: use smaller hash table */
-#undef  START_POWER
-#define START_POWER (3)
-#undef  START_SIZE
-#define START_SIZE  (8)
-#undef  START_FULL
-#define START_FULL  (4)
-#endif
-
 struct hash_entry
 {
-  const char *hash_string;	/* points to where the symbol string is */
-  /* NULL means slot is not used */
-  /* DELETED means slot was deleted */
-  PTR hash_value;		/* user's datum, associated with symbol */
-  unsigned long h;
+  /* Next entry for this hash code.  */
+  struct hash_entry *next;
+  /* String being hashed.  */
+  const char *string;
+  /* Hash code.  This is the full hash code, not the index into the
+     table.  */
+  unsigned long hash;
+  /* Pointer being stored in the hash table.  */
+  PTR data;
 };
 
-struct hash_control {
-  struct hash_entry *hash_where;/* address of hash table */
-  int hash_sizelog;		/* Log of ( hash_mask + 1 ) */
-  int hash_mask;		/* masks a hash into index into table */
-  int hash_full;		/* when hash_stat[STAT_USED] exceeds this, */
-  /* grow table */
-  struct hash_entry *hash_wall;	/* point just after last (usable) entry */
-  /* here we have some statistics */
-  int hash_stat[STATLENGTH];	/* lies & statistics */
+/* A hash table.  */
+
+struct hash_control
+{
+  /* The hash array.  */
+  struct hash_entry **table;
+  /* The number of slots in the hash table.  */
+  unsigned int size;
+  /* An obstack for this hash table.  */
+  struct obstack memory;
+
+#ifdef HASH_STATISTICS
+  /* Statistics.  */
+  unsigned long lookups;
+  unsigned long hash_compares;
+  unsigned long string_compares;
+  unsigned long insertions;
+  unsigned long replacements;
+  unsigned long deletions;
+#endif /* HASH_STATISTICS */
 };
-
-/*------------------ plan ---------------------------------- i = internal
-
-  struct hash_control * c;
-  struct hash_entry   * e;                                                    i
-  int                   b[z];     buffer for statistics
-  z         size of b
-  char                * s;        symbol string (address) [ key ]
-  char                * v;        value string (address)  [datum]
-  boolean               f;        TRUE if we found s in hash table            i
-  char                * t;        error string; 0 means OK
-  int                   a;        access type [0...n)                         i
-
-  c=hash_new       ()             create new hash_control
-
-  hash_die         (c)            destroy hash_control (and hash table)
-  table should be empty.
-  doesn't check if table is empty.
-  c has no meaning after this.
-
-  hash_say         (c,b,z)        report statistics of hash_control.
-  also report number of available statistics.
-
-  v=hash_delete    (c,s)          delete symbol, return old value if any.
-  ask()                       NULL means no old value.
-  f
-
-  v=hash_replace   (c,s,v)        replace old value of s with v.
-  ask()                       NULL means no old value: no table change.
-  f
-
-  t=hash_insert    (c,s,v)        insert (s,v) in c.
-  ask()                       return error string.
-  f                           it is an error to insert if s is already
-  in table.
-  if any error, c is unchanged.
-
-  t=hash_jam       (c,s,v)        assert that new value of s will be v.       i
-  ask()                       it may decide to GROW the table.            i
-  f                                                                       i
-  grow()                                                                  i
-  t=hash_grow      (c)            grow the hash table.                        i
-  jam()                       will invoke JAM.                            i
-
-  ?=hash_apply     (c,y)          apply y() to every symbol in c.
-  y                           evtries visited in 'unspecified' order.
-
-  v=hash_find      (c,s)          return value of s, or NULL if s not in c.
-  ask()
-  f
-
-  f,e=hash_ask()   (c,s,a)        return slot where s SHOULD live.            i
-  code()                      maintain collision stats in c.              i
-
-  .=hash_code      (c,s)          compute hash-code for s,                    i
-  from parameters of c.                       i
-
-  */
-
-/* Returned by hash_ask() to stop extra testing. hash_ask() wants to
-   return both a slot and a status. This is the status.  TRUE: found
-   symbol FALSE: absent: empty or deleted slot Also returned by
-   hash_jam().  TRUE: we replaced a value FALSE: we inserted a value.  */
-static char hash_found;
-
-static struct hash_entry *hash_ask PARAMS ((struct hash_control *,
-					    const char *, int));
-static int hash_code PARAMS ((struct hash_control *, const char *));
-static const char *hash_grow PARAMS ((struct hash_control *));
-
-/* Create a new hash table.  Return NULL if failed; otherwise return handle
-   (address of struct hash).  */
+
+/* Create a hash table.  This return a control block.  */
+
 struct hash_control *
 hash_new ()
 {
-  struct hash_control *retval;
-  struct hash_entry *room;	/* points to hash table */
-  struct hash_entry *wall;
-  struct hash_entry *entry;
-  int *ip;		/* scan stats block of struct hash_control */
-  int *nd;		/* limit of stats block */
-
-  room = (struct hash_entry *) xmalloc (sizeof (struct hash_entry)
-					/* +1 for the wall entry */
-					* ((1 << START_POWER) + 1));
-  retval = (struct hash_control *) xmalloc (sizeof (struct hash_control));
-
-  nd = retval->hash_stat + STATLENGTH;
-  for (ip = retval->hash_stat; ip < nd; ip++)
-    *ip = 0;
-
-  retval->hash_stat[STAT_SIZE] = 1 << START_POWER;
-  retval->hash_mask = (1 << START_POWER) - 1;
-  retval->hash_sizelog = START_POWER;
-  /* works for 1's compl ok */
-  retval->hash_where = room;
-  retval->hash_wall =
-    wall = room + (1 << START_POWER);
-  retval->hash_full = FULL_VALUE (1 << START_POWER);
-  for (entry = room; entry <= wall; entry++)
-    entry->hash_string = NULL;
-  return retval;
+  unsigned int size;
+  struct hash_control *ret;
+  unsigned int alloc;
+
+  size = DEFAULT_SIZE;
+
+  ret = (struct hash_control *) xmalloc (sizeof *ret);
+  obstack_begin (&ret->memory, chunksize);
+  alloc = size * sizeof (struct hash_entry *);
+  ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
+  memset (ret->table, 0, alloc);
+  ret->size = size;
+
+#ifdef HASH_STATISTICS
+  ret->lookups = 0;
+  ret->hash_compares = 0;
+  ret->string_compares = 0;
+  ret->insertions = 0;
+  ret->replacements = 0;
+  ret->deletions = 0;
+#endif
+
+  return ret;  
 }
 
-/*
- *           h a s h _ d i e ( )
- *
- * Table should be empty, but this is not checked.
- * To empty the table, try hash_apply()ing a symbol deleter.
- * Return to free memory both the hash table and it's control
- * block.
- * 'handle' has no meaning after this function.
- * No errors are recoverable.
- */
+/* Delete a hash table, freeing all allocated memory.  */
+
 void
-hash_die (handle)
-     struct hash_control *handle;
+hash_die (table)
+     struct hash_control *table;
 {
-  free ((char *) handle->hash_where);
-  free ((char *) handle);
+  obstack_free (&table->memory, 0);
+  free (table);
 }
-
-#ifdef TEST
-/*
- *           h a s h _ s a y ( )
- *
- * Return the size of the statistics table, and as many statistics as
- * we can until either (a) we have run out of statistics or (b) caller
- * has run out of buffer.
- * NOTE: hash_say treats all statistics alike.
- * These numbers may change with time, due to insertions, deletions
- * and expansions of the table.
- * The first "statistic" returned is the length of hash_stat[].
- * Then contents of hash_stat[] are read out (in ascending order)
- * until your buffer or hash_stat[] is exausted.
- */
-static void
-hash_say (handle, buffer, bufsiz)
-     struct hash_control *handle;
-     int buffer[ /*bufsiz*/ ];
-     int bufsiz;
+
+/* Look up a string in a hash table.  This returns a pointer to the
+   hash_entry, or NULL if the string is not in the table.  If PLIST is
+   not NULL, this sets *PLIST to point to the start of the list which
+   would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
+   to the hash code for KEY.
+
+   Each time we look up a string, we move it to the start of the list
+   for its hash code, to take advantage of referential locality.  */
+
+static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
+					       const char *,
+					       struct hash_entry ***,
+					       unsigned long *));
+
+static struct hash_entry *
+hash_lookup (table, key, plist, phash)
+     struct hash_control *table;
+     const char *key;
+     struct hash_entry ***plist;
+     unsigned long *phash;
 {
-  int *nd;		/* limit of statistics block */
-  int *ip;		/* scan statistics */
+  register unsigned long hash;
+  unsigned int len;
+  register const unsigned char *s;
+  register unsigned int c;
+  unsigned int index;
+  struct hash_entry **list;
+  struct hash_entry *p;
+  struct hash_entry *prev;
+
+#ifdef HASH_STATISTICS
+  ++table->lookups;
+#endif
 
-  ip = handle->hash_stat;
-  nd = ip + min (bufsiz - 1, STATLENGTH);
-  if (bufsiz > 0)		/* trust nothing! bufsiz<=0 is dangerous */
+  hash = 0;
+  len = 0;
+  s = (const unsigned char *) key;
+  while ((c = *s++) != '\0')
     {
-      *buffer++ = STATLENGTH;
-      for (; ip < nd; ip++, buffer++)
-	{
-	  *buffer = *ip;
-	}
+      hash += c + (c << 17);
+      hash ^= hash >> 2;
+      ++len;
     }
-}
-#endif
-
-/*
- *           h a s h _ d e l e t e ( )
- *
- * Try to delete a symbol from the table.
- * If it was there, return its value (and adjust STAT_USED).
- * Otherwise, return NULL.
- * Anyway, the symbol is not present after this function.
- *
- */
-PTR				/* NULL if string not in table, else */
-/* returns value of deleted symbol */
-hash_delete (handle, string)
-     struct hash_control *handle;
-     const char *string;
-{
-  PTR retval;
-  struct hash_entry *entry;
+  hash += len + (len << 17);
+  hash ^= hash >> 2;
+
+  if (phash != NULL)
+    *phash = hash;
+
+  index = hash % table->size;
+  list = table->table + index;
 
-  entry = hash_ask (handle, string, STAT__WRITE);
-  if (hash_found)
+  if (plist != NULL)
+    *plist = list;
+
+  prev = NULL;
+  for (p = *list; p != NULL; p = p->next)
     {
-      retval = entry->hash_value;
-      entry->hash_string = DELETED;
-      handle->hash_stat[STAT_USED] -= 1;
-#ifdef SUSPECT
-      if (handle->hash_stat[STAT_USED] < 0)
+#ifdef HASH_STATISTICS
+      ++table->hash_compares;
+#endif
+
+      if (p->hash == hash)
 	{
-	  error ("hash_delete");
+#ifdef HASH_STATISTICS
+	  ++table->string_compares;
+#endif
+
+	  if (strcmp (p->string, key) == 0)
+	    {
+	      if (prev != NULL)
+		{
+		  prev->next = p->next;
+		  p->next = *list;
+		  *list = p;
+		}
+
+	      return p;
+	    }
 	}
-#endif /* def SUSPECT */
-    }
-  else
-    {
-      retval = NULL;
-    }
-  return (retval);
-}
-
-/*
- *                   h a s h _ r e p l a c e ( )
- *
- * Try to replace the old value of a symbol with a new value.
- * Normally return the old value.
- * Return NULL and don't change the table if the symbol is not already
- * in the table.
- */
-PTR
-hash_replace (handle, string, value)
-     struct hash_control *handle;
-     const char *string;
-     PTR value;
-{
-  struct hash_entry *entry;
-  char *retval;
 
-  entry = hash_ask (handle, string, STAT__WRITE);
-  if (hash_found)
-    {
-      retval = entry->hash_value;
-      entry->hash_value = value;
-    }
-  else
-    {
-      retval = NULL;
+      prev = p;
     }
-  ;
-  return retval;
+
+  return NULL;
 }
-
-/*
- *                   h a s h _ i n s e r t ( )
- *
- * Insert a (symbol-string, value) into the hash table.
- * Return an error string, 0 means OK.
- * It is an 'error' to insert an existing symbol.
- */
-
-const char *			/* return error string */
-hash_insert (handle, string, value)
-     struct hash_control *handle;
-     const char *string;
+
+/* Insert an entry into a hash table.  This returns NULL on success.
+   On error, it returns a printable string indicating the error.  It
+   is considered to be an error if the entry already exists in the
+   hash table.  */
+
+const char *
+hash_insert (table, key, value)
+     struct hash_control *table;
+     const char *key;
      PTR value;
 {
-  struct hash_entry *entry;
-  const char *retval;
+  struct hash_entry *p;
+  struct hash_entry **list;
+  unsigned long hash;
 
-  retval = 0;
-  if (handle->hash_stat[STAT_USED] > handle->hash_full)
-    {
-      retval = hash_grow (handle);
-    }
-  if (!retval)
-    {
-      entry = hash_ask (handle, string, STAT__WRITE);
-      if (hash_found)
-	{
-	  retval = "exists";
-	}
-      else
-	{
-	  entry->hash_value = value;
-	  entry->hash_string = string;
-	  handle->hash_stat[STAT_USED] += 1;
-	}
-    }
-  return retval;
+  p = hash_lookup (table, key, &list, &hash);
+  if (p != NULL)
+    return "exists";
+
+#ifdef HASH_STATISTICS
+  ++table->insertions;
+#endif
+
+  p = obstack_alloc (&table->memory, sizeof *p);
+  p->string = key;
+  p->hash = hash;
+  p->data = value;
+
+  p->next = *list;
+  *list = p;
+
+  return NULL;
 }
-
-/*
- *               h a s h _ j a m ( )
- *
- * Regardless of what was in the symbol table before, after hash_jam()
- * the named symbol has the given value. The symbol is either inserted or
- * (its value is) replaced.
- * An error message string is returned, 0 means OK.
- *
- * WARNING: this may decide to grow the hashed symbol table.
- * To do this, we call hash_grow(), WHICH WILL recursively CALL US.
- *
- * We report status internally: hash_found is TRUE if we replaced, but
- * false if we inserted.
- */
+
+/* Insert or replace an entry in a hash table.  This returns NULL on
+   success.  On error, it returns a printable string indicating the
+   error.  If an entry already exists, its value is replaced.  */
+
 const char *
-hash_jam (handle, string, value)
-     struct hash_control *handle;
-     const char *string;
+hash_jam (table, key, value)
+     struct hash_control *table;
+     const char *key;
      PTR value;
 {
-  const char *retval;
-  struct hash_entry *entry;
+  struct hash_entry *p;
+  struct hash_entry **list;
+  unsigned long hash;
 
-  retval = 0;
-  if (handle->hash_stat[STAT_USED] > handle->hash_full)
+  p = hash_lookup (table, key, &list, &hash);
+  if (p != NULL)
     {
-      retval = hash_grow (handle);
+#ifdef HASH_STATISTICS
+      ++table->replacements;
+#endif
+
+      p->data = value;
     }
-  if (!retval)
+  else
     {
-      entry = hash_ask (handle, string, STAT__WRITE);
-      if (!hash_found)
-	{
-	  entry->hash_string = string;
-	  handle->hash_stat[STAT_USED] += 1;
-	}
-      entry->hash_value = value;
+#ifdef HASH_STATISTICS
+      ++table->insertions;
+#endif
+
+      p = obstack_alloc (&table->memory, sizeof *p);
+      p->string = key;
+      p->hash = hash;
+      p->data = value;
+
+      p->next = *list;
+      *list = p;
     }
-  return retval;
+
+  return NULL;
 }
 
-/*
- *               h a s h _ g r o w ( )
- *
- * Grow a new (bigger) hash table from the old one.
- * We choose to double the hash table's size.
- * Return a human-scrutible error string: 0 if OK.
- * Warning! This uses hash_jam(), which had better not recurse
- * back here! Hash_jam() conditionally calls us, but we ALWAYS
- * call hash_jam()!
- * Internal.
- */
-static const char *
-hash_grow (handle)		/* make a hash table grow */
-     struct hash_control *handle;
+/* Replace an existing entry in a hash table.  This returns the old
+   value stored for the entry.  If the entry is not found in the hash
+   table, this does nothing and returns NULL.  */
+
+PTR
+hash_replace (table, key, value)
+     struct hash_control *table;
+     const char *key;
+     PTR value;
 {
-  struct hash_entry *newwall;
-  struct hash_entry *newwhere;
-  struct hash_entry *newtrack;
-  struct hash_entry *oldtrack;
-  struct hash_entry *oldwhere;
-  struct hash_entry *oldwall;
-  int temp;
-  int newsize;
-  const char *string;
-  const char *retval;
-#ifdef SUSPECT
-  int oldused;
-#endif
+  struct hash_entry *p;
+  PTR ret;
 
-  /*
-   * capture info about old hash table
-   */
-  oldwhere = handle->hash_where;
-  oldwall = handle->hash_wall;
-#ifdef SUSPECT
-  oldused = handle->hash_stat[STAT_USED];
-#endif
-  /*
-   * attempt to get enough room for a hash table twice as big
-   */
-  temp = handle->hash_stat[STAT_SIZE];
-  newwhere = ((struct hash_entry *)
-	      xmalloc ((unsigned long) ((temp << (GROW_FACTOR + 1))
-					/* +1 for wall slot */
-					* sizeof (struct hash_entry))));
-  if (newwhere == NULL)
-    return "no_room";
-
-  /*
-   * have enough room: now we do all the work.
-   * double the size of everything in handle.
-   */
-  handle->hash_mask = ((handle->hash_mask + 1) << GROW_FACTOR) - 1;
-  handle->hash_stat[STAT_SIZE] <<= GROW_FACTOR;
-  newsize = handle->hash_stat[STAT_SIZE];
-  handle->hash_where = newwhere;
-  handle->hash_full <<= GROW_FACTOR;
-  handle->hash_sizelog += GROW_FACTOR;
-  handle->hash_wall = newwall = newwhere + newsize;
-  /* Set all those pesky new slots to vacant.  */
-  for (newtrack = newwhere; newtrack <= newwall; newtrack++)
-    newtrack->hash_string = NULL;
-  /* We will do a scan of the old table, the hard way, using the
-   * new control block to re-insert the data into new hash table.  */
-  handle->hash_stat[STAT_USED] = 0;
-  for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++)
-    if (((string = oldtrack->hash_string) != NULL) && string != DELETED)
-      if ((retval = hash_jam (handle, string, oldtrack->hash_value)))
-	return retval;
-
-#ifdef SUSPECT
-  if (handle->hash_stat[STAT_USED] != oldused)
-    return "hash_used";
+  p = hash_lookup (table, key, NULL, NULL);
+  if (p == NULL)
+    return NULL;
+
+#ifdef HASH_STATISTICS
+  ++table->replacements;
 #endif
 
-  /* We have a completely faked up control block.
-     Return the old hash table.  */
-  free ((char *) oldwhere);
+  ret = p->data;
 
-  return 0;
-}
-
-#ifdef TEST
-/*
- *          h a s h _ a p p l y ( )
- *
- * Use this to scan each entry in symbol table.
- * For each symbol, this calls (applys) a nominated function supplying the
- * symbol's value (and the symbol's name).
- * The idea is you use this to destroy whatever is associted with
- * any values in the table BEFORE you destroy the table with hash_die.
- * Of course, you can use it for other jobs; whenever you need to
- * visit all extant symbols in the table.
- *
- * We choose to have a call-you-back idea for two reasons:
- *  asthetic: it is a neater idea to use apply than an explicit loop
- *  sensible: if we ever had to grow the symbol table (due to insertions)
- *            then we would lose our place in the table when we re-hashed
- *            symbols into the new table in a different order.
- *
- * The order symbols are visited depends entirely on the hashing function.
- * Whenever you insert a (symbol, value) you risk expanding the table. If
- * you do expand the table, then the hashing function WILL change, so you
- * MIGHT get a different order of symbols visited. In other words, if you
- * want the same order of visiting symbols as the last time you used
- * hash_apply() then you better not have done any hash_insert()s or
- * hash_jam()s since the last time you used hash_apply().
- *
- * In future we may use the value returned by your nominated function.
- * One idea is to abort the scan if, after applying the function to a
- * certain node, the function returns a certain code.
- *
- * The function you supply should be of the form:
- *      void myfunct(string,value)
- *              char * string;        |* the symbol's name *|
- *              char * value;         |* the symbol's value *|
- *      {
- *        |* ... *|
- *      }
- *
- */
-void
-hash_apply (handle, function)
-     struct hash_control *handle;
-     void (*function) ();
-{
-  struct hash_entry *entry;
-  struct hash_entry *wall;
+  p->data = value;
 
-  wall = handle->hash_wall;
-  for (entry = handle->hash_where; entry < wall; entry++)
-    {
-      if (islive (entry))	/* silly code: tests entry->string twice! */
-	{
-	  (*function) (entry->hash_string, entry->hash_value);
-	}
-    }
+  return ret;
 }
-#endif
-
-/*
- *          h a s h _ f i n d ( )
- *
- * Given symbol string, find value (if any).
- * Return found value or NULL.
- */
+
+/* Find an entry in a hash table, returning its value.  Returns NULL
+   if the entry is not found.  */
+
 PTR
-hash_find (handle, string)
-     struct hash_control *handle;
-     const char *string;
+hash_find (table, key)
+     struct hash_control *table;
+     const char *key;
 {
-  struct hash_entry *entry;
+  struct hash_entry *p;
 
-  entry = hash_ask (handle, string, STAT__READ);
-  if (hash_found)
-    return entry->hash_value;
-  else
+  p = hash_lookup (table, key, NULL, NULL);
+  if (p == NULL)
     return NULL;
+
+  return p->data;
 }
-
-/*
- *          h a s h _ a s k ( )
- *
- * Searches for given symbol string.
- * Return the slot where it OUGHT to live. It may be there.
- * Return hash_found: TRUE only if symbol is in that slot.
- * Access argument is to help keep statistics in control block.
- * Internal.
- */
-static struct hash_entry *	/* string slot, may be empty or deleted */
-hash_ask (handle, string, access_type)
-     struct hash_control *handle;
-     const char *string;
-     int access_type;
-{
-  const char *s;
-  struct hash_entry *slot;
-  int collision;	/* count collisions */
-  int strcmps;
-  int hcode;
-
-  /* start looking here */
-  hcode = hash_code (handle, string);
-  slot = handle->hash_where + (hcode & handle->hash_mask);
-
-  handle->hash_stat[STAT_ACCESS + access_type] += 1;
-  collision = strcmps = 0;
-  hash_found = FALSE;
-  while (((s = slot->hash_string) != NULL) && s != DELETED)
-    {
-      if (string == s)
-	{
-	  hash_found = TRUE;
-	  break;
-	}
-      if (slot->h == (unsigned long) hcode)
-	{
-	  if (!strcmp (string, s))
-	    {
-	      hash_found = TRUE;
-	      break;
-	    }
-	  strcmps++;
-	}
-      collision++;
-      slot++;
-    }
-  /*
-   * slot:                                                      return:
-   *       in use:     we found string                           slot
-   *       at empty:
-   *                   at wall:        we fell off: wrap round   ????
-   *                   in table:       dig here                  slot
-   *       at DELETED: dig here                                  slot
-   */
-  if (slot == handle->hash_wall)
-    {
-      slot = handle->hash_where;/* now look again */
-      while (((s = slot->hash_string) != NULL) && s != DELETED)
-	{
-	  if (string == s)
-	    {
-	      hash_found = TRUE;
-	      break;
-	    }
-	  if (slot->h == (unsigned long) hcode)
-	    {
-	      if (!strcmp (string, s))
-		{
-		  hash_found = TRUE;
-		  break;
-		}
-	      strcmps++;
-	    }
-	  collision++;
-	  slot++;
-	}
-      /*
-       * slot:                                                   return:
-       *       in use: we found it                                slot
-       *       empty:  wall:         ERROR IMPOSSIBLE             !!!!
-       *               in table:     dig here                     slot
-       *       DELETED:dig here                                   slot
-       */
-    }
-  handle->hash_stat[STAT_COLLIDE + access_type] += collision;
-  handle->hash_stat[STAT_STRCMP + access_type] += strcmps;
-  if (!hash_found)
-    slot->h = hcode;
-  return slot;			/* also return hash_found */
-}
-
-/*
- *           h a s h _ c o d e
- *
- * Does hashing of symbol string to hash number.
- * Internal.
- */
-static int
-hash_code (handle, string)
-     struct hash_control *handle;
-     const char *string;
+
+/* Delete an entry from a hash table.  This returns the value stored
+   for that entry, or NULL if there is no such entry.  */
+
+PTR
+hash_delete (table, key)
+     struct hash_control *table;
+     const char *key;
 {
-#if 1 /* There seems to be some interesting property of this function
-	 that prevents the bfd version below from being an adequate
-	 substitute.  @@ Figure out what this property is!  */
-  long h;		/* hash code built here */
-  long c;		/* each character lands here */
-  int n;		/* Amount to shift h by */
-
-  n = (handle->hash_sizelog - 3);
-  h = 0;
-  while ((c = *string++) != 0)
-    {
-      h += c;
-      h = (h << 3) + (h >> n) + c;
-    }
-  return h;
-#else
-  /* from bfd */
-  unsigned long h = 0;
-  unsigned int len = 0;
-  unsigned int c;
-
-  while ((c = *string++) != 0)
-    {
-      h += c + (c << 17);
-      h ^= h >> 2;
-      ++len;
-    }
-  h += len + (len << 17);
-  h ^= h >> 2;
-  return h;
+  struct hash_entry *p;
+  struct hash_entry **list;
+
+  p = hash_lookup (table, key, &list, NULL);
+  if (p == NULL)
+    return NULL;
+
+  if (p != *list)
+    abort ();
+
+#ifdef HASH_STATISTICS
+  ++table->deletions;
 #endif
+
+  *list = p->next;
+
+  /* Note that we never reclaim the memory for this entry.  If gas
+     ever starts deleting hash table entries in a big way, this will
+     have to change.  */
+
+  return p->data;
 }
-
+
+/* Traverse a hash table.  Call the function on every entry in the
+   hash table.  */
+
 void
-hash_print_statistics (file, name, h)
-     FILE *file;
-     const char *name;
-     struct hash_control *h;
+hash_traverse (table, pfn)
+     struct hash_control *table;
+     void (*pfn) PARAMS ((const char *key, PTR value));
 {
-  unsigned long sz, used, pct;
+  unsigned int i;
 
-  if (h == 0)
-    return;
+  for (i = 0; i < table->size; ++i)
+    {
+      struct hash_entry *p;
 
-  sz = h->hash_stat[STAT_SIZE];
-  used = h->hash_stat[STAT_USED];
-  pct = (used * 100 + sz / 2) / sz;
+      for (p = table->table[i]; p != NULL; p = p->next)
+	(*pfn) (p->string, p->data);
+    }
+}
 
-  fprintf (file, "%s hash statistics:\n\t%lu/%lu slots used (%lu%%)\n",
-	   name, used, sz, pct);
+/* Print hash table statistics on the specified file.  NAME is the
+   name of the hash table, used for printing a header.  */
 
-#define P(name, off)							\
-  fprintf (file, "\t%-16s %6dr + %6dw = %7d\n", name,			\
-	   h->hash_stat[off+STAT__READ],				\
-	   h->hash_stat[off+STAT__WRITE],				\
-	   h->hash_stat[off+STAT__READ] + h->hash_stat[off+STAT__WRITE])
+void
+hash_print_statistics (f, name, table)
+     FILE *f;
+     const char *name;
+     struct hash_control *table;
+{
+#ifdef HASH_STATISTICS
+  unsigned int i;
+  unsigned long total;
+  unsigned long empty;
+
+  fprintf (f, "%s hash statistics:\n", name);
+  fprintf (f, "\t%lu lookups\n", table->lookups);
+  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
+  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
+  fprintf (f, "\t%lu insertions\n", table->insertions);
+  fprintf (f, "\t%lu replacements\n", table->replacements);
+  fprintf (f, "\t%lu deletions\n", table->deletions);
+
+  total = 0;
+  empty = 0;
+  for (i = 0; i < table->size; ++i)
+    {
+      struct hash_entry *p;
 
-  P ("accesses:", STAT_ACCESS);
-  P ("collisions:", STAT_COLLIDE);
-  P ("string compares:", STAT_STRCMP);
+      if (table->table[i] == NULL)
+	++empty;
+      else
+	{
+	  for (p = table->table[i]; p != NULL; p = p->next)
+	    ++total;
+	}
+    }
 
-#undef P
+  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
+  fprintf (f, "\t%lu empty slots\n", empty);
+#endif
 }
 
-/*
- * Here is a test program to exercise above.
- */
 #ifdef TEST
 
+/* This test program is left over from the old hash table code.  */
+
 #define TABLES (6)		/* number of hash tables to maintain */
-/* (at once) in any testing */
+				/* (at once) in any testing */
 #define STATBUFSIZE (12)	/* we can have 12 statistics */
 
 int statbuf[STATBUFSIZE];	/* display statistics here */
@@ -858,8 +431,9 @@ int size;
 int used;
 char command;
 int number;			/* number 0:TABLES-1 of current hashed */
-/* symbol table */
+				/* symbol table */
 
+int
 main ()
 {
   void applicatee ();
@@ -891,10 +465,10 @@ main ()
 	    }
 	  break;
 	case 'a':
-	  hash_apply (h, applicatee);
+	  hash_traverse (h, applicatee);
 	  break;
 	case 'd':
-	  hash_apply (h, destroy);
+	  hash_traverse (h, destroy);
 	  hash_die (h);
 	  break;
 	case 'f':
@@ -996,8 +570,9 @@ applicatee (string, value)
   printf ("%.20s-%.20s\n", string, value);
 }
 
+void
 whattable ()			/* determine number: what hash table to use */
-     /* also determine h: points to hash_control */
+			        /* also determine h: points to hash_control */
 {
 
   for (;;)
@@ -1021,8 +596,6 @@ whattable ()			/* determine number: what hash table to use */
     }
 }
 
-
-
 #endif /* #ifdef TEST */
 
 /* end of hash.c */