Commit 941ba8db57 (Eliminate recursion in setting/clearing
marks in commit list, 2012-01-14) used a clever double-loop
to avoid allocations for single-parent chains of history.
However, it did so only when following parents of parents
(which was an uncommon case), and _always_ incurred at least
one allocation to populate the list of pending parents in
the first place.
We can turn this into zero-allocation in the common case by
iterating directly over the initial parent list, and then
following up on any pending items we might have discovered.
Signed-off-by: Jeff King <peff@xxxxxxxx>
---
Again, try "-w" for more readability.
revision.c | 44 +++++++++++++++++++++++++-------------------
1 file changed, 25 insertions(+), 19 deletions(-)
diff --git a/revision.c b/revision.c
index 89ff9a99ce..cbe041128e 100644
--- a/revision.c
+++ b/revision.c
@@ -115,32 +115,38 @@ static void commit_stack_clear(struct commit_stack *stack)
stack->nr = stack->alloc = 0;
}
-void mark_parents_uninteresting(struct commit *commit)
+static void mark_one_parent_uninteresting(struct commit *commit,
+ struct commit_stack *pending)
{
- struct commit_stack pending = COMMIT_STACK_INIT;
struct commit_list *l;
+ if (commit->object.flags & UNINTERESTING)
+ return;
+ commit->object.flags |= UNINTERESTING;
+
+ /*
+ * Normally we haven't parsed the parent
+ * yet, so we won't have a parent of a parent
+ * here. However, it may turn out that we've
+ * reached this commit some other way (where it
+ * wasn't uninteresting), in which case we need
+ * to mark its parents recursively too..
+ */
for (l = commit->parents; l; l = l->next)
- commit_stack_push(&pending, l->item);
+ commit_stack_push(pending, l->item);
+}
- while (pending.nr > 0) {
- struct commit *commit = commit_stack_pop(&pending);
+void mark_parents_uninteresting(struct commit *commit)
+{
+ struct commit_stack pending = COMMIT_STACK_INIT;
+ struct commit_list *l;
- if (commit->object.flags & UNINTERESTING)
- return;
- commit->object.flags |= UNINTERESTING;
+ for (l = commit->parents; l; l = l->next)
+ mark_one_parent_uninteresting(l->item, &pending);
- /*
- * Normally we haven't parsed the parent
- * yet, so we won't have a parent of a parent
- * here. However, it may turn out that we've
- * reached this commit some other way (where it
- * wasn't uninteresting), in which case we need
- * to mark its parents recursively too..
- */
- for (l = commit->parents; l; l = l->next)
- commit_stack_push(&pending, l->item);
- }
+ while (pending.nr > 0)
+ mark_one_parent_uninteresting(commit_stack_pop(&pending),
+ &pending);
commit_stack_clear(&pending);
}
--
2.17.0.988.gec4b43b3e5
