Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative

From: Taylor Blau <me@ttaylorr.com>
Date: May 28, 2021, 01:32 UTC
Message-ID: <YLBIIL+yShDVlWo5@nand.local>
In-Reply-To: <5055dfce32815c8c8ec250457df389d4cd02ee12.1622104642.git.gitgitgadget@gmail.com>

On Thu, May 27, 2021 at 08:37:17AM +0000, Elijah Newren via GitGitGadget wrote:

> -static int string_list_df_name_compare(const char *one, const char *two)
> +static int sort_dirs_next_to_their_children(const void *a, const void *b)

I looked at the new implementation of this function (and df_name_compare() to double check it) and am convinced that it's correctness, with the exception of one question.

Some thoughts I had while trying to make sure this was all OK:

Show 8 quoted lines

> +	const char *one = ((struct string_list_item *)a)->string;
> +	const char *two = ((struct string_list_item *)b)->string;
> +	unsigned char c1, c2;
> +
> +	while (*one && (*one == *two)) {
> +		one++;
> +		two++;
> +	}

Advancing 'one' and 'two' to point at either the end of 'a' (and the same position within 'b'), or the first place where the two have different characters. If 'b' is shorter than 'a', '*one != *two' will terminate the loop (since '*two' will be NUL, and '*one' will not).

Show 7 quoted lines

> +	c1 = *one;
> +	if (!c1)
> +		c1 = '/';
> +
> +	c2 = *two;
> +	if (!c2)
> +		c2 = '/';

Store off the last character of each, or '/' if we got to the end. Hmm, is this right (the guard in 'df_name_compare()' read 'if (!c1 && S_ISDIR(mode1))'). Suppose both strings were "foo", then both c1 and c2 would be "/", and I think we would return -1.

That doesn't seem quite right to me. I think it *would* be right if we checked the mode of each entry before assigning c1 or c2 to '/', though. (Being generally unfamiliar with this area, I haven't looked to see whether getting access to the modes of each entry at this point is easy or not).

Show 5 quoted lines

> +
> +	if (c1 == c2) {
> +		/* Getting here means one is a leading directory of the other */
> +		return (*one) ? 1 : -1;
> +	}

> +	else

I did find this spacing awkward (would have expected '} else' or even '} else {'), but it hardly matters.

Thanks, Taylor