mark_parents_uninteresting(): avoid most allocation

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@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/revision.c b/revision.c
index 125327062fab067b19fc69d0a6878b7b2269ea55..c21acb2cb8144cb0c4f642c3556c7d58f5901e62 100644 (file)
--- a/revision.c
+++ b/revision.c
@@ -114,32 +114,38 @@ static void commit_stack_clear(struct commit_stack *stack)
        stack->nr = stack->alloc = 0;
 }
 
        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;
 
        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)
        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);
 }
 
        commit_stack_clear(&pending);
 }