diff options
Diffstat (limited to 'lib/libc')
| -rw-r--r-- | lib/libc/db/hash/extern.h | 5 | ||||
| -rw-r--r-- | lib/libc/db/hash/hash_func.c | 112 | ||||
| -rw-r--r-- | lib/libc/hidden/db.h | 5 | ||||
| -rw-r--r-- | lib/libc/stdlib/hcreate.c | 9 |
4 files changed, 11 insertions, 120 deletions
diff --git a/lib/libc/db/hash/extern.h b/lib/libc/db/hash/extern.h index 3d496169e13..ff9c4d1e0fd 100644 --- a/lib/libc/db/hash/extern.h +++ b/lib/libc/db/hash/extern.h @@ -1,4 +1,4 @@ -/* $OpenBSD: extern.h,v 1.8 2015/08/27 04:37:09 guenther Exp $ */ +/* $OpenBSD: extern.h,v 1.9 2016/05/29 20:47:49 guenther Exp $ */ /*- * Copyright (c) 1991, 1993, 1994 @@ -56,9 +56,6 @@ int __put_page(HTAB *, char *, u_int32_t, int, int); void __reclaim_buf(HTAB *, BUFHEAD *); int __split_page(HTAB *, u_int32_t, u_int32_t); -/* Default hash routine. */ -extern u_int32_t (*__default_hash)(const void *, size_t); - #ifdef HASH_STATISTICS extern int hash_accesses, hash_collisions, hash_expansions, hash_overflows; #endif diff --git a/lib/libc/db/hash/hash_func.c b/lib/libc/db/hash/hash_func.c index aa7f2d920bc..6d96a7341df 100644 --- a/lib/libc/db/hash/hash_func.c +++ b/lib/libc/db/hash/hash_func.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_func.c,v 1.10 2005/08/05 13:03:00 espie Exp $ */ +/* $OpenBSD: hash_func.c,v 1.11 2016/05/29 20:47:49 guenther Exp $ */ /*- * Copyright (c) 1990, 1993 @@ -35,118 +35,10 @@ #include <sys/types.h> #include <db.h> -#include "hash.h" -#include "page.h" -#include "extern.h" - -#ifdef notdef -static u_int32_t hash1(const void *, size_t); -static u_int32_t hash2(const void *, size_t); -static u_int32_t hash3(const void *, size_t); -#endif -static u_int32_t hash4(const void *, size_t); - -/* Default hash function. */ -u_int32_t (*__default_hash)(const void *, size_t) = hash4; - -#ifdef notdef -/* - * 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. - * - * EJB's original hsearch hash. - */ -#define PRIME1 37 -#define PRIME2 1048583 - -u_int32_t -hash1(const void *key, size_t len) -{ - u_int32_t h; - u_int8_t *k; - - h = 0; - k = (u_int8_t *)key; - /* Convert string to integer */ - while (len--) - h = h * PRIME1 ^ (*k++ - ' '); - h %= PRIME2; - return (h); -} - -/* - * Phong Vo's linear congruential hash - */ -#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) - -u_int32_t -hash2(const void *key, size_t len) -{ - u_int32_t h; - u_int8_t *e, c, *k; - - k = (u_int8_t *)key; - e = k + len; - for (h = 0; k != e;) { - c = *k++; - if (!c && k > e) - break; - dcharhash(h, c); - } - return (h); -} - -/* - * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte - * units. On the first time through the loop we get the "leftover bytes" - * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle - * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If - * this routine is heavily used enough, it's worth the ugly coding. - * - * Ozan Yigit's original sdbm hash. - */ -u_int32_t -hash3(const void *key, size_t len) -{ - u_int32_t n, loop; - u_int8_t *k; - -#define HASHC n = *k++ + 65599 * n - - n = 0; - k = (u_int8_t *)key; - if (len > 0) { - loop = (len + 8 - 1) >> 3; - - switch (len & (8 - 1)) { - case 0: - do { /* All fall throughs */ - HASHC; - case 7: - HASHC; - case 6: - HASHC; - case 5: - HASHC; - case 4: - HASHC; - case 3: - HASHC; - case 2: - HASHC; - case 1: - HASHC; - } while (--loop); - } - - } - return (n); -} -#endif /* notdef */ /* Chris Torek's hash function. */ u_int32_t -hash4(const void *key, size_t len) +__default_hash(const void *key, size_t len) { u_int32_t h, loop; u_int8_t *k; diff --git a/lib/libc/hidden/db.h b/lib/libc/hidden/db.h index 57eb5558010..b7175df5ba3 100644 --- a/lib/libc/hidden/db.h +++ b/lib/libc/hidden/db.h @@ -1,4 +1,4 @@ -/* $OpenBSD: db.h,v 1.3 2015/10/17 21:48:42 guenther Exp $ */ +/* $OpenBSD: db.h,v 1.4 2016/05/29 20:47:49 guenther Exp $ */ /* * Copyright (c) 2015 Philip Guenther <guenther@openbsd.org> * @@ -73,6 +73,9 @@ DB *__bt_open(const char *, int, int, const BTREEINFO *, int); DB *__hash_open(const char *, int, int, const HASHINFO *, int); DB *__rec_open(const char *, int, int, const RECNOINFO *, int); void __dbpanic(DB *dbp); + +/* Default hash function, from db/hash/hash_func.c */ +u_int32_t __default_hash(const void *, size_t); __END_HIDDEN_DECLS PROTO_NORMAL(dbopen); diff --git a/lib/libc/stdlib/hcreate.c b/lib/libc/stdlib/hcreate.c index cb547a8d36d..b31108a90e0 100644 --- a/lib/libc/stdlib/hcreate.c +++ b/lib/libc/stdlib/hcreate.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hcreate.c,v 1.6 2015/09/10 18:13:46 guenther Exp $ */ +/* $OpenBSD: hcreate.c,v 1.7 2016/05/29 20:47:49 guenther Exp $ */ /* $NetBSD: hcreate.c,v 1.5 2004/04/23 02:48:12 simonb Exp $ */ /* @@ -55,6 +55,8 @@ #include <string.h> #include <sys/queue.h> +#include <db.h> /* for __default_hash */ + #ifndef _DIAGASSERT #define _DIAGASSERT(x) #endif @@ -79,9 +81,6 @@ SLIST_HEAD(internal_head, internal_entry); #define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5) #define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2) -/* Default hash function, from db/hash/hash_func.c */ -extern u_int32_t (*__default_hash)(const void *, size_t); - static struct internal_head *htable; static size_t htablesize; @@ -164,7 +163,7 @@ hsearch(ENTRY item, ACTION action) _DIAGASSERT(action == ENTER || action == FIND); len = strlen(item.key); - hashval = (*__default_hash)(item.key, len); + hashval = __default_hash(item.key, len); head = &htable[hashval & (htablesize - 1)]; ie = SLIST_FIRST(head); |