Function remove_redundant_with_gen

commit-reach.c:339–456

}

static int remove_redundant_with_gen(struct repository *r,
				     struct commit **array, size_t cnt,
				     size_t *dedup_cnt)
{
	size_t i, count_non_stale = 0, count_still_independent = cnt;
	timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
	struct commit **sorted;
	struct commit_stack walk_start = COMMIT_STACK_INIT;
	size_t min_gen_pos = 0;

	/*
	 * Sort the input by generation number, ascending. This allows
	 * us to increase the "min_generation" limit when we discover
	 * the commit with lowest generation is STALE. The index
	 * min_gen_pos points to the current position within 'array'
	 * that is not yet known to be STALE.
	 */
	DUP_ARRAY(sorted, array, cnt);
	QSORT(sorted, cnt, compare_commits_by_gen);
	min_generation = commit_graph_generation(sorted[0]);

	commit_stack_grow(&walk_start, cnt);

	/* Mark all parents of the input as STALE */
	for (i = 0; i < cnt; i++) {
		struct commit_list *parents;

		repo_parse_commit(r, array[i]);
		array[i]->object.flags |= RESULT;
		parents = array[i]->parents;

		while (parents) {
			repo_parse_commit(r, parents->item);
			if (!(parents->item->object.flags & STALE)) {
				parents->item->object.flags |= STALE;
				commit_stack_push(&walk_start, parents->item);
			}
			parents = parents->next;
		}
	}

	QSORT(walk_start.items, walk_start.nr, compare_commits_by_gen);

	/* remove STALE bit for now to allow walking through parents */
	for (i = 0; i < walk_start.nr; i++)
		walk_start.items[i]->object.flags &= ~STALE;

	/*
	 * Start walking from the highest generation. Hopefully, it will
	 * find all other items during the first-parent walk, and we can
	 * terminate early. Otherwise, we will do the same amount of work
	 * as before.
	 */
	for (i = walk_start.nr; i && count_still_independent > 1; i--) {
		/* push the STALE bits up to min generation */
		struct commit_list *stack = NULL;

		commit_list_insert(walk_start.items[i - 1], &stack);