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, 2 insertions, 6 deletions

diff --git a/src/path.h b/src/path.h
index feefd65d1..ead4fa338 100644
--- a/src/path.h
+++ b/src/path.h
@@ -265,12 +265,8 @@ extern int git_path_direach(
  */
 extern int git_path_cmp(
 	const char *name1, size_t len1, int isdir1,
-	const char *name2, size_t len2, int isdir2);
-
-/** Path sort function that is case insensitive */
-extern int git_path_icmp(
-	const char *name1, size_t len1, int isdir1,
-	const char *name2, size_t len2, int isdir2);
+	const char *name2, size_t len2, int isdir2,
+	int (*compare)(const char *, const char *, size_t));
 
 /**
  * Invoke callback up path directory by directory until the ceiling is