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@xxxxxxxxxxxxx>
---
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
