Merge branch 'jt/binsearch-with-fanout' into next

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

diff --git a/packfile.c b/packfile.c
index 7dbe8739d17d64fad79eac9e7477d00ea3d80df2..860e6d7fe4d0d115b0b635599271f302c5bedb69 100644 (file)
--- 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;
+       int ret;
 
        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,9 @@ 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;
-       }
+       ret = bsearch_hash(sha1, level1_ofs, index, stride);
+       if (ret >= 0)
+               return nth_packed_object_offset(p, ret);
        return 0;
 }
 

diff --git a/sha1-lookup.c b/sha1-lookup.c
index 4cf3ebd9212f6d5c9b9829373e58c34b83f0a548..d11c5e526052e708a9a357ca4d4687d09467e382 100644 (file)
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -99,3 +99,27 @@ 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 cf5314f402ce78f0d5ab2bd72ee7f334b6394e04..3c59e9cb1e0792b891dd0bd033f337c7da708e8e 100644 (file)
--- a/sha1-lookup.h
+++ b/sha1-lookup.h
@@ -7,4 +7,25 @@ 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