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 diff --git a/builtin/branch.c b/builtin/branch.c index d8cccf7..98fa5d6 100644 --- a/builtin/branch.c +++ b/builtin/branch.c @@ -122,7 +122,7 @@ static int branch_merged(int kind, const char *name, if (!reference_rev) reference_rev = head_rev; - merged = in_merge_bases(rev, &reference_rev, 1); + merged = in_merge_bases(rev, reference_rev); /* * After the safety valve is fully redefined to "check with @@ -132,7 +132,7 @@ static int branch_merged(int kind, const char *name, * a gentle reminder is in order. */ if ((head_rev != reference_rev) && - in_merge_bases(rev, &head_rev, 1) != merged) { + in_merge_bases(rev, head_rev) != merged) { if (merged) warning(_("deleting branch '%s' that has been merged to\n" " '%s', but not yet merged to HEAD."), diff --git a/builtin/fetch.c b/builtin/fetch.c index 8ec4eae..97327e6 100644 --- a/builtin/fetch.c +++ b/builtin/fetch.c @@ -314,7 +314,7 @@ static int update_local_ref(struct ref *ref, return r; } - if (in_merge_bases(current, &updated, 1)) { + if (in_merge_bases(current, updated)) { char quickref[83]; int r; strcpy(quickref, find_unique_abbrev(current->object.sha1, DEFAULT_ABBREV)); diff --git a/commit.c b/commit.c index 35af498..0a05a10 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; diff --git a/commit.h b/commit.h index 154c0e3..5bb8a88 100644 --- a/commit.h +++ b/commit.h @@ -168,7 +168,7 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads, int depth, int shallow_flag, int not_shallow_flag); int is_descendant_of(struct commit *, struct commit_list *); -int in_merge_bases(struct commit *, struct commit **, int); +int in_merge_bases(struct commit *, struct commit *); extern int interactive_add(int argc, const char **argv, const char *prefix, int patch); extern int run_add_interactive(const char *revision, const char *patch_mode, diff --git a/contrib/examples/builtin-fetch--tool.c b/contrib/examples/builtin-fetch--tool.c index 3140e40..3038c39 100644 --- a/contrib/examples/builtin-fetch--tool.c +++ b/contrib/examples/builtin-fetch--tool.c @@ -96,7 +96,7 @@ static int update_local_ref(const char *name, strcpy(oldh, find_unique_abbrev(current->object.sha1, DEFAULT_ABBREV)); strcpy(newh, find_unique_abbrev(sha1_new, DEFAULT_ABBREV)); - if (in_merge_bases(current, &updated, 1)) { + if (in_merge_bases(current, updated)) { fprintf(stderr, "* %s: fast-forward to %s\n", name, note); fprintf(stderr, " old..new: %s..%s\n", oldh, newh); diff --git a/fast-import.c b/fast-import.c index a85275d..e6f61fc 100644 --- a/fast-import.c +++ b/fast-import.c @@ -1691,7 +1691,7 @@ static int update_branch(struct branch *b) return error("Branch %s is missing commits.", b->name); } - if (!in_merge_bases(old_cmit, &new_cmit, 1)) { + if (!in_merge_bases(old_cmit, new_cmit)) { unlock_ref(lock); warning("Not updating %s" " (new tip %s does not contain %s)", diff --git a/submodule.c b/submodule.c index 9a28060..8fc974d 100644 --- a/submodule.c +++ b/submodule.c @@ -738,7 +738,7 @@ static int find_first_merges(struct object_array *result, const char *path, die("revision walk setup failed"); while ((commit = get_revision(&revs)) != NULL) { struct object *o = &(commit->object); - if (in_merge_bases(b, &commit, 1)) + if (in_merge_bases(b, commit)) add_object_array(o, NULL, &merges); } @@ -752,7 +752,7 @@ static int find_first_merges(struct object_array *result, const char *path, contains_another = 0; for (j = 0; j < merges.nr; j++) { struct commit *m2 = (struct commit *) merges.objects[j].item; - if (i != j && in_merge_bases(m2, &m1, 1)) { + if (i != j && in_merge_bases(m2, m1)) { contains_another = 1; break; } @@ -814,18 +814,18 @@ int merge_submodule(unsigned char result[20], const char *path, } /* check whether both changes are forward */ - if (!in_merge_bases(commit_base, &commit_a, 1) || - !in_merge_bases(commit_base, &commit_b, 1)) { + if (!in_merge_bases(commit_base, commit_a) || + !in_merge_bases(commit_base, commit_b)) { MERGE_WARNING(path, "commits don't follow merge-base"); return 0; } /* Case #1: a is contained in b or vice versa */ - if (in_merge_bases(commit_a, &commit_b, 1)) { + if (in_merge_bases(commit_a, commit_b)) { hashcpy(result, b); return 1; } - if (in_merge_bases(commit_b, &commit_a, 1)) { + if (in_merge_bases(commit_b, commit_a)) { hashcpy(result, a); return 1; } -- cgit v0.10.2-6-g49f6 From 5d55915c7a58e59d913b0cfc38a6f49514068cd2 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 27 Aug 2012 15:16:38 -0700 Subject: receive-pack: use in_merge_bases() for fast-forward check The original computed merge-base between the old commit and the new commit and checked if the old commit was a merge base between them, in order to make sure we are fast-forwarding. Instead, call in_merge_bases(old, new) which does the same. Signed-off-by: Junio C Hamano diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c index 0afb8b2..58f3a37 100644 --- a/builtin/receive-pack.c +++ b/builtin/receive-pack.c @@ -478,7 +478,6 @@ static const char *update(struct command *cmd) !prefixcmp(name, "refs/heads/")) { struct object *old_object, *new_object; struct commit *old_commit, *new_commit; - struct commit_list *bases, *ent; old_object = parse_object(old_sha1); new_object = parse_object(new_sha1); @@ -491,12 +490,7 @@ static const char *update(struct command *cmd) } old_commit = (struct commit *)old_object; new_commit = (struct commit *)new_object; - bases = get_merge_bases(old_commit, new_commit, 1); - for (ent = bases; ent; ent = ent->next) - if (!hashcmp(old_sha1, ent->item->object.sha1)) - break; - free_commit_list(bases); - if (!ent) { + if (!in_merge_bases(old_commit, new_commit)) { rp_error("denying non-fast-forward %s" " (you should pull first)", name); return "non-fast-forward"; -- cgit v0.10.2-6-g49f6 From 6571225137b1ba270b49a0dfc6a30aab6f4b86ba Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 27 Aug 2012 15:21:37 -0700 Subject: http-push: use in_merge_bases() for fast-forward check The original computed merge-base between HEAD and the remote ref and checked if the remote ref is a merge base between them, in order to make sure that we are fast-forwarding. Instead, call in_merge_bases(remote, HEAD) which does the same. Signed-off-by: Junio C Hamano diff --git a/http-push.c b/http-push.c index f22f7e4..555c056 100644 --- a/http-push.c +++ b/http-push.c @@ -1610,9 +1610,8 @@ static int verify_merge_base(unsigned char *head_sha1, struct ref *remote) { struct commit *head = lookup_commit_or_die(head_sha1, "HEAD"); struct commit *branch = lookup_commit_or_die(remote->old_sha1, remote->name); - struct commit_list *merge_bases = get_merge_bases(head, branch, 1); - return (merge_bases && !merge_bases->next && merge_bases->item == branch); + return in_merge_bases(branch, head); } static int delete_remote_branch(const char *pattern, int force) -- cgit v0.10.2-6-g49f6 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 diff --git a/commit.c b/commit.c index 0a05a10..12e5396 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 v0.10.2-6-g49f6 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 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)) -- cgit v0.10.2-6-g49f6 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 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; } -- cgit v0.10.2-6-g49f6 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 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; } -- cgit v0.10.2-6-g49f6 From 5907cda1b2e0bd7dc5c26466f60b9cbb60288cc5 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 30 Aug 2012 14:52:20 -0700 Subject: merge-base: "--is-ancestor A B" In many scripted Porcelain commands, we find this idiom: if test "$(git rev-parse --verify A)" = "$(git merge-base A B)" then ... A is an ancestor of B ... fi But you do not have to compute exact merge-base only to see if A is an ancestor of B. Give them a more direct way to use the underlying machinery. Signed-off-by: Junio C Hamano diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt index b295bf8..87842e3 100644 --- a/Documentation/git-merge-base.txt +++ b/Documentation/git-merge-base.txt @@ -11,6 +11,7 @@ SYNOPSIS [verse] 'git merge-base' [-a|--all] ... 'git merge-base' [-a|--all] --octopus ... +'git merge-base' --is-ancestor 'git merge-base' --independent ... 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 is an ancestor of the second , + 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 a/builtin/merge-base.c b/builtin/merge-base.c index 4f30f1b..0568b07 100644 --- a/builtin/merge-base.c +++ b/builtin/merge-base.c @@ -26,6 +26,7 @@ static const char * const merge_base_usage[] = { "git merge-base [-a|--all] ...", "git merge-base [-a|--all] --octopus ...", "git merge-base --independent ...", + "git merge-base --is-ancestor ", NULL }; @@ -70,6 +71,20 @@ static int handle_octopus(int count, const char **args, int reduce, int show_all return 0; } +static int handle_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 +92,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 +107,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-ancestor cannot be used with other options"); + if (is_ancestor) + return handle_is_ancestor(argc, argv); if (reduce && (show_all || octopus)) die("--independent cannot be used with other options"); -- cgit v0.10.2-6-g49f6 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 diff --git a/commit.c b/commit.c index 2ff5061..69af370 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 v0.10.2-6-g49f6