From 653194758ee338b7c87d011007c532ed5cf68d45 Mon Sep 17 00:00:00 2001 From: Miklos Vajna Date: Fri, 27 Jun 2008 18:21:55 +0200 Subject: Move commit_list_count() to commit.c This function is useful outside builtin-merge-recursive, for example in builtin-merge. Signed-off-by: Miklos Vajna Signed-off-by: Junio C Hamano --- commit.h | 1 + 1 file changed, 1 insertion(+) (limited to 'commit.h') diff --git a/commit.h b/commit.h index 2d94d4148e..7f8c5ee0fc 100644 --- a/commit.h +++ b/commit.h @@ -41,6 +41,7 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size); int parse_commit(struct commit *item); struct commit_list * commit_list_insert(struct commit *item, struct commit_list **list_p); +unsigned commit_list_count(const struct commit_list *l); struct commit_list * insert_by_date(struct commit *item, struct commit_list **list); void free_commit_list(struct commit_list *list); -- cgit v1.3 From 5240c9d75d8e1b747da427ba6320432d3201168a Mon Sep 17 00:00:00 2001 From: Miklos Vajna Date: Fri, 27 Jun 2008 18:22:00 +0200 Subject: Introduce get_octopus_merge_bases() in commit.c This is like get_merge_bases() but it works for multiple heads, like show-branch --merge-base. Signed-off-by: Miklos Vajna Signed-off-by: Junio C Hamano --- commit.c | 27 +++++++++++++++++++++++++++ commit.h | 1 + 2 files changed, 28 insertions(+) (limited to 'commit.h') diff --git a/commit.c b/commit.c index bbf9c75416..6052ca34c8 100644 --- a/commit.c +++ b/commit.c @@ -600,6 +600,33 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two) return result; } +struct commit_list *get_octopus_merge_bases(struct commit_list *in) +{ + struct commit_list *i, *j, *k, *ret = NULL; + struct commit_list **pptr = &ret; + + for (i = in; i; i = i->next) { + if (!ret) + pptr = &commit_list_insert(i->item, pptr)->next; + else { + struct commit_list *new = NULL, *end = NULL; + + for (j = ret; j; j = j->next) { + struct commit_list *bases; + bases = get_merge_bases(i->item, j->item, 1); + if (!new) + new = bases; + else + end->next = bases; + for (k = bases; k; k = k->next) + end = k; + } + ret = new; + } + } + return ret; +} + struct commit_list *get_merge_bases(struct commit *one, struct commit *two, int cleanup) { diff --git a/commit.h b/commit.h index 7f8c5ee0fc..dcec7fb9a2 100644 --- a/commit.h +++ b/commit.h @@ -121,6 +121,7 @@ int read_graft_file(const char *graft_file); struct commit_graft *lookup_commit_graft(const unsigned char *sha1); extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, int cleanup); +extern struct commit_list *get_octopus_merge_bases(struct commit_list *in); extern int register_shallow(const unsigned char *sha1); extern int unregister_shallow(const unsigned char *sha1); -- cgit v1.3 From 98cf9c3bd7504d36e6049939bf9cc624f2cf5b9f Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 27 Jun 2008 18:22:03 +0200 Subject: Introduce reduce_heads() The new function reduce_heads() is given a list of commits, and removes ones that can be reached from other commits in the list. It is useful for reducing the commits randomly thrown at the git-merge command and remove redundant commits that the user shouldn't have given to it. The implementation uses the get_merge_bases_many() introduced in the previous commit. If the merge base between one commit taken from the list and the remaining commits is the commit itself, that means the commit is reachable from some of the other commits. Signed-off-by: Junio C Hamano --- commit.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ commit.h | 2 ++ 2 files changed, 47 insertions(+) (limited to 'commit.h') diff --git a/commit.c b/commit.c index cafed26928..d20b14ee3e 100644 --- a/commit.c +++ b/commit.c @@ -725,3 +725,48 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num) free_commit_list(bases); return ret; } + +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; + + 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; + + num_other = 0; + for (q = heads; q; q = q->next) { + if (p == q) + continue; + other[num_other++] = q->item; + } + 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); + return result; +} diff --git a/commit.h b/commit.h index dcec7fb9a2..2acfc79d34 100644 --- a/commit.h +++ b/commit.h @@ -140,4 +140,6 @@ static inline int single_parent(struct commit *commit) return commit->parents && !commit->parents->next; } +struct commit_list *reduce_heads(struct commit_list *heads); + #endif /* COMMIT_H */ -- cgit v1.3