From 5ca0f83d750615748e51f2f055a609009896c315 Mon Sep 17 00:00:00 2001
From: DJ Delorie <dj@redhat.com>
Date: Wed, 29 Nov 2000 19:19:10 +0000
Subject: [PATCH] * hashtab.c (higher_prime_number): Use a table, rather than a
 seive, to find the next prime.

---
 libiberty/ChangeLog |  5 +++
 libiberty/hashtab.c | 78 ++++++++++++++++++++++++++++++++-------------
 2 files changed, 61 insertions(+), 22 deletions(-)

diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index 1428d4d36a..2bb71c64ba 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,8 @@
+2000-11-29  Mark Mitchell  <mark@codesourcery.com>
+
+	* hashtab.c (higher_prime_number): Use a table, rather than a
+	seive, to find the next prime.
+	
 2000-11-29  Zack Weinberg  <zack@wolery.stanford.edu>
 
 	* aclocal.m4 (LIB_AC_PROG_CC): Moved here from configure.in.
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 9778998b24..122ed43e12 100644
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -71,35 +71,69 @@ static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
 htab_hash htab_hash_pointer = hash_pointer;
 htab_eq htab_eq_pointer = eq_pointer;
 
-/* The following function returns the nearest prime number which is
-   greater than a given source number, N. */
+/* The following function returns a nearest prime number which is
+   greater than N, and near a power of two. */
 
 static unsigned long
 higher_prime_number (n)
      unsigned long n;
 {
-  unsigned long i;
-
-  /* Ensure we have a larger number and then force to odd.  */
-  n++;  
-  n |= 0x01; 
-
-  /* All odd numbers < 9 are prime.  */
-  if (n < 9)
-    return n;
-
-  /* Otherwise find the next prime using a sieve.  */
-
- next:
+  /* These are primes that are near, but slightly smaller than, a
+     power of two.  */
+  static unsigned long primes[] = {
+    2,
+    7,
+    13,
+    31,
+    61,
+    127,
+    251,
+    509,
+    1021,
+    2039,
+    4093,
+    8191,
+    16381,
+    32749,
+    65521,
+    131071,
+    262139,
+    524287,
+    1048573,
+    2097143,
+    4194301,
+    8388593,
+    16777213,
+    33554393,
+    67108859,
+    134217689,
+    268435399,
+    536870909,
+    1073741789,
+    2147483647,
+    4294967291
+  };
+
+  unsigned long* low = &primes[0];
+  unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])];
+
+  while (low != high)
+    {
+      unsigned long* mid = low + (high - low) / 2;
+      if (n > *mid)
+	low = mid + 1;
+      else
+	high = mid;
+    }
 
-  for (i = 3; i * i <= n; i += 2)
-    if (n % i == 0)
-      {
-	 n += 2;
-	 goto next;
-       }
+  /* If we've run out of primes, abort.  */
+  if (n > *low)
+    {
+      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
+      abort ();
+    }
 
-  return n;
+  return *low;
 }
 
 /* Returns a hash code for P.  */
-- 
2.34.1