Re: [patch] expanding tables for bfd/hash.c

[Alan Modra <amodra at bigpond dot net dot au>]

On Tue, May 02, 2006 at 09:16:33PM -0400, DJ Delorie wrote:
> 
> > Are you offering to fix all the testsuite?
> 
> Yes, let me know which break and I'll rearrange the expected results
> to match the new ordering.

A quicker alternative might be to leave the default unchanged.  There
are a lot of tests that depend on symbol table order, and some only run
natively.

A simple change that accomplishes this is to depopulate primes[], which
might be a good idea in itself.  What is the point in growing a table
from 7 to 13?  You'd probably be better off growing to something quite a
lot larger, at least when the size is relatively small.

How about this?

	* hash.c (DEFAULT_SIZE): Revert last change.
	(higher_prime_number): Correct test for no larger prime.  Don't
	abort on error, instead return 0.  Depopulate primes[].
	(bfd_hash_lookup): If we overflow size, refuse to grow table.

Index: bfd/hash.c
===================================================================
RCS file: /cvs/src/src/bfd/hash.c,v
retrieving revision 1.21
diff -u -p -r1.21 hash.c
--- bfd/hash.c	1 May 2006 19:36:27 -0000	1.21
+++ bfd/hash.c	3 May 2006 03:43:05 -0000
@@ -298,10 +298,11 @@ SUBSUBSECTION
 */
 
 /* The default number of entries to use when creating a hash table.  */
-#define DEFAULT_SIZE (4093)
+#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.  */
+   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)
@@ -309,20 +310,8 @@ 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) 7,
-    (unsigned long) 13,
-    (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,
@@ -343,7 +332,7 @@ higher_prime_number (unsigned long n)
   };
 
   const unsigned long *low = &primes[0];
-  const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
+  const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
 
   while (low != high)
     {
@@ -354,12 +343,8 @@ higher_prime_number (unsigned long n)
 	high = mid;
     }
 
-  /* If we've run out of primes, abort.  */
-  if (n > *low)
-    {
-      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
-      abort ();
-    }
+  if (n >= *low)
+    return 0;
 
   return *low;
 }
@@ -486,12 +471,19 @@ bfd_hash_lookup (struct bfd_hash_table *
 
   if (table->count > table->size * 3 / 4)
     {
-      int newsize = higher_prime_number (table->size);
+      unsigned long newsize = higher_prime_number (table->size);
       struct bfd_hash_entry **newtable;
       unsigned int hi;
-      unsigned int alloc;
+      unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
 
-      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)
+	{
+	  /* Lie.  Stops us trying to grow again for a while.  */
+	  table->count = 0;
+	  return hashp;
+	}
 
       newtable = ((struct bfd_hash_entry **)
 		  objalloc_alloc ((struct objalloc *) table->memory, alloc));

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre