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
