[PATCH 10/13] Introduce get_merge_bases_many()
- From
Miklos Vajna <vmiklos@frugalware.org>
- Date
- Jun 21, 2008, 17:00 UTC
- Message-ID
- <57d8a308fae0012174ed4388baccf1bde8515f2f.1214066799.git.vmiklos@frugalware.org>
- In-Reply-To
- <0b7ea424b3d5ea18a5a8660c6aead51adcc6a40f.1214066799.git.vmiklos@frugalware.org>
From: Junio C Hamano <gitster@pobox.com>
This introduces a new function get_merge_bases_many() which is a natural extension of two commit merge base computation. It is given one commit (one) and a set of other commits (twos), and computes the merge base of one and a merge across other commits.
This is mostly useful to figure out the common ancestor when iterating over heads during an octopus merge. When making an octopus between commits A, B, C and D, we first merge tree of A and B, and then try to merge C with it. If we were making pairwise merge, we would be recording the tree resulting from the merge between A and B as a commit, say M, and then the next round we will be computing the merge base between M and C.
o---C...*
/ .
o---B...M
/ .
o---o---ABut during an octopus merge, we actually do not create a commit M. In order to figure out that the common ancestor to use for this merge, instead of computing the merge base between C and M, we can call merge_bases_many() with one set to C and twos containing A and B.
Signed-off-by: Junio C Hamano <gitster@pobox.com> --- commit.c | 56 ++++++++++++++++++++++++++++++++++++++------------------ 1 files changed, 38 insertions(+), 18 deletions(-)
diff --git a/commit.c b/commit.c index 6052ca3..cafed26 100644 --- a/commit.c +++ b/commit.c @@ -533,26 +533,34 @@ static struct commit *interesting(struct commit_list *list) return NULL; } -static struct commit_list *merge_bases(struct commit *one, struct commit *two) +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; - if (one == two) - /* We do not mark this even with RESULT so we do not - * have to clean it up. - */ - return commit_list_insert(one, &result); + 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; - if (parse_commit(two)) - return NULL; + for (i = 0; i < n; i++) { + if (parse_commit(twos[i])) + return NULL; + } one->object.flags |= PARENT1; - two->object.flags |= PARENT2; insert_by_date(one, &list); - insert_by_date(two, &list); + for (i = 0; i < n; i++) { + twos[i]->object.flags |= PARENT2; + insert_by_date(twos[i], &list); + } while (interesting(list)) { struct commit *commit; @@ -627,21 +635,26 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in) return ret; } -struct commit_list *get_merge_bases(struct commit *one, - struct commit *two, int cleanup) +struct commit_list *get_merge_bases_many(struct commit *one, + int n, + struct commit **twos, + int cleanup) { struct commit_list *list; struct commit **rslt; struct commit_list *result; int cnt, i, j; - result = merge_bases(one, two); - if (one == two) - return result; + result = merge_bases_many(one, n, twos); + for (i = 0; i < n; i++) { + if (one == twos[i]) + return result; + } if (!result || !result->next) { if (cleanup) { clear_commit_marks(one, all_flags); - clear_commit_marks(two, all_flags); + for (i = 0; i < n; i++) + clear_commit_marks(twos[i], all_flags); } return result; } @@ -659,12 +672,13 @@ struct commit_list *get_merge_bases(struct commit *one, free_commit_list(result); clear_commit_marks(one, all_flags); - clear_commit_marks(two, 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(rslt[i], rslt[j]); + 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) { @@ -686,6 +700,12 @@ struct commit_list *get_merge_bases(struct commit *one, return result; } +struct commit_list *get_merge_bases(struct commit *one, struct commit *two, + int cleanup) +{ + return get_merge_bases_many(one, 1, &two, cleanup); +} + int in_merge_bases(struct commit *commit, struct commit **reference, int num) { struct commit_list *bases, *b;
-- 1.5.6