[PATCH 3/7] merge-base: stop moving commits around in remove_redundant()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Oct 19, 2016, 04:23 UTC
- Message-ID
- <20161019042345.29766-4-gitster@pobox.com>
- In-Reply-To
- <20161019042345.29766-1-gitster@pobox.com>
The merge-base computation is performed in two steps. First, paint_down_to_common() traverses the history to find all possible merge bases (and more), and then remove_redundant() checks the result and culls the ones that can be reached from another commit in the result.
The latter received an array of commits, and then returned the same array after reordering the elements in it, moving the surviving ones to the front and returning the number of surviving ones.
This arrangement works, but it makes it cumbersome for the callers when they want to see the array's contents intact (e.g. the caller may want to keep an additional per-commit data in an independent array that parallels the array of commits).
Stop moving commits around in the array, and instead mark the ones that are not merge bases with the STALE bit in their object->flags bitword.
Signed-off-by: Junio C Hamano <gitster@pobox.com> --- commit.c | 32 ++++++++++++++++++-------------- 1 file changed, 18 insertions(+), 14 deletions(-)
diff --git a/commit.c b/commit.c index 6266c0380c..59bd18e67c 100644 --- a/commit.c +++ b/commit.c @@ -888,11 +888,11 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in) return ret; } -static int remove_redundant(struct commit **array, int cnt) +static void mark_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 + * another commit. Mark such commit as STALE in * the array, and return the number of commits that * are independent from each other. */ @@ -930,18 +930,16 @@ static int remove_redundant(struct commit **array, int cnt) free_commit_list(common); } - /* Now collect the result */ - COPY_ARRAY(work, array, cnt); - for (i = filled = 0; i < cnt; i++) - if (!redundant[i]) - array[filled++] = work[i]; - for (j = filled, i = 0; i < cnt; i++) + /* Mark the result */ + for (i = 0; i < cnt; i++) if (redundant[i]) - array[j++] = work[i]; + array[i]->object.flags |= STALE; + else + array[i]->object.flags &= ~STALE; + free(work); free(redundant); free(filled_index); - return filled; } static struct commit_list *get_merge_bases_many_0(struct commit *one, @@ -984,10 +982,13 @@ static struct commit_list *get_merge_bases_many_0(struct commit *one, clear_commit_marks(one, all_flags); clear_commit_marks_many(n, twos, all_flags); - cnt = remove_redundant(rslt, cnt); + mark_redundant(rslt, cnt); result = NULL; for (i = 0; i < cnt; i++) - commit_list_insert_by_date(rslt[i], &result); + if (!(rslt[i]->object.flags & STALE)) + commit_list_insert_by_date(rslt[i], &result); + else + rslt[i]->object.flags &= ~STALE; free(rslt); return result; } @@ -1086,9 +1087,12 @@ struct commit_list *reduce_heads(struct commit_list *heads) p->item->object.flags &= ~STALE; } } - num_head = remove_redundant(array, num_head); + mark_redundant(array, num_head); for (i = 0; i < num_head; i++) - tail = &commit_list_insert(array[i], tail)->next; + if (!(array[i]->object.flags & STALE)) + tail = &commit_list_insert(array[i], tail)->next; + else + array[i]->object.flags &= ~STALE; return result; }
-- 2.10.1-631-gb2c64dcf30