Jeff King <peff@xxxxxxxx> writes:
> On Wed, Jan 24, 2018 at 12:14:13PM +0100, Michael Haggerty wrote:
>
>> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
>> index 08698de6ea..361affd7ad 100644
>> --- a/refs/packed-backend.c
>> +++ b/refs/packed-backend.c
>> [...]
>> @@ -551,7 +553,7 @@ static const char *find_reference_location(struct snapshot *snapshot,
>> */
>> const char *hi = snapshot->eof;
>>
>> - while (lo < hi) {
>> + while (lo != hi) {
>> const char *mid, *rec;
>> int cmp;
>
> This tightens the binary search termination condition. If we ever did
> see "hi > lo", we'd want to terminate the loop. Is that ever possible?
I think you meant "lo > hi", but I shared the same "Huh?" moment.
Because "While lo is strictly lower than hi" is a so well
established binary search pattern, even though we know that it is
equivalent to "While lo and hi is different" due to your analysis
below, the new code looks somewhat strange at the first glance.
> I think the answer is "no". Our "hi" here is an exclusive bound, so we
> should never go past it via find_end_of_record() when assigning "lo".
> And "hi" is always assigned from the start of the current record. That
> can never cross "lo", because find_start_of_record() ensures it.
>
> So I think it's fine, but I wanted to double check.
It would be much simpler to reason about if we instead do
#define is_empty_snapshot(s) ((s)->start == NULL)
if (is_empty_snapshot(snapshot))
return NULL;
or something like that upfront.
