* config/tc-ppc.c (md_section_align): Don't round up address for ELF.

[deliverable/binutils-gdb.git] / gas / hash.c

diff --git a/gas/hash.c b/gas/hash.c
index df9101db6bec8cf83741cc06bd2ffb1cccf12c1d..6977ceeb53284c98e986d653f5152be82577547f 100644 (file)
--- a/gas/hash.c
+++ b/gas/hash.c
@@ -1,6 +1,6 @@
 /* hash.c -- gas hash table code
    Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
 /* hash.c -- gas hash table code
    Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,

-   2000, 2001, 2002
+   2000, 2001, 2002, 2003, 2005

    Free Software Foundation, Inc.
 
    This file is part of GAS, the GNU Assembler.
    Free Software Foundation, Inc.
 
    This file is part of GAS, the GNU Assembler.


@@ -17,13 +17,13 @@
 
    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
 
    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.  */
+   Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
+   02110-1301, 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
 
 /* 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
+   assembler.  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
    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


@@ -33,10 +33,6 @@
 #include "safe-ctype.h"
 #include "obstack.h"
 
 #include "safe-ctype.h"
 #include "obstack.h"
 

-/* The default number of entries to use when creating a hash table.  */
-
-#define DEFAULT_SIZE (4051)
-

 /* An entry in a hash table.  */
 
 struct hash_entry {
 /* An entry in a hash table.  */
 
 struct hash_entry {


@@ -72,21 +68,55 @@ struct hash_control {
 #endif /* HASH_STATISTICS */
 };
 
 #endif /* HASH_STATISTICS */
 };
 

+/* The default number of entries to use when creating a hash table.
+   Note this value can be reduced to 4051 by using the command line
+   switch --reduce-memory-overheads, or set to other values by using
+   the --hash-size=<NUMBER> switch.  */
+
+static unsigned long gas_hash_table_size = 65537;
+
+void
+set_gas_hash_table_size (unsigned long size)
+{
+  gas_hash_table_size = size;
+}
+
+/* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size().  */
+static unsigned long
+get_gas_hash_table_size (void)
+{
+  /* Extend this prime list if you want more granularity of hash table size.  */
+  static const unsigned long hash_size_primes[] =
+    {
+      1021, 4051, 8599, 16699, 65537
+    };
+  unsigned int index;
+
+  /* Work out the best prime number near the hash_size.
+     FIXME: This could be a more sophisticated algorithm,
+     but is it really worth implementing it ?   */
+  for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
+    if (gas_hash_table_size <= hash_size_primes[index])
+      break;
+
+  return hash_size_primes[index];
+}
+

 /* Create a hash table.  This return a control block.  */
 
 struct hash_control *
 /* Create a hash table.  This return a control block.  */
 
 struct hash_control *

-hash_new ()
+hash_new (void)

 {
 {

-  unsigned int size;
+  unsigned long size;
+  unsigned long alloc;

   struct hash_control *ret;
   struct hash_control *ret;

-  unsigned int alloc;

 
 

-  size = DEFAULT_SIZE;
+  size = get_gas_hash_table_size ();

 
 

-  ret = (struct hash_control *) xmalloc (sizeof *ret);
+  ret = xmalloc (sizeof *ret);

   obstack_begin (&ret->memory, chunksize);
   alloc = size * sizeof (struct hash_entry *);
   obstack_begin (&ret->memory, chunksize);
   alloc = size * sizeof (struct hash_entry *);

-  ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
+  ret->table = obstack_alloc (&ret->memory, alloc);

   memset (ret->table, 0, alloc);
   ret->size = size;
 
   memset (ret->table, 0, alloc);
   ret->size = size;
 


@@ -105,8 +135,7 @@ hash_new ()
 /* Delete a hash table, freeing all allocated memory.  */
 
 void
 /* Delete a hash table, freeing all allocated memory.  */
 
 void

-hash_die (table)
-     struct hash_control *table;
+hash_die (struct hash_control *table)

 {
   obstack_free (&table->memory, 0);
   free (table);
 {
   obstack_free (&table->memory, 0);
   free (table);


@@ -121,22 +150,13 @@ hash_die (table)
    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.  */
 
    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 *
 static struct hash_entry *

-hash_lookup (table, key, plist, phash)
-     struct hash_control *table;
-     const char *key;
-     struct hash_entry ***plist;
-     unsigned long *phash;
+hash_lookup (struct hash_control *table, const char *key, size_t len,
+            struct hash_entry ***plist, unsigned long *phash)

 {
 {

-  register unsigned long hash;
-  unsigned int len;
-  register const unsigned char *s;
-  register unsigned int c;
+  unsigned long hash;
+  size_t n;
+  unsigned int c;

   unsigned int index;
   struct hash_entry **list;
   struct hash_entry *p;
   unsigned int index;
   struct hash_entry **list;
   struct hash_entry *p;


@@ -147,13 +167,11 @@ hash_lookup (table, key, plist, phash)
 #endif
 
   hash = 0;
 #endif
 
   hash = 0;

-  len = 0;
-  s = (const unsigned char *) key;
-  while ((c = *s++) != '\0')
+  for (n = 0; n < len; n++)

     {
     {

+      c = key[n];

       hash += c + (c << 17);
       hash ^= hash >> 2;
       hash += c + (c << 17);
       hash ^= hash >> 2;

-      ++len;

     }
   hash += len + (len << 17);
   hash ^= hash >> 2;
     }
   hash += len + (len << 17);
   hash ^= hash >> 2;


@@ -180,7 +198,7 @@ hash_lookup (table, key, plist, phash)
          ++table->string_compares;
 #endif
 
          ++table->string_compares;
 #endif
 

-         if (strcmp (p->string, key) == 0)
+         if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')

            {
              if (prev != NULL)
                {
            {
              if (prev != NULL)
                {


@@ -205,16 +223,13 @@ hash_lookup (table, key, plist, phash)
    hash table.  */
 
 const char *
    hash table.  */
 
 const char *

-hash_insert (table, key, value)
-     struct hash_control *table;
-     const char *key;
-     PTR value;
+hash_insert (struct hash_control *table, const char *key, PTR value)

 {
   struct hash_entry *p;
   struct hash_entry **list;
   unsigned long hash;
 
 {
   struct hash_entry *p;
   struct hash_entry **list;
   unsigned long hash;
 

-  p = hash_lookup (table, key, &list, &hash);
+  p = hash_lookup (table, key, strlen (key), &list, &hash);

   if (p != NULL)
     return "exists";
 
   if (p != NULL)
     return "exists";
 


@@ -238,16 +253,13 @@ hash_insert (table, key, value)
    error.  If an entry already exists, its value is replaced.  */
 
 const char *
    error.  If an entry already exists, its value is replaced.  */
 
 const char *

-hash_jam (table, key, value)
-     struct hash_control *table;
-     const char *key;
-     PTR value;
+hash_jam (struct hash_control *table, const char *key, PTR value)

 {
   struct hash_entry *p;
   struct hash_entry **list;
   unsigned long hash;
 
 {
   struct hash_entry *p;
   struct hash_entry **list;
   unsigned long hash;
 

-  p = hash_lookup (table, key, &list, &hash);
+  p = hash_lookup (table, key, strlen (key), &list, &hash);

   if (p != NULL)
     {
 #ifdef HASH_STATISTICS
   if (p != NULL)
     {
 #ifdef HASH_STATISTICS


@@ -279,15 +291,12 @@ hash_jam (table, key, value)
    table, this does nothing and returns NULL.  */
 
 PTR
    table, this does nothing and returns NULL.  */
 
 PTR

-hash_replace (table, key, value)
-     struct hash_control *table;
-     const char *key;
-     PTR value;
+hash_replace (struct hash_control *table, const char *key, PTR value)

 {
   struct hash_entry *p;
   PTR ret;
 
 {
   struct hash_entry *p;
   PTR ret;
 

-  p = hash_lookup (table, key, NULL, NULL);
+  p = hash_lookup (table, key, strlen (key), NULL, NULL);

   if (p == NULL)
     return NULL;
 
   if (p == NULL)
     return NULL;
 


@@ -306,13 +315,26 @@ hash_replace (table, key, value)
    if the entry is not found.  */
 
 PTR
    if the entry is not found.  */
 
 PTR

-hash_find (table, key)
-     struct hash_control *table;
-     const char *key;
+hash_find (struct hash_control *table, const char *key)
+{
+  struct hash_entry *p;
+
+  p = hash_lookup (table, key, strlen (key), NULL, NULL);
+  if (p == NULL)
+    return NULL;
+
+  return p->data;
+}
+
+/* As hash_find, but KEY is of length LEN and is not guaranteed to be
+   NUL-terminated.  */
+
+PTR
+hash_find_n (struct hash_control *table, const char *key, size_t len)

 {
   struct hash_entry *p;
 
 {
   struct hash_entry *p;
 

-  p = hash_lookup (table, key, NULL, NULL);
+  p = hash_lookup (table, key, len, NULL, NULL);

   if (p == NULL)
     return NULL;
 
   if (p == NULL)
     return NULL;
 


@@ -323,14 +345,12 @@ hash_find (table, key)
    for that entry, or NULL if there is no such entry.  */
 
 PTR
    for that entry, or NULL if there is no such entry.  */
 
 PTR

-hash_delete (table, key)
-     struct hash_control *table;
-     const char *key;
+hash_delete (struct hash_control *table, const char *key)

 {
   struct hash_entry *p;
   struct hash_entry **list;
 
 {
   struct hash_entry *p;
   struct hash_entry **list;
 

-  p = hash_lookup (table, key, &list, NULL);
+  p = hash_lookup (table, key, strlen (key), &list, NULL);

   if (p == NULL)
     return NULL;
 
   if (p == NULL)
     return NULL;
 


@@ -354,9 +374,8 @@ hash_delete (table, key)
    hash table.  */
 
 void
    hash table.  */
 
 void

-hash_traverse (table, pfn)
-     struct hash_control *table;
-     void (*pfn) PARAMS ((const char *key, PTR value));
+hash_traverse (struct hash_control *table,
+              void (*pfn) (const char *key, PTR value))

 {
   unsigned int i;
 
 {
   unsigned int i;
 


@@ -373,10 +392,9 @@ hash_traverse (table, pfn)
    name of the hash table, used for printing a header.  */
 
 void
    name of the hash table, used for printing a header.  */
 
 void

-hash_print_statistics (f, name, table)
-     FILE *f ATTRIBUTE_UNUSED;
-     const char *name ATTRIBUTE_UNUSED;
-     struct hash_control *table ATTRIBUTE_UNUSED;
+hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
+                      const char *name ATTRIBUTE_UNUSED,
+                      struct hash_control *table ATTRIBUTE_UNUSED)

 {
 #ifdef HASH_STATISTICS
   unsigned int i;
 {
 #ifdef HASH_STATISTICS
   unsigned int i;


@@ -430,7 +448,7 @@ char answer[100];
 /* We test many hash tables at once.  */
 char *hashtable[TABLES];
 
 /* We test many hash tables at once.  */
 char *hashtable[TABLES];
 

-/* Points to curent hash_control.  */
+/* Points to current hash_control.  */

 char *h;
 char **pp;
 char *p;
 char *h;
 char **pp;
 char *p;