summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2012-08-31 06:20:40 (GMT)
committerJunio C Hamano <gitster@pobox.com>2012-08-31 18:45:36 (GMT)
commitf37d3c755209234acfc2ca280027ebdab8e9ea8a (patch)
tree91e9f5899d2cb51a5ff6807f62ee84ff4ff973cd
parent5907cda1b2e0bd7dc5c26466f60b9cbb60288cc5 (diff)
downloadgit-f37d3c755209234acfc2ca280027ebdab8e9ea8a.zip
git-f37d3c755209234acfc2ca280027ebdab8e9ea8a.tar.gz
git-f37d3c755209234acfc2ca280027ebdab8e9ea8a.tar.bz2
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 <gitster@pobox.com>
-rw-r--r--commit.c56
1 files changed, 18 insertions, 38 deletions
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;
}