thodg/libgit2/src

Diff

  • Show log

    Commit

  • Hash : 761aa2aa
    Author : Vicent Marti
    Date : 2011-07-13T02:49:47 

    tree: Fix wrong sort order when querying entries

Fixes #127 (that was quite an outstanding issue).

Rationale:

The tree objects on Git are stored and read following a very specific
sorting algorithm that places folders before files. That original sort
was the sort we were storing on memory, but this sort was being queried
with a binary search that used a simple `strcmp` for comparison, so
there were many instances where the search was failing.

Obviously, the most straightforward way to fix this is changing the
binary search CB to use the same comparison method as the sorting CB.
The problem with this is that the binary search callback compares a path
and an entry, so there is no way to know if the given path is a folder
or a standard file.

How do we work around this? Instead of splitting the `entry_byname`
method in two (one for searching directories and one for searching
normal files), we just assume that the path we are searching for is of
the same kind as the path it's being compared at the moment.

	return git_futils_cmp_path(
		ksearch->filename, ksearch->filename_len, entry->attr & 040000,
        entry->filename, entry->filename_len, entry->attr & 040000);

Since there cannot be a folder and a regular file with the same name on
the same tree, the most basic equality check will always fail
for all comparsions, until our path is compared with the actual entry we
are looking for; in this case, the matching will succeed with the file
type of the entry -- whatever it was initially.

I hope that makes sense.

PS: While I was at it, I switched the cmp methods to use cached values
for the length of each filename. That makes searches and sorts
retardedly fast -- I was wondering the reason of the performance hiccups
on massive trees; it's because of 2*strlen for each comparsion call.

kmx.io     mail     discord kmxgit v0.4.0