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];
* alt->name/alt->base while iterating over the
* object databases including our own.
*/
- const char *objdir = get_object_directory();
- size_t objdir_len = strlen(objdir);
- fakeent = xmalloc(st_add3(sizeof(*fakeent), objdir_len, 43));
- memcpy(fakeent->base, objdir, objdir_len);
- fakeent->name = fakeent->base + objdir_len + 1;
- fakeent->name[-1] = '/';
+ fakeent = alloc_alt_odb(get_object_directory());
}
fakeent->next = alt_odb_list;
xsnprintf(hex, sizeof(hex), "%.2s", ds->hex_pfx);
for (alt = fakeent; alt && !ds->ambiguous; alt = alt->next) {
+ struct strbuf *buf = alt_scratch_buf(alt);
struct dirent *de;
DIR *dir;
- /*
- * every alt_odb struct has 42 extra bytes after the base
- * for exactly this purpose
- */
- xsnprintf(alt->name, 42, "%.2s/", ds->hex_pfx);
- dir = opendir(alt->base);
+
+ strbuf_addf(buf, "%.2s/", ds->hex_pfx);
+ dir = opendir(buf->buf);
if (!dir)
continue;
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);
open_pack_index(p);
num = p->num_objects;
- ds->nrobjects += num;
last = num;
while (first < last) {
uint32_t mid = (first + last) / 2;
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)
{
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;
}
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) {
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;
}