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
--
2.44.GIT
Attachment:
signature.asc
Description: PGP signature
