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, 50 insertions, 0 deletions

diff --git a/tests-clar/core/pool.c b/tests-clar/core/pool.c
index 5ed97366f..c42bb6da0 100644
--- a/tests-clar/core/pool.c
+++ b/tests-clar/core/pool.c
@@ -83,3 +83,53 @@ void test_core_pool__2(void)
 
 	git_pool_clear(&p);
 }
+
+void test_core_pool__free_list(void)
+{
+	int i;
+	git_pool p;
+	void *ptr, *ptrs[50];
+
+	cl_git_pass(git_pool_init(&p, 100, 100));
+
+	for (i = 0; i < 10; ++i) {
+		ptr = git_pool_malloc(&p, 1);
+		cl_assert(ptr != NULL);
+	}
+	cl_assert_equal_i(10, (int)p.items);
+
+	for (i = 0; i < 50; ++i) {
+		ptrs[i] = git_pool_malloc(&p, 1);
+		cl_assert(ptrs[i] != NULL);
+	}
+	cl_assert_equal_i(60, (int)p.items);
+
+	git_pool_free(&p, ptr);
+	cl_assert_equal_i(60, (int)p.items);
+
+	git_pool_free_array(&p, 50, ptrs);
+	cl_assert_equal_i(60, (int)p.items);
+
+	for (i = 0; i < 50; ++i) {
+		ptrs[i] = git_pool_malloc(&p, 1);
+		cl_assert(ptrs[i] != NULL);
+	}
+	cl_assert_equal_i(60, (int)p.items);
+
+	for (i = 0; i < 111; ++i) {
+		ptr = git_pool_malloc(&p, 1);
+		cl_assert(ptr != NULL);
+	}
+	cl_assert_equal_i(170, (int)p.items);
+
+	git_pool_free_array(&p, 50, ptrs);
+	cl_assert_equal_i(170, (int)p.items);
+
+	for (i = 0; i < 50; ++i) {
+		ptrs[i] = git_pool_malloc(&p, 1);
+		cl_assert(ptrs[i] != NULL);
+	}
+	cl_assert_equal_i(170, (int)p.items);
+
+	git_pool_clear(&p);
+}