[PATCH 2/5] hashmap: allow memihash computation to be continued
- From
Johannes Schindelin <johannes.schindelin@gmx.de>
- Date
- Feb 14, 2017, 11:32 UTC
- Message-ID
- <bd4893f86c4484fc36480848bf2d0905d961e022.1487071883.git.johannes.schindelin@gmx.de>
- In-Reply-To
- <cover.1487071883.git.johannes.schindelin@gmx.de>
From: Jeff Hostetler <jeffhost@microsoft.com>
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 <jeffhost@microsoft.com> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> --- 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