[RFC PATCH 16/18] midx: nth_midxed_object_oid() and bsearch_midx()
From: Derrick Stolee <hidden>
Date: 2018-01-07 18:15:50
Subsystem:
the rest · Maintainer:
Linus Torvalds
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 <redacted> --- 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