reftable: prepare for re-seekable iterators
cover reftable: prepare for re-seekable iterators
Hi,
the reftable library uses iterators both to iterate through a set of records, but also to look up a single record. In past patch series, I have focussed quite a lot to optimize the case where we iterate through a large set of records. But looking up a records is still quite inefficient when doing multiple lookups. This is because whenever we want to look up a record, we need to create a new iterator, including all of its internal data structures.
To address this inefficiency, the patch series at hand refactors the reftable library such that creation of iterators and seeking on an iterator are separate steps. This refactoring prepares us for reusing iterators to perform multiple seeks, which in turn will allow us to reuse internal data structures for subsequent seeks.
The patch series is structured as follows:
- Patches 1 to 5 perform some general cleanups to make the reftable iterators easier to understand.
- Patchges 6 to 9 refactor the iterators internally such that creation of the iterator and seeking on it is clearly separated.
- Patches 10 to 13 adapt the external interfaces such that they allow for reuse of iterators.
Note: this series does not yet go all the way to re-seekable iterators, and there are no users yet. The patch series is complex enough as-is already, so I decided to defer that to the next iteration. Thus, the whole refactoring here should essentially be a large no-op that prepares the infrastructure for re-seekable iterators.
The series depends on pks/reftable-write-optim at fa74f32291 (reftable/block: reuse compressed array, 2024-04-08).
Thanks!
Patrick
Patrick Steinhardt (13):
reftable/block: use size_t to track restart point index reftable/reader: avoid copying index iterator reftable/reader: unify indexed and linear seeking reftable/reader: separate concerns of table iter and reftable reader reftable/reader: inline reader_seek_internal() reftable/reader: set up the reader when initializing table iterator reftable/merged: split up initialization and seeking of records reftable/merged: simplify indices for subiterators reftable/generic: move seeking of records into the iterator reftable/generic: adapt interface to allow reuse of iterators reftable/reader: adapt interface to allow reuse of iterators reftable/stack: provide convenience functions to create iterators reftable/merged: adapt interface to allow reuse of iterators
refs/reftable-backend.c | 48 ++++---- reftable/block.c | 4 +- reftable/generic.c | 94 +++++++++++---- reftable/generic.h | 9 +- reftable/iter.c | 23 +++- reftable/merged.c | 148 ++++++++---------------- reftable/merged.h | 6 + reftable/merged_test.c | 19 ++- reftable/reader.c | 218 +++++++++++++++-------------------- reftable/readwrite_test.c | 35 ++++-- reftable/reftable-generic.h | 8 +- reftable/reftable-iterator.h | 21 ++++ reftable/reftable-merged.h | 15 --- reftable/reftable-reader.h | 45 ++------ reftable/reftable-stack.h | 18 +++ reftable/stack.c | 29 ++++- 16 files changed, 378 insertions(+), 362 deletions(-)
Signature · 1 line
2.45.0
PATCH 1/13 reftable/block: use `size_t` to track restart point index
The function block_reader_restart_offset() gets the offset of the ith restart point. i is a signed integer though, which is certainly not the correct type to track indices like this. Furthermore, both callers end up passing a size_t.
Refactor the code to use a size_t instead.
--- reftable/block.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
reftable/block.c +2 -2
@@ -326,9 +326,9 @@ int block_reader_first_key(const struct block_reader *br, struct strbuf *key)return 0 ; } -static uint32_t block_reader_restart_offset (const struct block_reader *br,int i) +static uint32_t block_reader_restart_offset (const struct block_reader *br,size_t idx) { -return get_be24 (br->restart_bytes +3 * i); +return get_be24 (br->restart_bytes +3 * idx); }void block_iter_seek_start (struct block_iter *it,const struct block_reader *br)
Signature · 1 line
2.45.0
PATCH 2/13 reftable/reader: avoid copying index iterator
In reply to Patrick SteinhardtWhen doing an indexed seek we need to walk down the multi-level index until we finally hit a record of the desired indexed type. This loop performs a copy of the index iterator on every iteration, which is both hard to understand and completely unnecessary.
Refactor the code so that we use a single iterator to walk down the indices, only.
Note that while this should improve performance, the improvement is negligible in all but the most unreasonable repositories. This is because the effect is only really noticeable when we have to walk down many levels of indices, which is not something that a repository would typically have. So the motivation for this change is really only about readability.
--- reftable/reader.c | 38 ++++++++++++++------------------------ 1 file changed, 14 insertions(+), 24 deletions(-)
reftable/reader.c +14 -24
@@ -510,13 +510,11 @@ static int reader_seek_indexed(struct reftable_reader *r, .type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }, }; -struct table_iter index_iter =TABLE_ITER_INIT ; -struct table_iter empty =TABLE_ITER_INIT ; -struct table_iter next =TABLE_ITER_INIT ; +struct table_iter ti =TABLE_ITER_INIT , *malloced;int err =0 ;reftable_record_key (rec, &want_index.u.idx.last_key); - err =reader_start (r, &index_iter,reftable_record_type (rec),1 ); + err =reader_start (r, &ti,reftable_record_type (rec),1 );if (err <0 ) goto done;
@@ -526,7 +524,7 @@ static int reader_seek_indexed(struct reftable_reader *r,* highest layer that identifies the relevant index block as well as * the record inside that block that corresponds to our wanted key. */ - err =reader_seek_linear (&index_iter, &want_index); + err =reader_seek_linear (&ti, &want_index);if (err <0 ) goto done;
@@ -552,44 +550,36 @@ static int reader_seek_indexed(struct reftable_reader *r,* all levels of the index only to find out that the key does * not exist. */ - err =table_iter_next (&index_iter, &index_result); + err =table_iter_next (&ti, &index_result);if (err !=0 ) goto done; - err =reader_table_iter_at (r, &next, index_result.u.idx.offset, -0 ); + err =reader_table_iter_at (r, &ti, index_result.u.idx.offset,0 );if (err !=0 ) goto done; - err =block_iter_seek_key (&next.bi, &next.br, &want_index.u.idx.last_key); + err =block_iter_seek_key (&ti.bi, &ti.br, &want_index.u.idx.last_key);if (err <0 ) goto done; -if (next.typ ==reftable_record_type (rec)) { +if (ti.typ ==reftable_record_type (rec)) { err =0 ;break ; } -if (next.typ !=BLOCK_TYPE_INDEX ) { +if (ti.typ !=BLOCK_TYPE_INDEX ) { err =REFTABLE_FORMAT_ERROR ; -break ; + goto done; } - -table_iter_close (&index_iter); - index_iter = next; - next = empty; } -if (err ==0 ) { -struct table_iter *malloced =reftable_calloc (1 ,sizeof (*malloced)); - *malloced = next; - next = empty; -iterator_from_table_iter (it, malloced); - } +REFTABLE_ALLOC_ARRAY (malloced,1 ); + *malloced = ti; +iterator_from_table_iter (it, malloced); done: -table_iter_close (&next); -table_iter_close (&index_iter); +if (err) +table_iter_close (&ti);reftable_record_release (&want_index);reftable_record_release (&index_result);return err;
Signature · 1 line
2.45.0
PATCH 3/13 reftable/reader: unify indexed and linear seeking
In reply to Patrick SteinhardtIn reader_seek_internal() we either end up doing an indexed seek when there is one or a linear seek otherwise. These two code paths are disjunct without a good reason, where the indexed seek will cause us to exit early.
Refactor the two code paths such that it becomes possible to share a bit more code between them.
--- reftable/reader.c | 42 ++++++++++++++++-------------------------- 1 file changed, 16 insertions(+), 26 deletions(-)
reftable/reader.c +16 -26
@@ -425,7 +425,7 @@ static int reader_seek_linear(struct table_iter *ti,struct strbuf want_key =STRBUF_INIT ;struct strbuf got_key =STRBUF_INIT ;struct reftable_record rec; -int err =-1 ; +int err;reftable_record_init (&rec,reftable_record_type (want));reftable_record_key (want, &want_key);
@@ -499,8 +499,8 @@ static int reader_seek_linear(struct table_iter *ti,return err; } -static int reader_seek_indexed (struct reftable_reader *r, -struct reftable_iterator *it, +static int reader_seek_indexed (struct table_iter *ti, +struct reftable_reader *r,struct reftable_record *rec) {struct reftable_record want_index = {
@@ -510,13 +510,9 @@ static int reader_seek_indexed(struct reftable_reader *r, .type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }, }; -struct table_iter ti =TABLE_ITER_INIT , *malloced; -int err =0 ; +int err;reftable_record_key (rec, &want_index.u.idx.last_key); - err =reader_start (r, &ti,reftable_record_type (rec),1 ); -if (err <0 ) - goto done;/* * The index may consist of multiple levels, where each level may have
@@ -524,7 +520,7 @@ static int reader_seek_indexed(struct reftable_reader *r,* highest layer that identifies the relevant index block as well as * the record inside that block that corresponds to our wanted key. */ - err =reader_seek_linear (&ti, &want_index); + err =reader_seek_linear (ti, &want_index);if (err <0 ) goto done;
@@ -550,36 +546,30 @@ static int reader_seek_indexed(struct reftable_reader *r,* all levels of the index only to find out that the key does * not exist. */ - err =table_iter_next (&ti, &index_result); + err =table_iter_next (ti, &index_result);if (err !=0 ) goto done; - err =reader_table_iter_at (r, &ti, index_result.u.idx.offset,0 ); + err =reader_table_iter_at (r, ti, index_result.u.idx.offset,0 );if (err !=0 ) goto done; - err =block_iter_seek_key (&ti.bi, &ti.br, &want_index.u.idx.last_key); + err =block_iter_seek_key (&ti->bi, &ti->br, &want_index.u.idx.last_key);if (err <0 ) goto done; -if (ti.typ ==reftable_record_type (rec)) { +if (ti->typ ==reftable_record_type (rec)) { err =0 ;break ; } -if (ti.typ !=BLOCK_TYPE_INDEX ) { +if (ti->typ !=BLOCK_TYPE_INDEX ) { err =REFTABLE_FORMAT_ERROR ; goto done; } } -REFTABLE_ALLOC_ARRAY (malloced,1 ); - *malloced = ti; -iterator_from_table_iter (it, malloced); - done: -if (err) -table_iter_close (&ti);reftable_record_release (&want_index);reftable_record_release (&index_result);return err;
@@ -595,15 +585,15 @@ static int reader_seek_internal(struct reftable_reader *r,struct table_iter ti =TABLE_ITER_INIT , *p;int err; -if (idx >0 ) -return reader_seek_indexed (r, it, rec); - - err =reader_start (r, &ti,reftable_record_type (rec),0 ); + err =reader_start (r, &ti,reftable_record_type (rec), !!idx);if (err <0 ) goto out; - err =reader_seek_linear (&ti, rec); -if (err <0 ) +if (idx) + err =reader_seek_indexed (&ti, r, rec); +else + err =reader_seek_linear (&ti, rec); +if (err) goto out;REFTABLE_ALLOC_ARRAY (p,1 );
Signature · 1 line
2.45.0
PATCH 4/13 reftable/reader: separate concerns of table iter and reftable reader
In reply to Patrick SteinhardtIn "reftable/reader.c" we implement two different interfaces:
- The reftable reader contains the logic to read reftables.
- The table iterator is used to iterate through a single reftable read by the reader.
The way those two types are used in the code is somewhat confusing though because seeking inside a table is implemented as if it was part of the reftable reader, even though it is ultimately more of a detail implemented by the table iterator.
Make the boundary between those two types clearer by renaming functions that seek records in a table such that they clearly belong to the table iterator's logic.
--- reftable/reader.c | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-)
reftable/reader.c +15 -17
@@ -386,9 +386,8 @@ static void iterator_from_table_iter(struct reftable_iterator *it, it->ops = &table_iter_vtable; } -static int reader_table_iter_at (struct reftable_reader *r, -struct table_iter *ti,uint64_t off, -uint8_t typ) +static int table_iter_seek_to (struct table_iter *ti,struct reftable_reader *r, +uint64_t off,uint8_t typ) {int err;
@@ -403,8 +402,8 @@ static int reader_table_iter_at(struct reftable_reader *r,return 0 ; } -static int reader_start (struct reftable_reader *r,struct table_iter *ti, -uint8_t typ,int index) +static int table_iter_seek_start (struct table_iter *ti,struct reftable_reader *r, +uint8_t typ,int index) {struct reftable_reader_offsets *offs =reader_offsets_for (r, typ);uint64_t off = offs->offset;
@@ -416,11 +415,11 @@ static int reader_start(struct reftable_reader *r, struct table_iter *ti, typ =BLOCK_TYPE_INDEX ; } -return reader_table_iter_at (r, ti, off, typ); +return table_iter_seek_to (ti, r, off, typ); } -static int reader_seek_linear (struct table_iter *ti, -struct reftable_record *want) +static int table_iter_seek_linear (struct table_iter *ti, +struct reftable_record *want) {struct strbuf want_key =STRBUF_INIT ;struct strbuf got_key =STRBUF_INIT ;
@@ -499,9 +498,8 @@ static int reader_seek_linear(struct table_iter *ti,return err; } -static int reader_seek_indexed (struct table_iter *ti, -struct reftable_reader *r, -struct reftable_record *rec) +static int table_iter_seek_indexed (struct table_iter *ti, +struct reftable_record *rec) {struct reftable_record want_index = { .type =BLOCK_TYPE_INDEX , .u.idx = { .last_key =STRBUF_INIT }
@@ -520,7 +518,7 @@ static int reader_seek_indexed(struct table_iter *ti,* highest layer that identifies the relevant index block as well as * the record inside that block that corresponds to our wanted key. */ - err =reader_seek_linear (ti, &want_index); + err =table_iter_seek_linear (ti, &want_index);if (err <0 ) goto done;
@@ -550,7 +548,7 @@ static int reader_seek_indexed(struct table_iter *ti,if (err !=0 ) goto done; - err =reader_table_iter_at (r, ti, index_result.u.idx.offset,0 ); + err =table_iter_seek_to (ti, ti->r, index_result.u.idx.offset,0 );if (err !=0 ) goto done;
@@ -585,14 +583,14 @@ static int reader_seek_internal(struct reftable_reader *r,struct table_iter ti =TABLE_ITER_INIT , *p;int err; - err =reader_start (r, &ti,reftable_record_type (rec), !!idx); + err =table_iter_seek_start (&ti, r,reftable_record_type (rec), !!idx);if (err <0 ) goto out;if (idx) - err =reader_seek_indexed (&ti, r, rec); + err =table_iter_seek_indexed (&ti, rec);else - err =reader_seek_linear (&ti, rec); + err =table_iter_seek_linear (&ti, rec);if (err) goto out;
@@ -742,7 +740,7 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,int err; *ti = ti_empty; - err =reader_start (r, ti,BLOCK_TYPE_REF ,0 ); + err =table_iter_seek_start (ti, r,BLOCK_TYPE_REF ,0 );if (err <0 ) {reftable_free (ti);return err;
Signature · 1 line
2.45.0
PATCH 5/13 reftable/reader: inline `reader_seek_internal()`
In reply to Patrick SteinhardtWe have both reader_seek() and reader_seek_internal(), where the former function only exists so that we can exit early in case the given table has no records of the sought-after type.
Merge these two functions into one.
--- reftable/reader.c | 34 ++++++++++++---------------------- 1 file changed, 12 insertions(+), 22 deletions(-)
reftable/reader.c +12 -22
@@ -573,21 +573,25 @@ static int table_iter_seek_indexed(struct table_iter *ti,return err; } -static int reader_seek_internal (struct reftable_reader *r, -struct reftable_iterator *it, -struct reftable_record *rec) +static int reader_seek (struct reftable_reader *r,struct reftable_iterator *it, +struct reftable_record *rec) { -struct reftable_reader_offsets *offs = -reader_offsets_for (r,reftable_record_type (rec)); -uint64_t idx = offs->index_offset; +uint8_t typ =reftable_record_type (rec); +struct reftable_reader_offsets *offs =reader_offsets_for (r, typ);struct table_iter ti =TABLE_ITER_INIT , *p;int err; - err =table_iter_seek_start (&ti, r,reftable_record_type (rec), !!idx); +if (!offs->is_present) { +iterator_set_empty (it); +return 0 ; + } + + err =table_iter_seek_start (&ti, r,reftable_record_type (rec), + !!offs->index_offset);if (err <0 ) goto out; -if (idx) +if (offs->index_offset) err =table_iter_seek_indexed (&ti, rec);else err =table_iter_seek_linear (&ti, rec);
@@ -604,20 +608,6 @@ static int reader_seek_internal(struct reftable_reader *r,return err; } -static int reader_seek (struct reftable_reader *r,struct reftable_iterator *it, -struct reftable_record *rec) -{ -uint8_t typ =reftable_record_type (rec); - -struct reftable_reader_offsets *offs =reader_offsets_for (r, typ); -if (!offs->is_present) { -iterator_set_empty (it); -return 0 ; - } - -return reader_seek_internal (r, it, rec); -} -int reftable_reader_seek_ref (struct reftable_reader *r,struct reftable_iterator *it,const char *name) {
Signature · 1 line
2.45.0
PATCH 6/13 reftable/reader: set up the reader when initializing table iterator
In reply to Patrick SteinhardtAll the seeking functions accept a struct reftable_reader as input such that they can use the reader to look up the respective blocks. Refactor the code to instead set up the reader as a member of struct table_iter during initialization such that we don't have to pass the reader on every single call.
This step is required to move seeking of records into the generic struct reftable_iterator infrastructure.
--- reftable/reader.c | 39 ++++++++++++++++++++++----------------- 1 file changed, 22 insertions(+), 17 deletions(-)
reftable/reader.c +22 -17
@@ -224,8 +224,14 @@ struct table_iter {struct block_iter bi;int is_finished; }; -#define TABLE_ITER_INIT { \ - .bi = BLOCK_ITER_INIT \ + +static int table_iter_init (struct table_iter *ti,struct reftable_reader *r) +{ +struct block_iter bi =BLOCK_ITER_INIT ; +memset (ti,0 ,sizeof (*ti)); + ti->r = r; + ti->bi = bi; +return 0 ; } static int table_iter_next_in_block(struct table_iter *ti,
@@ -386,26 +392,23 @@ static void iterator_from_table_iter(struct reftable_iterator *it, it->ops = &table_iter_vtable; } -static int table_iter_seek_to (struct table_iter *ti,struct reftable_reader *r, -uint64_t off,uint8_t typ) +static int table_iter_seek_to (struct table_iter *ti,uint64_t off,uint8_t typ) {int err; - err =reader_init_block_reader (r, &ti->br, off, typ); + err =reader_init_block_reader (ti->r, &ti->br, off, typ);if (err !=0 )return err; - ti->r = r; ti->typ =block_reader_type (&ti->br); ti->block_off = off;block_iter_seek_start (&ti->bi, &ti->br);return 0 ; } -static int table_iter_seek_start (struct table_iter *ti,struct reftable_reader *r, -uint8_t typ,int index) +static int table_iter_seek_start (struct table_iter *ti,uint8_t typ,int index) { -struct reftable_reader_offsets *offs =reader_offsets_for (r, typ); +struct reftable_reader_offsets *offs =reader_offsets_for (ti->r, typ);uint64_t off = offs->offset;if (index) { off = offs->index_offset;
@@ -415,7 +418,7 @@ static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader * typ =BLOCK_TYPE_INDEX ; } -return table_iter_seek_to (ti, r, off, typ); +return table_iter_seek_to (ti, off, typ); } static int table_iter_seek_linear(struct table_iter *ti,
@@ -548,7 +551,7 @@ static int table_iter_seek_indexed(struct table_iter *ti,if (err !=0 ) goto done; - err =table_iter_seek_to (ti, ti->r, index_result.u.idx.offset,0 ); + err =table_iter_seek_to (ti, index_result.u.idx.offset,0 );if (err !=0 ) goto done;
@@ -578,7 +581,7 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it, {uint8_t typ =reftable_record_type (rec);struct reftable_reader_offsets *offs =reader_offsets_for (r, typ); -struct table_iter ti =TABLE_ITER_INIT , *p; +struct table_iter ti, *p;int err;if (!offs->is_present) {
@@ -586,7 +589,9 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,return 0 ; } - err =table_iter_seek_start (&ti, r,reftable_record_type (rec), +table_iter_init (&ti, r); + + err =table_iter_seek_start (&ti,reftable_record_type (rec), !!offs->index_offset);if (err <0 ) goto out;
@@ -722,15 +727,15 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,struct reftable_iterator *it, uint8_t *oid) { - struct table_iter ti_empty = TABLE_ITER_INIT; -struct table_iter *ti =reftable_calloc (1 ,sizeof (*ti)); + struct table_iter *ti;struct filtering_ref_iterator *filter =NULL ;struct filtering_ref_iterator empty =FILTERING_REF_ITERATOR_INIT ;int oid_len =hash_size (r->hash_id);int err; - *ti = ti_empty; - err =table_iter_seek_start (ti, r,BLOCK_TYPE_REF ,0 ); +REFTABLE_ALLOC_ARRAY (ti,1 ); +table_iter_init (ti, r); + err =table_iter_seek_start (ti,BLOCK_TYPE_REF ,0 );if (err <0 ) {reftable_free (ti);return err;
Signature · 1 line
2.45.0
PATCH 7/13 reftable/merged: split up initialization and seeking of records
In reply to Patrick SteinhardtTo initialize a struct merged_iter, we need to seek all subiterators to the wanted record and then add their results to the priority queue used to sort the records. This logic is split up across two functions, merged_table_seek_record() and merged_table_iter(). The scope of these functions is somewhat weird though, where merged_table_iter() is only responsible for adding the records of the subiterators to the priority queue.
Clarify the scope of those functions such that merged_table_iter() is only responsible for initializing the iterator's structure. Performing the subiterator seeks are now part of merged_table_seek_record().
This step is required to move seeking of records into the generic struct reftable_iterator infrastructure.
--- reftable/merged.c | 59 ++++++++++++++++++----------------------------- 1 file changed, 22 insertions(+), 37 deletions(-)
reftable/merged.c +22 -37
@@ -25,34 +25,18 @@ struct merged_subiter {struct merged_iter {struct merged_subiter *subiters;struct merged_iter_pqueue pq; -uint32_t hash_id;size_t stack_len; -uint8_t typ;int suppress_deletions;ssize_t advance_index; }; -static int merged_iter_init (struct merged_iter *mi) +static void merged_iter_init (struct merged_iter *mi, +struct reftable_merged_table *mt) { -for (size_t i =0 ; i < mi->stack_len; i++) { -struct pq_entry e = { - .index = i, - .rec = &mi->subiters[i].rec, - }; -int err; - -reftable_record_init (&mi->subiters[i].rec, mi->typ); - err =iterator_next (&mi->subiters[i].iter, - &mi->subiters[i].rec); -if (err <0 ) -return err; -if (err >0 ) -continue ; - -merged_iter_pqueue_add (&mi->pq, &e); - } - -return 0 ; +memset (mi,0 ,sizeof (*mi)); + mi->advance_index =-1 ; + mi->suppress_deletions = mt->suppress_deletions; +REFTABLE_CALLOC_ARRAY (mi->subiters, mt->stack_len); }static void merged_iter_close (void *p)
@@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,struct reftable_iterator *it, struct reftable_record *rec) { - struct merged_iter merged = { - .typ =reftable_record_type (rec), - .hash_id = mt->hash_id, - .suppress_deletions = mt->suppress_deletions, - .advance_index =-1 , - }; -struct merged_iter *p; + struct merged_iter merged, *p;int err; -REFTABLE_CALLOC_ARRAY (merged.subiters, mt->stack_len); +merged_iter_init (&merged, mt); +for (size_t i =0 ; i < mt->stack_len; i++) { +reftable_record_init (&merged.subiters[merged.stack_len].rec, +reftable_record_type (rec)); + err =reftable_table_seek_record (&mt->stack[i], &merged.subiters[merged.stack_len].iter, rec);if (err <0 ) goto out; -if (!err) - merged.stack_len++; - } +if (err >0 ) +continue ; - err =merged_iter_init (&merged); -if (err <0 ) - goto out; + err =merged_iter_advance_subiter (&merged, merged.stack_len); +if (err <0 ) + goto out; + + merged.stack_len++; + } - p =reftable_malloc (sizeof (struct merged_iter )); + p =reftable_malloc (sizeof (*p)); *p = merged;iterator_from_merged_iter (it, p); + err =0 ; out:if (err <0 )
Signature · 1 line
2.45.0
Re: [PATCH 07/13] reftable/merged: split up initialization and seeking of records
Quoted 4 lines · Patrick Steinhardt
To initialize a
struct merged_iter, we need to seek all subiterators to the wanted record and then add their results to the priority queue used to sort the records. This logic is split up across two functions,merged_table_seek_record()andmerged_table_iter(). The scope of
Did we mean merged_iter_init instead of merged_table_iter() here?
Quoted 12 lines
these functions is somewhat weird though, where
merged_table_iter()is only responsible for adding the records of the subiterators to the priority queue.Clarify the scope of those functions such that
merged_table_iter()is only responsible for initializing the iterator's structure. Performing the subiterator seeks are now part ofmerged_table_seek_record().This step is required to move seeking of records into the generic
struct reftable_iteratorinfrastructure.Signed-off-by Patrick Steinhardt <[email protected]>
...
Quoted 10 lines
reftable/merged.c +0
-6@@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,struct reftable_iterator *it, struct reftable_record *rec) { - struct merged_iter merged = { - .typ =reftable_record_type (rec), - .hash_id = mt->hash_id, - .suppress_deletions = mt->suppress_deletions, - .advance_index =-1 , - };
reftable/merged.c static int merged_table_seek_record(struct reftable_merged_table *mt, · line 240
Quoted 10 lines
reftable/merged.c +5
-2-struct merged_iter *p; +struct merged_iter merged, *p;int err; -REFTABLE_CALLOC_ARRAY (merged.subiters, mt->stack_len); +merged_iter_init (&merged, mt); +for (size_t i =0 ; i < mt->stack_len; i++) { +reftable_record_init (&merged.subiters[merged.stack_len].rec, +reftable_record_type (rec));
I find it somewhat confusing how we increment the subiterator index here. I assume this is because when a record is not found we don't want to add it to the index. Might be nice to add a comment here explaining this.
Edit: Looks like you address this in the next commit so I guess we are good :)
Quoted 32 lines
reftable/merged.c +11
-7+ err =reftable_table_seek_record (&mt->stack[i], &merged.subiters[merged.stack_len].iter, rec);if (err <0 ) goto out; -if (!err) - merged.stack_len++; - } +if (err >0 ) +continue ; - err =merged_iter_init (&merged); -if (err <0 ) - goto out; + err =merged_iter_advance_subiter (&merged, merged.stack_len); +if (err <0 ) + goto out; + + merged.stack_len++; + } - p =reftable_malloc (sizeof (struct merged_iter )); + p =reftable_malloc (sizeof (*p)); *p = merged;iterator_from_merged_iter (it, p); + err =0 ; out:if (err <0 )Signature · 1 line
2.45.0
Re: [PATCH 07/13] reftable/merged: split up initialization and seeking of records
Quoted 7 lines · Justin Tobler
Quoted 4 lines · Patrick Steinhardt
To initialize a
struct merged_iter, we need to seek all subiterators to the wanted record and then add their results to the priority queue used to sort the records. This logic is split up across two functions,merged_table_seek_record()andmerged_table_iter(). The scope ofDid we mean
merged_iter_initinstead ofmerged_table_iter()here?
Indeed, good catch.
Quoted 26 lines
Quoted 10 lines
reftable/merged.c +0
-6@@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,struct reftable_iterator *it, struct reftable_record *rec) { - struct merged_iter merged = { - .typ =reftable_record_type (rec), - .hash_id = mt->hash_id, - .suppress_deletions = mt->suppress_deletions, - .advance_index =-1 , - };reftable/merged.c static int merged_table_seek_record(struct reftable_merged_table *mt, · line 240
Quoted 10 lines
reftable/merged.c +5
-2-struct merged_iter *p; +struct merged_iter merged, *p;int err; -REFTABLE_CALLOC_ARRAY (merged.subiters, mt->stack_len); +merged_iter_init (&merged, mt); +for (size_t i =0 ; i < mt->stack_len; i++) { +reftable_record_init (&merged.subiters[merged.stack_len].rec, +reftable_record_type (rec));I find it somewhat confusing how we increment the subiterator index here. I assume this is because when a record is not found we don't want to add it to the index. Might be nice to add a comment here explaining this.
Quoted 2 lines
Edit: Looks like you address this in the next commit so I guess we are good :)
Seconded. And yes, as you noticed, this is one of the reasons why I change this in the next patch.
Patrick
PATCH 8/13 reftable/merged: simplify indices for subiterators
In reply to Patrick SteinhardtWhen seeking on a merged table, we perform the seek for each of the subiterators. If the subiterator hasa the desired record we add it to the priority queue, otherwise we skip it and don't add it to the stack of subiterators hosted by the merged table.
The consequence of this is that the index of the subiterator in the merged table does not necessarily correspond to the index of it in the merged iterator. Next to being potentially confusing, it also means that we won't easily be able to re-seek the merged iterator because we have no clear connection between both of the data structures.
Refactor the code so that the index stays the same in both structures.
--- reftable/merged.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
reftable/merged.c +4 -5
@@ -37,6 +37,7 @@ static void merged_iter_init(struct merged_iter *mi, mi->advance_index =-1 ; mi->suppress_deletions = mt->suppress_deletions;REFTABLE_CALLOC_ARRAY (mi->subiters, mt->stack_len); + mi->stack_len = mt->stack_len; }static void merged_iter_close (void *p)
@@ -236,21 +237,19 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,merged_iter_init (&merged, mt);for (size_t i =0 ; i < mt->stack_len; i++) { -reftable_record_init (&merged.subiters[merged.stack_len].rec, +reftable_record_init (&merged.subiters[i].rec,reftable_record_type (rec)); err =reftable_table_seek_record (&mt->stack[i], - &merged.subiters[merged.stack_len].iter, rec); + &merged.subiters[i].iter, rec);if (err <0 ) goto out;if (err >0 )continue ; - err =merged_iter_advance_subiter (&merged, merged.stack_len); + err =merged_iter_advance_subiter (&merged, i);if (err <0 ) goto out; - - merged.stack_len++; } p =reftable_malloc (sizeof (*p));
Signature · 1 line
2.45.0
Re: [PATCH 08/13] reftable/merged: simplify indices for subiterators
Quoted 2 lines · Patrick Steinhardt
When seeking on a merged table, we perform the seek for each of the subiterators. If the subiterator hasa the desired record we add it to
s/hasa/has/
Quoted 8 lines
the priority queue, otherwise we skip it and don't add it to the stack of subiterators hosted by the merged table.
The consequence of this is that the index of the subiterator in the merged table does not necessarily correspond to the index of it in the merged iterator. Next to being potentially confusing, it also means that we won't easily be able to re-seek the merged iterator because we have no clear connection between both of the data structures.
Ah, I also found this a bit confusing. I think this is a good change.
Quoted 2 lines
Refactor the code so that the index stays the same in both structures.
Was there any advantage to not adding subiterators to the stack originally? It looks like it adding them doesn't affect anything.
-Justin
Re: [PATCH 08/13] reftable/merged: simplify indices for subiterators
Quoted 5 lines · Justin Tobler
Quoted 2 lines · Patrick Steinhardt
When seeking on a merged table, we perform the seek for each of the subiterators. If the subiterator hasa the desired record we add it to
s/hasa/has/
Fixed.
Quoted 9 lines
Quoted 8 lines
the priority queue, otherwise we skip it and don't add it to the stack of subiterators hosted by the merged table.
The consequence of this is that the index of the subiterator in the merged table does not necessarily correspond to the index of it in the merged iterator. Next to being potentially confusing, it also means that we won't easily be able to re-seek the merged iterator because we have no clear connection between both of the data structures.
Quoted 6 lines
Ah, I also found this a bit confusing. I think this is a good change.
Quoted 2 lines
Refactor the code so that the index stays the same in both structures.
Was there any advantage to not adding subiterators to the stack originally? It looks like it adding them doesn't affect anything.
Not to the best of my knowledge, no.
Patrick
PATCH 9/13 reftable/generic: move seeking of records into the iterator
In reply to Patrick SteinhardtReftable iterators are created by seeking on the parent structure of a corresponding record. For example, to create an iterator for the merged table you would call reftable_merged_table_seek_ref(). Most notably, it is not posible to create an iterator and then seek it afterwards.
While this may be a bit easier to reason about, it comes with two significant downsides. The first downside is that the logic to find records is split up between the parent data structure and the iterator itself. Conceptually, it is more straight forward if all that logic was contained in a single place, which should be the iterator.
The second and more significant downside is that it is impossible to reuse iterators for multiple seeks. Whenever you want to look up a record, you need to re-create the whole infrastructure again, which is quite a waste of time. Furthermore, it is impossible to for example optimize seeks, for example when seeking the same record multiple times.
To address this, we essentially split up the concerns properly such that the parent data structure is responsible for setting up the iterator via a new init_iter() callback, whereas the iterator handles seeks via a new seek() callback. This will eventually allow us to call seek() on the iterator multiple times, where every iterator can potentially optimize for certain cases.
Note that at this point in time we are not yet ready to reuse the iterators. This will be left for a future patch series.
--- reftable/generic.c | 47 +++++++++++++---- reftable/generic.h | 9 +++- reftable/iter.c | 15 ++++++ reftable/merged.c | 97 +++++++++++++++++----------------- reftable/reader.c | 126 +++++++++++++++++++++++++-------------------- 5 files changed, 177 insertions(+), 117 deletions(-)
reftable/generic.c +36 -11
@@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at#include "reftable-iterator.h" #include "reftable-generic.h" +void table_init_iter (struct reftable_table *tab, +struct reftable_iterator *it, +uint8_t typ) +{ + + tab->ops->init_iter (tab->table_arg, it, typ); +} +int reftable_table_seek_ref (struct reftable_table *tab,struct reftable_iterator *it,const char *name) { -struct reftable_record rec = { .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - } }; -return tab->ops->seek_record (tab->table_arg, it, &rec); +struct reftable_record want = { + .type =BLOCK_TYPE_REF , + .u.ref = { + .refname = (char *)name, + }, + }; +table_init_iter (tab, it,BLOCK_TYPE_REF ); +return it->ops->seek (it->iter_arg, &want); }int reftable_table_seek_log (struct reftable_table *tab,struct reftable_iterator *it,const char *name) { -struct reftable_record rec = { .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = ~((uint64_t )0 ), - } }; -return tab->ops->seek_record (tab->table_arg, it, &rec); +struct reftable_record want = { + .type =BLOCK_TYPE_LOG , + .u.log = { + .refname = (char *)name, + .update_index = ~((uint64_t )0 ), + }, + }; +table_init_iter (tab, it,BLOCK_TYPE_LOG ); +return it->ops->seek (it->iter_arg, &want); } int reftable_table_read_ref(struct reftable_table *tab, const char *name,
@@ -152,11 +166,21 @@ int reftable_iterator_next_log(struct reftable_iterator *it,return err; } +int iterator_seek (struct reftable_iterator *it,struct reftable_record *want) +{ +return it->ops->seek (it->iter_arg, want); +} +int iterator_next (struct reftable_iterator *it,struct reftable_record *rec) {return it->ops->next (it->iter_arg, rec); } +static int empty_iterator_seek (void *arg,struct reftable_record *want) +{ +return 0 ; +} +static int empty_iterator_next (void *arg,struct reftable_record *rec) {return 1 ;
@@ -167,6 +191,7 @@ static void empty_iterator_close(void *arg) }static struct reftable_iterator_vtable empty_vtable = { + .seek = &empty_iterator_seek, .next = &empty_iterator_next, .close = &empty_iterator_close, };
reftable/generic.h +7 -2
@@ -14,19 +14,24 @@ license that can be found in the LICENSE file or at/* generic interface to reftables */ struct reftable_table_vtable { -int (*seek_record)(void *tab,struct reftable_iterator *it, -struct reftable_record *); +void (*init_iter)(void *tab,struct reftable_iterator *it,uint8_t typ);uint32_t (*hash_id)(void *tab);uint64_t (*min_update_index)(void *tab);uint64_t (*max_update_index)(void *tab); }; +void table_init_iter (struct reftable_table *tab, +struct reftable_iterator *it, +uint8_t typ); +struct reftable_iterator_vtable { +int (*seek)(void *iter_arg,struct reftable_record *want);int (*next)(void *iter_arg,struct reftable_record *rec);void (*close)(void *iter_arg); };void iterator_set_empty (struct reftable_iterator *it); +int iterator_seek (struct reftable_iterator *it,struct reftable_record *want);int iterator_next (struct reftable_iterator *it,struct reftable_record *rec);#endif
reftable/iter.c +15 -0
@@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)reftable_iterator_destroy (&fri->it); } +static int filtering_ref_iterator_seek (void *iter_arg, +struct reftable_record *want) +{ +struct filtering_ref_iterator *fri = iter_arg; +return iterator_seek (&fri->it, want); +} +static int filtering_ref_iterator_next (void *iter_arg,struct reftable_record *rec) {
@@ -73,6 +80,7 @@ static int filtering_ref_iterator_next(void *iter_arg, }static struct reftable_iterator_vtable filtering_ref_iterator_vtable = { + .seek = &filtering_ref_iterator_seek, .next = &filtering_ref_iterator_next, .close = &filtering_ref_iterator_close, };
@@ -119,6 +127,12 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)return 0 ; } +static int indexed_table_ref_iter_seek (void *p,struct reftable_record *want) +{ +BUG ("seeking indexed table is not supported" ); +return -1 ; +} +static int indexed_table_ref_iter_next (void *p,struct reftable_record *rec) {struct indexed_table_ref_iter *it = p;
@@ -175,6 +189,7 @@ int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest, }static struct reftable_iterator_vtable indexed_table_ref_iter_vtable = { + .seek = &indexed_table_ref_iter_seek, .next = &indexed_table_ref_iter_next, .close = &indexed_table_ref_iter_close, };
reftable/merged.c +49 -48
158 lines not on this page · raw message
reftable/reader.c +70 -56
185 lines not on this page · raw message
Signature · 1 line
2.45.0
Re: [PATCH 09/13] reftable/generic: move seeking of records into the iterator
Quoted 11 lines · Patrick Steinhardt
Reftable iterators are created by seeking on the parent structure of a corresponding record. For example, to create an iterator for the merged table you would call
reftable_merged_table_seek_ref(). Most notably, it is not posible to create an iterator and then seek it afterwards.While this may be a bit easier to reason about, it comes with two significant downsides. The first downside is that the logic to find records is split up between the parent data structure and the iterator itself. Conceptually, it is more straight forward if all that logic was contained in a single place, which should be the iterator.
Quoted 5 lines
The second and more significant downside is that it is impossible to reuse iterators for multiple seeks. Whenever you want to look up a record, you need to re-create the whole infrastructure again, which is quite a waste of time. Furthermore, it is impossible to for example optimize seeks, for example when seeking the same record multiple times.
The last setence could use some rewording.
"Furthermore, it is impossible to optimize seeks, such as when seeking the same record multiple times."
Quoted 25 lines
To address this, we essentially split up the concerns properly such that the parent data structure is responsible for setting up the iterator via a new
init_iter()callback, whereas the iterator handles seeks via a newseek()callback. This will eventually allow us to callseek()on the iterator multiple times, where every iterator can potentially optimize for certain cases.Note that at this point in time we are not yet ready to reuse the iterators. This will be left for a future patch series.
Signed-off-by Patrick Steinhardt <[email protected]>--- reftable/generic.c | 47 +++++++++++++---- reftable/generic.h | 9 +++- reftable/iter.c | 15 ++++++ reftable/merged.c | 97 +++++++++++++++++----------------- reftable/reader.c | 126 +++++++++++++++++++++++++-------------------- 5 files changed, 177 insertions(+), 117 deletions(-)reftable/generic.c +0
-0
reftable/generic.c license that can be found in the LICENSE file or at · line 15
Quoted 4 lines
reftable/generic.c +1
-0@@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at#include "reftable-iterator.h" #include "reftable-generic.h" +void table_init_iter(struct reftable_table *tab,
The following table related functions are prefixed with reftable_. Do we want to do the same here?
Quoted 46 lines
reftable/generic.c +24
-11+ struct reftable_iterator *it, + uint8_t typ) +{ + + tab->ops->init_iter (tab->table_arg, it, typ); +} +int reftable_table_seek_ref (struct reftable_table *tab,struct reftable_iterator *it,const char *name) { -struct reftable_record rec = { .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - } }; -return tab->ops->seek_record (tab->table_arg, it, &rec); +struct reftable_record want = { + .type =BLOCK_TYPE_REF , + .u.ref = { + .refname = (char *)name, + }, + }; +table_init_iter (tab, it,BLOCK_TYPE_REF ); +return it->ops->seek (it->iter_arg, &want); }int reftable_table_seek_log (struct reftable_table *tab,struct reftable_iterator *it,const char *name) { -struct reftable_record rec = { .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = ~((uint64_t )0 ), - } }; -return tab->ops->seek_record (tab->table_arg, it, &rec); +struct reftable_record want = { + .type =BLOCK_TYPE_LOG , + .u.log = { + .refname = (char *)name, + .update_index = ~((uint64_t )0 ), + }, + }; +table_init_iter (tab, it,BLOCK_TYPE_LOG ); +return it->ops->seek (it->iter_arg, &want); } int reftable_table_read_ref(struct reftable_table *tab, const char *name,
...
reftable/generic.c static void filtering_ref_iterator_close(void *iter_arg) · line 31
Quoted 10 lines
reftable/generic.c +6
-0@@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)reftable_iterator_destroy (&fri->it); } +static int filtering_ref_iterator_seek (void *iter_arg, +struct reftable_record *want) +{ +struct filtering_ref_iterator *fri = iter_arg; +return iterator_seek (&fri->it, want); +}
I've found the filtering_ref_iterator_seek() here to be a little confusing. At first, I assumed that the filtering_ref_iterator would have referenced filtering_ref_iterator_vtable thus resulting in a cycle, but on closer inspection this does not seem to be the case and is in face always set to some other iterator operation.
Am I understanding this correctly?
-Justin
Re: [PATCH 09/13] reftable/generic: move seeking of records into the iterator
Quoted 18 lines · Justin Tobler
Quoted 11 lines · Patrick Steinhardt
Reftable iterators are created by seeking on the parent structure of a corresponding record. For example, to create an iterator for the merged table you would call
reftable_merged_table_seek_ref(). Most notably, it is not posible to create an iterator and then seek it afterwards.While this may be a bit easier to reason about, it comes with two significant downsides. The first downside is that the logic to find records is split up between the parent data structure and the iterator itself. Conceptually, it is more straight forward if all that logic was contained in a single place, which should be the iterator.
Quoted 5 lines
The second and more significant downside is that it is impossible to reuse iterators for multiple seeks. Whenever you want to look up a record, you need to re-create the whole infrastructure again, which is quite a waste of time. Furthermore, it is impossible to for example optimize seeks, for example when seeking the same record multiple times.
Quoted 4 lines
The last setence could use some rewording.
"Furthermore, it is impossible to optimize seeks, such as when seeking the same record multiple times."
Done.
[snip]
Quoted 8 lines
Quoted 8 lines
reftable/generic.c +0
-0@@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at#include "reftable-iterator.h" #include "reftable-generic.h"
Quoted 4 lines
reftable/generic.c license that can be found in the LICENSE file or at · line 15
Quoted 1 line
reftable/generic.c +1
-0+void table_init_iter(struct reftable_table *tab,The following table related functions are prefixed with
reftable_. Do we want to do the same here?
Functions with the reftable_ prefix are supposed to be public, whereas functions without them are private. So this is intentionally missing the prefix.
[snip]
Quoted 17 lines
reftable/generic.c static void filtering_ref_iterator_close(void *iter_arg) · line 31
Quoted 10 lines
reftable/generic.c +6
-0@@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)reftable_iterator_destroy (&fri->it); } +static int filtering_ref_iterator_seek (void *iter_arg, +struct reftable_record *want) +{ +struct filtering_ref_iterator *fri = iter_arg; +return iterator_seek (&fri->it, want); +}I've found the
filtering_ref_iterator_seek()here to be a little confusing. At first, I assumed that thefiltering_ref_iteratorwould have referencedfiltering_ref_iterator_vtablethus resulting in a cycle, but on closer inspection this does not seem to be the case and is in face always set to some other iterator operation.
Quoted 1 line
Am I understanding this correctly?
Yes. The filtering ref iterator wraps a _different_ iterator, which is fri->it in the above case, and only returns a subset of the records of that wrapped iterator. So we eventually end up calling the callbacks of the wrapped iterator, which are likely not a filtering ref iterator themselves (even though that would in theory be possible).
Patrick
PATCH 10/13 reftable/generic: adapt interface to allow reuse of iterators
In reply to Patrick SteinhardtRefactor the interfaces exposed by struct reftable_table and struct reftable_iterator such that they support iterator reuse. This is done by separating initialization of the iterator and seeking on it.
--- reftable/generic.c | 53 ++++++++++++++++++++++++++---------- reftable/iter.c | 8 +++--- reftable/reftable-generic.h | 8 +++--- reftable/reftable-iterator.h | 21 ++++++++++++++ 4 files changed, 68 insertions(+), 22 deletions(-)
reftable/generic.c +39 -14
@@ -20,8 +20,20 @@ void table_init_iter(struct reftable_table *tab, tab->ops->init_iter (tab->table_arg, it, typ); } -int reftable_table_seek_ref (struct reftable_table *tab, -struct reftable_iterator *it,const char *name) +void reftable_table_init_ref_iter (struct reftable_table *tab, +struct reftable_iterator *it) +{ +table_init_iter (tab, it,BLOCK_TYPE_REF ); +} + +void reftable_table_init_log_iter (struct reftable_table *tab, +struct reftable_iterator *it) +{ +table_init_iter (tab, it,BLOCK_TYPE_LOG ); +} + +int reftable_iterator_seek_ref (struct reftable_iterator *it, +const char *name) {struct reftable_record want = { .type =BLOCK_TYPE_REF ,
@@ -29,29 +41,37 @@ int reftable_table_seek_ref(struct reftable_table *tab, .refname = (char *)name, }, }; -table_init_iter (tab, it,BLOCK_TYPE_REF );return it->ops->seek (it->iter_arg, &want); } -int reftable_table_seek_log (struct reftable_table *tab, -struct reftable_iterator *it,const char *name) +int reftable_iterator_seek_log_at (struct reftable_iterator *it, +const char *name,uint64_t update_index) {struct reftable_record want = { .type =BLOCK_TYPE_LOG , .u.log = { .refname = (char *)name, - .update_index = ~((uint64_t )0 ), + .update_index = update_index, }, }; -table_init_iter (tab, it,BLOCK_TYPE_LOG );return it->ops->seek (it->iter_arg, &want); } +int reftable_iterator_seek_log (struct reftable_iterator *it, +const char *name) +{ +return reftable_iterator_seek_log_at (it, name, ~((uint64_t )0 )); +} +int reftable_table_read_ref (struct reftable_table *tab,const char *name,struct reftable_ref_record *ref) {struct reftable_iterator it = {NULL }; -int err =reftable_table_seek_ref (tab, &it, name); +int err; + +reftable_table_init_ref_iter (tab, &it); + + err =reftable_iterator_seek_ref (&it, name);if (err) goto done;
@@ -76,10 +96,13 @@ int reftable_table_print(struct reftable_table *tab) {struct reftable_ref_record ref = {NULL };struct reftable_log_record log = {NULL };uint32_t hash_id =reftable_table_hash_id (tab); -int err =reftable_table_seek_ref (tab, &it,"" ); -if (err <0 ) { +int err; + +reftable_table_init_ref_iter (tab, &it); + + err =reftable_iterator_seek_ref (&it,"" ); +if (err <0 )return err; - }while (1 ) { err =reftable_iterator_next_ref (&it, &ref);
@@ -94,10 +117,12 @@ int reftable_table_print(struct reftable_table *tab) {reftable_iterator_destroy (&it);reftable_ref_record_release (&ref); - err =reftable_table_seek_log (tab, &it,"" ); -if (err <0 ) { +reftable_table_init_log_iter (tab, &it); + + err =reftable_iterator_seek_log (&it,"" ); +if (err <0 )return err; - } +while (1 ) { err =reftable_iterator_next_log (&it, &log);if (err >0 ) {
reftable/iter.c +4 -4
@@ -45,11 +45,11 @@ static int filtering_ref_iterator_next(void *iter_arg,if (fri->double_check) {struct reftable_iterator it = {NULL }; - err =reftable_table_seek_ref (&fri->tab, &it, - ref->refname); -if (err ==0 ) { +reftable_table_init_ref_iter (&fri->tab, &it); + + err =reftable_iterator_seek_ref (&it, ref->refname); +if (err ==0 ) err =reftable_iterator_next_ref (&it, ref); - }reftable_iterator_destroy (&it);
reftable/reftable-generic.h +4 -4
@@ -21,11 +21,11 @@ struct reftable_table {void *table_arg; }; -int reftable_table_seek_log (struct reftable_table *tab, -struct reftable_iterator *it,const char *name); +void reftable_table_init_ref_iter (struct reftable_table *tab, +struct reftable_iterator *it); -int reftable_table_seek_ref (struct reftable_table *tab, -struct reftable_iterator *it,const char *name); +void reftable_table_init_log_iter (struct reftable_table *tab, +struct reftable_iterator *it);/* returns the hash ID from a generic reftable_table */ uint32_t reftable_table_hash_id (struct reftable_table *tab);
reftable/reftable-iterator.h +21 -0
@@ -21,12 +21,33 @@ struct reftable_iterator {void *iter_arg; }; +/* +* Position the iterator at the ref record with given name such that the next +* call to `next_ref()` would yield the record. +*/ +int reftable_iterator_seek_ref (struct reftable_iterator *it, +const char *name); +/* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0: * end of iteration. */ int reftable_iterator_next_ref (struct reftable_iterator *it,struct reftable_ref_record *ref); +/* +* Position the iterator at the log record with given name and update index +* such that the next call to `next_log()` would yield the record. +*/ +int reftable_iterator_seek_log_at (struct reftable_iterator *it, +const char *name,uint64_t update_index); + +/* +* Position the iterator at the newest log record with given name such that the +* next call to `next_log()` would yield the record. +*/ +int reftable_iterator_seek_log (struct reftable_iterator *it, +const char *name); +/* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0: * end of iteration. */
Signature · 1 line
2.45.0
PATCH 11/13 reftable/reader: adapt interface to allow reuse of iterators
In reply to Patrick SteinhardtRefactor the interfaces exposed by struct reftable_reader and struct table_iterator such that they support iterator reuse. This is done by separating initialization of the iterator and seeking on it.
--- reftable/reader.c | 31 ++++---------------------- reftable/readwrite_test.c | 35 +++++++++++++++++++---------- reftable/reftable-reader.h | 45 ++++++-------------------------------- 3 files changed, 35 insertions(+), 76 deletions(-)
reftable/reader.c +4 -27
@@ -621,39 +621,16 @@ static void reader_init_iter(struct reftable_reader *r, } } -int reftable_reader_seek_ref (struct reftable_reader *r, -struct reftable_iterator *it,const char *name) +void reftable_reader_init_ref_iterator (struct reftable_reader *r, +struct reftable_iterator *it) { -struct reftable_record rec = { - .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - }, - };reader_init_iter (r, it,BLOCK_TYPE_REF ); -return iterator_seek (it, &rec); } -int reftable_reader_seek_log_at (struct reftable_reader *r, -struct reftable_iterator *it,const char *name, -uint64_t update_index) +void reftable_reader_init_log_iterator (struct reftable_reader *r, +struct reftable_iterator *it) { -struct reftable_record rec = { - .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = update_index, - }, - };reader_init_iter (r, it,BLOCK_TYPE_LOG ); -return iterator_seek (it, &rec); -} - -int reftable_reader_seek_log (struct reftable_reader *r, -struct reftable_iterator *it,const char *name) -{ -uint64_t max = ~((uint64_t )0 ); -return reftable_reader_seek_log_at (r, it, name, max); }void reader_close (struct reftable_reader *r)
reftable/readwrite_test.c +24 -11
@@ -239,7 +239,9 @@ static void test_log_write_read(void) err =init_reader (&rd, &source,"file.log" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (&rd, &it, names[N -1 ]); +reftable_reader_init_ref_iterator (&rd, &it); + + err =reftable_iterator_seek_ref (&it, names[N -1 ]);EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &ref);
@@ -252,7 +254,9 @@ static void test_log_write_read(void)reftable_iterator_destroy (&it);reftable_ref_record_release (&ref); - err =reftable_reader_seek_log (&rd, &it,"" ); +reftable_reader_init_log_iterator (&rd, &it); + + err =reftable_iterator_seek_log (&it,"" );EXPECT_ERR (err); i =0 ;
@@ -330,7 +334,8 @@ static void test_log_zlib_corruption(void) err =init_reader (&rd, &source,"file.log" );EXPECT_ERR (err); - err =reftable_reader_seek_log (&rd, &it,"refname" ); +reftable_reader_init_log_iterator (&rd, &it); + err =reftable_iterator_seek_log (&it,"refname" );EXPECT (err ==REFTABLE_ZLIB_ERROR );reftable_iterator_destroy (&it);
@@ -358,7 +363,8 @@ static void test_table_read_write_sequential(void) err =init_reader (&rd, &source,"file.ref" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (&rd, &it,"" ); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it,"" );EXPECT_ERR (err);while (1 ) {
@@ -412,7 +418,8 @@ static void test_table_read_api(void) err =init_reader (&rd, &source,"file.ref" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (&rd, &it, names[0 ]); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it, names[0 ]);EXPECT_ERR (err); err =reftable_iterator_next_log (&it, &log);
@@ -457,7 +464,8 @@ static void test_table_read_write_seek(int index, int hash_id) }for (i =1 ; i <N ; i++) { -int err =reftable_reader_seek_ref (&rd, &it, names[i]); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it, names[i]);EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &ref);EXPECT_ERR (err);
@@ -472,7 +480,8 @@ static void test_table_read_write_seek(int index, int hash_id)strbuf_addstr (&pastLast, names[N -1 ]);strbuf_addstr (&pastLast,"/" ); - err =reftable_reader_seek_ref (&rd, &it, pastLast.buf); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it, pastLast.buf);if (err ==0 ) {struct reftable_ref_record ref = {NULL };int err =reftable_iterator_next_ref (&it, &ref);
@@ -576,7 +585,8 @@ static void test_table_refs_for(int indexed) rd.obj_offsets.is_present =0 ; } - err =reftable_reader_seek_ref (&rd, &it,"" ); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it,"" );EXPECT_ERR (err);reftable_iterator_destroy (&it);
@@ -639,7 +649,8 @@ static void test_write_empty_table(void) err =reftable_new_reader (&rd, &source,"filename" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (rd, &it,"" ); +reftable_reader_init_ref_iterator (rd, &it); + err =reftable_iterator_seek_ref (&it,"" );EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &rec);
@@ -846,7 +857,8 @@ static void test_write_multiple_indices(void)* Seeking the log uses the log index now. In case there is any * confusion regarding indices we would notice here. */ - err =reftable_reader_seek_log (reader, &it,"" ); +reftable_reader_init_log_iterator (reader, &it); + err =reftable_iterator_seek_log (&it,"" );EXPECT_ERR (err);reftable_iterator_destroy (&it);
@@ -901,7 +913,8 @@ static void test_write_multi_level_index(void)/* * Seeking the last ref should work as expected. */ - err =reftable_reader_seek_ref (reader, &it,"refs/heads/199" ); +reftable_reader_init_ref_iterator (reader, &it); + err =reftable_iterator_seek_ref (&it,"refs/heads/199" );EXPECT_ERR (err);reftable_iterator_destroy (&it);
reftable/reftable-reader.h +7 -38
55 lines not on this page · raw message
Signature · 1 line
2.45.0
Re: [PATCH 11/13] reftable/reader: adapt interface to allow reuse of iterators
reftable/reftable-reader.h struct reftable_table; · line 43
Quoted 5 lines · Patrick Steinhardt
reftable/reftable-reader.h +5
-0+/* Initialize a reftable iterator for reading refs. */ +void reftable_reader_init_ref_iterator (struct reftable_reader *r, +struct reftable_iterator *it); + +/* Initialize a reftable iterator for reading refs. */
I think you meant to say "reading logs" here.
Quoted 3 lines
reftable/reftable-reader.h +2
-0+void reftable_reader_init_log_iterator (struct reftable_reader *r, +struct reftable_iterator *it);
Re: [PATCH 11/13] reftable/reader: adapt interface to allow reuse of iterators
Quoted 9 lines · Justin Tobler
reftable/reftable-reader.h struct reftable_table; · line 43
Quoted 5 lines · Patrick Steinhardt
reftable/reftable-reader.h +5
-0+/* Initialize a reftable iterator for reading refs. */ +void reftable_reader_init_ref_iterator (struct reftable_reader *r, +struct reftable_iterator *it); + +/* Initialize a reftable iterator for reading refs. */ I think you meant to say "reading logs" here.
Indeed, thanks!
Patrick
Quoted 3 lines
Quoted 3 lines
reftable/reftable-reader.h +2
-0+void reftable_reader_init_log_iterator (struct reftable_reader *r, +struct reftable_iterator *it);
PATCH 12/13 reftable/stack: provide convenience functions to create iterators
In reply to Patrick SteinhardtThere exist a bunch of call sites in the reftable backend that want to create iterators for a reftable stack. This is rather convoluted right now, where you always have to go via the merged table. And it is about to become even more convoluted when we split up iterator initialization and seeking in the next commit.
Introduce convenience functions that allow the caller to create an iterator from a reftable stack directly without going through the merged table. Adapt callers accordingly.
--- refs/reftable-backend.c | 48 +++++++++++++++++---------------------- reftable/merged.c | 6 ++--- reftable/merged.h | 6 +++++ reftable/reftable-stack.h | 18 +++++++++++++++ reftable/stack.c | 15 ++++++++++++ 5 files changed, 63 insertions(+), 30 deletions(-)
refs/reftable-backend.c +21 -27
@@ -15,7 +15,6 @@#include "../reftable/reftable-record.h" #include "../reftable/reftable-error.h" #include "../reftable/reftable-iterator.h" -#include "../reftable/reftable-merged.h" #include "../setup.h" #include "../strmap.h" #include "parse.h"
@@ -462,7 +461,6 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ const char *prefix, int flags) { -struct reftable_merged_table *merged_table;struct reftable_ref_iterator *iter;int ret;
@@ -482,9 +480,8 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_if (ret) goto done; - merged_table =reftable_stack_merged_table (stack); - - ret =reftable_merged_table_seek_ref (merged_table, &iter->iter, prefix); +reftable_stack_init_ref_iterator (stack, &iter->iter); + ret =reftable_iterator_seek_ref (&iter->iter, prefix);if (ret) goto done;
@@ -1015,8 +1012,6 @@ static int transaction_update_cmp(const void *a, const void *b)static int write_transaction_table (struct reftable_writer *writer,void *cb_data) {struct write_transaction_table_arg *arg = cb_data; -struct reftable_merged_table *mt = -reftable_stack_merged_table (arg->stack);uint64_t ts =reftable_stack_next_update_index (arg->stack);struct reftable_log_record *logs =NULL ;struct ident_split committer_ident = {0 };
@@ -1051,6 +1046,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_datastruct reftable_log_record log = {0 };struct reftable_iterator it = {0 }; +reftable_stack_init_log_iterator (arg->stack, &it); +/* * When deleting refs we also delete all reflog entries * with them. While it is not strictly required to
@@ -1060,7 +1057,7 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data* Unfortunately, we have no better way than to delete * all reflog entries one by one. */ - ret =reftable_merged_table_seek_log (mt, &it, u->refname); + ret =reftable_iterator_seek_log (&it, u->refname);while (ret ==0 ) {struct reftable_log_record *tombstone;
@@ -1354,7 +1351,6 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data) {struct write_copy_arg *arg = cb_data;uint64_t deletion_ts, creation_ts; -struct reftable_merged_table *mt =reftable_stack_merged_table (arg->stack);struct reftable_ref_record old_ref = {0 }, refs[2 ] = {0 };struct reftable_log_record old_log = {0 }, *logs =NULL ;struct reftable_iterator it = {0 };
@@ -1488,7 +1484,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)* copy over all log entries from the old reflog. Last but not least, * when renaming we also have to delete all the old reflog entries. */ - ret =reftable_merged_table_seek_log (mt, &it, arg->oldname); +reftable_stack_init_log_iterator (arg->stack, &it); + ret =reftable_iterator_seek_log (&it, arg->oldname);if (ret <0 ) goto done;
@@ -1694,7 +1691,6 @@ static struct ref_iterator_vtable reftable_reflog_iterator_vtable = {static struct reftable_reflog_iterator *reflog_iterator_for_stack (struct reftable_ref_store *refs,struct reftable_stack *stack) { -struct reftable_merged_table *merged_table;struct reftable_reflog_iterator *iter;int ret;
@@ -1711,9 +1707,8 @@ static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftablif (ret <0 ) goto done; - merged_table =reftable_stack_merged_table (stack); - - ret =reftable_merged_table_seek_log (merged_table, &iter->iter,"" ); +reftable_stack_init_log_iterator (stack, &iter->iter); + ret =reftable_iterator_seek_log (&iter->iter,"" );if (ret <0 ) goto done;
@@ -1771,7 +1766,6 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_READ ,"for_each_reflog_ent_reverse" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =NULL ;struct reftable_log_record log = {0 };struct reftable_iterator it = {0 };int ret;
@@ -1779,8 +1773,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,if (refs->err <0 )return refs->err; - mt =reftable_stack_merged_table (stack); - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + ret =reftable_iterator_seek_log (&it, refname);while (!ret) { ret =reftable_iterator_next_log (&it, &log);if (ret <0 )
@@ -1808,7 +1802,6 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_READ ,"for_each_reflog_ent" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =NULL ;struct reftable_log_record *logs =NULL ;struct reftable_iterator it = {0 };size_t logs_alloc =0 , logs_nr =0 , i;
@@ -1817,8 +1810,8 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,if (refs->err <0 )return refs->err; - mt =reftable_stack_merged_table (stack); - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + ret =reftable_iterator_seek_log (&it, refname);while (!ret) {struct reftable_log_record log = {0 };
@@ -1855,7 +1848,6 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_READ ,"reflog_exists" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =reftable_stack_merged_table (stack);struct reftable_log_record log = {0 };struct reftable_iterator it = {0 };int ret;
@@ -1868,7 +1860,8 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,if (ret <0 ) goto done; - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + ret =reftable_iterator_seek_log (&it, refname);if (ret <0 ) goto done;
@@ -1966,8 +1959,6 @@ struct write_reflog_delete_arg {static int write_reflog_delete_table (struct reftable_writer *writer,void *cb_data) {struct write_reflog_delete_arg *arg = cb_data; -struct reftable_merged_table *mt = -reftable_stack_merged_table (arg->stack);struct reftable_log_record log = {0 }, tombstone = {0 };struct reftable_iterator it = {0 };uint64_t ts =reftable_stack_next_update_index (arg->stack);
@@ -1975,12 +1966,14 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_dareftable_writer_set_limits (writer, ts, ts); +reftable_stack_init_log_iterator (arg->stack, &it); +/* * In order to delete a table we need to delete all reflog entries one * by one. This is inefficient, but the reftable format does not have a * better marker right now. */ - ret =reftable_merged_table_seek_log (mt, &it, arg->refname); + ret =reftable_iterator_seek_log (&it, arg->refname);while (ret ==0 ) { ret =reftable_iterator_next_log (&it, &log);if (ret <0 )
@@ -2116,7 +2109,6 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_WRITE ,"reflog_expire" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =reftable_stack_merged_table (stack);struct reftable_log_record *logs =NULL ;struct reftable_log_record *rewritten =NULL ;struct reftable_ref_record ref_record = {0 };
@@ -2135,7 +2127,9 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,if (ret <0 ) goto done; - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + + ret =reftable_iterator_seek_log (&it, refname);if (ret <0 ) goto done;
reftable/merged.c +3 -3
@@ -253,9 +253,9 @@ reftable_merged_table_min_update_index(struct reftable_merged_table *mt)return mt->min; } -static void merged_table_init_iter (struct reftable_merged_table *mt, -struct reftable_iterator *it, -uint8_t typ) +void merged_table_init_iter (struct reftable_merged_table *mt, +struct reftable_iterator *it, +uint8_t typ) {struct merged_iter *mi =reftable_malloc (sizeof (*mi));merged_iter_init (mi, mt, typ);
reftable/merged.h +6 -0
@@ -26,4 +26,10 @@ struct reftable_merged_table {void merged_table_release (struct reftable_merged_table *mt); +struct reftable_iterator ; + +void merged_table_init_iter (struct reftable_merged_table *mt, +struct reftable_iterator *it, +uint8_t typ); +#endif
reftable/reftable-stack.h +18 -0
@@ -66,6 +66,24 @@ int reftable_stack_add(struct reftable_stack *st, void *write_arg), void *write_arg); +struct reftable_iterator ; + +/* +* Initialize an iterator for the merged tables contained in the stack that can +* be used to iterate through refs. The iterator is valid until the next reload +* or write. +*/ +void reftable_stack_init_ref_iterator (struct reftable_stack *st, +struct reftable_iterator *it); + +/* +* Initialize an iterator for the merged tables contained in the stack that can +* be used to iterate through logs. The iterator is valid until the next reload +* or write. +*/ +void reftable_stack_init_log_iterator (struct reftable_stack *st, +struct reftable_iterator *it); +/* returns the merged_table for seeking. This table is valid until the * next write or reload, and should not be closed or deleted. */
reftable/stack.c +15 -0
@@ -10,6 +10,7 @@ license that can be found in the LICENSE file or at#include "../write-or-die.h" #include "system.h" +#include "constants.h" #include "merged.h" #include "reader.h" #include "reftable-error.h"
@@ -130,6 +131,20 @@ int read_lines(const char *filename, char ***namesp)return err; } +void reftable_stack_init_ref_iterator (struct reftable_stack *st, +struct reftable_iterator *it) +{ +merged_table_init_iter (reftable_stack_merged_table (st), + it,BLOCK_TYPE_REF ); +} + +void reftable_stack_init_log_iterator (struct reftable_stack *st, +struct reftable_iterator *it) +{ +merged_table_init_iter (reftable_stack_merged_table (st), + it,BLOCK_TYPE_LOG ); +} +struct reftable_merged_table *reftable_stack_merged_table (struct reftable_stack *st) {
Signature · 1 line
2.45.0
PATCH 13/13 reftable/merged: adapt interface to allow reuse of iterators
In reply to Patrick SteinhardtRefactor the interfaces exposed by struct reftable_merged_table and struct merged_iter such that they support iterator reuse. This is done by separating initialization of the iterator and seeking on it.
--- reftable/merged.c | 35 ----------------------------------- reftable/merged_test.c | 19 +++++++++++++------ reftable/reftable-merged.h | 15 --------------- reftable/stack.c | 14 +++++++++----- 4 files changed, 22 insertions(+), 61 deletions(-)
reftable/merged.c +0 -35
@@ -262,41 +262,6 @@ void merged_table_init_iter(struct reftable_merged_table *mt,iterator_from_merged_iter (it, mi); } -int reftable_merged_table_seek_ref (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name) -{ -struct reftable_record rec = { - .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - }, - }; -merged_table_init_iter (mt, it,BLOCK_TYPE_REF ); -return iterator_seek (it, &rec); -} - -int reftable_merged_table_seek_log_at (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name,uint64_t update_index) -{ -struct reftable_record rec = { .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = update_index, - } }; -merged_table_init_iter (mt, it,BLOCK_TYPE_LOG ); -return iterator_seek (it, &rec); -} - -int reftable_merged_table_seek_log (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name) -{ -uint64_t max = ~((uint64_t )0 ); -return reftable_merged_table_seek_log_at (mt, it, name, max); -} -uint32_t reftable_merged_table_hash_id (struct reftable_merged_table *mt) {return mt->hash_id;
reftable/merged_test.c +13 -6
@@ -12,6 +12,7 @@ license that can be found in the LICENSE file or at#include "basics.h" #include "blocksource.h" +#include "constants.h" #include "reader.h" #include "record.h" #include "test_framework.h"
@@ -145,7 +146,10 @@ static void test_merged_between(void)int i;struct reftable_ref_record ref = {NULL };struct reftable_iterator it = {NULL }; -int err =reftable_merged_table_seek_ref (mt, &it,"a" ); +int err; + +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + err =reftable_iterator_seek_ref (&it,"a" );EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &ref);
@@ -217,14 +221,15 @@ static void test_merged(void)struct reftable_reader **readers =NULL ;struct reftable_merged_table *mt =merged_table_from_records (refs, &bs, &readers, sizes, bufs,3 ); -struct reftable_iterator it = {NULL }; -int err =reftable_merged_table_seek_ref (mt, &it,"a" ); +int err;struct reftable_ref_record *out =NULL ;size_t len =0 ;size_t cap =0 ;int i =0 ; +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + err =reftable_iterator_seek_ref (&it,"a" );EXPECT_ERR (err);EXPECT (reftable_merged_table_hash_id (mt) ==GIT_SHA1_FORMAT_ID );EXPECT (reftable_merged_table_min_update_index (mt) ==1 );
@@ -348,14 +353,15 @@ static void test_merged_logs(void)struct reftable_reader **readers =NULL ;struct reftable_merged_table *mt =merged_table_from_log_records ( logs, &bs, &readers, sizes, bufs,3 ); -struct reftable_iterator it = {NULL }; -int err =reftable_merged_table_seek_log (mt, &it,"a" ); +int err;struct reftable_log_record *out =NULL ;size_t len =0 ;size_t cap =0 ;int i =0 ; +merged_table_init_iter (mt, &it,BLOCK_TYPE_LOG ); + err =reftable_iterator_seek_log (&it,"a" );EXPECT_ERR (err);EXPECT (reftable_merged_table_hash_id (mt) ==GIT_SHA1_FORMAT_ID );EXPECT (reftable_merged_table_min_update_index (mt) ==1 );
@@ -377,7 +383,8 @@ static void test_merged_logs(void) GIT_SHA1_RAWSZ)); } - err =reftable_merged_table_seek_log_at (mt, &it,"a" ,2 ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_LOG ); + err =reftable_iterator_seek_log_at (&it,"a" ,2 );EXPECT_ERR (err);reftable_log_record_release (&out[0 ]); err =reftable_iterator_next_log (&it, &out[0 ]);
reftable/reftable-merged.h +0 -15
@@ -36,21 +36,6 @@ int reftable_new_merged_table(struct reftable_merged_table **dest, struct reftable_table *stack, size_t n, uint32_t hash_id); -/* returns an iterator positioned just before 'name' */ -int reftable_merged_table_seek_ref (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name); - -/* returns an iterator for log entry, at given update_index */ -int reftable_merged_table_seek_log_at (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name,uint64_t update_index); - -/* like reftable_merged_table_seek_log_at but look for the newest entry. */ -int reftable_merged_table_seek_log (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name); -/* returns the max update_index covered by this merged table. */ uint64_t reftable_merged_table_max_update_index (struct reftable_merged_table *mt);
reftable/stack.c +9 -5
@@ -925,7 +925,8 @@ static int stack_write_compact(struct reftable_stack *st, goto done; } - err =reftable_merged_table_seek_ref (mt, &it,"" ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + err =reftable_iterator_seek_ref (&it,"" );if (err <0 ) goto done;
@@ -949,7 +950,8 @@ static int stack_write_compact(struct reftable_stack *st, }reftable_iterator_destroy (&it); - err =reftable_merged_table_seek_log (mt, &it,"" ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_LOG ); + err =reftable_iterator_seek_log (&it,"" );if (err <0 ) goto done;
@@ -1340,9 +1342,11 @@ int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,int reftable_stack_read_log (struct reftable_stack *st,const char *refname,struct reftable_log_record *log) { -struct reftable_iterator it = {NULL }; -struct reftable_merged_table *mt =reftable_stack_merged_table (st); -int err =reftable_merged_table_seek_log (mt, &it, refname); +struct reftable_iterator it = {0 }; +int err; + +reftable_stack_init_log_iterator (st, &it); + err =reftable_iterator_seek_log (&it, refname);if (err) goto done;
Signature · 1 line
2.45.0
Quoted 5 lines · Patrick Steinhardt
To address this inefficiency, the patch series at hand refactors the reftable library such that creation of iterators and seeking on an iterator are separate steps. This refactoring prepares us for reusing iterators to perform multiple seeks, which in turn will allow us to reuse internal data structures for subsequent seeks.
;-)
Quoted 8 lines
Note: this series does not yet go all the way to re-seekable iterators, and there are no users yet. The patch series is complex enough as-is already, so I decided to defer that to the next iteration. Thus, the whole refactoring here should essentially be a large no-op that prepares the infrastructure for re-seekable iterators.
The series depends on pks/reftable-write-optim at
fa74f32291(reftable/block: reuse compressed array, 2024-04-08).
There is another topic on reftable to make write options tweakable, whose addition of reftable/dump and reader_print_blocks interface needs to be adjusted to this change, I think.
reftable/reader.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-)
reftable/reader.c +9 -6
@@ -841,7 +841,7 @@ int reftable_reader_print_blocks(const char *tablename) }, };struct reftable_block_source src = {0 }; -struct table_iter ti =TABLE_ITER_INIT ; +struct table_iter *ti;struct reftable_reader *r =NULL ;size_t i;int err;
@@ -854,11 +854,14 @@ int reftable_reader_print_blocks(const char *tablename)if (err <0 ) goto done; +REFTABLE_ALLOC_ARRAY (ti,1 ); +table_iter_init (ti, r); +printf ("header:\n" );printf (" block_size: %d\n" , r->block_size);for (i =0 ; i <ARRAY_SIZE (sections); i++) { - err =reader_start (r, &ti, sections[i].type,0 ); + err =table_iter_seek_start (ti, sections[i].type,0 );if (err <0 ) goto done;if (err >0 )
@@ -867,10 +870,10 @@ int reftable_reader_print_blocks(const char *tablename)printf ("%s:\n" , sections[i].name);while (1 ) { -printf (" - length: %u\n" , ti.br.block_len); -printf (" restarts: %u\n" , ti.br.restart_count); +printf (" - length: %u\n" , ti->br.block_len); +printf (" restarts: %u\n" , ti->br.restart_count); - err =table_iter_next_block (&ti); + err =table_iter_next_block (ti);if (err <0 ) goto done;if (err >0 )
@@ -880,6 +883,6 @@ int reftable_reader_print_blocks(const char *tablename) done:reftable_reader_free (r); -table_iter_close (&ti); +table_iter_close (ti);return err; }
reftable/reader.c int reftable_reader_print_blocks(const char *tablename) · line 847
Quoted 13 lines · Junio C Hamano
reftable/reader.c +1
-1@@ -841,7 +841,7 @@ int reftable_reader_print_blocks(const char *tablename) }, };struct reftable_block_source src = {0 }; -struct table_iter ti =TABLE_ITER_INIT ; +struct table_iter *ti;struct reftable_reader *r =NULL ;size_t i;int err;
... an unusually early error could skip everything here ...
reftable/reader.c int reftable_reader_print_blocks(const char *tablename) · line 886
Quoted 6 lines
reftable/reader.c +1
-1@@ -880,6 +883,6 @@ int reftable_reader_print_blocks(const char *tablename) done:reftable_reader_free (r); -table_iter_close (&ti); +table_iter_close (ti);
... and cause this to break. In the version of the merge-fix I used, *ti is initialized to NULL and the _close() is called only when ti is not NULL.
Quoted 2 lines
reftable/reader.c +0
-0return err; }
Quoted 16 lines · Junio C Hamano
Quoted 5 lines · Patrick Steinhardt
To address this inefficiency, the patch series at hand refactors the reftable library such that creation of iterators and seeking on an iterator are separate steps. This refactoring prepares us for reusing iterators to perform multiple seeks, which in turn will allow us to reuse internal data structures for subsequent seeks.
;-)
Quoted 6 lines
Note: this series does not yet go all the way to re-seekable iterators, and there are no users yet. The patch series is complex enough as-is already, so I decided to defer that to the next iteration. Thus, the whole refactoring here should essentially be a large no-op that prepares the infrastructure for re-seekable iterators.
Quoted 6 lines
Quoted 2 lines
The series depends on pks/reftable-write-optim at
fa74f32291(reftable/block: reuse compressed array, 2024-04-08).There is another topic on reftable to make write options tweakable, whose addition of reftable/dump and
reader_print_blocksinterface needs to be adjusted to this change, I think.
True, I forgot to double check that one. Your proposed resolution isn't quite correct as we now leak the ti pointer -- table_iter_close() only closes the iterator and releases its underlying resources, but does not free the iterator itself.
The below diff would be needed on top of what you currently have in seen. In any case though, I can also resend this topic with ps/reftable-write-options pulled in as a dependency. Please let me know your preference.
Patrick
-- >8 --
reftable/reader.c +7 -9
@@ -841,8 +841,8 @@ int reftable_reader_print_blocks(const char *tablename) }, };struct reftable_block_source src = {0 }; -struct table_iter *ti =NULL ;struct reftable_reader *r =NULL ; +struct table_iter ti = {0 };size_t i;int err;
@@ -854,14 +854,13 @@ int reftable_reader_print_blocks(const char *tablename)if (err <0 ) goto done; -REFTABLE_ALLOC_ARRAY (ti,1 ); -table_iter_init (ti, r); +table_iter_init (&ti, r);printf ("header:\n" );printf (" block_size: %d\n" , r->block_size);for (i =0 ; i <ARRAY_SIZE (sections); i++) { - err =table_iter_seek_start (ti, sections[i].type,0 ); + err =table_iter_seek_start (&ti, sections[i].type,0 );if (err <0 ) goto done;if (err >0 )
@@ -870,10 +869,10 @@ int reftable_reader_print_blocks(const char *tablename)printf ("%s:\n" , sections[i].name);while (1 ) { -printf (" - length: %u\n" , ti->br.block_len); -printf (" restarts: %u\n" , ti->br.restart_count); +printf (" - length: %u\n" , ti.br.block_len); +printf (" restarts: %u\n" , ti.br.restart_count); - err =table_iter_next_block (ti); + err =table_iter_next_block (&ti);if (err <0 ) goto done;if (err >0 )
@@ -883,7 +882,6 @@ int reftable_reader_print_blocks(const char *tablename) done:reftable_reader_free (r); -if (ti) -table_iter_close (ti); +table_iter_close (&ti);return err; }
Quoted 4 lines · Patrick Steinhardt
The below diff would be needed on top of what you currently have in
seen. In any case though, I can also resend this topic with ps/reftable-write-options pulled in as a dependency. Please let me know your preference.
Is it "needed", in the sense that "without the fix what you posted is broken in such and such ways", or is it "I think it is niceR to have it on stack because this one instance does not have to be on heap"? To me, they look equivalent and I have no problems with the "nicer" variant, but your "needed" makes me wonder if I am missing some correctness invariants I am violating without realizing.
Thanks.
Quoted 7 lines · Junio C Hamano
Quoted 4 lines · Patrick Steinhardt
The below diff would be needed on top of what you currently have in
seen. In any case though, I can also resend this topic with ps/reftable-write-options pulled in as a dependency. Please let me know your preference.
Quoted 6 lines
Is it "needed", in the sense that "without the fix what you posted is broken in such and such ways", or is it "I think it is niceR to have it on stack because this one instance does not have to be on heap"? To me, they look equivalent and I have no problems with the "nicer" variant, but your "needed" makes me wonder if I am missing some correctness invariants I am violating without realizing.
It's needed in the sense that your version leaks memory -- the ti pointer is never free'd. Other than that they are equivalent indeed.
Patrick
Quoted 2 lines · Patrick Steinhardt
It's needed in the sense that your version leaks memory -- the
tipointer is never free'd. Other than that they are equivalent indeed.
Ah, OK, I somehow misread that _close() will free the resource, but it only frees the resources held by the shell and not the shell itself.
Thanks.
v2 cover reftable: prepare for re-seekable iterators
In reply to Patrick SteinhardtHi,
this is the second version of my patch series that prepares the reftable iterators to become re-seekable. These refactorings will eventually allow us to reuse data structures by iterators and optimize for certain cases.
Changes compared to v1:
- Various fixes to commit messages.
- Fixed a copy & pasted comment to refer to logs instead of refs.
The series continues to build on top of ps/reftable-write-optim. There is a merge conflict with the in-flight ps/reftable-write-options, but given that this series has not yet been merged to next and because Junio has already resolved the conflict in "seen" I decided to not pull it in as an additional dependency.
Thanks!
Patrick
Patrick Steinhardt (13):
reftable/block: use size_t to track restart point index reftable/reader: avoid copying index iterator reftable/reader: unify indexed and linear seeking reftable/reader: separate concerns of table iter and reftable reader reftable/reader: inline reader_seek_internal() reftable/reader: set up the reader when initializing table iterator reftable/merged: split up initialization and seeking of records reftable/merged: simplify indices for subiterators reftable/generic: move seeking of records into the iterator reftable/generic: adapt interface to allow reuse of iterators reftable/reader: adapt interface to allow reuse of iterators reftable/stack: provide convenience functions to create iterators reftable/merged: adapt interface to allow reuse of iterators
refs/reftable-backend.c | 48 ++++---- reftable/block.c | 4 +- reftable/generic.c | 94 +++++++++++---- reftable/generic.h | 9 +- reftable/iter.c | 23 +++- reftable/merged.c | 148 ++++++++---------------- reftable/merged.h | 6 + reftable/merged_test.c | 19 ++- reftable/reader.c | 218 +++++++++++++++-------------------- reftable/readwrite_test.c | 35 ++++-- reftable/reftable-generic.h | 8 +- reftable/reftable-iterator.h | 21 ++++ reftable/reftable-merged.h | 15 --- reftable/reftable-reader.h | 45 ++------ reftable/reftable-stack.h | 18 +++ reftable/stack.c | 29 ++++- 16 files changed, 378 insertions(+), 362 deletions(-)
Range-diff against v1:
1: ca86a8b58d = 1: ca86a8b58d reftable/block: use `size_t` to track restart point index 2: bdbebdbd36 = 2: bdbebdbd36 reftable/reader: avoid copying index iterator 3: 716863a580 = 3: 716863a580 reftable/reader: unify indexed and linear seeking 4: 91db2f18c1 = 4: 91db2f18c1 reftable/reader: separate concerns of table iter and reftable reader 5: 4d498ef342 = 5: 4d498ef342 reftable/reader: inline `reader_seek_internal()` 6: 5a10a11584 = 6: 5a10a11584 reftable/reader: set up the reader when initializing table iterator 7: 21b3e3ab5f ! 7: 12c10fd366 reftable/merged: split up initialization and seeking of records
@@ Commit message
To initialize a struct merged_iter, we need to seek all subiterators to the wanted record and then add their results to the priority queue used to sort the records. This logic is split up across two functions,
- merged_table_seek_record() and merged_table_iter(). The scope of
- these functions is somewhat weird though, where merged_table_iter() is
+ merged_table_seek_record() and merged_iter_init(). The scope of
+ these functions is somewhat weird though, where merged_iter_init() is
only responsible for adding the records of the subiterators to the priority queue.
- Clarify the scope of those functions such that merged_table_iter() is
+ Clarify the scope of those functions such that merged_iter_init() is
only responsible for initializing the iterator's structure. Performing the subiterator seeks are now part of merged_table_seek_record().
8: f0f42cd56b ! 8: 31bdfc1e34 reftable/merged: simplify indices for subiterators
@@ Commit message
reftable/merged: simplify indices for subiterators
When seeking on a merged table, we perform the seek for each of the
- subiterators. If the subiterator hasa the desired record we add it to
- the priority queue, otherwise we skip it and don't add it to the stack
- of subiterators hosted by the merged table.
+ subiterators. If the subiterator has the desired record we add it to the
+ priority queue, otherwise we skip it and don't add it to the stack of
+ subiterators hosted by the merged table.
The consequence of this is that the index of the subiterator in the merged table does not necessarily correspond to the index of it in the
9: 859b399e71 ! 9: 3e91c3830e reftable/generic: move seeking of records into the iterator
@@ Commit message
The second and more significant downside is that it is impossible to reuse iterators for multiple seeks. Whenever you want to look up a record, you need to re-create the whole infrastructure again, which is
- quite a waste of time. Furthermore, it is impossible to for example
- optimize seeks, for example when seeking the same record multiple times.
+ quite a waste of time. Furthermore, it is impossible to optimize seeks,
+ such as when seeking the same record multiple times.
To address this, we essentially split up the concerns properly such that the parent data structure is responsible for setting up the iterator via
10: 727b8fa432 = 10: b0641dd800 reftable/generic: adapt interface to allow reuse of iterators 11: f688f8f59a ! 11: 0745951650 reftable/reader: adapt interface to allow reuse of iterators
@@ reftable/reftable-reader.h: struct reftable_table;
+void reftable_reader_init_ref_iterator(struct reftable_reader *r,
+ struct reftable_iterator *it);
+
-+/* Initialize a reftable iterator for reading refs. */ ++/* Initialize a reftable iterator for reading logs. */
+void reftable_reader_init_log_iterator(struct reftable_reader *r,
+ struct reftable_iterator *it);
12: 68cc35919b = 12: 51480c4328 reftable/stack: provide convenience functions to create iterators 13: be4da295c6 = 13: 2586e93c44 reftable/merged: adapt interface to allow reuse of iterators
Signature · 1 line
2.45.GIT
PATCH v2 1/13 reftable/block: use `size_t` to track restart point index
The function block_reader_restart_offset() gets the offset of the ith restart point. i is a signed integer though, which is certainly not the correct type to track indices like this. Furthermore, both callers end up passing a size_t.
Refactor the code to use a size_t instead.
--- reftable/block.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
reftable/block.c +2 -2
@@ -326,9 +326,9 @@ int block_reader_first_key(const struct block_reader *br, struct strbuf *key)return 0 ; } -static uint32_t block_reader_restart_offset (const struct block_reader *br,int i) +static uint32_t block_reader_restart_offset (const struct block_reader *br,size_t idx) { -return get_be24 (br->restart_bytes +3 * i); +return get_be24 (br->restart_bytes +3 * idx); }void block_iter_seek_start (struct block_iter *it,const struct block_reader *br)
Signature · 1 line
2.45.GIT
Re: [PATCH v2 01/13] reftable/block: use `size_t` to track restart point index
Quoted 6 lines · Patrick Steinhardt
The function
block_reader_restart_offset()gets the offset of theith restart point.iis a signed integer though, which is certainly not the correct type to track indices like this. Furthermore, both callers end up passing asize_t.Refactor the code to use a
size_tinstead.
More of a question for my understanding: Why use size_t vs uint16_t here? I'm asking since the restart count is defined as uint16_t restart_count in struct block_reader.
Quoted 24 lines
Signed-off-by Patrick Steinhardt <[email protected]>--- reftable/block.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)reftable/block.c +2
-3@@ -326,9 +326,9 @@ int block_reader_first_key(const struct block_reader *br, struct strbuf *key)return 0 ; } -static uint32_t block_reader_restart_offset (const struct block_reader *br,int i) +static uint32_t block_reader_restart_offset (const struct block_reader *br,size_t idx) { -return get_be24 (br->restart_bytes +3 * i); +return get_be24 (br->restart_bytes +3 * idx); }void block_iter_seek_start (struct block_iter *it,const struct block_reader *br) --2.45.GIT
Re: [PATCH v2 01/13] reftable/block: use `size_t` to track restart point index
Quoted 7 lines · Karthik Nayak
Quoted 5 lines · Patrick Steinhardt
The function
block_reader_restart_offset()gets the offset of theith restart point.iis a signed integer though, which is certainly not the correct type to track indices like this. Furthermore, both callers end up passing asize_t.
Quoted 5 lines
Quoted 1 line
Refactor the code to use a
size_tinstead.More of a question for my understanding: Why use
size_tvsuint16_there? I'm asking since the restart count is defined asuint16_t restart_countinstruct block_reader.
Mostly because all callers already use size_t, and it's customary to use them when talking about indices. We could use uint16_t, too, but it didn't really feel worth it to adjust all callers.
Patrick
PATCH v2 2/13 reftable/reader: avoid copying index iterator
In reply to Patrick SteinhardtWhen doing an indexed seek we need to walk down the multi-level index until we finally hit a record of the desired indexed type. This loop performs a copy of the index iterator on every iteration, which is both hard to understand and completely unnecessary.
Refactor the code so that we use a single iterator to walk down the indices, only.
Note that while this should improve performance, the improvement is negligible in all but the most unreasonable repositories. This is because the effect is only really noticeable when we have to walk down many levels of indices, which is not something that a repository would typically have. So the motivation for this change is really only about readability.
--- reftable/reader.c | 38 ++++++++++++++------------------------ 1 file changed, 14 insertions(+), 24 deletions(-)
reftable/reader.c +14 -24
@@ -510,13 +510,11 @@ static int reader_seek_indexed(struct reftable_reader *r, .type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }, }; -struct table_iter index_iter =TABLE_ITER_INIT ; -struct table_iter empty =TABLE_ITER_INIT ; -struct table_iter next =TABLE_ITER_INIT ; +struct table_iter ti =TABLE_ITER_INIT , *malloced;int err =0 ;reftable_record_key (rec, &want_index.u.idx.last_key); - err =reader_start (r, &index_iter,reftable_record_type (rec),1 ); + err =reader_start (r, &ti,reftable_record_type (rec),1 );if (err <0 ) goto done;
@@ -526,7 +524,7 @@ static int reader_seek_indexed(struct reftable_reader *r,* highest layer that identifies the relevant index block as well as * the record inside that block that corresponds to our wanted key. */ - err =reader_seek_linear (&index_iter, &want_index); + err =reader_seek_linear (&ti, &want_index);if (err <0 ) goto done;
@@ -552,44 +550,36 @@ static int reader_seek_indexed(struct reftable_reader *r,* all levels of the index only to find out that the key does * not exist. */ - err =table_iter_next (&index_iter, &index_result); + err =table_iter_next (&ti, &index_result);if (err !=0 ) goto done; - err =reader_table_iter_at (r, &next, index_result.u.idx.offset, -0 ); + err =reader_table_iter_at (r, &ti, index_result.u.idx.offset,0 );if (err !=0 ) goto done; - err =block_iter_seek_key (&next.bi, &next.br, &want_index.u.idx.last_key); + err =block_iter_seek_key (&ti.bi, &ti.br, &want_index.u.idx.last_key);if (err <0 ) goto done; -if (next.typ ==reftable_record_type (rec)) { +if (ti.typ ==reftable_record_type (rec)) { err =0 ;break ; } -if (next.typ !=BLOCK_TYPE_INDEX ) { +if (ti.typ !=BLOCK_TYPE_INDEX ) { err =REFTABLE_FORMAT_ERROR ; -break ; + goto done; } - -table_iter_close (&index_iter); - index_iter = next; - next = empty; } -if (err ==0 ) { -struct table_iter *malloced =reftable_calloc (1 ,sizeof (*malloced)); - *malloced = next; - next = empty; -iterator_from_table_iter (it, malloced); - } +REFTABLE_ALLOC_ARRAY (malloced,1 ); + *malloced = ti; +iterator_from_table_iter (it, malloced); done: -table_iter_close (&next); -table_iter_close (&index_iter); +if (err) +table_iter_close (&ti);reftable_record_release (&want_index);reftable_record_release (&index_result);return err;
Signature · 1 line
2.45.GIT
PATCH v2 3/13 reftable/reader: unify indexed and linear seeking
In reply to Patrick SteinhardtIn reader_seek_internal() we either end up doing an indexed seek when there is one or a linear seek otherwise. These two code paths are disjunct without a good reason, where the indexed seek will cause us to exit early.
Refactor the two code paths such that it becomes possible to share a bit more code between them.
--- reftable/reader.c | 42 ++++++++++++++++-------------------------- 1 file changed, 16 insertions(+), 26 deletions(-)
reftable/reader.c +16 -26
@@ -425,7 +425,7 @@ static int reader_seek_linear(struct table_iter *ti,struct strbuf want_key =STRBUF_INIT ;struct strbuf got_key =STRBUF_INIT ;struct reftable_record rec; -int err =-1 ; +int err;reftable_record_init (&rec,reftable_record_type (want));reftable_record_key (want, &want_key);
@@ -499,8 +499,8 @@ static int reader_seek_linear(struct table_iter *ti,return err; } -static int reader_seek_indexed (struct reftable_reader *r, -struct reftable_iterator *it, +static int reader_seek_indexed (struct table_iter *ti, +struct reftable_reader *r,struct reftable_record *rec) {struct reftable_record want_index = {
@@ -510,13 +510,9 @@ static int reader_seek_indexed(struct reftable_reader *r, .type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }, }; -struct table_iter ti =TABLE_ITER_INIT , *malloced; -int err =0 ; +int err;reftable_record_key (rec, &want_index.u.idx.last_key); - err =reader_start (r, &ti,reftable_record_type (rec),1 ); -if (err <0 ) - goto done;/* * The index may consist of multiple levels, where each level may have
@@ -524,7 +520,7 @@ static int reader_seek_indexed(struct reftable_reader *r,* highest layer that identifies the relevant index block as well as * the record inside that block that corresponds to our wanted key. */ - err =reader_seek_linear (&ti, &want_index); + err =reader_seek_linear (ti, &want_index);if (err <0 ) goto done;
@@ -550,36 +546,30 @@ static int reader_seek_indexed(struct reftable_reader *r,* all levels of the index only to find out that the key does * not exist. */ - err =table_iter_next (&ti, &index_result); + err =table_iter_next (ti, &index_result);if (err !=0 ) goto done; - err =reader_table_iter_at (r, &ti, index_result.u.idx.offset,0 ); + err =reader_table_iter_at (r, ti, index_result.u.idx.offset,0 );if (err !=0 ) goto done; - err =block_iter_seek_key (&ti.bi, &ti.br, &want_index.u.idx.last_key); + err =block_iter_seek_key (&ti->bi, &ti->br, &want_index.u.idx.last_key);if (err <0 ) goto done; -if (ti.typ ==reftable_record_type (rec)) { +if (ti->typ ==reftable_record_type (rec)) { err =0 ;break ; } -if (ti.typ !=BLOCK_TYPE_INDEX ) { +if (ti->typ !=BLOCK_TYPE_INDEX ) { err =REFTABLE_FORMAT_ERROR ; goto done; } } -REFTABLE_ALLOC_ARRAY (malloced,1 ); - *malloced = ti; -iterator_from_table_iter (it, malloced); - done: -if (err) -table_iter_close (&ti);reftable_record_release (&want_index);reftable_record_release (&index_result);return err;
@@ -595,15 +585,15 @@ static int reader_seek_internal(struct reftable_reader *r,struct table_iter ti =TABLE_ITER_INIT , *p;int err; -if (idx >0 ) -return reader_seek_indexed (r, it, rec); - - err =reader_start (r, &ti,reftable_record_type (rec),0 ); + err =reader_start (r, &ti,reftable_record_type (rec), !!idx);if (err <0 ) goto out; - err =reader_seek_linear (&ti, rec); -if (err <0 ) +if (idx) + err =reader_seek_indexed (&ti, r, rec); +else + err =reader_seek_linear (&ti, rec); +if (err) goto out;REFTABLE_ALLOC_ARRAY (p,1 );
Signature · 1 line
2.45.GIT
Re: [PATCH v2 03/13] reftable/reader: unify indexed and linear seeking
Quoted 2 lines · Patrick Steinhardt
In
reader_seek_internal()we either end up doing an indexed seek when there is one or a linear seek otherwise. These two code paths are
Are we missing the subject here?
[snip]
Re: [PATCH v2 03/13] reftable/reader: unify indexed and linear seeking
Quoted 6 lines · Karthik Nayak
Quoted 2 lines · Patrick Steinhardt
In
reader_seek_internal()we either end up doing an indexed seek when there is one or a linear seek otherwise. These two code paths areAre we missing the subject here?
Hm. "one" refers back to "indexed" and is supposed to mean "index" here. I agree that this is easy to misread though and may not even be proper English.
It doesn't really feel worth it to rebase this series just for this issue, but if I did it would be 's/one/an index/'. Let me know in case you disagree though.
Patrick
Re: [PATCH v2 03/13] reftable/reader: unify indexed and linear seeking
Quoted 12 lines · Patrick Steinhardt
Quoted 6 lines · Karthik Nayak
Quoted 2 lines · Patrick Steinhardt
In
reader_seek_internal()we either end up doing an indexed seek when there is one or a linear seek otherwise. These two code paths areAre we missing the subject here?
Hm. "one" refers back to "indexed" and is supposed to mean "index" here. I agree that this is easy to misread though and may not even be proper English.
Quoted 5 lines
It doesn't really feel worth it to rebase this series just for this issue, but if I did it would be 's/one/an index/'. Let me know in case you disagree though.
Patrick
Okay that makes a bunch of sense, I think it is okay though and not worth a reroll.
Karthik
PATCH v2 4/13 reftable/reader: separate concerns of table iter and reftable reader
In reply to Patrick SteinhardtIn "reftable/reader.c" we implement two different interfaces:
- The reftable reader contains the logic to read reftables.
- The table iterator is used to iterate through a single reftable read by the reader.
The way those two types are used in the code is somewhat confusing though because seeking inside a table is implemented as if it was part of the reftable reader, even though it is ultimately more of a detail implemented by the table iterator.
Make the boundary between those two types clearer by renaming functions that seek records in a table such that they clearly belong to the table iterator's logic.
--- reftable/reader.c | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-)
reftable/reader.c +15 -17
@@ -386,9 +386,8 @@ static void iterator_from_table_iter(struct reftable_iterator *it, it->ops = &table_iter_vtable; } -static int reader_table_iter_at (struct reftable_reader *r, -struct table_iter *ti,uint64_t off, -uint8_t typ) +static int table_iter_seek_to (struct table_iter *ti,struct reftable_reader *r, +uint64_t off,uint8_t typ) {int err;
@@ -403,8 +402,8 @@ static int reader_table_iter_at(struct reftable_reader *r,return 0 ; } -static int reader_start (struct reftable_reader *r,struct table_iter *ti, -uint8_t typ,int index) +static int table_iter_seek_start (struct table_iter *ti,struct reftable_reader *r, +uint8_t typ,int index) {struct reftable_reader_offsets *offs =reader_offsets_for (r, typ);uint64_t off = offs->offset;
@@ -416,11 +415,11 @@ static int reader_start(struct reftable_reader *r, struct table_iter *ti, typ =BLOCK_TYPE_INDEX ; } -return reader_table_iter_at (r, ti, off, typ); +return table_iter_seek_to (ti, r, off, typ); } -static int reader_seek_linear (struct table_iter *ti, -struct reftable_record *want) +static int table_iter_seek_linear (struct table_iter *ti, +struct reftable_record *want) {struct strbuf want_key =STRBUF_INIT ;struct strbuf got_key =STRBUF_INIT ;
@@ -499,9 +498,8 @@ static int reader_seek_linear(struct table_iter *ti,return err; } -static int reader_seek_indexed (struct table_iter *ti, -struct reftable_reader *r, -struct reftable_record *rec) +static int table_iter_seek_indexed (struct table_iter *ti, +struct reftable_record *rec) {struct reftable_record want_index = { .type =BLOCK_TYPE_INDEX , .u.idx = { .last_key =STRBUF_INIT }
@@ -520,7 +518,7 @@ static int reader_seek_indexed(struct table_iter *ti,* highest layer that identifies the relevant index block as well as * the record inside that block that corresponds to our wanted key. */ - err =reader_seek_linear (ti, &want_index); + err =table_iter_seek_linear (ti, &want_index);if (err <0 ) goto done;
@@ -550,7 +548,7 @@ static int reader_seek_indexed(struct table_iter *ti,if (err !=0 ) goto done; - err =reader_table_iter_at (r, ti, index_result.u.idx.offset,0 ); + err =table_iter_seek_to (ti, ti->r, index_result.u.idx.offset,0 );if (err !=0 ) goto done;
@@ -585,14 +583,14 @@ static int reader_seek_internal(struct reftable_reader *r,struct table_iter ti =TABLE_ITER_INIT , *p;int err; - err =reader_start (r, &ti,reftable_record_type (rec), !!idx); + err =table_iter_seek_start (&ti, r,reftable_record_type (rec), !!idx);if (err <0 ) goto out;if (idx) - err =reader_seek_indexed (&ti, r, rec); + err =table_iter_seek_indexed (&ti, rec);else - err =reader_seek_linear (&ti, rec); + err =table_iter_seek_linear (&ti, rec);if (err) goto out;
@@ -742,7 +740,7 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,int err; *ti = ti_empty; - err =reader_start (r, ti,BLOCK_TYPE_REF ,0 ); + err =table_iter_seek_start (ti, r,BLOCK_TYPE_REF ,0 );if (err <0 ) {reftable_free (ti);return err;
Signature · 1 line
2.45.GIT
PATCH v2 5/13 reftable/reader: inline `reader_seek_internal()`
In reply to Patrick SteinhardtWe have both reader_seek() and reader_seek_internal(), where the former function only exists so that we can exit early in case the given table has no records of the sought-after type.
Merge these two functions into one.
--- reftable/reader.c | 34 ++++++++++++---------------------- 1 file changed, 12 insertions(+), 22 deletions(-)
reftable/reader.c +12 -22
@@ -573,21 +573,25 @@ static int table_iter_seek_indexed(struct table_iter *ti,return err; } -static int reader_seek_internal (struct reftable_reader *r, -struct reftable_iterator *it, -struct reftable_record *rec) +static int reader_seek (struct reftable_reader *r,struct reftable_iterator *it, +struct reftable_record *rec) { -struct reftable_reader_offsets *offs = -reader_offsets_for (r,reftable_record_type (rec)); -uint64_t idx = offs->index_offset; +uint8_t typ =reftable_record_type (rec); +struct reftable_reader_offsets *offs =reader_offsets_for (r, typ);struct table_iter ti =TABLE_ITER_INIT , *p;int err; - err =table_iter_seek_start (&ti, r,reftable_record_type (rec), !!idx); +if (!offs->is_present) { +iterator_set_empty (it); +return 0 ; + } + + err =table_iter_seek_start (&ti, r,reftable_record_type (rec), + !!offs->index_offset);if (err <0 ) goto out; -if (idx) +if (offs->index_offset) err =table_iter_seek_indexed (&ti, rec);else err =table_iter_seek_linear (&ti, rec);
@@ -604,20 +608,6 @@ static int reader_seek_internal(struct reftable_reader *r,return err; } -static int reader_seek (struct reftable_reader *r,struct reftable_iterator *it, -struct reftable_record *rec) -{ -uint8_t typ =reftable_record_type (rec); - -struct reftable_reader_offsets *offs =reader_offsets_for (r, typ); -if (!offs->is_present) { -iterator_set_empty (it); -return 0 ; - } - -return reader_seek_internal (r, it, rec); -} -int reftable_reader_seek_ref (struct reftable_reader *r,struct reftable_iterator *it,const char *name) {
Signature · 1 line
2.45.GIT
PATCH v2 6/13 reftable/reader: set up the reader when initializing table iterator
In reply to Patrick SteinhardtAll the seeking functions accept a struct reftable_reader as input such that they can use the reader to look up the respective blocks. Refactor the code to instead set up the reader as a member of struct table_iter during initialization such that we don't have to pass the reader on every single call.
This step is required to move seeking of records into the generic struct reftable_iterator infrastructure.
--- reftable/reader.c | 39 ++++++++++++++++++++++----------------- 1 file changed, 22 insertions(+), 17 deletions(-)
reftable/reader.c +22 -17
@@ -224,8 +224,14 @@ struct table_iter {struct block_iter bi;int is_finished; }; -#define TABLE_ITER_INIT { \ - .bi = BLOCK_ITER_INIT \ + +static int table_iter_init (struct table_iter *ti,struct reftable_reader *r) +{ +struct block_iter bi =BLOCK_ITER_INIT ; +memset (ti,0 ,sizeof (*ti)); + ti->r = r; + ti->bi = bi; +return 0 ; } static int table_iter_next_in_block(struct table_iter *ti,
@@ -386,26 +392,23 @@ static void iterator_from_table_iter(struct reftable_iterator *it, it->ops = &table_iter_vtable; } -static int table_iter_seek_to (struct table_iter *ti,struct reftable_reader *r, -uint64_t off,uint8_t typ) +static int table_iter_seek_to (struct table_iter *ti,uint64_t off,uint8_t typ) {int err; - err =reader_init_block_reader (r, &ti->br, off, typ); + err =reader_init_block_reader (ti->r, &ti->br, off, typ);if (err !=0 )return err; - ti->r = r; ti->typ =block_reader_type (&ti->br); ti->block_off = off;block_iter_seek_start (&ti->bi, &ti->br);return 0 ; } -static int table_iter_seek_start (struct table_iter *ti,struct reftable_reader *r, -uint8_t typ,int index) +static int table_iter_seek_start (struct table_iter *ti,uint8_t typ,int index) { -struct reftable_reader_offsets *offs =reader_offsets_for (r, typ); +struct reftable_reader_offsets *offs =reader_offsets_for (ti->r, typ);uint64_t off = offs->offset;if (index) { off = offs->index_offset;
@@ -415,7 +418,7 @@ static int table_iter_seek_start(struct table_iter *ti, struct reftable_reader * typ =BLOCK_TYPE_INDEX ; } -return table_iter_seek_to (ti, r, off, typ); +return table_iter_seek_to (ti, off, typ); } static int table_iter_seek_linear(struct table_iter *ti,
@@ -548,7 +551,7 @@ static int table_iter_seek_indexed(struct table_iter *ti,if (err !=0 ) goto done; - err =table_iter_seek_to (ti, ti->r, index_result.u.idx.offset,0 ); + err =table_iter_seek_to (ti, index_result.u.idx.offset,0 );if (err !=0 ) goto done;
@@ -578,7 +581,7 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it, {uint8_t typ =reftable_record_type (rec);struct reftable_reader_offsets *offs =reader_offsets_for (r, typ); -struct table_iter ti =TABLE_ITER_INIT , *p; +struct table_iter ti, *p;int err;if (!offs->is_present) {
@@ -586,7 +589,9 @@ static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,return 0 ; } - err =table_iter_seek_start (&ti, r,reftable_record_type (rec), +table_iter_init (&ti, r); + + err =table_iter_seek_start (&ti,reftable_record_type (rec), !!offs->index_offset);if (err <0 ) goto out;
@@ -722,15 +727,15 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,struct reftable_iterator *it, uint8_t *oid) { - struct table_iter ti_empty = TABLE_ITER_INIT; -struct table_iter *ti =reftable_calloc (1 ,sizeof (*ti)); + struct table_iter *ti;struct filtering_ref_iterator *filter =NULL ;struct filtering_ref_iterator empty =FILTERING_REF_ITERATOR_INIT ;int oid_len =hash_size (r->hash_id);int err; - *ti = ti_empty; - err =table_iter_seek_start (ti, r,BLOCK_TYPE_REF ,0 ); +REFTABLE_ALLOC_ARRAY (ti,1 ); +table_iter_init (ti, r); + err =table_iter_seek_start (ti,BLOCK_TYPE_REF ,0 );if (err <0 ) {reftable_free (ti);return err;
Signature · 1 line
2.45.GIT
PATCH v2 7/13 reftable/merged: split up initialization and seeking of records
In reply to Patrick SteinhardtTo initialize a struct merged_iter, we need to seek all subiterators to the wanted record and then add their results to the priority queue used to sort the records. This logic is split up across two functions, merged_table_seek_record() and merged_iter_init(). The scope of these functions is somewhat weird though, where merged_iter_init() is only responsible for adding the records of the subiterators to the priority queue.
Clarify the scope of those functions such that merged_iter_init() is only responsible for initializing the iterator's structure. Performing the subiterator seeks are now part of merged_table_seek_record().
This step is required to move seeking of records into the generic struct reftable_iterator infrastructure.
--- reftable/merged.c | 59 ++++++++++++++++++----------------------------- 1 file changed, 22 insertions(+), 37 deletions(-)
reftable/merged.c +22 -37
@@ -25,34 +25,18 @@ struct merged_subiter {struct merged_iter {struct merged_subiter *subiters;struct merged_iter_pqueue pq; -uint32_t hash_id;size_t stack_len; -uint8_t typ;int suppress_deletions;ssize_t advance_index; }; -static int merged_iter_init (struct merged_iter *mi) +static void merged_iter_init (struct merged_iter *mi, +struct reftable_merged_table *mt) { -for (size_t i =0 ; i < mi->stack_len; i++) { -struct pq_entry e = { - .index = i, - .rec = &mi->subiters[i].rec, - }; -int err; - -reftable_record_init (&mi->subiters[i].rec, mi->typ); - err =iterator_next (&mi->subiters[i].iter, - &mi->subiters[i].rec); -if (err <0 ) -return err; -if (err >0 ) -continue ; - -merged_iter_pqueue_add (&mi->pq, &e); - } - -return 0 ; +memset (mi,0 ,sizeof (*mi)); + mi->advance_index =-1 ; + mi->suppress_deletions = mt->suppress_deletions; +REFTABLE_CALLOC_ARRAY (mi->subiters, mt->stack_len); }static void merged_iter_close (void *p)
@@ -246,32 +230,33 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,struct reftable_iterator *it, struct reftable_record *rec) { - struct merged_iter merged = { - .typ =reftable_record_type (rec), - .hash_id = mt->hash_id, - .suppress_deletions = mt->suppress_deletions, - .advance_index =-1 , - }; -struct merged_iter *p; + struct merged_iter merged, *p;int err; -REFTABLE_CALLOC_ARRAY (merged.subiters, mt->stack_len); +merged_iter_init (&merged, mt); +for (size_t i =0 ; i < mt->stack_len; i++) { +reftable_record_init (&merged.subiters[merged.stack_len].rec, +reftable_record_type (rec)); + err =reftable_table_seek_record (&mt->stack[i], &merged.subiters[merged.stack_len].iter, rec);if (err <0 ) goto out; -if (!err) - merged.stack_len++; - } +if (err >0 ) +continue ; - err =merged_iter_init (&merged); -if (err <0 ) - goto out; + err =merged_iter_advance_subiter (&merged, merged.stack_len); +if (err <0 ) + goto out; + + merged.stack_len++; + } - p =reftable_malloc (sizeof (struct merged_iter )); + p =reftable_malloc (sizeof (*p)); *p = merged;iterator_from_merged_iter (it, p); + err =0 ; out:if (err <0 )
Signature · 1 line
2.45.GIT
PATCH v2 8/13 reftable/merged: simplify indices for subiterators
In reply to Patrick SteinhardtWhen seeking on a merged table, we perform the seek for each of the subiterators. If the subiterator has the desired record we add it to the priority queue, otherwise we skip it and don't add it to the stack of subiterators hosted by the merged table.
The consequence of this is that the index of the subiterator in the merged table does not necessarily correspond to the index of it in the merged iterator. Next to being potentially confusing, it also means that we won't easily be able to re-seek the merged iterator because we have no clear connection between both of the data structures.
Refactor the code so that the index stays the same in both structures.
--- reftable/merged.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
reftable/merged.c +4 -5
@@ -37,6 +37,7 @@ static void merged_iter_init(struct merged_iter *mi, mi->advance_index =-1 ; mi->suppress_deletions = mt->suppress_deletions;REFTABLE_CALLOC_ARRAY (mi->subiters, mt->stack_len); + mi->stack_len = mt->stack_len; }static void merged_iter_close (void *p)
@@ -236,21 +237,19 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,merged_iter_init (&merged, mt);for (size_t i =0 ; i < mt->stack_len; i++) { -reftable_record_init (&merged.subiters[merged.stack_len].rec, +reftable_record_init (&merged.subiters[i].rec,reftable_record_type (rec)); err =reftable_table_seek_record (&mt->stack[i], - &merged.subiters[merged.stack_len].iter, rec); + &merged.subiters[i].iter, rec);if (err <0 ) goto out;if (err >0 )continue ; - err =merged_iter_advance_subiter (&merged, merged.stack_len); + err =merged_iter_advance_subiter (&merged, i);if (err <0 ) goto out; - - merged.stack_len++; } p =reftable_malloc (sizeof (*p));
Signature · 1 line
2.45.GIT
PATCH v2 9/13 reftable/generic: move seeking of records into the iterator
In reply to Patrick SteinhardtReftable iterators are created by seeking on the parent structure of a corresponding record. For example, to create an iterator for the merged table you would call reftable_merged_table_seek_ref(). Most notably, it is not posible to create an iterator and then seek it afterwards.
While this may be a bit easier to reason about, it comes with two significant downsides. The first downside is that the logic to find records is split up between the parent data structure and the iterator itself. Conceptually, it is more straight forward if all that logic was contained in a single place, which should be the iterator.
The second and more significant downside is that it is impossible to reuse iterators for multiple seeks. Whenever you want to look up a record, you need to re-create the whole infrastructure again, which is quite a waste of time. Furthermore, it is impossible to optimize seeks, such as when seeking the same record multiple times.
To address this, we essentially split up the concerns properly such that the parent data structure is responsible for setting up the iterator via a new init_iter() callback, whereas the iterator handles seeks via a new seek() callback. This will eventually allow us to call seek() on the iterator multiple times, where every iterator can potentially optimize for certain cases.
Note that at this point in time we are not yet ready to reuse the iterators. This will be left for a future patch series.
--- reftable/generic.c | 47 +++++++++++++---- reftable/generic.h | 9 +++- reftable/iter.c | 15 ++++++ reftable/merged.c | 97 +++++++++++++++++----------------- reftable/reader.c | 126 +++++++++++++++++++++++++-------------------- 5 files changed, 177 insertions(+), 117 deletions(-)
reftable/generic.c +36 -11
@@ -12,25 +12,39 @@ license that can be found in the LICENSE file or at#include "reftable-iterator.h" #include "reftable-generic.h" +void table_init_iter (struct reftable_table *tab, +struct reftable_iterator *it, +uint8_t typ) +{ + + tab->ops->init_iter (tab->table_arg, it, typ); +} +int reftable_table_seek_ref (struct reftable_table *tab,struct reftable_iterator *it,const char *name) { -struct reftable_record rec = { .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - } }; -return tab->ops->seek_record (tab->table_arg, it, &rec); +struct reftable_record want = { + .type =BLOCK_TYPE_REF , + .u.ref = { + .refname = (char *)name, + }, + }; +table_init_iter (tab, it,BLOCK_TYPE_REF ); +return it->ops->seek (it->iter_arg, &want); }int reftable_table_seek_log (struct reftable_table *tab,struct reftable_iterator *it,const char *name) { -struct reftable_record rec = { .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = ~((uint64_t )0 ), - } }; -return tab->ops->seek_record (tab->table_arg, it, &rec); +struct reftable_record want = { + .type =BLOCK_TYPE_LOG , + .u.log = { + .refname = (char *)name, + .update_index = ~((uint64_t )0 ), + }, + }; +table_init_iter (tab, it,BLOCK_TYPE_LOG ); +return it->ops->seek (it->iter_arg, &want); } int reftable_table_read_ref(struct reftable_table *tab, const char *name,
@@ -152,11 +166,21 @@ int reftable_iterator_next_log(struct reftable_iterator *it,return err; } +int iterator_seek (struct reftable_iterator *it,struct reftable_record *want) +{ +return it->ops->seek (it->iter_arg, want); +} +int iterator_next (struct reftable_iterator *it,struct reftable_record *rec) {return it->ops->next (it->iter_arg, rec); } +static int empty_iterator_seek (void *arg,struct reftable_record *want) +{ +return 0 ; +} +static int empty_iterator_next (void *arg,struct reftable_record *rec) {return 1 ;
@@ -167,6 +191,7 @@ static void empty_iterator_close(void *arg) }static struct reftable_iterator_vtable empty_vtable = { + .seek = &empty_iterator_seek, .next = &empty_iterator_next, .close = &empty_iterator_close, };
reftable/generic.h +7 -2
@@ -14,19 +14,24 @@ license that can be found in the LICENSE file or at/* generic interface to reftables */ struct reftable_table_vtable { -int (*seek_record)(void *tab,struct reftable_iterator *it, -struct reftable_record *); +void (*init_iter)(void *tab,struct reftable_iterator *it,uint8_t typ);uint32_t (*hash_id)(void *tab);uint64_t (*min_update_index)(void *tab);uint64_t (*max_update_index)(void *tab); }; +void table_init_iter (struct reftable_table *tab, +struct reftable_iterator *it, +uint8_t typ); +struct reftable_iterator_vtable { +int (*seek)(void *iter_arg,struct reftable_record *want);int (*next)(void *iter_arg,struct reftable_record *rec);void (*close)(void *iter_arg); };void iterator_set_empty (struct reftable_iterator *it); +int iterator_seek (struct reftable_iterator *it,struct reftable_record *want);int iterator_next (struct reftable_iterator *it,struct reftable_record *rec);#endif
reftable/iter.c +15 -0
@@ -23,6 +23,13 @@ static void filtering_ref_iterator_close(void *iter_arg)reftable_iterator_destroy (&fri->it); } +static int filtering_ref_iterator_seek (void *iter_arg, +struct reftable_record *want) +{ +struct filtering_ref_iterator *fri = iter_arg; +return iterator_seek (&fri->it, want); +} +static int filtering_ref_iterator_next (void *iter_arg,struct reftable_record *rec) {
@@ -73,6 +80,7 @@ static int filtering_ref_iterator_next(void *iter_arg, }static struct reftable_iterator_vtable filtering_ref_iterator_vtable = { + .seek = &filtering_ref_iterator_seek, .next = &filtering_ref_iterator_next, .close = &filtering_ref_iterator_close, };
@@ -119,6 +127,12 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)return 0 ; } +static int indexed_table_ref_iter_seek (void *p,struct reftable_record *want) +{ +BUG ("seeking indexed table is not supported" ); +return -1 ; +} +static int indexed_table_ref_iter_next (void *p,struct reftable_record *rec) {struct indexed_table_ref_iter *it = p;
@@ -175,6 +189,7 @@ int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest, }static struct reftable_iterator_vtable indexed_table_ref_iter_vtable = { + .seek = &indexed_table_ref_iter_seek, .next = &indexed_table_ref_iter_next, .close = &indexed_table_ref_iter_close, };
reftable/merged.c +49 -48
158 lines not on this page · raw message
reftable/reader.c +70 -56
185 lines not on this page · raw message
Signature · 1 line
2.45.GIT
PATCH v2 10/13 reftable/generic: adapt interface to allow reuse of iterators
In reply to Patrick SteinhardtRefactor the interfaces exposed by struct reftable_table and struct reftable_iterator such that they support iterator reuse. This is done by separating initialization of the iterator and seeking on it.
--- reftable/generic.c | 53 ++++++++++++++++++++++++++---------- reftable/iter.c | 8 +++--- reftable/reftable-generic.h | 8 +++--- reftable/reftable-iterator.h | 21 ++++++++++++++ 4 files changed, 68 insertions(+), 22 deletions(-)
reftable/generic.c +39 -14
@@ -20,8 +20,20 @@ void table_init_iter(struct reftable_table *tab, tab->ops->init_iter (tab->table_arg, it, typ); } -int reftable_table_seek_ref (struct reftable_table *tab, -struct reftable_iterator *it,const char *name) +void reftable_table_init_ref_iter (struct reftable_table *tab, +struct reftable_iterator *it) +{ +table_init_iter (tab, it,BLOCK_TYPE_REF ); +} + +void reftable_table_init_log_iter (struct reftable_table *tab, +struct reftable_iterator *it) +{ +table_init_iter (tab, it,BLOCK_TYPE_LOG ); +} + +int reftable_iterator_seek_ref (struct reftable_iterator *it, +const char *name) {struct reftable_record want = { .type =BLOCK_TYPE_REF ,
@@ -29,29 +41,37 @@ int reftable_table_seek_ref(struct reftable_table *tab, .refname = (char *)name, }, }; -table_init_iter (tab, it,BLOCK_TYPE_REF );return it->ops->seek (it->iter_arg, &want); } -int reftable_table_seek_log (struct reftable_table *tab, -struct reftable_iterator *it,const char *name) +int reftable_iterator_seek_log_at (struct reftable_iterator *it, +const char *name,uint64_t update_index) {struct reftable_record want = { .type =BLOCK_TYPE_LOG , .u.log = { .refname = (char *)name, - .update_index = ~((uint64_t )0 ), + .update_index = update_index, }, }; -table_init_iter (tab, it,BLOCK_TYPE_LOG );return it->ops->seek (it->iter_arg, &want); } +int reftable_iterator_seek_log (struct reftable_iterator *it, +const char *name) +{ +return reftable_iterator_seek_log_at (it, name, ~((uint64_t )0 )); +} +int reftable_table_read_ref (struct reftable_table *tab,const char *name,struct reftable_ref_record *ref) {struct reftable_iterator it = {NULL }; -int err =reftable_table_seek_ref (tab, &it, name); +int err; + +reftable_table_init_ref_iter (tab, &it); + + err =reftable_iterator_seek_ref (&it, name);if (err) goto done;
@@ -76,10 +96,13 @@ int reftable_table_print(struct reftable_table *tab) {struct reftable_ref_record ref = {NULL };struct reftable_log_record log = {NULL };uint32_t hash_id =reftable_table_hash_id (tab); -int err =reftable_table_seek_ref (tab, &it,"" ); -if (err <0 ) { +int err; + +reftable_table_init_ref_iter (tab, &it); + + err =reftable_iterator_seek_ref (&it,"" ); +if (err <0 )return err; - }while (1 ) { err =reftable_iterator_next_ref (&it, &ref);
@@ -94,10 +117,12 @@ int reftable_table_print(struct reftable_table *tab) {reftable_iterator_destroy (&it);reftable_ref_record_release (&ref); - err =reftable_table_seek_log (tab, &it,"" ); -if (err <0 ) { +reftable_table_init_log_iter (tab, &it); + + err =reftable_iterator_seek_log (&it,"" ); +if (err <0 )return err; - } +while (1 ) { err =reftable_iterator_next_log (&it, &log);if (err >0 ) {
reftable/iter.c +4 -4
@@ -45,11 +45,11 @@ static int filtering_ref_iterator_next(void *iter_arg,if (fri->double_check) {struct reftable_iterator it = {NULL }; - err =reftable_table_seek_ref (&fri->tab, &it, - ref->refname); -if (err ==0 ) { +reftable_table_init_ref_iter (&fri->tab, &it); + + err =reftable_iterator_seek_ref (&it, ref->refname); +if (err ==0 ) err =reftable_iterator_next_ref (&it, ref); - }reftable_iterator_destroy (&it);
reftable/reftable-generic.h +4 -4
@@ -21,11 +21,11 @@ struct reftable_table {void *table_arg; }; -int reftable_table_seek_log (struct reftable_table *tab, -struct reftable_iterator *it,const char *name); +void reftable_table_init_ref_iter (struct reftable_table *tab, +struct reftable_iterator *it); -int reftable_table_seek_ref (struct reftable_table *tab, -struct reftable_iterator *it,const char *name); +void reftable_table_init_log_iter (struct reftable_table *tab, +struct reftable_iterator *it);/* returns the hash ID from a generic reftable_table */ uint32_t reftable_table_hash_id (struct reftable_table *tab);
reftable/reftable-iterator.h +21 -0
@@ -21,12 +21,33 @@ struct reftable_iterator {void *iter_arg; }; +/* +* Position the iterator at the ref record with given name such that the next +* call to `next_ref()` would yield the record. +*/ +int reftable_iterator_seek_ref (struct reftable_iterator *it, +const char *name); +/* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0: * end of iteration. */ int reftable_iterator_next_ref (struct reftable_iterator *it,struct reftable_ref_record *ref); +/* +* Position the iterator at the log record with given name and update index +* such that the next call to `next_log()` would yield the record. +*/ +int reftable_iterator_seek_log_at (struct reftable_iterator *it, +const char *name,uint64_t update_index); + +/* +* Position the iterator at the newest log record with given name such that the +* next call to `next_log()` would yield the record. +*/ +int reftable_iterator_seek_log (struct reftable_iterator *it, +const char *name); +/* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0: * end of iteration. */
Signature · 1 line
2.45.GIT
PATCH v2 11/13 reftable/reader: adapt interface to allow reuse of iterators
In reply to Patrick SteinhardtRefactor the interfaces exposed by struct reftable_reader and struct table_iterator such that they support iterator reuse. This is done by separating initialization of the iterator and seeking on it.
--- reftable/reader.c | 31 ++++---------------------- reftable/readwrite_test.c | 35 +++++++++++++++++++---------- reftable/reftable-reader.h | 45 ++++++-------------------------------- 3 files changed, 35 insertions(+), 76 deletions(-)
reftable/reader.c +4 -27
@@ -621,39 +621,16 @@ static void reader_init_iter(struct reftable_reader *r, } } -int reftable_reader_seek_ref (struct reftable_reader *r, -struct reftable_iterator *it,const char *name) +void reftable_reader_init_ref_iterator (struct reftable_reader *r, +struct reftable_iterator *it) { -struct reftable_record rec = { - .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - }, - };reader_init_iter (r, it,BLOCK_TYPE_REF ); -return iterator_seek (it, &rec); } -int reftable_reader_seek_log_at (struct reftable_reader *r, -struct reftable_iterator *it,const char *name, -uint64_t update_index) +void reftable_reader_init_log_iterator (struct reftable_reader *r, +struct reftable_iterator *it) { -struct reftable_record rec = { - .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = update_index, - }, - };reader_init_iter (r, it,BLOCK_TYPE_LOG ); -return iterator_seek (it, &rec); -} - -int reftable_reader_seek_log (struct reftable_reader *r, -struct reftable_iterator *it,const char *name) -{ -uint64_t max = ~((uint64_t )0 ); -return reftable_reader_seek_log_at (r, it, name, max); }void reader_close (struct reftable_reader *r)
reftable/readwrite_test.c +24 -11
@@ -239,7 +239,9 @@ static void test_log_write_read(void) err =init_reader (&rd, &source,"file.log" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (&rd, &it, names[N -1 ]); +reftable_reader_init_ref_iterator (&rd, &it); + + err =reftable_iterator_seek_ref (&it, names[N -1 ]);EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &ref);
@@ -252,7 +254,9 @@ static void test_log_write_read(void)reftable_iterator_destroy (&it);reftable_ref_record_release (&ref); - err =reftable_reader_seek_log (&rd, &it,"" ); +reftable_reader_init_log_iterator (&rd, &it); + + err =reftable_iterator_seek_log (&it,"" );EXPECT_ERR (err); i =0 ;
@@ -330,7 +334,8 @@ static void test_log_zlib_corruption(void) err =init_reader (&rd, &source,"file.log" );EXPECT_ERR (err); - err =reftable_reader_seek_log (&rd, &it,"refname" ); +reftable_reader_init_log_iterator (&rd, &it); + err =reftable_iterator_seek_log (&it,"refname" );EXPECT (err ==REFTABLE_ZLIB_ERROR );reftable_iterator_destroy (&it);
@@ -358,7 +363,8 @@ static void test_table_read_write_sequential(void) err =init_reader (&rd, &source,"file.ref" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (&rd, &it,"" ); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it,"" );EXPECT_ERR (err);while (1 ) {
@@ -412,7 +418,8 @@ static void test_table_read_api(void) err =init_reader (&rd, &source,"file.ref" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (&rd, &it, names[0 ]); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it, names[0 ]);EXPECT_ERR (err); err =reftable_iterator_next_log (&it, &log);
@@ -457,7 +464,8 @@ static void test_table_read_write_seek(int index, int hash_id) }for (i =1 ; i <N ; i++) { -int err =reftable_reader_seek_ref (&rd, &it, names[i]); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it, names[i]);EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &ref);EXPECT_ERR (err);
@@ -472,7 +480,8 @@ static void test_table_read_write_seek(int index, int hash_id)strbuf_addstr (&pastLast, names[N -1 ]);strbuf_addstr (&pastLast,"/" ); - err =reftable_reader_seek_ref (&rd, &it, pastLast.buf); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it, pastLast.buf);if (err ==0 ) {struct reftable_ref_record ref = {NULL };int err =reftable_iterator_next_ref (&it, &ref);
@@ -576,7 +585,8 @@ static void test_table_refs_for(int indexed) rd.obj_offsets.is_present =0 ; } - err =reftable_reader_seek_ref (&rd, &it,"" ); +reftable_reader_init_ref_iterator (&rd, &it); + err =reftable_iterator_seek_ref (&it,"" );EXPECT_ERR (err);reftable_iterator_destroy (&it);
@@ -639,7 +649,8 @@ static void test_write_empty_table(void) err =reftable_new_reader (&rd, &source,"filename" );EXPECT_ERR (err); - err =reftable_reader_seek_ref (rd, &it,"" ); +reftable_reader_init_ref_iterator (rd, &it); + err =reftable_iterator_seek_ref (&it,"" );EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &rec);
@@ -846,7 +857,8 @@ static void test_write_multiple_indices(void)* Seeking the log uses the log index now. In case there is any * confusion regarding indices we would notice here. */ - err =reftable_reader_seek_log (reader, &it,"" ); +reftable_reader_init_log_iterator (reader, &it); + err =reftable_iterator_seek_log (&it,"" );EXPECT_ERR (err);reftable_iterator_destroy (&it);
@@ -901,7 +913,8 @@ static void test_write_multi_level_index(void)/* * Seeking the last ref should work as expected. */ - err =reftable_reader_seek_ref (reader, &it,"refs/heads/199" ); +reftable_reader_init_ref_iterator (reader, &it); + err =reftable_iterator_seek_ref (&it,"refs/heads/199" );EXPECT_ERR (err);reftable_iterator_destroy (&it);
reftable/reftable-reader.h +7 -38
55 lines not on this page · raw message
Signature · 1 line
2.45.GIT
PATCH v2 12/13 reftable/stack: provide convenience functions to create iterators
In reply to Patrick SteinhardtThere exist a bunch of call sites in the reftable backend that want to create iterators for a reftable stack. This is rather convoluted right now, where you always have to go via the merged table. And it is about to become even more convoluted when we split up iterator initialization and seeking in the next commit.
Introduce convenience functions that allow the caller to create an iterator from a reftable stack directly without going through the merged table. Adapt callers accordingly.
--- refs/reftable-backend.c | 48 +++++++++++++++++---------------------- reftable/merged.c | 6 ++--- reftable/merged.h | 6 +++++ reftable/reftable-stack.h | 18 +++++++++++++++ reftable/stack.c | 15 ++++++++++++ 5 files changed, 63 insertions(+), 30 deletions(-)
refs/reftable-backend.c +21 -27
@@ -15,7 +15,6 @@#include "../reftable/reftable-record.h" #include "../reftable/reftable-error.h" #include "../reftable/reftable-iterator.h" -#include "../reftable/reftable-merged.h" #include "../setup.h" #include "../strmap.h" #include "parse.h"
@@ -462,7 +461,6 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ const char *prefix, int flags) { -struct reftable_merged_table *merged_table;struct reftable_ref_iterator *iter;int ret;
@@ -482,9 +480,8 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_if (ret) goto done; - merged_table =reftable_stack_merged_table (stack); - - ret =reftable_merged_table_seek_ref (merged_table, &iter->iter, prefix); +reftable_stack_init_ref_iterator (stack, &iter->iter); + ret =reftable_iterator_seek_ref (&iter->iter, prefix);if (ret) goto done;
@@ -1015,8 +1012,6 @@ static int transaction_update_cmp(const void *a, const void *b)static int write_transaction_table (struct reftable_writer *writer,void *cb_data) {struct write_transaction_table_arg *arg = cb_data; -struct reftable_merged_table *mt = -reftable_stack_merged_table (arg->stack);uint64_t ts =reftable_stack_next_update_index (arg->stack);struct reftable_log_record *logs =NULL ;struct ident_split committer_ident = {0 };
@@ -1051,6 +1046,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_datastruct reftable_log_record log = {0 };struct reftable_iterator it = {0 }; +reftable_stack_init_log_iterator (arg->stack, &it); +/* * When deleting refs we also delete all reflog entries * with them. While it is not strictly required to
@@ -1060,7 +1057,7 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data* Unfortunately, we have no better way than to delete * all reflog entries one by one. */ - ret =reftable_merged_table_seek_log (mt, &it, u->refname); + ret =reftable_iterator_seek_log (&it, u->refname);while (ret ==0 ) {struct reftable_log_record *tombstone;
@@ -1354,7 +1351,6 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data) {struct write_copy_arg *arg = cb_data;uint64_t deletion_ts, creation_ts; -struct reftable_merged_table *mt =reftable_stack_merged_table (arg->stack);struct reftable_ref_record old_ref = {0 }, refs[2 ] = {0 };struct reftable_log_record old_log = {0 }, *logs =NULL ;struct reftable_iterator it = {0 };
@@ -1488,7 +1484,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)* copy over all log entries from the old reflog. Last but not least, * when renaming we also have to delete all the old reflog entries. */ - ret =reftable_merged_table_seek_log (mt, &it, arg->oldname); +reftable_stack_init_log_iterator (arg->stack, &it); + ret =reftable_iterator_seek_log (&it, arg->oldname);if (ret <0 ) goto done;
@@ -1694,7 +1691,6 @@ static struct ref_iterator_vtable reftable_reflog_iterator_vtable = {static struct reftable_reflog_iterator *reflog_iterator_for_stack (struct reftable_ref_store *refs,struct reftable_stack *stack) { -struct reftable_merged_table *merged_table;struct reftable_reflog_iterator *iter;int ret;
@@ -1711,9 +1707,8 @@ static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftablif (ret <0 ) goto done; - merged_table =reftable_stack_merged_table (stack); - - ret =reftable_merged_table_seek_log (merged_table, &iter->iter,"" ); +reftable_stack_init_log_iterator (stack, &iter->iter); + ret =reftable_iterator_seek_log (&iter->iter,"" );if (ret <0 ) goto done;
@@ -1771,7 +1766,6 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_READ ,"for_each_reflog_ent_reverse" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =NULL ;struct reftable_log_record log = {0 };struct reftable_iterator it = {0 };int ret;
@@ -1779,8 +1773,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,if (refs->err <0 )return refs->err; - mt =reftable_stack_merged_table (stack); - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + ret =reftable_iterator_seek_log (&it, refname);while (!ret) { ret =reftable_iterator_next_log (&it, &log);if (ret <0 )
@@ -1808,7 +1802,6 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_READ ,"for_each_reflog_ent" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =NULL ;struct reftable_log_record *logs =NULL ;struct reftable_iterator it = {0 };size_t logs_alloc =0 , logs_nr =0 , i;
@@ -1817,8 +1810,8 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,if (refs->err <0 )return refs->err; - mt =reftable_stack_merged_table (stack); - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + ret =reftable_iterator_seek_log (&it, refname);while (!ret) {struct reftable_log_record log = {0 };
@@ -1855,7 +1848,6 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_READ ,"reflog_exists" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =reftable_stack_merged_table (stack);struct reftable_log_record log = {0 };struct reftable_iterator it = {0 };int ret;
@@ -1868,7 +1860,8 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,if (ret <0 ) goto done; - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + ret =reftable_iterator_seek_log (&it, refname);if (ret <0 ) goto done;
@@ -1966,8 +1959,6 @@ struct write_reflog_delete_arg {static int write_reflog_delete_table (struct reftable_writer *writer,void *cb_data) {struct write_reflog_delete_arg *arg = cb_data; -struct reftable_merged_table *mt = -reftable_stack_merged_table (arg->stack);struct reftable_log_record log = {0 }, tombstone = {0 };struct reftable_iterator it = {0 };uint64_t ts =reftable_stack_next_update_index (arg->stack);
@@ -1975,12 +1966,14 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_dareftable_writer_set_limits (writer, ts, ts); +reftable_stack_init_log_iterator (arg->stack, &it); +/* * In order to delete a table we need to delete all reflog entries one * by one. This is inefficient, but the reftable format does not have a * better marker right now. */ - ret =reftable_merged_table_seek_log (mt, &it, arg->refname); + ret =reftable_iterator_seek_log (&it, arg->refname);while (ret ==0 ) { ret =reftable_iterator_next_log (&it, &log);if (ret <0 )
@@ -2116,7 +2109,6 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,struct reftable_ref_store *refs =reftable_be_downcast (ref_store,REF_STORE_WRITE ,"reflog_expire" );struct reftable_stack *stack =stack_for (refs, refname, &refname); -struct reftable_merged_table *mt =reftable_stack_merged_table (stack);struct reftable_log_record *logs =NULL ;struct reftable_log_record *rewritten =NULL ;struct reftable_ref_record ref_record = {0 };
@@ -2135,7 +2127,9 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,if (ret <0 ) goto done; - ret =reftable_merged_table_seek_log (mt, &it, refname); +reftable_stack_init_log_iterator (stack, &it); + + ret =reftable_iterator_seek_log (&it, refname);if (ret <0 ) goto done;
reftable/merged.c +3 -3
@@ -253,9 +253,9 @@ reftable_merged_table_min_update_index(struct reftable_merged_table *mt)return mt->min; } -static void merged_table_init_iter (struct reftable_merged_table *mt, -struct reftable_iterator *it, -uint8_t typ) +void merged_table_init_iter (struct reftable_merged_table *mt, +struct reftable_iterator *it, +uint8_t typ) {struct merged_iter *mi =reftable_malloc (sizeof (*mi));merged_iter_init (mi, mt, typ);
reftable/merged.h +6 -0
@@ -26,4 +26,10 @@ struct reftable_merged_table {void merged_table_release (struct reftable_merged_table *mt); +struct reftable_iterator ; + +void merged_table_init_iter (struct reftable_merged_table *mt, +struct reftable_iterator *it, +uint8_t typ); +#endif
reftable/reftable-stack.h +18 -0
@@ -66,6 +66,24 @@ int reftable_stack_add(struct reftable_stack *st, void *write_arg), void *write_arg); +struct reftable_iterator ; + +/* +* Initialize an iterator for the merged tables contained in the stack that can +* be used to iterate through refs. The iterator is valid until the next reload +* or write. +*/ +void reftable_stack_init_ref_iterator (struct reftable_stack *st, +struct reftable_iterator *it); + +/* +* Initialize an iterator for the merged tables contained in the stack that can +* be used to iterate through logs. The iterator is valid until the next reload +* or write. +*/ +void reftable_stack_init_log_iterator (struct reftable_stack *st, +struct reftable_iterator *it); +/* returns the merged_table for seeking. This table is valid until the * next write or reload, and should not be closed or deleted. */
reftable/stack.c +15 -0
@@ -10,6 +10,7 @@ license that can be found in the LICENSE file or at#include "../write-or-die.h" #include "system.h" +#include "constants.h" #include "merged.h" #include "reader.h" #include "reftable-error.h"
@@ -130,6 +131,20 @@ int read_lines(const char *filename, char ***namesp)return err; } +void reftable_stack_init_ref_iterator (struct reftable_stack *st, +struct reftable_iterator *it) +{ +merged_table_init_iter (reftable_stack_merged_table (st), + it,BLOCK_TYPE_REF ); +} + +void reftable_stack_init_log_iterator (struct reftable_stack *st, +struct reftable_iterator *it) +{ +merged_table_init_iter (reftable_stack_merged_table (st), + it,BLOCK_TYPE_LOG ); +} +struct reftable_merged_table *reftable_stack_merged_table (struct reftable_stack *st) {
Signature · 1 line
2.45.GIT
PATCH v2 13/13 reftable/merged: adapt interface to allow reuse of iterators
In reply to Patrick SteinhardtRefactor the interfaces exposed by struct reftable_merged_table and struct merged_iter such that they support iterator reuse. This is done by separating initialization of the iterator and seeking on it.
--- reftable/merged.c | 35 ----------------------------------- reftable/merged_test.c | 19 +++++++++++++------ reftable/reftable-merged.h | 15 --------------- reftable/stack.c | 14 +++++++++----- 4 files changed, 22 insertions(+), 61 deletions(-)
reftable/merged.c +0 -35
@@ -262,41 +262,6 @@ void merged_table_init_iter(struct reftable_merged_table *mt,iterator_from_merged_iter (it, mi); } -int reftable_merged_table_seek_ref (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name) -{ -struct reftable_record rec = { - .type =BLOCK_TYPE_REF , - .u.ref = { - .refname = (char *)name, - }, - }; -merged_table_init_iter (mt, it,BLOCK_TYPE_REF ); -return iterator_seek (it, &rec); -} - -int reftable_merged_table_seek_log_at (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name,uint64_t update_index) -{ -struct reftable_record rec = { .type =BLOCK_TYPE_LOG , - .u.log = { - .refname = (char *)name, - .update_index = update_index, - } }; -merged_table_init_iter (mt, it,BLOCK_TYPE_LOG ); -return iterator_seek (it, &rec); -} - -int reftable_merged_table_seek_log (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name) -{ -uint64_t max = ~((uint64_t )0 ); -return reftable_merged_table_seek_log_at (mt, it, name, max); -} -uint32_t reftable_merged_table_hash_id (struct reftable_merged_table *mt) {return mt->hash_id;
reftable/merged_test.c +13 -6
@@ -12,6 +12,7 @@ license that can be found in the LICENSE file or at#include "basics.h" #include "blocksource.h" +#include "constants.h" #include "reader.h" #include "record.h" #include "test_framework.h"
@@ -145,7 +146,10 @@ static void test_merged_between(void)int i;struct reftable_ref_record ref = {NULL };struct reftable_iterator it = {NULL }; -int err =reftable_merged_table_seek_ref (mt, &it,"a" ); +int err; + +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + err =reftable_iterator_seek_ref (&it,"a" );EXPECT_ERR (err); err =reftable_iterator_next_ref (&it, &ref);
@@ -217,14 +221,15 @@ static void test_merged(void)struct reftable_reader **readers =NULL ;struct reftable_merged_table *mt =merged_table_from_records (refs, &bs, &readers, sizes, bufs,3 ); -struct reftable_iterator it = {NULL }; -int err =reftable_merged_table_seek_ref (mt, &it,"a" ); +int err;struct reftable_ref_record *out =NULL ;size_t len =0 ;size_t cap =0 ;int i =0 ; +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + err =reftable_iterator_seek_ref (&it,"a" );EXPECT_ERR (err);EXPECT (reftable_merged_table_hash_id (mt) ==GIT_SHA1_FORMAT_ID );EXPECT (reftable_merged_table_min_update_index (mt) ==1 );
@@ -348,14 +353,15 @@ static void test_merged_logs(void)struct reftable_reader **readers =NULL ;struct reftable_merged_table *mt =merged_table_from_log_records ( logs, &bs, &readers, sizes, bufs,3 ); -struct reftable_iterator it = {NULL }; -int err =reftable_merged_table_seek_log (mt, &it,"a" ); +int err;struct reftable_log_record *out =NULL ;size_t len =0 ;size_t cap =0 ;int i =0 ; +merged_table_init_iter (mt, &it,BLOCK_TYPE_LOG ); + err =reftable_iterator_seek_log (&it,"a" );EXPECT_ERR (err);EXPECT (reftable_merged_table_hash_id (mt) ==GIT_SHA1_FORMAT_ID );EXPECT (reftable_merged_table_min_update_index (mt) ==1 );
@@ -377,7 +383,8 @@ static void test_merged_logs(void) GIT_SHA1_RAWSZ)); } - err =reftable_merged_table_seek_log_at (mt, &it,"a" ,2 ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_LOG ); + err =reftable_iterator_seek_log_at (&it,"a" ,2 );EXPECT_ERR (err);reftable_log_record_release (&out[0 ]); err =reftable_iterator_next_log (&it, &out[0 ]);
reftable/reftable-merged.h +0 -15
@@ -36,21 +36,6 @@ int reftable_new_merged_table(struct reftable_merged_table **dest, struct reftable_table *stack, size_t n, uint32_t hash_id); -/* returns an iterator positioned just before 'name' */ -int reftable_merged_table_seek_ref (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name); - -/* returns an iterator for log entry, at given update_index */ -int reftable_merged_table_seek_log_at (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name,uint64_t update_index); - -/* like reftable_merged_table_seek_log_at but look for the newest entry. */ -int reftable_merged_table_seek_log (struct reftable_merged_table *mt, -struct reftable_iterator *it, -const char *name); -/* returns the max update_index covered by this merged table. */ uint64_t reftable_merged_table_max_update_index (struct reftable_merged_table *mt);
reftable/stack.c +9 -5
@@ -925,7 +925,8 @@ static int stack_write_compact(struct reftable_stack *st, goto done; } - err =reftable_merged_table_seek_ref (mt, &it,"" ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + err =reftable_iterator_seek_ref (&it,"" );if (err <0 ) goto done;
@@ -949,7 +950,8 @@ static int stack_write_compact(struct reftable_stack *st, }reftable_iterator_destroy (&it); - err =reftable_merged_table_seek_log (mt, &it,"" ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_LOG ); + err =reftable_iterator_seek_log (&it,"" );if (err <0 ) goto done;
@@ -1340,9 +1342,11 @@ int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,int reftable_stack_read_log (struct reftable_stack *st,const char *refname,struct reftable_log_record *log) { -struct reftable_iterator it = {NULL }; -struct reftable_merged_table *mt =reftable_stack_merged_table (st); -int err =reftable_merged_table_seek_log (mt, &it, refname); +struct reftable_iterator it = {0 }; +int err; + +reftable_stack_init_log_iterator (st, &it); + err =reftable_iterator_seek_log (&it, refname);if (err) goto done;
Signature · 1 line
2.45.GIT
Quoted 11 lines · Patrick Steinhardt
Hi,
this is the second version of my patch series that prepares the reftable iterators to become re-seekable. These refactorings will eventually allow us to reuse data structures by iterators and optimize for certain cases.
Changes compared to v1:
- Various fixes to commit messages.
Quoted 7 lines
- Fixed a copy & pasted comment to refer to logs instead of refs.
The series continues to build on top of ps/reftable-write-optim. There is a merge conflict with the in-flight ps/reftable-write-options, but given that this series has not yet been merged to next and because Junio has already resolved the conflict in "seen" I decided to not pull it in as an additional dependency.
Thanks Patrick! From the range-diff, this version looks good to me :)
-Justin
Hello,
Quoted 19 lines · Patrick Steinhardt
Hi,
this is the second version of my patch series that prepares the reftable iterators to become re-seekable. These refactorings will eventually allow us to reuse data structures by iterators and optimize for certain cases.
Changes compared to v1:
- Various fixes to commit messages.
- Fixed a copy & pasted comment to refer to logs instead of refs.
The series continues to build on top of ps/reftable-write-optim. There is a merge conflict with the in-flight ps/reftable-write-options, but given that this series has not yet been merged to next and because Junio has already resolved the conflict in "seen" I decided to not pull it in as an additional dependency.
Quoted 3 lines
Thanks!
Patrick
I didn't review the earlier version. I did go through the patches in this version, I only have a nit in the first patch, not worth a reroll. Thanks for the series, I have nothing more to add.
Karthik
Quoted 22 lines · Karthik Nayak
Hello,
Quoted 19 lines · Patrick Steinhardt
Hi,
this is the second version of my patch series that prepares the reftable iterators to become re-seekable. These refactorings will eventually allow us to reuse data structures by iterators and optimize for certain cases.
Changes compared to v1:
- Various fixes to commit messages.
- Fixed a copy & pasted comment to refer to logs instead of refs.
The series continues to build on top of ps/reftable-write-optim. There is a merge conflict with the in-flight ps/reftable-write-options, but given that this series has not yet been merged to next and because Junio has already resolved the conflict in "seen" I decided to not pull it in as an additional dependency.
Quoted 7 lines
Quoted 3 lines
Thanks!
Patrick
I didn't review the earlier version. I did go through the patches in this version, I only have a nit in the first patch, not worth a reroll. Thanks for the series, I have nothing more to add.
Thanks!
Patrick