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, 10 insertions, 18 deletions

diff --git a/src/revwalk.c b/src/revwalk.c
index e30e543a8..c073be13f 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -28,28 +28,23 @@
 #include "revwalk.h"
 #include "hashtable.h"
 
-uint32_t git_revwalk__commit_hash(const void *key)
+uint32_t git_revwalk__commit_hash(const void *key, int hash_id)
 {
 	uint32_t r;
 	git_commit *commit;
 
 	commit = (git_commit *)key;
-	memcpy(&r, commit->object.id.id, sizeof(r));
+	memcpy(&r, commit->object.id.id + (hash_id * sizeof(uint32_t)), sizeof(r));
 	return r;
 }
 
-int git_revwalk__commit_haskey(void *object, const void *key)
+int git_revwalk__commit_keycmp(const void *key_a, const void *key_b)
 {
-	git_revwalk_commit *walk_commit;
-	git_commit *commit_object;
-
-	walk_commit = (git_revwalk_commit *)object;
-	commit_object = (git_commit *)key;
-
-	return (walk_commit->commit_object == commit_object);
+	git_commit *a = (git_commit *)key_a;
+	git_commit *b = (git_commit *)key_b;
+	return git_oid_cmp(&a->object.id, &b->object.id);
 }
 
-
 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 {
 	git_revwalk *walk;
@@ -62,7 +57,7 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 
 	walk->commits = git_hashtable_alloc(64,
 			git_revwalk__commit_hash,
-			git_revwalk__commit_haskey);
+			git_revwalk__commit_keycmp);
 
 	if (walk->commits == NULL) {
 		free(walk);
@@ -245,18 +240,15 @@ int git_revwalk_next(git_commit **commit, git_revwalk *walk)
 
 void git_revwalk_reset(git_revwalk *walk)
 {
-	git_hashtable_iterator it;
+	const void *_unused;
 	git_revwalk_commit *commit;
 
 	assert(walk);
 
-	git_hashtable_iterator_init(walk->commits, &it);
-
-	while ((commit = (git_revwalk_commit *)
-				git_hashtable_iterator_next(&it)) != NULL) {
+	GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit, {
 		git_revwalk_list_clear(&commit->parents);
 		free(commit);
-	}
+	});
 
 	git_hashtable_clear(walk->commits);
 	git_revwalk_list_clear(&walk->iterator);