aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--reftable/block.c43
-rw-r--r--reftable/block.h17
-rw-r--r--reftable/reader.c123
3 files changed, 100 insertions, 83 deletions
diff --git a/reftable/block.c b/reftable/block.c
index fe836c21e5..2d8d0668b3 100644
--- a/reftable/block.c
+++ b/reftable/block.c
@@ -261,12 +261,12 @@ void block_reader_release(struct block_reader *br)
reftable_block_done(&br->block);
}
-uint8_t block_reader_type(struct block_reader *r)
+uint8_t block_reader_type(const struct block_reader *r)
{
return r->block.data[r->header_off];
}
-int block_reader_first_key(struct block_reader *br, struct strbuf *key)
+int block_reader_first_key(const struct block_reader *br, struct strbuf *key)
{
int off = br->header_off + 4, n;
struct string_view in = {
@@ -286,14 +286,16 @@ int block_reader_first_key(struct block_reader *br, struct strbuf *key)
return 0;
}
-static uint32_t block_reader_restart_offset(struct block_reader *br, int i)
+static uint32_t block_reader_restart_offset(const struct block_reader *br, int i)
{
return get_be24(br->restart_bytes + 3 * i);
}
-void block_iter_seek_start(struct block_iter *it, struct block_reader *br)
+void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)
{
- it->br = br;
+ it->block = br->block.data;
+ it->block_len = br->block_len;
+ it->hash_size = br->hash_size;
strbuf_reset(&it->last_key);
it->next_off = br->header_off + 4;
}
@@ -301,7 +303,7 @@ void block_iter_seek_start(struct block_iter *it, struct block_reader *br)
struct restart_needle_less_args {
int error;
struct strbuf needle;
- struct block_reader *reader;
+ const struct block_reader *reader;
};
static int restart_needle_less(size_t idx, void *_args)
@@ -340,9 +342,11 @@ static int restart_needle_less(size_t idx, void *_args)
return args->needle.len < suffix_len;
}
-void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)
+void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src)
{
- dest->br = src->br;
+ dest->block = src->block;
+ dest->block_len = src->block_len;
+ dest->hash_size = src->hash_size;
dest->next_off = src->next_off;
strbuf_reset(&dest->last_key);
strbuf_addbuf(&dest->last_key, &src->last_key);
@@ -351,14 +355,14 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)
int block_iter_next(struct block_iter *it, struct reftable_record *rec)
{
struct string_view in = {
- .buf = it->br->block.data + it->next_off,
- .len = it->br->block_len - it->next_off,
+ .buf = (unsigned char *) it->block + it->next_off,
+ .len = it->block_len - it->next_off,
};
struct string_view start = in;
uint8_t extra = 0;
int n = 0;
- if (it->next_off >= it->br->block_len)
+ if (it->next_off >= it->block_len)
return 1;
n = reftable_decode_key(&it->last_key, &extra, in);
@@ -368,7 +372,7 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)
return REFTABLE_FORMAT_ERROR;
string_view_consume(&in, n);
- n = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size,
+ n = reftable_record_decode(rec, it->last_key, extra, in, it->hash_size,
&it->scratch);
if (n < 0)
return -1;
@@ -378,13 +382,22 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)
return 0;
}
+void block_iter_reset(struct block_iter *it)
+{
+ strbuf_reset(&it->last_key);
+ it->next_off = 0;
+ it->block = NULL;
+ it->block_len = 0;
+ it->hash_size = 0;
+}
+
void block_iter_close(struct block_iter *it)
{
strbuf_release(&it->last_key);
strbuf_release(&it->scratch);
}
-int block_iter_seek_key(struct block_iter *it, struct block_reader *br,
+int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,
struct strbuf *want)
{
struct restart_needle_less_args args = {
@@ -436,7 +449,9 @@ int block_iter_seek_key(struct block_iter *it, struct block_reader *br,
it->next_off = block_reader_restart_offset(br, i - 1);
else
it->next_off = br->header_off + 4;
- it->br = br;
+ it->block = br->block.data;
+ it->block_len = br->block_len;
+ it->hash_size = br->hash_size;
reftable_record_init(&rec, block_reader_type(br));
diff --git a/reftable/block.h b/reftable/block.h
index 601a1e0e89..d733d45ee0 100644
--- a/reftable/block.h
+++ b/reftable/block.h
@@ -84,16 +84,18 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,
void block_reader_release(struct block_reader *br);
/* Returns the block type (eg. 'r' for refs) */
-uint8_t block_reader_type(struct block_reader *r);
+uint8_t block_reader_type(const struct block_reader *r);
/* Decodes the first key in the block */
-int block_reader_first_key(struct block_reader *br, struct strbuf *key);
+int block_reader_first_key(const struct block_reader *br, struct strbuf *key);
/* Iterate over entries in a block */
struct block_iter {
/* offset within the block of the next entry to read. */
uint32_t next_off;
- struct block_reader *br;
+ const unsigned char *block;
+ size_t block_len;
+ int hash_size;
/* key for last entry we read. */
struct strbuf last_key;
@@ -106,17 +108,20 @@ struct block_iter {
}
/* Position `it` at start of the block */
-void block_iter_seek_start(struct block_iter *it, struct block_reader *br);
+void block_iter_seek_start(struct block_iter *it, const struct block_reader *br);
/* Position `it` to the `want` key in the block */
-int block_iter_seek_key(struct block_iter *it, struct block_reader *br,
+int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,
struct strbuf *want);
-void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);
+void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src);
/* return < 0 for error, 0 for OK, > 0 for EOF. */
int block_iter_next(struct block_iter *it, struct reftable_record *rec);
+/* Reset the block iterator to pristine state without releasing its memory. */
+void block_iter_reset(struct block_iter *it);
+
/* deallocate memory for `it`. The block reader and its block is left intact. */
void block_iter_close(struct block_iter *it);
diff --git a/reftable/reader.c b/reftable/reader.c
index f925570bf3..b77b639751 100644
--- a/reftable/reader.c
+++ b/reftable/reader.c
@@ -220,6 +220,7 @@ struct table_iter {
struct reftable_reader *r;
uint8_t typ;
uint64_t block_off;
+ struct block_reader br;
struct block_iter bi;
int is_finished;
};
@@ -227,16 +228,6 @@ struct table_iter {
.bi = BLOCK_ITER_INIT \
}
-static void table_iter_copy_from(struct table_iter *dest,
- struct table_iter *src)
-{
- dest->r = src->r;
- dest->typ = src->typ;
- dest->block_off = src->block_off;
- dest->is_finished = src->is_finished;
- block_iter_copy_from(&dest->bi, &src->bi);
-}
-
static int table_iter_next_in_block(struct table_iter *ti,
struct reftable_record *rec)
{
@@ -250,14 +241,8 @@ static int table_iter_next_in_block(struct table_iter *ti,
static void table_iter_block_done(struct table_iter *ti)
{
- if (!ti->bi.br) {
- return;
- }
- block_reader_release(ti->bi.br);
- FREE_AND_NULL(ti->bi.br);
-
- ti->bi.last_key.len = 0;
- ti->bi.next_off = 0;
+ block_reader_release(&ti->br);
+ block_iter_reset(&ti->bi);
}
static int32_t extract_block_size(uint8_t *data, uint8_t *typ, uint64_t off,
@@ -321,32 +306,33 @@ done:
return err;
}
+static void table_iter_close(struct table_iter *ti)
+{
+ table_iter_block_done(ti);
+ block_iter_close(&ti->bi);
+}
+
static int table_iter_next_block(struct table_iter *dest,
struct table_iter *src)
{
- uint64_t next_block_off = src->block_off + src->bi.br->full_block_size;
- struct block_reader br = { 0 };
- int err = 0;
+ uint64_t next_block_off = src->block_off + src->br.full_block_size;
+ int err;
dest->r = src->r;
dest->typ = src->typ;
dest->block_off = next_block_off;
- err = reader_init_block_reader(src->r, &br, next_block_off, src->typ);
- if (err > 0) {
+ err = reader_init_block_reader(src->r, &dest->br, next_block_off, src->typ);
+ if (err > 0)
dest->is_finished = 1;
- return 1;
- }
- if (err != 0)
+ if (err) {
+ table_iter_block_done(dest);
return err;
- else {
- struct block_reader *brp =
- reftable_malloc(sizeof(struct block_reader));
- *brp = br;
-
- dest->is_finished = 0;
- block_iter_seek_start(&dest->bi, brp);
}
+
+ dest->is_finished = 0;
+ block_iter_seek_start(&dest->bi, &dest->br);
+
return 0;
}
@@ -377,14 +363,13 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)
* iterator is drained.
*/
err = table_iter_next_block(&next, ti);
- table_iter_block_done(ti);
if (err) {
ti->is_finished = 1;
return err;
}
- table_iter_copy_from(ti, &next);
- block_iter_close(&next.bi);
+ table_iter_close(ti);
+ *ti = next;
}
}
@@ -393,16 +378,14 @@ static int table_iter_next_void(void *ti, struct reftable_record *rec)
return table_iter_next(ti, rec);
}
-static void table_iter_close(void *p)
+static void table_iter_close_void(void *ti)
{
- struct table_iter *ti = p;
- table_iter_block_done(ti);
- block_iter_close(&ti->bi);
+ table_iter_close(ti);
}
static struct reftable_iterator_vtable table_iter_vtable = {
.next = &table_iter_next_void,
- .close = &table_iter_close,
+ .close = &table_iter_close_void,
};
static void iterator_from_table_iter(struct reftable_iterator *it,
@@ -417,19 +400,16 @@ static int reader_table_iter_at(struct reftable_reader *r,
struct table_iter *ti, uint64_t off,
uint8_t typ)
{
- struct block_reader br = { 0 };
- struct block_reader *brp = NULL;
+ int err;
- int err = reader_init_block_reader(r, &br, off, typ);
+ err = reader_init_block_reader(r, &ti->br, off, typ);
if (err != 0)
return err;
- brp = reftable_malloc(sizeof(struct block_reader));
- *brp = br;
ti->r = r;
- ti->typ = block_reader_type(brp);
+ ti->typ = block_reader_type(&ti->br);
ti->block_off = off;
- block_iter_seek_start(&ti->bi, brp);
+ block_iter_seek_start(&ti->bi, &ti->br);
return 0;
}
@@ -454,23 +434,34 @@ static int reader_seek_linear(struct table_iter *ti,
{
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);
+ /*
+ * First we need to locate the block that must contain our record. To
+ * do so we scan through blocks linearly until we find the first block
+ * whose first key is bigger than our wanted key. Once we have found
+ * that block we know that the key must be contained in the preceding
+ * block.
+ *
+ * This algorithm is somewhat unfortunate because it means that we
+ * always have to seek one block too far and then back up. But as we
+ * can only decode the _first_ key of a block but not its _last_ key we
+ * have no other way to do this.
+ */
while (1) {
+ struct table_iter next = TABLE_ITER_INIT;
+
err = table_iter_next_block(&next, ti);
if (err < 0)
goto done;
-
- if (err > 0) {
+ if (err > 0)
break;
- }
- err = block_reader_first_key(next.bi.br, &got_key);
+ err = block_reader_first_key(&next.br, &got_key);
if (err < 0)
goto done;
@@ -480,16 +471,20 @@ static int reader_seek_linear(struct table_iter *ti,
}
table_iter_block_done(ti);
- table_iter_copy_from(ti, &next);
+ *ti = next;
}
- err = block_iter_seek_key(&ti->bi, ti->bi.br, &want_key);
+ /*
+ * We have located the block that must contain our record, so we seek
+ * the wanted key inside of it. If the block does not contain our key
+ * we know that the corresponding record does not exist.
+ */
+ err = block_iter_seek_key(&ti->bi, &ti->br, &want_key);
if (err < 0)
goto done;
err = 0;
done:
- block_iter_close(&next.bi);
reftable_record_release(&rec);
strbuf_release(&want_key);
strbuf_release(&got_key);
@@ -508,6 +503,7 @@ static int reader_seek_indexed(struct reftable_reader *r,
.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;
int err = 0;
@@ -549,7 +545,6 @@ static int reader_seek_indexed(struct reftable_reader *r,
* not exist.
*/
err = table_iter_next(&index_iter, &index_result);
- table_iter_block_done(&index_iter);
if (err != 0)
goto done;
@@ -558,7 +553,7 @@ static int reader_seek_indexed(struct reftable_reader *r,
if (err != 0)
goto done;
- err = block_iter_seek_key(&next.bi, next.bi.br, &want_index.u.idx.last_key);
+ err = block_iter_seek_key(&next.bi, &next.br, &want_index.u.idx.last_key);
if (err < 0)
goto done;
@@ -572,18 +567,20 @@ static int reader_seek_indexed(struct reftable_reader *r,
break;
}
- table_iter_copy_from(&index_iter, &next);
+ table_iter_close(&index_iter);
+ index_iter = next;
+ next = empty;
}
if (err == 0) {
- struct table_iter empty = TABLE_ITER_INIT;
struct table_iter *malloced = reftable_calloc(1, sizeof(*malloced));
- *malloced = empty;
- table_iter_copy_from(malloced, &next);
+ *malloced = next;
+ next = empty;
iterator_from_table_iter(it, malloced);
}
+
done:
- block_iter_close(&next.bi);
+ table_iter_close(&next);
table_iter_close(&index_iter);
reftable_record_release(&want_index);
reftable_record_release(&index_result);
generated by cgit 1.2.3-korg (git 2.39.0) at 2024-05-23 21:53:40 +0000