sha1-lookup: make selection of 'middle' less aggressive

diff --git a/read-cache.c b/read-cache.c
index 22d7b462454463fb149d02ac62415fc63aca7672..a92b25b59bf0e096942bca126542a1ea411b525b 100644 (file)
--- a/read-cache.c
+++ b/read-cache.c
@@ -37,8 +37,13 @@ static unsigned int hash_name(const char *name, int namelen)
 static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 {
        void **pos;
-       unsigned int hash = hash_name(ce->name, ce_namelen(ce));
+       unsigned int hash;
 
+       if (ce->ce_flags & CE_HASHED)
+               return;
+       ce->ce_flags |= CE_HASHED;
+       ce->next = NULL;
+       hash = hash_name(ce->name, ce_namelen(ce));
        pos = insert_hash(hash, ce, &istate->name_hash);
        if (pos) {
                ce->next = *pos;
@@ -59,33 +64,18 @@ static void lazy_init_name_hash(struct index_state *istate)
 
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
+       ce->ce_flags &= ~CE_UNHASHED;
        istate->cache[nr] = ce;
        if (istate->name_hash_initialized)
                hash_index_entry(istate, ce);
 }
 
-/*
- * We don't actually *remove* it, we can just mark it invalid so that
- * we won't find it in lookups.
- *
- * Not only would we have to search the lists (simple enough), but
- * we'd also have to rehash other hash buckets in case this makes the
- * hash bucket empty (common). So it's much better to just mark
- * it.
- */
-static void remove_hash_entry(struct index_state *istate, struct cache_entry *ce)
-{
-       ce->ce_flags |= CE_UNHASHED;
-}
-
 static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
        struct cache_entry *old = istate->cache[nr];
 
-       if (ce != old) {
-               remove_hash_entry(istate, old);
-               set_index_entry(istate, nr, ce);
-       }
+       remove_index_entry(old);
+       set_index_entry(istate, nr, ce);
        istate->cache_changed = 1;
 }
 
@@ -265,13 +255,13 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)
        return changed;
 }
 
-static int is_racy_timestamp(struct index_state *istate, struct cache_entry *ce)
+static int is_racy_timestamp(const struct index_state *istate, struct cache_entry *ce)
 {
        return (istate->timestamp &&
                ((unsigned int)istate->timestamp) <= ce->ce_mtime);
 }
 
-int ie_match_stat(struct index_state *istate,
+int ie_match_stat(const struct index_state *istate,
                  struct cache_entry *ce, struct stat *st,
                  unsigned int options)
 {
@@ -314,7 +304,7 @@ int ie_match_stat(struct index_state *istate,
        return changed;
 }
 
-int ie_modified(struct index_state *istate,
+int ie_modified(const struct index_state *istate,
                struct cache_entry *ce, struct stat *st, unsigned int options)
 {
        int changed, changed_fs;
@@ -361,6 +351,41 @@ int base_name_compare(const char *name1, int len1, int mode1,
        return (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
 }
 
+/*
+ * df_name_compare() is identical to base_name_compare(), except it
+ * compares conflicting directory/file entries as equal. Note that
+ * while a directory name compares as equal to a regular file, they
+ * then individually compare _differently_ to a filename that has
+ * a dot after the basename (because '\0' < '.' < '/').
+ *
+ * This is used by routines that want to traverse the git namespace
+ * but then handle conflicting entries together when possible.
+ */
+int df_name_compare(const char *name1, int len1, int mode1,
+                   const char *name2, int len2, int mode2)
+{
+       int len = len1 < len2 ? len1 : len2, cmp;
+       unsigned char c1, c2;
+
+       cmp = memcmp(name1, name2, len);
+       if (cmp)
+               return cmp;
+       /* Directories and files compare equal (same length, same name) */
+       if (len1 == len2)
+               return 0;
+       c1 = name1[len];
+       if (!c1 && S_ISDIR(mode1))
+               c1 = '/';
+       c2 = name2[len];
+       if (!c2 && S_ISDIR(mode2))
+               c2 = '/';
+       if (c1 == '/' && !c2)
+               return 0;
+       if (c2 == '/' && !c1)
+               return 0;
+       return c1 - c2;
+}
+
 int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
 {
        int len1 = flags1 & CE_NAMEMASK;
@@ -387,7 +412,7 @@ int cache_name_compare(const char *name1, int flags1, const char *name2, int fla
        return 0;
 }
 
-int index_name_pos(struct index_state *istate, const char *name, int namelen)
+int index_name_pos(const struct index_state *istate, const char *name, int namelen)
 {
        int first, last;
 
@@ -413,7 +438,7 @@ int remove_index_entry_at(struct index_state *istate, int pos)
 {
        struct cache_entry *ce = istate->cache[pos];
 
-       remove_hash_entry(istate, ce);
+       remove_index_entry(ce);
        istate->cache_changed = 1;
        istate->cache_nr--;
        if (pos >= istate->cache_nr)
@@ -1176,7 +1201,7 @@ int discard_index(struct index_state *istate)
        return 0;
 }
 
-int unmerged_index(struct index_state *istate)
+int unmerged_index(const struct index_state *istate)
 {
        int i;
        for (i = 0; i < istate->cache_nr; i++) {
@@ -1321,7 +1346,7 @@ static int ce_write_entry(SHA_CTX *c, int fd, struct cache_entry *ce)
        return ce_write(c, fd, ondisk, size);
 }
 
-int write_index(struct index_state *istate, int newfd)
+int write_index(const struct index_state *istate, int newfd)
 {
        SHA_CTX c;
        struct cache_header hdr;