Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()

["René Scharfe" <l.s.r@web.de>]

Am 28.01.21 um 21:51 schrieb Junio C Hamano:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>> +	/* 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?

Had the same reaction.  Both callers ignore the stale entries.

> Other than that, nicely done.
>
>> +	/* 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;
>>  		}

This loop clears STALE from the parents of both the non-stale and
stale entries.  OK.  Should it also clear it from the stale entries
themselves?

>> -		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,