summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2018-03-13 20:34:04 (GMT)
committerJunio C Hamano <gitster@pobox.com>2018-03-13 20:34:04 (GMT)
commit7d4bebfe93b5ef0eb81b8a7b0f6edf365104ed01 (patch)
treeb72cb530e83c5ea670b1bfb4c7e506e5c3077836
parent0fd90daba84a165adda7cd4721fcd009e0bebc56 (diff)
parentb4e00f7306a160639f047b3421985e8f3d0c6fb1 (diff)
downloadgit-7d4bebfe93b5ef0eb81b8a7b0f6edf365104ed01.zip
git-7d4bebfe93b5ef0eb81b8a7b0f6edf365104ed01.tar.gz
git-7d4bebfe93b5ef0eb81b8a7b0f6edf365104ed01.tar.bz2
Merge branch 'jt/binsearch-with-fanout' into HEAD
* jt/binsearch-with-fanout: packfile: refactor hash search with fanout table packfile: remove GIT_DEBUG_LOOKUP log statements
-rw-r--r--packfile.c29
-rw-r--r--sha1-lookup.c28
-rw-r--r--sha1-lookup.h22
3 files changed, 54 insertions, 25 deletions
diff --git a/packfile.c b/packfile.c
index 7dbe873..5d07f33 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1722,11 +1722,8 @@ 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 hi, lo, stride;
- static int debug_lookup = -1;
-
- if (debug_lookup < 0)
- debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
+ unsigned stride;
+ uint32_t result;
if (!index) {
if (open_pack_index(p))
@@ -1739,8 +1736,6 @@ 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 {
@@ -1748,24 +1743,8 @@ off_t find_pack_entry_one(const unsigned char *sha1,
index += 4;
}
- 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;
- }
+ if (bsearch_hash(sha1, level1_ofs, index, stride, &result))
+ return nth_packed_object_offset(p, result);
return 0;
}
diff --git a/sha1-lookup.c b/sha1-lookup.c
index 4cf3ebd..8d0b1db 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;
+}
diff --git a/sha1-lookup.h b/sha1-lookup.h
index cf5314f..7678b23 100644
--- a/sha1-lookup.h
+++ b/sha1-lookup.h
@@ -7,4 +7,26 @@ 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 1 if found, 0 if not.
+ *
+ * Takes the following parameters:
+ *
+ * - sha1: the hash to search for
+ * - fanout_nbo: 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)
+ * - result: if not NULL, this function stores the element index of the
+ * position found (if the search is successful) or the index of the least
+ * element that is greater than sha1 (if the search is not successful)
+ *
+ * This function does not verify the validity of the fanout table.
+ */
+int bsearch_hash(const unsigned char *sha1, const uint32_t *fanout_nbo,
+ const unsigned char *table, size_t stride, uint32_t *result);
#endif