[v4,0/7] reftable: improvements for the `binsearch()` mechanism

Message

Patrick Steinhardt April 3, 2024, 6:03 a.m. UTC

Hi,

this is the fourth and hopefully final version of my patch series that
refactors the `binsearch()` mechanism in the reftable library.

There's only a single change compared to v3, which is a fix to a comment
that was misexplaining one of the cases when searching for the restart
points.

Thanks!

Patrick

Patrick Steinhardt (7):
  reftable/basics: fix return type of `binsearch()` to be `size_t`
  reftable/basics: improve `binsearch()` test
  reftable/refname: refactor binary search over refnames
  reftable/block: refactor binary search over restart points
  reftable/block: fix error handling when searching restart points
  reftable/record: extract function to decode key lengths
  reftable/block: avoid decoding keys when searching restart points

 reftable/basics.c      |   7 ++-
 reftable/basics.h      |   7 +--
 reftable/basics_test.c |  55 ++++++++++---------
 reftable/block.c       | 117 ++++++++++++++++++++++++++++++-----------
 reftable/record.c      |  34 ++++++++----
 reftable/record.h      |   6 +++
 reftable/refname.c     |  53 +++++++++----------
 7 files changed, 182 insertions(+), 97 deletions(-)

Range-diff against v3:
1:  baa07ef144 = 1:  baa07ef144 reftable/basics: fix return type of `binsearch()` to be `size_t`
2:  cbc2a107c1 = 2:  cbc2a107c1 reftable/basics: improve `binsearch()` test
3:  f5bf65e0dd = 3:  f5bf65e0dd reftable/refname: refactor binary search over refnames
4:  435cd0be94 ! 4:  6d4a79f3e2 reftable/block: refactor binary search over restart points
    @@ reftable/block.c: int block_reader_seek(struct block_reader *br, struct block_it
     +	/*
     +	 * Now there are multiple cases:
     +	 *
    -+	 *   - `i == 0`: The wanted record must be contained before the first
    -+	 *     restart point. We will thus start searching for the record in
    -+	 *     that section after accounting for the header offset.
    ++	 *   - `i == 0`: The wanted record is smaller than the record found at
    ++	 *     the first restart point. As the first restart point is the first
    ++	 *     record in the block, our wanted record cannot be located in this
    ++	 *     block at all. We still need to position the iterator so that the
    ++	 *     next call to `block_iter_next()` will yield an end-of-iterator
    ++	 *     signal.
     +	 *
     +	 *   - `i == restart_count`: The wanted record was not found at any of
     +	 *     the restart points. As there is no restart point at the end of
5:  8d8abfd290 = 5:  52c238ee9f reftable/block: fix error handling when searching restart points
6:  f87f7ad01a = 6:  ca41ad30f4 reftable/record: extract function to decode key lengths
7:  f53bf9e1cc = 7:  632f725dde reftable/block: avoid decoding keys when searching restart points