Re: [PATCH v2 5/5] reftable: document reading and writing indices

[Patrick Steinhardt <ps@pks.im>]

[-- Attachment #1: Type: text/plain, Size: 2275 bytes --]

On Mon, Feb 05, 2024 at 07:43:07PM -0600, jltobler wrote:
> On 24/02/01 08:52AM, Patrick Steinhardt wrote:
> > The way the index gets written and read is not trivial at all and
> > requires the reader to piece together a bunch of parts to figure out how
> > it works. Add some documentation to hopefully make this easier to
> > understand for the next reader.
> > 
> > Signed-off-by: Patrick Steinhardt <ps@pks.im>
> > ---
> >  reftable/reader.c | 27 +++++++++++++++++++++++++++
> >  reftable/writer.c | 23 +++++++++++++++++++++++
> >  2 files changed, 50 insertions(+)
> > 
> > diff --git a/reftable/reader.c b/reftable/reader.c
> > index 278f727a3d..6011d0aa04 100644
> > --- a/reftable/reader.c
> > +++ b/reftable/reader.c
> > @@ -508,11 +508,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.
> 
> The last block in the highest-level index section should end with the
> record key of greatest value. Doesn't that mean the initial linear seek
> should be sufficient to stop the iterator from continuing if the wanted
> record key is of a greater value?

Yes. But we only notice it here when calling `table_iter_next()`. The
call to `reader_seek_linear()` will not return an end-of-iterator
indication.

Is there any way you think this comment can be improved to clarify this?

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]