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, 3 insertions, 26 deletions

diff --git a/src/path.c b/src/path.c
index 263cf9e7c..5767faeed 100644
--- a/src/path.c
+++ b/src/path.c
@@ -679,37 +679,14 @@ int git_path_apply_relative(git_buf *target, const char *relpath)
 
 int git_path_cmp(
 	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))
 {
 	unsigned char c1, c2;
 	size_t len = len1 < len2 ? len1 : len2;
 	int cmp;
 
-	cmp = memcmp(name1, name2, len);
-	if (cmp)
-		return cmp;
-
-	c1 = name1[len];
-	c2 = name2[len];
-
-	if (c1 == '\0' && isdir1)
-		c1 = '/';
-
-	if (c2 == '\0' && isdir2)
-		c2 = '/';
-
-	return (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
-}
-
-int git_path_icmp(
-	const char *name1, size_t len1, int isdir1,
-	const char *name2, size_t len2, int isdir2)
-{
-	unsigned char c1, c2;
-	size_t len = len1 < len2 ? len1 : len2;
-	int cmp;
-
-	cmp = strncasecmp(name1, name2, len);
+	cmp = compare(name1, name2, len);
 	if (cmp)
 		return cmp;