From: Jeff Hostetler <jeffhost@xxxxxxxxxxxxx>
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@xxxxxxxxxxxxx>
Signed-off-by: Johannes Schindelin <johannes.schindelin@xxxxxx>
---
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