Change the Revwalk reset behavior to the old version

The `reset` call now removes the pushed commits so we can reuse
the revwalker. The API documentation has been updated with the details.

5 files changed, 157 insertions, 113 deletions

diff --git a/include/git2/revwalk.h b/include/git2/revwalk.h
index fdbbe236c..4b5ea8e06 100644
--- a/include/git2/revwalk.h
+++ b/include/git2/revwalk.h
@@ -70,6 +70,17 @@ GIT_BEGIN_DECL
 /**
  * Allocate a new revision walker to iterate through a repo.
  *
+ * This revision walker uses a custom memory pool and an internal
+ * commit cache, so it is relatively expensive to allocate.
+ *
+ * For maximum performance, this revision walker should be
+ * reused for different walks.
+ *
+ * This revision walker is *not* thread safe: it may only be
+ * used to walk a repository on a single thread; however,
+ * it is possible to have several revision walkers in
+ * several different threads walking the same repository.
+ *
  * @param walker pointer to the new revision walker
  * @param repo the repo to walk through
  * @return 0 on success; error code otherwise
@@ -77,32 +88,67 @@ GIT_BEGIN_DECL
 GIT_EXTERN(int) git_revwalk_new(git_revwalk **walker, git_repository *repo);
 
 /**
- * Reset the walking machinery for reuse.
+ * Reset the revision walker for reuse.
+ *
+ * This will clear all the pushed and hidden commits, and
+ * leave the walker in a blank state (just like at
+ * creation) ready to receive new commit pushes and
+ * start a new walk.
+ *
+ * The revision walk is automatically reset when a walk
+ * is over.
+ *
  * @param walker handle to reset.
  */
 GIT_EXTERN(void) git_revwalk_reset(git_revwalk *walker);
 
 /**
  * Mark a commit to start traversal from.
- * The commit object must belong to the repo which is being walked through.
+ *
+ * The given OID must belong to a commit on the walked
+ * repository.
+ *
+ * The given commit will be used as one of the roots
+ * when starting the revision walk. At least one commit
+ * must be pushed the repository before a walk can
+ * be started.
  *
  * @param walker the walker being used for the traversal.
- * @param commit the commit to start from.
+ * @param oid the oid of the commit to start from.
+ * @return 0 on success; error code otherwise
  */
 GIT_EXTERN(int) git_revwalk_push(git_revwalk *walk, const git_oid *oid);
 
 
 /**
  * Mark a commit (and its ancestors) uninteresting for the output.
+ *
+ * The given OID must belong to a commit on the walked
+ * repository.
+ *
+ * The resolved commit and all its parents will be hidden from the
+ * output on the revision walk.
+ *
  * @param walker the walker being used for the traversal.
  * @param commit the commit that will be ignored during the traversal
+ * @return 0 on success; error code otherwise
  */
 GIT_EXTERN(int) git_revwalk_hide(git_revwalk *walk, const git_oid *oid);
 
 /**
- * Get the next commit from the revision traversal.
+ * Get the next commit from the revision walk.
+ *
+ * The initial call to this method is *not* blocking when
+ * iterating through a repo with a time-sorting mode.
+ *
+ * Iterating with Topological or inverted modes makes the initial
+ * call blocking to preprocess the commit list, but this block should be
+ * mostly unnoticeable on most repositories (topological preprocessing
+ * times at 0.3s on the git.git repo).
  *
- * @param commit Pointer where to store the next commit
+ * The revision walker is reset when the walk is over.
+ *
+ * @param oid Pointer where to store the oid of the next commit
  * @param walk the walker to pop the commit from.
  * @return GIT_SUCCESS if the next commit was found;
  *	GIT_EREVWALKOVER if there are no commits left to iterate
@@ -112,14 +158,17 @@ GIT_EXTERN(int) git_revwalk_next(git_oid *oid, git_revwalk *walk);
 /**
  * Change the sorting mode when iterating through the
  * 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
+ * @param sort_mode combination of GIT_SORT_XXX flags
  */
-GIT_EXTERN(int) git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode);
+GIT_EXTERN(void) git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode);
 
 /**
- * Free a revwalk previously allocated.
+ * Free a revision walker previously allocated.
+ *
  * @param walk traversal handle to close.  If NULL nothing occurs.
  */
 GIT_EXTERN(void) git_revwalk_free(git_revwalk *walk);
diff --git a/src/pqueue.c b/src/pqueue.c
index 98152cb85..6307175e3 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -50,6 +50,10 @@ void git_pqueue_free(git_pqueue *q)
 	q->d = NULL;
 }
 
+void git_pqueue_clear(git_pqueue *q)
+{
+	q->size = 1;
+}
 
 size_t git_pqueue_size(git_pqueue *q)
 {
diff --git a/src/pqueue.h b/src/pqueue.h
index 6db74661d..7a1394803 100644
--- a/src/pqueue.h
+++ b/src/pqueue.h
@@ -53,6 +53,11 @@ int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri);
  */
 void git_pqueue_free(git_pqueue *q);
 
+/**
+ * clear all the elements in the queue
+ * @param q the queue
+ */
+void git_pqueue_clear(git_pqueue *q);
 
 /**
  * return the size of the queue.
diff --git a/src/revwalk.c b/src/revwalk.c
index d17b44053..a2fc092d5 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -52,7 +52,6 @@ struct git_revwalk {
 	git_repository *repo;
 
 	git_hashtable *commits;
-	git_vector pending;
 
 	commit_list *iterator_topo;
 	commit_list *iterator_rand;
@@ -159,71 +158,6 @@ static commit_object **alloc_parents(commit_object *commit, size_t n_parents)
 	return git__malloc(n_parents * sizeof(commit_object *));
 }
 
-int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
-{
-	git_revwalk *walk;
-
-	walk = git__malloc(sizeof(git_revwalk));
-	if (walk == NULL)
-		return GIT_ENOMEM;
-
-	memset(walk, 0x0, sizeof(git_revwalk));
-
-	walk->commits = git_hashtable_alloc(64,
-			object_table_hash,
-			(git_hash_keyeq_ptr)git_oid_cmp);
-
-	if (walk->commits == NULL) {
-		free(walk);
-		return GIT_ENOMEM;
-	}
-
-	git_vector_init(&walk->pending, 8, NULL);
-	git_vector_init(&walk->memory_alloc, 8, NULL);
-	alloc_chunk(walk);
-
-	walk->repo = repo;
-
-	*revwalk_out = walk;
-	return GIT_SUCCESS;
-}
-
-void git_revwalk_free(git_revwalk *walk)
-{
-	unsigned int i;
-
-	if (walk == NULL)
-		return;
-
-	git_revwalk_reset(walk);
-	git_hashtable_free(walk->commits);
-	git_vector_free(&walk->pending);
-
-	for (i = 0; i < walk->memory_alloc.length; ++i) {
-		free(git_vector_get(&walk->memory_alloc, i));
-	}
-
-	git_vector_free(&walk->memory_alloc);
-	free(walk);
-}
-
-git_repository *git_revwalk_repository(git_revwalk *walk)
-{
-	assert(walk);
-	return walk->repo;
-}
-
-int git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
-{
-	assert(walk);
-
-	if (walk->walking)
-		return GIT_EBUSY;
-
-	walk->sorting = sort_mode;
-	git_revwalk_reset(walk);
-	return GIT_SUCCESS;
-}
 
 static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 {
@@ -370,10 +304,9 @@ static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
 	if (commit == NULL)
 		return GIT_ENOTFOUND;
 
-	if (uninteresting)
-		mark_uninteresting(commit);
+	commit->uninteresting = uninteresting;
 
-	return git_vector_insert(&walk->pending, commit);
+	return process_commit(walk, commit);
 }
 
 int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
@@ -472,31 +405,11 @@ static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
 
 static int prepare_walk(git_revwalk *walk)
 {
-	unsigned int i;
 	int error;
-
-	if (walk->sorting & GIT_SORT_TIME) {
-		if ((error = git_pqueue_init(&walk->iterator_time, 32, commit_time_cmp)) < GIT_SUCCESS)
-			return error;
-
-		walk->get_next = &revwalk_next_timesort;
-		walk->enqueue = &revwalk_enqueue_timesort;
-	} else {
-		walk->get_next = &revwalk_next_unsorted;
-		walk->enqueue = &revwalk_enqueue_unsorted;
-	}
-
-	for (i = 0; i < walk->pending.length; ++i) {
-		commit_object *commit = walk->pending.contents[i];
-		if ((error = process_commit(walk, commit)) < GIT_SUCCESS) {
-			return error;
-		}
-	}
+	commit_object *next;
 
 	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
-		commit_object *next;
 		unsigned short i;
-		int error;
 
 		while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) {
 			for (i = 0; i < next->out_degree; ++i) {
@@ -514,8 +427,6 @@ static int prepare_walk(git_revwalk *walk)
 	}
 
 	if (walk->sorting & GIT_SORT_REVERSE) {
-		commit_object *next;
-		int error;
 
 		while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS)
 			commit_list_insert(next, &walk->iterator_reverse);
@@ -531,6 +442,83 @@ static int prepare_walk(git_revwalk *walk)
 }
 
 
+
+
+
+int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
+{
+	git_revwalk *walk;
+
+	walk = git__malloc(sizeof(git_revwalk));
+	if (walk == NULL)
+		return GIT_ENOMEM;
+
+	memset(walk, 0x0, sizeof(git_revwalk));
+
+	walk->commits = git_hashtable_alloc(64,
+			object_table_hash,
+			(git_hash_keyeq_ptr)git_oid_cmp);
+
+	if (walk->commits == NULL) {
+		free(walk);
+		return GIT_ENOMEM;
+	}
+
+	git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp);
+	git_vector_init(&walk->memory_alloc, 8, NULL);
+	alloc_chunk(walk);
+
+	walk->get_next = &revwalk_next_unsorted;
+	walk->enqueue = &revwalk_enqueue_unsorted;
+
+	walk->repo = repo;
+
+	*revwalk_out = walk;
+	return GIT_SUCCESS;
+}
+
+void git_revwalk_free(git_revwalk *walk)
+{
+	unsigned int i;
+
+	if (walk == NULL)
+		return;
+
+	git_revwalk_reset(walk);
+	git_hashtable_free(walk->commits);
+	git_pqueue_free(&walk->iterator_time);
+
+	for (i = 0; i < walk->memory_alloc.length; ++i)
+		free(git_vector_get(&walk->memory_alloc, i));
+
+	git_vector_free(&walk->memory_alloc);
+	free(walk);
+}
+
+git_repository *git_revwalk_repository(git_revwalk *walk)
+{
+	assert(walk);
+	return walk->repo;
+}
+
+void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
+{
+	assert(walk);
+
+	if (walk->walking)
+		git_revwalk_reset(walk);
+
+	walk->sorting = sort_mode;
+
+	if (walk->sorting & GIT_SORT_TIME) {
+		walk->get_next = &revwalk_next_timesort;
+		walk->enqueue = &revwalk_enqueue_timesort;
+	} else {
+		walk->get_next = &revwalk_next_unsorted;
+		walk->enqueue = &revwalk_enqueue_unsorted;
+	}
+}
+
 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 {
 	int error;
@@ -544,8 +532,11 @@ int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 	}
 
 	error = walk->get_next(&next, walk);
-	if (error < GIT_SUCCESS)
+	if (error < GIT_SUCCESS) {
+		if (error == GIT_EREVWALKOVER)
+			git_revwalk_reset(walk);
 		return error;
+	}
 
 	git_oid_cpy(oid, &next->oid);
 	return GIT_SUCCESS;
@@ -564,7 +555,7 @@ void git_revwalk_reset(git_revwalk *walk)
 		commit->topo_delay = 0;
 	);
 
-	git_pqueue_free(&walk->iterator_time);
+	git_pqueue_clear(&walk->iterator_time);
 	commit_list_free(&walk->iterator_topo);
 	commit_list_free(&walk->iterator_rand);
 	commit_list_free(&walk->iterator_reverse);
diff --git a/tests/t05-revwalk.c b/tests/t05-revwalk.c
index bdec09e83..0460d4c08 100644
--- a/tests/t05-revwalk.c
+++ b/tests/t05-revwalk.c
@@ -84,7 +84,7 @@ static int get_commit_index(git_oid *raw_oid)
 	return -1;
 }
 
-static int test_walk(git_revwalk *walk,
+static int test_walk(git_revwalk *walk, const git_oid *root,
 		int flags, const int possible_results[][6], int results_count)
 {
 	git_oid oid;
@@ -92,8 +92,8 @@ static int test_walk(git_revwalk *walk,
 	int i;
 	int result_array[commit_count];
 
-	git_revwalk_reset(walk);
 	git_revwalk_sorting(walk, flags);
+	git_revwalk_push(walk, root);
 
 	for (i = 0; i < commit_count; ++i)
 		result_array[i] = -1;
@@ -124,19 +124,14 @@ BEGIN_TEST(walk0, "do a simple walk on a repo with different sorting modes")
 	git_revwalk *walk;
 
 	must_pass(git_repository_open(&repo, REPOSITORY_FOLDER));
-
 	must_pass(git_revwalk_new(&walk, repo));
 
 	git_oid_mkstr(&id, commit_head);
-	git_revwalk_push(walk, &id);
-
-	must_pass(test_walk(walk, GIT_SORT_TIME, commit_sorting_time, 1));
-
-	must_pass(test_walk(walk, GIT_SORT_TOPOLOGICAL, commit_sorting_topo, 2));
-
-	must_pass(test_walk(walk, GIT_SORT_TIME | GIT_SORT_REVERSE, commit_sorting_time_reverse, 1));
 
-	must_pass(test_walk(walk, GIT_SORT_TOPOLOGICAL | GIT_SORT_REVERSE, commit_sorting_topo_reverse, 2));
+	must_pass(test_walk(walk, &id, GIT_SORT_TIME, commit_sorting_time, 1));
+	must_pass(test_walk(walk, &id, GIT_SORT_TOPOLOGICAL, commit_sorting_topo, 2));
+	must_pass(test_walk(walk, &id, GIT_SORT_TIME | GIT_SORT_REVERSE, commit_sorting_time_reverse, 1));
+	must_pass(test_walk(walk, &id, GIT_SORT_TOPOLOGICAL | GIT_SORT_REVERSE, commit_sorting_topo_reverse, 2));
 
 	git_revwalk_free(walk);
 	git_repository_free(repo);