X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gas%2Fhash.c;h=2d11a1d453b2926bc94caaa95259c8be2c9117b0;hb=0dc4c667aceab372c5500045bd76a4c93af315ca;hp=276b8f5b9badff33cf78e36760804c8e3fbd2f22;hpb=b2683e0914903c870e5782e1cf8501a5ac291a0a;p=binutils-gdb.git

diff --git a/gas/hash.c b/gas/hash.c
index 276b8f5b9ba..2d11a1d453b 100644
--- a/gas/hash.c
+++ b/gas/hash.c
@@ -15,7 +15,7 @@
 
    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, 675 Mass Ave, Cambridge, MA 02139, USA.  */
+   the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
 /*
  * BUGS, GRIPES, APOLOGIA etc.
@@ -136,26 +136,39 @@
 
 #define error	as_fatal
 
-#define DELETED     ((PTR)1)	/* guarenteed invalid address */
-#define START_POWER    (11)	/* power of two: size of new hash table */
+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)
 
-/* Number of slots in hash table.  The wall does not count here.
-   We expect this is always a power of 2.  */
-#define STAT_SIZE      (0)
-#define STAT_ACCESS    (1)	/* number of hash_ask()s */
+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 */
-/* Number of collisions (total).  This may exceed STAT_ACCESS if we
-   have lots of collisions/access.  */
-#define STAT_COLLIDE   (3)
-#define STAT_USED      (5)	/* slots used right now */
-#define STATLENGTH     (6)	/* size of statistics block */
-#if STATLENGTH != HASH_STATLENGTH
-Panic! Please make #include "stat.h" agree with previous definitions!
-#endif
+
+/* 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) / 4)
 
 /* #define SUSPECT to do runtime checks */
 /* #define TEST to be a test jig for hash...() */
@@ -170,6 +183,17 @@ Panic! Please make #include "stat.h" agree with previous definitions!
 #define START_FULL  (4)
 #endif
 
+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 */
+};
+
 /*------------------ plan ---------------------------------- i = internal
 
   struct hash_control * c;
@@ -267,7 +291,7 @@ hash_new ()
   retval->hash_where = room;
   retval->hash_wall =
     wall = room + (1 << START_POWER);
-  retval->hash_full = (1 << START_POWER) / 2;
+  retval->hash_full = FULL_VALUE (1 << START_POWER);
   for (entry = room; entry <= wall; entry++)
     entry->hash_string = NULL;
   return retval;
@@ -291,6 +315,7 @@ hash_die (handle)
   free ((char *) handle);
 }
 
+#ifdef TEST
 /*
  *           h a s h _ s a y ( )
  *
@@ -304,7 +329,7 @@ hash_die (handle)
  * Then contents of hash_stat[] are read out (in ascending order)
  * until your buffer or hash_stat[] is exausted.
  */
-void
+static void
 hash_say (handle, buffer, bufsiz)
      struct hash_control *handle;
      int buffer[ /*bufsiz*/ ];
@@ -324,6 +349,7 @@ hash_say (handle, buffer, bufsiz)
 	}
     }
 }
+#endif
 
 /*
  *           h a s h _ d e l e t e ( )
@@ -438,7 +464,7 @@ hash_insert (handle, string, value)
  *
  * 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) relpaced.
+ * (its value is) replaced.
  * An error message string is returned, 0 means OK.
  *
  * WARNING: this may decide to grow the hashed symbol table.
@@ -515,69 +541,48 @@ hash_grow (handle)		/* make a hash table grow */
    * attempt to get enough room for a hash table twice as big
    */
   temp = handle->hash_stat[STAT_SIZE];
-  if ((newwhere = ((struct hash_entry *)
-		   xmalloc ((unsigned long) ((temp + temp + 1)
-					     * sizeof (struct hash_entry)))))
-      != NULL)
-    /* +1 for wall slot */
-    {
-      retval = 0;		/* assume success until proven otherwise */
-      /*
-       * have enough room: now we do all the work.
-       * double the size of everything in handle,
-       * note: hash_mask frob works for 1's & for 2's complement machines
-       */
-      handle->hash_mask = handle->hash_mask + handle->hash_mask + 1;
-      handle->hash_stat[STAT_SIZE] <<= 1;
-      newsize = handle->hash_stat[STAT_SIZE];
-      handle->hash_where = newwhere;
-      handle->hash_full <<= 1;
-      handle->hash_sizelog += 1;
-      handle->hash_stat[STAT_USED] = 0;
-      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;	/* inserts will bump it up to correct */
-      for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++)
-	if (((string = oldtrack->hash_string) != NULL) && string != DELETED)
-	  if ((retval = hash_jam (handle, string, oldtrack->hash_value)))
-	    break;
+  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 (!retval && handle->hash_stat[STAT_USED] != oldused)
-	{
-	  retval = "hash_used";
-	}
+  if (handle->hash_stat[STAT_USED] != oldused)
+    return "hash_used";
 #endif
-      if (!retval)
-	{
-	  /*
-	   * we have a completely faked up control block.
-	   * return the old hash table.
-	   */
-	  free ((char *) oldwhere);
-	  /*
-	   * Here with success. retval is already 0.
-	   */
-	}
-    }
-  else
-    {
-      retval = "no room";
-    }
-  return retval;
+
+  /* We have a completely faked up control block.
+     Return the old hash table.  */
+  free ((char *) oldwhere);
+
+  return 0;
 }
 
+#ifdef TEST
 /*
  *          h a s h _ a p p l y ( )
  *
@@ -606,28 +611,20 @@ hash_grow (handle)		/* make a hash table grow */
  * 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.
- * To be safe, please make your functions of type char *. If you always
- * return NULL, then the scan will complete, visiting every symbol in
- * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet!
- * Caveat Actor!
  *
  * The function you supply should be of the form:
- *      char * myfunct(string,value)
+ *      void myfunct(string,value)
  *              char * string;        |* the symbol's name *|
  *              char * value;         |* the symbol's value *|
  *      {
  *        |* ... *|
- *        return(NULL);
  *      }
  *
- * The returned value of hash_apply() is (char*)NULL. In future it may return
- * other values. NULL means "completed scan OK". Other values have no meaning
- * yet. (The function has no graceful failures.)
  */
-char *
+void
 hash_apply (handle, function)
      struct hash_control *handle;
-     char *(*function) ();
+     void (*function) ();
 {
   struct hash_entry *entry;
   struct hash_entry *wall;
@@ -640,8 +637,8 @@ hash_apply (handle, function)
 	  (*function) (entry->hash_string, entry->hash_value);
 	}
     }
-  return (NULL);
 }
+#endif
 
 /*
  *          h a s h _ f i n d ( )
@@ -673,27 +670,40 @@ hash_find (handle, string)
  * Internal.
  */
 static struct hash_entry *	/* string slot, may be empty or deleted */
-hash_ask (handle, string, access)
+hash_ask (handle, string, access_type)
      struct hash_control *handle;
      const char *string;
-     int access;		/* access type */
+     int access_type;
 {
   const char *s;
   struct hash_entry *slot;
   int collision;	/* count collisions */
+  int strcmps;
+  int hcode;
 
   /* start looking here */
-  slot = handle->hash_where + hash_code (handle, string);
+  hcode = hash_code (handle, string);
+  slot = handle->hash_where + (hcode & handle->hash_mask);
 
-  handle->hash_stat[STAT_ACCESS + access] += 1;
-  collision = 0;
+  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 || !strcmp (string, s))
-	hash_found = TRUE;
-      if (hash_found)
-	break;
+      if (string == s)
+	{
+	  hash_found = TRUE;
+	  break;
+	}
+      if (slot->h == hcode)
+	{
+	  if (!strcmp (string, s))
+	    {
+	      hash_found = TRUE;
+	      break;
+	    }
+	  strcmps++;
+	}
       collision++;
       slot++;
     }
@@ -710,8 +720,20 @@ hash_ask (handle, string, access)
       slot = handle->hash_where;/* now look again */
       while (((s = slot->hash_string) != NULL) && s != DELETED)
 	{
-	  if (string == s || !strcmp (string, s))
-	    hash_found = TRUE;
+	  if (string == s)
+	    {
+	      hash_found = TRUE;
+	      break;
+	    }
+	  if (slot->h == hcode)
+	    {
+	      if (!strcmp (string, s))
+		{
+		  hash_found = TRUE;
+		  break;
+		}
+	      strcmps++;
+	    }
 	  collision++;
 	  slot++;
 	}
@@ -723,8 +745,11 @@ hash_ask (handle, string, access)
        *       DELETED:dig here                                   slot
        */
     }
-  handle->hash_stat[STAT_COLLIDE + access] += collision;
-  return (slot);		/* also return hash_found */
+  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 */
 }
 
 /*
@@ -752,7 +777,7 @@ hash_code (handle, string)
       h += c;
       h = (h << 3) + (h >> n) + c;
     }
-  return (h & handle->hash_mask);
+  return h;
 #else
   /* from bfd */
   unsigned long h = 0;
@@ -767,10 +792,41 @@ hash_code (handle, string)
     }
   h += len + (len << 17);
   h ^= h >> 2;
-  return h & handle->hash_mask;
+  return h;
 #endif
 }
 
+void
+hash_print_statistics (file, name, h)
+     FILE *file;
+     const char *name;
+     struct hash_control *h;
+{
+  unsigned long sz, used, pct;
+
+  if (h == 0)
+    return;
+
+  sz = h->hash_stat[STAT_SIZE];
+  used = h->hash_stat[STAT_USED];
+  pct = (used * 100 + sz / 2) / sz;
+
+  fprintf (file, "%s hash statistics:\n\t%d/%d slots used (%d%%)\n",
+	   name, used, sz, pct);
+
+#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])
+
+  P ("accesses:", STAT_ACCESS);
+  P ("collisions:", STAT_COLLIDE);
+  P ("string compares:", STAT_STRCMP);
+
+#undef P
+}
+
 /*
  * Here is a test program to exercise above.
  */
@@ -796,8 +852,8 @@ int number;			/* number 0:TABLES-1 of current hashed */
 
 main ()
 {
-  char (*applicatee ());
-  char *destroy ();
+  void applicatee ();
+  void destroy ();
   char *what ();
   int *ip;
 
@@ -912,24 +968,22 @@ what (description)
   return (retval);
 }
 
-char *
+void
 destroy (string, value)
      char *string;
      char *value;
 {
   free (string);
   free (value);
-  return (NULL);
 }
 
 
-char *
+void
 applicatee (string, value)
      char *string;
      char *value;
 {
   printf ("%.20s-%.20s\n", string, value);
-  return (NULL);
 }
 
 whattable ()			/* determine number: what hash table to use */