Function table_iter_seek_linear

reftable/table.c:270–354

}

static int table_iter_seek_linear(struct table_iter *ti,
				  struct reftable_record *want)
{
	struct reftable_buf want_key = REFTABLE_BUF_INIT;
	struct reftable_buf got_key = REFTABLE_BUF_INIT;
	struct reftable_record rec;
	int err;

	err = reftable_record_init(&rec, reftable_record_type(want));
	if (err < 0)
		goto done;

	err = reftable_record_key(want, &want_key);
	if (err < 0)
		goto done;

	/*
	 * 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 = *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.block.block_data, 0, sizeof(next.block.block_data));
		next.block.zstream = NULL;
		next.block.uncompressed_data = NULL;
		next.block.uncompressed_cap = 0;

		err = table_iter_next_block(&next);
		if (err < 0)
			goto done;
		if (err > 0)
			break;

		err = reftable_block_first_key(&next.block, &got_key);
		if (err < 0)
			goto done;