1 files changed, 240 insertions, 195 deletions
diff --git a/reftable/reader.c b/reftable/reader.c
index 2663b03938..29c99e2269 100644
--- a/reftable/reader.c
+++ b/reftable/reader.c
@@ -220,21 +220,18 @@ 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;
 };
-#define TABLE_ITER_INIT { \
-	.bi = BLOCK_ITER_INIT \
-}
 
-static void table_iter_copy_from(struct table_iter *dest,
-				 struct table_iter *src)
+static int table_iter_init(struct table_iter *ti, struct reftable_reader *r)
 {
-	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);
+	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,
@@ -250,14 +247,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;
-	}
-	reftable_block_done(&ti->bi.br->block);
-	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 +312,27 @@ done:
 	return err;
 }
 
-static int table_iter_next_block(struct table_iter *dest,
-				 struct table_iter *src)
+static void table_iter_close(struct table_iter *ti)
 {
-	uint64_t next_block_off = src->block_off + src->bi.br->full_block_size;
-	struct block_reader br = { 0 };
-	int err = 0;
+	table_iter_block_done(ti);
+	block_iter_close(&ti->bi);
+}
 
-	dest->r = src->r;
-	dest->typ = src->typ;
-	dest->block_off = next_block_off;
+static int table_iter_next_block(struct table_iter *ti)
+{
+	uint64_t next_block_off = ti->block_off + ti->br.full_block_size;
+	int err;
 
-	err = reader_init_block_reader(src->r, &br, next_block_off, src->typ);
-	if (err > 0) {
-		dest->is_finished = 1;
-		return 1;
-	}
-	if (err != 0)
+	err = reader_init_block_reader(ti->r, &ti->br, next_block_off, ti->typ);
+	if (err > 0)
+		ti->is_finished = 1;
+	if (err)
 		return err;
-	else {
-		struct block_reader *brp =
-			reftable_malloc(sizeof(struct block_reader));
-		*brp = br;
 
-		dest->is_finished = 0;
-		block_reader_start(brp, &dest->bi);
-	}
+	ti->block_off = next_block_off;
+	ti->is_finished = 0;
+	block_iter_seek_start(&ti->bi, &ti->br);
+
 	return 0;
 }
 
@@ -356,79 +342,50 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)
 		return REFTABLE_API_ERROR;
 
 	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;
-		}
 
-		err = table_iter_next_block(&next, ti);
-		if (err != 0) {
+		/*
+		 * 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(ti);
+		if (err) {
 			ti->is_finished = 1;
-		}
-		table_iter_block_done(ti);
-		if (err != 0) {
 			return err;
 		}
-		table_iter_copy_from(ti, &next);
-		block_iter_close(&next.bi);
 	}
 }
 
-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)
-{
-	struct table_iter *ti = p;
-	table_iter_block_done(ti);
-	block_iter_close(&ti->bi);
-}
-
-static struct reftable_iterator_vtable table_iter_vtable = {
-	.next = &table_iter_next_void,
-	.close = &table_iter_close,
-};
-
-static void iterator_from_table_iter(struct reftable_iterator *it,
-				     struct table_iter *ti)
-{
-	assert(!it->ops);
-	it->iter_arg = ti;
-	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, 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(ti->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_reader_start(brp, &ti->bi);
+	block_iter_seek_start(&ti->bi, &ti->br);
 	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, 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;
@@ -438,31 +395,60 @@ 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, 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;
-	struct table_iter next = TABLE_ITER_INIT;
 	struct reftable_record rec;
-	int err = -1;
+	int err;
 
 	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) {
-		err = table_iter_next_block(&next, ti);
+		struct table_iter next = *ti;
+
+		/*
+		 * We must be careful to not modify underlying data of `ti`
+		 * because we may find that `next` does not contain our desired
+		 * block, but that `ti` does. In that case, we would discard
+		 * `next` and continue with `ti`.
+		 *
+		 * This also means that we cannot reuse allocated memory for
+		 * `next` here. While it would be great if we could, it should
+		 * in practice not be too bad given that we should only ever
+		 * end up doing linear seeks with at most three blocks. As soon
+		 * as we have more than three blocks we would have an index, so
+		 * we would not do a linear search there anymore.
+		 */
+		memset(&next.br.block, 0, sizeof(next.br.block));
+		next.br.zstream = NULL;
+		next.br.uncompressed_data = NULL;
+		next.br.uncompressed_cap = 0;
+
+		err = table_iter_next_block(&next);
 		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;
 
@@ -472,25 +458,28 @@ 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(&ti->bi, &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);
 	return err;
 }
 
-static int reader_seek_indexed(struct reftable_reader *r,
-			       struct reftable_iterator *it,
-			       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 }
@@ -499,14 +488,9 @@ 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 next = TABLE_ITER_INIT;
-	int err = 0;
+	int err;
 
 	reftable_record_key(rec, &want_index.u.idx.last_key);
-	err = reader_start(r, &index_iter, reftable_record_type(rec), 1);
-	if (err < 0)
-		goto done;
 
 	/*
 	 * The index may consist of multiple levels, where each level may have
@@ -514,7 +498,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 = table_iter_seek_linear(ti, &want_index);
 	if (err < 0)
 		goto done;
 
@@ -540,119 +524,113 @@ 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);
-		table_iter_block_done(&index_iter);
+		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 = table_iter_seek_to(ti, index_result.u.idx.offset, 0);
 		if (err != 0)
 			goto done;
 
-		err = block_iter_seek(&next.bi, &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_copy_from(&index_iter, &next);
 	}
 
-	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);
-		iterator_from_table_iter(it, malloced);
-	}
 done:
-	block_iter_close(&next.bi);
-	table_iter_close(&index_iter);
 	reftable_record_release(&want_index);
 	reftable_record_release(&index_result);
 	return err;
 }
 
-static int reader_seek_internal(struct reftable_reader *r,
-				struct reftable_iterator *it,
-				struct reftable_record *rec)
+static int table_iter_seek(struct table_iter *ti,
+			   struct reftable_record *want)
 {
-	struct reftable_reader_offsets *offs =
-		reader_offsets_for(r, reftable_record_type(rec));
-	uint64_t idx = offs->index_offset;
-	struct table_iter ti = TABLE_ITER_INIT;
-	int err = 0;
-	if (idx > 0)
-		return reader_seek_indexed(r, it, rec);
+	uint8_t typ = reftable_record_type(want);
+	struct reftable_reader_offsets *offs = reader_offsets_for(ti->r, typ);
+	int err;
 
-	err = reader_start(r, &ti, reftable_record_type(rec), 0);
+	err = table_iter_seek_start(ti, reftable_record_type(want),
+				    !!offs->index_offset);
 	if (err < 0)
-		return err;
-	err = reader_seek_linear(&ti, rec);
-	if (err < 0)
-		return err;
-	else {
-		struct table_iter *p =
-			reftable_malloc(sizeof(struct table_iter));
-		*p = ti;
-		iterator_from_table_iter(it, p);
-	}
+		goto out;
 
-	return 0;
+	if (offs->index_offset)
+		err = table_iter_seek_indexed(ti, want);
+	else
+		err = table_iter_seek_linear(ti, want);
+	if (err)
+		goto out;
+
+out:
+	return err;
 }
 
-static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,
-		       struct reftable_record *rec)
+static int table_iter_seek_void(void *ti, struct reftable_record *want)
 {
-	uint8_t typ = reftable_record_type(rec);
+	return table_iter_seek(ti, want);
+}
 
-	struct reftable_reader_offsets *offs = reader_offsets_for(r, typ);
-	if (!offs->is_present) {
-		iterator_set_empty(it);
-		return 0;
-	}
+static int table_iter_next_void(void *ti, struct reftable_record *rec)
+{
+	return table_iter_next(ti, rec);
+}
 
-	return reader_seek_internal(r, it, rec);
+static void table_iter_close_void(void *ti)
+{
+	table_iter_close(ti);
 }
 
-int reftable_reader_seek_ref(struct reftable_reader *r,
-			     struct reftable_iterator *it, const char *name)
+static struct reftable_iterator_vtable table_iter_vtable = {
+	.seek = &table_iter_seek_void,
+	.next = &table_iter_next_void,
+	.close = &table_iter_close_void,
+};
+
+static void iterator_from_table_iter(struct reftable_iterator *it,
+				     struct table_iter *ti)
 {
-	struct reftable_record rec = {
-		.type = BLOCK_TYPE_REF,
-		.u.ref = {
-			.refname = (char *)name,
-		},
-	};
-	return reader_seek(r, it, &rec);
+	assert(!it->ops);
+	it->iter_arg = ti;
+	it->ops = &table_iter_vtable;
+}
+
+static void reader_init_iter(struct reftable_reader *r,
+			     struct reftable_iterator *it,
+			     uint8_t typ)
+{
+	struct reftable_reader_offsets *offs = reader_offsets_for(r, typ);
+
+	if (offs->is_present) {
+		struct table_iter *ti;
+		REFTABLE_ALLOC_ARRAY(ti, 1);
+		table_iter_init(ti, r);
+		iterator_from_table_iter(it, ti);
+	} else {
+		iterator_set_empty(it);
+	}
 }
 
-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_ref_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,
-				       } };
-	return reader_seek(r, it, &rec);
+	reader_init_iter(r, it, BLOCK_TYPE_REF);
 }
 
-int reftable_reader_seek_log(struct reftable_reader *r,
-			     struct reftable_iterator *it, const char *name)
+void reftable_reader_init_log_iterator(struct reftable_reader *r,
+				       struct reftable_iterator *it)
 {
-	uint64_t max = ~((uint64_t)0);
-	return reftable_reader_seek_log_at(r, it, name, max);
+	reader_init_iter(r, it, BLOCK_TYPE_LOG);
 }
 
 void reader_close(struct reftable_reader *r)
@@ -703,7 +681,8 @@ static int reftable_reader_refs_for_indexed(struct reftable_reader *r,
 	struct indexed_table_ref_iter *itr = NULL;
 
 	/* Look through the reverse index. */
-	err = reader_seek(r, &oit, &want);
+	reader_init_iter(r, &oit, BLOCK_TYPE_OBJ);
+	err = iterator_seek(&oit, &want);
 	if (err != 0)
 		goto done;
 
@@ -738,15 +717,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 = reader_start(r, ti, 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;
@@ -784,10 +763,11 @@ uint64_t reftable_reader_min_update_index(struct reftable_reader *r)
 
 /* generic table interface. */
 
-static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,
-				     struct reftable_record *rec)
+static void reftable_reader_init_iter_void(void *tab,
+					   struct reftable_iterator *it,
+					   uint8_t typ)
 {
-	return reader_seek(tab, it, rec);
+	reader_init_iter(tab, it, typ);
 }
 
 static uint32_t reftable_reader_hash_id_void(void *tab)
@@ -806,7 +786,7 @@ static uint64_t reftable_reader_max_update_index_void(void *tab)
 }
 
 static struct reftable_table_vtable reader_vtable = {
-	.seek_record = reftable_reader_seek_void,
+	.init_iter = reftable_reader_init_iter_void,
 	.hash_id = reftable_reader_hash_id_void,
 	.min_update_index = reftable_reader_min_update_index_void,
 	.max_update_index = reftable_reader_max_update_index_void,
@@ -840,3 +820,68 @@ done:
 	reftable_reader_free(r);
 	return err;
 }
+
+int reftable_reader_print_blocks(const char *tablename)
+{
+	struct {
+		const char *name;
+		int type;
+	} sections[] = {
+		{
+			.name = "ref",
+			.type = BLOCK_TYPE_REF,
+		},
+		{
+			.name = "obj",
+			.type = BLOCK_TYPE_OBJ,
+		},
+		{
+			.name = "log",
+			.type = BLOCK_TYPE_LOG,
+		},
+	};
+	struct reftable_block_source src = { 0 };
+	struct reftable_reader *r = NULL;
+	struct table_iter ti = { 0 };
+	size_t i;
+	int err;
+
+	err = reftable_block_source_from_file(&src, tablename);
+	if (err < 0)
+		goto done;
+
+	err = reftable_new_reader(&r, &src, tablename);
+	if (err < 0)
+		goto done;
+
+	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);
+		if (err < 0)
+			goto done;
+		if (err > 0)
+			continue;
+
+		printf("%s:\n", sections[i].name);
+
+		while (1) {
+			printf("  - length: %u\n", ti.br.block_len);
+			printf("    restarts: %u\n", ti.br.restart_count);
+
+			err = table_iter_next_block(&ti);
+			if (err < 0)
+				goto done;
+			if (err > 0)
+				break;
+		}
+	}
+
+done:
+	reftable_reader_free(r);
+	table_iter_close(&ti);
+	return err;
+}