Improved tree iterator internals

This updates the tree iterator internals to be more efficient.

The tree_iterator_entry objects are now kept as pointers that are
allocated from a git_pool, so that we may use git__tsort_r for
sorting (which is better than qsort, given that the tree is
likely mostly ordered already).

Those tree_iterator_entry objects now keep direct pointers to the
data they refer to instead of keeping indirect index values.  This
simplifies a lot of the data structure traversal code.

This also adds bsearch to find the start item position for range-
limited tree iterators, and is more explicit about using
git_path_cmp instead of reimplementing it.  The git_path_cmp
changed a bit to make it easier for tree_iterators to use it (but
it was barely being used previously, so not a big deal).

This adds a git_pool_free_array function that efficiently frees a
list of pool allocated pointers (which the tree_iterator keeps).
Also, added new tests for the git_pool free list functionality
that was not previously being tested (or used).

1 files changed, 13 insertions, 8 deletions

diff --git a/src/tree.c b/src/tree.c
index 11123a18a..17b3c378d 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -55,23 +55,28 @@ static int valid_entry_name(const char *filename)
 		  strcmp(filename, DOT_GIT) != 0));
 }
 
-int git_tree_entry_cmp(const git_tree_entry *e1, const git_tree_entry *e2)
+static int entry_sort_cmp(const void *a, const void *b)
 {
+	const git_tree_entry *e1 = (const git_tree_entry *)a;
+	const git_tree_entry *e2 = (const git_tree_entry *)b;
+
 	return git_path_cmp(
 		e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
-		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2));
+		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2),
+		git__strncmp);
 }
 
-int git_tree_entry_icmp(const git_tree_entry *e1, const git_tree_entry *e2)
+int git_tree_entry_cmp(const git_tree_entry *e1, const git_tree_entry *e2)
 {
-	return git_path_icmp(
-		e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
-		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2));
+	return entry_sort_cmp(e1, e2);
 }
 
-static int entry_sort_cmp(const void *a, const void *b)
+int git_tree_entry_icmp(const git_tree_entry *e1, const git_tree_entry *e2)
 {
-	return git_tree_entry_cmp((const git_tree_entry *)a, (const git_tree_entry *)b);
+	return git_path_cmp(
+		e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
+		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2),
+		git__strncasecmp);
 }
 
 static git_tree_entry *alloc_entry(const char *filename)