diff options
Diffstat (limited to 'reftable/reader.c')
| -rw-r--r-- | reftable/reader.c | 76 |
1 files changed, 55 insertions, 21 deletions
diff --git a/reftable/reader.c b/reftable/reader.c index b4db23ce18..b113daab77 100644 --- a/reftable/reader.c +++ b/reftable/reader.c @@ -16,7 +16,6 @@ https://developers.google.com/open-source/licenses/bsd #include "record.h" #include "reftable-error.h" #include "reftable-generic.h" -#include "tree.h" uint64_t block_source_size(struct reftable_block_source *source) { @@ -224,10 +223,9 @@ struct table_iter { struct block_iter bi; int is_finished; }; -#define TABLE_ITER_INIT \ - { \ - .bi = {.last_key = STRBUF_INIT } \ - } +#define TABLE_ITER_INIT { \ + .bi = BLOCK_ITER_INIT \ +} static void table_iter_copy_from(struct table_iter *dest, struct table_iter *src) @@ -359,24 +357,32 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec) while (1) { struct table_iter next = TABLE_ITER_INIT; - int err = 0; - if (ti->is_finished) { + int err; + + if (ti->is_finished) return 1; - } + /* + * Check whether the current block still has more records. If + * so, return it. If the iterator returns positive then the + * current block has been exhausted. + */ err = table_iter_next_in_block(ti, rec); - if (err <= 0) { + if (err <= 0) return err; - } + /* + * Otherwise, we need to continue to the next block in the + * table and retry. If there are no more blocks then the + * iterator is drained. + */ err = table_iter_next_block(&next, ti); - if (err != 0) { - ti->is_finished = 1; - } table_iter_block_done(ti); - if (err != 0) { + if (err) { + ti->is_finished = 1; return err; } + table_iter_copy_from(ti, &next); block_iter_close(&next.bi); } @@ -446,13 +452,13 @@ static int reader_start(struct reftable_reader *r, struct table_iter *ti, static int reader_seek_linear(struct table_iter *ti, struct reftable_record *want) { - struct reftable_record rec = - reftable_new_record(reftable_record_type(want)); struct strbuf want_key = STRBUF_INIT; struct strbuf got_key = STRBUF_INIT; struct table_iter next = TABLE_ITER_INIT; + struct reftable_record rec; int err = -1; + reftable_record_init(&rec, reftable_record_type(want)); reftable_record_key(want, &want_key); while (1) { @@ -510,8 +516,38 @@ static int reader_seek_indexed(struct reftable_reader *r, if (err < 0) goto done; + /* + * The index may consist of multiple levels, where each level may have + * multiple index blocks. We start by doing a linear search in the + * 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); + if (err < 0) + goto done; + + /* + * Traverse down the levels until we find a non-index entry. + */ while (1) { + /* + * In case we seek a record that does not exist the index iter + * will tell us that the iterator is over. This works because + * the last index entry of the current level will contain the + * last key it knows about. So in case our seeked key is larger + * than the last indexed key we know that it won't exist. + * + * There is one subtlety in the layout of the index section + * that makes this work as expected: the highest-level index is + * at end of the section and will point backwards and thus we + * start reading from the end of the index section, not the + * beginning. + * + * If that wasn't the case and the order was reversed then the + * linear seek would seek into the lower levels and traverse + * all levels of the index only to find out that the key does + * not exist. + */ err = table_iter_next(&index_iter, &index_result); table_iter_block_done(&index_iter); if (err != 0) @@ -541,8 +577,7 @@ static int reader_seek_indexed(struct reftable_reader *r, if (err == 0) { struct table_iter empty = TABLE_ITER_INIT; - struct table_iter *malloced = - reftable_calloc(sizeof(struct table_iter)); + struct table_iter *malloced = reftable_calloc(1, sizeof(*malloced)); *malloced = empty; table_iter_copy_from(malloced, &next); iterator_from_table_iter(it, malloced); @@ -637,8 +672,7 @@ void reader_close(struct reftable_reader *r) int reftable_new_reader(struct reftable_reader **p, struct reftable_block_source *src, char const *name) { - struct reftable_reader *rd = - reftable_calloc(sizeof(struct reftable_reader)); + struct reftable_reader *rd = reftable_calloc(1, sizeof(*rd)); int err = init_reader(rd, src, name); if (err == 0) { *p = rd; @@ -713,7 +747,7 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r, uint8_t *oid) { struct table_iter ti_empty = TABLE_ITER_INIT; - struct table_iter *ti = reftable_calloc(sizeof(struct table_iter)); + struct table_iter *ti = reftable_calloc(1, sizeof(*ti)); struct filtering_ref_iterator *filter = NULL; struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT; int oid_len = hash_size(r->hash_id); |