diff options
author | Mark Mitchell <mark@codesourcery.com> | 2000-11-27 04:23:38 +0000 |
---|---|---|
committer | Mark Mitchell <mmitchel@gcc.gnu.org> | 2000-11-27 04:23:38 +0000 |
commit | a4c9b97e262791f8bfc0e12ad1d564c90d8b966a (patch) | |
tree | fe78cc9d5672a5574eff55bb4c96cf9a55f5eb4c /libiberty/hashtab.c | |
parent | e9608fe6f0bc34b79bb3750e9d22065632cc4b27 (diff) | |
download | gcc-a4c9b97e262791f8bfc0e12ad1d564c90d8b966a.zip gcc-a4c9b97e262791f8bfc0e12ad1d564c90d8b966a.tar.gz gcc-a4c9b97e262791f8bfc0e12ad1d564c90d8b966a.tar.bz2 |
hashtab.c (higher_prime_number): Use a table, rather than a seive, to find the next prime.
* hashtab.c (higher_prime_number): Use a table, rather than a
seive, to find the next prime.
From-SVN: r37775
Diffstat (limited to 'libiberty/hashtab.c')
-rw-r--r-- | libiberty/hashtab.c | 78 |
1 files changed, 56 insertions, 22 deletions
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index 9778998..122ed43 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. */ |