[PATCH v2 2/6] pack-bitmap-write.c: write lookup table extension

["Abhradeep Chakraborty via GitGitGadget" <gitgitgadget@gmail.com>]

From: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>

The bitmap lookup table extension was documentated by an earlier
change, but Git does not yet knowhow to write that extension.

Teach git to write bitmap lookup table extension. The table contains
the list of `N` <commit pos, offset, xor offset>` triplets. These
triplets are sorted according to their commit pos (ascending order).
The meaning of each data in the i'th triplet is given below:

  - Commit pos is the position of the commit in the pack-index
    (or midx) to which the i'th bitmap belongs. It is a 4 byte
    network byte order integer.

  - offset is the position of the i'th bitmap.

  - xor offset denotes the position of the triplet with whose
    bitmap the current triplet's bitmap need to xor with.

Co-authored-by: Taylor Blau <me@ttaylorr.com>
Mentored-by: Taylor Blau <me@ttaylorr.com>
Co-mentored-by: Kaartic Sivaraam <kaartic.sivaraam@gmail.com>
Signed-off-by: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>
---
 pack-bitmap-write.c | 72 +++++++++++++++++++++++++++++++++++++++++++--
 pack-bitmap.h       |  5 ++--
 2 files changed, 73 insertions(+), 4 deletions(-)

diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index c43375bd344..899a4a941e1 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -650,7 +650,9 @@ static const struct object_id *oid_access(size_t pos, const void *table)
 
 static void write_selected_commits_v1(struct hashfile *f,
 				      struct pack_idx_entry **index,
-				      uint32_t index_nr)
+				      uint32_t index_nr,
+				      uint64_t *offsets,
+				      uint32_t *commit_positions)
 {
 	int i;
 
@@ -663,6 +665,11 @@ static void write_selected_commits_v1(struct hashfile *f,
 		if (commit_pos < 0)
 			BUG("trying to write commit not in index");
 
+		if (offsets)
+			offsets[i] = hashfile_total(f);
+		if (commit_positions)
+			commit_positions[i] = commit_pos;
+
 		hashwrite_be32(f, commit_pos);
 		hashwrite_u8(f, stored->xor_offset);
 		hashwrite_u8(f, stored->flags);
@@ -671,6 +678,55 @@ static void write_selected_commits_v1(struct hashfile *f,
 	}
 }
 
+static int table_cmp(const void *_va, const void *_vb, void *commit_positions)
+{
+	int8_t result = 0;
+	uint32_t *positions = (uint32_t *) commit_positions;
+	uint32_t a = positions[*(uint32_t *)_va];
+	uint32_t b = positions[*(uint32_t *)_vb];
+
+	if (a > b)
+		result = 1;
+	else if (a < b)
+		result = -1;
+	else
+		result = 0;
+
+	return result;
+}
+
+static void write_lookup_table(struct hashfile *f,
+			       uint64_t *offsets,
+			       uint32_t *commit_positions)
+{
+	uint32_t i;
+	uint32_t *table, *table_inv;
+
+	ALLOC_ARRAY(table, writer.selected_nr);
+	ALLOC_ARRAY(table_inv, writer.selected_nr);
+
+	for (i = 0; i < writer.selected_nr; i++)
+		table[i] = i;
+
+	QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);
+
+	for (i = 0; i < writer.selected_nr; i++)
+		table_inv[table[i]] = i;
+
+	for (i = 0; i < writer.selected_nr; i++) {
+		struct bitmapped_commit *selected = &writer.selected[table[i]];
+		uint32_t xor_offset = selected->xor_offset;
+
+		hashwrite_be32(f, commit_positions[table[i]]);
+		hashwrite_be64(f, offsets[table[i]]);
+		hashwrite_be32(f, xor_offset ?
+				table_inv[table[i] - xor_offset]: 0xffffffff);
+	}
+
+	free(table);
+	free(table_inv);
+}
+
 static void write_hash_cache(struct hashfile *f,
 			     struct pack_idx_entry **index,
 			     uint32_t index_nr)
@@ -695,6 +751,8 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 {
 	static uint16_t default_version = 1;
 	static uint16_t flags = BITMAP_OPT_FULL_DAG;
+	uint64_t *offsets = NULL;
+	uint32_t *commit_positions = NULL;
 	struct strbuf tmp_file = STRBUF_INIT;
 	struct hashfile *f;
 
@@ -715,8 +773,16 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 	dump_bitmap(f, writer.trees);
 	dump_bitmap(f, writer.blobs);
 	dump_bitmap(f, writer.tags);
-	write_selected_commits_v1(f, index, index_nr);
 
+	if (options & BITMAP_OPT_LOOKUP_TABLE) {
+		CALLOC_ARRAY(offsets, index_nr);
+		CALLOC_ARRAY(commit_positions, index_nr);
+	}
+
+	write_selected_commits_v1(f, index, index_nr, offsets, commit_positions);
+
+	if (options & BITMAP_OPT_LOOKUP_TABLE)
+		write_lookup_table(f, offsets, commit_positions);
 	if (options & BITMAP_OPT_HASH_CACHE)
 		write_hash_cache(f, index, index_nr);
 
@@ -730,4 +796,6 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 		die_errno("unable to rename temporary bitmap file to '%s'", filename);
 
 	strbuf_release(&tmp_file);
+	free(offsets);
+	free(commit_positions);
 }
diff --git a/pack-bitmap.h b/pack-bitmap.h
index 3d3ddd77345..67a9d0fc303 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -24,8 +24,9 @@ struct bitmap_disk_header {
 #define NEEDS_BITMAP (1u<<22)
 
 enum pack_bitmap_opts {
-	BITMAP_OPT_FULL_DAG = 1,
-	BITMAP_OPT_HASH_CACHE = 4,
+	BITMAP_OPT_FULL_DAG = 0x1,
+	BITMAP_OPT_HASH_CACHE = 0x4,
+	BITMAP_OPT_LOOKUP_TABLE = 0x10,
 };
 
 enum pack_bitmap_flags {
-- 
gitgitgadget