git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 11/16] reftable/block: make block iterators reseekable

From
Justin Tobler <jltobler@gmail.com>
Date
Apr 2, 2025, 21:24 UTC
Message-ID
<5dbbo5wiszgx74ijinu7xkf7ptddoubkzt53sc6cg5ak357fja@x7v2kra4ny32>
In-Reply-To
<20250331-pks-reftable-polishing-v1-11-ebed5247434c@pks.im>
On 25/03/31 10:41AM, Patrick Steinhardt wrote:
> Refactor the block iterators so that initialization and seeking are
> different from one another. This makes the iterator trivially reseekable
> by storing the pointer to the block at initialization time, which we can
> then reuse on ever seek.
s/ever/every/
Show 43 quoted lines
> This refactoring prepares the code for exposing a `reftable_iterator`
> interface for blocks in a subsequent commit. Callsites are adjusted
> accordingly.
> 
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>  reftable/block.c                | 23 +++++++++++++----------
>  reftable/block.h                | 21 ++++++++++++++++-----
>  reftable/iter.c                 |  2 +-
>  reftable/table.c                | 11 +++++++----
>  t/unit-tests/t-reftable-block.c | 30 +++++++++++++++---------------
>  5 files changed, 52 insertions(+), 35 deletions(-)
> 
> diff --git a/reftable/block.c b/reftable/block.c
> index 576c6caf59b..6e5c1191f5f 100644
> --- a/reftable/block.c
> +++ b/reftable/block.c
> @@ -381,11 +381,16 @@ static uint32_t block_restart_offset(const struct reftable_block *b, size_t idx)
>  	return reftable_get_be24(b->block.data + b->restart_off + 3 * idx);
>  }
>  
> -void block_iter_seek_start(struct block_iter *it, const struct reftable_block *block)
> +void block_iter_init(struct block_iter *it, const struct reftable_block *block)
>  {
>  	it->block = block;
> +	block_iter_seek_start(it);
> +}
> +
> +void block_iter_seek_start(struct block_iter *it)
> +{
>  	reftable_buf_reset(&it->last_key);
> -	it->next_off = block->header_off + 4;
> +	it->next_off = it->block->header_off + 4;
>  }
>  
>  struct restart_needle_less_args {
> @@ -473,12 +478,11 @@ void block_iter_close(struct block_iter *it)
>  	reftable_buf_release(&it->scratch);
>  }
>  
> -int block_iter_seek_key(struct block_iter *it, const struct reftable_block *block,
> -			struct reftable_buf *want)
> +int block_iter_seek_key(struct block_iter *it, struct reftable_buf *want)

Ah so now that we store the `reftable_block` directly as part of `block_iter`, passing the block in `block_iter_seek_key()` becomes redundant. Nice!

Show 133 quoted lines
>  {
>  	struct restart_needle_less_args args = {
>  		.needle = *want,
> -		.block = block,
> +		.block = it->block,
>  	};
>  	struct reftable_record rec;
>  	int err = 0;
> @@ -496,7 +500,7 @@ int block_iter_seek_key(struct block_iter *it, const struct reftable_block *bloc
>  	 * restart point. While that works alright, we would end up scanning
>  	 * too many record.
>  	 */
> -	i = binsearch(block->restart_count, &restart_needle_less, &args);
> +	i = binsearch(it->block->restart_count, &restart_needle_less, &args);
>  	if (args.error) {
>  		err = REFTABLE_FORMAT_ERROR;
>  		goto done;
> @@ -521,12 +525,11 @@ int block_iter_seek_key(struct block_iter *it, const struct reftable_block *bloc
>  	 *     starting from the preceding restart point.
>  	 */
>  	if (i > 0)
> -		it->next_off = block_restart_offset(block, i - 1);
> +		it->next_off = block_restart_offset(it->block, i - 1);
>  	else
> -		it->next_off = block->header_off + 4;
> -	it->block = block;
> +		it->next_off = it->block->header_off + 4;
>  
> -	err = reftable_record_init(&rec, reftable_block_type(block));
> +	err = reftable_record_init(&rec, reftable_block_type(it->block));
>  	if (err < 0)
>  		goto done;
>  
> diff --git a/reftable/block.h b/reftable/block.h
> index 268d5a1e005..1bfd44f56aa 100644
> --- a/reftable/block.h
> +++ b/reftable/block.h
> @@ -79,12 +79,23 @@ struct block_iter {
>  	.scratch = REFTABLE_BUF_INIT, \
>  }
>  
> -/* Position `it` at start of the block */
> -void block_iter_seek_start(struct block_iter *it, const struct reftable_block *block);
> +/*
> + * Initialize the block iterator with the given block. The iterator will be
> + * positioned at the first record contained in the block. The block must remain
> + * valid until the end of the iterator's lifetime. It is valid to re-initialize
> + * iterators multiple times.
> + */
> +void block_iter_init(struct block_iter *it, const struct reftable_block *block);
> +
> +/* Position the initialized iterator at the first record of its block. */
> +void block_iter_seek_start(struct block_iter *it);
>  
> -/* Position `it` to the `want` key in the block */
> -int block_iter_seek_key(struct block_iter *it, const struct reftable_block *block,
> -			struct reftable_buf *want);
> +/*
> + * Position the initialized iterator at the desired record key. It is not an
> + * error in case the record cannot be found. If so, a subsequent call to
> + * `block_iter_next()` will indicate that the iterator is exhausted.
> + */
> +int block_iter_seek_key(struct block_iter *it, struct reftable_buf *want);
>  
>  /* return < 0 for error, 0 for OK, > 0 for EOF. */
>  int block_iter_next(struct block_iter *it, struct reftable_record *rec);
> diff --git a/reftable/iter.c b/reftable/iter.c
> index 74684de8f6a..7a7e8aa4d7e 100644
> --- a/reftable/iter.c
> +++ b/reftable/iter.c
> @@ -139,7 +139,7 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)
>  		/* indexed block does not exist. */
>  		return REFTABLE_FORMAT_ERROR;
>  	}
> -	block_iter_seek_start(&it->cur, &it->block);
> +	block_iter_init(&it->cur, &it->block);
>  	return 0;
>  }
>  
> diff --git a/reftable/table.c b/reftable/table.c
> index 3f2e70caac4..5422ed6769c 100644
> --- a/reftable/table.c
> +++ b/reftable/table.c
> @@ -208,7 +208,7 @@ static int table_iter_next_block(struct table_iter *ti)
>  
>  	ti->block_off = next_block_off;
>  	ti->is_finished = 0;
> -	block_iter_seek_start(&ti->bi, &ti->block);
> +	block_iter_init(&ti->bi, &ti->block);
>  
>  	return 0;
>  }
> @@ -256,7 +256,7 @@ static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)
>  
>  	ti->typ = reftable_block_type(&ti->block);
>  	ti->block_off = off;
> -	block_iter_seek_start(&ti->bi, &ti->block);
> +	block_iter_init(&ti->bi, &ti->block);
>  	ti->is_finished = 0;
>  	return 0;
>  }
> @@ -349,7 +349,8 @@ static int table_iter_seek_linear(struct table_iter *ti,
>  	 * 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->block, &want_key);
> +	block_iter_init(&ti->bi, &ti->block);
> +	err = block_iter_seek_key(&ti->bi, &want_key);
>  	if (err < 0)
>  		goto done;
>  	err = 0;
> @@ -417,7 +418,9 @@ static int table_iter_seek_indexed(struct table_iter *ti,
>  		if (err != 0)
>  			goto done;
>  
> -		err = block_iter_seek_key(&ti->bi, &ti->block, &want_index.u.idx.last_key);
> +		block_iter_init(&ti->bi, &ti->block);
> +
> +		err = block_iter_seek_key(&ti->bi, &want_index.u.idx.last_key);
>  		if (err < 0)
>  			goto done;
>  
> diff --git a/t/unit-tests/t-reftable-block.c b/t/unit-tests/t-reftable-block.c
> index e36ed7ac576..c4ced39a73b 100644
> --- a/t/unit-tests/t-reftable-block.c
> +++ b/t/unit-tests/t-reftable-block.c
> @@ -66,7 +66,8 @@ static void t_ref_block_read_write(void)
>  	block_source_from_buf(&source ,&block_data);
>  	reftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);
>  
> -	block_iter_seek_start(&it, &block);
> +	block_iter_init(&it, &block);
> +	block_iter_seek_start(&it);

If I'm understanding correctly, `block_iter_init()` already invokes `block_iter_seek_start()`. Why do we need to invoke `block_iter_seek_start()` again?

Show 114 quoted lines
>  
>  	for (i = 0; ; i++) {
>  		ret = block_iter_next(&it, &rec);
> @@ -79,10 +80,9 @@ static void t_ref_block_read_write(void)
>  	}
>  
>  	for (i = 0; i < N; i++) {
> -		block_iter_reset(&it);
>  		reftable_record_key(&recs[i], &want);
>  
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> @@ -91,7 +91,7 @@ static void t_ref_block_read_write(void)
>  		check(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1));
>  
>  		want.len--;
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> @@ -156,7 +156,8 @@ static void t_log_block_read_write(void)
>  	block_source_from_buf(&source, &block_data);
>  	reftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);
>  
> -	block_iter_seek_start(&it, &block);
> +	block_iter_init(&it, &block);
> +	block_iter_seek_start(&it);
>  
>  	for (i = 0; ; i++) {
>  		ret = block_iter_next(&it, &rec);
> @@ -169,11 +170,10 @@ static void t_log_block_read_write(void)
>  	}
>  
>  	for (i = 0; i < N; i++) {
> -		block_iter_reset(&it);
>  		reftable_buf_reset(&want);
>  		check(!reftable_buf_addstr(&want, recs[i].u.log.refname));
>  
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> @@ -182,7 +182,7 @@ static void t_log_block_read_write(void)
>  		check(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1));
>  
>  		want.len--;
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> @@ -249,7 +249,8 @@ static void t_obj_block_read_write(void)
>  	block_source_from_buf(&source, &block_data);
>  	reftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);
>  
> -	block_iter_seek_start(&it, &block);
> +	block_iter_init(&it, &block);
> +	block_iter_seek_start(&it);
>  
>  	for (i = 0; ; i++) {
>  		ret = block_iter_next(&it, &rec);
> @@ -262,10 +263,9 @@ static void t_obj_block_read_write(void)
>  	}
>  
>  	for (i = 0; i < N; i++) {
> -		block_iter_reset(&it);
>  		reftable_record_key(&recs[i], &want);
>  
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> @@ -334,7 +334,8 @@ static void t_index_block_read_write(void)
>  	block_source_from_buf(&source, &block_data);
>  	reftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);
>  
> -	block_iter_seek_start(&it, &block);
> +	block_iter_init(&it, &block);
> +	block_iter_seek_start(&it);
>  
>  	for (i = 0; ; i++) {
>  		ret = block_iter_next(&it, &rec);
> @@ -347,10 +348,9 @@ static void t_index_block_read_write(void)
>  	}
>  
>  	for (i = 0; i < N; i++) {
> -		block_iter_reset(&it);
>  		reftable_record_key(&recs[i], &want);
>  
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> @@ -359,7 +359,7 @@ static void t_index_block_read_write(void)
>  		check(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1));
>  
>  		want.len--;
> -		ret = block_iter_seek_key(&it, &block, &want);
> +		ret = block_iter_seek_key(&it, &want);
>  		check_int(ret, ==, 0);
>  
>  		ret = block_iter_next(&it, &rec);
> 
> -- 
> 2.49.0.604.gff1f9ca942.dirty
> 
>
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 26 of 55 in “reftable: overhaul the API to expose access to blocks”
  1. 00/16 reftable: overhaul the API to expose access to blocksPatrick Steinhardt, Mar 31, 2025
  2. 01/16 reftable: fix formatting of the license headerPatrick Steinhardt, Mar 31, 2025
  3. 03/16 reftable/blocksource: consolidate code into a single filePatrick Steinhardt, Mar 31, 2025
  4. Justin ToblerApr 2, 2025
  5. Karthik NayakApr 3, 2025
  6. 02/16 reftable/reader: rename data structure to "table"Patrick Steinhardt, Mar 31, 2025
  7. 04/16 reftable/block: simplify how we track restart pointsPatrick Steinhardt, Mar 31, 2025
  8. Justin ToblerApr 2, 2025
  9. Karthik NayakApr 3, 2025
  10. Patrick SteinhardtApr 7, 2025
  11. 05/16 reftable/table: move reading block into block readerPatrick Steinhardt, Mar 31, 2025
  12. Justin ToblerApr 2, 2025
  13. Patrick SteinhardtApr 7, 2025
  14. 06/16 reftable/block: rename `block` to `block_data`Patrick Steinhardt, Mar 31, 2025
  15. Justin ToblerApr 2, 2025
  16. Patrick SteinhardtApr 7, 2025
  17. 07/16 reftable/block: rename `block_reader` to `reftable_block`Patrick Steinhardt, Mar 31, 2025
  18. Justin ToblerApr 2, 2025
  19. Patrick SteinhardtApr 7, 2025
  20. 08/16 git-zlib: use `struct z_stream_s` instead of typedefPatrick Steinhardt, Mar 31, 2025
  21. 10/16 reftable/block: store block pointer in the block iteratorPatrick Steinhardt, Mar 31, 2025
  22. Justin ToblerApr 2, 2025
  23. Patrick SteinhardtApr 7, 2025
  24. 09/16 reftable/block: create public interface for reading blocksPatrick Steinhardt, Mar 31, 2025
  25. 11/16 reftable/block: make block iterators reseekablePatrick Steinhardt, Mar 31, 2025
  26. Justin ToblerApr 2, 2025
  27. Patrick SteinhardtApr 7, 2025
  28. 12/16 reftable/block: expose a generic iterator over reftable recordsPatrick Steinhardt, Mar 31, 2025
  29. 13/16 reftable/table: add `reftable_table` to the public interfacePatrick Steinhardt, Mar 31, 2025
  30. 14/16 reftable/table: introduce iterator for table blocksPatrick Steinhardt, Mar 31, 2025
  31. Junio C HamanoApr 1, 2025
  32. Patrick SteinhardtApr 2, 2025
  33. Justin ToblerApr 2, 2025
  34. Patrick SteinhardtApr 7, 2025
  35. 15/16 reftable/constants: make block types part of the public interfacePatrick Steinhardt, Mar 31, 2025
  36. 16/16 reftable/table: move printing logic into test helperPatrick Steinhardt, Mar 31, 2025
  37. Justin ToblerApr 2, 2025
  38. 00/16 reftable: overhaul the API to expose access to blocksPatrick Steinhardt, Apr 7, 2025
  39. 01/16 reftable: fix formatting of the license headerPatrick Steinhardt, Apr 7, 2025
  40. 03/16 reftable/blocksource: consolidate code into a single filePatrick Steinhardt, Apr 7, 2025
  41. 02/16 reftable/reader: rename data structure to "table"Patrick Steinhardt, Apr 7, 2025
  42. 04/16 reftable/block: simplify how we track restart pointsPatrick Steinhardt, Apr 7, 2025
  43. 06/16 reftable/block: rename `block` to `block_data`Patrick Steinhardt, Apr 7, 2025
  44. 05/16 reftable/table: move reading block into block readerPatrick Steinhardt, Apr 7, 2025
  45. 07/16 reftable/block: rename `block_reader` to `reftable_block`Patrick Steinhardt, Apr 7, 2025
  46. 08/16 git-zlib: use `struct z_stream_s` instead of typedefPatrick Steinhardt, Apr 7, 2025
  47. 09/16 reftable/block: create public interface for reading blocksPatrick Steinhardt, Apr 7, 2025
  48. 10/16 reftable/block: store block pointer in the block iteratorPatrick Steinhardt, Apr 7, 2025
  49. 11/16 reftable/block: make block iterators reseekablePatrick Steinhardt, Apr 7, 2025
  50. 12/16 reftable/block: expose a generic iterator over reftable recordsPatrick Steinhardt, Apr 7, 2025
  51. 13/16 reftable/table: add `reftable_table` to the public interfacePatrick Steinhardt, Apr 7, 2025
  52. 14/16 reftable/table: introduce iterator for table blocksPatrick Steinhardt, Apr 7, 2025
  53. 15/16 reftable/constants: make block types part of the public interfacePatrick Steinhardt, Apr 7, 2025
  54. 16/16 reftable/table: move printing logic into test helperPatrick Steinhardt, Apr 7, 2025
  55. Justin ToblerApr 14, 2025

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.