Function write_lookup_table

pack-bitmap-write.c:1289–1345

}

static void write_lookup_table(struct bitmap_writer *writer, struct hashfile *f,
			       off_t *offsets)
{
	uint32_t i;
	uint32_t *table, *table_inv;

	ALLOC_ARRAY(table, bitmap_writer_nr_selected_commits(writer));
	ALLOC_ARRAY(table_inv, bitmap_writer_nr_selected_commits(writer));

	for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++)
		table[i] = i;

	/*
	 * At the end of this sort table[j] = i means that the i'th
	 * bitmap corresponds to j'th bitmapped commit (among the selected
	 * commits) in lex order of OIDs.
	 */
	QSORT_S(table, bitmap_writer_nr_selected_commits(writer), table_cmp, writer);

	/* table_inv helps us discover that relationship (i'th bitmap
	 * to j'th commit by j = table_inv[i])
	 */
	for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++)
		table_inv[table[i]] = i;

	trace2_region_enter("pack-bitmap-write", "writing_lookup_table", writer->repo);
	for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {
		struct bitmapped_commit *selected = &writer->selected[table[i]];
		uint32_t xor_offset = selected->xor_offset;
		uint32_t xor_row;

		if (xor_offset) {
			/*
			 * xor_index stores the index (in the bitmap entries)
			 * of the corresponding xor bitmap. But we need to convert
			 * this index into lookup table's index. So, table_inv[xor_index]
			 * gives us the index position w.r.t. the lookup table.
			 *
			 * If "k = table[i] - xor_offset" then the xor base is the k'th
			 * bitmap. `table_inv[k]` gives us the position of that bitmap
			 * in the lookup table.
			 */
			uint32_t xor_index = table[i] - xor_offset;
			xor_row = table_inv[xor_index];
		} else {
			xor_row = 0xffffffff;
		}

		hashwrite_be32(f, writer->selected[table[i]].commit_pos);
		hashwrite_be64(f, (uint64_t)offsets[table[i]]);
		hashwrite_be32(f, xor_row);
	}
	trace2_region_leave("pack-bitmap-write", "writing_lookup_table", writer->repo);

	free(table);
	free(table_inv);
}