]> git.hungrycats.org Git - bees/commit
seeker: harden against changes in the data during binary search
authorZygo Blaxell <bees@furryterror.org>
Thu, 13 Feb 2025 02:26:33 +0000 (21:26 -0500)
committerZygo Blaxell <bees@furryterror.org>
Thu, 19 Jun 2025 01:17:48 +0000 (21:17 -0400)
commitb1bd99c077a1e121fb3989b5655eba3387b07f5b
treec62b8f7a85df9c3c67bc42162815a0c58d18b2e7
parentd5e805ab8dbfa683087e360e40e61196fad6b21c
seeker: harden against changes in the data during binary search

During the search, the region between `upper_bound` and `target_pos`
should contain no data items.  The search lowers `upper_bound` and raises
`lower_bound` until they both point to the last item before `target_pos`.

The `lower_bound` is increased to the position of the last item returned
by a search (`high_pos`) when that item is lower than `target_pos`.
This avoids some loop iterations compared to a strict binary search
algorithm, which would increase `lower_bound` only as far as `probe_pos`.

When the search runs over live extent items, occasionally a new extent
will appear between `upper_bound` and `target_pos`.  When this happens,
`lower_bound` is bumped up to the position of one of the new items, but
that position is in the "unoccupied" space between `upper_bound` and
`target_pos`, where no items are supposed to exist, so `seek_backward`
throws an exception.

To cut down on the noise, only increase `lower_bound` as far as
`upper_bound`.  This avoids the exception without increasing the number
of loop iterations for normal cases.

In the exceptional cases, extra loop iterations are needed to skip over
the new items.  This raises the worst-case number of loop iterations
by one.

Signed-off-by: Zygo Blaxell <bees@furryterror.org>
include/crucible/seeker.h