Commit 32e49929725a76d9871038f30e2ea67fe0e4a4f8
2013-09-06T14:20:51
Merge pull request #1791 from libgit2/cmn/revwalk-recursive revwalk: make mark_unintersting use a loop
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
diff --git a/src/array.h b/src/array.h
index c25a1b2..b82079b 100644
--- a/src/array.h
+++ b/src/array.h
@@ -63,6 +63,8 @@ GIT_INLINE(void *) git_array_grow(void *_a, size_t item_size)
#define git_array_last(a) ((a).size ? &(a).ptr[(a).size - 1] : NULL)
+#define git_array_pop(a) ((a).size ? &(a).ptr[--(a).size] : NULL)
+
#define git_array_get(a, i) (((i) < (a).size) ? &(a).ptr[(i)] : NULL)
#define git_array_size(a) (a).size
diff --git a/src/revwalk.c b/src/revwalk.c
index 528d02b..1ff41bf 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -41,28 +41,50 @@ git_commit_list_node *git_revwalk__commit_lookup(
return commit;
}
-static void mark_uninteresting(git_commit_list_node *commit)
+static int mark_uninteresting(git_commit_list_node *commit)
{
unsigned short i;
+ git_array_t(git_commit_list_node *) pending = GIT_ARRAY_INIT;
+ git_commit_list_node **tmp;
+
assert(commit);
- commit->uninteresting = 1;
+ git_array_alloc(pending);
+ GITERR_CHECK_ARRAY(pending);
- /* This means we've reached a merge base, so there's no need to walk any more */
- if ((commit->flags & (RESULT | STALE)) == RESULT)
- return;
+ do {
+ 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) {
+ tmp = git_array_pop(pending);
+ commit = tmp ? *tmp : NULL;
+ continue;
+ }
+
+ for (i = 0; i < commit->out_degree; ++i)
+ if (!commit->parents[i]->uninteresting) {
+ git_commit_list_node **node = git_array_alloc(pending);
+ GITERR_CHECK_ALLOC(node);
+ *node = commit->parents[i];
+ }
+
+ tmp = git_array_pop(pending);
+ commit = tmp ? *tmp : NULL;
+
+ } while (git_array_size(pending) > 0);
- for (i = 0; i < commit->out_degree; ++i)
- if (!commit->parents[i]->uninteresting)
- mark_uninteresting(commit->parents[i]);
+ git_array_clear(pending);
+
+ return 0;
}
static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
{
int error;
- if (hide)
- mark_uninteresting(commit);
+ if (hide && mark_uninteresting(commit) < 0)
+ return -1;
if (commit->seen)
return 0;