Re: [PATCH 1/4] hashmap: introduce memhash_feed to access the internals of FNV-1 hash
From: René Scharfe <hidden>
Date: 2017-10-24 20:23:36
Am 24.10.2017 um 20:59 schrieb Stefan Beller:
quoted hunk ↗ jump to hunk
This will be useful shortly. Signed-off-by: Stefan Beller <redacted> --- hashmap.c | 7 ++++++- hashmap.h | 3 +++ 2 files changed, 9 insertions(+), 1 deletion(-)diff --git a/hashmap.c b/hashmap.c index d42f01ff5a..d103eb1fd2 100644 --- a/hashmap.c +++ b/hashmap.c@@ -26,13 +26,18 @@ unsigned int strihash(const char *str) return hash; } +unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next)
Why is the second parameter const and the first one isn't? (We tend not to bother with const for value types.)
quoted hunk ↗ jump to hunk
+{ + return (hash_seed * FNV32_PRIME) ^ next; +} + unsigned int memhash(const void *buf, size_t len) { unsigned int hash = FNV32_BASE; unsigned char *ucbuf = (unsigned char *) buf; while (len--) { unsigned int c = *ucbuf++; - hash = (hash * FNV32_PRIME) ^ c; + hash = memhash_feed(hash, c);
I guess compilers inline a copy of the function here with -O2. My knee-jerk reaction, however, is horror in the face of adding a function call to the inner loop of a hash function. Do you have performance test results, ideally also with -O0? And why not make memhash_feed() an inline function or macro to sidestep that issue?
quoted hunk ↗ jump to hunk
} return hash; }diff --git a/hashmap.h b/hashmap.h index 7cb29a6aed..c2464385ed 100644 --- a/hashmap.h +++ b/hashmap.h@@ -105,10 +105,13 @@ * `strihash` and `memihash` are case insensitive versions. * `memihash_cont` is a variant of `memihash` that allows a computation to be * continued with another chunk of data. + * `memhash_feed` takes just one character and returns the hash based off + * a previous hash. */ extern unsigned int strhash(const char *buf); extern unsigned int strihash(const char *buf); extern unsigned int memhash(const void *buf, size_t len); +extern unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next); extern unsigned int memihash(const void *buf, size_t len); extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);