t1700: add tests for splitIndex.maxPercentChange

diff --git a/sha1_name.c b/sha1_name.c
index 84662a68041bed3f92b04a6c17d984104b3cf7b9..73a915ff1b3278f08ef4f327a55fe61d238f720a 100644 (file)
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -15,7 +15,6 @@ typedef int (*disambiguate_hint_fn)(const unsigned char *, void *);
 
 struct disambiguate_state {
        int len; /* length of prefix in hex chars */
-       unsigned int nrobjects;
        char hex_pfx[GIT_SHA1_HEXSZ + 1];
        unsigned char bin_pfx[GIT_SHA1_RAWSZ];
 
@@ -112,14 +111,6 @@ static void find_short_object_filename(struct disambiguate_state *ds)
 
                        if (strlen(de->d_name) != 38)
                                continue;
-
-                       /*
-                        * We only look at the one subdirectory, and we assume
-                        * each subdirectory is roughly similar, so each
-                        * object we find probably has 255 other objects in
-                        * the other fan-out directories.
-                        */
-                       ds->nrobjects += 256;
                        if (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2))
                                continue;
                        memcpy(hex + 2, de->d_name, 38);
@@ -153,7 +144,6 @@ static void unique_in_pack(struct packed_git *p,
 
        open_pack_index(p);
        num = p->num_objects;
-       ds->nrobjects += num;
        last = num;
        while (first < last) {
                uint32_t mid = (first + last) / 2;
@@ -383,9 +373,6 @@ static int show_ambiguous_object(const unsigned char *sha1, void *data)
        return 0;
 }
 
-/* start from our historical default before the automatic abbreviation */
-static int default_automatic_abbrev = FALLBACK_DEFAULT_ABBREV;
-
 static int get_short_sha1(const char *name, int len, unsigned char *sha1,
                          unsigned flags)
 {
@@ -432,14 +419,6 @@ static int get_short_sha1(const char *name, int len, unsigned char *sha1,
                for_each_abbrev(ds.hex_pfx, show_ambiguous_object, &ds);
        }
 
-       if (len < 16 && !status && (flags & GET_SHA1_AUTOMATIC)) {
-               unsigned int expect_collision = 1 << (len * 2);
-               if (ds.nrobjects > expect_collision) {
-                       default_automatic_abbrev = len+1;
-                       return SHORT_NAME_AMBIGUOUS;
-               }
-       }
-
        return status;
 }
 
@@ -469,22 +448,53 @@ int for_each_abbrev(const char *prefix, each_abbrev_fn fn, void *cb_data)
        return ret;
 }
 
+/*
+ * Return the slot of the most-significant bit set in "val". There are various
+ * ways to do this quickly with fls() or __builtin_clzl(), but speed is
+ * probably not a big deal here.
+ */
+static unsigned msb(unsigned long val)
+{
+       unsigned r = 0;
+       while (val >>= 1)
+               r++;
+       return r;
+}
+
 int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 {
        int status, exists;
-       int flags = GET_SHA1_QUIETLY;
 
        if (len < 0) {
-               flags |= GET_SHA1_AUTOMATIC;
-               len = default_automatic_abbrev;
+               unsigned long count = approximate_object_count();
+               /*
+                * Add one because the MSB only tells us the highest bit set,
+                * not including the value of all the _other_ bits (so "15"
+                * is only one off of 2^4, but the MSB is the 3rd bit.
+                */
+               len = msb(count) + 1;
+               /*
+                * We now know we have on the order of 2^len objects, which
+                * expects a collision at 2^(len/2). But we also care about hex
+                * chars, not bits, and there are 4 bits per hex. So all
+                * together we need to divide by 2; but we also want to round
+                * odd numbers up, hence adding one before dividing.
+                */
+               len = (len + 1) / 2;
+               /*
+                * For very small repos, we stick with our regular fallback.
+                */
+               if (len < FALLBACK_DEFAULT_ABBREV)
+                       len = FALLBACK_DEFAULT_ABBREV;
        }
+
        sha1_to_hex_r(hex, sha1);
        if (len == 40 || !len)
                return 40;
        exists = has_sha1_file(sha1);
        while (len < 40) {
                unsigned char sha1_ret[20];
-               status = get_short_sha1(hex, len, sha1_ret, flags);
+               status = get_short_sha1(hex, len, sha1_ret, GET_SHA1_QUIETLY);
                if (exists
                    ? !status
                    : status == SHORT_NAME_NOT_FOUND) {
@@ -498,7 +508,10 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 
 const char *find_unique_abbrev(const unsigned char *sha1, int len)
 {
-       static char hex[GIT_SHA1_HEXSZ + 1];
+       static int bufno;
+       static char hexbuffer[4][GIT_SHA1_HEXSZ + 1];
+       char *hex = hexbuffer[bufno];
+       bufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);
        find_unique_abbrev_r(hex, sha1, len);
        return hex;
 }