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

diff --git a/src/pool.c b/src/pool.c
index 64b5c6b00..6b78a0b74 100644
--- a/src/pool.c
+++ b/src/pool.c
@@ -235,10 +235,28 @@ char *git_pool_strcat(git_pool *pool, const char *a, const char *b)
 
 void git_pool_free(git_pool *pool, void *ptr)
 {
-	assert(pool && ptr && pool->item_size >= sizeof(void*));
+	assert(pool && pool->item_size >= sizeof(void*));
 
-	*((void **)ptr) = pool->free_list;
-	pool->free_list = ptr;
+	if (ptr) {
+		*((void **)ptr) = pool->free_list;
+		pool->free_list = ptr;
+	}
+}
+
+void git_pool_free_array(git_pool *pool, size_t count, void **ptrs)
+{
+	size_t i;
+
+	assert(pool && ptrs && pool->item_size >= sizeof(void*));
+
+	if (!count)
+		return;
+
+	for (i = count - 1; i > 0; --i)
+		*((void **)ptrs[i]) = ptrs[i - 1];
+
+	*((void **)ptrs[0]) = pool->free_list;
+	pool->free_list = ptrs[count - 1];
 }
 
 uint32_t git_pool__open_pages(git_pool *pool)