diff options
Diffstat (limited to 'lib/libc/db/hash/hash_func.c')
| -rw-r--r-- | lib/libc/db/hash/hash_func.c | 106 |
1 files changed, 43 insertions, 63 deletions
diff --git a/lib/libc/db/hash/hash_func.c b/lib/libc/db/hash/hash_func.c index 2ca0a483180f1..db32a75b7286a 100644 --- a/lib/libc/db/hash/hash_func.c +++ b/lib/libc/db/hash/hash_func.c @@ -43,60 +43,57 @@ __FBSDID("$FreeBSD$"); #include "page.h" #include "extern.h" +#ifdef notdef static u_int32_t hash1(const void *, size_t) __unused; static u_int32_t hash2(const void *, size_t) __unused; static u_int32_t hash3(const void *, size_t) __unused; +#endif static u_int32_t hash4(const void *, size_t); -/* Global default hash function */ +/* Default hash function. */ u_int32_t (*__default_hash)(const void *, size_t) = hash4; +#ifdef notdef /* - * HASH FUNCTIONS - * * Assume that we've already split the bucket to which this key hashes, * calculate that bucket, and check that in fact we did already split it. * - * This came from ejb's hsearch. + * EJB's original hsearch hash. */ - #define PRIME1 37 #define PRIME2 1048583 -static u_int32_t -hash1(keyarg, len) - const void *keyarg; - size_t len; +u_int32_t +hash1(const void *key, size_t len) { - const u_char *key; u_int32_t h; + u_int8_t *k; + h = 0; + k = (u_int8_t *)key; /* Convert string to integer */ - for (key = keyarg, h = 0; len--;) - h = h * PRIME1 ^ (*key++ - ' '); + while (len--) + h = h * PRIME1 ^ (*k++ - ' '); h %= PRIME2; return (h); } /* - * Phong's linear congruential hash + * Phong Vo's linear congruential hash */ #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) -static u_int32_t -hash2(keyarg, len) - const void *keyarg; - size_t len; +u_int32_t +hash2(const void *key, size_t len) { - const u_char *e, *key; u_int32_t h; - u_char c; + u_int8_t *e, c, *k; - key = keyarg; - e = key + len; - for (h = 0; key != e;) { - c = *key++; - if (!c && key > e) + k = (u_int8_t *)key; + e = k + len; + for (h = 0; k != e;) { + c = *k++; + if (!c && k > e) break; dcharhash(h, c); } @@ -110,101 +107,84 @@ hash2(keyarg, len) * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If * this routine is heavily used enough, it's worth the ugly coding. * - * OZ's original sdbm hash + * Ozan Yigit's original sdbm hash. */ -static u_int32_t -hash3(keyarg, len) - const void *keyarg; - size_t len; +u_int32_t +hash3(const void *key, size_t len) { - const u_char *key; - size_t loop; - u_int32_t h; + u_int32_t n, loop; + u_int8_t *k; -#define HASHC h = *key++ + 65599 * h +#define HASHC n = *k++ + 65599 * n - h = 0; - key = keyarg; + n = 0; + k = (u_int8_t *)key; if (len > 0) { loop = (len + 8 - 1) >> 3; switch (len & (8 - 1)) { case 0: - do { + do { /* All fall throughs */ HASHC; - /* FALLTHROUGH */ case 7: HASHC; - /* FALLTHROUGH */ case 6: HASHC; - /* FALLTHROUGH */ case 5: HASHC; - /* FALLTHROUGH */ case 4: HASHC; - /* FALLTHROUGH */ case 3: HASHC; - /* FALLTHROUGH */ case 2: HASHC; - /* FALLTHROUGH */ case 1: HASHC; } while (--loop); } + } - return (h); + return (n); } +#endif /* notdef */ -/* Hash function from Chris Torek. */ -static u_int32_t -hash4(keyarg, len) - const void *keyarg; - size_t len; +/* Chris Torek's hash function. */ +u_int32_t +hash4(const void *key, size_t len) { - const u_char *key; - size_t loop; - u_int32_t h; + u_int32_t h, loop; + const u_int8_t *k; -#define HASH4a h = (h << 5) - h + *key++; -#define HASH4b h = (h << 5) + h + *key++; +#define HASH4a h = (h << 5) - h + *k++; +#define HASH4b h = (h << 5) + h + *k++; #define HASH4 HASH4b h = 0; - key = keyarg; + k = key; if (len > 0) { loop = (len + 8 - 1) >> 3; switch (len & (8 - 1)) { case 0: - do { + do { /* All fall throughs */ HASH4; - /* FALLTHROUGH */ case 7: HASH4; - /* FALLTHROUGH */ case 6: HASH4; - /* FALLTHROUGH */ case 5: HASH4; - /* FALLTHROUGH */ case 4: HASH4; - /* FALLTHROUGH */ case 3: HASH4; - /* FALLTHROUGH */ case 2: HASH4; - /* FALLTHROUGH */ case 1: HASH4; } while (--loop); } + } return (h); } |