reftable: improvements for the `binsearch()` mechanism
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v4 Latest7 patches 0 repliesNew
- v37 patches 1 replySuperseded
- v27 patches 8 repliesSuperseded
Earlier versions · 1
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v1 | 7 patches | 4 replies | Superseded |
Patches in v4 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/7 | reftable/basics: fix return type of `binsearch()` to be `size_t`reftable/ reftable/ reftable/ +2 more | +14 | 0 replies | |
| 2/7 | reftable/basics: improve `binsearch()` testreftable/ | +31 | 0 replies | |
| 3/7 | reftable/refname: refactor binary search over refnamesreftable/ | +22 | 0 replies | |
| 4/7 | reftable/block: refactor binary search over restart pointsreftable/ | +73 | 0 replies | |
| 5/7 | reftable/block: fix error handling when searching restart pointsreftable/ reftable/ reftable/ | +11 | 0 replies | |
| 6/7 | reftable/record: extract function to decode key lengthsreftable/ reftable/ | +31 | 0 replies | |
| 7/7 | reftable/block: avoid decoding keys when searching restart pointsreftable/ | +19 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v4 yet.
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 pointsSignature · 1 line
2.44.GIT