diff options
Diffstat (limited to 'contrib/binutils/libiberty/hashtab.c')
| -rw-r--r-- | contrib/binutils/libiberty/hashtab.c | 112 |
1 files changed, 76 insertions, 36 deletions
diff --git a/contrib/binutils/libiberty/hashtab.c b/contrib/binutils/libiberty/hashtab.c index 122ed43..36ad6e4 100644 --- a/contrib/binutils/libiberty/hashtab.c +++ b/contrib/binutils/libiberty/hashtab.c @@ -1,5 +1,5 @@ /* An expandable hash tables datatype. - Copyright (C) 1999, 2000 Free Software Foundation, Inc. + Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc. Contributed by Vladimir Makarov (vmakarov@cygnus.com). This file is part of the libiberty library. @@ -80,46 +80,47 @@ higher_prime_number (n) { /* 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 + static const unsigned long primes[] = { + (unsigned long) 2, + (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, + (unsigned long) 1048573, + (unsigned long) 2097143, + (unsigned long) 4194301, + (unsigned long) 8388593, + (unsigned long) 16777213, + (unsigned long) 33554393, + (unsigned long) 67108859, + (unsigned long) 134217689, + (unsigned long) 268435399, + (unsigned long) 536870909, + (unsigned long) 1073741789, + (unsigned long) 2147483647, + /* 4294967291L */ + ((unsigned long) 2147483647) + ((unsigned long) 2147483644), }; - unsigned long* low = &primes[0]; - unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])]; + const unsigned long *low = &primes[0]; + const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])]; while (low != high) { - unsigned long* mid = low + (high - low) / 2; + const unsigned long *mid = low + (high - low) / 2; if (n > *mid) low = mid + 1; else @@ -560,3 +561,42 @@ htab_collisions (htab) return (double) htab->collisions / (double) htab->searches; } + +/* Hash P as a null-terminated string. + + Copied from gcc/hashtable.c. Zack had the following to say with respect + to applicability, though note that unlike hashtable.c, this hash table + implementation re-hashes rather than chain buckets. + + http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html + From: Zack Weinberg <zackw@panix.com> + Date: Fri, 17 Aug 2001 02:15:56 -0400 + + I got it by extracting all the identifiers from all the source code + I had lying around in mid-1999, and testing many recurrences of + the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either + prime numbers or the appropriate identity. This was the best one. + I don't remember exactly what constituted "best", except I was + looking at bucket-length distributions mostly. + + So it should be very good at hashing identifiers, but might not be + as good at arbitrary strings. + + I'll add that it thoroughly trounces the hash functions recommended + for this use at http://burtleburtle.net/bob/hash/index.html, both + on speed and bucket distribution. I haven't tried it against the + function they just started using for Perl's hashes. */ + +hashval_t +htab_hash_string (p) + const PTR p; +{ + const unsigned char *str = (const unsigned char *) p; + hashval_t r = 0; + unsigned char c; + + while ((c = *str++) != 0) + r = r * 67 + c - 113; + + return r; +} |
