Merge pull request #642 from arrbee/mem-pools

Memory pools and khash hashtables

1 files changed, 32 insertions, 73 deletions

diff --git a/src/revwalk.c b/src/revwalk.c
index 041dc1a1c..4f2f82798 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -8,14 +8,17 @@
 #include "common.h"
 #include "commit.h"
 #include "odb.h"
-#include "hashtable.h"
 #include "pqueue.h"
+#include "pool.h"
+#include "oidmap.h"
 
 #include "git2/revwalk.h"
 #include "git2/merge.h"
 
 #include <regex.h>
 
+GIT__USE_OIDMAP;
+
 #define PARENT1  (1 << 0)
 #define PARENT2  (1 << 1)
 #define RESULT   (1 << 2)
@@ -45,7 +48,8 @@ struct git_revwalk {
 	git_repository *repo;
 	git_odb *odb;
 
-	git_hashtable *commits;
+	git_oidmap *commits;
+	git_pool commit_pool;
 
 	commit_list *iterator_topo;
 	commit_list *iterator_rand;
@@ -55,9 +59,6 @@ struct git_revwalk {
 	int (*get_next)(commit_object **, git_revwalk *);
 	int (*enqueue)(git_revwalk *, commit_object *);
 
-	git_vector memory_alloc;
-	size_t chunk_size;
-
 	unsigned walking:1;
 	unsigned int sorting;
 
@@ -124,60 +125,36 @@ static commit_object *commit_list_pop(commit_list **stack)
 	return item;
 }
 
-static uint32_t object_table_hash(const void *key, int hash_id)
-{
-	uint32_t r;
-	const git_oid *id = key;
-
-	memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
-	return r;
-}
-
-#define COMMITS_PER_CHUNK 128
-#define CHUNK_STEP 64
-#define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *))
-
-static int alloc_chunk(git_revwalk *walk)
-{
-	void *chunk;
-
-	chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP);
-	GITERR_CHECK_ALLOC(chunk);
-
-	walk->chunk_size = 0;
-	return git_vector_insert(&walk->memory_alloc, chunk);
-}
+#define PARENTS_PER_COMMIT	2
+#define COMMIT_ALLOC \
+	(sizeof(commit_object) + PARENTS_PER_COMMIT * sizeof(commit_object *))
 
 static commit_object *alloc_commit(git_revwalk *walk)
 {
-	unsigned char *chunk;
-
-	if (walk->chunk_size == COMMITS_PER_CHUNK)
-		if (alloc_chunk(walk) < 0)
-			return NULL;
-
-	chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1);
-	chunk += (walk->chunk_size * CHUNK_STEP);
-	walk->chunk_size++;
-
-	return (commit_object *)chunk;
+	return (commit_object *)git_pool_malloc(&walk->commit_pool, COMMIT_ALLOC);
 }
 
-static commit_object **alloc_parents(commit_object *commit, size_t n_parents)
+static commit_object **alloc_parents(
+	git_revwalk *walk, commit_object *commit, size_t n_parents)
 {
 	if (n_parents <= PARENTS_PER_COMMIT)
-		return (commit_object **)((unsigned char *)commit + sizeof(commit_object));
+		return (commit_object **)((char *)commit + sizeof(commit_object));
 
-	return git__malloc(n_parents * sizeof(commit_object *));
+	return (commit_object **)git_pool_malloc(
+		&walk->commit_pool, n_parents * sizeof(commit_object *));
 }
 
 
 static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 {
 	commit_object *commit;
+	khiter_t pos;
+	int ret;
 
-	if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)
-		return commit;
+	/* lookup and reserve space if not already present */
+	pos = kh_get(oid, walk->commits, oid);
+	if (pos != kh_end(walk->commits))
+		return kh_value(walk->commits, pos);
 
 	commit = alloc_commit(walk);
 	if (commit == NULL)
@@ -185,10 +162,9 @@ static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 
 	git_oid_cpy(&commit->oid, oid);
 
-	if (git_hashtable_insert(walk->commits, &commit->oid, commit) < 0) {
-		git__free(commit);
-		return NULL;
-	}
+	pos = kh_put(oid, walk->commits, &commit->oid, &ret);
+	assert(ret != 0);
+	kh_value(walk->commits, pos) = commit;
 
 	return commit;
 }
@@ -212,7 +188,7 @@ static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawo
 		buffer += parent_len;
 	}
 
-	commit->parents = alloc_parents(commit, parents);
+	commit->parents = alloc_parents(walk, commit, parents);
 	GITERR_CHECK_ALLOC(commit->parents);
 
 	buffer = parents_start;
@@ -757,15 +733,13 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 
 	memset(walk, 0x0, sizeof(git_revwalk));
 
-	walk->commits = git_hashtable_alloc(64,
-			object_table_hash,
-			(git_hash_keyeq_ptr)git_oid_cmp);
+	walk->commits = git_oidmap_alloc();
 	GITERR_CHECK_ALLOC(walk->commits);
 
 	if (git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp) < 0 ||
-		git_vector_init(&walk->memory_alloc, 8, NULL) < 0 ||
 		git_vector_init(&walk->twos, 4, NULL) < 0 ||
-		alloc_chunk(walk) < 0)
+		git_pool_init(&walk->commit_pool, 1,
+			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
 		return -1;
 
 	walk->get_next = &revwalk_next_unsorted;
@@ -784,30 +758,15 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 
 void git_revwalk_free(git_revwalk *walk)
 {
-	unsigned int i;
-	commit_object *commit;
-
 	if (walk == NULL)
 		return;
 
 	git_revwalk_reset(walk);
 	git_odb_free(walk->odb);
 
-	/* if the parent has more than PARENTS_PER_COMMIT parents,
-	 * we had to allocate a separate array for those parents.
-	 * make sure it's being free'd */
-	GIT_HASHTABLE_FOREACH_VALUE(walk->commits, commit, {
-		if (commit->out_degree > PARENTS_PER_COMMIT)
-			git__free(commit->parents);
-	});
-
-	git_hashtable_free(walk->commits);
+	git_oidmap_free(walk->commits);
+	git_pool_clear(&walk->commit_pool);
 	git_pqueue_free(&walk->iterator_time);
-
-	for (i = 0; i < walk->memory_alloc.length; ++i)
-		git__free(git_vector_get(&walk->memory_alloc, i));
-
-	git_vector_free(&walk->memory_alloc);
 	git_vector_free(&walk->twos);
 	git__free(walk);
 }
@@ -867,12 +826,12 @@ void git_revwalk_reset(git_revwalk *walk)
 
 	assert(walk);
 
-	GIT_HASHTABLE_FOREACH_VALUE(walk->commits, commit,
+	kh_foreach_value(walk->commits, commit, {
 		commit->seen = 0;
 		commit->in_degree = 0;
 		commit->topo_delay = 0;
 		commit->uninteresting = 0;
-	);
+		});
 
 	git_pqueue_clear(&walk->iterator_time);
 	commit_list_free(&walk->iterator_topo);