diff options
author | DJ Delorie <dj@redhat.com> | 2000-11-29 19:19:10 +0000 |
---|---|---|
committer | DJ Delorie <dj@redhat.com> | 2000-11-29 19:19:10 +0000 |
commit | 5ca0f83d750615748e51f2f055a609009896c315 (patch) | |
tree | 8682313c765747cb6b544e85d59e693661f19bcc /libiberty | |
parent | 2ea7befd8e4c7e771401059d57452834b6a30da8 (diff) | |
download | fsf-binutils-gdb-5ca0f83d750615748e51f2f055a609009896c315.zip fsf-binutils-gdb-5ca0f83d750615748e51f2f055a609009896c315.tar.gz fsf-binutils-gdb-5ca0f83d750615748e51f2f055a609009896c315.tar.bz2 |
* hashtab.c (higher_prime_number): Use a table, rather than a
seive, to find the next prime.
Diffstat (limited to 'libiberty')
-rw-r--r-- | libiberty/ChangeLog | 5 | ||||
-rw-r--r-- | libiberty/hashtab.c | 78 |
2 files changed, 61 insertions, 22 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index 1428d4d..2bb71c6 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 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. */ |