Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()
flat view
From: Junio C Hamano <hidden>
Date: 2021-01-28 20:54:00
"Derrick Stolee via GitGitGadget" [off-list ref] writes:
quoted hunk
+ /* Mark all parents of the input as STALE */ + for (i = 0; i < cnt; i++) { + struct commit_list *parents; + timestamp_t generation; repo_parse_commit(r, array[i]); + parents = array[i]->parents; + + while (parents) { + repo_parse_commit(r, parents->item); + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + prio_queue_put(&queue, parents->item); + } + parents = parents->next; + } + + generation = commit_graph_generation(array[i]); + + if (generation < min_generation) + min_generation = generation; + } + + /* push the STALE bits up to min generation */ + while (queue.nr) { + struct commit_list *parents; + struct commit *c = prio_queue_get(&queue); + + repo_parse_commit(r, c); + if (commit_graph_generation(c) < min_generation) continue; + parents = c->parents; + while (parents) { + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + prio_queue_put(&queue, parents->item); + } + parents = parents->next; + } + }
So, the inner loop makes sure we won't revisit STALE parent, but keep digging parents we haven't seen, and stop when the generation is old enough. What happens when there is no generation number computed yet, I wonder... We'll keep getting infinity and dig all the way down to root?
quoted hunk
+ /* rearrange array */ + dup = xcalloc(cnt, sizeof(struct commit *)); + COPY_ARRAY(dup, array, cnt); + for (i = 0; i < cnt; i++) { + if (dup[i]->object.flags & STALE) { + int insert = cnt - 1 - (i - count_non_stale); + array[insert] = dup[i]; + } else { + array[count_non_stale] = dup[i]; + count_non_stale++; + } + } + free(dup);
The "fill stale ones from the end, non-stale ones from the
beginning" in the loop looks unnecessarily complex to me. I wonder
if we can do only the "fill non-stale ones from the beginning" half,
i.e.
for (i = count_non_stale = 0; i < cnt; i++) {
if (dup[i] is not stale)
array[count_non_stale++] = dup[i];
}
without the "keep the stale one at the end of array[]", and clear
marks using what is in dup[] as starting points before discarding
dup[]?
Or do the callers still look at the entries beyond count_non_stale?
Other than that, nicely done.
quoted hunk
+ /* clear marks */ + for (i = 0; i < cnt; i++) { + struct commit_list *parents; + parents = array[i]->parents; + + while (parents) { + clear_commit_marks(parents->item, STALE); + parents = parents->next; } - common = paint_down_to_common(r, array[i], filled, - work, min_generation); - 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); - clear_commit_marks_many(filled, work, all_flags); - 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++) - if (redundant[i]) - array[j++] = work[i]; - free(work); - free(redundant); - free(filled_index); - return filled; + return count_non_stale; } static struct commit_list *get_merge_bases_many_0(struct repository *r,