From 485300fd3f3b9603024664f0f72cc538a85cc114 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Thu, 15 Feb 2018 13:08:21 -0800
Subject: [PATCH] Revert "Merge branch 'jt/binsearch-with-fanout' into next"

This reverts commit 86fc3e8104af660d0eddb69be81160f6ef5cd14a, reversing
changes made to d8f074e6fb809bd64ad443ba0ea6f23a6a657d90.
---
 packfile.c    | 30 +++++++++++++++++++++++++-----
 sha1-lookup.c | 24 ------------------------
 sha1-lookup.h | 21 ---------------------
 3 files changed, 25 insertions(+), 50 deletions(-)

diff --git a/packfile.c b/packfile.c
index 860e6d7fe4..7dbe8739d1 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1722,8 +1722,11 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 {
 	const uint32_t *level1_ofs = p->index_data;
 	const unsigned char *index = p->index_data;
-	unsigned stride;
-	int ret;
+	unsigned hi, lo, stride;
+	static int debug_lookup = -1;
+
+	if (debug_lookup < 0)
+		debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
 
 	if (!index) {
 		if (open_pack_index(p))
@@ -1736,6 +1739,8 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 		index += 8;
 	}
 	index += 4 * 256;
+	hi = ntohl(level1_ofs[*sha1]);
+	lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
 	if (p->index_version > 1) {
 		stride = 20;
 	} else {
@@ -1743,9 +1748,24 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 		index += 4;
 	}
 
-	ret = bsearch_hash(sha1, level1_ofs, index, stride);
-	if (ret >= 0)
-		return nth_packed_object_offset(p, ret);
+	if (debug_lookup)
+		printf("%02x%02x%02x... lo %u hi %u nr %"PRIu32"\n",
+		       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);
+
+	while (lo < hi) {
+		unsigned mi = lo + (hi - lo) / 2;
+		int cmp = hashcmp(index + mi * stride, sha1);
+
+		if (debug_lookup)
+			printf("lo %u hi %u rg %u mi %u\n",
+			       lo, hi, hi - lo, mi);
+		if (!cmp)
+			return nth_packed_object_offset(p, mi);
+		if (cmp > 0)
+			hi = mi;
+		else
+			lo = mi+1;
+	}
 	return 0;
 }
 
diff --git a/sha1-lookup.c b/sha1-lookup.c
index d11c5e5260..4cf3ebd921 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -99,27 +99,3 @@ 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 void *fanout_,
-		 const void *table_, size_t stride)
-{
-	const uint32_t *fanout = fanout_;
-	const unsigned char *table = table_;
-	int hi, lo;
-
-	hi = ntohl(fanout[*sha1]);
-	lo = ((*sha1 == 0x0) ? 0 : ntohl(fanout[*sha1 - 1]));
-
-	while (lo < hi) {
-		unsigned mi = lo + (hi - lo) / 2;
-		int cmp = hashcmp(table + mi * stride, sha1);
-
-		if (!cmp)
-			return mi;
-		if (cmp > 0)
-			hi = mi;
-		else
-			lo = mi + 1;
-	}
-	return -lo - 1;
-}
diff --git a/sha1-lookup.h b/sha1-lookup.h
index 3c59e9cb1e..cf5314f402 100644
--- a/sha1-lookup.h
+++ b/sha1-lookup.h
@@ -7,25 +7,4 @@ extern int sha1_pos(const unsigned char *sha1,
 		    void *table,
 		    size_t nr,
 		    sha1_access_fn fn);
-
-/*
- * Searches for sha1 in table, using the given fanout table to determine the
- * interval to search, then using binary search. Returns the element index of
- * the position found if successful, -i-1 if not (where i is the index of the
- * least element that is greater than sha1).
- *
- * Takes the following parameters:
- *
- *  - sha1: the hash to search for
- *  - fanout: a 256-element array of NETWORK-order 32-bit integers; the integer
- *    at position i represents the number of elements in table whose first byte
- *    is less than or equal to i
- *  - table: a sorted list of hashes with optional extra information in between
- *  - stride: distance between two consecutive elements in table (should be
- *    GIT_MAX_RAWSZ or greater)
- *
- * This function does not verify the validity of the fanout table.
- */
-extern int bsearch_hash(const unsigned char *sha1, const void *fanout,
-			const void *table, size_t stride);
 #endif
-- 
2.48.1