Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Wed, Jan 24, 2018 at 01:11:00PM -0800, Junio C Hamano wrote:

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

Er, yeah. Sorry about that.

> 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 thought at first that this was due to the way the record-finding
happens, but I think even in our normal binary searches, it is an
invariant that "lo <= hi".

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

Yes, I agree that would also work.

-Peff



[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]

  Powered by Linux