Commit e7970576f1bcef1561813dbef339a31efabdc9b1
2014-10-08T15:52:11
revwalk: mark uninteresting only up to the common ancestors This introduces a phase at the start of preparing a walk which pre-marks uninteresting commits, but only up to the common ancestors. We do this in a similar way to git, by walking down the history and marking (which is what we used to do), but we keep a time-sorted priority queue of commits and stop marking as soon as there are only uninteresting commits in this queue. This is a similar rule to the one used to find the merge-base. As we keep inserting commits regardless of the uninteresting bit, if there are only uninteresting commits in the queue, it means we've run out of interesting commits in our walk, so we can stop. The old mark_unintesting() logic is still in place, but that stops walking if it finds an already-uninteresting commit, so it will stop on the ones we've pre-marked; but keeping it allows us to also hide those that are hidden via the callback.
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 95 96 97
diff --git a/src/revwalk.c b/src/revwalk.c
index 8a5a846..a1d761f 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -369,19 +369,91 @@ static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *
}
+static int interesting(git_pqueue *list)
+{
+ size_t i;
+
+ for (i = 0; i < git_pqueue_size(list); i++) {
+ git_commit_list_node *commit = git_pqueue_get(list, i);
+ if (!commit->uninteresting)
+ return 1;
+ }
+
+ return 0;
+}
+
+static int contains(git_pqueue *list, git_commit_list_node *node)
+{
+ size_t i;
+
+ for (i = 0; i < git_pqueue_size(list); i++) {
+ git_commit_list_node *commit = git_pqueue_get(list, i);
+ if (commit == node)
+ return 1;
+ }
+
+ return 0;
+}
+
+static int premark_uninteresting(git_revwalk *walk)
+{
+ int error = 0;
+ unsigned short i;
+ git_pqueue q;
+ git_commit_list *list;
+ git_commit_list_node *commit, *parent;
+
+ if ((error = git_pqueue_init(&q, 0, 8, git_commit_list_time_cmp)) < 0)
+ return error;
+
+ for (list = walk->user_input; list; list = list->next) {
+ if ((error = git_commit_list_parse(walk, list->item)) < 0)
+ goto cleanup;
+
+ if ((error = git_pqueue_insert(&q, list->item)) < 0)
+ goto cleanup;
+ }
+
+ while (interesting(&q)) {
+ commit = git_pqueue_pop(&q);
+
+ for (i = 0; i < commit->out_degree; i++) {
+ parent = commit->parents[i];
+
+ if ((error = git_commit_list_parse(walk, parent)) < 0)
+ goto cleanup;
+
+ if (commit->uninteresting)
+ parent->uninteresting = 1;
+
+ if (contains(&q, parent))
+ continue;
+
+ if ((error = git_pqueue_insert(&q, parent)) < 0)
+ goto cleanup;
+ }
+ }
+
+cleanup:
+ git_pqueue_free(&q);
+ return error;
+}
+
static int prepare_walk(git_revwalk *walk)
{
int error, interesting = 0;
git_commit_list *list;
git_commit_list_node *next;
+ if ((error = premark_uninteresting(walk)) < 0)
+ return error;
+
for (list = walk->user_input; list; list = list->next) {
interesting += !list->item->uninteresting;
if (process_commit(walk, list->item, list->item->uninteresting) < 0)
return -1;
}
-
/*
* If there were no pushes, we know that the walk is already over.
*/