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@xxxxxxxxx>
---
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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html