Merge branch 'jt/binsearch-with-fanout'

Refactor the code to binary search starting from a fan-out table
(which is how the packfile is indexed with object names) into a
reusable helper.

* jt/binsearch-with-fanout:
  packfile: refactor hash search with fanout table
  packfile: remove GIT_DEBUG_LOOKUP log statements

1 files changed, 28 insertions, 0 deletions

diff --git a/sha1-lookup.c b/sha1-lookup.c
index 4cf3ebd921..8d0b1db3e2 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -99,3 +99,31 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
 	} while (lo < hi);
 	return -lo-1;
 }
+
+int bsearch_hash(const unsigned char *sha1, const uint32_t *fanout_nbo,
+		 const unsigned char *table, size_t stride, uint32_t *result)
+{
+	uint32_t hi, lo;
+
+	hi = ntohl(fanout_nbo[*sha1]);
+	lo = ((*sha1 == 0x0) ? 0 : ntohl(fanout_nbo[*sha1 - 1]));
+
+	while (lo < hi) {
+		unsigned mi = lo + (hi - lo) / 2;
+		int cmp = hashcmp(table + mi * stride, sha1);
+
+		if (!cmp) {
+			if (result)
+				*result = mi;
+			return 1;
+		}
+		if (cmp > 0)
+			hi = mi;
+		else
+			lo = mi + 1;
+	}
+
+	if (result)
+		*result = lo;
+	return 0;
+}