Redesigned the walking/object lookup interface

The old 'git_revpool' object has been removed and
split into two distinct objects with separate
functionality, in order to have separate methods for
object management and object walking.

*	A new object 'git_repository' does the high-level
	management of a repository's objects (commits, trees,
	tags, etc) on top of a 'git_odb'.

	Eventually, it will also manage other repository
	attributes (e.g. tag resolution, references, etc).

	See: src/git/repository.h

*	A new external method
		'git_repository_lookup(repo, oid, type)'
	has been added to the 'git_repository' API.

	All object lookups (git_XXX_lookup()) are now
	wrappers to this method, and duplicated code
	has been removed. The method does automatic type
	checking and returns a generic 'git_revpool_object'
	that can be cast to any specific object.

	See: src/git/repository.h

*	The external methods for object parsing of repository
	objects (git_XXX_parse()) have been removed.

	Loading objects from the repository is now managed
	through the 'lookup' functions. These objects are
	loaded with minimal information, and the relevant
	parsing is done automatically when the user requests
	any of the parsed attributes through accessor methods.

	An attribute has been added to 'git_repository' in
	order to force the parsing of all the repository objects
	immediately after lookup.

	See: src/git/commit.h
	See: src/git/tag.h
	See: src/git/tree.h

*	The previous walking functionality of the revpool
	is now found in 'git_revwalk', which does the actual
	revision walking on a repository; the attributes
	when walking through commits in a database have been
	decoupled from the actual commit objects.
	This increases performance when accessing commits
	during the walk and allows to have several
	'git_revwalk' instances working at the same time on
	top of the same repository, without having to load
	commits in memory several times.

	See: src/git/revwalk.h

*	The old 'git_revpool_table' has been renamed to
	'git_hashtable' and now works as a generic hashtable
	with support for any kind of object and custom hash
	functions.

	See: src/hashtable.h

*	All the relevant unit tests have been updated, renamed
	and grouped accordingly.

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

1 files changed, 337 insertions, 107 deletions

diff --git a/src/revwalk.c b/src/revwalk.c
index d4627ae2e..ca008849a 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -26,187 +26,417 @@
 #include "common.h"
 #include "commit.h"
 #include "revwalk.h"
+#include "hashtable.h"
 
-static const int default_table_size = 32;
+uint32_t git_revwalk_commit_hash(const void *key)
+{
+	uint32_t r;
+	git_commit *commit;
 
-git_revpool *gitrp_alloc(git_odb *db)
+	commit = (git_commit *)key;
+	memcpy(&r, commit->object.id.id, sizeof(r));
+	return r;
+}
+
+int git_revwalk_commit_haskey(void *object, const void *key)
 {
-	git_revpool *walk = git__malloc(sizeof(*walk));
-	if (!walk)
+	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_revwalk *git_revwalk_alloc(git_repository *repo)
+{
+	git_revwalk *walk;
+
+	walk = git__malloc(sizeof(git_revwalk));
+	if (walk == NULL)
 		return NULL;
 
-	memset(walk, 0x0, sizeof(git_revpool));
+	memset(walk, 0x0, sizeof(git_revwalk));
 
-	walk->objects = git_revpool_table_create(default_table_size);
+	walk->commits = git_hashtable_alloc(64,
+			git_revwalk_commit_hash,
+			git_revwalk_commit_haskey);
+
+	if (walk->commits == NULL) {
+		free(walk);
+		return NULL;
+	}
 
-	walk->db = db;
+	walk->repo = repo;
 	return walk;
 }
 
-void gitrp_free(git_revpool *walk)
+void git_revwalk_free(git_revwalk *walk)
 {
-	git_revpool_object *obj;
-	git_revpool_tableit it;
+	git_revwalk_reset(walk);
+	git_hashtable_free(walk->commits);
+	free(walk);
+}
 
-	git_commit_list_clear(&(walk->iterator), 0);
-	git_commit_list_clear(&(walk->roots), 0);
+void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
+{
+	if (walk->walking)
+		return;
 
-	git_revpool_tableit_init(walk->objects, &it);
+	walk->sorting = sort_mode;
+	git_revwalk_reset(walk);
+}
 
-	while ((obj = git_revpool_tableit_next(&it)) != NULL) {
-		switch (obj->type) {
+static git_revwalk_commit *commit_to_walkcommit(git_revwalk *walk, git_commit *commit_object)
+{
+	git_revwalk_commit *commit;
 
-		case GIT_OBJ_COMMIT:
-			git_commit__free((git_commit *)obj);
-			break;
+	commit = (git_revwalk_commit *)git_hashtable_lookup(walk->commits, commit_object);
 
-		case GIT_OBJ_TREE:
-			git_tree__free((git_tree *)obj);
-			break;
+	if (commit != NULL)
+		return commit;
 
-		default:
-			free(obj);
-			break;
-		}
+	if (!commit_object->basic_parse) {
+		if (git_commit__parse_basic(commit_object) < 0)
+			return NULL;
 	}
 
-	git_revpool_table_free(walk->objects);
+	commit = git__malloc(sizeof(git_revwalk_commit));
+	if (commit == NULL)
+		return NULL;
 
-	free(walk);
+	memset(commit, 0x0, sizeof(git_revwalk_commit));
+
+	commit->commit_object = commit_object;
+
+	git_hashtable_insert(walk->commits, commit_object, commit);
+
+	return commit;
 }
 
-void gitrp_sorting(git_revpool *pool, unsigned int sort_mode)
+static git_revwalk_commit *insert_commit(git_revwalk *walk, git_commit *commit_object)
 {
-	if (pool->walking)
-		return;
+	git_revwalk_commit *commit;
+	git_commit_parents *parents;
+
+	assert(walk && commit_object);
+
+	if (commit_object->object.repo != walk->repo || walk->walking)
+		return NULL;
+
+	commit = commit_to_walkcommit(walk, commit_object);
+	if (commit == NULL)
+		return NULL;
 
-	pool->sorting = sort_mode;
-	gitrp_reset(pool);
+	if (commit->seen)
+		return commit;
+
+	commit->seen = 1;
+
+	assert(commit->commit_object->basic_parse);
+
+	for (parents = commit->commit_object->parents; parents != NULL; parents = parents->next) {
+		git_revwalk_commit *parent;
+
+		if ((parent = commit_to_walkcommit(walk, parents->commit)) == NULL)
+			return NULL;
+
+		parent = insert_commit(walk, parents->commit);
+		if (parent == NULL)
+			return NULL;
+
+		parent->in_degree++;
+
+		git_revwalk_list_push_back(&commit->parents, parent);
+	}
+
+	if (git_revwalk_list_push_back(&walk->iterator, commit))
+		return NULL;
+
+	return commit;
 }
 
-int gitrp_push(git_revpool *pool, git_commit *commit)
+int git_revwalk_push(git_revwalk *walk, git_commit *commit)
 {
-	if (commit == NULL || commit->seen)
-		return GIT_ENOTFOUND;
+	return insert_commit(walk, commit) ? GIT_SUCCESS : GIT_ERROR;
+}
 
-	if (commit->object.pool != pool || pool->walking)
-		return GIT_ERROR;
+static void mark_uninteresting(git_revwalk_commit *commit)
+{
+	git_revwalk_listnode *parent;
+
+	if (commit == NULL)
+		return;
 
-	if (!commit->basic_parse) {
-		int error = git_commit__parse_basic(commit);
+	commit->uninteresting = 1;
+	parent = commit->parents.head;
 
-		if (error < 0)
-			return error;
+	while (parent) {
+		mark_uninteresting(parent->walk_commit);
+		parent = parent->next;
 	}
+}
+
+int git_revwalk_hide(git_revwalk *walk, git_commit *commit)
+{
+	git_revwalk_commit *hide;
+	
+	hide = insert_commit(walk, commit);
+	if (hide == NULL)
+		return GIT_ERROR;
 
-	/*
-	 * Sanity check: make sure that if the commit
-	 * has been manually marked as uninteresting,
-	 * all the parent commits are too.
-	 */
-	if (commit->uninteresting)
-		git_commit__mark_uninteresting(commit);
+	mark_uninteresting(hide);
+	return GIT_SUCCESS;
+}
 
-	if (git_commit_list_push_back(&pool->roots, commit) < 0)
-		return GIT_ENOMEM;
 
-	return 0;
+static void prepare_walk(git_revwalk *walk)
+{
+	if (walk->sorting & GIT_SORT_TIME)
+		git_revwalk_list_timesort(&walk->iterator);
+
+	if (walk->sorting & GIT_SORT_TOPOLOGICAL)
+		git_revwalk_list_toposort(&walk->iterator);
+
+	if (walk->sorting & GIT_SORT_REVERSE)
+		walk->next = &git_revwalk_list_pop_back;
+	else
+		walk->next = &git_revwalk_list_pop_front;
+
+	walk->walking = 1;
 }
 
-int gitrp_hide(git_revpool *pool, git_commit *commit)
+git_commit *git_revwalk_next(git_revwalk *walk)
 {
-	if (pool->walking)
-		return GIT_ERROR;
+	git_revwalk_commit *next;
 
-	git_commit__mark_uninteresting(commit);
-	return gitrp_push(pool, commit);
+	if (!walk->walking)
+		prepare_walk(walk);
+
+	while ((next = walk->next(&walk->iterator)) != NULL) {
+		if (!next->uninteresting)
+			return next->commit_object;
+	}
+
+	/* No commits left to iterate */
+	git_revwalk_reset(walk);
+	return NULL;
 }
 
-int gitrp__enroot(git_revpool *pool, git_commit *commit)
+void git_revwalk_reset(git_revwalk *walk)
 {
-	int error;
-	git_commit_node *parents;
+	git_hashtable_iterator it;
+	git_revwalk_commit *commit;
 
-	if (commit->seen)
-		return 0;
+	git_hashtable_iterator_init(walk->commits, &it);
 
-	if (!commit->basic_parse) {
-		error = git_commit__parse_basic(commit);
-		if (error < 0)
-			return error;
+	while ((commit = (git_revwalk_commit *)
+				git_hashtable_iterator_next(&it)) != NULL) {
+		git_revwalk_list_clear(&commit->parents);
+		free(commit);
 	}
 
-	commit->seen = 1;
+	git_hashtable_clear(walk->commits);
+	git_revwalk_list_clear(&walk->iterator);
+	walk->walking = 0;
+}
+
+
+
+
+
+
+int git_revwalk_list_push_back(git_revwalk_list *list, git_revwalk_commit *commit)
+{
+	git_revwalk_listnode *node = NULL;
+
+	node = git__malloc(sizeof(git_revwalk_listnode));
+
+	if (node == NULL)
+		return GIT_ENOMEM;
 
-	for (parents = commit->parents.head; parents != NULL; parents = parents->next) {
-		parents->commit->in_degree++;
+	node->walk_commit = commit;
+	node->next = NULL;
+	node->prev = list->tail;
 
-		error = gitrp__enroot(pool, parents->commit);
-		if (error < 0)
-			return error;
+	if (list->tail == NULL) {
+		list->head = list->tail = node;
+	} else {
+		list->tail->next = node;
+		list->tail = node;
 	}
 
-	if (git_commit_list_push_back(&pool->iterator, commit))
+	list->size++;
+	return 0;
+}
+
+int git_revwalk_list_push_front(git_revwalk_list *list, git_revwalk_commit *commit)
+{
+	git_revwalk_listnode *node = NULL;
+
+	node = git__malloc(sizeof(git_revwalk_listnode));
+
+	if (node == NULL)
 		return GIT_ENOMEM;
 
+	node->walk_commit = commit;
+	node->next = list->head;
+	node->prev = NULL;
+
+	if (list->head == NULL) {
+		list->head = list->tail = node;
+	} else {
+		list->head->prev = node;
+		list->head = node;
+	}
+
+	list->size++;
 	return 0;
 }
 
-void gitrp__prepare_walk(git_revpool *pool)
+
+git_revwalk_commit *git_revwalk_list_pop_back(git_revwalk_list *list)
 {
-	git_commit_node *it;
+	git_revwalk_listnode *node;
+	git_revwalk_commit *commit;
 
-	for (it = pool->roots.head; it != NULL; it = it->next)
-		gitrp__enroot(pool, it->commit);
+	if (list->tail == NULL)
+		return NULL;
 
-	if (pool->sorting & GIT_RPSORT_TIME)
-		git_commit_list_timesort(&pool->iterator);
+	node = list->tail;
+	list->tail = list->tail->prev;
+	if (list->tail == NULL)
+		list->head = NULL;
 
-	if (pool->sorting & GIT_RPSORT_TOPOLOGICAL)
-		git_commit_list_toposort(&pool->iterator);
+	commit = node->walk_commit;
+	free(node);
 
-	if (pool->sorting & GIT_RPSORT_REVERSE)
-		pool->next_commit = &git_commit_list_pop_back;
-	else
-		pool->next_commit = &git_commit_list_pop_front;
+	list->size--;
 
-	pool->walking = 1;
+	return commit;
 }
 
-git_commit *gitrp_next(git_revpool *pool)
+git_revwalk_commit *git_revwalk_list_pop_front(git_revwalk_list *list)
 {
-	git_commit *next;
+	git_revwalk_listnode *node;
+	git_revwalk_commit *commit;
+
+	if (list->head == NULL)
+		return NULL;
 
-	if (!pool->walking)
-		gitrp__prepare_walk(pool);
+	node = list->head;
+	list->head = list->head->next;
+	if (list->head == NULL)
+		list->tail = NULL;
 
-	while ((next = pool->next_commit(&pool->iterator)) != NULL) {
-		if (!next->uninteresting)
-			return next;
+	commit = node->walk_commit;
+	free(node);
+
+	list->size--;
+
+	return commit;
+}
+
+void git_revwalk_list_clear(git_revwalk_list *list)
+{
+	git_revwalk_listnode *node, *next_node;
+
+	node = list->head;
+	while (node) {
+		next_node = node->next;
+		free(node);
+		node = next_node;
 	}
 
-	/* No commits left to iterate */
-	gitrp_reset(pool);
-	return NULL;
+	list->head = list->tail = NULL;
+	list->size = 0;
 }
 
-void gitrp_reset(git_revpool *pool)
+void git_revwalk_list_timesort(git_revwalk_list *list)
 {
-	git_commit *commit;
-	git_revpool_tableit it;
+	git_revwalk_listnode *p, *q, *e;
+	int in_size, p_size, q_size, merge_count, i;
+
+	if (list->head == NULL)
+		return;
+
+	in_size = 1;
+
+	do {
+		p = list->head;
+		list->tail = NULL;
+		merge_count = 0;
+
+		while (p != NULL) {
+			merge_count++;
+			q = p;
+			p_size = 0;
+			q_size = in_size;
+
+			for (i = 0; i < in_size && q; ++i, q = q->next)
+				p_size++;
+
+			while (p_size > 0 || (q_size > 0 && q)) {
 
-	git_revpool_tableit_init(pool->objects, &it);
+				if (p_size == 0)
+					e = q, q = q->next, q_size--;
 
-	while ((commit =
-			(git_commit *)git_revpool_tableit_nextfilter(
-				&it, GIT_OBJ_COMMIT)) != NULL) {
+				else if (q_size == 0 || q == NULL ||
+						p->walk_commit->commit_object->commit_time >= 
+						q->walk_commit->commit_object->commit_time)
+					e = p, p = p->next, p_size--;
+
+				else
+					e = q, q = q->next, q_size--;
+
+				if (list->tail != NULL)
+					list->tail->next = e;
+				else
+					list->head = e;
+
+				e->prev = list->tail;
+				list->tail = e;
+			}
+
+			p = q;
+		}
+
+		list->tail->next = NULL;
+		in_size *= 2;
+
+	} while (merge_count > 1);
+}
+
+void git_revwalk_list_toposort(git_revwalk_list *list)
+{
+	git_revwalk_commit *commit;
+	git_revwalk_list topo;
+	memset(&topo, 0x0, sizeof(git_revwalk_list));
+
+	while ((commit = git_revwalk_list_pop_back(list)) != NULL) {
+		git_revwalk_listnode *p;
+
+		if (commit->in_degree > 0) {
+			commit->topo_delay = 1;
+			continue;
+		}
+
+		for (p = commit->parents.head; p != NULL; p = p->next) {
+			p->walk_commit->in_degree--;
+
+			if (p->walk_commit->in_degree == 0 && p->walk_commit->topo_delay) {
+				p->walk_commit->topo_delay = 0;
+				git_revwalk_list_push_back(list, p->walk_commit);
+			}
+		}
 
-		commit->seen = 0;
-		commit->topo_delay = 0;
-		commit->in_degree = 0;
+		git_revwalk_list_push_back(&topo, commit);
 	}
 
-	git_commit_list_clear(&pool->iterator, 0);
-	pool->walking = 0;
+	list->head = topo.head;
+	list->tail = topo.tail;
+	list->size = topo.size;
 }