[RFC PATCH 16/18] midx: nth_midxed_object_oid() and bsearch_midx()

[Derrick Stolee <stolee@gmail.com>]

Using a binary search, we can navigate to the position n within a
MIDX file where an object appears in the ordered list of objects.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 midx.c | 30 ++++++++++++++++++++++++++++++
 midx.h |  9 +++++++++
 2 files changed, 39 insertions(+)

diff --git a/midx.c b/midx.c
index a66763b9e3..8c643caa92 100644
--- a/midx.c
+++ b/midx.c
@@ -299,6 +299,36 @@ const struct object_id *nth_midxed_object_oid(struct object_id *oid,
 	return oid;
 }
 
+int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos)
+{
+	uint32_t last, first = 0;
+
+	if (sha1[0])
+		first = ntohl(*(uint32_t*)(m->chunk_oid_fanout + 4 * (sha1[0] - 1)));
+	last = ntohl(*(uint32_t*)(m->chunk_oid_fanout + 4 * sha1[0]));
+
+	while (first < last) {
+		uint32_t mid = first + (last - first) / 2;
+		const unsigned char *current;
+		int cmp;
+
+		current = m->chunk_oid_lookup + m->hdr->hash_len * mid;
+		cmp = hashcmp(sha1, current);
+		if (!cmp) {
+			*pos = mid;
+			return 1;
+		}
+		if (cmp > 0) {
+			first = mid + 1;
+			continue;
+		}
+		last = mid;
+	}
+
+	*pos = first;
+	return 0;
+}
+
 int contains_pack(struct midxed_git *m, const char *pack_name)
 {
 	uint32_t first = 0, last = m->num_packs;
diff --git a/midx.h b/midx.h
index d8ede8121c..5598799189 100644
--- a/midx.h
+++ b/midx.h
@@ -101,6 +101,15 @@ extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,
 						     struct midxed_git *m,
 						     uint32_t n);
 
+/*
+ * Perform a binary search on the object list in a MIDX file for the given sha1.
+ *
+ * If the object exists, then return 1 and set *pos to the position of the sha1.
+ * Otherwise, return 0 and set *pos to the position of the lex-first object greater
+ * than the given sha1.
+ */
+extern int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos);
+
 extern int contains_pack(struct midxed_git *m, const char *pack_name);
 
 /*
-- 
2.15.0