[PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel

[Junio C Hamano <gitster@pobox.com>]

After merge_bases_many() paints the graph in two colors to find
common ancestors, get_merge_bases_many() reduces the result by
excluding commits that can be reached from other commits in the
result.  We used to do N * (N-1) traversals for this, but we can
check if one commit is reachable from any of the other (N-1) commits
by a single traversal, and repeat it N times to find the answer.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 commit.c | 42 +++++++++++++++++++++++-------------------
 1 file changed, 23 insertions(+), 19 deletions(-)

diff --git a/commit.c b/commit.c
index f5211bd..ccf2c5a 100644
--- a/commit.c
+++ b/commit.c
@@ -715,7 +715,7 @@ struct commit_list *get_merge_bases_many(struct commit *one,
 					 int cleanup)
 {
 	struct commit_list *list;
-	struct commit **rslt;
+	struct commit **rslt, **others;
 	struct commit_list *result;
 	int cnt, i, j;
 
@@ -744,33 +744,37 @@ struct commit_list *get_merge_bases_many(struct commit *one,
 	for (list = result, i = 0; list; list = list->next)
 		rslt[i++] = list->item;
 	free_commit_list(result);
+	result = NULL;
 
 	clear_commit_marks(one, all_flags);
 	for (i = 0; i < n; i++)
 		clear_commit_marks(twos[i], all_flags);
-	for (i = 0; i < cnt - 1; i++) {
-		for (j = i+1; j < cnt; j++) {
-			if (!rslt[i] || !rslt[j])
-				continue;
-			result = merge_bases_many(rslt[i], 1, &rslt[j]);
-			clear_commit_marks(rslt[i], all_flags);
-			clear_commit_marks(rslt[j], all_flags);
-			for (list = result; list; list = list->next) {
-				if (rslt[i] == list->item)
-					rslt[i] = NULL;
-				if (rslt[j] == list->item)
-					rslt[j] = NULL;
-			}
-		}
-	}
 
-	/* Surviving ones in rslt[] are the independent results */
-	result = NULL;
+	others = xcalloc(cnt - 1, sizeof(*others));
 	for (i = 0; i < cnt; i++) {
-		if (rslt[i])
+		/*
+		 * Is rslt[i] an ancestor of any of the others?
+		 * then it is not interesting to us.
+		 */
+		for (j = 0; j < i; j++)
+			others[j] = rslt[j];
+		for (j = 1 + 1; j < cnt; j++)
+			others[j - 1] = rslt[j];
+		list = merge_bases_many(rslt[i], cnt - 1, others);
+		clear_commit_marks(rslt[i], all_flags);
+		for (j = 0; j < cnt - 1; j++)
+			clear_commit_marks(others[j], all_flags);
+		while (list) {
+			if (rslt[i] == list->item)
+				break;
+			list = list->next;
+		}
+		if (!list)
 			commit_list_insert_by_date(rslt[i], &result);
+		free_commit_list(list);
 	}
 	free(rslt);
+	free(others);
 	return result;
 }
 
-- 
1.7.12.116.g31e0100