Use Git's own tree entry sorting algorithm

If plain strcmp is used, as this code did before, the final sorting may
end up different from what git-add would do (for example, 'boost'
appearing before 'boost-build.jam', because Git sorts as if it were
spelled 'boost/').

If the sorting is incorrect like this, Git 1.7.4 insists that unmodified
files have been modified.  For example, my test repository has these
four entries:

drwxr-xr-x  199 johnw  wheel   6766 Feb  2 17:21 boost
-rw-r--r--    1 johnw  wheel    849 Feb  2 17:22 boost-build.jam
-rw-r--r--    1 johnw  wheel    989 Feb  2 17:21 boost.css
-rw-r--r--    1 johnw  wheel   6308 Feb  2 17:21 boost.png

Here is the output from git-ls-tree for these files, in a commit tree
created using git-add and git-commit:

100644 blob 8b8775433aef73e9e12609610ae2e35cf1e7ec2c    boost-build.jam
100644 blob 986c4050fa96d825a1311c8e871cdcc9a3e0d2c3    boost.css
100644 blob b4d51fcd5c9149fd77f5ca6ed2b6b1b70e8fe24f    boost.png
040000 tree 46537eeaa4d577010f19b1c9e940cae9a670ff5c    boost

Here is the output for the same commit produced using libgit2:

040000 tree c27c0fd1436f28a6ba99acd0a6c17d178ed58288	boost
100644 blob 8b8775433aef73e9e12609610ae2e35cf1e7ec2c	boost-build.jam
100644 blob 986c4050fa96d825a1311c8e871cdcc9a3e0d2c3	boost.css
100644 blob b4d51fcd5c9149fd77f5ca6ed2b6b1b70e8fe24f	boost.png

Due to this reordering, git-status claims the three blobs are always
modified, no matter what I do using git-read-tree or git-reset or
git-checkout to update the index.

1 files changed, 22 insertions, 1 deletions

diff --git a/src/tree.c b/src/tree.c
index 605af8b39..ab3bec8cd 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -40,12 +40,33 @@ int entry_search_cmp(const void *key, const void *array_member)
 	return strcmp(filename, entry->filename);
 }
 
+static int cache_name_compare(const char *name1, int len1, int isdir1,
+                              const char *name2, int len2, int isdir2)
+{
+	int len = len1 < len2 ? len1 : len2;
+	int cmp;
+
+	cmp = memcmp(name1, name2, len);
+	if (cmp)
+		return cmp;
+	if (len1 < len2)
+		return ((isdir1 == isdir2) ? -1 :
+                        (isdir1 ? '/' - name2[len1] : name2[len1] - '/'));
+	if (len1 > len2)
+		return ((isdir1 == isdir2) ? 1 :
+                        (isdir2 ? name1[len2] - '/' : '/' - name1[len2]));
+	return 0;
+}
+
 int entry_sort_cmp(const void *a, const void *b)
 {
 	const git_tree_entry *entry_a = *(const git_tree_entry **)(a);
 	const git_tree_entry *entry_b = *(const git_tree_entry **)(b);
 
-	return strcmp(entry_a->filename, entry_b->filename);
+	return cache_name_compare(entry_a->filename, strlen(entry_a->filename),
+                                  entry_a->attr & 040000,
+                                  entry_b->filename, strlen(entry_b->filename),
+                                  entry_b->attr & 040000);
 }
 
 void git_tree_clear_entries(git_tree *tree)