[PATCH 2/5] hashmap: allow memihash computation to be continued
From: Johannes Schindelin <hidden>
Date: 2017-02-14 11:33:31
Subsystem:
the rest · Maintainer:
Linus Torvalds
From: Jeff Hostetler <redacted> There are times when we compute the hash on a full path and then the hash on just the path to the parent directory. This can be expensive on large repositories. With the new memihash_continue() function, we can hash the parent directory first, and reuse that computed hash for all directory entries. Signed-off-by: Jeff Hostetler <redacted> Signed-off-by: Johannes Schindelin <redacted> --- hashmap.c | 14 ++++++++++++++ hashmap.h | 2 ++ 2 files changed, 16 insertions(+)
diff --git a/hashmap.c b/hashmap.c
index b10b642229c..061b7d61da6 100644
--- a/hashmap.c
+++ b/hashmap.c@@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len) return hash; } +/* Incoporate another chunk of data into a memihash computation. */ +unsigned int memihash_continue(unsigned int hash, + const void *buf, size_t len) +{ + const unsigned char *p = buf; + while (len--) { + unsigned int c = *p++; + if (c >= 'a' && c <= 'z') + c -= 'a' - 'A'; + hash = (hash * FNV32_PRIME) ^ c; + } + return hash; +} + #define HASHMAP_INITIAL_SIZE 64 /* grow / shrink by 2^2 */ #define HASHMAP_RESIZE_BITS 2
diff --git a/hashmap.h b/hashmap.h
index ab7958ae333..78e14dfde71 100644
--- a/hashmap.h
+++ b/hashmap.h@@ -12,6 +12,8 @@ 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 memihash(const void *buf, size_t len); +extern unsigned int memihash_continue(unsigned int hash_seed, + const void *buf, size_t len); static inline unsigned int sha1hash(const unsigned char *sha1) {
--
2.11.1.windows.1