Commit 2c4ef1dd0da560e91b6440aa430537b98e8345dc
2012-03-03T16:43:24
revwalk: use merge bases to speed up processing There is no need walk down the parents of a merge base to mark them as uninteresting because we'll never see them. Calculate the merge bases in prepare_walk() so mark_uninteresting() can stop at a merge base instead of walking all the way to the root.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
diff --git a/src/revwalk.c b/src/revwalk.c
index 92885d6..727bcd7 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -59,6 +59,10 @@ struct git_revwalk {
unsigned walking:1;
unsigned int sorting;
+
+ /* merge base calculation */
+ commit_object *one;
+ git_vector twos;
};
static int commit_time_cmp(void *a, void *b)
@@ -341,6 +345,7 @@ static int merge_bases_many(commit_list **out, git_revwalk *walk, commit_object
}
commit_list_free(&list);
+
/* filter out any stale commits in the results */
list = result;
result = NULL;
@@ -409,6 +414,10 @@ static void mark_uninteresting(commit_object *commit)
commit->uninteresting = 1;
+ /* This means we've reached a merge base, so there's no need to walk any more */
+ if ((commit->flags & (RESULT | STALE)) == RESULT)
+ return;
+
for (i = 0; i < commit->out_degree; ++i)
if (!commit->parents[i]->uninteresting)
mark_uninteresting(commit->parents[i]);
@@ -452,7 +461,15 @@ static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
if (commit == NULL)
return git__throw(GIT_ENOTFOUND, "Failed to push commit. Object not found");
- return process_commit(walk, commit, uninteresting);
+ commit->uninteresting = uninteresting;
+ if (walk->one == NULL && !uninteresting) {
+ walk->one = commit;
+ } else {
+ if (git_vector_insert(&walk->twos, commit) < GIT_SUCCESS)
+ return GIT_ENOMEM;
+ }
+
+ return GIT_SUCCESS;
}
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
@@ -666,7 +683,25 @@ static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
static int prepare_walk(git_revwalk *walk)
{
int error;
- commit_object *next;
+ unsigned int i;
+ commit_object *next, *two;
+ commit_list *bases = NULL;
+
+ /* first figure out what the merge bases are */
+ error = merge_bases_many(&bases, walk, walk->one, &walk->twos);
+ if (error < GIT_SUCCESS)
+ return error;
+
+ commit_list_free(&bases);
+ error = process_commit(walk, walk->one, walk->one->uninteresting);
+ if (error < GIT_SUCCESS)
+ return error;
+
+ git_vector_foreach(&walk->twos, i, two) {
+ error = process_commit(walk, two, two->uninteresting);
+ if (error < GIT_SUCCESS)
+ return error;
+ }
if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
unsigned short i;
@@ -729,6 +764,7 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp);
git_vector_init(&walk->memory_alloc, 8, NULL);
+ git_vector_init(&walk->twos, 4, NULL);
alloc_chunk(walk);
walk->get_next = &revwalk_next_unsorted;
@@ -772,6 +808,7 @@ void git_revwalk_free(git_revwalk *walk)
git__free(git_vector_get(&walk->memory_alloc, i));
git_vector_free(&walk->memory_alloc);
+ git_vector_free(&walk->twos);
git__free(walk);
}