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>
author: Vicent Marti <tanoku@gmail.com> 2010-08-08 14:12:17 +0200
committer: Vicent Marti <tanoku@gmail.com> 2010-08-12 18:48:55 +0200
commit: 3315782cb4f2b683c66a53c93aa81de501c5a4ab (patch)
tree: e3fa8b56dc17b749cc53520eb350cbcc46101007 /src
parent: f8758044876b30b0f6482d1fe8c3b1de743f4186 (diff)
download: libgit2-3315782cb4f2b683c66a53c93aa81de501c5a4ab.tar.gz
20 files changed, 871 insertions, 724 deletions
diff --git a/src/commit.c b/src/commit.c
index 4199e8e9c..1ffbc72ca 100644
--- a/src/commit.c
+++ b/src/commit.c
@@ -27,6 +27,7 @@
 #include "commit.h"
 #include "revwalk.h"
 #include "git/odb.h"
+#include "git/repository.h"
 
 #define COMMIT_PRINT(commit) {\
 	char oid[41]; oid[40] = 0;\
@@ -34,9 +35,23 @@
 	printf("Oid: %s | In degree: %d | Time: %u\n", oid, commit->in_degree, commit->commit_time);\
 }
 
+static void clear_parents(git_commit *commit)
+{
+	git_commit_parents *node, *next_node;
+
+	node = commit->parents;
+	while (node) {
+		next_node = node->next;
+		free(node);
+		node = next_node;
+	}
+
+	commit->parents = NULL;
+}
+
 void git_commit__free(git_commit *commit)
 {
-	git_commit_list_clear(&commit->parents, 0);
+	clear_parents(commit);
 
 	if (commit->odb_open)
 		git_obj_close(&commit->odb_object);
@@ -53,47 +68,12 @@ const git_oid *git_commit_id(git_commit *c)
 	return &c->object.id;
 }
 
-void git_commit__mark_uninteresting(git_commit *commit)
-{
-	git_commit_node *parents;
-
-	if (commit == NULL)
-		return;
-
-	parents = commit->parents.head;
-
-	commit->uninteresting = 1;
-
-	while (parents) {
-		parents->commit->uninteresting = 1;
-		parents = parents->next;
-	}
-}
-
-git_commit *git_commit_parse(git_revpool *pool, const git_oid *id)
-{
-	git_commit *commit = NULL;
-
-	if ((commit = git_commit_lookup(pool, id)) == NULL)
-		return NULL;
-
-	if (git_commit__parse_basic(commit) < 0)
-		goto error_cleanup;
-
-	return commit;
-
-error_cleanup:
-	/* FIXME: do not free; the commit is owned by the revpool */
-	free(commit);
-	return NULL;
-}
-
 int git_commit__parse(git_commit *commit, unsigned int parse_flags, int close_db_object)
 {
 	int error = 0;
 
 	if (!commit->odb_open) {
-		error = git_odb_read(&commit->odb_object, commit->object.pool->db, &commit->object.id);
+		error = git_odb_read(&commit->odb_object, commit->object.repo->db, &commit->object.id);
 		if (error < 0)
 			return error;
 
@@ -133,32 +113,9 @@ int git_commit__parse_basic(git_commit *commit)
 	return 0;
 }
 
-git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id)
+git_commit *git_commit_lookup(git_repository *repo, const git_oid *id)
 {
-	git_commit *commit = NULL;
-
-	if (pool == NULL)
-		return NULL;
-
-	commit = (git_commit *)git_revpool_table_lookup(pool->objects, id);
-	if (commit != NULL)
-		return commit;
-
-	commit = git__malloc(sizeof(git_commit));
-
-	if (commit == NULL)
-		return NULL;
-
-	memset(commit, 0x0, sizeof(git_commit));
-
-	/* Initialize parent object */
-	git_oid_cpy(&commit->object.id, id);
-	commit->object.pool = pool;
-	commit->object.type = GIT_OBJ_COMMIT;
-
-	git_revpool_table_insert(pool->objects, (git_revpool_object *)commit);
-
-	return commit;
+	return (git_commit *)git_repository_lookup(repo, id, GIT_OBJ_COMMIT);
 }
 
 int git__parse_person(git_person *person, char **buffer_out,
@@ -257,30 +214,31 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len, unsigne
 		return GIT_EOBJCORRUPTED;
 
 	if (parse_flags & GIT_COMMIT_TREE)
-		commit->tree = git_tree_lookup(commit->object.pool, &oid);
+		commit->tree = git_tree_lookup(commit->object.repo, &oid);
 
 	/*
 	 * TODO: commit grafts!
 	 */
 
 	if (parse_flags & GIT_COMMIT_PARENTS)
-		git_commit_list_clear(&commit->parents, 0);
+		clear_parents(commit);
 
 	while (git__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) {
 		git_commit *parent;
+		git_commit_parents *node;
 
 		if ((parse_flags & GIT_COMMIT_PARENTS) == 0)
 			continue;
 
-		if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL)
+		if ((parent = git_commit_lookup(commit->object.repo, &oid)) == NULL)
 			return GIT_ENOTFOUND;
 
-		/* Inherit uninteresting flag */
-		if (commit->uninteresting)
-			parent->uninteresting = 1;
-
-		if (git_commit_list_push_back(&commit->parents, parent) < 0)
+		if ((node = git__malloc(sizeof(git_commit_parents))) == NULL)
 			return GIT_ENOMEM;
+
+		node->commit = parent;
+		node->next = commit->parents;
+		commit->parents = node;
 	}
 
 	if (git__parse_person(&person, &buffer, buffer_end, "author ") < 0)
@@ -391,200 +349,3 @@ const char *git_commit_message_short(git_commit *commit)
 	git_commit__parse(commit, GIT_COMMIT_MESSAGE_SHORT, 0);
 	return commit->message_short;
 }
-
-
-
-int git_commit_list_push_back(git_commit_list *list, git_commit *commit)
-{
-	git_commit_node *node = NULL;
-
-	node = git__malloc(sizeof(git_commit_list));
-
-	if (node == NULL)
-		return GIT_ENOMEM;
-
-	node->commit = commit;
-	node->next = NULL;
-	node->prev = list->tail;
-
-	if (list->tail == NULL) {
-		list->head = list->tail = node;
-	} else {
-		list->tail->next = node;
-		list->tail = node;
-	}
-
-	list->size++;
-	return 0;
-}
-
-int git_commit_list_push_front(git_commit_list *list, git_commit *commit)
-{
-	git_commit_node *node = NULL;
-
-	node = git__malloc(sizeof(git_commit_list));
-
-	if (node == NULL)
-		return GIT_ENOMEM;
-
-	node->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;
-}
-
-
-git_commit *git_commit_list_pop_back(git_commit_list *list)
-{
-	git_commit_node *node;
-	git_commit *commit;
-
-	if (list->tail == NULL)
-		return NULL;
-
-	node = list->tail;
-	list->tail = list->tail->prev;
-	if (list->tail == NULL)
-		list->head = NULL;
-
-	commit = node->commit;
-	free(node);
-
-	list->size--;
-
-	return commit;
-}
-
-git_commit *git_commit_list_pop_front(git_commit_list *list)
-{
-	git_commit_node *node;
-	git_commit *commit;
-
-	if (list->head == NULL)
-		return NULL;
-
-	node = list->head;
-	list->head = list->head->next;
-	if (list->head == NULL)
-		list->tail = NULL;
-
-	commit = node->commit;
-	free(node);
-
-	list->size--;
-
-	return commit;
-}
-
-void git_commit_list_clear(git_commit_list *list, int free_commits)
-{
-	git_commit_node *node, *next_node;
-
-	node = list->head;
-	while (node) {
-		if (free_commits)
-			free(node->commit);
-
-		next_node = node->next;
-		free(node);
-		node = next_node;
-	}
-
-	list->head = list->tail = NULL;
-	list->size = 0;
-}
-
-void git_commit_list_timesort(git_commit_list *list)
-{
-	git_commit_node *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)) {
-
-				if (p_size == 0)
-					e = q, q = q->next, q_size--;
-
-				else if (q_size == 0 || q == NULL ||
-						p->commit->commit_time >= q->commit->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_commit_list_toposort(git_commit_list *list)
-{
-	git_commit *commit;
-	git_commit_list topo;
-	memset(&topo, 0x0, sizeof(git_commit_list));
-
-	while ((commit = git_commit_list_pop_back(list)) != NULL) {
-		git_commit_node *p;
-
-		if (commit->in_degree > 0) {
-			commit->topo_delay = 1;
-			continue;
-		}
-
-		for (p = commit->parents.head; p != NULL; p = p->next) {
-			p->commit->in_degree--;
-
-			if (p->commit->in_degree == 0 && p->commit->topo_delay) {
-				p->commit->topo_delay = 0;
-				git_commit_list_push_back(list, p->commit);
-			}
-		}
-
-		git_commit_list_push_back(&topo, commit);
-	}
-
-	list->head = topo.head;
-	list->tail = topo.tail;
-	list->size = topo.size;
-}
-
diff --git a/src/commit.h b/src/commit.h
index 028c83712..60e1d1115 100644
--- a/src/commit.h
+++ b/src/commit.h
@@ -3,26 +3,10 @@
 
 #include "git/commit.h"
 #include "tree.h"
-#include "revobject.h"
+#include "repository.h"
 
 #include <time.h>
 
-struct git_commit_node {
-	struct git_commit *commit;
-
-	struct git_commit_node *next;
-	struct git_commit_node *prev;
-};
-
-struct git_commit_list {
-	struct git_commit_node *head;
-	struct git_commit_node *tail;
-	size_t size;
-};
-
-typedef struct git_commit_list git_commit_list;
-typedef struct git_commit_node git_commit_node;
-
 #define GIT_COMMIT_TREE		(1 << 1)
 #define GIT_COMMIT_PARENTS	(1 << 2)
 #define GIT_COMMIT_AUTHOR	(1 << 3)
@@ -32,12 +16,17 @@ typedef struct git_commit_node git_commit_node;
 #define GIT_COMMIT_MESSAGE_SHORT (1 << 7)
 #define GIT_COMMIT_FOOTERS	(1 << 8)
 
+typedef struct git_commit_parents {
+	git_commit *commit;
+	struct git_commit_parents *next;
+} git_commit_parents;
+
 struct git_commit {
-	git_revpool_object object;
+	git_repository_object object;
 	git_obj odb_object;
 
 	time_t commit_time;
-	git_commit_list parents;
+	git_commit_parents *parents;
 
 	git_tree *tree;
 	git_person *author;
@@ -46,13 +35,8 @@ struct git_commit {
 	char *message;
 	char *message_short;
 
-	unsigned short in_degree;
 	unsigned basic_parse:1,
-			 odb_open:1,
-			 seen:1,
-			 uninteresting:1,
-			 topo_delay:1,
-			 flags:25;
+			 odb_open:1;
 };
 
 void git_commit__free(git_commit *c);
@@ -64,15 +48,5 @@ void git_commit__mark_uninteresting(git_commit *commit);
 int git__parse_oid(git_oid *oid, char **buffer_out, const char *buffer_end, const char *header);
 int git__parse_person(git_person *person, char **buffer_out, const char *buffer_end, const char *header);
 
-int git_commit_list_push_back(git_commit_list *list, git_commit *commit);
-int git_commit_list_push_front(git_commit_list *list, git_commit *commit);
-
-git_commit *git_commit_list_pop_back(git_commit_list *list);
-git_commit *git_commit_list_pop_front(git_commit_list *list);
-
-void git_commit_list_clear(git_commit_list *list, int free_commits);
-
-void git_commit_list_timesort(git_commit_list *list);
-void git_commit_list_toposort(git_commit_list *list);
 
 #endif
diff --git a/src/git/commit.h b/src/git/commit.h
index 89f0929c9..56243c5be 100644
--- a/src/git/commit.h
+++ b/src/git/commit.h
@@ -4,6 +4,7 @@
 #include "common.h"
 #include "oid.h"
 #include "tree.h"
+#include "repository.h"
 
 /**
  * @file git/commit.h
@@ -18,31 +19,16 @@ GIT_BEGIN_DECL
 typedef struct git_commit git_commit;
 
 /**
- * Locate a reference to a commit without loading it.
+ * Lookup a commit object from a repository.
  * The generated commit object is owned by the revision
- * pool and shall not be freed by the user.
+ * repo and shall not be freed by the user.
  *
- * @param pool the pool to use when locating the commit.
+ * @param repo the repo to use when locating the commit.
  * @param id identity of the commit to locate.  If the object is
  *        an annotated tag it will be peeled back to the commit.
  * @return the commit; NULL if the commit could not be created
  */
-GIT_EXTERN(git_commit *) git_commit_lookup(git_revpool *pool, const git_oid *id);
-
-/**
- * Locate a reference to a commit, and try to load and parse it it from
- * the commit cache or the object database.
- * The generated commit object is owned by the revision
- * pool and shall not be freed by the user.
- *
- * @param pool the pool to use when parsing/caching the commit.
- * @param id identity of the commit to locate.  If the object is
- *        an annotated tag it will be peeled back to the commit.
- * @return the commit; NULL if the commit does not exist in the
- *         pool's git_odb, or if the commit is present but is
- *         too malformed to be parsed successfully.
- */
-GIT_EXTERN(git_commit *) git_commit_parse(git_revpool *pool, const git_oid *id);
+GIT_EXTERN(git_commit *) git_commit_lookup(git_repository *repo, const git_oid *id);
 
 /**
  * Get the id of a commit.
diff --git a/src/git/common.h b/src/git/common.h
index 09972aade..b43f4ee01 100644
--- a/src/git/common.h
+++ b/src/git/common.h
@@ -85,8 +85,14 @@
 
 GIT_BEGIN_DECL
 
-/** A revision traversal pool. */
-typedef struct git_revpool git_revpool;
+/** 
+ * Representation of an existing git repository,
+ * including all its object contents 
+ */
+typedef struct git_repository git_repository;
+
+/* Representation of a generic object in a repository */
+typedef struct git_repository_object git_repository_object;
 
 /** Parsed representation of a person */
 typedef struct git_person {
diff --git a/src/git/odb.h b/src/git/odb.h
index 58b932645..5d105ba70 100644
--- a/src/git/odb.h
+++ b/src/git/odb.h
@@ -35,6 +35,7 @@ GIT_EXTERN(void) git_odb_close(git_odb *db);
 
 /** Basic type (loose or packed) of any Git object. */
 typedef enum {
+	GIT_OBJ_ANY = -2,		/**< Object can be any of the following */
 	GIT_OBJ_BAD = -1,       /**< Object is invalid. */
 	GIT_OBJ__EXT1 = 0,      /**< Reserved for future use. */
 	GIT_OBJ_COMMIT = 1,     /**< A commit object. */
diff --git a/src/git/repository.h b/src/git/repository.h
new file mode 100644
index 000000000..3b6981d50
--- /dev/null
+++ b/src/git/repository.h
@@ -0,0 +1,60 @@
+#ifndef INCLUDE_git_repository_h__
+#define INCLUDE_git_repository_h__
+
+#include "common.h"
+#include "odb.h"
+#include "commit.h"
+
+/**
+ * @file git/repository.h
+ * @brief Git revision object management routines
+ * @defgroup git_repository Git revision object management routines
+ * @ingroup Git
+ * @{
+ */
+GIT_BEGIN_DECL
+
+/**
+ * Allocate a new repository object.
+ *
+ * TODO: specify the repository's path instead
+ * of its object database
+ *
+ * @param odb an existing object database to back the repo
+ * @return the new repository handle; NULL on error 
+ */
+GIT_EXTERN(git_repository *) git_repository_alloc(git_odb *odb);
+
+
+/**
+ * Lookup a reference to one of the objects in the repostory.
+ * 
+ * The generated reference is owned by the repository and
+ * should not be freed by the user.
+ * The generated reference should be cast back to the
+ * expected type; e.g.
+ *
+ *	git_commit *c = (git_commit *)
+ *		git_repository_lookup(repo, id, GIT_OBJ_COMMIT);
+ *
+ * The 'type' parameter must match the type of the object
+ * in the odb; the method will fail otherwise.
+ * The special value 'GIT_OBJ_ANY' may be passed to let
+ * the method guess the object's type.
+ *
+ * @param repo the repository to look up the object
+ * @param id the unique identifier for the object
+ * @param type the type of the object
+ * @return a reference to the object
+ */
+GIT_EXTERN(git_repository_object *) git_repository_lookup(git_repository *repo, const git_oid *id, git_otype type);
+
+/**
+ * Free a previously allocated repository
+ * @param repo repository handle to close. If NULL nothing occurs.
+ */
+GIT_EXTERN(void) git_repository_free(git_repository *repo);
+
+/** @} */
+GIT_END_DECL
+#endif
diff --git a/src/git/revwalk.h b/src/git/revwalk.h
index 7aa92d44a..842503dea 100644
--- a/src/git/revwalk.h
+++ b/src/git/revwalk.h
@@ -15,87 +15,87 @@
 GIT_BEGIN_DECL
 
 /**
- * Sort the revpool contents in no particular ordering;
+ * Sort the repository contents in no particular ordering;
  * this sorting is arbritary, implementation-specific
  * and subject to change at any time.
- * This is the default sorting for new revision pools.
+ * This is the default sorting for new walkers.
  */
-#define GIT_RPSORT_NONE         (0)
+#define GIT_SORT_NONE         (0)
 
 /**
- * Sort the revpool contents in topological order
+ * Sort the repository contents in topological order
  * (parents before children); this sorting mode
  * can be combined with time sorting.
  */
-#define GIT_RPSORT_TOPOLOGICAL  (1 << 0)
+#define GIT_SORT_TOPOLOGICAL  (1 << 0)
 
 /**
- * Sort the revpool contents by commit time;
+ * Sort the repository contents by commit time;
  * this sorting mode can be combined with
  * topological sorting.
  */
-#define GIT_RPSORT_TIME         (1 << 1)
+#define GIT_SORT_TIME         (1 << 1)
 
 /**
- * Iterate through the revpool contents in reverse
+ * Iterate through the repository contents in reverse
  * order; this sorting mode can be combined with
  * any of the above.
  */
-#define GIT_RPSORT_REVERSE      (1 << 2)
+#define GIT_SORT_REVERSE      (1 << 2)
+
+typedef struct git_revwalk git_revwalk;
 
 /**
- * Allocate a new revision traversal pool.
- *
- * The configuration is copied during allocation.  Changes
- * to the configuration after allocation do not affect the pool
- * returned by this function.  Callers may safely free the
- * passed configuration after the function completes.
+ * Allocate a new revision walker to iterate through a repo.
  *
- * @param db the database objects are read from.
- * @return the new traversal handle; NULL if memory is exhausted.
+ * @param repo the repo to walk through
+ * @return the new walker handle; NULL if memory is exhausted.
  */
-GIT_EXTERN(git_revpool *) gitrp_alloc(git_odb *db);
+GIT_EXTERN(git_revwalk *) git_revwalk_alloc(git_repository *repo);
 
 /**
- * Reset the traversal machinary for reuse.
- * @param pool traversal handle to reset.
+ * Reset the walking machinary for reuse.
+ * @param walker handle to reset.
  */
-GIT_EXTERN(void) gitrp_reset(git_revpool *pool);
+GIT_EXTERN(void) git_revwalk_reset(git_revwalk *walker);
 
 /**
- * Mark an object to start traversal from.
- * @param pool the pool being used for the traversal.
+ * Mark a commit to start traversal from.
+ * The commit object must belong to the repo which is being walked through.
+ *
+ * @param walker the walker being used for the traversal.
  * @param commit the commit to start from.
  */
-GIT_EXTERN(int) gitrp_push(git_revpool *pool, git_commit *commit);
+GIT_EXTERN(int) git_revwalk_push(git_revwalk *walk, git_commit *commit);
 
 /**
  * Mark a commit (and its ancestors) uninteresting for the output.
- * @param pool the pool being used for the traversal.
+ * @param walker the walker being used for the traversal.
  * @param commit the commit that will be ignored during the traversal
  */
-GIT_EXTERN(int) gitrp_hide(git_revpool *pool, git_commit *commit);
+GIT_EXTERN(int) git_revwalk_hide(git_revwalk *walk, git_commit *commit);
 
 /**
  * Get the next commit from the revision traversal.
- * @param pool the pool to pop the commit from.
+ * @param walk the walker to pop the commit from.
  * @return next commit; NULL if there is no more output.
  */
-GIT_EXTERN(git_commit *) gitrp_next(git_revpool *pool);
+GIT_EXTERN(git_commit *) git_revwalk_next(git_revwalk *walk);
 
 /**
  * Change the sorting mode when iterating through the
- * revision pool's contents.
- * @param pool the pool being used for the traversal.
+ * repository's contents.
+ * Changing the sorting mode resets the walker.
+ * @param walk the walker being used for the traversal.
  * @param sort_mode combination of GIT_RPSORT_XXX flags
  */
-GIT_EXTERN(void) gitrp_sorting(git_revpool *pool, unsigned int sort_mode);
+GIT_EXTERN(void) git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode);
 
 /**
  * Free a revwalk previously allocated.
- * @param pool traversal handle to close.  If NULL nothing occurs.
+ * @param walk traversal handle to close.  If NULL nothing occurs.
  */
-GIT_EXTERN(void) gitrp_free(git_revpool *pool);
+GIT_EXTERN(void) git_revwalk_free(git_revwalk *walk);
 
 /** @} */
 GIT_END_DECL
diff --git a/src/git/tag.h b/src/git/tag.h
index 509d2f047..d94083b11 100644
--- a/src/git/tag.h
+++ b/src/git/tag.h
@@ -4,6 +4,7 @@
 #include "common.h"
 #include "oid.h"
 #include "tree.h"
+#include "repository.h"
 
 /**
  * @file git/tag.h
@@ -18,29 +19,15 @@ GIT_BEGIN_DECL
 typedef struct git_tag git_tag;
 
 /**
- * Locate a reference to a tag without loading it.
+ * Lookup a tag object from the repository.
  * The generated tag object is owned by the revision
- * pool and shall not be freed by the user.
+ * repo and shall not be freed by the user.
  *
- * @param pool the pool to use when locating the tag.
+ * @param repo the repo to use when locating the tag.
  * @param id identity of the tag to locate.
  * @return the tag; NULL if the tag could not be created
  */
-GIT_EXTERN(git_tag *) git_tag_lookup(git_revpool *pool, const git_oid *id);
-
-/**
- * Locate a reference to a tag, and try to load and parse it it from
- * the object cache or the object database.
- * The generated tag object is owned by the revision
- * pool and shall not be freed by the user.
- *
- * @param pool the pool to use when parsing/caching the tag.
- * @param id identity of the tag to locate.  
- * @return the tag; NULL if the tag does not exist in the
- *         pool's git_odb, or if the tag is present but is
- *         too malformed to be parsed successfully.
- */
-GIT_EXTERN(git_tag *) git_tag_parse(git_revpool *pool, const git_oid *id);
+GIT_EXTERN(git_tag *) git_tag_lookup(git_repository *repo, const git_oid *id);
 
 /**
  * Get the id of a tag.
diff --git a/src/git/tree.h b/src/git/tree.h
index 9a4973ba6..95b233009 100644
--- a/src/git/tree.h
+++ b/src/git/tree.h
@@ -3,6 +3,7 @@
 
 #include "common.h"
 #include "oid.h"
+#include "repository.h"
 
 /**
  * @file git/tree.h
@@ -17,27 +18,15 @@ GIT_BEGIN_DECL
 typedef struct git_tree git_tree;
 
 /**
- * Locate a reference to a tree without loading it.
+ * Lookup a tree object from the repository.
  * The generated tree object is owned by the revision
- * pool and shall not be freed by the user.
+ * repo and shall not be freed by the user.
  *
- * @param pool the pool to use when locating the tree.
+ * @param repo the repo to use when locating the tree.
  * @param id identity of the tree to locate.
  * @return the tree; NULL if the tree could not be created
  */
-GIT_EXTERN(git_tree *) git_tree_lookup(git_revpool *pool, const git_oid *id);
-
-/**
- * Locate a reference to a tree object and parse its
- * contents.
- * The generated tree object is owned by the revision
- * pool and shall not be freed by the user.
- *
- * @param pool the pool to use when locating the tree.
- * @param id identity of the tree to locate.
- * @return the tree; NULL if the tree could not be created
- */
-GIT_EXTERN(git_tree *) git_tree_parse(git_revpool *pool, const git_oid *id);
+GIT_EXTERN(git_tree *) git_tree_lookup(git_repository *repo, const git_oid *id);
 
 /**
  * Get the id of a tree.
diff --git a/src/revobject.c b/src/hashtable.c
index 47d75e047..4006a8714 100644
--- a/src/revobject.c
+++ b/src/hashtable.c
@@ -24,25 +24,55 @@
  */
 
 #include "common.h"
-#include "revobject.h"
+#include "repository.h"
+#include "commit.h"
 
+static const int default_table_size = 32;
 static const double max_load_factor = 0.65;
 
-static unsigned int git_revpool_table__hash(const git_oid *id)
+static void hashtable_resize(git_hashtable *table)
 {
-	unsigned int r;
-	memcpy(&r, id->id, sizeof(r));
-	return r;
+	git_hashtable_node **new_nodes;
+	unsigned int new_size, i;
+
+	assert(table);
+
+	new_size = (table->size_mask + 1) * 2;
+
+	new_nodes = git__malloc(new_size * sizeof(git_hashtable_node *));
+	if (new_nodes == NULL)
+		return;
+
+	memset(new_nodes, 0x0, new_size * sizeof(git_hashtable_node *));
+
+	for (i = 0; i <= table->size_mask; ++i) {
+		git_hashtable_node *n;
+		unsigned int index;
+
+		while ((n = table->nodes[i]) != NULL) {
+			table->nodes[i] = n->next;
+			index = n->hash & (new_size - 1);
+			n->next = new_nodes[index];
+			new_nodes[index] = n;
+		}
+	}
+
+	free(table->nodes);
+	table->nodes = new_nodes;
+	table->size_mask = (new_size - 1);
+	table->max_count = (unsigned int)(new_size * max_load_factor);
 }
 
-git_revpool_table *git_revpool_table_create(unsigned int min_size)
+git_hashtable *git_hashtable_alloc(unsigned int min_size, 
+		git_hash_ptr hash,
+		git_hash_keyeq_ptr key_eq)
 {
-	git_revpool_table *table;
 	unsigned int i;
+	git_hashtable *table;
 
-	table = git__malloc(sizeof(*table));
+	assert(hash && key_eq);
 
-	if (table == NULL)
+	if ((table = git__malloc(sizeof(git_hashtable))) == NULL)
 		return NULL;
 
 	/* round up size to closest power of 2 */
@@ -57,7 +87,10 @@ git_revpool_table *git_revpool_table_create(unsigned int min_size)
 	table->count = 0;
 	table->max_count = (unsigned int)((min_size + 1) * max_load_factor);
 
-	table->nodes = git__malloc((min_size + 1) * sizeof(git_revpool_node *));
+	table->hash = hash;
+	table->key_equal = key_eq;
+
+	table->nodes = git__malloc((min_size + 1) * sizeof(git_hashtable_node *));
 
 	if (table->nodes == NULL) {
 		free(table);
@@ -70,48 +103,78 @@ git_revpool_table *git_revpool_table_create(unsigned int min_size)
 	return table;
 }
 
-int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object)
+void git_hashtable_clear(git_hashtable *table)
 {
-	git_revpool_node *node;
-	unsigned int index, hash;
+	unsigned int index;
+
+	assert(table);
+
+	for (index = 0; index <= table->size_mask; ++index) {
+		git_hashtable_node *node, *next_node;
+
+		node = table->nodes[index];
+		while (node != NULL) {
+			next_node = node->next;
+			free(node);
+			node = next_node;
+		}
+
+		table->nodes[index] = NULL;
+	}
+
+	table->count = 0;
+}
+
+void git_hashtable_free(git_hashtable *table)
+{
+	assert(table);
 
-	if (table == NULL)
-		return GIT_ERROR;
+	git_hashtable_clear(table);
+	free(table->nodes);
+	free(table);
+}
+
+
+int git_hashtable_insert(git_hashtable *table, const void *key, void *value)
+{
+	git_hashtable_node *node;
+	uint32_t index, hash;
+
+	assert(table);
 
 	if (table->count + 1 > table->max_count)
-		git_revpool_table_resize(table);
+		hashtable_resize(table);
 
-	node = git__malloc(sizeof(git_revpool_node));
+	node = git__malloc(sizeof(git_hashtable_node));
 	if (node == NULL)
 		return GIT_ENOMEM;
 
-	hash = git_revpool_table__hash(&object->id);
+	hash = table->hash(key);
 	index = (hash & table->size_mask);
 
-	node->object = object;
+	node->object = value;
 	node->hash = hash;
 	node->next = table->nodes[index];
 
 	table->nodes[index] = node;
 	table->count++;
 
-	return 0;
+	return GIT_SUCCESS;
 }
 
-git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id)
+void *git_hashtable_lookup(git_hashtable *table, const void *key)
 {
-	git_revpool_node *node;
-	unsigned int index, hash;
+	git_hashtable_node *node;
+	uint32_t index, hash;
 
-	if (table == NULL)
-		return NULL;
+	assert(table);
 
-	hash = git_revpool_table__hash(id);
+	hash = table->hash(key);
 	index = (hash & table->size_mask);
 	node = table->nodes[index];
 
 	while (node != NULL) {
-		if (node->hash == hash && git_oid_cmp(id, &node->object->id) == 0)
+		if (node->hash == hash && table->key_equal(node->object, key))
 			return node->object;
 
 		node = node->next;
@@ -120,60 +183,13 @@ git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git
 	return NULL;
 }
 
-void git_revpool_table_resize(git_revpool_table *table)
-{
-	git_revpool_node **new_nodes;
-	unsigned int new_size, i;
-
-	new_size = (table->size_mask + 1) * 2;
-
-	new_nodes = git__malloc(new_size * sizeof(git_revpool_node *));
-	if (new_nodes == NULL)
-		return;
-
-	memset(new_nodes, 0x0, new_size * sizeof(git_revpool_node *));
-
-	for (i = 0; i <= table->size_mask; ++i) {
-		git_revpool_node *n;
-		unsigned int index;
-
-		while ((n = table->nodes[i]) != NULL) {
-			table->nodes[i] = n->next;
-			index = n->hash & (new_size - 1);
-			n->next = new_nodes[index];
-			new_nodes[index] = n;
-		}
-	}
-
-	free(table->nodes);
-	table->nodes = new_nodes;
-	table->size_mask = (new_size - 1);
-	table->max_count = (unsigned int)(new_size * max_load_factor);
-}
 
 
-void git_revpool_table_free(git_revpool_table *table)
+void git_hashtable_iterator_init(git_hashtable *table, git_hashtable_iterator *it)
 {
-	unsigned int index;
-
-	for (index = 0; index <= table->size_mask; ++index) {
-		git_revpool_node *node, *next_node;
-
-		node = table->nodes[index];
-		while (node != NULL) {
-			next_node = node->next;
-			free(node);
-			node = next_node;
-		}
-	}
-
-	free(table->nodes);
-	free(table);
-}
+	assert(table && it);
 
-void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it)
-{
-	memset(it, 0x0, sizeof(git_revpool_tableit));
+	memset(it, 0x0, sizeof(git_hashtable_iterator));
 
 	it->nodes = table->nodes;
 	it->current_node = NULL;
@@ -181,9 +197,11 @@ void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it)
 	it->size = table->size_mask + 1;
 }
 
-git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it)
+void *git_hashtable_iterator_next(git_hashtable_iterator *it)
 {
-	git_revpool_node *next = NULL;
+	git_hashtable_node *next = NULL;
+
+	assert(it);
 
 	while (it->current_node == NULL) {
 		if (it->current_pos >= it->size)
@@ -198,13 +216,3 @@ git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it)
 	return next->object;
 }
 
-git_revpool_object *git_revpool_tableit_nextfilter(git_revpool_tableit *it, git_otype type)
-{
-	git_revpool_object *obj;
-
-	do {
-		obj = git_revpool_tableit_next(it);
-	} while (obj != NULL && obj->type != type);
-
-	return obj;
-}
diff --git a/src/hashtable.h b/src/hashtable.h
new file mode 100644
index 000000000..622a260e1
--- /dev/null
+++ b/src/hashtable.h
@@ -0,0 +1,51 @@
+#ifndef INCLUDE_hashtable_h__
+#define INCLUDE_hashtable_h__
+
+#include "git/common.h"
+#include "git/oid.h"
+#include "git/odb.h"
+
+
+typedef uint32_t (*git_hash_ptr)(const void *);
+typedef int (*git_hash_keyeq_ptr)(void *obj, const void *obj_key);
+
+struct git_hashtable_node {
+	void *object;
+	uint32_t hash;
+	struct git_hashtable_node *next;
+};
+
+struct git_hashtable {
+	struct git_hashtable_node **nodes;
+
+	unsigned int size_mask;
+	unsigned int count;
+	unsigned int max_count;
+
+	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_hash_ptr hash,
+		git_hash_keyeq_ptr key_eq);
+int git_hashtable_insert(git_hashtable *h, const void *key, void *value);
+void *git_hashtable_lookup(git_hashtable *h, 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);
+
+#endif
diff --git a/src/repository.c b/src/repository.c
new file mode 100644
index 000000000..dd5b5f70f
--- /dev/null
+++ b/src/repository.c
@@ -0,0 +1,143 @@
+/*
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License, version 2,
+ * as published by the Free Software Foundation.
+ *
+ * In addition to the permissions in the GNU General Public License,
+ * the authors give you unlimited permission to link the compiled
+ * version of this file into combinations with other programs,
+ * and to distribute those combinations without any restriction
+ * coming from the use of this file.  (The General Public License
+ * restrictions do apply in other respects; for example, they cover
+ * modification of the file, and distribution when not linked into
+ * a combined executable.)
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; see the file COPYING.  If not, write to
+ * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include "common.h"
+#include "repository.h"
+#include "commit.h"
+#include "tag.h"
+
+static const int default_table_size = 32;
+static const double max_load_factor = 0.65;
+
+uint32_t git_repository_object_hash(const void *key)
+{
+	uint32_t r;
+	git_oid *id;
+
+	id = (git_oid *)key;
+	memcpy(&r, id->id, sizeof(r));
+	return r;
+}
+
+int git_repository_object_haskey(void *object, const void *key)
+{
+	git_repository_object *obj;
+	git_oid *oid;
+
+	obj = (git_repository_object *)object;
+	oid = (git_oid *)key;
+
+	return (git_oid_cmp(oid, &obj->id) == 0);
+}
+
+git_repository *git_repository_alloc(git_odb *odb)
+{
+	git_repository *repo = git__malloc(sizeof(git_repository));
+	if (!repo)
+		return NULL;
+
+	memset(repo, 0x0, sizeof(git_repository));
+
+	repo->objects = git_hashtable_alloc(
+			default_table_size, 
+			git_repository_object_hash,
+			git_repository_object_haskey);
+
+	if (repo->objects == NULL) {
+		free(repo);
+		return NULL;
+	}
+
+	repo->db = odb; /* TODO: create ODB manually! */
+
+	return repo;
+}
+
+void git_repository_free(git_repository *repo)
+{
+	git_hashtable_iterator it;
+	git_repository_object *object;
+
+	git_hashtable_iterator_init(repo->objects, &it);
+
+	while ((object = (git_repository_object *)
+				git_hashtable_iterator_next(&it)) != NULL) {
+	
+		switch (object->type) {
+		case GIT_OBJ_COMMIT:
+			git_commit__free((git_commit *)object);
+			break;
+
+		case GIT_OBJ_TREE:
+			git_tree__free((git_tree *)object);
+			break;
+
+		case GIT_OBJ_TAG:
+			git_tag__free((git_tag *)object);
+			break;
+
+		default:
+			free(object);
+			break;
+		}
+	}
+
+	git_hashtable_free(repo->objects);
+	/* TODO: free odb */
+	free(repo);
+}
+
+git_repository_object *git_repository_lookup(git_repository *repo, const git_oid *id, git_otype type)
+{
+	git_repository_object *object = NULL;
+	git_obj obj_file;
+
+	assert(repo);
+
+	object = git_hashtable_lookup(repo->objects, id);
+	if (object != NULL)
+		return object;
+
+	if (git_odb_read(&obj_file, repo->db, id) < 0 ||
+		(type != GIT_OBJ_ANY && type != obj_file.type))
+		return NULL;
+
+	object = git__malloc(sizeof(git_commit));
+
+	if (object == NULL)
+		return NULL;
+
+	memset(object, 0x0, sizeof(git_commit));
+
+	/* Initialize parent object */
+	git_oid_cpy(&object->id, id);
+	object->repo = repo;
+	object->type = obj_file.type;
+
+	git_hashtable_insert(repo->objects, &object->id, object);
+	git_obj_close(&obj_file);
+
+	return object;
+}
diff --git a/src/repository.h b/src/repository.h
new file mode 100644
index 000000000..5db598765
--- /dev/null
+++ b/src/repository.h
@@ -0,0 +1,25 @@
+#ifndef INCLUDE_repository_h__
+#define INCLUDE_repository_h__
+
+#include "git/common.h"
+#include "git/oid.h"
+#include "git/odb.h"
+#include "git/repository.h"
+
+#include "hashtable.h"
+
+struct git_repository_object {
+	git_oid id;
+	git_repository *repo;
+	git_otype type;
+};
+
+struct git_repository {
+	git_odb *db;
+	git_hashtable *objects;
+};
+
+int git_repository__insert(git_repository *repo, git_repository_object *obj);
+git_repository_object *git_repository__lookup(git_repository *repo, const git_oid *id);
+
+#endif
diff --git a/src/revobject.h b/src/revobject.h
deleted file mode 100644
index d76d8a639..000000000
--- a/src/revobject.h
+++ /dev/null
@@ -1,52 +0,0 @@
-#ifndef INCLUDE_objecttable_h__
-#define INCLUDE_objecttable_h__
-
-#include "git/common.h"
-#include "git/oid.h"
-#include "git/odb.h"
-
-struct git_revpool_object {
-	git_oid id;
-	git_revpool *pool;
-	git_otype type;
-};
-
-struct git_revpool_node {
-	struct git_revpool_object *object;
-	unsigned int hash;
-	struct git_revpool_node *next;
-};
-
-struct git_revpool_table {
-	struct git_revpool_node **nodes;
-
-	unsigned int size_mask;
-	unsigned int count;
-	unsigned int max_count;
-};
-
-struct git_revpool_tableit {
-	struct git_revpool_node **nodes;
-	struct git_revpool_node *current_node;
-	unsigned int current_pos;
-	unsigned int size;
-};
-
-
-typedef struct git_revpool_node git_revpool_node;
-typedef struct git_revpool_object git_revpool_object;
-typedef struct git_revpool_table git_revpool_table;
-typedef struct git_revpool_tableit git_revpool_tableit;
-
-git_revpool_table *git_revpool_table_create(unsigned int min_size);
-int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object);
-git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id);
-void git_revpool_table_resize(git_revpool_table *table);
-void git_revpool_table_free(git_revpool_table *table);
-
-
-git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it);
-git_revpool_object *git_revpool_tableit_nextfilter(git_revpool_tableit *it, git_otype type);
-void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it);
-
-#endif
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;
 }
 
diff --git a/src/revwalk.h b/src/revwalk.h
index 270eb8c6b..d97e5ce8c 100644
--- a/src/revwalk.h
+++ b/src/revwalk.h
@@ -5,21 +5,63 @@
 #include "git/revwalk.h"
 
 #include "commit.h"
+#include "repository.h"
+#include "hashtable.h"
 
-struct git_revpool {
-	git_odb *db;
+struct git_revwalk_commit;
 
-	git_commit_list iterator;
-	git_commit *(*next_commit)(git_commit_list *);
+typedef struct git_revwalk_listnode {
+	struct git_revwalk_commit *walk_commit;
+	struct git_revwalk_listnode *next;
+	struct git_revwalk_listnode *prev;
+} git_revwalk_listnode;
 
-	git_commit_list roots;
-	git_revpool_table *objects;
+typedef struct git_revwalk_list {
+	struct git_revwalk_listnode *head;
+	struct git_revwalk_listnode *tail;
+	size_t size;
+} git_revwalk_list;
+
+
+struct git_revwalk_commit {
+
+	git_commit *commit_object;
+	git_revwalk_list parents;
+
+	unsigned short in_degree;
+	unsigned seen:1,
+			 uninteresting:1,
+			 topo_delay:1,
+			 flags:25;
+};
+
+typedef struct git_revwalk_commit git_revwalk_commit;
+
+struct git_revwalk {
+	git_repository *repo;
+
+	git_hashtable *commits;
+	git_revwalk_list iterator;
+
+	git_revwalk_commit *(*next)(git_revwalk_list *);
 
 	unsigned walking:1;
 	unsigned int sorting;
 };
 
-void gitrp__prepare_walk(git_revpool *pool);
-int gitrp__enroot(git_revpool *pool, git_commit *commit);
+
+void git_revwalk__prepare_walk(git_revwalk *walk);
+int git_revwalk__enroot(git_revwalk *walk, git_commit *commit);
+
+int git_revwalk_list_push_back(git_revwalk_list *list, git_revwalk_commit *commit);
+int git_revwalk_list_push_front(git_revwalk_list *list, git_revwalk_commit *obj);
+
+git_revwalk_commit *git_revwalk_list_pop_back(git_revwalk_list *list);
+git_revwalk_commit *git_revwalk_list_pop_front(git_revwalk_list *list);
+
+void git_revwalk_list_clear(git_revwalk_list *list);
+
+void git_revwalk_list_timesort(git_revwalk_list *list);
+void git_revwalk_list_toposort(git_revwalk_list *list);
 
 #endif /* INCLUDE_revwalk_h__ */
diff --git a/src/tag.c b/src/tag.c
index 803cfa13c..ea2e4e7b3 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -28,7 +28,7 @@
 #include "tag.h"
 #include "revwalk.h"
 #include "git/odb.h"
-
+#include "git/repository.h"
 
 void git_tag__free(git_tag *tag)
 {
@@ -43,7 +43,7 @@ const git_oid *git_tag_id(git_tag *t)
 	return &t->object.id;
 }
 
-const git_revpool_object *git_tag_target(git_tag *t)
+const git_repository_object *git_tag_target(git_tag *t)
 {
 	if (t->target)
 		return t->target;
@@ -183,7 +183,7 @@ int git_tag__parse(git_tag *tag)
 	int error = 0;
 	git_obj odb_object;
 
-	error = git_odb_read(&odb_object, tag->object.pool->db, &tag->object.id);
+	error = git_odb_read(&odb_object, tag->object.repo->db, &tag->object.id);
 	if (error < 0)
 		return error;
 
@@ -199,30 +199,7 @@ cleanup:
 	return error;
 }
 
-git_tag *git_tag_lookup(git_revpool *pool, const git_oid *id)
+git_tag *git_tag_lookup(git_repository *repo, const git_oid *id)
 {
-	git_tag *tag = NULL;
-
-	if (pool == NULL)
-		return NULL;
-
-	tag = (git_tag *)git_revpool_table_lookup(pool->objects, id);
-	if (tag != NULL)
-		return tag;
-
-	tag = git__malloc(sizeof(git_tag));
-
-	if (tag == NULL)
-		return NULL;
-
-	memset(tag, 0x0, sizeof(git_tag));
-
-	/* Initialize parent object */
-	git_oid_cpy(&tag->object.id, id);
-	tag->object.pool = pool;
-	tag->object.type = GIT_OBJ_TAG;
-
-	git_revpool_table_insert(pool->objects, (git_revpool_object *)tag);
-
-	return tag;
+	return (git_tag *)git_repository_lookup(repo, id, GIT_OBJ_TAG);
 }
diff --git a/src/tag.h b/src/tag.h
index 5b1f5e2b9..df03e2ad1 100644
--- a/src/tag.h
+++ b/src/tag.h
@@ -2,12 +2,12 @@
 #define INCLUDE_tag_h__
 
 #include "git/tag.h"
-#include "revobject.h"
+#include "repository.h"
 
 struct git_tag {
-	git_revpool_object object;
+	git_repository_object object;
 
-	git_revpool_object *target;
+	git_repository_object *target;
 	git_otype type;
 	char *tag_name;
 	git_person *tagger;
diff --git a/src/tree.c b/src/tree.c
index 47b027322..15603e7a9 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -27,6 +27,7 @@
 #include "commit.h"
 #include "revwalk.h"
 #include "tree.h"
+#include "git/repository.h"
 
 void git_tree__free(git_tree *tree)
 {
@@ -38,51 +39,9 @@ const git_oid *git_tree_id(git_tree *tree)
 	return &tree->object.id;
 }
 
-git_tree *git_tree_lookup(git_revpool *pool, const git_oid *id)
+git_tree *git_tree_lookup(git_repository *repo, const git_oid *id)
 {
-	git_tree *tree = NULL;
-
-	if (pool == NULL)
-		return NULL;
-
-	tree = (git_tree *)git_revpool_table_lookup(pool->objects, id);
-	if (tree != NULL)
-		return tree;
-
-	tree = git__malloc(sizeof(git_tree));
-
-	if (tree == NULL)
-		return NULL;
-
-	memset(tree, 0x0, sizeof(git_tree));
-
-	/* Initialize parent object */
-	git_oid_cpy(&tree->object.id, id);
-	tree->object.pool = pool;
-	tree->object.type = GIT_OBJ_TREE;
-
-	git_revpool_table_insert(pool->objects, (git_revpool_object *)tree);
-
-	return tree;
-}
-
-
-git_tree *git_tree_parse(git_revpool *pool, const git_oid *id)
-{
-	git_tree *tree = NULL;
-
-	if ((tree = git_tree_lookup(pool, id)) == NULL)
-		return NULL;
-
-	if (git_tree__parse(tree) < 0)
-		goto error_cleanup;
-
-	return tree;
-
-error_cleanup:
-	/* FIXME: do not free; the tree is owned by the revpool */
-	free(tree);
-	return NULL;
+	return (git_tree *)git_repository_lookup(repo, id, GIT_OBJ_TREE);
 }
 
 int git_tree__parse(git_tree *tree)
@@ -93,7 +52,7 @@ int git_tree__parse(git_tree *tree)
 	git_obj odb_object;
 	char *buffer, *buffer_end;
 
-	error = git_odb_read(&odb_object, tree->object.pool->db, &tree->object.id);
+	error = git_odb_read(&odb_object, tree->object.repo->db, &tree->object.id);
 	if (error < 0)
 		return error;
 
diff --git a/src/tree.h b/src/tree.h
index 373345663..f21668586 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -2,7 +2,7 @@
 #define INCLUDE_tree_h__
 
 #include <git/tree.h>
-#include "revobject.h"
+#include "repository.h"
 
 struct git_tree_entry {
 
@@ -16,7 +16,7 @@ struct git_tree_entry {
 typedef struct git_tree_entry git_tree_entry;
 
 struct git_tree {
-	git_revpool_object object;
+	git_repository_object object;
 
 	size_t byte_size;
 	git_tree_entry *entries;
author	Vicent Marti <tanoku@gmail.com>	2010-08-08 14:12:17 +0200
committer	Vicent Marti <tanoku@gmail.com>	2010-08-12 18:48:55 +0200
commit	3315782cb4f2b683c66a53c93aa81de501c5a4ab (patch)
tree	e3fa8b56dc17b749cc53520eb350cbcc46101007 /src
parent	f8758044876b30b0f6482d1fe8c3b1de743f4186 (diff)
download	libgit2-3315782cb4f2b683c66a53c93aa81de501c5a4ab.tar.gz