From a20efee9cfcf9c68bb01d0aa82ffc7903d88bab4 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 27 Aug 2012 14:46:01 -0700 Subject: in_merge_bases(): support only one "other" commit In early days of its life, I planned to make it possible to compute "is a commit contained in all of these other commits?" with this function, but it turned out that no caller needed it. Just make it take two commit objects and add a comment to say what these two functions do. Signed-off-by: Junio C Hamano --- commit.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 35af4988f0..0a05a1075a 100644 --- a/commit.c +++ b/commit.c @@ -754,6 +754,9 @@ struct commit_list *get_merge_bases(struct commit *one, struct commit *two, return get_merge_bases_many(one, 1, &two, cleanup); } +/* + * Is "commit" a decendant of one of the elements on the "with_commit" list? + */ int is_descendant_of(struct commit *commit, struct commit_list *with_commit) { if (!with_commit) @@ -763,21 +766,21 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit) other = with_commit->item; with_commit = with_commit->next; - if (in_merge_bases(other, &commit, 1)) + if (in_merge_bases(other, commit)) return 1; } return 0; } -int in_merge_bases(struct commit *commit, struct commit **reference, int num) +/* + * Is "commit" an ancestor of (i.e. reachable from) the "reference"? + */ +int in_merge_bases(struct commit *commit, struct commit *reference) { struct commit_list *bases, *b; int ret = 0; - if (num == 1) - bases = get_merge_bases(commit, *reference, 1); - else - die("not yet"); + bases = get_merge_bases(commit, reference, 1); for (b = bases; b; b = b->next) { if (!hashcmp(commit->object.sha1, b->item->object.sha1)) { ret = 1; -- cgit v1.2.3 From b0f9e9eeef0ed4f21fc9bfa92f1314e3112d5cc1 Mon Sep 17 00:00:00 2001 From: Thomas Rast Date: Thu, 23 Aug 2012 16:20:41 +0200 Subject: in_merge_bases(): omit unnecessary redundant common ancestor reduction The function get_merge_bases() needs to postprocess the result from merge_bases_many() in order to make sure none of the commit is a true ancestor of another commit, which is expensive. However, when checking if a commit is an ancestor of another commit, we only need to see if the commit is a common ancestor between the two, and do not have to care if other common ancestors merge_bases_many() finds are true merge bases or an ancestor of another merge base. Signed-off-by: Thomas Rast Signed-off-by: Junio C Hamano --- commit.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 0a05a1075a..12e5396e4c 100644 --- a/commit.c +++ b/commit.c @@ -780,7 +780,10 @@ int in_merge_bases(struct commit *commit, struct commit *reference) struct commit_list *bases, *b; int ret = 0; - bases = get_merge_bases(commit, reference, 1); + bases = merge_bases_many(commit, 1, &reference); + 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; -- cgit v1.2.3 From da1f515641f4853a6b7c4710392796ed08efaa6f Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 30 Aug 2012 14:39:03 -0700 Subject: merge_bases_many(): split out the logic to paint history Introduce a new helper function paint_down_to_common() that takes the same parameters as merge_bases_many(), but without the first optimization of not painting anything when "one" is one of the "twos" (or vice versa), and the last clean-up of removing the common ancestor that is known to be an ancestor of another common one. This way, the caller of the new function could tell if "one" is reachable from any of the "twos" by simply looking at the flag bits of "one". If (and only if) it is painted in PARENT2, it is reachable from one of the "twos". Signed-off-by: Junio C Hamano --- commit.c | 47 ++++++++++++++++++++++++++++------------------- 1 file changed, 28 insertions(+), 19 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 12e5396e4c..0058fa5b43 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)) -- cgit v1.2.3 From 6440fdbab430bc10fdac37e86ae25607c93d3903 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 30 Aug 2012 15:04:13 -0700 Subject: in_merge_bases(): use paint_down_to_common() With paint_down_to_common(), we can tell if "commit" is reachable from "reference" by simply looking at its object flag, instead of iterating over the merge bases. Signed-off-by: Junio C Hamano --- commit.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 0058fa5b43..d39a9e9693 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; } -- cgit v1.2.3 From 94f0ced0d08c8f835992b82224231b9353490e0c Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 30 Aug 2012 15:35:39 -0700 Subject: get_merge_bases_many(): walk from many tips in parallel The get_merge_bases_many() function reduces the result returned by the merge_bases_many() function, which is a set of possible merge bases, by excluding commits that can be reached from other commits. We used to do N*(N-1) traversals for this, but we can check if one commit reaches which other (N-1) commits by a single traversal, and repeat it for all the candidates to find the answer. Introduce remove_redundant() helper function to do this painting; we should be able to use it to reimplement reduce_heads() as well. Signed-off-by: Junio C Hamano --- commit.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 58 insertions(+), 21 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index d39a9e9693..2ff5061c12 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; } -- cgit v1.2.3 From f37d3c755209234acfc2ca280027ebdab8e9ea8a Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 30 Aug 2012 23:20:40 -0700 Subject: reduce_heads(): reimplement on top of remove_redundant() This is used by "git merge" and "git merge-base --independent" but used to use a similar N*(N-1) traversals to reject commits that are ancestors of other commits. Reimplement it on top of remove_redundant(). Note that the callers of this function are allowed to pass the same commit more than once, but remove_redundant() is designed to be fed each commit only once. The function removes duplicates before calling remove_redundant(). Signed-off-by: Junio C Hamano --- commit.c | 56 ++++++++++++++++++-------------------------------------- 1 file changed, 18 insertions(+), 38 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 2ff5061c12..69af37014f 100644 --- a/commit.c +++ b/commit.c @@ -842,51 +842,31 @@ struct commit_list *reduce_heads(struct commit_list *heads) { struct commit_list *p; struct commit_list *result = NULL, **tail = &result; - struct commit **other; - size_t num_head, num_other; + struct commit **array; + int num_head, i; if (!heads) return NULL; - /* Avoid unnecessary reallocations */ - for (p = heads, num_head = 0; p; p = p->next) - num_head++; - other = xcalloc(sizeof(*other), num_head); - - /* For each commit, see if it can be reached by others */ - for (p = heads; p; p = p->next) { - struct commit_list *q, *base; - - /* Do we already have this in the result? */ - for (q = result; q; q = q->next) - if (p->item == q->item) - break; - if (q) + /* Uniquify */ + for (p = heads; p; p = p->next) + p->item->object.flags &= ~STALE; + for (p = heads, num_head = 0; p; p = p->next) { + if (p->item->object.flags & STALE) continue; - - num_other = 0; - for (q = heads; q; q = q->next) { - if (p->item == q->item) - continue; - other[num_other++] = q->item; + p->item->object.flags |= STALE; + num_head++; + } + array = xcalloc(sizeof(*array), num_head); + for (p = heads, i = 0; p; p = p->next) { + if (p->item->object.flags & STALE) { + array[i++] = p->item; + p->item->object.flags &= ~STALE; } - if (num_other) - base = get_merge_bases_many(p->item, num_other, other, 1); - else - base = NULL; - /* - * If p->item does not have anything common with other - * commits, there won't be any merge base. If it is - * reachable from some of the others, p->item will be - * the merge base. If its history is connected with - * others, but p->item is not reachable by others, we - * will get something other than p->item back. - */ - if (!base || (base->item != p->item)) - tail = &(commit_list_insert(p->item, tail)->next); - free_commit_list(base); } - free(other); + num_head = remove_redundant(array, num_head); + for (i = 0; i < num_head; i++) + tail = &commit_list_insert(array[i], tail)->next; return result; } -- cgit v1.2.3