patch, 4 partsget_merge_bases_many(): walk from many tips in parallel

diff --git a/commit.c b/commit.c
index 12e5396..0058fa5 100644
--- a/commit.c
+++ b/commit.c
@@ -581,28 +581,12 @@ static struct commit *interesting(struct commit_list *list)
 	return NULL;
 }
 
-static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
 {
 	struct commit_list *list = NULL;
 	struct commit_list *result = NULL;
 	int i;
 
-	for (i = 0; i < n; i++) {
-		if (one == twos[i])
-			/*
-			 * We do not mark this even with RESULT so we do not
-			 * have to clean it up.
-			 */
-			return commit_list_insert(one, &result);
-	}
-
-	if (parse_commit(one))
-		return NULL;
-	for (i = 0; i < n; i++) {
-		if (parse_commit(twos[i]))
-			return NULL;
-	}
-
 	one->object.flags |= PARENT1;
 	commit_list_insert_by_date(one, &list);
 	for (i = 0; i < n; i++) {
@@ -643,9 +627,34 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
 		}
 	}
 
-	/* Clean up the result to remove stale ones */
 	free_commit_list(list);
-	list = result; result = NULL;
+	return result;
+}
+
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+{
+	struct commit_list *list = NULL;
+	struct commit_list *result = NULL;
+	int i;
+
+	for (i = 0; i < n; i++) {
+		if (one == twos[i])
+			/*
+			 * We do not mark this even with RESULT so we do not
+			 * have to clean it up.
+			 */
+			return commit_list_insert(one, &result);
+	}
+
+	if (parse_commit(one))
+		return NULL;
+	for (i = 0; i < n; i++) {
+		if (parse_commit(twos[i]))
+			return NULL;
+	}
+
+	list = paint_down_to_common(one, n, twos);
+
 	while (list) {
 		struct commit_list *next = list->next;
 		if (!(list->item->object.flags & STALE))

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 4f30f1b..615aa04 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -70,6 +70,20 @@ static int handle_octopus(int count, const char **args, int reduce, int show_all
 	return 0;
 }
 
+static int show_is_ancestor(int argc, const char **argv)
+{
+	struct commit *one, *two;
+
+	if (argc != 2)
+		die("--is-ancestor takes exactly two commits");
+	one = get_commit_reference(argv[0]);
+	two = get_commit_reference(argv[1]);
+	if (in_merge_bases(one, two))
+		return 0;
+	else
+		return 1;
+}
+
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
 	struct commit **rev;
@@ -77,11 +91,14 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	int show_all = 0;
 	int octopus = 0;
 	int reduce = 0;
+	int is_ancestor = 0;
 
 	struct option options[] = {
 		OPT_BOOLEAN('a', "all", &show_all, "output all common ancestors"),
 		OPT_BOOLEAN(0, "octopus", &octopus, "find ancestors for a single n-way merge"),
 		OPT_BOOLEAN(0, "independent", &reduce, "list revs not reachable from others"),
+		OPT_BOOLEAN(0, "is-ancestor", &is_ancestor,
+			    "is the first one ancestor of the other?"),
 		OPT_END()
 	};
 
@@ -89,6 +106,10 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	argc = parse_options(argc, argv, prefix, options, merge_base_usage, 0);
 	if (!octopus && !reduce && argc < 2)
 		usage_with_options(merge_base_usage, options);
+	if (is_ancestor && (show_all | octopus | reduce))
+		die("--is-reachable cannot be used with other options");
+	if (is_ancestor)
+		return show_is_ancestor(argc, argv);
 	if (reduce && (show_all || octopus))
 		die("--independent cannot be used with other options");
 

diff --git i/Documentation/git-merge-base.txt w/Documentation/git-merge-base.txt
index b295bf8..87842e3 100644
--- i/Documentation/git-merge-base.txt
+++ w/Documentation/git-merge-base.txt
@@ -11,6 +11,7 @@ SYNOPSIS
 [verse]
 'git merge-base' [-a|--all] <commit> <commit>...
 'git merge-base' [-a|--all] --octopus <commit>...
+'git merge-base' --is-ancestor <commit> <commit>
 'git merge-base' --independent <commit>...
 
 DESCRIPTION
@@ -50,6 +51,12 @@ from linkgit:git-show-branch[1] when used with the `--merge-base` option.
 	from any other.  This mimics the behavior of 'git show-branch
 	--independent'.
 
+--is-ancestor::
+	Check if the first <commit> is an ancestor of the second <commit>,
+	and exit with status 0 if true, or with status 1 if not.
+	Errors are signaled by a non-zero status that is not 1.
+
+
 OPTIONS
 -------
 -a::
@@ -110,6 +117,27 @@ both '1' and '2' are merge-bases of A and B.  Neither one is better than
 the other (both are 'best' merge bases).  When the `--all` option is not given,
 it is unspecified which best one is output.
 
+A common idiom to check "fast-forward-ness" between two commits A
+and B is (or at least used to be) to compute the merge base between
+A and B, and check if it is the same as A, in which case, A is an
+ancestor of B.  You will see this idiom used often in older scripts.
+
+	A=$(git rev-parse --verify A)
+	if test "$A" = "$(git merge-base A B)"
+	then
+		... A is an ancestor of B ...
+	fi
+
+In modern git, you can say this in a more direct way:
+
+	if git merge-base --is-ancestor A B
+	then
+		... A is an ancestor of B ...
+	fi
+
+instead.
+
+
 See also
 --------
 linkgit:git-rev-list[1],
diff --git i/builtin/merge-base.c w/builtin/merge-base.c
index 615aa04..447ab7c 100644
--- i/builtin/merge-base.c
+++ w/builtin/merge-base.c
@@ -70,7 +70,7 @@ static int handle_octopus(int count, const char **args, int reduce, int show_all
 	return 0;
 }
 
-static int show_is_ancestor(int argc, const char **argv)
+static int handle_is_ancestor(int argc, const char **argv)
 {
 	struct commit *one, *two;
 
@@ -107,9 +107,9 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	if (!octopus && !reduce && argc < 2)
 		usage_with_options(merge_base_usage, options);
 	if (is_ancestor && (show_all | octopus | reduce))
-		die("--is-reachable cannot be used with other options");
+		die("--is-ancestor cannot be used with other options");
 	if (is_ancestor)
-		return show_is_ancestor(argc, argv);
+		return handle_is_ancestor(argc, argv);
 	if (reduce && (show_all || octopus))
 		die("--independent cannot be used with other options");
 

diff --git a/commit.c b/commit.c
index 0058fa5..d39a9e9 100644
--- a/commit.c
+++ b/commit.c
@@ -786,20 +786,17 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
  */
 int in_merge_bases(struct commit *commit, struct commit *reference)
 {
-	struct commit_list *bases, *b;
+	struct commit_list *bases;
 	int ret = 0;
 
-	bases = merge_bases_many(commit, 1, &reference);
+	if (parse_commit(commit) || parse_commit(reference))
+		return ret;
+
+	bases = paint_down_to_common(commit, 1, &reference);
+	if (commit->object.flags & PARENT2)
+		ret = 1;
 	clear_commit_marks(commit, all_flags);
 	clear_commit_marks(reference, all_flags);
-
-	for (b = bases; b; b = b->next) {
-		if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {
-			ret = 1;
-			break;
-		}
-	}
-
 	free_commit_list(bases);
 	return ret;
 }

diff --git a/commit.c b/commit.c
index d39a9e9..2ff5061 100644
--- a/commit.c
+++ b/commit.c
@@ -692,6 +692,60 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)
 	return ret;
 }
 
+static int remove_redundant(struct commit **array, int cnt)
+{
+	/*
+	 * Some commit in the array may be an ancestor of
+	 * another commit.  Move such commit to the end of
+	 * the array, and return the number of commits that
+	 * are independent from each other.
+	 */
+	struct commit **work;
+	unsigned char *redundant;
+	int *filled_index;
+	int i, j, filled;
+
+	work = xcalloc(cnt, sizeof(*work));
+	redundant = xcalloc(cnt, 1);
+	filled_index = xmalloc(sizeof(*filled_index) * (cnt - 1));
+
+	for (i = 0; i < cnt; i++) {
+		struct commit_list *common;
+
+		if (redundant[i])
+			continue;
+		for (j = filled = 0; j < cnt; j++) {
+			if (i == j || redundant[j])
+				continue;
+			filled_index[filled] = j;
+			work[filled++] = array[j];
+		}
+		common = paint_down_to_common(array[i], filled, work);
+		if (array[i]->object.flags & PARENT2)
+			redundant[i] = 1;
+		for (j = 0; j < filled; j++)
+			if (work[j]->object.flags & PARENT1)
+				redundant[filled_index[j]] = 1;
+		clear_commit_marks(array[i], all_flags);
+		for (j = 0; j < filled; j++)
+			clear_commit_marks(work[j], all_flags);
+		free_commit_list(common);
+	}
+
+	/* Now collect the result */
+	memcpy(work, array, sizeof(*array) * cnt);
+	for (i = filled = 0; i < cnt; i++)
+		if (!redundant[i])
+			array[filled++] = work[i];
+	for (j = filled, i = 0; i < cnt; i++)
+		if (redundant[i])
+			array[j++] = work[i];
+	free(work);
+	free(redundant);
+	free(filled_index);
+	return filled;
+}
+
 struct commit_list *get_merge_bases_many(struct commit *one,
 					 int n,
 					 struct commit **twos,
@@ -700,7 +754,7 @@ struct commit_list *get_merge_bases_many(struct commit *one,
 	struct commit_list *list;
 	struct commit **rslt;
 	struct commit_list *result;
-	int cnt, i, j;
+	int cnt, i;
 
 	result = merge_bases_many(one, n, twos);
 	for (i = 0; i < n; i++) {
@@ -731,28 +785,11 @@ struct commit_list *get_merge_bases_many(struct commit *one,
 	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 */
+	cnt = remove_redundant(rslt, cnt);
 	result = NULL;
-	for (i = 0; i < cnt; i++) {
-		if (rslt[i])
-			commit_list_insert_by_date(rslt[i], &result);
-	}
+	for (i = 0; i < cnt; i++)
+		commit_list_insert_by_date(rslt[i], &result);
 	free(rslt);
 	return result;
 }