Rewrite git_hashtable internals

The old hash table with chained buckets has been replaced by a new one
using Cuckoo hashing, which offers guaranteed constant lookup times.
This should improve speeds on most use cases, since hash tables in
libgit2 are usually used as caches where the objects are stored once and
queried several times.

The Cuckoo hash implementation is based off the one in the Basekit
library [1] for the IO language, but rewritten to support an arbritrary
number of hashes. We currently use 3 to maximize the usage of the nodes pool.

[1]: https://github.com/stevedekorte/basekit/blob/master/source/CHash.c

Signed-off-by: Vicent Marti <tanoku@gmail.com>

1 files changed, 12 insertions, 22 deletions

diff --git a/src/refs.c b/src/refs.c
index 1f434ea03..b95ec70cf 100644
--- a/src/refs.c
+++ b/src/refs.c
@@ -28,28 +28,21 @@
 #include "repository.h"
 #include "fileops.h"
 
-#define HASH_SEED 2147483647
 #define MAX_NESTING_LEVEL 5
 
 static const int default_table_size = 32;
 
-static uint32_t reftable_hash(const void *key)
+static uint32_t reftable_hash(const void *key, int hash_id)
 {
-	return git__hash(key, strlen((const char *)key), HASH_SEED);
-}
-
-static int reftable_haskey(void *reference, const void *key)
-{
-	git_reference *ref;
-	char *name;
+	static uint32_t hash_seeds[GIT_HASHTABLE_HASHES] = {
+		2147483647,
+		0x5d20bb23,
+		0x7daaab3c 
+	};
 
-	ref = (git_reference *)reference;
-	name = (char *)key;
-
-	return strcmp(name, ref->name) == 0;
+	return git__hash(key, strlen((const char *)key), hash_seeds[hash_id]);
 }
 
-
 static int check_refname(const char *name) 
 {
 	/*
@@ -641,24 +634,21 @@ int git_repository__refcache_init(git_refcache *refs)
 	refs->cache = git_hashtable_alloc(
 		default_table_size, 
 		reftable_hash,
-		reftable_haskey);
+		(git_hash_keyeq_ptr)strcmp);
 
 	return refs->cache ? GIT_SUCCESS : GIT_ENOMEM; 
 }
 
 void git_repository__refcache_free(git_refcache *refs)
 {
-	git_hashtable_iterator it;
+	const char *ref_name;
 	git_reference *reference;
 
 	assert(refs);
 
-	git_hashtable_iterator_init(refs->cache, &it);
-
-	while ((reference = (git_reference *)git_hashtable_iterator_next(&it)) != NULL) {
-		git_hashtable_remove(refs->cache, reference->name);
-		reference_free(reference);
-	}
+	GIT_HASHTABLE_FOREACH(refs->cache, ref_name, reference,
+		reference_free(reference)
+	);
 
 	git_hashtable_free(refs->cache);
 }