From 5ca0f83d750615748e51f2f055a609009896c315 Mon Sep 17 00:00:00 2001 From: DJ Delorie 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 1428d4d36af..2bb71c64ba7 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,8 @@ +2000-11-29 Mark Mitchell + + * hashtab.c (higher_prime_number): Use a table, rather than a + seive, to find the next prime. + 2000-11-29 Zack Weinberg * aclocal.m4 (LIB_AC_PROG_CC): Moved here from configure.in. diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index 9778998b240..122ed43e128 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.30.2