{"thread":{"id":"61433","subject":"[PATCH 00/13] reftable: prepare for re-seekable iterators","startedAt":"2024-05-08T11:03:40Z","lastAt":"2024-05-22T07:56:07Z","messageCount":50,"participants":["Patrick Steinhardt","Junio C Hamano","Justin Tobler","Karthik Nayak"],"isPatch":true,"patchVersion":1,"patchTotal":13},"messages":[{"id":"494298","messageId":"cover.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":null,"subject":"[PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:03:33Z","receivedAt":"2024-05-08T11:03:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthe reftable library uses iterators both to iterate through a set of\nrecords, but also to look up a single record. In past patch series, I\nhave focussed quite a lot to optimize the case where we iterate through\na large set of records. But looking up a records is still quite\ninefficient when doing multiple lookups. This is because whenever we\nwant to look up a record, we need to create a new iterator, including\nall of its internal data structures.\n\nTo address this inefficiency, the patch series at hand refactors the\nreftable library such that creation of iterators and seeking on an\niterator are separate steps. This refactoring prepares us for reusing\niterators to perform multiple seeks, which in turn will allow us to\nreuse internal data structures for subsequent seeks.\n\nThe patch series is structured as follows:\n\n - Patches 1 to 5 perform some general cleanups to make the reftable\n iterators easier to understand.\n\n - Patchges 6 to 9 refactor the iterators internally such that creation\n of the iterator and seeking on it is clearly separated.\n\n - Patches 10 to 13 adapt the external interfaces such that they allow\n for reuse of iterators.\n\nNote: this series does not yet go all the way to re-seekable iterators,\nand there are no users yet. The patch series is complex enough as-is\nalready, so I decided to defer that to the next iteration. Thus, the\nwhole refactoring here should essentially be a large no-op that prepares\nthe infrastructure for re-seekable iterators.\n\nThe series depends on pks/reftable-write-optim at fa74f32291\n(reftable/block: reuse compressed array, 2024-04-08).\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (13):\n reftable/block: use `size_t` to track restart point index\n reftable/reader: avoid copying index iterator\n reftable/reader: unify indexed and linear seeking\n reftable/reader: separate concerns of table iter and reftable reader\n reftable/reader: inline `reader_seek_internal()`\n reftable/reader: set up the reader when initializing table iterator\n reftable/merged: split up initialization and seeking of records\n reftable/merged: simplify indices for subiterators\n reftable/generic: move seeking of records into the iterator\n reftable/generic: adapt interface to allow reuse of iterators\n reftable/reader: adapt interface to allow reuse of iterators\n reftable/stack: provide convenience functions to create iterators\n reftable/merged: adapt interface to allow reuse of iterators\n\n refs/reftable-backend.c | 48 ++++----\n reftable/block.c | 4 +-\n reftable/generic.c | 94 +++++++++++----\n reftable/generic.h | 9 +-\n reftable/iter.c | 23 +++-\n reftable/merged.c | 148 ++++++++----------------\n reftable/merged.h | 6 +\n reftable/merged_test.c | 19 ++-\n reftable/reader.c | 218 +++++++++++++++--------------------\n reftable/readwrite_test.c | 35 ++++--\n reftable/reftable-generic.h | 8 +-\n reftable/reftable-iterator.h | 21 ++++\n reftable/reftable-merged.h | 15 ---\n reftable/reftable-reader.h | 45 ++------\n reftable/reftable-stack.h | 18 +++\n reftable/stack.c | 29 ++++-\n 16 files changed, 378 insertions(+), 362 deletions(-)\n\n-- \n2.45.0\n\n"},{"id":"494299","messageId":"ca86a8b58dd074287dd2dd352610ffe46e1605b9.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 01/13] reftable/block: use `size_t` to track restart point index","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:03:38Z","receivedAt":"2024-05-08T11:03:49Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `block_reader_restart_offset()` gets the offset of the\n`i`th restart point. `i` is a signed integer though, which is certainly\nnot the correct type to track indices like this. Furthermore, both\ncallers end up passing a `size_t`.\n\nRefactor the code to use a `size_t` instead.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 5942cb4053..00030eee06 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -326,9 +326,9 @@ int block_reader_first_key(const struct block_reader *br, struct strbuf *key)\n \treturn 0;\n }\n \n-static uint32_t block_reader_restart_offset(const struct block_reader *br, int i)\n+static uint32_t block_reader_restart_offset(const struct block_reader *br, size_t idx)\n {\n-\treturn get_be24(br->restart_bytes + 3 * i);\n+\treturn get_be24(br->restart_bytes + 3 * idx);\n }\n \n void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)\n-- \n2.45.0\n\n"},{"id":"494300","messageId":"bdbebdbd363fc264c6327e7bf0af29ee5357e83d.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 02/13] reftable/reader: avoid copying index iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:03:42Z","receivedAt":"2024-05-08T11:03:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing an indexed seek we need to walk down the multi-level index\nuntil we finally hit a record of the desired indexed type. This loop\nperforms a copy of the index iterator on every iteration, which is both\nhard to understand and completely unnecessary.\n\nRefactor the code so that we use a single iterator to walk down the\nindices, only.\n\nNote that while this should improve performance, the improvement is\nnegligible in all but the most unreasonable repositories. This is\nbecause the effect is only really noticeable when we have to walk down\nmany levels of indices, which is not something that a repository would\ntypically have. So the motivation for this change is really only about\nreadability.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 38 ++++++++++++++------------------------\n 1 file changed, 14 insertions(+), 24 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 481dff10d4..6bfadcad71 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -510,13 +510,11 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t.type = BLOCK_TYPE_INDEX,\n \t\t.u.idx = { .last_key = STRBUF_INIT },\n \t};\n-\tstruct table_iter index_iter = TABLE_ITER_INIT;\n-\tstruct table_iter empty = TABLE_ITER_INIT;\n-\tstruct table_iter next = TABLE_ITER_INIT;\n+\tstruct table_iter ti = TABLE_ITER_INIT, *malloced;\n \tint err = 0;\n \n \treftable_record_key(rec, &want_index.u.idx.last_key);\n-\terr = reader_start(r, &index_iter, reftable_record_type(rec), 1);\n+\terr = reader_start(r, &ti, reftable_record_type(rec), 1);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -526,7 +524,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t * highest layer that identifies the relevant index block as well as\n \t * the record inside that block that corresponds to our wanted key.\n \t */\n-\terr = reader_seek_linear(&index_iter, &want_index);\n+\terr = reader_seek_linear(&ti, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -552,44 +550,36 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t * all levels of the index only to find out that the key does\n \t\t * not exist.\n \t\t */\n-\t\terr = table_iter_next(&index_iter, &index_result);\n+\t\terr = table_iter_next(&ti, &index_result);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = reader_table_iter_at(r, &next, index_result.u.idx.offset,\n-\t\t\t\t\t 0);\n+\t\terr = reader_table_iter_at(r, &ti, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek_key(&next.bi, &next.br, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&ti.bi, &ti.br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\tif (next.typ == reftable_record_type(rec)) {\n+\t\tif (ti.typ == reftable_record_type(rec)) {\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (next.typ != BLOCK_TYPE_INDEX) {\n+\t\tif (ti.typ != BLOCK_TYPE_INDEX) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n-\t\t\tbreak;\n+\t\t\tgoto done;\n \t\t}\n-\n-\t\ttable_iter_close(&index_iter);\n-\t\tindex_iter = next;\n-\t\tnext = empty;\n \t}\n \n-\tif (err == 0) {\n-\t\tstruct table_iter *malloced = reftable_calloc(1, sizeof(*malloced));\n-\t\t*malloced = next;\n-\t\tnext = empty;\n-\t\titerator_from_table_iter(it, malloced);\n-\t}\n+\tREFTABLE_ALLOC_ARRAY(malloced, 1);\n+\t*malloced = ti;\n+\titerator_from_table_iter(it, malloced);\n \n done:\n-\ttable_iter_close(&next);\n-\ttable_iter_close(&index_iter);\n+\tif (err)\n+\t\ttable_iter_close(&ti);\n \treftable_record_release(&want_index);\n \treftable_record_release(&index_result);\n \treturn err;\n-- \n2.45.0\n\n"},{"id":"494301","messageId":"716863a580f9e1ef8ea796c25c97e50c63585a7b.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 03/13] reftable/reader: unify indexed and linear seeking","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:03:47Z","receivedAt":"2024-05-08T11:03:51Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In `reader_seek_internal()` we either end up doing an indexed seek when\nthere is one or a linear seek otherwise. These two code paths are\ndisjunct without a good reason, where the indexed seek will cause us to\nexit early.\n\nRefactor the two code paths such that it becomes possible to share a bit\nmore code between them.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 42 ++++++++++++++++--------------------------\n 1 file changed, 16 insertions(+), 26 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 6bfadcad71..cf7f126d8d 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -425,7 +425,7 @@ static int reader_seek_linear(struct table_iter *ti,\n \tstruct strbuf want_key = STRBUF_INIT;\n \tstruct strbuf got_key = STRBUF_INIT;\n \tstruct reftable_record rec;\n-\tint err = -1;\n+\tint err;\n \n \treftable_record_init(&rec, reftable_record_type(want));\n \treftable_record_key(want, &want_key);\n@@ -499,8 +499,8 @@ static int reader_seek_linear(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek_indexed(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it,\n+static int reader_seek_indexed(struct table_iter *ti,\n+\t\t\t struct reftable_reader *r,\n \t\t\t struct reftable_record *rec)\n {\n \tstruct reftable_record want_index = {\n@@ -510,13 +510,9 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t.type = BLOCK_TYPE_INDEX,\n \t\t.u.idx = { .last_key = STRBUF_INIT },\n \t};\n-\tstruct table_iter ti = TABLE_ITER_INIT, *malloced;\n-\tint err = 0;\n+\tint err;\n \n \treftable_record_key(rec, &want_index.u.idx.last_key);\n-\terr = reader_start(r, &ti, reftable_record_type(rec), 1);\n-\tif (err < 0)\n-\t\tgoto done;\n \n \t/*\n \t * The index may consist of multiple levels, where each level may have\n@@ -524,7 +520,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t * highest layer that identifies the relevant index block as well as\n \t * the record inside that block that corresponds to our wanted key.\n \t */\n-\terr = reader_seek_linear(&ti, &want_index);\n+\terr = reader_seek_linear(ti, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -550,36 +546,30 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t * all levels of the index only to find out that the key does\n \t\t * not exist.\n \t\t */\n-\t\terr = table_iter_next(&ti, &index_result);\n+\t\terr = table_iter_next(ti, &index_result);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = reader_table_iter_at(r, &ti, index_result.u.idx.offset, 0);\n+\t\terr = reader_table_iter_at(r, ti, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek_key(&ti.bi, &ti.br, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&ti->bi, &ti->br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\tif (ti.typ == reftable_record_type(rec)) {\n+\t\tif (ti->typ == reftable_record_type(rec)) {\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (ti.typ != BLOCK_TYPE_INDEX) {\n+\t\tif (ti->typ != BLOCK_TYPE_INDEX) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n \t\t\tgoto done;\n \t\t}\n \t}\n \n-\tREFTABLE_ALLOC_ARRAY(malloced, 1);\n-\t*malloced = ti;\n-\titerator_from_table_iter(it, malloced);\n-\n done:\n-\tif (err)\n-\t\ttable_iter_close(&ti);\n \treftable_record_release(&want_index);\n \treftable_record_release(&index_result);\n \treturn err;\n@@ -595,15 +585,15 @@ static int reader_seek_internal(struct reftable_reader *r,\n \tstruct table_iter ti = TABLE_ITER_INIT, *p;\n \tint err;\n \n-\tif (idx > 0)\n-\t\treturn reader_seek_indexed(r, it, rec);\n-\n-\terr = reader_start(r, &ti, reftable_record_type(rec), 0);\n+\terr = reader_start(r, &ti, reftable_record_type(rec), !!idx);\n \tif (err < 0)\n \t\tgoto out;\n \n-\terr = reader_seek_linear(&ti, rec);\n-\tif (err < 0)\n+\tif (idx)\n+\t\terr = reader_seek_indexed(&ti, r, rec);\n+\telse\n+\t\terr = reader_seek_linear(&ti, rec);\n+\tif (err)\n \t\tgoto out;\n \n \tREFTABLE_ALLOC_ARRAY(p, 1);\n-- \n2.45.0\n\n"},{"id":"494302","messageId":"91db2f18c105611bc85fa07fa6eb33ba600e742a.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 04/13] reftable/reader: separate concerns of table iter and reftable reader","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:03:51Z","receivedAt":"2024-05-08T11:03:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In \"reftable/reader.c\" we implement two different interfaces:\n\n - The reftable reader contains the logic to read reftables.\n\n - The table iterator is used to iterate through a single reftable read\n by the reader.\n\nThe way those two types are used in the code is somewhat confusing\nthough because seeking inside a table is implemented as if it was part\nof the reftable reader, even though it is ultimately more of a detail\nimplemented by the table iterator.\n\nMake the boundary between those two types clearer by renaming functions\nthat seek records in a table such that they clearly belong to the table\niterator's logic.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 32 +++++++++++++++-----------------\n 1 file changed, 15 insertions(+), 17 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex cf7f126d8d..b210753441 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -386,9 +386,8 @@ static void iterator_from_table_iter(struct reftable_iterator *it,\n \tit->ops = &table_iter_vtable;\n }\n \n-static int reader_table_iter_at(struct reftable_reader *r,\n-\t\t\t\tstruct table_iter *ti, uint64_t off,\n-\t\t\t\tuint8_t typ)\n+static int table_iter_seek_to(struct table_iter *ti, struct reftable_reader *r,\n+\t\t\t uint64_t off, uint8_t typ)\n {\n \tint err;\n \n@@ -403,8 +402,8 @@ static int reader_table_iter_at(struct reftable_reader *r,\n \treturn 0;\n }\n \n-static int reader_start(struct reftable_reader *r, struct table_iter *ti,\n-\t\t\tuint8_t typ, int index)\n+static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader *r,\n+\t\t\t\t uint8_t typ, int index)\n {\n \tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n \tuint64_t off = offs->offset;\n@@ -416,11 +415,11 @@ static int reader_start(struct reftable_reader *r, struct table_iter *ti,\n \t\ttyp = BLOCK_TYPE_INDEX;\n \t}\n \n-\treturn reader_table_iter_at(r, ti, off, typ);\n+\treturn table_iter_seek_to(ti, r, off, typ);\n }\n \n-static int reader_seek_linear(struct table_iter *ti,\n-\t\t\t struct reftable_record *want)\n+static int table_iter_seek_linear(struct table_iter *ti,\n+\t\t\t\t struct reftable_record *want)\n {\n \tstruct strbuf want_key = STRBUF_INIT;\n \tstruct strbuf got_key = STRBUF_INIT;\n@@ -499,9 +498,8 @@ static int reader_seek_linear(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek_indexed(struct table_iter *ti,\n-\t\t\t struct reftable_reader *r,\n-\t\t\t struct reftable_record *rec)\n+static int table_iter_seek_indexed(struct table_iter *ti,\n+\t\t\t\t struct reftable_record *rec)\n {\n \tstruct reftable_record want_index = {\n \t\t.type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }\n@@ -520,7 +518,7 @@ static int reader_seek_indexed(struct table_iter *ti,\n \t * highest layer that identifies the relevant index block as well as\n \t * the record inside that block that corresponds to our wanted key.\n \t */\n-\terr = reader_seek_linear(ti, &want_index);\n+\terr = table_iter_seek_linear(ti, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -550,7 +548,7 @@ static int reader_seek_indexed(struct table_iter *ti,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = reader_table_iter_at(r, ti, index_result.u.idx.offset, 0);\n+\t\terr = table_iter_seek_to(ti, ti->r, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n@@ -585,14 +583,14 @@ static int reader_seek_internal(struct reftable_reader *r,\n \tstruct table_iter ti = TABLE_ITER_INIT, *p;\n \tint err;\n \n-\terr = reader_start(r, &ti, reftable_record_type(rec), !!idx);\n+\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec), !!idx);\n \tif (err < 0)\n \t\tgoto out;\n \n \tif (idx)\n-\t\terr = reader_seek_indexed(&ti, r, rec);\n+\t\terr = table_iter_seek_indexed(&ti, rec);\n \telse\n-\t\terr = reader_seek_linear(&ti, rec);\n+\t\terr = table_iter_seek_linear(&ti, rec);\n \tif (err)\n \t\tgoto out;\n \n@@ -742,7 +740,7 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,\n \tint err;\n \n \t*ti = ti_empty;\n-\terr = reader_start(r, ti, BLOCK_TYPE_REF, 0);\n+\terr = table_iter_seek_start(ti, r, BLOCK_TYPE_REF, 0);\n \tif (err < 0) {\n \t\treftable_free(ti);\n \t\treturn err;\n-- \n2.45.0\n\n"},{"id":"494303","messageId":"4d498ef3426877c703bababaa743dd5613ba5839.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 05/13] reftable/reader: inline `reader_seek_internal()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:03:56Z","receivedAt":"2024-05-08T11:04:00Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have both `reader_seek()` and `reader_seek_internal()`, where the\nformer function only exists so that we can exit early in case the given\ntable has no records of the sought-after type.\n\nMerge these two functions into one.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 34 ++++++++++++----------------------\n 1 file changed, 12 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex b210753441..c3541e2c43 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -573,21 +573,25 @@ static int table_iter_seek_indexed(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek_internal(struct reftable_reader *r,\n-\t\t\t\tstruct reftable_iterator *it,\n-\t\t\t\tstruct reftable_record *rec)\n+static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n+\t\t struct reftable_record *rec)\n {\n-\tstruct reftable_reader_offsets *offs =\n-\t\treader_offsets_for(r, reftable_record_type(rec));\n-\tuint64_t idx = offs->index_offset;\n+\tuint8_t typ = reftable_record_type(rec);\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n \tstruct table_iter ti = TABLE_ITER_INIT, *p;\n \tint err;\n \n-\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec), !!idx);\n+\tif (!offs->is_present) {\n+\t\titerator_set_empty(it);\n+\t\treturn 0;\n+\t}\n+\n+\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec),\n+\t\t\t\t !!offs->index_offset);\n \tif (err < 0)\n \t\tgoto out;\n \n-\tif (idx)\n+\tif (offs->index_offset)\n \t\terr = table_iter_seek_indexed(&ti, rec);\n \telse\n \t\terr = table_iter_seek_linear(&ti, rec);\n@@ -604,20 +608,6 @@ static int reader_seek_internal(struct reftable_reader *r,\n \treturn err;\n }\n \n-static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n-\t\t struct reftable_record *rec)\n-{\n-\tuint8_t typ = reftable_record_type(rec);\n-\n-\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n-\tif (!offs->is_present) {\n-\t\titerator_set_empty(it);\n-\t\treturn 0;\n-\t}\n-\n-\treturn reader_seek_internal(r, it, rec);\n-}\n-\n int reftable_reader_seek_ref(struct reftable_reader *r,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n-- \n2.45.0\n\n"},{"id":"494304","messageId":"5a10a115841512a46e4d3a3d3713e5532facdb39.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 06/13] reftable/reader: set up the reader when initializing table iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:01Z","receivedAt":"2024-05-08T11:04:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"All the seeking functions accept a `struct reftable_reader` as input\nsuch that they can use the reader to look up the respective blocks.\nRefactor the code to instead set up the reader as a member of `struct\ntable_iter` during initialization such that we don't have to pass the\nreader on every single call.\n\nThis step is required to move seeking of records into the generic\n`struct reftable_iterator` infrastructure.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 39 ++++++++++++++++++++++-----------------\n 1 file changed, 22 insertions(+), 17 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex c3541e2c43..021608f638 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -224,8 +224,14 @@ struct table_iter {\n \tstruct block_iter bi;\n \tint is_finished;\n };\n-#define TABLE_ITER_INIT { \\\n-\t.bi = BLOCK_ITER_INIT \\\n+\n+static int table_iter_init(struct table_iter *ti, struct reftable_reader *r)\n+{\n+\tstruct block_iter bi = BLOCK_ITER_INIT;\n+\tmemset(ti, 0, sizeof(*ti));\n+\tti->r = r;\n+\tti->bi = bi;\n+\treturn 0;\n }\n \n static int table_iter_next_in_block(struct table_iter *ti,\n@@ -386,26 +392,23 @@ static void iterator_from_table_iter(struct reftable_iterator *it,\n \tit->ops = &table_iter_vtable;\n }\n \n-static int table_iter_seek_to(struct table_iter *ti, struct reftable_reader *r,\n-\t\t\t uint64_t off, uint8_t typ)\n+static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)\n {\n \tint err;\n \n-\terr = reader_init_block_reader(r, &ti->br, off, typ);\n+\terr = reader_init_block_reader(ti->r, &ti->br, off, typ);\n \tif (err != 0)\n \t\treturn err;\n \n-\tti->r = r;\n \tti->typ = block_reader_type(&ti->br);\n \tti->block_off = off;\n \tblock_iter_seek_start(&ti->bi, &ti->br);\n \treturn 0;\n }\n \n-static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader *r,\n-\t\t\t\t uint8_t typ, int index)\n+static int table_iter_seek_start(struct table_iter *ti, uint8_t typ, int index)\n {\n-\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(ti->r, typ);\n \tuint64_t off = offs->offset;\n \tif (index) {\n \t\toff = offs->index_offset;\n@@ -415,7 +418,7 @@ static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader *\n \t\ttyp = BLOCK_TYPE_INDEX;\n \t}\n \n-\treturn table_iter_seek_to(ti, r, off, typ);\n+\treturn table_iter_seek_to(ti, off, typ);\n }\n \n static int table_iter_seek_linear(struct table_iter *ti,\n@@ -548,7 +551,7 @@ static int table_iter_seek_indexed(struct table_iter *ti,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = table_iter_seek_to(ti, ti->r, index_result.u.idx.offset, 0);\n+\t\terr = table_iter_seek_to(ti, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n@@ -578,7 +581,7 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n {\n \tuint8_t typ = reftable_record_type(rec);\n \tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n-\tstruct table_iter ti = TABLE_ITER_INIT, *p;\n+\tstruct table_iter ti, *p;\n \tint err;\n \n \tif (!offs->is_present) {\n@@ -586,7 +589,9 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n \t\treturn 0;\n \t}\n \n-\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec),\n+\ttable_iter_init(&ti, r);\n+\n+\terr = table_iter_seek_start(&ti, reftable_record_type(rec),\n \t\t\t\t !!offs->index_offset);\n \tif (err < 0)\n \t\tgoto out;\n@@ -722,15 +727,15 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,\n \t\t\t\t\t struct reftable_iterator *it,\n \t\t\t\t\t uint8_t *oid)\n {\n-\tstruct table_iter ti_empty = TABLE_ITER_INIT;\n-\tstruct table_iter *ti = reftable_calloc(1, sizeof(*ti));\n+\tstruct table_iter *ti;\n \tstruct filtering_ref_iterator *filter = NULL;\n \tstruct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;\n \tint oid_len = hash_size(r->hash_id);\n \tint err;\n \n-\t*ti = ti_empty;\n-\terr = table_iter_seek_start(ti, r, BLOCK_TYPE_REF, 0);\n+\tREFTABLE_ALLOC_ARRAY(ti, 1);\n+\ttable_iter_init(ti, r);\n+\terr = table_iter_seek_start(ti, BLOCK_TYPE_REF, 0);\n \tif (err < 0) {\n \t\treftable_free(ti);\n \t\treturn err;\n-- \n2.45.0\n\n"},{"id":"494305","messageId":"21b3e3ab5f04e66fdd352187b1da699d1ab67cee.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 07/13] reftable/merged: split up initialization and seeking of records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:06Z","receivedAt":"2024-05-08T11:04:10Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"To initialize a `struct merged_iter`, we need to seek all subiterators\nto the wanted record and then add their results to the priority queue\nused to sort the records. This logic is split up across two functions,\n`merged_table_seek_record()` and `merged_table_iter()`. The scope of\nthese functions is somewhat weird though, where `merged_table_iter()` is\nonly responsible for adding the records of the subiterators to the\npriority queue.\n\nClarify the scope of those functions such that `merged_table_iter()` is\nonly responsible for initializing the iterator's structure. Performing\nthe subiterator seeks are now part of `merged_table_seek_record()`.\n\nThis step is required to move seeking of records into the generic\n`struct reftable_iterator` infrastructure.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 59 ++++++++++++++++++-----------------------------\n 1 file changed, 22 insertions(+), 37 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex f85a24c678..4e1b78e93f 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -25,34 +25,18 @@ struct merged_subiter {\n struct merged_iter {\n \tstruct merged_subiter *subiters;\n \tstruct merged_iter_pqueue pq;\n-\tuint32_t hash_id;\n \tsize_t stack_len;\n-\tuint8_t typ;\n \tint suppress_deletions;\n \tssize_t advance_index;\n };\n \n-static int merged_iter_init(struct merged_iter *mi)\n+static void merged_iter_init(struct merged_iter *mi,\n+\t\t\t struct reftable_merged_table *mt)\n {\n-\tfor (size_t i = 0; i < mi->stack_len; i++) {\n-\t\tstruct pq_entry e = {\n-\t\t\t.index = i,\n-\t\t\t.rec = &mi->subiters[i].rec,\n-\t\t};\n-\t\tint err;\n-\n-\t\treftable_record_init(&mi->subiters[i].rec, mi->typ);\n-\t\terr = iterator_next(&mi->subiters[i].iter,\n-\t\t\t\t &mi->subiters[i].rec);\n-\t\tif (err < 0)\n-\t\t\treturn err;\n-\t\tif (err > 0)\n-\t\t\tcontinue;\n-\n-\t\tmerged_iter_pqueue_add(&mi->pq, &e);\n-\t}\n-\n-\treturn 0;\n+\tmemset(mi, 0, sizeof(*mi));\n+\tmi->advance_index = -1;\n+\tmi->suppress_deletions = mt->suppress_deletions;\n+\tREFTABLE_CALLOC_ARRAY(mi->subiters, mt->stack_len);\n }\n \n static void merged_iter_close(void *p)\n@@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \t\t\t\t struct reftable_iterator *it,\n \t\t\t\t struct reftable_record *rec)\n {\n-\tstruct merged_iter merged = {\n-\t\t.typ = reftable_record_type(rec),\n-\t\t.hash_id = mt->hash_id,\n-\t\t.suppress_deletions = mt->suppress_deletions,\n-\t\t.advance_index = -1,\n-\t};\n-\tstruct merged_iter *p;\n+\tstruct merged_iter merged, *p;\n \tint err;\n \n-\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n+\tmerged_iter_init(&merged, mt);\n+\n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n+\t\treftable_record_init(&merged.subiters[merged.stack_len].rec,\n+\t\t\t\t reftable_record_type(rec));\n+\n \t\terr = reftable_table_seek_record(&mt->stack[i],\n \t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n-\t\tif (!err)\n-\t\t\tmerged.stack_len++;\n-\t}\n+\t\tif (err > 0)\n+\t\t\tcontinue;\n \n-\terr = merged_iter_init(&merged);\n-\tif (err < 0)\n-\t\tgoto out;\n+\t\terr = merged_iter_advance_subiter(&merged, merged.stack_len);\n+\t\tif (err < 0)\n+\t\t\tgoto out;\n+\n+\t\tmerged.stack_len++;\n+\t}\n \n-\tp = reftable_malloc(sizeof(struct merged_iter));\n+\tp = reftable_malloc(sizeof(*p));\n \t*p = merged;\n \titerator_from_merged_iter(it, p);\n+\terr = 0;\n \n out:\n \tif (err < 0)\n-- \n2.45.0\n\n"},{"id":"494306","messageId":"f0f42cd56b9e54e9c7d58be41fcc4e226d5c76ff.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 08/13] reftable/merged: simplify indices for subiterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:11Z","receivedAt":"2024-05-08T11:04:15Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking on a merged table, we perform the seek for each of the\nsubiterators. If the subiterator hasa the desired record we add it to\nthe priority queue, otherwise we skip it and don't add it to the stack\nof subiterators hosted by the merged table.\n\nThe consequence of this is that the index of the subiterator in the\nmerged table does not necessarily correspond to the index of it in the\nmerged iterator. Next to being potentially confusing, it also means that\nwe won't easily be able to re-seek the merged iterator because we have\nno clear connection between both of the data structures.\n\nRefactor the code so that the index stays the same in both structures.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 4e1b78e93f..18a2a6f09b 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -37,6 +37,7 @@ static void merged_iter_init(struct merged_iter *mi,\n \tmi->advance_index = -1;\n \tmi->suppress_deletions = mt->suppress_deletions;\n \tREFTABLE_CALLOC_ARRAY(mi->subiters, mt->stack_len);\n+\tmi->stack_len = mt->stack_len;\n }\n \n static void merged_iter_close(void *p)\n@@ -236,21 +237,19 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \tmerged_iter_init(&merged, mt);\n \n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n-\t\treftable_record_init(&merged.subiters[merged.stack_len].rec,\n+\t\treftable_record_init(&merged.subiters[i].rec,\n \t\t\t\t reftable_record_type(rec));\n \n \t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n+\t\t\t\t\t\t &merged.subiters[i].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n \t\tif (err > 0)\n \t\t\tcontinue;\n \n-\t\terr = merged_iter_advance_subiter(&merged, merged.stack_len);\n+\t\terr = merged_iter_advance_subiter(&merged, i);\n \t\tif (err < 0)\n \t\t\tgoto out;\n-\n-\t\tmerged.stack_len++;\n \t}\n \n \tp = reftable_malloc(sizeof(*p));\n-- \n2.45.0\n\n"},{"id":"494307","messageId":"859b399e71e92dd7aa0fa7fc9f2d9ca6f389d34a.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 09/13] reftable/generic: move seeking of records into the iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:15Z","receivedAt":"2024-05-08T11:04:19Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Reftable iterators are created by seeking on the parent structure of a\ncorresponding record. For example, to create an iterator for the merged\ntable you would call `reftable_merged_table_seek_ref()`. Most notably,\nit is not posible to create an iterator and then seek it afterwards.\n\nWhile this may be a bit easier to reason about, it comes with two\nsignificant downsides. The first downside is that the logic to find\nrecords is split up between the parent data structure and the iterator\nitself. Conceptually, it is more straight forward if all that logic was\ncontained in a single place, which should be the iterator.\n\nThe second and more significant downside is that it is impossible to\nreuse iterators for multiple seeks. Whenever you want to look up a\nrecord, you need to re-create the whole infrastructure again, which is\nquite a waste of time. Furthermore, it is impossible to for example\noptimize seeks, for example when seeking the same record multiple times.\n\nTo address this, we essentially split up the concerns properly such that\nthe parent data structure is responsible for setting up the iterator via\na new `init_iter()` callback, whereas the iterator handles seeks via a\nnew `seek()` callback. This will eventually allow us to call `seek()` on\nthe iterator multiple times, where every iterator can potentially\noptimize for certain cases.\n\nNote that at this point in time we are not yet ready to reuse the\niterators. This will be left for a future patch series.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/generic.c | 47 +++++++++++++----\n reftable/generic.h | 9 +++-\n reftable/iter.c | 15 ++++++\n reftable/merged.c | 97 +++++++++++++++++-----------------\n reftable/reader.c | 126 +++++++++++++++++++++++++--------------------\n 5 files changed, 177 insertions(+), 117 deletions(-)\n\ndiff --git a/reftable/generic.c b/reftable/generic.c\nindex b9f1c7c18a..1cf68fe124 100644\n--- a/reftable/generic.c\n+++ b/reftable/generic.c\n@@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at\n #include \"reftable-iterator.h\"\n #include \"reftable-generic.h\"\n \n+void table_init_iter(struct reftable_table *tab,\n+\t\t struct reftable_iterator *it,\n+\t\t uint8_t typ)\n+{\n+\n+\ttab->ops->init_iter(tab->table_arg, it, typ);\n+}\n+\n int reftable_table_seek_ref(struct reftable_table *tab,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_REF,\n-\t\t\t\t .u.ref = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t } };\n-\treturn tab->ops->seek_record(tab->table_arg, it, &rec);\n+\tstruct reftable_record want = {\n+\t\t.type = BLOCK_TYPE_REF,\n+\t\t.u.ref = {\n+\t\t\t.refname = (char *)name,\n+\t\t},\n+\t};\n+\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n+\treturn it->ops->seek(it->iter_arg, &want);\n }\n \n int reftable_table_seek_log(struct reftable_table *tab,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n-\t\t\t\t .u.log = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t\t .update_index = ~((uint64_t)0),\n-\t\t\t\t } };\n-\treturn tab->ops->seek_record(tab->table_arg, it, &rec);\n+\tstruct reftable_record want = {\n+\t\t.type = BLOCK_TYPE_LOG,\n+\t\t.u.log = {\n+\t\t\t.refname = (char *)name,\n+\t\t\t.update_index = ~((uint64_t)0),\n+\t\t},\n+\t};\n+\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n+\treturn it->ops->seek(it->iter_arg, &want);\n }\n \n int reftable_table_read_ref(struct reftable_table *tab, const char *name,\n@@ -152,11 +166,21 @@ int reftable_iterator_next_log(struct reftable_iterator *it,\n \treturn err;\n }\n \n+int iterator_seek(struct reftable_iterator *it, struct reftable_record *want)\n+{\n+\treturn it->ops->seek(it->iter_arg, want);\n+}\n+\n int iterator_next(struct reftable_iterator *it, struct reftable_record *rec)\n {\n \treturn it->ops->next(it->iter_arg, rec);\n }\n \n+static int empty_iterator_seek(void *arg, struct reftable_record *want)\n+{\n+\treturn 0;\n+}\n+\n static int empty_iterator_next(void *arg, struct reftable_record *rec)\n {\n \treturn 1;\n@@ -167,6 +191,7 @@ static void empty_iterator_close(void *arg)\n }\n \n static struct reftable_iterator_vtable empty_vtable = {\n+\t.seek = &empty_iterator_seek,\n \t.next = &empty_iterator_next,\n \t.close = &empty_iterator_close,\n };\ndiff --git a/reftable/generic.h b/reftable/generic.h\nindex 98886a0640..8341fa570e 100644\n--- a/reftable/generic.h\n+++ b/reftable/generic.h\n@@ -14,19 +14,24 @@ license that can be found in the LICENSE file or at\n \n /* generic interface to reftables */\n struct reftable_table_vtable {\n-\tint (*seek_record)(void *tab, struct reftable_iterator *it,\n-\t\t\t struct reftable_record *);\n+\tvoid (*init_iter)(void *tab, struct reftable_iterator *it, uint8_t typ);\n \tuint32_t (*hash_id)(void *tab);\n \tuint64_t (*min_update_index)(void *tab);\n \tuint64_t (*max_update_index)(void *tab);\n };\n \n+void table_init_iter(struct reftable_table *tab,\n+\t\t struct reftable_iterator *it,\n+\t\t uint8_t typ);\n+\n struct reftable_iterator_vtable {\n+\tint (*seek)(void *iter_arg, struct reftable_record *want);\n \tint (*next)(void *iter_arg, struct reftable_record *rec);\n \tvoid (*close)(void *iter_arg);\n };\n \n void iterator_set_empty(struct reftable_iterator *it);\n+int iterator_seek(struct reftable_iterator *it, struct reftable_record *want);\n int iterator_next(struct reftable_iterator *it, struct reftable_record *rec);\n \n #endif\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex aa9ac199b1..b4528fab47 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)\n \treftable_iterator_destroy(&fri->it);\n }\n \n+static int filtering_ref_iterator_seek(void *iter_arg,\n+\t\t\t\t struct reftable_record *want)\n+{\n+\tstruct filtering_ref_iterator *fri = iter_arg;\n+\treturn iterator_seek(&fri->it, want);\n+}\n+\n static int filtering_ref_iterator_next(void *iter_arg,\n \t\t\t\t struct reftable_record *rec)\n {\n@@ -73,6 +80,7 @@ static int filtering_ref_iterator_next(void *iter_arg,\n }\n \n static struct reftable_iterator_vtable filtering_ref_iterator_vtable = {\n+\t.seek = &filtering_ref_iterator_seek,\n \t.next = &filtering_ref_iterator_next,\n \t.close = &filtering_ref_iterator_close,\n };\n@@ -119,6 +127,12 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)\n \treturn 0;\n }\n \n+static int indexed_table_ref_iter_seek(void *p, struct reftable_record *want)\n+{\n+\tBUG(\"seeking indexed table is not supported\");\n+\treturn -1;\n+}\n+\n static int indexed_table_ref_iter_next(void *p, struct reftable_record *rec)\n {\n \tstruct indexed_table_ref_iter *it = p;\n@@ -175,6 +189,7 @@ int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest,\n }\n \n static struct reftable_iterator_vtable indexed_table_ref_iter_vtable = {\n+\t.seek = &indexed_table_ref_iter_seek,\n \t.next = &indexed_table_ref_iter_next,\n \t.close = &indexed_table_ref_iter_close,\n };\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 18a2a6f09b..fc7946d90d 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -31,12 +31,18 @@ struct merged_iter {\n };\n \n static void merged_iter_init(struct merged_iter *mi,\n-\t\t\t struct reftable_merged_table *mt)\n+\t\t\t struct reftable_merged_table *mt,\n+\t\t\t uint8_t typ)\n {\n \tmemset(mi, 0, sizeof(*mi));\n \tmi->advance_index = -1;\n \tmi->suppress_deletions = mt->suppress_deletions;\n+\n \tREFTABLE_CALLOC_ARRAY(mi->subiters, mt->stack_len);\n+\tfor (size_t i = 0; i < mt->stack_len; i++) {\n+\t\treftable_record_init(&mi->subiters[i].rec, typ);\n+\t\ttable_init_iter(&mt->stack[i], &mi->subiters[i].iter, typ);\n+\t}\n \tmi->stack_len = mt->stack_len;\n }\n \n@@ -68,6 +74,27 @@ static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n \treturn 0;\n }\n \n+static int merged_iter_seek(struct merged_iter *mi, struct reftable_record *want)\n+{\n+\tint err;\n+\n+\tmi->advance_index = -1;\n+\n+\tfor (size_t i = 0; i < mi->stack_len; i++) {\n+\t\terr = iterator_seek(&mi->subiters[i].iter, want);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t\tif (err > 0)\n+\t\t\tcontinue;\n+\n+\t\terr = merged_iter_advance_subiter(mi, i);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t struct reftable_record *rec)\n {\n@@ -133,6 +160,11 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \treturn 0;\n }\n \n+static int merged_iter_seek_void(void *it, struct reftable_record *want)\n+{\n+\treturn merged_iter_seek(it, want);\n+}\n+\n static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n \tstruct merged_iter *mi = p;\n@@ -147,6 +179,7 @@ static int merged_iter_next_void(void *p, struct reftable_record *rec)\n }\n \n static struct reftable_iterator_vtable merged_iter_vtable = {\n+\t.seek = merged_iter_seek_void,\n \t.next = &merged_iter_next_void,\n \t.close = &merged_iter_close,\n };\n@@ -220,47 +253,13 @@ reftable_merged_table_min_update_index(struct reftable_merged_table *mt)\n \treturn mt->min;\n }\n \n-static int reftable_table_seek_record(struct reftable_table *tab,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t struct reftable_record *rec)\n-{\n-\treturn tab->ops->seek_record(tab->table_arg, it, rec);\n-}\n-\n-static int merged_table_seek_record(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t struct reftable_record *rec)\n+static void merged_table_init_iter(struct reftable_merged_table *mt,\n+\t\t\t\t struct reftable_iterator *it,\n+\t\t\t\t uint8_t typ)\n {\n-\tstruct merged_iter merged, *p;\n-\tint err;\n-\n-\tmerged_iter_init(&merged, mt);\n-\n-\tfor (size_t i = 0; i < mt->stack_len; i++) {\n-\t\treftable_record_init(&merged.subiters[i].rec,\n-\t\t\t\t reftable_record_type(rec));\n-\n-\t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.subiters[i].iter, rec);\n-\t\tif (err < 0)\n-\t\t\tgoto out;\n-\t\tif (err > 0)\n-\t\t\tcontinue;\n-\n-\t\terr = merged_iter_advance_subiter(&merged, i);\n-\t\tif (err < 0)\n-\t\t\tgoto out;\n-\t}\n-\n-\tp = reftable_malloc(sizeof(*p));\n-\t*p = merged;\n-\titerator_from_merged_iter(it, p);\n-\terr = 0;\n-\n-out:\n-\tif (err < 0)\n-\t\tmerged_iter_close(&merged);\n-\treturn err;\n+\tstruct merged_iter *mi = reftable_malloc(sizeof(*mi));\n+\tmerged_iter_init(mi, mt, typ);\n+\titerator_from_merged_iter(it, mi);\n }\n \n int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n@@ -273,7 +272,8 @@ int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n \t\t\t.refname = (char *)name,\n \t\t},\n \t};\n-\treturn merged_table_seek_record(mt, it, &rec);\n+\tmerged_table_init_iter(mt, it, BLOCK_TYPE_REF);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n@@ -285,7 +285,8 @@ int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n \t\t\t\t\t .refname = (char *)name,\n \t\t\t\t\t .update_index = update_index,\n \t\t\t\t } };\n-\treturn merged_table_seek_record(mt, it, &rec);\n+\tmerged_table_init_iter(mt, it, BLOCK_TYPE_LOG);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_merged_table_seek_log(struct reftable_merged_table *mt,\n@@ -301,11 +302,11 @@ uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *mt)\n \treturn mt->hash_id;\n }\n \n-static int reftable_merged_table_seek_void(void *tab,\n-\t\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t\t struct reftable_record *rec)\n+static void reftable_merged_table_init_iter_void(void *tab,\n+\t\t\t\t\t\t struct reftable_iterator *it,\n+\t\t\t\t\t\t uint8_t typ)\n {\n-\treturn merged_table_seek_record(tab, it, rec);\n+\tmerged_table_init_iter(tab, it, typ);\n }\n \n static uint32_t reftable_merged_table_hash_id_void(void *tab)\n@@ -324,7 +325,7 @@ static uint64_t reftable_merged_table_max_update_index_void(void *tab)\n }\n \n static struct reftable_table_vtable merged_table_vtable = {\n-\t.seek_record = reftable_merged_table_seek_void,\n+\t.init_iter = reftable_merged_table_init_iter_void,\n \t.hash_id = reftable_merged_table_hash_id_void,\n \t.min_update_index = reftable_merged_table_min_update_index_void,\n \t.max_update_index = reftable_merged_table_max_update_index_void,\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 021608f638..a5a13cb0b9 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -369,29 +369,6 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t}\n }\n \n-static int table_iter_next_void(void *ti, struct reftable_record *rec)\n-{\n-\treturn table_iter_next(ti, rec);\n-}\n-\n-static void table_iter_close_void(void *ti)\n-{\n-\ttable_iter_close(ti);\n-}\n-\n-static struct reftable_iterator_vtable table_iter_vtable = {\n-\t.next = &table_iter_next_void,\n-\t.close = &table_iter_close_void,\n-};\n-\n-static void iterator_from_table_iter(struct reftable_iterator *it,\n-\t\t\t\t struct table_iter *ti)\n-{\n-\tassert(!it->ops);\n-\tit->iter_arg = ti;\n-\tit->ops = &table_iter_vtable;\n-}\n-\n static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)\n {\n \tint err;\n@@ -576,43 +553,74 @@ static int table_iter_seek_indexed(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n-\t\t struct reftable_record *rec)\n+static int table_iter_seek(struct table_iter *ti,\n+\t\t\t struct reftable_record *want)\n {\n-\tuint8_t typ = reftable_record_type(rec);\n-\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n-\tstruct table_iter ti, *p;\n+\tuint8_t typ = reftable_record_type(want);\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(ti->r, typ);\n \tint err;\n \n-\tif (!offs->is_present) {\n-\t\titerator_set_empty(it);\n-\t\treturn 0;\n-\t}\n-\n-\ttable_iter_init(&ti, r);\n-\n-\terr = table_iter_seek_start(&ti, reftable_record_type(rec),\n+\terr = table_iter_seek_start(ti, reftable_record_type(want),\n \t\t\t\t !!offs->index_offset);\n \tif (err < 0)\n \t\tgoto out;\n \n \tif (offs->index_offset)\n-\t\terr = table_iter_seek_indexed(&ti, rec);\n+\t\terr = table_iter_seek_indexed(ti, want);\n \telse\n-\t\terr = table_iter_seek_linear(&ti, rec);\n+\t\terr = table_iter_seek_linear(ti, want);\n \tif (err)\n \t\tgoto out;\n \n-\tREFTABLE_ALLOC_ARRAY(p, 1);\n-\t*p = ti;\n-\titerator_from_table_iter(it, p);\n-\n out:\n-\tif (err)\n-\t\ttable_iter_close(&ti);\n \treturn err;\n }\n \n+static int table_iter_seek_void(void *ti, struct reftable_record *want)\n+{\n+\treturn table_iter_seek(ti, want);\n+}\n+\n+static int table_iter_next_void(void *ti, struct reftable_record *rec)\n+{\n+\treturn table_iter_next(ti, rec);\n+}\n+\n+static void table_iter_close_void(void *ti)\n+{\n+\ttable_iter_close(ti);\n+}\n+\n+static struct reftable_iterator_vtable table_iter_vtable = {\n+\t.seek = &table_iter_seek_void,\n+\t.next = &table_iter_next_void,\n+\t.close = &table_iter_close_void,\n+};\n+\n+static void iterator_from_table_iter(struct reftable_iterator *it,\n+\t\t\t\t struct table_iter *ti)\n+{\n+\tassert(!it->ops);\n+\tit->iter_arg = ti;\n+\tit->ops = &table_iter_vtable;\n+}\n+\n+static void reader_init_iter(struct reftable_reader *r,\n+\t\t\t struct reftable_iterator *it,\n+\t\t\t uint8_t typ)\n+{\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n+\n+\tif (offs->is_present) {\n+\t\tstruct table_iter *ti;\n+\t\tREFTABLE_ALLOC_ARRAY(ti, 1);\n+\t\ttable_iter_init(ti, r);\n+\t\titerator_from_table_iter(it, ti);\n+\t} else {\n+\t\titerator_set_empty(it);\n+\t}\n+}\n+\n int reftable_reader_seek_ref(struct reftable_reader *r,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n@@ -622,19 +630,23 @@ int reftable_reader_seek_ref(struct reftable_reader *r,\n \t\t\t.refname = (char *)name,\n \t\t},\n \t};\n-\treturn reader_seek(r, it, &rec);\n+\treader_init_iter(r, it, BLOCK_TYPE_REF);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_reader_seek_log_at(struct reftable_reader *r,\n \t\t\t\tstruct reftable_iterator *it, const char *name,\n \t\t\t\tuint64_t update_index)\n {\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n-\t\t\t\t .u.log = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t\t .update_index = update_index,\n-\t\t\t\t } };\n-\treturn reader_seek(r, it, &rec);\n+\tstruct reftable_record rec = {\n+\t\t.type = BLOCK_TYPE_LOG,\n+\t\t.u.log = {\n+\t\t\t.refname = (char *)name,\n+\t\t\t.update_index = update_index,\n+\t\t},\n+\t};\n+\treader_init_iter(r, it, BLOCK_TYPE_LOG);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_reader_seek_log(struct reftable_reader *r,\n@@ -692,7 +704,8 @@ static int reftable_reader_refs_for_indexed(struct reftable_reader *r,\n \tstruct indexed_table_ref_iter *itr = NULL;\n \n \t/* Look through the reverse index. */\n-\terr = reader_seek(r, &oit, &want);\n+\treader_init_iter(r, &oit, BLOCK_TYPE_OBJ);\n+\terr = iterator_seek(&oit, &want);\n \tif (err != 0)\n \t\tgoto done;\n \n@@ -773,10 +786,11 @@ uint64_t reftable_reader_min_update_index(struct reftable_reader *r)\n \n /* generic table interface. */\n \n-static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,\n-\t\t\t\t struct reftable_record *rec)\n+static void reftable_reader_init_iter_void(void *tab,\n+\t\t\t\t\t struct reftable_iterator *it,\n+\t\t\t\t\t uint8_t typ)\n {\n-\treturn reader_seek(tab, it, rec);\n+\treader_init_iter(tab, it, typ);\n }\n \n static uint32_t reftable_reader_hash_id_void(void *tab)\n@@ -795,7 +809,7 @@ static uint64_t reftable_reader_max_update_index_void(void *tab)\n }\n \n static struct reftable_table_vtable reader_vtable = {\n-\t.seek_record = reftable_reader_seek_void,\n+\t.init_iter = reftable_reader_init_iter_void,\n \t.hash_id = reftable_reader_hash_id_void,\n \t.min_update_index = reftable_reader_min_update_index_void,\n \t.max_update_index = reftable_reader_max_update_index_void,\n-- \n2.45.0\n\n"},{"id":"494308","messageId":"727b8fa4327b710aba37b9cc7ca8de0f9bb2efaa.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 10/13] reftable/generic: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:20Z","receivedAt":"2024-05-08T11:04:24Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Refactor the interfaces exposed by `struct reftable_table` and `struct\nreftable_iterator` such that they support iterator reuse. This is done\nby separating initialization of the iterator and seeking on it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/generic.c | 53 ++++++++++++++++++++++++++----------\n reftable/iter.c | 8 +++---\n reftable/reftable-generic.h | 8 +++---\n reftable/reftable-iterator.h | 21 ++++++++++++++\n 4 files changed, 68 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/generic.c b/reftable/generic.c\nindex 1cf68fe124..28ae26145e 100644\n--- a/reftable/generic.c\n+++ b/reftable/generic.c\n@@ -20,8 +20,20 @@ void table_init_iter(struct reftable_table *tab,\n \ttab->ops->init_iter(tab->table_arg, it, typ);\n }\n \n-int reftable_table_seek_ref(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name)\n+void reftable_table_init_ref_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n+}\n+\n+void reftable_table_init_log_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n+}\n+\n+int reftable_iterator_seek_ref(struct reftable_iterator *it,\n+\t\t\t const char *name)\n {\n \tstruct reftable_record want = {\n \t\t.type = BLOCK_TYPE_REF,\n@@ -29,29 +41,37 @@ int reftable_table_seek_ref(struct reftable_table *tab,\n \t\t\t.refname = (char *)name,\n \t\t},\n \t};\n-\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n \treturn it->ops->seek(it->iter_arg, &want);\n }\n \n-int reftable_table_seek_log(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name)\n+int reftable_iterator_seek_log_at(struct reftable_iterator *it,\n+\t\t\t\t const char *name, uint64_t update_index)\n {\n \tstruct reftable_record want = {\n \t\t.type = BLOCK_TYPE_LOG,\n \t\t.u.log = {\n \t\t\t.refname = (char *)name,\n-\t\t\t.update_index = ~((uint64_t)0),\n+\t\t\t.update_index = update_index,\n \t\t},\n \t};\n-\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n \treturn it->ops->seek(it->iter_arg, &want);\n }\n \n+int reftable_iterator_seek_log(struct reftable_iterator *it,\n+\t\t\t const char *name)\n+{\n+\treturn reftable_iterator_seek_log_at(it, name, ~((uint64_t) 0));\n+}\n+\n int reftable_table_read_ref(struct reftable_table *tab, const char *name,\n \t\t\t struct reftable_ref_record *ref)\n {\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_table_seek_ref(tab, &it, name);\n+\tint err;\n+\n+\treftable_table_init_ref_iter(tab, &it);\n+\n+\terr = reftable_iterator_seek_ref(&it, name);\n \tif (err)\n \t\tgoto done;\n \n@@ -76,10 +96,13 @@ int reftable_table_print(struct reftable_table *tab) {\n \tstruct reftable_ref_record ref = { NULL };\n \tstruct reftable_log_record log = { NULL };\n \tuint32_t hash_id = reftable_table_hash_id(tab);\n-\tint err = reftable_table_seek_ref(tab, &it, \"\");\n-\tif (err < 0) {\n+\tint err;\n+\n+\treftable_table_init_ref_iter(tab, &it);\n+\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n+\tif (err < 0)\n \t\treturn err;\n-\t}\n \n \twhile (1) {\n \t\terr = reftable_iterator_next_ref(&it, &ref);\n@@ -94,10 +117,12 @@ int reftable_table_print(struct reftable_table *tab) {\n \treftable_iterator_destroy(&it);\n \treftable_ref_record_release(&ref);\n \n-\terr = reftable_table_seek_log(tab, &it, \"\");\n-\tif (err < 0) {\n+\treftable_table_init_log_iter(tab, &it);\n+\n+\terr = reftable_iterator_seek_log(&it, \"\");\n+\tif (err < 0)\n \t\treturn err;\n-\t}\n+\n \twhile (1) {\n \t\terr = reftable_iterator_next_log(&it, &log);\n \t\tif (err > 0) {\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex b4528fab47..fddea31e51 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -45,11 +45,11 @@ static int filtering_ref_iterator_next(void *iter_arg,\n \t\tif (fri->double_check) {\n \t\t\tstruct reftable_iterator it = { NULL };\n \n-\t\t\terr = reftable_table_seek_ref(&fri->tab, &it,\n-\t\t\t\t\t\t ref->refname);\n-\t\t\tif (err == 0) {\n+\t\t\treftable_table_init_ref_iter(&fri->tab, &it);\n+\n+\t\t\terr = reftable_iterator_seek_ref(&it, ref->refname);\n+\t\t\tif (err == 0)\n \t\t\t\terr = reftable_iterator_next_ref(&it, ref);\n-\t\t\t}\n \n \t\t\treftable_iterator_destroy(&it);\n \ndiff --git a/reftable/reftable-generic.h b/reftable/reftable-generic.h\nindex d239751a77..65670ea093 100644\n--- a/reftable/reftable-generic.h\n+++ b/reftable/reftable-generic.h\n@@ -21,11 +21,11 @@ struct reftable_table {\n \tvoid *table_arg;\n };\n \n-int reftable_table_seek_log(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name);\n+void reftable_table_init_ref_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it);\n \n-int reftable_table_seek_ref(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name);\n+void reftable_table_init_log_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it);\n \n /* returns the hash ID from a generic reftable_table */\n uint32_t reftable_table_hash_id(struct reftable_table *tab);\ndiff --git a/reftable/reftable-iterator.h b/reftable/reftable-iterator.h\nindex d3eee7af35..e3bf688d53 100644\n--- a/reftable/reftable-iterator.h\n+++ b/reftable/reftable-iterator.h\n@@ -21,12 +21,33 @@ struct reftable_iterator {\n \tvoid *iter_arg;\n };\n \n+/*\n+ * Position the iterator at the ref record with given name such that the next\n+ * call to `next_ref()` would yield the record.\n+ */\n+int reftable_iterator_seek_ref(struct reftable_iterator *it,\n+\t\t\t const char *name);\n+\n /* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0:\n * end of iteration.\n */\n int reftable_iterator_next_ref(struct reftable_iterator *it,\n \t\t\t struct reftable_ref_record *ref);\n \n+/*\n+ * Position the iterator at the log record with given name and update index\n+ * such that the next call to `next_log()` would yield the record.\n+ */\n+int reftable_iterator_seek_log_at(struct reftable_iterator *it,\n+\t\t\t\t const char *name, uint64_t update_index);\n+\n+/*\n+ * Position the iterator at the newest log record with given name such that the\n+ * next call to `next_log()` would yield the record.\n+ */\n+int reftable_iterator_seek_log(struct reftable_iterator *it,\n+\t\t\t const char *name);\n+\n /* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0:\n * end of iteration.\n */\n-- \n2.45.0\n\n"},{"id":"494309","messageId":"f688f8f59a05b667b4f4118b7f8c7504bd33329a.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 11/13] reftable/reader: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:25Z","receivedAt":"2024-05-08T11:04:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Refactor the interfaces exposed by `struct reftable_reader` and `struct\ntable_iterator` such that they support iterator reuse. This is done by\nseparating initialization of the iterator and seeking on it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 31 ++++----------------------\n reftable/readwrite_test.c | 35 +++++++++++++++++++----------\n reftable/reftable-reader.h | 45 ++++++--------------------------------\n 3 files changed, 35 insertions(+), 76 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex a5a13cb0b9..bbdb4bdafa 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -621,39 +621,16 @@ static void reader_init_iter(struct reftable_reader *r,\n \t}\n }\n \n-int reftable_reader_seek_ref(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name)\n+void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it)\n {\n-\tstruct reftable_record rec = {\n-\t\t.type = BLOCK_TYPE_REF,\n-\t\t.u.ref = {\n-\t\t\t.refname = (char *)name,\n-\t\t},\n-\t};\n \treader_init_iter(r, it, BLOCK_TYPE_REF);\n-\treturn iterator_seek(it, &rec);\n }\n \n-int reftable_reader_seek_log_at(struct reftable_reader *r,\n-\t\t\t\tstruct reftable_iterator *it, const char *name,\n-\t\t\t\tuint64_t update_index)\n+void reftable_reader_init_log_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it)\n {\n-\tstruct reftable_record rec = {\n-\t\t.type = BLOCK_TYPE_LOG,\n-\t\t.u.log = {\n-\t\t\t.refname = (char *)name,\n-\t\t\t.update_index = update_index,\n-\t\t},\n-\t};\n \treader_init_iter(r, it, BLOCK_TYPE_LOG);\n-\treturn iterator_seek(it, &rec);\n-}\n-\n-int reftable_reader_seek_log(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name)\n-{\n-\tuint64_t max = ~((uint64_t)0);\n-\treturn reftable_reader_seek_log_at(r, it, name, max);\n }\n \n void reader_close(struct reftable_reader *r)\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex a6dbd214c5..d99543bbd6 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -239,7 +239,9 @@ static void test_log_write_read(void)\n \terr = init_reader(&rd, &source, \"file.log\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(&rd, &it, names[N - 1]);\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\n+\terr = reftable_iterator_seek_ref(&it, names[N - 1]);\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_ref(&it, &ref);\n@@ -252,7 +254,9 @@ static void test_log_write_read(void)\n \treftable_iterator_destroy(&it);\n \treftable_ref_record_release(&ref);\n \n-\terr = reftable_reader_seek_log(&rd, &it, \"\");\n+\treftable_reader_init_log_iterator(&rd, &it);\n+\n+\terr = reftable_iterator_seek_log(&it, \"\");\n \tEXPECT_ERR(err);\n \n \ti = 0;\n@@ -330,7 +334,8 @@ static void test_log_zlib_corruption(void)\n \terr = init_reader(&rd, &source, \"file.log\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_log(&rd, &it, \"refname\");\n+\treftable_reader_init_log_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_log(&it, \"refname\");\n \tEXPECT(err == REFTABLE_ZLIB_ERROR);\n \n \treftable_iterator_destroy(&it);\n@@ -358,7 +363,8 @@ static void test_table_read_write_sequential(void)\n \terr = init_reader(&rd, &source, \"file.ref\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(&rd, &it, \"\");\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tEXPECT_ERR(err);\n \n \twhile (1) {\n@@ -412,7 +418,8 @@ static void test_table_read_api(void)\n \terr = init_reader(&rd, &source, \"file.ref\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(&rd, &it, names[0]);\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, names[0]);\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_log(&it, &log);\n@@ -457,7 +464,8 @@ static void test_table_read_write_seek(int index, int hash_id)\n \t}\n \n \tfor (i = 1; i < N; i++) {\n-\t\tint err = reftable_reader_seek_ref(&rd, &it, names[i]);\n+\t\treftable_reader_init_ref_iterator(&rd, &it);\n+\t\terr = reftable_iterator_seek_ref(&it, names[i]);\n \t\tEXPECT_ERR(err);\n \t\terr = reftable_iterator_next_ref(&it, &ref);\n \t\tEXPECT_ERR(err);\n@@ -472,7 +480,8 @@ static void test_table_read_write_seek(int index, int hash_id)\n \tstrbuf_addstr(&pastLast, names[N - 1]);\n \tstrbuf_addstr(&pastLast, \"/\");\n \n-\terr = reftable_reader_seek_ref(&rd, &it, pastLast.buf);\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, pastLast.buf);\n \tif (err == 0) {\n \t\tstruct reftable_ref_record ref = { NULL };\n \t\tint err = reftable_iterator_next_ref(&it, &ref);\n@@ -576,7 +585,8 @@ static void test_table_refs_for(int indexed)\n \t\trd.obj_offsets.is_present = 0;\n \t}\n \n-\terr = reftable_reader_seek_ref(&rd, &it, \"\");\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tEXPECT_ERR(err);\n \treftable_iterator_destroy(&it);\n \n@@ -639,7 +649,8 @@ static void test_write_empty_table(void)\n \terr = reftable_new_reader(&rd, &source, \"filename\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(rd, &it, \"\");\n+\treftable_reader_init_ref_iterator(rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_ref(&it, &rec);\n@@ -846,7 +857,8 @@ static void test_write_multiple_indices(void)\n \t * Seeking the log uses the log index now. In case there is any\n \t * confusion regarding indices we would notice here.\n \t */\n-\terr = reftable_reader_seek_log(reader, &it, \"\");\n+\treftable_reader_init_log_iterator(reader, &it);\n+\terr = reftable_iterator_seek_log(&it, \"\");\n \tEXPECT_ERR(err);\n \n \treftable_iterator_destroy(&it);\n@@ -901,7 +913,8 @@ static void test_write_multi_level_index(void)\n \t/*\n \t * Seeking the last ref should work as expected.\n \t */\n-\terr = reftable_reader_seek_ref(reader, &it, \"refs/heads/199\");\n+\treftable_reader_init_ref_iterator(reader, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"refs/heads/199\");\n \tEXPECT_ERR(err);\n \n \treftable_iterator_destroy(&it);\ndiff --git a/reftable/reftable-reader.h b/reftable/reftable-reader.h\nindex 4a4bc2fdf8..35b9fb66e4 100644\n--- a/reftable/reftable-reader.h\n+++ b/reftable/reftable-reader.h\n@@ -36,48 +36,17 @@ struct reftable_table;\n int reftable_new_reader(struct reftable_reader **pp,\n \t\t\tstruct reftable_block_source *src, const char *name);\n \n-/* reftable_reader_seek_ref returns an iterator where 'name' would be inserted\n- in the table. To seek to the start of the table, use name = \"\".\n-\n- example:\n-\n- struct reftable_reader *r = NULL;\n- int err = reftable_new_reader(&r, &src, \"filename\");\n- if (err < 0) { ... }\n- struct reftable_iterator it = {0};\n- err = reftable_reader_seek_ref(r, &it, \"refs/heads/master\");\n- if (err < 0) { ... }\n- struct reftable_ref_record ref = {0};\n- while (1) {\n- err = reftable_iterator_next_ref(&it, &ref);\n- if (err > 0) {\n- break;\n- }\n- if (err < 0) {\n- ..error handling..\n- }\n- ..found..\n- }\n- reftable_iterator_destroy(&it);\n- reftable_ref_record_release(&ref);\n-*/\n-int reftable_reader_seek_ref(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name);\n+/* Initialize a reftable iterator for reading refs. */\n+void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it);\n+\n+/* Initialize a reftable iterator for reading refs. */\n+void reftable_reader_init_log_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it);\n \n /* returns the hash ID used in this table. */\n uint32_t reftable_reader_hash_id(struct reftable_reader *r);\n \n-/* seek to logs for the given name, older than update_index. To seek to the\n- start of the table, use name = \"\".\n-*/\n-int reftable_reader_seek_log_at(struct reftable_reader *r,\n-\t\t\t\tstruct reftable_iterator *it, const char *name,\n-\t\t\t\tuint64_t update_index);\n-\n-/* seek to newest log entry for given name. */\n-int reftable_reader_seek_log(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name);\n-\n /* closes and deallocates a reader. */\n void reftable_reader_free(struct reftable_reader *);\n \n-- \n2.45.0\n\n"},{"id":"494310","messageId":"68cc35919b9e3c232c4ab725b6249c2e543ad1ae.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 12/13] reftable/stack: provide convenience functions to create iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:30Z","receivedAt":"2024-05-08T11:04:33Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"There exist a bunch of call sites in the reftable backend that want to\ncreate iterators for a reftable stack. This is rather convoluted right\nnow, where you always have to go via the merged table. And it is about\nto become even more convoluted when we split up iterator initialization\nand seeking in the next commit.\n\nIntroduce convenience functions that allow the caller to create an\niterator from a reftable stack directly without going through the merged\ntable. Adapt callers accordingly.\n\nSigned-off-by: Patrick Steinhardt \n---\n refs/reftable-backend.c | 48 +++++++++++++++++----------------------\n reftable/merged.c | 6 ++---\n reftable/merged.h | 6 +++++\n reftable/reftable-stack.h | 18 +++++++++++++++\n reftable/stack.c | 15 ++++++++++++\n 5 files changed, 63 insertions(+), 30 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex 010ef811b6..7ac2772bcb 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -15,7 +15,6 @@\n #include \"../reftable/reftable-record.h\"\n #include \"../reftable/reftable-error.h\"\n #include \"../reftable/reftable-iterator.h\"\n-#include \"../reftable/reftable-merged.h\"\n #include \"../setup.h\"\n #include \"../strmap.h\"\n #include \"parse.h\"\n@@ -462,7 +461,6 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n \t\t\t\t\t\t\t const char *prefix,\n \t\t\t\t\t\t\t int flags)\n {\n-\tstruct reftable_merged_table *merged_table;\n \tstruct reftable_ref_iterator *iter;\n \tint ret;\n \n@@ -482,9 +480,8 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n \tif (ret)\n \t\tgoto done;\n \n-\tmerged_table = reftable_stack_merged_table(stack);\n-\n-\tret = reftable_merged_table_seek_ref(merged_table, &iter->iter, prefix);\n+\treftable_stack_init_ref_iterator(stack, &iter->iter);\n+\tret = reftable_iterator_seek_ref(&iter->iter, prefix);\n \tif (ret)\n \t\tgoto done;\n \n@@ -1015,8 +1012,6 @@ static int transaction_update_cmp(const void *a, const void *b)\n static int write_transaction_table(struct reftable_writer *writer, void *cb_data)\n {\n \tstruct write_transaction_table_arg *arg = cb_data;\n-\tstruct reftable_merged_table *mt =\n-\t\treftable_stack_merged_table(arg->stack);\n \tuint64_t ts = reftable_stack_next_update_index(arg->stack);\n \tstruct reftable_log_record *logs = NULL;\n \tstruct ident_split committer_ident = {0};\n@@ -1051,6 +1046,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\tstruct reftable_log_record log = {0};\n \t\t\tstruct reftable_iterator it = {0};\n \n+\t\t\treftable_stack_init_log_iterator(arg->stack, &it);\n+\n \t\t\t/*\n \t\t\t * When deleting refs we also delete all reflog entries\n \t\t\t * with them. While it is not strictly required to\n@@ -1060,7 +1057,7 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\t * Unfortunately, we have no better way than to delete\n \t\t\t * all reflog entries one by one.\n \t\t\t */\n-\t\t\tret = reftable_merged_table_seek_log(mt, &it, u->refname);\n+\t\t\tret = reftable_iterator_seek_log(&it, u->refname);\n \t\t\twhile (ret == 0) {\n \t\t\t\tstruct reftable_log_record *tombstone;\n \n@@ -1354,7 +1351,6 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n {\n \tstruct write_copy_arg *arg = cb_data;\n \tuint64_t deletion_ts, creation_ts;\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(arg->stack);\n \tstruct reftable_ref_record old_ref = {0}, refs[2] = {0};\n \tstruct reftable_log_record old_log = {0}, *logs = NULL;\n \tstruct reftable_iterator it = {0};\n@@ -1488,7 +1484,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n \t * copy over all log entries from the old reflog. Last but not least,\n \t * when renaming we also have to delete all the old reflog entries.\n \t */\n-\tret = reftable_merged_table_seek_log(mt, &it, arg->oldname);\n+\treftable_stack_init_log_iterator(arg->stack, &it);\n+\tret = reftable_iterator_seek_log(&it, arg->oldname);\n \tif (ret < 0)\n \t\tgoto done;\n \n@@ -1694,7 +1691,6 @@ static struct ref_iterator_vtable reftable_reflog_iterator_vtable = {\n static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftable_ref_store *refs,\n \t\t\t\t\t\t\t\t struct reftable_stack *stack)\n {\n-\tstruct reftable_merged_table *merged_table;\n \tstruct reftable_reflog_iterator *iter;\n \tint ret;\n \n@@ -1711,9 +1707,8 @@ static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftabl\n \tif (ret < 0)\n \t\tgoto done;\n \n-\tmerged_table = reftable_stack_merged_table(stack);\n-\n-\tret = reftable_merged_table_seek_log(merged_table, &iter->iter, \"\");\n+\treftable_stack_init_log_iterator(stack, &iter->iter);\n+\tret = reftable_iterator_seek_log(&iter->iter, \"\");\n \tif (ret < 0)\n \t\tgoto done;\n \n@@ -1771,7 +1766,6 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_READ, \"for_each_reflog_ent_reverse\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = NULL;\n \tstruct reftable_log_record log = {0};\n \tstruct reftable_iterator it = {0};\n \tint ret;\n@@ -1779,8 +1773,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \tif (refs->err < 0)\n \t\treturn refs->err;\n \n-\tmt = reftable_stack_merged_table(stack);\n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\tret = reftable_iterator_seek_log(&it, refname);\n \twhile (!ret) {\n \t\tret = reftable_iterator_next_log(&it, &log);\n \t\tif (ret < 0)\n@@ -1808,7 +1802,6 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_READ, \"for_each_reflog_ent\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = NULL;\n \tstruct reftable_log_record *logs = NULL;\n \tstruct reftable_iterator it = {0};\n \tsize_t logs_alloc = 0, logs_nr = 0, i;\n@@ -1817,8 +1810,8 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \tif (refs->err < 0)\n \t\treturn refs->err;\n \n-\tmt = reftable_stack_merged_table(stack);\n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\tret = reftable_iterator_seek_log(&it, refname);\n \twhile (!ret) {\n \t\tstruct reftable_log_record log = {0};\n \n@@ -1855,7 +1848,6 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_READ, \"reflog_exists\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(stack);\n \tstruct reftable_log_record log = {0};\n \tstruct reftable_iterator it = {0};\n \tint ret;\n@@ -1868,7 +1860,8 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \tif (ret < 0)\n \t\tgoto done;\n \n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\tret = reftable_iterator_seek_log(&it, refname);\n \tif (ret < 0)\n \t\tgoto done;\n \n@@ -1966,8 +1959,6 @@ struct write_reflog_delete_arg {\n static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_data)\n {\n \tstruct write_reflog_delete_arg *arg = cb_data;\n-\tstruct reftable_merged_table *mt =\n-\t\treftable_stack_merged_table(arg->stack);\n \tstruct reftable_log_record log = {0}, tombstone = {0};\n \tstruct reftable_iterator it = {0};\n \tuint64_t ts = reftable_stack_next_update_index(arg->stack);\n@@ -1975,12 +1966,14 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da\n \n \treftable_writer_set_limits(writer, ts, ts);\n \n+\treftable_stack_init_log_iterator(arg->stack, &it);\n+\n \t/*\n \t * In order to delete a table we need to delete all reflog entries one\n \t * by one. This is inefficient, but the reftable format does not have a\n \t * better marker right now.\n \t */\n-\tret = reftable_merged_table_seek_log(mt, &it, arg->refname);\n+\tret = reftable_iterator_seek_log(&it, arg->refname);\n \twhile (ret == 0) {\n \t\tret = reftable_iterator_next_log(&it, &log);\n \t\tif (ret < 0)\n@@ -2116,7 +2109,6 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_WRITE, \"reflog_expire\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(stack);\n \tstruct reftable_log_record *logs = NULL;\n \tstruct reftable_log_record *rewritten = NULL;\n \tstruct reftable_ref_record ref_record = {0};\n@@ -2135,7 +2127,9 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \tif (ret < 0)\n \t\tgoto done;\n \n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\n+\tret = reftable_iterator_seek_log(&it, refname);\n \tif (ret < 0)\n \t\tgoto done;\n \ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex fc7946d90d..d127f99360 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -253,9 +253,9 @@ reftable_merged_table_min_update_index(struct reftable_merged_table *mt)\n \treturn mt->min;\n }\n \n-static void merged_table_init_iter(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t uint8_t typ)\n+void merged_table_init_iter(struct reftable_merged_table *mt,\n+\t\t\t struct reftable_iterator *it,\n+\t\t\t uint8_t typ)\n {\n \tstruct merged_iter *mi = reftable_malloc(sizeof(*mi));\n \tmerged_iter_init(mi, mt, typ);\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex a2571dbc99..a10469f58e 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -26,4 +26,10 @@ struct reftable_merged_table {\n \n void merged_table_release(struct reftable_merged_table *mt);\n \n+struct reftable_iterator;\n+\n+void merged_table_init_iter(struct reftable_merged_table *mt,\n+\t\t\t struct reftable_iterator *it,\n+\t\t\t uint8_t typ);\n+\n #endif\ndiff --git a/reftable/reftable-stack.h b/reftable/reftable-stack.h\nindex 1b602dda58..26740e6073 100644\n--- a/reftable/reftable-stack.h\n+++ b/reftable/reftable-stack.h\n@@ -66,6 +66,24 @@ int reftable_stack_add(struct reftable_stack *st,\n \t\t\t\t\t void *write_arg),\n \t\t void *write_arg);\n \n+struct reftable_iterator;\n+\n+/*\n+ * Initialize an iterator for the merged tables contained in the stack that can\n+ * be used to iterate through refs. The iterator is valid until the next reload\n+ * or write.\n+ */\n+void reftable_stack_init_ref_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it);\n+\n+/*\n+ * Initialize an iterator for the merged tables contained in the stack that can\n+ * be used to iterate through logs. The iterator is valid until the next reload\n+ * or write.\n+ */\n+void reftable_stack_init_log_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it);\n+\n /* returns the merged_table for seeking. This table is valid until the\n * next write or reload, and should not be closed or deleted.\n */\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex a59ebe038d..03f95935e1 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -10,6 +10,7 @@ license that can be found in the LICENSE file or at\n \n #include \"../write-or-die.h\"\n #include \"system.h\"\n+#include \"constants.h\"\n #include \"merged.h\"\n #include \"reader.h\"\n #include \"reftable-error.h\"\n@@ -130,6 +131,20 @@ int read_lines(const char *filename, char ***namesp)\n \treturn err;\n }\n \n+void reftable_stack_init_ref_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\tmerged_table_init_iter(reftable_stack_merged_table(st),\n+\t\t\t it, BLOCK_TYPE_REF);\n+}\n+\n+void reftable_stack_init_log_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\tmerged_table_init_iter(reftable_stack_merged_table(st),\n+\t\t\t it, BLOCK_TYPE_LOG);\n+}\n+\n struct reftable_merged_table *\n reftable_stack_merged_table(struct reftable_stack *st)\n {\n-- \n2.45.0\n\n"},{"id":"494311","messageId":"be4da295c6a716dd56604101828a3d38b6fcf067.1715166175.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH 13/13] reftable/merged: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-08T11:04:35Z","receivedAt":"2024-05-08T11:04:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Refactor the interfaces exposed by `struct reftable_merged_table` and\n`struct merged_iter` such that they support iterator reuse. This is done\nby separating initialization of the iterator and seeking on it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 35 -----------------------------------\n reftable/merged_test.c | 19 +++++++++++++------\n reftable/reftable-merged.h | 15 ---------------\n reftable/stack.c | 14 +++++++++-----\n 4 files changed, 22 insertions(+), 61 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex d127f99360..0da9dba265 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -262,41 +262,6 @@ void merged_table_init_iter(struct reftable_merged_table *mt,\n \titerator_from_merged_iter(it, mi);\n }\n \n-int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name)\n-{\n-\tstruct reftable_record rec = {\n-\t\t.type = BLOCK_TYPE_REF,\n-\t\t.u.ref = {\n-\t\t\t.refname = (char *)name,\n-\t\t},\n-\t};\n-\tmerged_table_init_iter(mt, it, BLOCK_TYPE_REF);\n-\treturn iterator_seek(it, &rec);\n-}\n-\n-int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name, uint64_t update_index)\n-{\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n-\t\t\t\t .u.log = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t\t .update_index = update_index,\n-\t\t\t\t } };\n-\tmerged_table_init_iter(mt, it, BLOCK_TYPE_LOG);\n-\treturn iterator_seek(it, &rec);\n-}\n-\n-int reftable_merged_table_seek_log(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name)\n-{\n-\tuint64_t max = ~((uint64_t)0);\n-\treturn reftable_merged_table_seek_log_at(mt, it, name, max);\n-}\n-\n uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *mt)\n {\n \treturn mt->hash_id;\ndiff --git a/reftable/merged_test.c b/reftable/merged_test.c\nindex 530fc82d1c..33a17efcde 100644\n--- a/reftable/merged_test.c\n+++ b/reftable/merged_test.c\n@@ -12,6 +12,7 @@ license that can be found in the LICENSE file or at\n \n #include \"basics.h\"\n #include \"blocksource.h\"\n+#include \"constants.h\"\n #include \"reader.h\"\n #include \"record.h\"\n #include \"test_framework.h\"\n@@ -145,7 +146,10 @@ static void test_merged_between(void)\n \tint i;\n \tstruct reftable_ref_record ref = { NULL };\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_merged_table_seek_ref(mt, &it, \"a\");\n+\tint err;\n+\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_REF);\n+\terr = reftable_iterator_seek_ref(&it, \"a\");\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_ref(&it, &ref);\n@@ -217,14 +221,15 @@ static void test_merged(void)\n \tstruct reftable_reader **readers = NULL;\n \tstruct reftable_merged_table *mt =\n \t\tmerged_table_from_records(refs, &bs, &readers, sizes, bufs, 3);\n-\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_merged_table_seek_ref(mt, &it, \"a\");\n+\tint err;\n \tstruct reftable_ref_record *out = NULL;\n \tsize_t len = 0;\n \tsize_t cap = 0;\n \tint i = 0;\n \n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_REF);\n+\terr = reftable_iterator_seek_ref(&it, \"a\");\n \tEXPECT_ERR(err);\n \tEXPECT(reftable_merged_table_hash_id(mt) == GIT_SHA1_FORMAT_ID);\n \tEXPECT(reftable_merged_table_min_update_index(mt) == 1);\n@@ -348,14 +353,15 @@ static void test_merged_logs(void)\n \tstruct reftable_reader **readers = NULL;\n \tstruct reftable_merged_table *mt = merged_table_from_log_records(\n \t\tlogs, &bs, &readers, sizes, bufs, 3);\n-\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_merged_table_seek_log(mt, &it, \"a\");\n+\tint err;\n \tstruct reftable_log_record *out = NULL;\n \tsize_t len = 0;\n \tsize_t cap = 0;\n \tint i = 0;\n \n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);\n+\terr = reftable_iterator_seek_log(&it, \"a\");\n \tEXPECT_ERR(err);\n \tEXPECT(reftable_merged_table_hash_id(mt) == GIT_SHA1_FORMAT_ID);\n \tEXPECT(reftable_merged_table_min_update_index(mt) == 1);\n@@ -377,7 +383,8 @@ static void test_merged_logs(void)\n \t\t\t\t\t\t GIT_SHA1_RAWSZ));\n \t}\n \n-\terr = reftable_merged_table_seek_log_at(mt, &it, \"a\", 2);\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);\n+\terr = reftable_iterator_seek_log_at(&it, \"a\", 2);\n \tEXPECT_ERR(err);\n \treftable_log_record_release(&out[0]);\n \terr = reftable_iterator_next_log(&it, &out[0]);\ndiff --git a/reftable/reftable-merged.h b/reftable/reftable-merged.h\nindex c91a2d83a2..14d5fc9f05 100644\n--- a/reftable/reftable-merged.h\n+++ b/reftable/reftable-merged.h\n@@ -36,21 +36,6 @@ int reftable_new_merged_table(struct reftable_merged_table **dest,\n \t\t\t struct reftable_table *stack, size_t n,\n \t\t\t uint32_t hash_id);\n \n-/* returns an iterator positioned just before 'name' */\n-int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name);\n-\n-/* returns an iterator for log entry, at given update_index */\n-int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name, uint64_t update_index);\n-\n-/* like reftable_merged_table_seek_log_at but look for the newest entry. */\n-int reftable_merged_table_seek_log(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name);\n-\n /* returns the max update_index covered by this merged table. */\n uint64_t\n reftable_merged_table_max_update_index(struct reftable_merged_table *mt);\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 03f95935e1..7af4c3fd66 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -925,7 +925,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\tgoto done;\n \t}\n \n-\terr = reftable_merged_table_seek_ref(mt, &it, \"\");\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_REF);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -949,7 +950,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t}\n \treftable_iterator_destroy(&it);\n \n-\terr = reftable_merged_table_seek_log(mt, &it, \"\");\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);\n+\terr = reftable_iterator_seek_log(&it, \"\");\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -1340,9 +1342,11 @@ int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,\n int reftable_stack_read_log(struct reftable_stack *st, const char *refname,\n \t\t\t struct reftable_log_record *log)\n {\n-\tstruct reftable_iterator it = { NULL };\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(st);\n-\tint err = reftable_merged_table_seek_log(mt, &it, refname);\n+\tstruct reftable_iterator it = {0};\n+\tint err;\n+\n+\treftable_stack_init_log_iterator(st, &it);\n+\terr = reftable_iterator_seek_log(&it, refname);\n \tif (err)\n \t\tgoto done;\n \n-- \n2.45.0\n\n"},{"id":"494335","messageId":"xmqqwmo3x44s.fsf@gitster.g","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"Re: [PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-05-08T23:42:11Z","receivedAt":"2024-05-08T23:42:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> To address this inefficiency, the patch series at hand refactors the\n> reftable library such that creation of iterators and seeking on an\n> iterator are separate steps. This refactoring prepares us for reusing\n> iterators to perform multiple seeks, which in turn will allow us to\n> reuse internal data structures for subsequent seeks.\n\n;-)\n\n> Note: this series does not yet go all the way to re-seekable iterators,\n> and there are no users yet. The patch series is complex enough as-is\n> already, so I decided to defer that to the next iteration. Thus, the\n> whole refactoring here should essentially be a large no-op that prepares\n> the infrastructure for re-seekable iterators.\n>\n> The series depends on pks/reftable-write-optim at fa74f32291\n> (reftable/block: reuse compressed array, 2024-04-08).\n\nThere is another topic on reftable to make write options tweakable,\nwhose addition of reftable/dump and reader_print_blocks interface\nneeds to be adjusted to this change, I think.\n\n\n\n reftable/reader.c | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git c/reftable/reader.c w/reftable/reader.c\nindex 2ea830bdb6..fd516e01db 100644\n--- c/reftable/reader.c\n+++ w/reftable/reader.c\n@@ -841,7 +841,7 @@ int reftable_reader_print_blocks(const char *tablename)\n \t\t},\n \t};\n \tstruct reftable_block_source src = { 0 };\n-\tstruct table_iter ti = TABLE_ITER_INIT;\n+\tstruct table_iter *ti;\n \tstruct reftable_reader *r = NULL;\n \tsize_t i;\n \tint err;\n@@ -854,11 +854,14 @@ int reftable_reader_print_blocks(const char *tablename)\n \tif (err < 0)\n \t\tgoto done;\n \n+\tREFTABLE_ALLOC_ARRAY(ti, 1);\n+\ttable_iter_init(ti, r);\n+\n \tprintf(\"header:\\n\");\n \tprintf(\" block_size: %d\\n\", r->block_size);\n \n \tfor (i = 0; i < ARRAY_SIZE(sections); i++) {\n-\t\terr = reader_start(r, &ti, sections[i].type, 0);\n+\t\terr = table_iter_seek_start(ti, sections[i].type, 0);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \t\tif (err > 0)\n@@ -867,10 +870,10 @@ int reftable_reader_print_blocks(const char *tablename)\n \t\tprintf(\"%s:\\n\", sections[i].name);\n \n \t\twhile (1) {\n-\t\t\tprintf(\" - length: %u\\n\", ti.br.block_len);\n-\t\t\tprintf(\" restarts: %u\\n\", ti.br.restart_count);\n+\t\t\tprintf(\" - length: %u\\n\", ti->br.block_len);\n+\t\t\tprintf(\" restarts: %u\\n\", ti->br.restart_count);\n \n-\t\t\terr = table_iter_next_block(&ti);\n+\t\t\terr = table_iter_next_block(ti);\n \t\t\tif (err < 0)\n \t\t\t\tgoto done;\n \t\t\tif (err > 0)\n@@ -880,6 +883,6 @@ int reftable_reader_print_blocks(const char *tablename)\n \n done:\n \treftable_reader_free(r);\n-\ttable_iter_close(&ti);\n+\ttable_iter_close(ti);\n \treturn err;\n }\n"},{"id":"494339","messageId":"xmqqmsozx2j4.fsf@gitster.g","threadId":"61433","inReplyTo":"xmqqwmo3x44s.fsf@gitster.g","subject":"Re: [PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-05-09T00:16:47Z","receivedAt":"2024-05-09T00:16:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> diff --git c/reftable/reader.c w/reftable/reader.c\n> index 2ea830bdb6..fd516e01db 100644\n> --- c/reftable/reader.c\n> +++ w/reftable/reader.c\n> @@ -841,7 +841,7 @@ int reftable_reader_print_blocks(const char *tablename)\n> \t\t},\n> \t};\n> \tstruct reftable_block_source src = { 0 };\n> -\tstruct table_iter ti = TABLE_ITER_INIT;\n> +\tstruct table_iter *ti;\n> \tstruct reftable_reader *r = NULL;\n> \tsize_t i;\n> \tint err;\n\n... an unusually early error could skip everything here ...\n\n> @@ -880,6 +883,6 @@ int reftable_reader_print_blocks(const char *tablename)\n> \n> done:\n> \treftable_reader_free(r);\n> -\ttable_iter_close(&ti);\n> +\ttable_iter_close(ti);\n\n... and cause this to break. In the version of the merge-fix I\nused, *ti is initialized to NULL and the _close() is called only\nwhen ti is not NULL.\n\n> \treturn err;\n> }\n"},{"id":"494395","messageId":"Zj3RR-I1v1XwSuJ-@tanuki","threadId":"61433","inReplyTo":"xmqqwmo3x44s.fsf@gitster.g","subject":"Re: [PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-10T07:48:23Z","receivedAt":"2024-05-10T07:48:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, May 08, 2024 at 04:42:11PM -0700, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n> > To address this inefficiency, the patch series at hand refactors the\n> > reftable library such that creation of iterators and seeking on an\n> > iterator are separate steps. This refactoring prepares us for reusing\n> > iterators to perform multiple seeks, which in turn will allow us to\n> > reuse internal data structures for subsequent seeks.\n> \n> ;-)\n> \n> > Note: this series does not yet go all the way to re-seekable iterators,\n> > and there are no users yet. The patch series is complex enough as-is\n> > already, so I decided to defer that to the next iteration. Thus, the\n> > whole refactoring here should essentially be a large no-op that prepares\n> > the infrastructure for re-seekable iterators.\n> >\n> > The series depends on pks/reftable-write-optim at fa74f32291\n> > (reftable/block: reuse compressed array, 2024-04-08).\n> \n> There is another topic on reftable to make write options tweakable,\n> whose addition of reftable/dump and reader_print_blocks interface\n> needs to be adjusted to this change, I think.\n\nTrue, I forgot to double check that one. Your proposed resolution isn't\nquite correct as we now leak the `ti` pointer -- `table_iter_close()`\nonly closes the iterator and releases its underlying resources, but does\nnot free the iterator itself.\n\nThe below diff would be needed on top of what you currently have in\n`seen`. In any case though, I can also resend this topic with\nps/reftable-write-options pulled in as a dependency. Please let me know\nyour preference.\n\nPatrick\n\n-- >8 --\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 2d9630b7c2..83f6772e5d 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -841,8 +841,8 @@ int reftable_reader_print_blocks(const char *tablename)\n \t\t},\n \t};\n \tstruct reftable_block_source src = { 0 };\n-\tstruct table_iter *ti = NULL;\n \tstruct reftable_reader *r = NULL;\n+\tstruct table_iter ti = {0};\n \tsize_t i;\n \tint err;\n \n@@ -854,14 +854,13 @@ int reftable_reader_print_blocks(const char *tablename)\n \tif (err < 0)\n \t\tgoto done;\n \n-\tREFTABLE_ALLOC_ARRAY(ti, 1);\n-\ttable_iter_init(ti, r);\n+\ttable_iter_init(&ti, r);\n \n \tprintf(\"header:\\n\");\n \tprintf(\" block_size: %d\\n\", r->block_size);\n \n \tfor (i = 0; i < ARRAY_SIZE(sections); i++) {\n-\t\terr = table_iter_seek_start(ti, sections[i].type, 0);\n+\t\terr = table_iter_seek_start(&ti, sections[i].type, 0);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \t\tif (err > 0)\n@@ -870,10 +869,10 @@ int reftable_reader_print_blocks(const char *tablename)\n \t\tprintf(\"%s:\\n\", sections[i].name);\n \n \t\twhile (1) {\n-\t\t\tprintf(\" - length: %u\\n\", ti->br.block_len);\n-\t\t\tprintf(\" restarts: %u\\n\", ti->br.restart_count);\n+\t\t\tprintf(\" - length: %u\\n\", ti.br.block_len);\n+\t\t\tprintf(\" restarts: %u\\n\", ti.br.restart_count);\n \n-\t\t\terr = table_iter_next_block(ti);\n+\t\t\terr = table_iter_next_block(&ti);\n \t\t\tif (err < 0)\n \t\t\t\tgoto done;\n \t\t\tif (err > 0)\n@@ -883,7 +882,6 @@ int reftable_reader_print_blocks(const char *tablename)\n \n done:\n \treftable_reader_free(r);\n-\tif (ti)\n-\t\ttable_iter_close(ti);\n+\ttable_iter_close(&ti);\n \treturn err;\n }\n"},{"id":"494469","messageId":"xmqq1q697jzr.fsf@gitster.g","threadId":"61433","inReplyTo":"Zj3RR-I1v1XwSuJ-@tanuki","subject":"Re: [PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-05-10T15:40:56Z","receivedAt":"2024-05-10T15:41:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> The below diff would be needed on top of what you currently have in\n> `seen`. In any case though, I can also resend this topic with\n> ps/reftable-write-options pulled in as a dependency. Please let me know\n> your preference.\n\nIs it \"needed\", in the sense that \"without the fix what you posted\nis broken in such and such ways\", or is it \"I think it is niceR to\nhave it on stack because this one instance does not have to be on\nheap\"? To me, they look equivalent and I have no problems with the\n\"nicer\" variant, but your \"needed\" makes me wonder if I am missing\nsome correctness invariants I am violating without realizing.\n\nThanks.\n"},{"id":"494472","messageId":"Zj5HvF-Uq0uWranj@framework","threadId":"61433","inReplyTo":"xmqq1q697jzr.fsf@gitster.g","subject":"Re: [PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-10T16:13:48Z","receivedAt":"2024-05-10T16:13:55Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, May 10, 2024 at 08:40:56AM -0700, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n> > The below diff would be needed on top of what you currently have in\n> > `seen`. In any case though, I can also resend this topic with\n> > ps/reftable-write-options pulled in as a dependency. Please let me know\n> > your preference.\n> \n> Is it \"needed\", in the sense that \"without the fix what you posted\n> is broken in such and such ways\", or is it \"I think it is niceR to\n> have it on stack because this one instance does not have to be on\n> heap\"? To me, they look equivalent and I have no problems with the\n> \"nicer\" variant, but your \"needed\" makes me wonder if I am missing\n> some correctness invariants I am violating without realizing.\n\nIt's needed in the sense that your version leaks memory -- the `ti`\npointer is never free'd. Other than that they are equivalent indeed.\n\nPatrick\n"},{"id":"494481","messageId":"xmqq8r0h60yc.fsf@gitster.g","threadId":"61433","inReplyTo":"Zj5HvF-Uq0uWranj@framework","subject":"Re: [PATCH 00/13] reftable: prepare for re-seekable iterators","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-05-10T17:17:31Z","receivedAt":"2024-05-10T17:17:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> It's needed in the sense that your version leaks memory -- the `ti`\n> pointer is never free'd. Other than that they are equivalent indeed.\n\nAh, OK, I somehow misread that _close() will free the resource, but\nit only frees the resources held by the shell and not the shell\nitself.\n\nThanks.\n"},{"id":"494491","messageId":"dqnhhjdingkhhwwp5nwut2hsnkkze7m2ls4kscddqxm3txjzbf@5knvdk4vc6eg","threadId":"61433","inReplyTo":"21b3e3ab5f04e66fdd352187b1da699d1ab67cee.1715166175.git.ps@pks.im","subject":"Re: [PATCH 07/13] reftable/merged: split up initialization and seeking of records","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-05-10T19:18:16Z","receivedAt":"2024-05-10T19:19:42Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> To initialize a `struct merged_iter`, we need to seek all subiterators\n> to the wanted record and then add their results to the priority queue\n> used to sort the records. This logic is split up across two functions,\n> `merged_table_seek_record()` and `merged_table_iter()`. The scope of\n\nDid we mean `merged_iter_init` instead of `merged_table_iter()` here?\n\n> these functions is somewhat weird though, where `merged_table_iter()` is\n> only responsible for adding the records of the subiterators to the\n> priority queue.\n> \n> Clarify the scope of those functions such that `merged_table_iter()` is\n> only responsible for initializing the iterator's structure. Performing\n> the subiterator seeks are now part of `merged_table_seek_record()`.\n> \n> This step is required to move seeking of records into the generic\n> `struct reftable_iterator` infrastructure.\n> \n> Signed-off-by: Patrick Steinhardt \n...\n> @@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n> \t\t\t\t struct reftable_iterator *it,\n> \t\t\t\t struct reftable_record *rec)\n> {\n> -\tstruct merged_iter merged = {\n> -\t\t.typ = reftable_record_type(rec),\n> -\t\t.hash_id = mt->hash_id,\n> -\t\t.suppress_deletions = mt->suppress_deletions,\n> -\t\t.advance_index = -1,\n> -\t};\n> -\tstruct merged_iter *p;\n> +\tstruct merged_iter merged, *p;\n> \tint err;\n> \n> -\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n> +\tmerged_iter_init(&merged, mt);\n> +\n> \tfor (size_t i = 0; i < mt->stack_len; i++) {\n> +\t\treftable_record_init(&merged.subiters[merged.stack_len].rec,\n> +\t\t\t\t reftable_record_type(rec));\n\nI find it somewhat confusing how we increment the subiterator index\nhere. I assume this is because when a record is not found we don't want\nto add it to the index. Might be nice to add a comment here explaining\nthis.\n\nEdit: Looks like you address this in the next commit so I guess we are\ngood :)\n\n> +\n> \t\terr = reftable_table_seek_record(&mt->stack[i],\n> \t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n> \t\tif (err < 0)\n> \t\t\tgoto out;\n> -\t\tif (!err)\n> -\t\t\tmerged.stack_len++;\n> -\t}\n> +\t\tif (err > 0)\n> +\t\t\tcontinue;\n> \n> -\terr = merged_iter_init(&merged);\n> -\tif (err < 0)\n> -\t\tgoto out;\n> +\t\terr = merged_iter_advance_subiter(&merged, merged.stack_len);\n> +\t\tif (err < 0)\n> +\t\t\tgoto out;\n> +\n> +\t\tmerged.stack_len++;\n> +\t}\n> \n> -\tp = reftable_malloc(sizeof(struct merged_iter));\n> +\tp = reftable_malloc(sizeof(*p));\n> \t*p = merged;\n> \titerator_from_merged_iter(it, p);\n> +\terr = 0;\n> \n> out:\n> \tif (err < 0)\n> -- \n> 2.45.0\n> \n\n\n"},{"id":"494492","messageId":"uecirknp6pdo5amkv6kvfvxryiptqrgblttbu6dhz3vh74obzd@7dwnx3agsllr","threadId":"61433","inReplyTo":"f0f42cd56b9e54e9c7d58be41fcc4e226d5c76ff.1715166175.git.ps@pks.im","subject":"Re: [PATCH 08/13] reftable/merged: simplify indices for subiterators","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-05-10T19:25:09Z","receivedAt":"2024-05-10T19:26:35Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> When seeking on a merged table, we perform the seek for each of the\n> subiterators. If the subiterator hasa the desired record we add it to\n\ns/hasa/has/\n\n> the priority queue, otherwise we skip it and don't add it to the stack\n> of subiterators hosted by the merged table.\n> \n> The consequence of this is that the index of the subiterator in the\n> merged table does not necessarily correspond to the index of it in the\n> merged iterator. Next to being potentially confusing, it also means that\n> we won't easily be able to re-seek the merged iterator because we have\n> no clear connection between both of the data structures.\n\nAh, I also found this a bit confusing. I think this is a good change.\n> \n> Refactor the code so that the index stays the same in both structures.\n\nWas there any advantage to not adding subiterators to the stack\noriginally? It looks like it adding them doesn't affect anything.\n\n-Justin\n"},{"id":"494514","messageId":"4pyzm53ioaqt5men72ti4ffu7zjbpigytfgcyg4h2q7657zoji@7hlrvlt2cws2","threadId":"61433","inReplyTo":"859b399e71e92dd7aa0fa7fc9f2d9ca6f389d34a.1715166175.git.ps@pks.im","subject":"Re: [PATCH 09/13] reftable/generic: move seeking of records into the iterator","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-05-10T21:44:54Z","receivedAt":"2024-05-10T21:46:20Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> Reftable iterators are created by seeking on the parent structure of a\n> corresponding record. For example, to create an iterator for the merged\n> table you would call `reftable_merged_table_seek_ref()`. Most notably,\n> it is not posible to create an iterator and then seek it afterwards.\n> \n> While this may be a bit easier to reason about, it comes with two\n> significant downsides. The first downside is that the logic to find\n> records is split up between the parent data structure and the iterator\n> itself. Conceptually, it is more straight forward if all that logic was\n> contained in a single place, which should be the iterator.\n> \n> The second and more significant downside is that it is impossible to\n> reuse iterators for multiple seeks. Whenever you want to look up a\n> record, you need to re-create the whole infrastructure again, which is\n> quite a waste of time. Furthermore, it is impossible to for example\n> optimize seeks, for example when seeking the same record multiple times.\n\nThe last setence could use some rewording.\n\n\"Furthermore, it is impossible to optimize seeks, such as when seeking\nthe same record multiple times.\"\n\n> \n> To address this, we essentially split up the concerns properly such that\n> the parent data structure is responsible for setting up the iterator via\n> a new `init_iter()` callback, whereas the iterator handles seeks via a\n> new `seek()` callback. This will eventually allow us to call `seek()` on\n> the iterator multiple times, where every iterator can potentially\n> optimize for certain cases.\n> \n> Note that at this point in time we are not yet ready to reuse the\n> iterators. This will be left for a future patch series.\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/generic.c | 47 +++++++++++++----\n> reftable/generic.h | 9 +++-\n> reftable/iter.c | 15 ++++++\n> reftable/merged.c | 97 +++++++++++++++++-----------------\n> reftable/reader.c | 126 +++++++++++++++++++++++++--------------------\n> 5 files changed, 177 insertions(+), 117 deletions(-)\n> \n> diff --git a/reftable/generic.c b/reftable/generic.c\n> index b9f1c7c18a..1cf68fe124 100644\n> --- a/reftable/generic.c\n> +++ b/reftable/generic.c\n> @@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at\n> #include \"reftable-iterator.h\"\n> #include \"reftable-generic.h\"\n> \n> +void table_init_iter(struct reftable_table *tab,\n\nThe following table related functions are prefixed with `reftable_`. Do\nwe want to do the same here?\n\n> +\t\t struct reftable_iterator *it,\n> +\t\t uint8_t typ)\n> +{\n> +\n> +\ttab->ops->init_iter(tab->table_arg, it, typ);\n> +}\n> +\n> int reftable_table_seek_ref(struct reftable_table *tab,\n> \t\t\t struct reftable_iterator *it, const char *name)\n> {\n> -\tstruct reftable_record rec = { .type = BLOCK_TYPE_REF,\n> -\t\t\t\t .u.ref = {\n> -\t\t\t\t\t .refname = (char *)name,\n> -\t\t\t\t } };\n> -\treturn tab->ops->seek_record(tab->table_arg, it, &rec);\n> +\tstruct reftable_record want = {\n> +\t\t.type = BLOCK_TYPE_REF,\n> +\t\t.u.ref = {\n> +\t\t\t.refname = (char *)name,\n> +\t\t},\n> +\t};\n> +\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n> +\treturn it->ops->seek(it->iter_arg, &want);\n> }\n> \n> int reftable_table_seek_log(struct reftable_table *tab,\n> \t\t\t struct reftable_iterator *it, const char *name)\n> {\n> -\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n> -\t\t\t\t .u.log = {\n> -\t\t\t\t\t .refname = (char *)name,\n> -\t\t\t\t\t .update_index = ~((uint64_t)0),\n> -\t\t\t\t } };\n> -\treturn tab->ops->seek_record(tab->table_arg, it, &rec);\n> +\tstruct reftable_record want = {\n> +\t\t.type = BLOCK_TYPE_LOG,\n> +\t\t.u.log = {\n> +\t\t\t.refname = (char *)name,\n> +\t\t\t.update_index = ~((uint64_t)0),\n> +\t\t},\n> +\t};\n> +\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n> +\treturn it->ops->seek(it->iter_arg, &want);\n> }\n> \n> int reftable_table_read_ref(struct reftable_table *tab, const char *name,\n...\n> @@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)\n> \treftable_iterator_destroy(&fri->it);\n> }\n> \n> +static int filtering_ref_iterator_seek(void *iter_arg,\n> +\t\t\t\t struct reftable_record *want)\n> +{\n> +\tstruct filtering_ref_iterator *fri = iter_arg;\n> +\treturn iterator_seek(&fri->it, want);\n> +}\n\nI've found the `filtering_ref_iterator_seek()` here to be a little\nconfusing. At first, I assumed that the `filtering_ref_iterator` would\nhave referenced `filtering_ref_iterator_vtable` thus resulting in a\ncycle, but on closer inspection this does not seem to be the case and is\nin face always set to some other iterator operation.\n\nAm I understanding this correctly?\n\n-Justin\n"},{"id":"494515","messageId":"odftefkdt65kt4qiptd4tfnlssymmv2wnpzz4uefq6sxycxdsr@b5jm42ulf3b2","threadId":"61433","inReplyTo":"f688f8f59a05b667b4f4118b7f8c7504bd33329a.1715166175.git.ps@pks.im","subject":"Re: [PATCH 11/13] reftable/reader: adapt interface to allow reuse of iterators","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-05-10T21:48:45Z","receivedAt":"2024-05-10T21:50:11Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n\n> +/* Initialize a reftable iterator for reading refs. */\n> +void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n> +\t\t\t\t struct reftable_iterator *it);\n> +\n> +/* Initialize a reftable iterator for reading refs. */\n\nI think you meant to say \"reading logs\" here.\n\n> +void reftable_reader_init_log_iterator(struct reftable_reader *r,\n> +\t\t\t\t struct reftable_iterator *it);\n> \n"},{"id":"494585","messageId":"ZkHQ-yAtzm1GNqFY@tanuki","threadId":"61433","inReplyTo":"dqnhhjdingkhhwwp5nwut2hsnkkze7m2ls4kscddqxm3txjzbf@5knvdk4vc6eg","subject":"Re: [PATCH 07/13] reftable/merged: split up initialization and seeking of records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:36:11Z","receivedAt":"2024-05-13T08:36:19Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, May 10, 2024 at 02:18:16PM -0500, Justin Tobler wrote:\n> On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> > To initialize a `struct merged_iter`, we need to seek all subiterators\n> > to the wanted record and then add their results to the priority queue\n> > used to sort the records. This logic is split up across two functions,\n> > `merged_table_seek_record()` and `merged_table_iter()`. The scope of\n> \n> Did we mean `merged_iter_init` instead of `merged_table_iter()` here?\n\nIndeed, good catch.\n\n> > @@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n> > \t\t\t\t struct reftable_iterator *it,\n> > \t\t\t\t struct reftable_record *rec)\n> > {\n> > -\tstruct merged_iter merged = {\n> > -\t\t.typ = reftable_record_type(rec),\n> > -\t\t.hash_id = mt->hash_id,\n> > -\t\t.suppress_deletions = mt->suppress_deletions,\n> > -\t\t.advance_index = -1,\n> > -\t};\n> > -\tstruct merged_iter *p;\n> > +\tstruct merged_iter merged, *p;\n> > \tint err;\n> > \n> > -\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n> > +\tmerged_iter_init(&merged, mt);\n> > +\n> > \tfor (size_t i = 0; i < mt->stack_len; i++) {\n> > +\t\treftable_record_init(&merged.subiters[merged.stack_len].rec,\n> > +\t\t\t\t reftable_record_type(rec));\n> \n> I find it somewhat confusing how we increment the subiterator index\n> here. I assume this is because when a record is not found we don't want\n> to add it to the index. Might be nice to add a comment here explaining\n> this.\n> \n> Edit: Looks like you address this in the next commit so I guess we are\n> good :)\n\nSeconded. And yes, as you noticed, this is one of the reasons why I\nchange this in the next patch.\n\nPatrick\n"},{"id":"494586","messageId":"ZkHRApu7WvdihQBe@tanuki","threadId":"61433","inReplyTo":"uecirknp6pdo5amkv6kvfvxryiptqrgblttbu6dhz3vh74obzd@7dwnx3agsllr","subject":"Re: [PATCH 08/13] reftable/merged: simplify indices for subiterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:36:18Z","receivedAt":"2024-05-13T08:36:22Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, May 10, 2024 at 02:25:09PM -0500, Justin Tobler wrote:\n> On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> > When seeking on a merged table, we perform the seek for each of the\n> > subiterators. If the subiterator hasa the desired record we add it to\n> \n> s/hasa/has/\n\nFixed.\n\n> > the priority queue, otherwise we skip it and don't add it to the stack\n> > of subiterators hosted by the merged table.\n> > \n> > The consequence of this is that the index of the subiterator in the\n> > merged table does not necessarily correspond to the index of it in the\n> > merged iterator. Next to being potentially confusing, it also means that\n> > we won't easily be able to re-seek the merged iterator because we have\n> > no clear connection between both of the data structures.\n> \n> Ah, I also found this a bit confusing. I think this is a good change.\n> > \n> > Refactor the code so that the index stays the same in both structures.\n> \n> Was there any advantage to not adding subiterators to the stack\n> originally? It looks like it adding them doesn't affect anything.\n\nNot to the best of my knowledge, no.\n\nPatrick\n"},{"id":"494587","messageId":"ZkHRCKwJiAfx0Z1a@tanuki","threadId":"61433","inReplyTo":"4pyzm53ioaqt5men72ti4ffu7zjbpigytfgcyg4h2q7657zoji@7hlrvlt2cws2","subject":"Re: [PATCH 09/13] reftable/generic: move seeking of records into the iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:36:24Z","receivedAt":"2024-05-13T08:36:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, May 10, 2024 at 04:44:54PM -0500, Justin Tobler wrote:\n> On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> > Reftable iterators are created by seeking on the parent structure of a\n> > corresponding record. For example, to create an iterator for the merged\n> > table you would call `reftable_merged_table_seek_ref()`. Most notably,\n> > it is not posible to create an iterator and then seek it afterwards.\n> > \n> > While this may be a bit easier to reason about, it comes with two\n> > significant downsides. The first downside is that the logic to find\n> > records is split up between the parent data structure and the iterator\n> > itself. Conceptually, it is more straight forward if all that logic was\n> > contained in a single place, which should be the iterator.\n> > \n> > The second and more significant downside is that it is impossible to\n> > reuse iterators for multiple seeks. Whenever you want to look up a\n> > record, you need to re-create the whole infrastructure again, which is\n> > quite a waste of time. Furthermore, it is impossible to for example\n> > optimize seeks, for example when seeking the same record multiple times.\n> \n> The last setence could use some rewording.\n> \n> \"Furthermore, it is impossible to optimize seeks, such as when seeking\n> the same record multiple times.\"\n\nDone.\n\n[snip]\n> > diff --git a/reftable/generic.c b/reftable/generic.c\n> > index b9f1c7c18a..1cf68fe124 100644\n> > --- a/reftable/generic.c\n> > +++ b/reftable/generic.c\n> > @@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at\n> > #include \"reftable-iterator.h\"\n> > #include \"reftable-generic.h\"\n> > \n> > +void table_init_iter(struct reftable_table *tab,\n> \n> The following table related functions are prefixed with `reftable_`. Do\n> we want to do the same here?\n\nFunctions with the `reftable_` prefix are supposed to be public, whereas\nfunctions without them are private. So this is intentionally missing the\nprefix.\n\n[snip]\n> > @@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)\n> > \treftable_iterator_destroy(&fri->it);\n> > }\n> > \n> > +static int filtering_ref_iterator_seek(void *iter_arg,\n> > +\t\t\t\t struct reftable_record *want)\n> > +{\n> > +\tstruct filtering_ref_iterator *fri = iter_arg;\n> > +\treturn iterator_seek(&fri->it, want);\n> > +}\n> \n> I've found the `filtering_ref_iterator_seek()` here to be a little\n> confusing. At first, I assumed that the `filtering_ref_iterator` would\n> have referenced `filtering_ref_iterator_vtable` thus resulting in a\n> cycle, but on closer inspection this does not seem to be the case and is\n> in face always set to some other iterator operation.\n> \n> Am I understanding this correctly?\n\nYes. The filtering ref iterator wraps a _different_ iterator, which is\n`fri->it` in the above case, and only returns a subset of the records of\nthat wrapped iterator. So we eventually end up calling the callbacks of\nthe wrapped iterator, which are likely not a filtering ref iterator\nthemselves (even though that would in theory be possible).\n\nPatrick\n"},{"id":"494588","messageId":"ZkHRD8zn_KFmJVqi@tanuki","threadId":"61433","inReplyTo":"odftefkdt65kt4qiptd4tfnlssymmv2wnpzz4uefq6sxycxdsr@b5jm42ulf3b2","subject":"Re: [PATCH 11/13] reftable/reader: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:36:31Z","receivedAt":"2024-05-13T08:36:35Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, May 10, 2024 at 04:48:45PM -0500, Justin Tobler wrote:\n> On 24/05/08 01:04PM, Patrick Steinhardt wrote:\n> \n> > +/* Initialize a reftable iterator for reading refs. */\n> > +void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n> > +\t\t\t\t struct reftable_iterator *it);\n> > +\n> > +/* Initialize a reftable iterator for reading refs. */\n> \n> I think you meant to say \"reading logs\" here.\n\nIndeed, thanks!\n\nPatrick\n\n> > +void reftable_reader_init_log_iterator(struct reftable_reader *r,\n> > +\t\t\t\t struct reftable_iterator *it);\n> > \n"},{"id":"494589","messageId":"cover.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715166175.git.ps@pks.im","subject":"[PATCH v2 00/13] reftable: prepare for re-seekable iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:46:56Z","receivedAt":"2024-05-13T08:47:01Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second version of my patch series that prepares the reftable\niterators to become re-seekable. These refactorings will eventually\nallow us to reuse data structures by iterators and optimize for certain\ncases.\n\nChanges compared to v1:\n\n - Various fixes to commit messages.\n\n - Fixed a copy & pasted comment to refer to logs instead of refs.\n\nThe series continues to build on top of ps/reftable-write-optim. There\nis a merge conflict with the in-flight ps/reftable-write-options, but\ngiven that this series has not yet been merged to next and because Junio\nhas already resolved the conflict in \"seen\" I decided to not pull it in\nas an additional dependency.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (13):\n reftable/block: use `size_t` to track restart point index\n reftable/reader: avoid copying index iterator\n reftable/reader: unify indexed and linear seeking\n reftable/reader: separate concerns of table iter and reftable reader\n reftable/reader: inline `reader_seek_internal()`\n reftable/reader: set up the reader when initializing table iterator\n reftable/merged: split up initialization and seeking of records\n reftable/merged: simplify indices for subiterators\n reftable/generic: move seeking of records into the iterator\n reftable/generic: adapt interface to allow reuse of iterators\n reftable/reader: adapt interface to allow reuse of iterators\n reftable/stack: provide convenience functions to create iterators\n reftable/merged: adapt interface to allow reuse of iterators\n\n refs/reftable-backend.c | 48 ++++----\n reftable/block.c | 4 +-\n reftable/generic.c | 94 +++++++++++----\n reftable/generic.h | 9 +-\n reftable/iter.c | 23 +++-\n reftable/merged.c | 148 ++++++++----------------\n reftable/merged.h | 6 +\n reftable/merged_test.c | 19 ++-\n reftable/reader.c | 218 +++++++++++++++--------------------\n reftable/readwrite_test.c | 35 ++++--\n reftable/reftable-generic.h | 8 +-\n reftable/reftable-iterator.h | 21 ++++\n reftable/reftable-merged.h | 15 ---\n reftable/reftable-reader.h | 45 ++------\n reftable/reftable-stack.h | 18 +++\n reftable/stack.c | 29 ++++-\n 16 files changed, 378 insertions(+), 362 deletions(-)\n\nRange-diff against v1:\n 1: ca86a8b58d = 1: ca86a8b58d reftable/block: use `size_t` to track restart point index\n 2: bdbebdbd36 = 2: bdbebdbd36 reftable/reader: avoid copying index iterator\n 3: 716863a580 = 3: 716863a580 reftable/reader: unify indexed and linear seeking\n 4: 91db2f18c1 = 4: 91db2f18c1 reftable/reader: separate concerns of table iter and reftable reader\n 5: 4d498ef342 = 5: 4d498ef342 reftable/reader: inline `reader_seek_internal()`\n 6: 5a10a11584 = 6: 5a10a11584 reftable/reader: set up the reader when initializing table iterator\n 7: 21b3e3ab5f ! 7: 12c10fd366 reftable/merged: split up initialization and seeking of records\n @@ Commit message\n To initialize a `struct merged_iter`, we need to seek all subiterators\n to the wanted record and then add their results to the priority queue\n used to sort the records. This logic is split up across two functions,\n - `merged_table_seek_record()` and `merged_table_iter()`. The scope of\n - these functions is somewhat weird though, where `merged_table_iter()` is\n + `merged_table_seek_record()` and `merged_iter_init()`. The scope of\n + these functions is somewhat weird though, where `merged_iter_init()` is\n only responsible for adding the records of the subiterators to the\n priority queue.\n \n - Clarify the scope of those functions such that `merged_table_iter()` is\n + Clarify the scope of those functions such that `merged_iter_init()` is\n only responsible for initializing the iterator's structure. Performing\n the subiterator seeks are now part of `merged_table_seek_record()`.\n \n 8: f0f42cd56b ! 8: 31bdfc1e34 reftable/merged: simplify indices for subiterators\n @@ Commit message\n reftable/merged: simplify indices for subiterators\n \n When seeking on a merged table, we perform the seek for each of the\n - subiterators. If the subiterator hasa the desired record we add it to\n - the priority queue, otherwise we skip it and don't add it to the stack\n - of subiterators hosted by the merged table.\n + subiterators. If the subiterator has the desired record we add it to the\n + priority queue, otherwise we skip it and don't add it to the stack of\n + subiterators hosted by the merged table.\n \n The consequence of this is that the index of the subiterator in the\n merged table does not necessarily correspond to the index of it in the\n 9: 859b399e71 ! 9: 3e91c3830e reftable/generic: move seeking of records into the iterator\n @@ Commit message\n The second and more significant downside is that it is impossible to\n reuse iterators for multiple seeks. Whenever you want to look up a\n record, you need to re-create the whole infrastructure again, which is\n - quite a waste of time. Furthermore, it is impossible to for example\n - optimize seeks, for example when seeking the same record multiple times.\n + quite a waste of time. Furthermore, it is impossible to optimize seeks,\n + such as when seeking the same record multiple times.\n \n To address this, we essentially split up the concerns properly such that\n the parent data structure is responsible for setting up the iterator via\n10: 727b8fa432 = 10: b0641dd800 reftable/generic: adapt interface to allow reuse of iterators\n11: f688f8f59a ! 11: 0745951650 reftable/reader: adapt interface to allow reuse of iterators\n @@ reftable/reftable-reader.h: struct reftable_table;\n +void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n +\t\t\t\t struct reftable_iterator *it);\n +\n -+/* Initialize a reftable iterator for reading refs. */\n ++/* Initialize a reftable iterator for reading logs. */\n +void reftable_reader_init_log_iterator(struct reftable_reader *r,\n +\t\t\t\t struct reftable_iterator *it);\n \n12: 68cc35919b = 12: 51480c4328 reftable/stack: provide convenience functions to create iterators\n13: be4da295c6 = 13: 2586e93c44 reftable/merged: adapt interface to allow reuse of iterators\n-- \n2.45.GIT\n\n"},{"id":"494590","messageId":"ca86a8b58dd074287dd2dd352610ffe46e1605b9.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 01/13] reftable/block: use `size_t` to track restart point index","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:01Z","receivedAt":"2024-05-13T08:47:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `block_reader_restart_offset()` gets the offset of the\n`i`th restart point. `i` is a signed integer though, which is certainly\nnot the correct type to track indices like this. Furthermore, both\ncallers end up passing a `size_t`.\n\nRefactor the code to use a `size_t` instead.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 5942cb4053..00030eee06 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -326,9 +326,9 @@ int block_reader_first_key(const struct block_reader *br, struct strbuf *key)\n \treturn 0;\n }\n \n-static uint32_t block_reader_restart_offset(const struct block_reader *br, int i)\n+static uint32_t block_reader_restart_offset(const struct block_reader *br, size_t idx)\n {\n-\treturn get_be24(br->restart_bytes + 3 * i);\n+\treturn get_be24(br->restart_bytes + 3 * idx);\n }\n \n void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)\n-- \n2.45.GIT\n\n"},{"id":"494591","messageId":"bdbebdbd363fc264c6327e7bf0af29ee5357e83d.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 02/13] reftable/reader: avoid copying index iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:06Z","receivedAt":"2024-05-13T08:47:10Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing an indexed seek we need to walk down the multi-level index\nuntil we finally hit a record of the desired indexed type. This loop\nperforms a copy of the index iterator on every iteration, which is both\nhard to understand and completely unnecessary.\n\nRefactor the code so that we use a single iterator to walk down the\nindices, only.\n\nNote that while this should improve performance, the improvement is\nnegligible in all but the most unreasonable repositories. This is\nbecause the effect is only really noticeable when we have to walk down\nmany levels of indices, which is not something that a repository would\ntypically have. So the motivation for this change is really only about\nreadability.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 38 ++++++++++++++------------------------\n 1 file changed, 14 insertions(+), 24 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 481dff10d4..6bfadcad71 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -510,13 +510,11 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t.type = BLOCK_TYPE_INDEX,\n \t\t.u.idx = { .last_key = STRBUF_INIT },\n \t};\n-\tstruct table_iter index_iter = TABLE_ITER_INIT;\n-\tstruct table_iter empty = TABLE_ITER_INIT;\n-\tstruct table_iter next = TABLE_ITER_INIT;\n+\tstruct table_iter ti = TABLE_ITER_INIT, *malloced;\n \tint err = 0;\n \n \treftable_record_key(rec, &want_index.u.idx.last_key);\n-\terr = reader_start(r, &index_iter, reftable_record_type(rec), 1);\n+\terr = reader_start(r, &ti, reftable_record_type(rec), 1);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -526,7 +524,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t * highest layer that identifies the relevant index block as well as\n \t * the record inside that block that corresponds to our wanted key.\n \t */\n-\terr = reader_seek_linear(&index_iter, &want_index);\n+\terr = reader_seek_linear(&ti, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -552,44 +550,36 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t * all levels of the index only to find out that the key does\n \t\t * not exist.\n \t\t */\n-\t\terr = table_iter_next(&index_iter, &index_result);\n+\t\terr = table_iter_next(&ti, &index_result);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = reader_table_iter_at(r, &next, index_result.u.idx.offset,\n-\t\t\t\t\t 0);\n+\t\terr = reader_table_iter_at(r, &ti, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek_key(&next.bi, &next.br, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&ti.bi, &ti.br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\tif (next.typ == reftable_record_type(rec)) {\n+\t\tif (ti.typ == reftable_record_type(rec)) {\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (next.typ != BLOCK_TYPE_INDEX) {\n+\t\tif (ti.typ != BLOCK_TYPE_INDEX) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n-\t\t\tbreak;\n+\t\t\tgoto done;\n \t\t}\n-\n-\t\ttable_iter_close(&index_iter);\n-\t\tindex_iter = next;\n-\t\tnext = empty;\n \t}\n \n-\tif (err == 0) {\n-\t\tstruct table_iter *malloced = reftable_calloc(1, sizeof(*malloced));\n-\t\t*malloced = next;\n-\t\tnext = empty;\n-\t\titerator_from_table_iter(it, malloced);\n-\t}\n+\tREFTABLE_ALLOC_ARRAY(malloced, 1);\n+\t*malloced = ti;\n+\titerator_from_table_iter(it, malloced);\n \n done:\n-\ttable_iter_close(&next);\n-\ttable_iter_close(&index_iter);\n+\tif (err)\n+\t\ttable_iter_close(&ti);\n \treftable_record_release(&want_index);\n \treftable_record_release(&index_result);\n \treturn err;\n-- \n2.45.GIT\n\n"},{"id":"494592","messageId":"716863a580f9e1ef8ea796c25c97e50c63585a7b.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 03/13] reftable/reader: unify indexed and linear seeking","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:11Z","receivedAt":"2024-05-13T08:47:16Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In `reader_seek_internal()` we either end up doing an indexed seek when\nthere is one or a linear seek otherwise. These two code paths are\ndisjunct without a good reason, where the indexed seek will cause us to\nexit early.\n\nRefactor the two code paths such that it becomes possible to share a bit\nmore code between them.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 42 ++++++++++++++++--------------------------\n 1 file changed, 16 insertions(+), 26 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 6bfadcad71..cf7f126d8d 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -425,7 +425,7 @@ static int reader_seek_linear(struct table_iter *ti,\n \tstruct strbuf want_key = STRBUF_INIT;\n \tstruct strbuf got_key = STRBUF_INIT;\n \tstruct reftable_record rec;\n-\tint err = -1;\n+\tint err;\n \n \treftable_record_init(&rec, reftable_record_type(want));\n \treftable_record_key(want, &want_key);\n@@ -499,8 +499,8 @@ static int reader_seek_linear(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek_indexed(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it,\n+static int reader_seek_indexed(struct table_iter *ti,\n+\t\t\t struct reftable_reader *r,\n \t\t\t struct reftable_record *rec)\n {\n \tstruct reftable_record want_index = {\n@@ -510,13 +510,9 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t.type = BLOCK_TYPE_INDEX,\n \t\t.u.idx = { .last_key = STRBUF_INIT },\n \t};\n-\tstruct table_iter ti = TABLE_ITER_INIT, *malloced;\n-\tint err = 0;\n+\tint err;\n \n \treftable_record_key(rec, &want_index.u.idx.last_key);\n-\terr = reader_start(r, &ti, reftable_record_type(rec), 1);\n-\tif (err < 0)\n-\t\tgoto done;\n \n \t/*\n \t * The index may consist of multiple levels, where each level may have\n@@ -524,7 +520,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t * highest layer that identifies the relevant index block as well as\n \t * the record inside that block that corresponds to our wanted key.\n \t */\n-\terr = reader_seek_linear(&ti, &want_index);\n+\terr = reader_seek_linear(ti, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -550,36 +546,30 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t * all levels of the index only to find out that the key does\n \t\t * not exist.\n \t\t */\n-\t\terr = table_iter_next(&ti, &index_result);\n+\t\terr = table_iter_next(ti, &index_result);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = reader_table_iter_at(r, &ti, index_result.u.idx.offset, 0);\n+\t\terr = reader_table_iter_at(r, ti, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek_key(&ti.bi, &ti.br, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&ti->bi, &ti->br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\tif (ti.typ == reftable_record_type(rec)) {\n+\t\tif (ti->typ == reftable_record_type(rec)) {\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (ti.typ != BLOCK_TYPE_INDEX) {\n+\t\tif (ti->typ != BLOCK_TYPE_INDEX) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n \t\t\tgoto done;\n \t\t}\n \t}\n \n-\tREFTABLE_ALLOC_ARRAY(malloced, 1);\n-\t*malloced = ti;\n-\titerator_from_table_iter(it, malloced);\n-\n done:\n-\tif (err)\n-\t\ttable_iter_close(&ti);\n \treftable_record_release(&want_index);\n \treftable_record_release(&index_result);\n \treturn err;\n@@ -595,15 +585,15 @@ static int reader_seek_internal(struct reftable_reader *r,\n \tstruct table_iter ti = TABLE_ITER_INIT, *p;\n \tint err;\n \n-\tif (idx > 0)\n-\t\treturn reader_seek_indexed(r, it, rec);\n-\n-\terr = reader_start(r, &ti, reftable_record_type(rec), 0);\n+\terr = reader_start(r, &ti, reftable_record_type(rec), !!idx);\n \tif (err < 0)\n \t\tgoto out;\n \n-\terr = reader_seek_linear(&ti, rec);\n-\tif (err < 0)\n+\tif (idx)\n+\t\terr = reader_seek_indexed(&ti, r, rec);\n+\telse\n+\t\terr = reader_seek_linear(&ti, rec);\n+\tif (err)\n \t\tgoto out;\n \n \tREFTABLE_ALLOC_ARRAY(p, 1);\n-- \n2.45.GIT\n\n"},{"id":"494593","messageId":"91db2f18c105611bc85fa07fa6eb33ba600e742a.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 04/13] reftable/reader: separate concerns of table iter and reftable reader","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:16Z","receivedAt":"2024-05-13T08:47:20Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In \"reftable/reader.c\" we implement two different interfaces:\n\n - The reftable reader contains the logic to read reftables.\n\n - The table iterator is used to iterate through a single reftable read\n by the reader.\n\nThe way those two types are used in the code is somewhat confusing\nthough because seeking inside a table is implemented as if it was part\nof the reftable reader, even though it is ultimately more of a detail\nimplemented by the table iterator.\n\nMake the boundary between those two types clearer by renaming functions\nthat seek records in a table such that they clearly belong to the table\niterator's logic.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 32 +++++++++++++++-----------------\n 1 file changed, 15 insertions(+), 17 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex cf7f126d8d..b210753441 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -386,9 +386,8 @@ static void iterator_from_table_iter(struct reftable_iterator *it,\n \tit->ops = &table_iter_vtable;\n }\n \n-static int reader_table_iter_at(struct reftable_reader *r,\n-\t\t\t\tstruct table_iter *ti, uint64_t off,\n-\t\t\t\tuint8_t typ)\n+static int table_iter_seek_to(struct table_iter *ti, struct reftable_reader *r,\n+\t\t\t uint64_t off, uint8_t typ)\n {\n \tint err;\n \n@@ -403,8 +402,8 @@ static int reader_table_iter_at(struct reftable_reader *r,\n \treturn 0;\n }\n \n-static int reader_start(struct reftable_reader *r, struct table_iter *ti,\n-\t\t\tuint8_t typ, int index)\n+static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader *r,\n+\t\t\t\t uint8_t typ, int index)\n {\n \tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n \tuint64_t off = offs->offset;\n@@ -416,11 +415,11 @@ static int reader_start(struct reftable_reader *r, struct table_iter *ti,\n \t\ttyp = BLOCK_TYPE_INDEX;\n \t}\n \n-\treturn reader_table_iter_at(r, ti, off, typ);\n+\treturn table_iter_seek_to(ti, r, off, typ);\n }\n \n-static int reader_seek_linear(struct table_iter *ti,\n-\t\t\t struct reftable_record *want)\n+static int table_iter_seek_linear(struct table_iter *ti,\n+\t\t\t\t struct reftable_record *want)\n {\n \tstruct strbuf want_key = STRBUF_INIT;\n \tstruct strbuf got_key = STRBUF_INIT;\n@@ -499,9 +498,8 @@ static int reader_seek_linear(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek_indexed(struct table_iter *ti,\n-\t\t\t struct reftable_reader *r,\n-\t\t\t struct reftable_record *rec)\n+static int table_iter_seek_indexed(struct table_iter *ti,\n+\t\t\t\t struct reftable_record *rec)\n {\n \tstruct reftable_record want_index = {\n \t\t.type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }\n@@ -520,7 +518,7 @@ static int reader_seek_indexed(struct table_iter *ti,\n \t * highest layer that identifies the relevant index block as well as\n \t * the record inside that block that corresponds to our wanted key.\n \t */\n-\terr = reader_seek_linear(ti, &want_index);\n+\terr = table_iter_seek_linear(ti, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -550,7 +548,7 @@ static int reader_seek_indexed(struct table_iter *ti,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = reader_table_iter_at(r, ti, index_result.u.idx.offset, 0);\n+\t\terr = table_iter_seek_to(ti, ti->r, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n@@ -585,14 +583,14 @@ static int reader_seek_internal(struct reftable_reader *r,\n \tstruct table_iter ti = TABLE_ITER_INIT, *p;\n \tint err;\n \n-\terr = reader_start(r, &ti, reftable_record_type(rec), !!idx);\n+\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec), !!idx);\n \tif (err < 0)\n \t\tgoto out;\n \n \tif (idx)\n-\t\terr = reader_seek_indexed(&ti, r, rec);\n+\t\terr = table_iter_seek_indexed(&ti, rec);\n \telse\n-\t\terr = reader_seek_linear(&ti, rec);\n+\t\terr = table_iter_seek_linear(&ti, rec);\n \tif (err)\n \t\tgoto out;\n \n@@ -742,7 +740,7 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,\n \tint err;\n \n \t*ti = ti_empty;\n-\terr = reader_start(r, ti, BLOCK_TYPE_REF, 0);\n+\terr = table_iter_seek_start(ti, r, BLOCK_TYPE_REF, 0);\n \tif (err < 0) {\n \t\treftable_free(ti);\n \t\treturn err;\n-- \n2.45.GIT\n\n"},{"id":"494594","messageId":"4d498ef3426877c703bababaa743dd5613ba5839.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 05/13] reftable/reader: inline `reader_seek_internal()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:21Z","receivedAt":"2024-05-13T08:47:26Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have both `reader_seek()` and `reader_seek_internal()`, where the\nformer function only exists so that we can exit early in case the given\ntable has no records of the sought-after type.\n\nMerge these two functions into one.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 34 ++++++++++++----------------------\n 1 file changed, 12 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex b210753441..c3541e2c43 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -573,21 +573,25 @@ static int table_iter_seek_indexed(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek_internal(struct reftable_reader *r,\n-\t\t\t\tstruct reftable_iterator *it,\n-\t\t\t\tstruct reftable_record *rec)\n+static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n+\t\t struct reftable_record *rec)\n {\n-\tstruct reftable_reader_offsets *offs =\n-\t\treader_offsets_for(r, reftable_record_type(rec));\n-\tuint64_t idx = offs->index_offset;\n+\tuint8_t typ = reftable_record_type(rec);\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n \tstruct table_iter ti = TABLE_ITER_INIT, *p;\n \tint err;\n \n-\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec), !!idx);\n+\tif (!offs->is_present) {\n+\t\titerator_set_empty(it);\n+\t\treturn 0;\n+\t}\n+\n+\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec),\n+\t\t\t\t !!offs->index_offset);\n \tif (err < 0)\n \t\tgoto out;\n \n-\tif (idx)\n+\tif (offs->index_offset)\n \t\terr = table_iter_seek_indexed(&ti, rec);\n \telse\n \t\terr = table_iter_seek_linear(&ti, rec);\n@@ -604,20 +608,6 @@ static int reader_seek_internal(struct reftable_reader *r,\n \treturn err;\n }\n \n-static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n-\t\t struct reftable_record *rec)\n-{\n-\tuint8_t typ = reftable_record_type(rec);\n-\n-\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n-\tif (!offs->is_present) {\n-\t\titerator_set_empty(it);\n-\t\treturn 0;\n-\t}\n-\n-\treturn reader_seek_internal(r, it, rec);\n-}\n-\n int reftable_reader_seek_ref(struct reftable_reader *r,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n-- \n2.45.GIT\n\n"},{"id":"494595","messageId":"5a10a115841512a46e4d3a3d3713e5532facdb39.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 06/13] reftable/reader: set up the reader when initializing table iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:26Z","receivedAt":"2024-05-13T08:47:31Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"All the seeking functions accept a `struct reftable_reader` as input\nsuch that they can use the reader to look up the respective blocks.\nRefactor the code to instead set up the reader as a member of `struct\ntable_iter` during initialization such that we don't have to pass the\nreader on every single call.\n\nThis step is required to move seeking of records into the generic\n`struct reftable_iterator` infrastructure.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 39 ++++++++++++++++++++++-----------------\n 1 file changed, 22 insertions(+), 17 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex c3541e2c43..021608f638 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -224,8 +224,14 @@ struct table_iter {\n \tstruct block_iter bi;\n \tint is_finished;\n };\n-#define TABLE_ITER_INIT { \\\n-\t.bi = BLOCK_ITER_INIT \\\n+\n+static int table_iter_init(struct table_iter *ti, struct reftable_reader *r)\n+{\n+\tstruct block_iter bi = BLOCK_ITER_INIT;\n+\tmemset(ti, 0, sizeof(*ti));\n+\tti->r = r;\n+\tti->bi = bi;\n+\treturn 0;\n }\n \n static int table_iter_next_in_block(struct table_iter *ti,\n@@ -386,26 +392,23 @@ static void iterator_from_table_iter(struct reftable_iterator *it,\n \tit->ops = &table_iter_vtable;\n }\n \n-static int table_iter_seek_to(struct table_iter *ti, struct reftable_reader *r,\n-\t\t\t uint64_t off, uint8_t typ)\n+static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)\n {\n \tint err;\n \n-\terr = reader_init_block_reader(r, &ti->br, off, typ);\n+\terr = reader_init_block_reader(ti->r, &ti->br, off, typ);\n \tif (err != 0)\n \t\treturn err;\n \n-\tti->r = r;\n \tti->typ = block_reader_type(&ti->br);\n \tti->block_off = off;\n \tblock_iter_seek_start(&ti->bi, &ti->br);\n \treturn 0;\n }\n \n-static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader *r,\n-\t\t\t\t uint8_t typ, int index)\n+static int table_iter_seek_start(struct table_iter *ti, uint8_t typ, int index)\n {\n-\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(ti->r, typ);\n \tuint64_t off = offs->offset;\n \tif (index) {\n \t\toff = offs->index_offset;\n@@ -415,7 +418,7 @@ static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader *\n \t\ttyp = BLOCK_TYPE_INDEX;\n \t}\n \n-\treturn table_iter_seek_to(ti, r, off, typ);\n+\treturn table_iter_seek_to(ti, off, typ);\n }\n \n static int table_iter_seek_linear(struct table_iter *ti,\n@@ -548,7 +551,7 @@ static int table_iter_seek_indexed(struct table_iter *ti,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = table_iter_seek_to(ti, ti->r, index_result.u.idx.offset, 0);\n+\t\terr = table_iter_seek_to(ti, index_result.u.idx.offset, 0);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n@@ -578,7 +581,7 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n {\n \tuint8_t typ = reftable_record_type(rec);\n \tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n-\tstruct table_iter ti = TABLE_ITER_INIT, *p;\n+\tstruct table_iter ti, *p;\n \tint err;\n \n \tif (!offs->is_present) {\n@@ -586,7 +589,9 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n \t\treturn 0;\n \t}\n \n-\terr = table_iter_seek_start(&ti, r, reftable_record_type(rec),\n+\ttable_iter_init(&ti, r);\n+\n+\terr = table_iter_seek_start(&ti, reftable_record_type(rec),\n \t\t\t\t !!offs->index_offset);\n \tif (err < 0)\n \t\tgoto out;\n@@ -722,15 +727,15 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,\n \t\t\t\t\t struct reftable_iterator *it,\n \t\t\t\t\t uint8_t *oid)\n {\n-\tstruct table_iter ti_empty = TABLE_ITER_INIT;\n-\tstruct table_iter *ti = reftable_calloc(1, sizeof(*ti));\n+\tstruct table_iter *ti;\n \tstruct filtering_ref_iterator *filter = NULL;\n \tstruct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;\n \tint oid_len = hash_size(r->hash_id);\n \tint err;\n \n-\t*ti = ti_empty;\n-\terr = table_iter_seek_start(ti, r, BLOCK_TYPE_REF, 0);\n+\tREFTABLE_ALLOC_ARRAY(ti, 1);\n+\ttable_iter_init(ti, r);\n+\terr = table_iter_seek_start(ti, BLOCK_TYPE_REF, 0);\n \tif (err < 0) {\n \t\treftable_free(ti);\n \t\treturn err;\n-- \n2.45.GIT\n\n"},{"id":"494596","messageId":"12c10fd366c30a9e615d0928c2874a6099e04e21.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 07/13] reftable/merged: split up initialization and seeking of records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:31Z","receivedAt":"2024-05-13T08:47:35Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"To initialize a `struct merged_iter`, we need to seek all subiterators\nto the wanted record and then add their results to the priority queue\nused to sort the records. This logic is split up across two functions,\n`merged_table_seek_record()` and `merged_iter_init()`. The scope of\nthese functions is somewhat weird though, where `merged_iter_init()` is\nonly responsible for adding the records of the subiterators to the\npriority queue.\n\nClarify the scope of those functions such that `merged_iter_init()` is\nonly responsible for initializing the iterator's structure. Performing\nthe subiterator seeks are now part of `merged_table_seek_record()`.\n\nThis step is required to move seeking of records into the generic\n`struct reftable_iterator` infrastructure.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 59 ++++++++++++++++++-----------------------------\n 1 file changed, 22 insertions(+), 37 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex f85a24c678..4e1b78e93f 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -25,34 +25,18 @@ struct merged_subiter {\n struct merged_iter {\n \tstruct merged_subiter *subiters;\n \tstruct merged_iter_pqueue pq;\n-\tuint32_t hash_id;\n \tsize_t stack_len;\n-\tuint8_t typ;\n \tint suppress_deletions;\n \tssize_t advance_index;\n };\n \n-static int merged_iter_init(struct merged_iter *mi)\n+static void merged_iter_init(struct merged_iter *mi,\n+\t\t\t struct reftable_merged_table *mt)\n {\n-\tfor (size_t i = 0; i < mi->stack_len; i++) {\n-\t\tstruct pq_entry e = {\n-\t\t\t.index = i,\n-\t\t\t.rec = &mi->subiters[i].rec,\n-\t\t};\n-\t\tint err;\n-\n-\t\treftable_record_init(&mi->subiters[i].rec, mi->typ);\n-\t\terr = iterator_next(&mi->subiters[i].iter,\n-\t\t\t\t &mi->subiters[i].rec);\n-\t\tif (err < 0)\n-\t\t\treturn err;\n-\t\tif (err > 0)\n-\t\t\tcontinue;\n-\n-\t\tmerged_iter_pqueue_add(&mi->pq, &e);\n-\t}\n-\n-\treturn 0;\n+\tmemset(mi, 0, sizeof(*mi));\n+\tmi->advance_index = -1;\n+\tmi->suppress_deletions = mt->suppress_deletions;\n+\tREFTABLE_CALLOC_ARRAY(mi->subiters, mt->stack_len);\n }\n \n static void merged_iter_close(void *p)\n@@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \t\t\t\t struct reftable_iterator *it,\n \t\t\t\t struct reftable_record *rec)\n {\n-\tstruct merged_iter merged = {\n-\t\t.typ = reftable_record_type(rec),\n-\t\t.hash_id = mt->hash_id,\n-\t\t.suppress_deletions = mt->suppress_deletions,\n-\t\t.advance_index = -1,\n-\t};\n-\tstruct merged_iter *p;\n+\tstruct merged_iter merged, *p;\n \tint err;\n \n-\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n+\tmerged_iter_init(&merged, mt);\n+\n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n+\t\treftable_record_init(&merged.subiters[merged.stack_len].rec,\n+\t\t\t\t reftable_record_type(rec));\n+\n \t\terr = reftable_table_seek_record(&mt->stack[i],\n \t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n-\t\tif (!err)\n-\t\t\tmerged.stack_len++;\n-\t}\n+\t\tif (err > 0)\n+\t\t\tcontinue;\n \n-\terr = merged_iter_init(&merged);\n-\tif (err < 0)\n-\t\tgoto out;\n+\t\terr = merged_iter_advance_subiter(&merged, merged.stack_len);\n+\t\tif (err < 0)\n+\t\t\tgoto out;\n+\n+\t\tmerged.stack_len++;\n+\t}\n \n-\tp = reftable_malloc(sizeof(struct merged_iter));\n+\tp = reftable_malloc(sizeof(*p));\n \t*p = merged;\n \titerator_from_merged_iter(it, p);\n+\terr = 0;\n \n out:\n \tif (err < 0)\n-- \n2.45.GIT\n\n"},{"id":"494597","messageId":"31bdfc1e34079dd79ba3bfd39a03eacaa2929762.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 08/13] reftable/merged: simplify indices for subiterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:36Z","receivedAt":"2024-05-13T08:47:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking on a merged table, we perform the seek for each of the\nsubiterators. If the subiterator has the desired record we add it to the\npriority queue, otherwise we skip it and don't add it to the stack of\nsubiterators hosted by the merged table.\n\nThe consequence of this is that the index of the subiterator in the\nmerged table does not necessarily correspond to the index of it in the\nmerged iterator. Next to being potentially confusing, it also means that\nwe won't easily be able to re-seek the merged iterator because we have\nno clear connection between both of the data structures.\n\nRefactor the code so that the index stays the same in both structures.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 4e1b78e93f..18a2a6f09b 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -37,6 +37,7 @@ static void merged_iter_init(struct merged_iter *mi,\n \tmi->advance_index = -1;\n \tmi->suppress_deletions = mt->suppress_deletions;\n \tREFTABLE_CALLOC_ARRAY(mi->subiters, mt->stack_len);\n+\tmi->stack_len = mt->stack_len;\n }\n \n static void merged_iter_close(void *p)\n@@ -236,21 +237,19 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \tmerged_iter_init(&merged, mt);\n \n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n-\t\treftable_record_init(&merged.subiters[merged.stack_len].rec,\n+\t\treftable_record_init(&merged.subiters[i].rec,\n \t\t\t\t reftable_record_type(rec));\n \n \t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n+\t\t\t\t\t\t &merged.subiters[i].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n \t\tif (err > 0)\n \t\t\tcontinue;\n \n-\t\terr = merged_iter_advance_subiter(&merged, merged.stack_len);\n+\t\terr = merged_iter_advance_subiter(&merged, i);\n \t\tif (err < 0)\n \t\t\tgoto out;\n-\n-\t\tmerged.stack_len++;\n \t}\n \n \tp = reftable_malloc(sizeof(*p));\n-- \n2.45.GIT\n\n"},{"id":"494598","messageId":"3e91c3830e42063a74dac983152b7b8f0053bafa.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 09/13] reftable/generic: move seeking of records into the iterator","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:41Z","receivedAt":"2024-05-13T08:47:45Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Reftable iterators are created by seeking on the parent structure of a\ncorresponding record. For example, to create an iterator for the merged\ntable you would call `reftable_merged_table_seek_ref()`. Most notably,\nit is not posible to create an iterator and then seek it afterwards.\n\nWhile this may be a bit easier to reason about, it comes with two\nsignificant downsides. The first downside is that the logic to find\nrecords is split up between the parent data structure and the iterator\nitself. Conceptually, it is more straight forward if all that logic was\ncontained in a single place, which should be the iterator.\n\nThe second and more significant downside is that it is impossible to\nreuse iterators for multiple seeks. Whenever you want to look up a\nrecord, you need to re-create the whole infrastructure again, which is\nquite a waste of time. Furthermore, it is impossible to optimize seeks,\nsuch as when seeking the same record multiple times.\n\nTo address this, we essentially split up the concerns properly such that\nthe parent data structure is responsible for setting up the iterator via\na new `init_iter()` callback, whereas the iterator handles seeks via a\nnew `seek()` callback. This will eventually allow us to call `seek()` on\nthe iterator multiple times, where every iterator can potentially\noptimize for certain cases.\n\nNote that at this point in time we are not yet ready to reuse the\niterators. This will be left for a future patch series.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/generic.c | 47 +++++++++++++----\n reftable/generic.h | 9 +++-\n reftable/iter.c | 15 ++++++\n reftable/merged.c | 97 +++++++++++++++++-----------------\n reftable/reader.c | 126 +++++++++++++++++++++++++--------------------\n 5 files changed, 177 insertions(+), 117 deletions(-)\n\ndiff --git a/reftable/generic.c b/reftable/generic.c\nindex b9f1c7c18a..1cf68fe124 100644\n--- a/reftable/generic.c\n+++ b/reftable/generic.c\n@@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at\n #include \"reftable-iterator.h\"\n #include \"reftable-generic.h\"\n \n+void table_init_iter(struct reftable_table *tab,\n+\t\t struct reftable_iterator *it,\n+\t\t uint8_t typ)\n+{\n+\n+\ttab->ops->init_iter(tab->table_arg, it, typ);\n+}\n+\n int reftable_table_seek_ref(struct reftable_table *tab,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_REF,\n-\t\t\t\t .u.ref = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t } };\n-\treturn tab->ops->seek_record(tab->table_arg, it, &rec);\n+\tstruct reftable_record want = {\n+\t\t.type = BLOCK_TYPE_REF,\n+\t\t.u.ref = {\n+\t\t\t.refname = (char *)name,\n+\t\t},\n+\t};\n+\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n+\treturn it->ops->seek(it->iter_arg, &want);\n }\n \n int reftable_table_seek_log(struct reftable_table *tab,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n-\t\t\t\t .u.log = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t\t .update_index = ~((uint64_t)0),\n-\t\t\t\t } };\n-\treturn tab->ops->seek_record(tab->table_arg, it, &rec);\n+\tstruct reftable_record want = {\n+\t\t.type = BLOCK_TYPE_LOG,\n+\t\t.u.log = {\n+\t\t\t.refname = (char *)name,\n+\t\t\t.update_index = ~((uint64_t)0),\n+\t\t},\n+\t};\n+\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n+\treturn it->ops->seek(it->iter_arg, &want);\n }\n \n int reftable_table_read_ref(struct reftable_table *tab, const char *name,\n@@ -152,11 +166,21 @@ int reftable_iterator_next_log(struct reftable_iterator *it,\n \treturn err;\n }\n \n+int iterator_seek(struct reftable_iterator *it, struct reftable_record *want)\n+{\n+\treturn it->ops->seek(it->iter_arg, want);\n+}\n+\n int iterator_next(struct reftable_iterator *it, struct reftable_record *rec)\n {\n \treturn it->ops->next(it->iter_arg, rec);\n }\n \n+static int empty_iterator_seek(void *arg, struct reftable_record *want)\n+{\n+\treturn 0;\n+}\n+\n static int empty_iterator_next(void *arg, struct reftable_record *rec)\n {\n \treturn 1;\n@@ -167,6 +191,7 @@ static void empty_iterator_close(void *arg)\n }\n \n static struct reftable_iterator_vtable empty_vtable = {\n+\t.seek = &empty_iterator_seek,\n \t.next = &empty_iterator_next,\n \t.close = &empty_iterator_close,\n };\ndiff --git a/reftable/generic.h b/reftable/generic.h\nindex 98886a0640..8341fa570e 100644\n--- a/reftable/generic.h\n+++ b/reftable/generic.h\n@@ -14,19 +14,24 @@ license that can be found in the LICENSE file or at\n \n /* generic interface to reftables */\n struct reftable_table_vtable {\n-\tint (*seek_record)(void *tab, struct reftable_iterator *it,\n-\t\t\t struct reftable_record *);\n+\tvoid (*init_iter)(void *tab, struct reftable_iterator *it, uint8_t typ);\n \tuint32_t (*hash_id)(void *tab);\n \tuint64_t (*min_update_index)(void *tab);\n \tuint64_t (*max_update_index)(void *tab);\n };\n \n+void table_init_iter(struct reftable_table *tab,\n+\t\t struct reftable_iterator *it,\n+\t\t uint8_t typ);\n+\n struct reftable_iterator_vtable {\n+\tint (*seek)(void *iter_arg, struct reftable_record *want);\n \tint (*next)(void *iter_arg, struct reftable_record *rec);\n \tvoid (*close)(void *iter_arg);\n };\n \n void iterator_set_empty(struct reftable_iterator *it);\n+int iterator_seek(struct reftable_iterator *it, struct reftable_record *want);\n int iterator_next(struct reftable_iterator *it, struct reftable_record *rec);\n \n #endif\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex aa9ac199b1..b4528fab47 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)\n \treftable_iterator_destroy(&fri->it);\n }\n \n+static int filtering_ref_iterator_seek(void *iter_arg,\n+\t\t\t\t struct reftable_record *want)\n+{\n+\tstruct filtering_ref_iterator *fri = iter_arg;\n+\treturn iterator_seek(&fri->it, want);\n+}\n+\n static int filtering_ref_iterator_next(void *iter_arg,\n \t\t\t\t struct reftable_record *rec)\n {\n@@ -73,6 +80,7 @@ static int filtering_ref_iterator_next(void *iter_arg,\n }\n \n static struct reftable_iterator_vtable filtering_ref_iterator_vtable = {\n+\t.seek = &filtering_ref_iterator_seek,\n \t.next = &filtering_ref_iterator_next,\n \t.close = &filtering_ref_iterator_close,\n };\n@@ -119,6 +127,12 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)\n \treturn 0;\n }\n \n+static int indexed_table_ref_iter_seek(void *p, struct reftable_record *want)\n+{\n+\tBUG(\"seeking indexed table is not supported\");\n+\treturn -1;\n+}\n+\n static int indexed_table_ref_iter_next(void *p, struct reftable_record *rec)\n {\n \tstruct indexed_table_ref_iter *it = p;\n@@ -175,6 +189,7 @@ int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest,\n }\n \n static struct reftable_iterator_vtable indexed_table_ref_iter_vtable = {\n+\t.seek = &indexed_table_ref_iter_seek,\n \t.next = &indexed_table_ref_iter_next,\n \t.close = &indexed_table_ref_iter_close,\n };\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 18a2a6f09b..fc7946d90d 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -31,12 +31,18 @@ struct merged_iter {\n };\n \n static void merged_iter_init(struct merged_iter *mi,\n-\t\t\t struct reftable_merged_table *mt)\n+\t\t\t struct reftable_merged_table *mt,\n+\t\t\t uint8_t typ)\n {\n \tmemset(mi, 0, sizeof(*mi));\n \tmi->advance_index = -1;\n \tmi->suppress_deletions = mt->suppress_deletions;\n+\n \tREFTABLE_CALLOC_ARRAY(mi->subiters, mt->stack_len);\n+\tfor (size_t i = 0; i < mt->stack_len; i++) {\n+\t\treftable_record_init(&mi->subiters[i].rec, typ);\n+\t\ttable_init_iter(&mt->stack[i], &mi->subiters[i].iter, typ);\n+\t}\n \tmi->stack_len = mt->stack_len;\n }\n \n@@ -68,6 +74,27 @@ static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n \treturn 0;\n }\n \n+static int merged_iter_seek(struct merged_iter *mi, struct reftable_record *want)\n+{\n+\tint err;\n+\n+\tmi->advance_index = -1;\n+\n+\tfor (size_t i = 0; i < mi->stack_len; i++) {\n+\t\terr = iterator_seek(&mi->subiters[i].iter, want);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t\tif (err > 0)\n+\t\t\tcontinue;\n+\n+\t\terr = merged_iter_advance_subiter(mi, i);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t struct reftable_record *rec)\n {\n@@ -133,6 +160,11 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \treturn 0;\n }\n \n+static int merged_iter_seek_void(void *it, struct reftable_record *want)\n+{\n+\treturn merged_iter_seek(it, want);\n+}\n+\n static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n \tstruct merged_iter *mi = p;\n@@ -147,6 +179,7 @@ static int merged_iter_next_void(void *p, struct reftable_record *rec)\n }\n \n static struct reftable_iterator_vtable merged_iter_vtable = {\n+\t.seek = merged_iter_seek_void,\n \t.next = &merged_iter_next_void,\n \t.close = &merged_iter_close,\n };\n@@ -220,47 +253,13 @@ reftable_merged_table_min_update_index(struct reftable_merged_table *mt)\n \treturn mt->min;\n }\n \n-static int reftable_table_seek_record(struct reftable_table *tab,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t struct reftable_record *rec)\n-{\n-\treturn tab->ops->seek_record(tab->table_arg, it, rec);\n-}\n-\n-static int merged_table_seek_record(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t struct reftable_record *rec)\n+static void merged_table_init_iter(struct reftable_merged_table *mt,\n+\t\t\t\t struct reftable_iterator *it,\n+\t\t\t\t uint8_t typ)\n {\n-\tstruct merged_iter merged, *p;\n-\tint err;\n-\n-\tmerged_iter_init(&merged, mt);\n-\n-\tfor (size_t i = 0; i < mt->stack_len; i++) {\n-\t\treftable_record_init(&merged.subiters[i].rec,\n-\t\t\t\t reftable_record_type(rec));\n-\n-\t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.subiters[i].iter, rec);\n-\t\tif (err < 0)\n-\t\t\tgoto out;\n-\t\tif (err > 0)\n-\t\t\tcontinue;\n-\n-\t\terr = merged_iter_advance_subiter(&merged, i);\n-\t\tif (err < 0)\n-\t\t\tgoto out;\n-\t}\n-\n-\tp = reftable_malloc(sizeof(*p));\n-\t*p = merged;\n-\titerator_from_merged_iter(it, p);\n-\terr = 0;\n-\n-out:\n-\tif (err < 0)\n-\t\tmerged_iter_close(&merged);\n-\treturn err;\n+\tstruct merged_iter *mi = reftable_malloc(sizeof(*mi));\n+\tmerged_iter_init(mi, mt, typ);\n+\titerator_from_merged_iter(it, mi);\n }\n \n int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n@@ -273,7 +272,8 @@ int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n \t\t\t.refname = (char *)name,\n \t\t},\n \t};\n-\treturn merged_table_seek_record(mt, it, &rec);\n+\tmerged_table_init_iter(mt, it, BLOCK_TYPE_REF);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n@@ -285,7 +285,8 @@ int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n \t\t\t\t\t .refname = (char *)name,\n \t\t\t\t\t .update_index = update_index,\n \t\t\t\t } };\n-\treturn merged_table_seek_record(mt, it, &rec);\n+\tmerged_table_init_iter(mt, it, BLOCK_TYPE_LOG);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_merged_table_seek_log(struct reftable_merged_table *mt,\n@@ -301,11 +302,11 @@ uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *mt)\n \treturn mt->hash_id;\n }\n \n-static int reftable_merged_table_seek_void(void *tab,\n-\t\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t\t struct reftable_record *rec)\n+static void reftable_merged_table_init_iter_void(void *tab,\n+\t\t\t\t\t\t struct reftable_iterator *it,\n+\t\t\t\t\t\t uint8_t typ)\n {\n-\treturn merged_table_seek_record(tab, it, rec);\n+\tmerged_table_init_iter(tab, it, typ);\n }\n \n static uint32_t reftable_merged_table_hash_id_void(void *tab)\n@@ -324,7 +325,7 @@ static uint64_t reftable_merged_table_max_update_index_void(void *tab)\n }\n \n static struct reftable_table_vtable merged_table_vtable = {\n-\t.seek_record = reftable_merged_table_seek_void,\n+\t.init_iter = reftable_merged_table_init_iter_void,\n \t.hash_id = reftable_merged_table_hash_id_void,\n \t.min_update_index = reftable_merged_table_min_update_index_void,\n \t.max_update_index = reftable_merged_table_max_update_index_void,\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 021608f638..a5a13cb0b9 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -369,29 +369,6 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t}\n }\n \n-static int table_iter_next_void(void *ti, struct reftable_record *rec)\n-{\n-\treturn table_iter_next(ti, rec);\n-}\n-\n-static void table_iter_close_void(void *ti)\n-{\n-\ttable_iter_close(ti);\n-}\n-\n-static struct reftable_iterator_vtable table_iter_vtable = {\n-\t.next = &table_iter_next_void,\n-\t.close = &table_iter_close_void,\n-};\n-\n-static void iterator_from_table_iter(struct reftable_iterator *it,\n-\t\t\t\t struct table_iter *ti)\n-{\n-\tassert(!it->ops);\n-\tit->iter_arg = ti;\n-\tit->ops = &table_iter_vtable;\n-}\n-\n static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)\n {\n \tint err;\n@@ -576,43 +553,74 @@ static int table_iter_seek_indexed(struct table_iter *ti,\n \treturn err;\n }\n \n-static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n-\t\t struct reftable_record *rec)\n+static int table_iter_seek(struct table_iter *ti,\n+\t\t\t struct reftable_record *want)\n {\n-\tuint8_t typ = reftable_record_type(rec);\n-\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n-\tstruct table_iter ti, *p;\n+\tuint8_t typ = reftable_record_type(want);\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(ti->r, typ);\n \tint err;\n \n-\tif (!offs->is_present) {\n-\t\titerator_set_empty(it);\n-\t\treturn 0;\n-\t}\n-\n-\ttable_iter_init(&ti, r);\n-\n-\terr = table_iter_seek_start(&ti, reftable_record_type(rec),\n+\terr = table_iter_seek_start(ti, reftable_record_type(want),\n \t\t\t\t !!offs->index_offset);\n \tif (err < 0)\n \t\tgoto out;\n \n \tif (offs->index_offset)\n-\t\terr = table_iter_seek_indexed(&ti, rec);\n+\t\terr = table_iter_seek_indexed(ti, want);\n \telse\n-\t\terr = table_iter_seek_linear(&ti, rec);\n+\t\terr = table_iter_seek_linear(ti, want);\n \tif (err)\n \t\tgoto out;\n \n-\tREFTABLE_ALLOC_ARRAY(p, 1);\n-\t*p = ti;\n-\titerator_from_table_iter(it, p);\n-\n out:\n-\tif (err)\n-\t\ttable_iter_close(&ti);\n \treturn err;\n }\n \n+static int table_iter_seek_void(void *ti, struct reftable_record *want)\n+{\n+\treturn table_iter_seek(ti, want);\n+}\n+\n+static int table_iter_next_void(void *ti, struct reftable_record *rec)\n+{\n+\treturn table_iter_next(ti, rec);\n+}\n+\n+static void table_iter_close_void(void *ti)\n+{\n+\ttable_iter_close(ti);\n+}\n+\n+static struct reftable_iterator_vtable table_iter_vtable = {\n+\t.seek = &table_iter_seek_void,\n+\t.next = &table_iter_next_void,\n+\t.close = &table_iter_close_void,\n+};\n+\n+static void iterator_from_table_iter(struct reftable_iterator *it,\n+\t\t\t\t struct table_iter *ti)\n+{\n+\tassert(!it->ops);\n+\tit->iter_arg = ti;\n+\tit->ops = &table_iter_vtable;\n+}\n+\n+static void reader_init_iter(struct reftable_reader *r,\n+\t\t\t struct reftable_iterator *it,\n+\t\t\t uint8_t typ)\n+{\n+\tstruct reftable_reader_offsets *offs = reader_offsets_for(r, typ);\n+\n+\tif (offs->is_present) {\n+\t\tstruct table_iter *ti;\n+\t\tREFTABLE_ALLOC_ARRAY(ti, 1);\n+\t\ttable_iter_init(ti, r);\n+\t\titerator_from_table_iter(it, ti);\n+\t} else {\n+\t\titerator_set_empty(it);\n+\t}\n+}\n+\n int reftable_reader_seek_ref(struct reftable_reader *r,\n \t\t\t struct reftable_iterator *it, const char *name)\n {\n@@ -622,19 +630,23 @@ int reftable_reader_seek_ref(struct reftable_reader *r,\n \t\t\t.refname = (char *)name,\n \t\t},\n \t};\n-\treturn reader_seek(r, it, &rec);\n+\treader_init_iter(r, it, BLOCK_TYPE_REF);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_reader_seek_log_at(struct reftable_reader *r,\n \t\t\t\tstruct reftable_iterator *it, const char *name,\n \t\t\t\tuint64_t update_index)\n {\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n-\t\t\t\t .u.log = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t\t .update_index = update_index,\n-\t\t\t\t } };\n-\treturn reader_seek(r, it, &rec);\n+\tstruct reftable_record rec = {\n+\t\t.type = BLOCK_TYPE_LOG,\n+\t\t.u.log = {\n+\t\t\t.refname = (char *)name,\n+\t\t\t.update_index = update_index,\n+\t\t},\n+\t};\n+\treader_init_iter(r, it, BLOCK_TYPE_LOG);\n+\treturn iterator_seek(it, &rec);\n }\n \n int reftable_reader_seek_log(struct reftable_reader *r,\n@@ -692,7 +704,8 @@ static int reftable_reader_refs_for_indexed(struct reftable_reader *r,\n \tstruct indexed_table_ref_iter *itr = NULL;\n \n \t/* Look through the reverse index. */\n-\terr = reader_seek(r, &oit, &want);\n+\treader_init_iter(r, &oit, BLOCK_TYPE_OBJ);\n+\terr = iterator_seek(&oit, &want);\n \tif (err != 0)\n \t\tgoto done;\n \n@@ -773,10 +786,11 @@ uint64_t reftable_reader_min_update_index(struct reftable_reader *r)\n \n /* generic table interface. */\n \n-static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,\n-\t\t\t\t struct reftable_record *rec)\n+static void reftable_reader_init_iter_void(void *tab,\n+\t\t\t\t\t struct reftable_iterator *it,\n+\t\t\t\t\t uint8_t typ)\n {\n-\treturn reader_seek(tab, it, rec);\n+\treader_init_iter(tab, it, typ);\n }\n \n static uint32_t reftable_reader_hash_id_void(void *tab)\n@@ -795,7 +809,7 @@ static uint64_t reftable_reader_max_update_index_void(void *tab)\n }\n \n static struct reftable_table_vtable reader_vtable = {\n-\t.seek_record = reftable_reader_seek_void,\n+\t.init_iter = reftable_reader_init_iter_void,\n \t.hash_id = reftable_reader_hash_id_void,\n \t.min_update_index = reftable_reader_min_update_index_void,\n \t.max_update_index = reftable_reader_max_update_index_void,\n-- \n2.45.GIT\n\n"},{"id":"494599","messageId":"b0641dd80073648b297bcd18b9945afd1afa8ba0.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 10/13] reftable/generic: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:47Z","receivedAt":"2024-05-13T08:47:51Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Refactor the interfaces exposed by `struct reftable_table` and `struct\nreftable_iterator` such that they support iterator reuse. This is done\nby separating initialization of the iterator and seeking on it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/generic.c | 53 ++++++++++++++++++++++++++----------\n reftable/iter.c | 8 +++---\n reftable/reftable-generic.h | 8 +++---\n reftable/reftable-iterator.h | 21 ++++++++++++++\n 4 files changed, 68 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/generic.c b/reftable/generic.c\nindex 1cf68fe124..28ae26145e 100644\n--- a/reftable/generic.c\n+++ b/reftable/generic.c\n@@ -20,8 +20,20 @@ void table_init_iter(struct reftable_table *tab,\n \ttab->ops->init_iter(tab->table_arg, it, typ);\n }\n \n-int reftable_table_seek_ref(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name)\n+void reftable_table_init_ref_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n+}\n+\n+void reftable_table_init_log_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n+}\n+\n+int reftable_iterator_seek_ref(struct reftable_iterator *it,\n+\t\t\t const char *name)\n {\n \tstruct reftable_record want = {\n \t\t.type = BLOCK_TYPE_REF,\n@@ -29,29 +41,37 @@ int reftable_table_seek_ref(struct reftable_table *tab,\n \t\t\t.refname = (char *)name,\n \t\t},\n \t};\n-\ttable_init_iter(tab, it, BLOCK_TYPE_REF);\n \treturn it->ops->seek(it->iter_arg, &want);\n }\n \n-int reftable_table_seek_log(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name)\n+int reftable_iterator_seek_log_at(struct reftable_iterator *it,\n+\t\t\t\t const char *name, uint64_t update_index)\n {\n \tstruct reftable_record want = {\n \t\t.type = BLOCK_TYPE_LOG,\n \t\t.u.log = {\n \t\t\t.refname = (char *)name,\n-\t\t\t.update_index = ~((uint64_t)0),\n+\t\t\t.update_index = update_index,\n \t\t},\n \t};\n-\ttable_init_iter(tab, it, BLOCK_TYPE_LOG);\n \treturn it->ops->seek(it->iter_arg, &want);\n }\n \n+int reftable_iterator_seek_log(struct reftable_iterator *it,\n+\t\t\t const char *name)\n+{\n+\treturn reftable_iterator_seek_log_at(it, name, ~((uint64_t) 0));\n+}\n+\n int reftable_table_read_ref(struct reftable_table *tab, const char *name,\n \t\t\t struct reftable_ref_record *ref)\n {\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_table_seek_ref(tab, &it, name);\n+\tint err;\n+\n+\treftable_table_init_ref_iter(tab, &it);\n+\n+\terr = reftable_iterator_seek_ref(&it, name);\n \tif (err)\n \t\tgoto done;\n \n@@ -76,10 +96,13 @@ int reftable_table_print(struct reftable_table *tab) {\n \tstruct reftable_ref_record ref = { NULL };\n \tstruct reftable_log_record log = { NULL };\n \tuint32_t hash_id = reftable_table_hash_id(tab);\n-\tint err = reftable_table_seek_ref(tab, &it, \"\");\n-\tif (err < 0) {\n+\tint err;\n+\n+\treftable_table_init_ref_iter(tab, &it);\n+\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n+\tif (err < 0)\n \t\treturn err;\n-\t}\n \n \twhile (1) {\n \t\terr = reftable_iterator_next_ref(&it, &ref);\n@@ -94,10 +117,12 @@ int reftable_table_print(struct reftable_table *tab) {\n \treftable_iterator_destroy(&it);\n \treftable_ref_record_release(&ref);\n \n-\terr = reftable_table_seek_log(tab, &it, \"\");\n-\tif (err < 0) {\n+\treftable_table_init_log_iter(tab, &it);\n+\n+\terr = reftable_iterator_seek_log(&it, \"\");\n+\tif (err < 0)\n \t\treturn err;\n-\t}\n+\n \twhile (1) {\n \t\terr = reftable_iterator_next_log(&it, &log);\n \t\tif (err > 0) {\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex b4528fab47..fddea31e51 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -45,11 +45,11 @@ static int filtering_ref_iterator_next(void *iter_arg,\n \t\tif (fri->double_check) {\n \t\t\tstruct reftable_iterator it = { NULL };\n \n-\t\t\terr = reftable_table_seek_ref(&fri->tab, &it,\n-\t\t\t\t\t\t ref->refname);\n-\t\t\tif (err == 0) {\n+\t\t\treftable_table_init_ref_iter(&fri->tab, &it);\n+\n+\t\t\terr = reftable_iterator_seek_ref(&it, ref->refname);\n+\t\t\tif (err == 0)\n \t\t\t\terr = reftable_iterator_next_ref(&it, ref);\n-\t\t\t}\n \n \t\t\treftable_iterator_destroy(&it);\n \ndiff --git a/reftable/reftable-generic.h b/reftable/reftable-generic.h\nindex d239751a77..65670ea093 100644\n--- a/reftable/reftable-generic.h\n+++ b/reftable/reftable-generic.h\n@@ -21,11 +21,11 @@ struct reftable_table {\n \tvoid *table_arg;\n };\n \n-int reftable_table_seek_log(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name);\n+void reftable_table_init_ref_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it);\n \n-int reftable_table_seek_ref(struct reftable_table *tab,\n-\t\t\t struct reftable_iterator *it, const char *name);\n+void reftable_table_init_log_iter(struct reftable_table *tab,\n+\t\t\t\t struct reftable_iterator *it);\n \n /* returns the hash ID from a generic reftable_table */\n uint32_t reftable_table_hash_id(struct reftable_table *tab);\ndiff --git a/reftable/reftable-iterator.h b/reftable/reftable-iterator.h\nindex d3eee7af35..e3bf688d53 100644\n--- a/reftable/reftable-iterator.h\n+++ b/reftable/reftable-iterator.h\n@@ -21,12 +21,33 @@ struct reftable_iterator {\n \tvoid *iter_arg;\n };\n \n+/*\n+ * Position the iterator at the ref record with given name such that the next\n+ * call to `next_ref()` would yield the record.\n+ */\n+int reftable_iterator_seek_ref(struct reftable_iterator *it,\n+\t\t\t const char *name);\n+\n /* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0:\n * end of iteration.\n */\n int reftable_iterator_next_ref(struct reftable_iterator *it,\n \t\t\t struct reftable_ref_record *ref);\n \n+/*\n+ * Position the iterator at the log record with given name and update index\n+ * such that the next call to `next_log()` would yield the record.\n+ */\n+int reftable_iterator_seek_log_at(struct reftable_iterator *it,\n+\t\t\t\t const char *name, uint64_t update_index);\n+\n+/*\n+ * Position the iterator at the newest log record with given name such that the\n+ * next call to `next_log()` would yield the record.\n+ */\n+int reftable_iterator_seek_log(struct reftable_iterator *it,\n+\t\t\t const char *name);\n+\n /* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0:\n * end of iteration.\n */\n-- \n2.45.GIT\n\n"},{"id":"494600","messageId":"07459516508c6982ad185c5f9409be523878bc50.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 11/13] reftable/reader: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:52Z","receivedAt":"2024-05-13T08:47:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Refactor the interfaces exposed by `struct reftable_reader` and `struct\ntable_iterator` such that they support iterator reuse. This is done by\nseparating initialization of the iterator and seeking on it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/reader.c | 31 ++++----------------------\n reftable/readwrite_test.c | 35 +++++++++++++++++++----------\n reftable/reftable-reader.h | 45 ++++++--------------------------------\n 3 files changed, 35 insertions(+), 76 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex a5a13cb0b9..bbdb4bdafa 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -621,39 +621,16 @@ static void reader_init_iter(struct reftable_reader *r,\n \t}\n }\n \n-int reftable_reader_seek_ref(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name)\n+void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it)\n {\n-\tstruct reftable_record rec = {\n-\t\t.type = BLOCK_TYPE_REF,\n-\t\t.u.ref = {\n-\t\t\t.refname = (char *)name,\n-\t\t},\n-\t};\n \treader_init_iter(r, it, BLOCK_TYPE_REF);\n-\treturn iterator_seek(it, &rec);\n }\n \n-int reftable_reader_seek_log_at(struct reftable_reader *r,\n-\t\t\t\tstruct reftable_iterator *it, const char *name,\n-\t\t\t\tuint64_t update_index)\n+void reftable_reader_init_log_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it)\n {\n-\tstruct reftable_record rec = {\n-\t\t.type = BLOCK_TYPE_LOG,\n-\t\t.u.log = {\n-\t\t\t.refname = (char *)name,\n-\t\t\t.update_index = update_index,\n-\t\t},\n-\t};\n \treader_init_iter(r, it, BLOCK_TYPE_LOG);\n-\treturn iterator_seek(it, &rec);\n-}\n-\n-int reftable_reader_seek_log(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name)\n-{\n-\tuint64_t max = ~((uint64_t)0);\n-\treturn reftable_reader_seek_log_at(r, it, name, max);\n }\n \n void reader_close(struct reftable_reader *r)\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex a6dbd214c5..d99543bbd6 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -239,7 +239,9 @@ static void test_log_write_read(void)\n \terr = init_reader(&rd, &source, \"file.log\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(&rd, &it, names[N - 1]);\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\n+\terr = reftable_iterator_seek_ref(&it, names[N - 1]);\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_ref(&it, &ref);\n@@ -252,7 +254,9 @@ static void test_log_write_read(void)\n \treftable_iterator_destroy(&it);\n \treftable_ref_record_release(&ref);\n \n-\terr = reftable_reader_seek_log(&rd, &it, \"\");\n+\treftable_reader_init_log_iterator(&rd, &it);\n+\n+\terr = reftable_iterator_seek_log(&it, \"\");\n \tEXPECT_ERR(err);\n \n \ti = 0;\n@@ -330,7 +334,8 @@ static void test_log_zlib_corruption(void)\n \terr = init_reader(&rd, &source, \"file.log\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_log(&rd, &it, \"refname\");\n+\treftable_reader_init_log_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_log(&it, \"refname\");\n \tEXPECT(err == REFTABLE_ZLIB_ERROR);\n \n \treftable_iterator_destroy(&it);\n@@ -358,7 +363,8 @@ static void test_table_read_write_sequential(void)\n \terr = init_reader(&rd, &source, \"file.ref\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(&rd, &it, \"\");\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tEXPECT_ERR(err);\n \n \twhile (1) {\n@@ -412,7 +418,8 @@ static void test_table_read_api(void)\n \terr = init_reader(&rd, &source, \"file.ref\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(&rd, &it, names[0]);\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, names[0]);\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_log(&it, &log);\n@@ -457,7 +464,8 @@ static void test_table_read_write_seek(int index, int hash_id)\n \t}\n \n \tfor (i = 1; i < N; i++) {\n-\t\tint err = reftable_reader_seek_ref(&rd, &it, names[i]);\n+\t\treftable_reader_init_ref_iterator(&rd, &it);\n+\t\terr = reftable_iterator_seek_ref(&it, names[i]);\n \t\tEXPECT_ERR(err);\n \t\terr = reftable_iterator_next_ref(&it, &ref);\n \t\tEXPECT_ERR(err);\n@@ -472,7 +480,8 @@ static void test_table_read_write_seek(int index, int hash_id)\n \tstrbuf_addstr(&pastLast, names[N - 1]);\n \tstrbuf_addstr(&pastLast, \"/\");\n \n-\terr = reftable_reader_seek_ref(&rd, &it, pastLast.buf);\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, pastLast.buf);\n \tif (err == 0) {\n \t\tstruct reftable_ref_record ref = { NULL };\n \t\tint err = reftable_iterator_next_ref(&it, &ref);\n@@ -576,7 +585,8 @@ static void test_table_refs_for(int indexed)\n \t\trd.obj_offsets.is_present = 0;\n \t}\n \n-\terr = reftable_reader_seek_ref(&rd, &it, \"\");\n+\treftable_reader_init_ref_iterator(&rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tEXPECT_ERR(err);\n \treftable_iterator_destroy(&it);\n \n@@ -639,7 +649,8 @@ static void test_write_empty_table(void)\n \terr = reftable_new_reader(&rd, &source, \"filename\");\n \tEXPECT_ERR(err);\n \n-\terr = reftable_reader_seek_ref(rd, &it, \"\");\n+\treftable_reader_init_ref_iterator(rd, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_ref(&it, &rec);\n@@ -846,7 +857,8 @@ static void test_write_multiple_indices(void)\n \t * Seeking the log uses the log index now. In case there is any\n \t * confusion regarding indices we would notice here.\n \t */\n-\terr = reftable_reader_seek_log(reader, &it, \"\");\n+\treftable_reader_init_log_iterator(reader, &it);\n+\terr = reftable_iterator_seek_log(&it, \"\");\n \tEXPECT_ERR(err);\n \n \treftable_iterator_destroy(&it);\n@@ -901,7 +913,8 @@ static void test_write_multi_level_index(void)\n \t/*\n \t * Seeking the last ref should work as expected.\n \t */\n-\terr = reftable_reader_seek_ref(reader, &it, \"refs/heads/199\");\n+\treftable_reader_init_ref_iterator(reader, &it);\n+\terr = reftable_iterator_seek_ref(&it, \"refs/heads/199\");\n \tEXPECT_ERR(err);\n \n \treftable_iterator_destroy(&it);\ndiff --git a/reftable/reftable-reader.h b/reftable/reftable-reader.h\nindex 4a4bc2fdf8..52e4942b7b 100644\n--- a/reftable/reftable-reader.h\n+++ b/reftable/reftable-reader.h\n@@ -36,48 +36,17 @@ struct reftable_table;\n int reftable_new_reader(struct reftable_reader **pp,\n \t\t\tstruct reftable_block_source *src, const char *name);\n \n-/* reftable_reader_seek_ref returns an iterator where 'name' would be inserted\n- in the table. To seek to the start of the table, use name = \"\".\n-\n- example:\n-\n- struct reftable_reader *r = NULL;\n- int err = reftable_new_reader(&r, &src, \"filename\");\n- if (err < 0) { ... }\n- struct reftable_iterator it = {0};\n- err = reftable_reader_seek_ref(r, &it, \"refs/heads/master\");\n- if (err < 0) { ... }\n- struct reftable_ref_record ref = {0};\n- while (1) {\n- err = reftable_iterator_next_ref(&it, &ref);\n- if (err > 0) {\n- break;\n- }\n- if (err < 0) {\n- ..error handling..\n- }\n- ..found..\n- }\n- reftable_iterator_destroy(&it);\n- reftable_ref_record_release(&ref);\n-*/\n-int reftable_reader_seek_ref(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name);\n+/* Initialize a reftable iterator for reading refs. */\n+void reftable_reader_init_ref_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it);\n+\n+/* Initialize a reftable iterator for reading logs. */\n+void reftable_reader_init_log_iterator(struct reftable_reader *r,\n+\t\t\t\t struct reftable_iterator *it);\n \n /* returns the hash ID used in this table. */\n uint32_t reftable_reader_hash_id(struct reftable_reader *r);\n \n-/* seek to logs for the given name, older than update_index. To seek to the\n- start of the table, use name = \"\".\n-*/\n-int reftable_reader_seek_log_at(struct reftable_reader *r,\n-\t\t\t\tstruct reftable_iterator *it, const char *name,\n-\t\t\t\tuint64_t update_index);\n-\n-/* seek to newest log entry for given name. */\n-int reftable_reader_seek_log(struct reftable_reader *r,\n-\t\t\t struct reftable_iterator *it, const char *name);\n-\n /* closes and deallocates a reader. */\n void reftable_reader_free(struct reftable_reader *);\n \n-- \n2.45.GIT\n\n"},{"id":"494601","messageId":"51480c43287ee3164d108859725ca819b3466df5.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 12/13] reftable/stack: provide convenience functions to create iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:47:56Z","receivedAt":"2024-05-13T08:48:00Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"There exist a bunch of call sites in the reftable backend that want to\ncreate iterators for a reftable stack. This is rather convoluted right\nnow, where you always have to go via the merged table. And it is about\nto become even more convoluted when we split up iterator initialization\nand seeking in the next commit.\n\nIntroduce convenience functions that allow the caller to create an\niterator from a reftable stack directly without going through the merged\ntable. Adapt callers accordingly.\n\nSigned-off-by: Patrick Steinhardt \n---\n refs/reftable-backend.c | 48 +++++++++++++++++----------------------\n reftable/merged.c | 6 ++---\n reftable/merged.h | 6 +++++\n reftable/reftable-stack.h | 18 +++++++++++++++\n reftable/stack.c | 15 ++++++++++++\n 5 files changed, 63 insertions(+), 30 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex 010ef811b6..7ac2772bcb 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -15,7 +15,6 @@\n #include \"../reftable/reftable-record.h\"\n #include \"../reftable/reftable-error.h\"\n #include \"../reftable/reftable-iterator.h\"\n-#include \"../reftable/reftable-merged.h\"\n #include \"../setup.h\"\n #include \"../strmap.h\"\n #include \"parse.h\"\n@@ -462,7 +461,6 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n \t\t\t\t\t\t\t const char *prefix,\n \t\t\t\t\t\t\t int flags)\n {\n-\tstruct reftable_merged_table *merged_table;\n \tstruct reftable_ref_iterator *iter;\n \tint ret;\n \n@@ -482,9 +480,8 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n \tif (ret)\n \t\tgoto done;\n \n-\tmerged_table = reftable_stack_merged_table(stack);\n-\n-\tret = reftable_merged_table_seek_ref(merged_table, &iter->iter, prefix);\n+\treftable_stack_init_ref_iterator(stack, &iter->iter);\n+\tret = reftable_iterator_seek_ref(&iter->iter, prefix);\n \tif (ret)\n \t\tgoto done;\n \n@@ -1015,8 +1012,6 @@ static int transaction_update_cmp(const void *a, const void *b)\n static int write_transaction_table(struct reftable_writer *writer, void *cb_data)\n {\n \tstruct write_transaction_table_arg *arg = cb_data;\n-\tstruct reftable_merged_table *mt =\n-\t\treftable_stack_merged_table(arg->stack);\n \tuint64_t ts = reftable_stack_next_update_index(arg->stack);\n \tstruct reftable_log_record *logs = NULL;\n \tstruct ident_split committer_ident = {0};\n@@ -1051,6 +1046,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\tstruct reftable_log_record log = {0};\n \t\t\tstruct reftable_iterator it = {0};\n \n+\t\t\treftable_stack_init_log_iterator(arg->stack, &it);\n+\n \t\t\t/*\n \t\t\t * When deleting refs we also delete all reflog entries\n \t\t\t * with them. While it is not strictly required to\n@@ -1060,7 +1057,7 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\t * Unfortunately, we have no better way than to delete\n \t\t\t * all reflog entries one by one.\n \t\t\t */\n-\t\t\tret = reftable_merged_table_seek_log(mt, &it, u->refname);\n+\t\t\tret = reftable_iterator_seek_log(&it, u->refname);\n \t\t\twhile (ret == 0) {\n \t\t\t\tstruct reftable_log_record *tombstone;\n \n@@ -1354,7 +1351,6 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n {\n \tstruct write_copy_arg *arg = cb_data;\n \tuint64_t deletion_ts, creation_ts;\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(arg->stack);\n \tstruct reftable_ref_record old_ref = {0}, refs[2] = {0};\n \tstruct reftable_log_record old_log = {0}, *logs = NULL;\n \tstruct reftable_iterator it = {0};\n@@ -1488,7 +1484,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n \t * copy over all log entries from the old reflog. Last but not least,\n \t * when renaming we also have to delete all the old reflog entries.\n \t */\n-\tret = reftable_merged_table_seek_log(mt, &it, arg->oldname);\n+\treftable_stack_init_log_iterator(arg->stack, &it);\n+\tret = reftable_iterator_seek_log(&it, arg->oldname);\n \tif (ret < 0)\n \t\tgoto done;\n \n@@ -1694,7 +1691,6 @@ static struct ref_iterator_vtable reftable_reflog_iterator_vtable = {\n static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftable_ref_store *refs,\n \t\t\t\t\t\t\t\t struct reftable_stack *stack)\n {\n-\tstruct reftable_merged_table *merged_table;\n \tstruct reftable_reflog_iterator *iter;\n \tint ret;\n \n@@ -1711,9 +1707,8 @@ static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftabl\n \tif (ret < 0)\n \t\tgoto done;\n \n-\tmerged_table = reftable_stack_merged_table(stack);\n-\n-\tret = reftable_merged_table_seek_log(merged_table, &iter->iter, \"\");\n+\treftable_stack_init_log_iterator(stack, &iter->iter);\n+\tret = reftable_iterator_seek_log(&iter->iter, \"\");\n \tif (ret < 0)\n \t\tgoto done;\n \n@@ -1771,7 +1766,6 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_READ, \"for_each_reflog_ent_reverse\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = NULL;\n \tstruct reftable_log_record log = {0};\n \tstruct reftable_iterator it = {0};\n \tint ret;\n@@ -1779,8 +1773,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \tif (refs->err < 0)\n \t\treturn refs->err;\n \n-\tmt = reftable_stack_merged_table(stack);\n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\tret = reftable_iterator_seek_log(&it, refname);\n \twhile (!ret) {\n \t\tret = reftable_iterator_next_log(&it, &log);\n \t\tif (ret < 0)\n@@ -1808,7 +1802,6 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_READ, \"for_each_reflog_ent\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = NULL;\n \tstruct reftable_log_record *logs = NULL;\n \tstruct reftable_iterator it = {0};\n \tsize_t logs_alloc = 0, logs_nr = 0, i;\n@@ -1817,8 +1810,8 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \tif (refs->err < 0)\n \t\treturn refs->err;\n \n-\tmt = reftable_stack_merged_table(stack);\n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\tret = reftable_iterator_seek_log(&it, refname);\n \twhile (!ret) {\n \t\tstruct reftable_log_record log = {0};\n \n@@ -1855,7 +1848,6 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_READ, \"reflog_exists\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(stack);\n \tstruct reftable_log_record log = {0};\n \tstruct reftable_iterator it = {0};\n \tint ret;\n@@ -1868,7 +1860,8 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \tif (ret < 0)\n \t\tgoto done;\n \n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\tret = reftable_iterator_seek_log(&it, refname);\n \tif (ret < 0)\n \t\tgoto done;\n \n@@ -1966,8 +1959,6 @@ struct write_reflog_delete_arg {\n static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_data)\n {\n \tstruct write_reflog_delete_arg *arg = cb_data;\n-\tstruct reftable_merged_table *mt =\n-\t\treftable_stack_merged_table(arg->stack);\n \tstruct reftable_log_record log = {0}, tombstone = {0};\n \tstruct reftable_iterator it = {0};\n \tuint64_t ts = reftable_stack_next_update_index(arg->stack);\n@@ -1975,12 +1966,14 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da\n \n \treftable_writer_set_limits(writer, ts, ts);\n \n+\treftable_stack_init_log_iterator(arg->stack, &it);\n+\n \t/*\n \t * In order to delete a table we need to delete all reflog entries one\n \t * by one. This is inefficient, but the reftable format does not have a\n \t * better marker right now.\n \t */\n-\tret = reftable_merged_table_seek_log(mt, &it, arg->refname);\n+\tret = reftable_iterator_seek_log(&it, arg->refname);\n \twhile (ret == 0) {\n \t\tret = reftable_iterator_next_log(&it, &log);\n \t\tif (ret < 0)\n@@ -2116,7 +2109,6 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \tstruct reftable_ref_store *refs =\n \t\treftable_be_downcast(ref_store, REF_STORE_WRITE, \"reflog_expire\");\n \tstruct reftable_stack *stack = stack_for(refs, refname, &refname);\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(stack);\n \tstruct reftable_log_record *logs = NULL;\n \tstruct reftable_log_record *rewritten = NULL;\n \tstruct reftable_ref_record ref_record = {0};\n@@ -2135,7 +2127,9 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \tif (ret < 0)\n \t\tgoto done;\n \n-\tret = reftable_merged_table_seek_log(mt, &it, refname);\n+\treftable_stack_init_log_iterator(stack, &it);\n+\n+\tret = reftable_iterator_seek_log(&it, refname);\n \tif (ret < 0)\n \t\tgoto done;\n \ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex fc7946d90d..d127f99360 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -253,9 +253,9 @@ reftable_merged_table_min_update_index(struct reftable_merged_table *mt)\n \treturn mt->min;\n }\n \n-static void merged_table_init_iter(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t uint8_t typ)\n+void merged_table_init_iter(struct reftable_merged_table *mt,\n+\t\t\t struct reftable_iterator *it,\n+\t\t\t uint8_t typ)\n {\n \tstruct merged_iter *mi = reftable_malloc(sizeof(*mi));\n \tmerged_iter_init(mi, mt, typ);\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex a2571dbc99..a10469f58e 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -26,4 +26,10 @@ struct reftable_merged_table {\n \n void merged_table_release(struct reftable_merged_table *mt);\n \n+struct reftable_iterator;\n+\n+void merged_table_init_iter(struct reftable_merged_table *mt,\n+\t\t\t struct reftable_iterator *it,\n+\t\t\t uint8_t typ);\n+\n #endif\ndiff --git a/reftable/reftable-stack.h b/reftable/reftable-stack.h\nindex 1b602dda58..26740e6073 100644\n--- a/reftable/reftable-stack.h\n+++ b/reftable/reftable-stack.h\n@@ -66,6 +66,24 @@ int reftable_stack_add(struct reftable_stack *st,\n \t\t\t\t\t void *write_arg),\n \t\t void *write_arg);\n \n+struct reftable_iterator;\n+\n+/*\n+ * Initialize an iterator for the merged tables contained in the stack that can\n+ * be used to iterate through refs. The iterator is valid until the next reload\n+ * or write.\n+ */\n+void reftable_stack_init_ref_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it);\n+\n+/*\n+ * Initialize an iterator for the merged tables contained in the stack that can\n+ * be used to iterate through logs. The iterator is valid until the next reload\n+ * or write.\n+ */\n+void reftable_stack_init_log_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it);\n+\n /* returns the merged_table for seeking. This table is valid until the\n * next write or reload, and should not be closed or deleted.\n */\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex a59ebe038d..03f95935e1 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -10,6 +10,7 @@ license that can be found in the LICENSE file or at\n \n #include \"../write-or-die.h\"\n #include \"system.h\"\n+#include \"constants.h\"\n #include \"merged.h\"\n #include \"reader.h\"\n #include \"reftable-error.h\"\n@@ -130,6 +131,20 @@ int read_lines(const char *filename, char ***namesp)\n \treturn err;\n }\n \n+void reftable_stack_init_ref_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\tmerged_table_init_iter(reftable_stack_merged_table(st),\n+\t\t\t it, BLOCK_TYPE_REF);\n+}\n+\n+void reftable_stack_init_log_iterator(struct reftable_stack *st,\n+\t\t\t\t struct reftable_iterator *it)\n+{\n+\tmerged_table_init_iter(reftable_stack_merged_table(st),\n+\t\t\t it, BLOCK_TYPE_LOG);\n+}\n+\n struct reftable_merged_table *\n reftable_stack_merged_table(struct reftable_stack *st)\n {\n-- \n2.45.GIT\n\n"},{"id":"494602","messageId":"2586e93c448e5df2fab51ba231e413c12e522f0e.1715589670.git.ps@pks.im","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"[PATCH v2 13/13] reftable/merged: adapt interface to allow reuse of iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-13T08:48:01Z","receivedAt":"2024-05-13T08:48:06Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Refactor the interfaces exposed by `struct reftable_merged_table` and\n`struct merged_iter` such that they support iterator reuse. This is done\nby separating initialization of the iterator and seeking on it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 35 -----------------------------------\n reftable/merged_test.c | 19 +++++++++++++------\n reftable/reftable-merged.h | 15 ---------------\n reftable/stack.c | 14 +++++++++-----\n 4 files changed, 22 insertions(+), 61 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex d127f99360..0da9dba265 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -262,41 +262,6 @@ void merged_table_init_iter(struct reftable_merged_table *mt,\n \titerator_from_merged_iter(it, mi);\n }\n \n-int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name)\n-{\n-\tstruct reftable_record rec = {\n-\t\t.type = BLOCK_TYPE_REF,\n-\t\t.u.ref = {\n-\t\t\t.refname = (char *)name,\n-\t\t},\n-\t};\n-\tmerged_table_init_iter(mt, it, BLOCK_TYPE_REF);\n-\treturn iterator_seek(it, &rec);\n-}\n-\n-int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name, uint64_t update_index)\n-{\n-\tstruct reftable_record rec = { .type = BLOCK_TYPE_LOG,\n-\t\t\t\t .u.log = {\n-\t\t\t\t\t .refname = (char *)name,\n-\t\t\t\t\t .update_index = update_index,\n-\t\t\t\t } };\n-\tmerged_table_init_iter(mt, it, BLOCK_TYPE_LOG);\n-\treturn iterator_seek(it, &rec);\n-}\n-\n-int reftable_merged_table_seek_log(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name)\n-{\n-\tuint64_t max = ~((uint64_t)0);\n-\treturn reftable_merged_table_seek_log_at(mt, it, name, max);\n-}\n-\n uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *mt)\n {\n \treturn mt->hash_id;\ndiff --git a/reftable/merged_test.c b/reftable/merged_test.c\nindex 530fc82d1c..33a17efcde 100644\n--- a/reftable/merged_test.c\n+++ b/reftable/merged_test.c\n@@ -12,6 +12,7 @@ license that can be found in the LICENSE file or at\n \n #include \"basics.h\"\n #include \"blocksource.h\"\n+#include \"constants.h\"\n #include \"reader.h\"\n #include \"record.h\"\n #include \"test_framework.h\"\n@@ -145,7 +146,10 @@ static void test_merged_between(void)\n \tint i;\n \tstruct reftable_ref_record ref = { NULL };\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_merged_table_seek_ref(mt, &it, \"a\");\n+\tint err;\n+\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_REF);\n+\terr = reftable_iterator_seek_ref(&it, \"a\");\n \tEXPECT_ERR(err);\n \n \terr = reftable_iterator_next_ref(&it, &ref);\n@@ -217,14 +221,15 @@ static void test_merged(void)\n \tstruct reftable_reader **readers = NULL;\n \tstruct reftable_merged_table *mt =\n \t\tmerged_table_from_records(refs, &bs, &readers, sizes, bufs, 3);\n-\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_merged_table_seek_ref(mt, &it, \"a\");\n+\tint err;\n \tstruct reftable_ref_record *out = NULL;\n \tsize_t len = 0;\n \tsize_t cap = 0;\n \tint i = 0;\n \n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_REF);\n+\terr = reftable_iterator_seek_ref(&it, \"a\");\n \tEXPECT_ERR(err);\n \tEXPECT(reftable_merged_table_hash_id(mt) == GIT_SHA1_FORMAT_ID);\n \tEXPECT(reftable_merged_table_min_update_index(mt) == 1);\n@@ -348,14 +353,15 @@ static void test_merged_logs(void)\n \tstruct reftable_reader **readers = NULL;\n \tstruct reftable_merged_table *mt = merged_table_from_log_records(\n \t\tlogs, &bs, &readers, sizes, bufs, 3);\n-\n \tstruct reftable_iterator it = { NULL };\n-\tint err = reftable_merged_table_seek_log(mt, &it, \"a\");\n+\tint err;\n \tstruct reftable_log_record *out = NULL;\n \tsize_t len = 0;\n \tsize_t cap = 0;\n \tint i = 0;\n \n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);\n+\terr = reftable_iterator_seek_log(&it, \"a\");\n \tEXPECT_ERR(err);\n \tEXPECT(reftable_merged_table_hash_id(mt) == GIT_SHA1_FORMAT_ID);\n \tEXPECT(reftable_merged_table_min_update_index(mt) == 1);\n@@ -377,7 +383,8 @@ static void test_merged_logs(void)\n \t\t\t\t\t\t GIT_SHA1_RAWSZ));\n \t}\n \n-\terr = reftable_merged_table_seek_log_at(mt, &it, \"a\", 2);\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);\n+\terr = reftable_iterator_seek_log_at(&it, \"a\", 2);\n \tEXPECT_ERR(err);\n \treftable_log_record_release(&out[0]);\n \terr = reftable_iterator_next_log(&it, &out[0]);\ndiff --git a/reftable/reftable-merged.h b/reftable/reftable-merged.h\nindex c91a2d83a2..14d5fc9f05 100644\n--- a/reftable/reftable-merged.h\n+++ b/reftable/reftable-merged.h\n@@ -36,21 +36,6 @@ int reftable_new_merged_table(struct reftable_merged_table **dest,\n \t\t\t struct reftable_table *stack, size_t n,\n \t\t\t uint32_t hash_id);\n \n-/* returns an iterator positioned just before 'name' */\n-int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name);\n-\n-/* returns an iterator for log entry, at given update_index */\n-int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name, uint64_t update_index);\n-\n-/* like reftable_merged_table_seek_log_at but look for the newest entry. */\n-int reftable_merged_table_seek_log(struct reftable_merged_table *mt,\n-\t\t\t\t struct reftable_iterator *it,\n-\t\t\t\t const char *name);\n-\n /* returns the max update_index covered by this merged table. */\n uint64_t\n reftable_merged_table_max_update_index(struct reftable_merged_table *mt);\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 03f95935e1..7af4c3fd66 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -925,7 +925,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\tgoto done;\n \t}\n \n-\terr = reftable_merged_table_seek_ref(mt, &it, \"\");\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_REF);\n+\terr = reftable_iterator_seek_ref(&it, \"\");\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -949,7 +950,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t}\n \treftable_iterator_destroy(&it);\n \n-\terr = reftable_merged_table_seek_log(mt, &it, \"\");\n+\tmerged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);\n+\terr = reftable_iterator_seek_log(&it, \"\");\n \tif (err < 0)\n \t\tgoto done;\n \n@@ -1340,9 +1342,11 @@ int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,\n int reftable_stack_read_log(struct reftable_stack *st, const char *refname,\n \t\t\t struct reftable_log_record *log)\n {\n-\tstruct reftable_iterator it = { NULL };\n-\tstruct reftable_merged_table *mt = reftable_stack_merged_table(st);\n-\tint err = reftable_merged_table_seek_log(mt, &it, refname);\n+\tstruct reftable_iterator it = {0};\n+\tint err;\n+\n+\treftable_stack_init_log_iterator(st, &it);\n+\terr = reftable_iterator_seek_log(&it, refname);\n \tif (err)\n \t\tgoto done;\n \n-- \n2.45.GIT\n\n"},{"id":"494838","messageId":"hkjaxz4qykmiby3xxsq23mnlawsp7e6kgarbvo3owdoepi6dii@znu6igt7ki2c","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"Re: [PATCH v2 00/13] reftable: prepare for re-seekable iterators","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-05-15T20:15:55Z","receivedAt":"2024-05-15T20:17:24Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/05/13 10:46AM, Patrick Steinhardt wrote:\n> Hi,\n> \n> this is the second version of my patch series that prepares the reftable\n> iterators to become re-seekable. These refactorings will eventually\n> allow us to reuse data structures by iterators and optimize for certain\n> cases.\n> \n> Changes compared to v1:\n> \n> - Various fixes to commit messages.\n> \n> - Fixed a copy & pasted comment to refer to logs instead of refs.\n> \n> The series continues to build on top of ps/reftable-write-optim. There\n> is a merge conflict with the in-flight ps/reftable-write-options, but\n> given that this series has not yet been merged to next and because Junio\n> has already resolved the conflict in \"seen\" I decided to not pull it in\n> as an additional dependency.\n\nThanks Patrick! From the range-diff, this version looks good to me :)\n\n-Justin\n"},{"id":"495161","messageId":"CAOLa=ZQb3if7vcvRcOm8qHSMGo=dSv0nsjCk0R_hhRWU_d7wfw@mail.gmail.com","threadId":"61433","inReplyTo":"ca86a8b58dd074287dd2dd352610ffe46e1605b9.1715589670.git.ps@pks.im","subject":"Re: [PATCH v2 01/13] reftable/block: use `size_t` to track restart point index","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-05-21T13:34:48Z","receivedAt":"2024-05-21T13:34:49Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt writes:\n\n> The function `block_reader_restart_offset()` gets the offset of the\n> `i`th restart point. `i` is a signed integer though, which is certainly\n> not the correct type to track indices like this. Furthermore, both\n> callers end up passing a `size_t`.\n>\n> Refactor the code to use a `size_t` instead.\n\nMore of a question for my understanding: Why use `size_t` vs `uint16_t`\nhere? I'm asking since the restart count is defined as `uint16_t\nrestart_count` in `struct block_reader`.\n\n>\n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/block.c | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/reftable/block.c b/reftable/block.c\n> index 5942cb4053..00030eee06 100644\n> --- a/reftable/block.c\n> +++ b/reftable/block.c\n> @@ -326,9 +326,9 @@ int block_reader_first_key(const struct block_reader *br, struct strbuf *key)\n> \treturn 0;\n> }\n>\n> -static uint32_t block_reader_restart_offset(const struct block_reader *br, int i)\n> +static uint32_t block_reader_restart_offset(const struct block_reader *br, size_t idx)\n> {\n> -\treturn get_be24(br->restart_bytes + 3 * i);\n> +\treturn get_be24(br->restart_bytes + 3 * idx);\n> }\n>\n> void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)\n> --\n> 2.45.GIT\n"},{"id":"495167","messageId":"CAOLa=ZSC4OF9b1STzEZfPjrJDbee04A-piNZ86kDS_GDij_3Jw@mail.gmail.com","threadId":"61433","inReplyTo":"716863a580f9e1ef8ea796c25c97e50c63585a7b.1715589670.git.ps@pks.im","subject":"Re: [PATCH v2 03/13] reftable/reader: unify indexed and linear seeking","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-05-21T14:41:27Z","receivedAt":"2024-05-21T14:41:30Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt writes:\n\n> In `reader_seek_internal()` we either end up doing an indexed seek when\n> there is one or a linear seek otherwise. These two code paths are\n\nAre we missing the subject here?\n\n[snip]\n"},{"id":"495170","messageId":"CAOLa=ZQPS_gVAf-f3cW_=C18B4C7i-gh=bYMWW2X03S4nYK3Aw@mail.gmail.com","threadId":"61433","inReplyTo":"cover.1715589670.git.ps@pks.im","subject":"Re: [PATCH v2 00/13] reftable: prepare for re-seekable iterators","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-05-21T15:31:15Z","receivedAt":"2024-05-21T15:31:17Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Hello,\n\nPatrick Steinhardt writes:\n> Hi,\n>\n> this is the second version of my patch series that prepares the reftable\n> iterators to become re-seekable. These refactorings will eventually\n> allow us to reuse data structures by iterators and optimize for certain\n> cases.\n>\n> Changes compared to v1:\n>\n> - Various fixes to commit messages.\n>\n> - Fixed a copy & pasted comment to refer to logs instead of refs.\n>\n> The series continues to build on top of ps/reftable-write-optim. There\n> is a merge conflict with the in-flight ps/reftable-write-options, but\n> given that this series has not yet been merged to next and because Junio\n> has already resolved the conflict in \"seen\" I decided to not pull it in\n> as an additional dependency.\n>\n> Thanks!\n>\n> Patrick\n\nI didn't review the earlier version. I did go through the patches in\nthis version, I only have a nit in the first patch, not worth a reroll.\nThanks for the series, I have nothing more to add.\n\nKarthik\n"},{"id":"495270","messageId":"Zk2ddTsVLXbjDmmh@tanuki","threadId":"61433","inReplyTo":"CAOLa=ZQb3if7vcvRcOm8qHSMGo=dSv0nsjCk0R_hhRWU_d7wfw@mail.gmail.com","subject":"Re: [PATCH v2 01/13] reftable/block: use `size_t` to track restart point index","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-22T07:23:33Z","receivedAt":"2024-05-22T07:23:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, May 21, 2024 at 01:34:48PM +0000, Karthik Nayak wrote:\n> Patrick Steinhardt writes:\n> \n> > The function `block_reader_restart_offset()` gets the offset of the\n> > `i`th restart point. `i` is a signed integer though, which is certainly\n> > not the correct type to track indices like this. Furthermore, both\n> > callers end up passing a `size_t`.\n> >\n> > Refactor the code to use a `size_t` instead.\n> \n> More of a question for my understanding: Why use `size_t` vs `uint16_t`\n> here? I'm asking since the restart count is defined as `uint16_t\n> restart_count` in `struct block_reader`.\n\nMostly because all callers already use `size_t`, and it's customary to\nuse them when talking about indices. We could use `uint16_t`, too, but\nit didn't really feel worth it to adjust all callers.\n\nPatrick\n"},{"id":"495271","messageId":"Zk2de9lNrNJRuwUp@tanuki","threadId":"61433","inReplyTo":"CAOLa=ZSC4OF9b1STzEZfPjrJDbee04A-piNZ86kDS_GDij_3Jw@mail.gmail.com","subject":"Re: [PATCH v2 03/13] reftable/reader: unify indexed and linear seeking","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-22T07:23:39Z","receivedAt":"2024-05-22T07:23:44Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, May 21, 2024 at 02:41:27PM +0000, Karthik Nayak wrote:\n> Patrick Steinhardt writes:\n> \n> > In `reader_seek_internal()` we either end up doing an indexed seek when\n> > there is one or a linear seek otherwise. These two code paths are\n> \n> Are we missing the subject here?\n\nHm. \"one\" refers back to \"indexed\" and is supposed to mean \"index\" here.\nI agree that this is easy to misread though and may not even be proper\nEnglish.\n\nIt doesn't really feel worth it to rebase this series just for this\nissue, but if I did it would be 's/one/an index/'. Let me know in case\nyou disagree though.\n\nPatrick\n"},{"id":"495272","messageId":"Zk2dh9-E8Sa8kzJd@tanuki","threadId":"61433","inReplyTo":"CAOLa=ZQPS_gVAf-f3cW_=C18B4C7i-gh=bYMWW2X03S4nYK3Aw@mail.gmail.com","subject":"Re: [PATCH v2 00/13] reftable: prepare for re-seekable iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-05-22T07:23:51Z","receivedAt":"2024-05-22T07:23:57Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, May 21, 2024 at 03:31:15PM +0000, Karthik Nayak wrote:\n> Hello,\n> \n> Patrick Steinhardt writes:\n> > Hi,\n> >\n> > this is the second version of my patch series that prepares the reftable\n> > iterators to become re-seekable. These refactorings will eventually\n> > allow us to reuse data structures by iterators and optimize for certain\n> > cases.\n> >\n> > Changes compared to v1:\n> >\n> > - Various fixes to commit messages.\n> >\n> > - Fixed a copy & pasted comment to refer to logs instead of refs.\n> >\n> > The series continues to build on top of ps/reftable-write-optim. There\n> > is a merge conflict with the in-flight ps/reftable-write-options, but\n> > given that this series has not yet been merged to next and because Junio\n> > has already resolved the conflict in \"seen\" I decided to not pull it in\n> > as an additional dependency.\n> >\n> > Thanks!\n> >\n> > Patrick\n> \n> I didn't review the earlier version. I did go through the patches in\n> this version, I only have a nit in the first patch, not worth a reroll.\n> Thanks for the series, I have nothing more to add.\n\nThanks!\n\nPatrick\n"},{"id":"495275","messageId":"CAOLa=ZR=681m_XE=-CRrEZfQLPdbSAm7S8M0b7ZotUSG9LbX+Q@mail.gmail.com","threadId":"61433","inReplyTo":"Zk2de9lNrNJRuwUp@tanuki","subject":"Re: [PATCH v2 03/13] reftable/reader: unify indexed and linear seeking","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-05-22T07:56:05Z","receivedAt":"2024-05-22T07:56:07Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt writes:\n\n> On Tue, May 21, 2024 at 02:41:27PM +0000, Karthik Nayak wrote:\n>> Patrick Steinhardt writes:\n>>\n>> > In `reader_seek_internal()` we either end up doing an indexed seek when\n>> > there is one or a linear seek otherwise. These two code paths are\n>>\n>> Are we missing the subject here?\n>\n> Hm. \"one\" refers back to \"indexed\" and is supposed to mean \"index\" here.\n> I agree that this is easy to misread though and may not even be proper\n> English.\n>\n> It doesn't really feel worth it to rebase this series just for this\n> issue, but if I did it would be 's/one/an index/'. Let me know in case\n> you disagree though.\n>\n> Patrick\n\nOkay that makes a bunch of sense, I think it is okay though and not\nworth a reroll.\n\nKarthik\n"}]}