Skip to content

reftable: improvements for the `binsearch()` mechanism

Patrick Steinhardt git 4 versions – New

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest7 patches 0 repliesNew
  2. v37 patches 1 replySuperseded
  3. v27 patches 8 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v17 patches4 repliesSuperseded

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/7reftable/basics: fix return type of `binsearch()` to be `size_t`reftable/basics.c reftable/basics.h reftable/basics_test.c +2 more+14 -160 replies
2/7reftable/basics: improve `binsearch()` testreftable/basics_test.c+31 -240 replies
3/7reftable/refname: refactor binary search over refnamesreftable/refname.c+22 -220 replies
4/7reftable/block: refactor binary search over restart pointsreftable/block.c+73 -270 replies
5/7reftable/block: fix error handling when searching restart pointsreftable/basics.c reftable/basics.h reftable/block.c+11 -80 replies
6/7reftable/record: extract function to decode key lengthsreftable/record.c reftable/record.h+31 -90 replies
7/7reftable/block: avoid decoding keys when searching restart pointsreftable/block.c+19 -100 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v4 yet.

Read the v4 thread

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

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
Signature · 1 line
2.44.GIT