[PATCH 1/5] fnv: migrate code from hashmap to fnv
The functions regarding the Fowler–Noll–Vo hash function are put in a separate compilation unit, as it is logically different from the hashmap functionality.
Signed-off-by: Stefan Beller <sbeller@google.com>
---
This may still be an interesting cleanup on its own.
Thanks, Stefan
Makefile | 1 +
attr.c | 1 +
builtin/fast-export.c | 1 +
diff.c | 1 +
fnv.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++
fnv.h | 20 ++++++++++++++++
hashmap.c | 64 +------------------------------------------------
hashmap.h | 15 ------------
merge-recursive.c | 1 +
remote.c | 1 +
submodule-config.c | 1 +
t/helper/test-hashmap.c | 1 +
12 files changed, 93 insertions(+), 78 deletions(-)
create mode 100644 fnv.c
create mode 100644 fnv.h
Show changes to 12 files +93 −78
Makefile, attr.c, builtin/fast-export.c, diff.c, fnv.c, fnv.h, hashmap.c, hashmap.h, merge-recursive.c, remote.c, submodule-config.c, t/helper/test-hashmap.c
diff --git a/Makefile b/Makefile
index cd75985991..8e1c5988f3 100644
--- a/Makefile
+++ b/Makefile
@@ -793,6 +793,7 @@ LIB_OBJS += ewah/ewah_io.o
LIB_OBJS += ewah/ewah_rlw.o
LIB_OBJS += exec_cmd.o
LIB_OBJS += fetch-pack.o
+LIB_OBJS += fnv.o
LIB_OBJS += fsck.o
LIB_OBJS += gettext.o
LIB_OBJS += gpg-interface.o
diff --git a/attr.c b/attr.c
index dfc3a558d8..2e4217c4f1 100644
--- a/attr.c
+++ b/attr.c
@@ -16,6 +16,7 @@
#include "utf8.h"
#include "quote.h"
#include "thread-utils.h"
+#include "fnv.h"
const char git_attr__true[] = "(builtin)true";
const char git_attr__false[] = "\0(builtin)false";
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 2fb60d6d48..62f4010510 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -21,6 +21,7 @@
#include "quote.h"
#include "remote.h"
#include "blob.h"
+#include "fnv.h"
static const char *fast_export_usage[] = {
N_("git fast-export [rev-list-opts]"),
diff --git a/diff.c b/diff.c
index c4a669ffa8..a23f4521fb 100644
--- a/diff.c
+++ b/diff.c
@@ -22,6 +22,7 @@
#include "argv-array.h"
#include "graph.h"
#include "packfile.h"
+#include "fnv.h"
#ifdef NO_FAST_WORKING_DIRECTORY
#define FAST_WORKING_DIRECTORY 0
diff --git a/fnv.c b/fnv.c
new file mode 100644
index 0000000000..b4cbf39f0a
--- /dev/null
+++ b/fnv.c
@@ -0,0 +1,64 @@
+#include "fnv.h"
+
+#define FNV32_BASE ((unsigned int) 0x811c9dc5)
+#define FNV32_PRIME ((unsigned int) 0x01000193)
+
+unsigned int strhash(const char *str)
+{
+ unsigned int c, hash = FNV32_BASE;
+ while ((c = (unsigned char) *str++))
+ hash = (hash * FNV32_PRIME) ^ c;
+ return hash;
+}
+
+unsigned int strihash(const char *str)
+{
+ unsigned int c, hash = FNV32_BASE;
+ while ((c = (unsigned char) *str++)) {
+ if (c >= 'a' && c <= 'z')
+ c -= 'a' - 'A';
+ hash = (hash * FNV32_PRIME) ^ c;
+ }
+ return hash;
+}
+
+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;
+ }
+ return hash;
+}
+
+unsigned int memihash(const void *buf, size_t len)
+{
+ unsigned int hash = FNV32_BASE;
+ unsigned char *ucbuf = (unsigned char *) buf;
+ while (len--) {
+ unsigned int c = *ucbuf++;
+ if (c >= 'a' && c <= 'z')
+ c -= 'a' - 'A';
+ hash = (hash * FNV32_PRIME) ^ c;
+ }
+ return hash;
+}
+
+/*
+ * Incoporate another chunk of data into a memihash
+ * computation.
+ */
+unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)
+{
+ unsigned int hash = hash_seed;
+ unsigned char *ucbuf = (unsigned char *) buf;
+ while (len--) {
+ unsigned int c = *ucbuf++;
+ if (c >= 'a' && c <= 'z')
+ c -= 'a' - 'A';
+ hash = (hash * FNV32_PRIME) ^ c;
+ }
+ return hash;
+}
diff --git a/fnv.h b/fnv.h
new file mode 100644
index 0000000000..b425c85c66
--- /dev/null
+++ b/fnv.h
@@ -0,0 +1,20 @@
+#ifndef FNV_H
+#define FNV_H
+
+#include <stdlib.h>
+/*
+ * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see
+ * http://www.isthe.com/chongo/tech/comp/fnv).
+ * `strhash` and `strihash` take 0-terminated strings, while `memhash` and
+ * `memihash` operate on arbitrary-length memory.
+ * `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.
+ */
+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_cont(unsigned int hash_seed, const void *buf, size_t len);
+
+#endif
diff --git a/hashmap.c b/hashmap.c
index d42f01ff5a..1605edbbc3 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -3,69 +3,7 @@
*/
#include "cache.h"
#include "hashmap.h"
-
-#define FNV32_BASE ((unsigned int) 0x811c9dc5)
-#define FNV32_PRIME ((unsigned int) 0x01000193)
-
-unsigned int strhash(const char *str)
-{
- unsigned int c, hash = FNV32_BASE;
- while ((c = (unsigned char) *str++))
- hash = (hash * FNV32_PRIME) ^ c;
- return hash;
-}
-
-unsigned int strihash(const char *str)
-{
- unsigned int c, hash = FNV32_BASE;
- while ((c = (unsigned char) *str++)) {
- if (c >= 'a' && c <= 'z')
- c -= 'a' - 'A';
- hash = (hash * FNV32_PRIME) ^ c;
- }
- return hash;
-}
-
-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;
- }
- return hash;
-}
-
-unsigned int memihash(const void *buf, size_t len)
-{
- unsigned int hash = FNV32_BASE;
- unsigned char *ucbuf = (unsigned char *) buf;
- while (len--) {
- unsigned int c = *ucbuf++;
- if (c >= 'a' && c <= 'z')
- c -= 'a' - 'A';
- hash = (hash * FNV32_PRIME) ^ c;
- }
- return hash;
-}
-
-/*
- * Incoporate another chunk of data into a memihash
- * computation.
- */
-unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)
-{
- unsigned int hash = hash_seed;
- unsigned char *ucbuf = (unsigned char *) buf;
- while (len--) {
- unsigned int c = *ucbuf++;
- if (c >= 'a' && c <= 'z')
- c -= 'a' - 'A';
- hash = (hash * FNV32_PRIME) ^ c;
- }
- return hash;
-}
+#include "fnv.h"
#define HASHMAP_INITIAL_SIZE 64
/* grow / shrink by 2^2 */
diff --git a/hashmap.h b/hashmap.h
index 7cb29a6aed..96176f7d8c 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -97,21 +97,6 @@
* }
*/
-/*
- * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see
- * http://www.isthe.com/chongo/tech/comp/fnv).
- * `strhash` and `strihash` take 0-terminated strings, while `memhash` and
- * `memihash` operate on arbitrary-length memory.
- * `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.
- */
-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_cont(unsigned int hash_seed, const void *buf, size_t len);
-
/*
* Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code
* for use in hash tables. Cryptographic hashes are supposed to have
diff --git a/merge-recursive.c b/merge-recursive.c
index 1d3f8f0d22..d1fb2f5f3d 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -22,6 +22,7 @@
#include "attr.h"
#include "merge-recursive.h"
#include "dir.h"
+#include "fnv.h"
#include "submodule.h"
struct path_hashmap_entry {
diff --git a/remote.c b/remote.c
index b220f0dfc6..24957ba32c 100644
--- a/remote.c
+++ b/remote.c
@@ -10,6 +10,7 @@
#include "string-list.h"
#include "mergesort.h"
#include "argv-array.h"
+#include "fnv.h"
enum map_direction { FROM_SRC, FROM_DST };
diff --git a/submodule-config.c b/submodule-config.c
index 2aa8a1747f..432423f876 100644
--- a/submodule-config.c
+++ b/submodule-config.c
@@ -5,6 +5,7 @@
#include "submodule.h"
#include "strbuf.h"
#include "parse-options.h"
+#include "fnv.h"
/*
* submodule cache lookup structure
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 1145d51671..b5ac97886f 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -1,5 +1,6 @@
#include "git-compat-util.h"
#include "hashmap.h"
+#include "fnv.h"
struct test_entry
{
--
2.15.0.rc2.6.g953226eb5f
Stefan Beller
