From 0c46863384e9da3746b90ddf81eef6d25d475e5c Mon Sep 17 00:00:00 2001 From: Russell Belfer Date: Thu, 14 Mar 2013 13:40:15 -0700 Subject: 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). --- src/pool.c | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-) (limited to 'src/pool.c') 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) -- cgit v1.2.3