Function table_iter_seek_indexed

reftable/table.c:356–433

}

static int table_iter_seek_indexed(struct table_iter *ti,
				   struct reftable_record *rec)
{
	struct reftable_record want_index = {
		.type = REFTABLE_BLOCK_TYPE_INDEX, .u.idx = { .last_key = REFTABLE_BUF_INIT }
	};
	struct reftable_record index_result = {
		.type = REFTABLE_BLOCK_TYPE_INDEX,
		.u.idx = { .last_key = REFTABLE_BUF_INIT },
	};
	int err;

	err = reftable_record_key(rec, &want_index.u.idx.last_key);
	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 = table_iter_seek_linear(ti, &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.
		 *
		 * There is one subtlety in the layout of the index section
		 * that makes this work as expected: the highest-level index is
		 * at end of the section and will point backwards and thus we
		 * start reading from the end of the index section, not the
		 * beginning.
		 *
		 * If that wasn't the case and the order was reversed then the
		 * linear seek would seek into the lower levels and traverse
		 * all levels of the index only to find out that the key does
		 * not exist.
		 */
		err = table_iter_next(ti, &index_result);
		if (err != 0)
			goto done;

		err = table_iter_seek_to(ti, index_result.u.idx.offset, 0);
		if (err != 0)
			goto done;

		block_iter_init(&ti->bi, &ti->block);