Am 13.02.2013 19:18, schrieb Jeff King:
> Moreover, looking at it again, I
> don't think my patch produces the right behavior: we have a single
> dir_next pointer, even though the same ce_entry may appear under many
> directory hashes. So the cache_entries that has to "dir/foo/" and those
> that hash to "dir/bar/" may get confused, because they will also both be
> found under "dir/", and both try to create a linked list from the
> dir_next pointer.

Indeed. In the worst case, this causes an endless loop if ce->dir_next == ce
mkdir V
mkdir V/XQANY
touch V/XQANY/test
git init
git config core.ignorecase true
git add .
git status
Note: "V/", "V/XQANY/" and "WURZAUP/" all have the same hash_name. Although I 
found those strange values by brute force, hash collisions in 32 bit values are 
not that uncommon in real life :-)

> Looking at Karsten's patch, it seems like it will not add a cache entry
> if there is one of the same name. But I'm not sure if that is right, as
> the old one might be CE_UNHASHED (or it might get removed later). You
> actually want to be able to find each cache_entry that has a file under
> the directory at the hash of that directory, so you can make sure it is
> still valid.

Yes, the patch was just to show potential performance savings, I didn't 
consider CE_UNHASHED at all.

> I think the best way forward is to actually create a separate hash table
> for the directory lookups. I note that we only care about these entries
> in directory_exists_in_index_icase, which is really about whether
> something is there, versus what exactly is there. So could we maybe get
> by with a separate hash table that stores a count of entries at each
> directory, and increment/decrement the count when we add/remove entries?

Alternatively, we could simply create normal cache_entries for the directories 
that are linked via ce->next, but have a trailing '/' in their name?

Reference counting sounds good to me, at least better than allocating directory 
entries per cache entry * parent dirs.

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at

Reply via email to