bfd/

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

diff --git a/bfd/hash.c b/bfd/hash.c
index e53eda1b901cb929ff6613d5cf6548a75ba496a6..14fc40301508728a4a72498e57b5b895d28bf152 100644 (file)
--- a/bfd/hash.c
+++ b/bfd/hash.c
@@ -1,13 +1,13 @@
 /* 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
-   Free Software Foundation, Inc.
+   Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
+   2006, 2007 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 +17,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"


@@ -299,6 +300,58 @@ SUBSUBSECTION
 
 /* The default number of entries to use when creating a hash table.  */
 #define DEFAULT_SIZE 4051
 
 /* The default number of entries to use when creating a hash table.  */
 #define DEFAULT_SIZE 4051

+
+/* The following function returns a nearest prime number which is
+   greater than N, and near a power of two.  Copied from libiberty.
+   Returns zero for ridiculously large N to signify an error.  */
+
+static unsigned long
+higher_prime_number (unsigned long n)
+{
+  /* 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,
+                                       /* 4294967291L */
+    ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
+  };
+
+  const unsigned long *low = &primes[0];
+  const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
+
+  while (low != high)
+    {
+      const unsigned long *mid = low + (high - low) / 2;
+      if (n >= *mid)
+       low = mid + 1;
+      else
+       high = mid;
+    }
+
+  if (n >= *low)
+    return 0;
+
+  return *low;
+}
+

 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
 
 /* Create a new hash table, given a number of entries.  */
 static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
 
 /* Create a new hash table, given a number of entries.  */


@@ -308,6 +361,7 @@ bfd_hash_table_init_n (struct bfd_hash_table *table,
                       struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
                                                          struct bfd_hash_table *,
                                                          const char *),
                       struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
                                                          struct bfd_hash_table *,
                                                          const char *),

+                      unsigned int entsize,

                       unsigned int size)
 {
   unsigned int alloc;
                       unsigned int size)
 {
   unsigned int alloc;


@@ -328,6 +382,9 @@ bfd_hash_table_init_n (struct bfd_hash_table *table,
     }
   memset ((void *) table->table, 0, alloc);
   table->size = size;
     }
   memset ((void *) table->table, 0, alloc);
   table->size = size;

+  table->entsize = entsize;
+  table->count = 0;
+  table->frozen = 0;

   table->newfunc = newfunc;
   return TRUE;
 }
   table->newfunc = newfunc;
   return TRUE;
 }


@@ -338,9 +395,11 @@ bfd_boolean
 bfd_hash_table_init (struct bfd_hash_table *table,
                     struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
                                                        struct bfd_hash_table *,
 bfd_hash_table_init (struct bfd_hash_table *table,
                     struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
                                                        struct bfd_hash_table *,

-                                                       const char *))
+                                                       const char *),
+                    unsigned int entsize)

 {
 {

-  return bfd_hash_table_init_n (table, newfunc, bfd_default_hash_table_size);
+  return bfd_hash_table_init_n (table, newfunc, entsize,
+                               bfd_default_hash_table_size);

 }
 
 /* Free a hash table.  */
 }
 
 /* Free a hash table.  */


@@ -392,9 +451,6 @@ 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)
     {
       char *new;
   if (copy)
     {
       char *new;


@@ -408,10 +464,71 @@ bfd_hash_lookup (struct bfd_hash_table *table,
       memcpy (new, string, len + 1);
       string = new;
     }
       memcpy (new, string, len + 1);
       string = new;
     }

+
+  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;

+  index = hash % table->size;

   hashp->next = table->table[index];
   table->table[index] = hashp;
   hashp->next = table->table[index];
   table->table[index] = hashp;

+  table->count++;
+
+  if (!table->frozen && table->count > table->size * 3 / 4)
+    {
+      unsigned long newsize = higher_prime_number (table->size);
+      struct bfd_hash_entry **newtable;
+      unsigned int hi;
+      unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
+
+      /* If we can't find a higher prime, or we can't possibly alloc
+        that much memory, don't try to grow the table.  */
+      if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
+       {
+         table->frozen = 1;
+         return hashp;
+       }
+
+      newtable = ((struct bfd_hash_entry **)
+                 objalloc_alloc ((struct objalloc *) table->memory, alloc));
+      if (newtable == NULL)
+       {
+         table->frozen = 1;
+         return hashp;
+       }
+      memset ((PTR) 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;
+
+           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;
+         }
+      table->table = newtable;
+      table->size = newsize;
+    }

 
   return hashp;
 }
 
   return hashp;
 }


@@ -476,14 +593,17 @@ bfd_hash_traverse (struct bfd_hash_table *table,
 {
   unsigned int i;
 
 {
   unsigned int i;
 

+  table->frozen = 1;

   for (i = 0; i < table->size; i++)
     {
       struct bfd_hash_entry *p;
 
       for (p = table->table[i]; p != NULL; p = p->next)
        if (! (*func) (p, info))
   for (i = 0; i < table->size; i++)
     {
       struct bfd_hash_entry *p;
 
       for (p = table->table[i]; p != NULL; p = p->next)
        if (! (*func) (p, info))

-         return;
+         goto out;

     }
     }

+ out:
+  table->frozen = 0;

 }
 \f
 void
 }
 \f
 void


@@ -591,7 +711,8 @@ _bfd_stringtab_init (void)
   if (table == NULL)
     return NULL;
 
   if (table == NULL)
     return NULL;
 

-  if (! bfd_hash_table_init (& table->table, strtab_hash_newfunc))
+  if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
+                           sizeof (struct strtab_hash_entry)))

     {
       free (table);
       return NULL;
     {
       free (table);
       return NULL;