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, 29 insertions, 20 deletions

diff --git a/src/hashtable.h b/src/hashtable.h
index 69535040d..74da580ef 100644
--- a/src/hashtable.h
+++ b/src/hashtable.h
@@ -5,39 +5,33 @@
 #include "git2/oid.h"
 #include "git2/odb.h"
 
+#define GIT_HASHTABLE_HASHES 3
 
-typedef uint32_t (*git_hash_ptr)(const void *);
-typedef int (*git_hash_keyeq_ptr)(void *obj, const void *obj_key);
+typedef uint32_t (*git_hash_ptr)(const void *, int hash_id);
+typedef int (*git_hash_keyeq_ptr)(const void *key_a, const void *key_b);
 
 struct git_hashtable_node {
-	void *object;
-	uint32_t hash;
-	struct git_hashtable_node *next;
+	const void *key;
+	void *value;
 };
 
 struct git_hashtable {
-	struct git_hashtable_node **nodes;
+	struct git_hashtable_node *nodes;
 
-	unsigned int size_mask;
-	unsigned int count;
-	unsigned int max_count;
+	size_t size_mask;
+	size_t size;
+	size_t key_count;
+
+	int is_resizing;
 
 	git_hash_ptr hash;
 	git_hash_keyeq_ptr key_equal;
 };
 
-struct git_hashtable_iterator {
-	struct git_hashtable_node **nodes;
-	struct git_hashtable_node *current_node;
-	unsigned int current_pos;
-	unsigned int size;
-};
-
 typedef struct git_hashtable_node git_hashtable_node;
 typedef struct git_hashtable git_hashtable;
-typedef struct git_hashtable_iterator git_hashtable_iterator;
 
-git_hashtable *git_hashtable_alloc(unsigned int min_size, 
+git_hashtable *git_hashtable_alloc(size_t min_size, 
 		git_hash_ptr hash,
 		git_hash_keyeq_ptr key_eq);
 int git_hashtable_insert(git_hashtable *h, const void *key, void *value);
@@ -46,7 +40,22 @@ int git_hashtable_remove(git_hashtable *table, const void *key);
 void git_hashtable_free(git_hashtable *h);
 void git_hashtable_clear(git_hashtable *h);
 
-void *git_hashtable_iterator_next(git_hashtable_iterator *it);
-void git_hashtable_iterator_init(git_hashtable *h, git_hashtable_iterator *it);
+#define git_hashtable_node_at(nodes, pos) ((git_hashtable_node *)(&nodes[pos]))
+
+#define GIT_HASHTABLE_FOREACH(self, pkey, pvalue, code) {\
+	git_hashtable *_self = (self);\
+	git_hashtable_node *_nodes = _self->nodes;\
+	unsigned int _i, _size = _self->size;\
+	for (_i = 0; _i < _size; _i ++) {\
+		git_hashtable_node *_node = git_hashtable_node_at(_nodes, _i);\
+		if (_node->key)\
+		{\
+			pkey = _node->key;\
+			pvalue = _node->value;\
+			code;\
+		}\
+	}\
+}
+
 
 #endif