gas: avoid spurious failures in non-ELF targets in the SPARC testsuite.

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

diff --git a/bfd/hash.c b/bfd/hash.c
index 1157980a8f8aa06f591cabed7dc270a47574c736..ff026756080aa1db2c394f8ea4f56250f76bc831 100644 (file)
--- a/bfd/hash.c
+++ b/bfd/hash.c
@@ -1,13 +1,12 @@
 /* hash.c -- hash table routines for BFD
 /* hash.c -- hash table routines for BFD

-   Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
-   2006 Free Software Foundation, Inc.
+   Copyright (C) 1993-2016 Free Software Foundation, Inc.

    Written by Steve Chamberlain <sac@cygnus.com>
 
    This file is part of BFD, the Binary File Descriptor library.
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    Written by Steve Chamberlain <sac@cygnus.com>
 
    This file is part of BFD, the Binary File Descriptor library.
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by

-   the Free Software Foundation; either version 2 of the License, or
+   the Free Software Foundation; either version 3 of the License, or

    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,


@@ -17,10 +16,11 @@
 
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
 
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software

-   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.  */
+   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+   MA 02110-1301, USA.  */

 
 

-#include "bfd.h"

 #include "sysdep.h"
 #include "sysdep.h"

+#include "bfd.h"

 #include "libbfd.h"
 #include "objalloc.h"
 #include "libiberty.h"
 #include "libbfd.h"
 #include "objalloc.h"
 #include "libiberty.h"


@@ -309,28 +309,37 @@ higher_prime_number (unsigned long n)
 {
   /* These are primes that are near, but slightly smaller than, a
      power of two.  */
 {
   /* These are primes that are near, but slightly smaller than, a
      power of two.  */

-  static const unsigned long primes[] = {
-    (unsigned long) 127,
-    (unsigned long) 2039,
-    (unsigned long) 32749,
-    (unsigned long) 65521,
-    (unsigned long) 131071,
-    (unsigned long) 262139,
-    (unsigned long) 524287,
-    (unsigned long) 1048573,
-    (unsigned long) 2097143,
-    (unsigned long) 4194301,
-    (unsigned long) 8388593,
-    (unsigned long) 16777213,
-    (unsigned long) 33554393,
-    (unsigned long) 67108859,
-    (unsigned long) 134217689,
-    (unsigned long) 268435399,
-    (unsigned long) 536870909,
-    (unsigned long) 1073741789,
-    (unsigned long) 2147483647,
+  static const unsigned long primes[] =
+    {
+      (unsigned long) 31,
+      (unsigned long) 61,
+      (unsigned long) 127,
+      (unsigned long) 251,
+      (unsigned long) 509,
+      (unsigned long) 1021,
+      (unsigned long) 2039,
+      (unsigned long) 4093,
+      (unsigned long) 8191,
+      (unsigned long) 16381,
+      (unsigned long) 32749,
+      (unsigned long) 65521,
+      (unsigned long) 131071,
+      (unsigned long) 262139,
+      (unsigned long) 524287,
+      (unsigned long) 1048573,
+      (unsigned long) 2097143,
+      (unsigned long) 4194301,
+      (unsigned long) 8388593,
+      (unsigned long) 16777213,
+      (unsigned long) 33554393,
+      (unsigned long) 67108859,
+      (unsigned long) 134217689,
+      (unsigned long) 268435399,
+      (unsigned long) 536870909,
+      (unsigned long) 1073741789,
+      (unsigned long) 2147483647,

                                        /* 4294967291L */
                                        /* 4294967291L */

-    ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
+      ((unsigned long) 2147483647) + ((unsigned long) 2147483644),

   };
 
   const unsigned long *low = &primes[0];
   };
 
   const unsigned long *low = &primes[0];


@@ -351,7 +360,7 @@ higher_prime_number (unsigned long n)
   return *low;
 }
 
   return *low;
 }
 

-static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
+static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE;

 
 /* Create a new hash table, given a number of entries.  */
 
 
 /* Create a new hash table, given a number of entries.  */
 


@@ -363,9 +372,15 @@ bfd_hash_table_init_n (struct bfd_hash_table *table,
                       unsigned int entsize,
                       unsigned int size)
 {
                       unsigned int entsize,
                       unsigned int size)
 {

-  unsigned int alloc;
+  unsigned long alloc;

 
 

-  alloc = size * sizeof (struct bfd_hash_entry *);
+  alloc = size;
+  alloc *= sizeof (struct bfd_hash_entry *);
+  if (alloc / sizeof (struct bfd_hash_entry *) != size)
+    {
+      bfd_set_error (bfd_error_no_memory);
+      return FALSE;
+    }

 
   table->memory = (void *) objalloc_create ();
   if (table->memory == NULL)
 
   table->memory = (void *) objalloc_create ();
   if (table->memory == NULL)


@@ -373,9 +388,11 @@ bfd_hash_table_init_n (struct bfd_hash_table *table,
       bfd_set_error (bfd_error_no_memory);
       return FALSE;
     }
       bfd_set_error (bfd_error_no_memory);
       return FALSE;
     }

-  table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
+  table->table = (struct bfd_hash_entry **)
+      objalloc_alloc ((struct objalloc *) table->memory, alloc);

   if (table->table == NULL)
     {
   if (table->table == NULL)
     {

+      bfd_hash_table_free (table);

       bfd_set_error (bfd_error_no_memory);
       return FALSE;
     }
       bfd_set_error (bfd_error_no_memory);
       return FALSE;
     }


@@ -406,24 +423,17 @@ bfd_hash_table_init (struct bfd_hash_table *table,
 void
 bfd_hash_table_free (struct bfd_hash_table *table)
 {
 void
 bfd_hash_table_free (struct bfd_hash_table *table)
 {

-  objalloc_free (table->memory);
+  objalloc_free ((struct objalloc *) table->memory);

   table->memory = NULL;
 }
 
   table->memory = NULL;
 }
 

-/* Look up a string in a hash table.  */
-
-struct bfd_hash_entry *
-bfd_hash_lookup (struct bfd_hash_table *table,
-                const char *string,
-                bfd_boolean create,
-                bfd_boolean copy)
+static inline unsigned long
+bfd_hash_hash (const char *string, unsigned int *lenp)

 {
   const unsigned char *s;
   unsigned long hash;
 {
   const unsigned char *s;
   unsigned long hash;

-  unsigned int c;
-  struct bfd_hash_entry *hashp;

   unsigned int len;
   unsigned int len;

-  unsigned int index;
+  unsigned int c;

 
   hash = 0;
   len = 0;
 
   hash = 0;
   len = 0;


@@ -436,9 +446,27 @@ bfd_hash_lookup (struct bfd_hash_table *table,
   len = (s - (const unsigned char *) string) - 1;
   hash += len + (len << 17);
   hash ^= hash >> 2;
   len = (s - (const unsigned char *) string) - 1;
   hash += len + (len << 17);
   hash ^= hash >> 2;

+  if (lenp != NULL)
+    *lenp = len;
+  return hash;
+}
+
+/* Look up a string in a hash table.  */
+
+struct bfd_hash_entry *
+bfd_hash_lookup (struct bfd_hash_table *table,
+                const char *string,
+                bfd_boolean create,
+                bfd_boolean copy)
+{
+  unsigned long hash;
+  struct bfd_hash_entry *hashp;
+  unsigned int len;
+  unsigned int _index;

 
 

-  index = hash % table->size;
-  for (hashp = table->table[index];
+  hash = bfd_hash_hash (string, &len);
+  _index = hash % table->size;
+  for (hashp = table->table[_index];

        hashp != NULL;
        hashp = hashp->next)
     {
        hashp != NULL;
        hashp = hashp->next)
     {


@@ -450,26 +478,42 @@ bfd_hash_lookup (struct bfd_hash_table *table,
   if (! create)
     return NULL;
 
   if (! create)
     return NULL;
 

-  hashp = (*table->newfunc) (NULL, table, string);
-  if (hashp == NULL)
-    return NULL;

   if (copy)
     {
   if (copy)
     {

-      char *new;
+      char *new_string;

 
 

-      new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
-      if (!new)
+      new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
+                                            len + 1);
+      if (!new_string)

        {
          bfd_set_error (bfd_error_no_memory);
          return NULL;
        }
        {
          bfd_set_error (bfd_error_no_memory);
          return NULL;
        }

-      memcpy (new, string, len + 1);
-      string = new;
+      memcpy (new_string, string, len + 1);
+      string = new_string;

     }
     }

+
+  return bfd_hash_insert (table, string, hash);
+}
+
+/* Insert an entry in a hash table.  */
+
+struct bfd_hash_entry *
+bfd_hash_insert (struct bfd_hash_table *table,
+                const char *string,
+                unsigned long hash)
+{
+  struct bfd_hash_entry *hashp;
+  unsigned int _index;
+
+  hashp = (*table->newfunc) (NULL, table, string);
+  if (hashp == NULL)
+    return NULL;

   hashp->string = string;
   hashp->hash = hash;
   hashp->string = string;
   hashp->hash = hash;

-  hashp->next = table->table[index];
-  table->table[index] = hashp;
+  _index = hash % table->size;
+  hashp->next = table->table[_index];
+  table->table[_index] = hashp;

   table->count++;
 
   if (!table->frozen && table->count > table->size * 3 / 4)
   table->count++;
 
   if (!table->frozen && table->count > table->size * 3 / 4)


@@ -489,22 +533,26 @@ bfd_hash_lookup (struct bfd_hash_table *table,
 
       newtable = ((struct bfd_hash_entry **)
                  objalloc_alloc ((struct objalloc *) table->memory, alloc));
 
       newtable = ((struct bfd_hash_entry **)
                  objalloc_alloc ((struct objalloc *) table->memory, alloc));

-      memset ((PTR) newtable, 0, alloc);
+      if (newtable == NULL)
+       {
+         table->frozen = 1;
+         return hashp;
+       }
+      memset (newtable, 0, alloc);

 
       for (hi = 0; hi < table->size; hi ++)
        while (table->table[hi])
          {
            struct bfd_hash_entry *chain = table->table[hi];
            struct bfd_hash_entry *chain_end = chain;
 
       for (hi = 0; hi < table->size; hi ++)
        while (table->table[hi])
          {
            struct bfd_hash_entry *chain = table->table[hi];
            struct bfd_hash_entry *chain_end = chain;

-           int index;

 
            while (chain_end->next && chain_end->next->hash == chain->hash)
              chain_end = chain_end->next;
 
            table->table[hi] = chain_end->next;
 
            while (chain_end->next && chain_end->next->hash == chain->hash)
              chain_end = chain_end->next;
 
            table->table[hi] = chain_end->next;

-           index = chain->hash % newsize;
-           chain_end->next = newtable[index];
-           newtable[index] = chain;
+           _index = chain->hash % newsize;
+           chain_end->next = newtable[_index];
+           newtable[_index] = chain;

          }
       table->table = newtable;
       table->size = newsize;
          }
       table->table = newtable;
       table->size = newsize;


@@ -513,6 +561,31 @@ bfd_hash_lookup (struct bfd_hash_table *table,
   return hashp;
 }
 
   return hashp;
 }
 

+/* Rename an entry in a hash table.  */
+
+void
+bfd_hash_rename (struct bfd_hash_table *table,
+                const char *string,
+                struct bfd_hash_entry *ent)
+{
+  unsigned int _index;
+  struct bfd_hash_entry **pph;
+
+  _index = ent->hash % table->size;
+  for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
+    if (*pph == ent)
+      break;
+  if (*pph == NULL)
+    abort ();
+
+  *pph = ent->next;
+  ent->string = string;
+  ent->hash = bfd_hash_hash (string, NULL);
+  _index = ent->hash % table->size;
+  ent->next = table->table[_index];
+  table->table[_index] = ent;
+}
+

 /* Replace an entry in a hash table.  */
 
 void
 /* Replace an entry in a hash table.  */
 
 void


@@ -520,11 +593,11 @@ bfd_hash_replace (struct bfd_hash_table *table,
                  struct bfd_hash_entry *old,
                  struct bfd_hash_entry *nw)
 {
                  struct bfd_hash_entry *old,
                  struct bfd_hash_entry *nw)
 {

-  unsigned int index;
+  unsigned int _index;

   struct bfd_hash_entry **pph;
 
   struct bfd_hash_entry **pph;
 

-  index = old->hash % table->size;
-  for (pph = &table->table[index];
+  _index = old->hash % table->size;
+  for (pph = &table->table[_index];

        (*pph) != NULL;
        pph = &(*pph)->next)
     {
        (*pph) != NULL;
        pph = &(*pph)->next)
     {


@@ -560,7 +633,8 @@ bfd_hash_newfunc (struct bfd_hash_entry *entry,
                  const char *string ATTRIBUTE_UNUSED)
 {
   if (entry == NULL)
                  const char *string ATTRIBUTE_UNUSED)
 {
   if (entry == NULL)

-    entry = bfd_hash_allocate (table, sizeof (* entry));
+    entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
+                                                         sizeof (* entry));

   return entry;
 }
 
   return entry;
 }
 


@@ -586,22 +660,23 @@ bfd_hash_traverse (struct bfd_hash_table *table,
   table->frozen = 0;
 }
 \f
   table->frozen = 0;
 }
 \f

-void
-bfd_hash_set_default_size (bfd_size_type hash_size)
+unsigned long
+bfd_hash_set_default_size (unsigned long hash_size)

 {
   /* Extend this prime list if you want more granularity of hash table size.  */
 {
   /* Extend this prime list if you want more granularity of hash table size.  */

-  static const bfd_size_type hash_size_primes[] =
+  static const unsigned long hash_size_primes[] =

     {
     {

-      251, 509, 1021, 2039, 4051, 8599, 16699, 32749
+      31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537

     };
     };

-  size_t index;
+  unsigned int _index;

 
   /* Work out best prime number near the hash_size.  */
 
   /* Work out best prime number near the hash_size.  */

-  for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
-    if (hash_size <= hash_size_primes[index])
+  for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index)
+    if (hash_size <= hash_size_primes[_index])

       break;
 
       break;
 

-  bfd_default_hash_table_size = hash_size_primes[index];
+  bfd_default_hash_table_size = hash_size_primes[_index];
+  return bfd_default_hash_table_size;

 }
 \f
 /* A few different object file formats (a.out, COFF, ELF) use a string
 }
 \f
 /* A few different object file formats (a.out, COFF, ELF) use a string


@@ -655,7 +730,8 @@ strtab_hash_newfunc (struct bfd_hash_entry *entry,
   /* Allocate the structure if it has not already been allocated by a
      subclass.  */
   if (ret == NULL)
   /* Allocate the structure if it has not already been allocated by a
      subclass.  */
   if (ret == NULL)

-    ret = bfd_hash_allocate (table, sizeof (* ret));
+    ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
+                                                          sizeof (* ret));

   if (ret == NULL)
     return NULL;
 
   if (ret == NULL)
     return NULL;
 


@@ -687,7 +763,7 @@ _bfd_stringtab_init (void)
   struct bfd_strtab_hash *table;
   bfd_size_type amt = sizeof (* table);
 
   struct bfd_strtab_hash *table;
   bfd_size_type amt = sizeof (* table);
 

-  table = bfd_malloc (amt);
+  table = (struct bfd_strtab_hash *) bfd_malloc (amt);

   if (table == NULL)
     return NULL;
 
   if (table == NULL)
     return NULL;
 


@@ -732,7 +808,8 @@ _bfd_stringtab_free (struct bfd_strtab_hash *table)
 
 /* Get the index of a string in a strtab, adding it if it is not
    already present.  If HASH is FALSE, we don't really use the hash
 
 /* Get the index of a string in a strtab, adding it if it is not
    already present.  If HASH is FALSE, we don't really use the hash

-   table, and we don't eliminate duplicate strings.  */
+   table, and we don't eliminate duplicate strings.  If COPY is true
+   then store a copy of STR if creating a new entry.  */

 
 bfd_size_type
 _bfd_stringtab_add (struct bfd_strtab_hash *tab,
 
 bfd_size_type
 _bfd_stringtab_add (struct bfd_strtab_hash *tab,


@@ -750,18 +827,21 @@ _bfd_stringtab_add (struct bfd_strtab_hash *tab,
     }
   else
     {
     }
   else
     {

-      entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
+      entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
+                                                              sizeof (* entry));

       if (entry == NULL)
        return (bfd_size_type) -1;
       if (! copy)
        entry->root.string = str;
       else
        {
       if (entry == NULL)
        return (bfd_size_type) -1;
       if (! copy)
        entry->root.string = str;
       else
        {

+         size_t len = strlen (str) + 1;

          char *n;
 
          char *n;
 

-         n = bfd_hash_allocate (&tab->table, strlen (str) + 1);
+         n = (char *) bfd_hash_allocate (&tab->table, len);

          if (n == NULL)
            return (bfd_size_type) -1;
          if (n == NULL)
            return (bfd_size_type) -1;

+          memcpy (n, str, len);

          entry->root.string = n;
        }
       entry->index = (bfd_size_type) -1;
          entry->root.string = n;
        }
       entry->index = (bfd_size_type) -1;