iterators: refactored tree iterator

Refactored the tree iterator to never recurse; simply process the
next entry in order in `advance`.  Additionally, reduce the number of
allocations and sorting as much as possible to provide a ~30% speedup
on case-sensitive iteration.  (The gains for case-insensitive iteration
are less majestic.)

2 files changed, 4 insertions, 11 deletions

diff --git a/tests/diff/iterator.c b/tests/diff/iterator.c
index b64c95415..4c9585047 100644
--- a/tests/diff/iterator.c
+++ b/tests/diff/iterator.c
@@ -264,37 +264,30 @@ static void check_tree_entry(
 	const git_index_entry *ie;
 	const git_tree_entry *te;
 	const git_tree *tree;
-	git_buf path = GIT_BUF_INIT;
 
 	cl_git_pass(git_iterator_current_tree_entry(&te, i));
 	cl_assert(te);
 	cl_assert(git_oid_streq(te->oid, oid) == 0);
 
 	cl_git_pass(git_iterator_current(&ie, i));
-	cl_git_pass(git_buf_sets(&path, ie->path));
 
 	if (oid_p) {
-		git_buf_rtruncate_at_char(&path, '/');
-		cl_git_pass(git_iterator_current_parent_tree(&tree, i, path.ptr));
+		cl_git_pass(git_iterator_current_parent_tree(&tree, i, 0));
 		cl_assert(tree);
 		cl_assert(git_oid_streq(git_tree_id(tree), oid_p) == 0);
 	}
 
 	if (oid_pp) {
-		git_buf_rtruncate_at_char(&path, '/');
-		cl_git_pass(git_iterator_current_parent_tree(&tree, i, path.ptr));
+		cl_git_pass(git_iterator_current_parent_tree(&tree, i, 1));
 		cl_assert(tree);
 		cl_assert(git_oid_streq(git_tree_id(tree), oid_pp) == 0);
 	}
 
 	if (oid_ppp) {
-		git_buf_rtruncate_at_char(&path, '/');
-		cl_git_pass(git_iterator_current_parent_tree(&tree, i, path.ptr));
+		cl_git_pass(git_iterator_current_parent_tree(&tree, i, 2));
 		cl_assert(tree);
 		cl_assert(git_oid_streq(git_tree_id(tree), oid_ppp) == 0);
 	}
-
-	git_buf_free(&path);
 }
 
 void test_diff_iterator__tree_special_functions(void)
diff --git a/tests/repo/iterator.c b/tests/repo/iterator.c
index 0ab8d68c0..f3a0682f9 100644
--- a/tests/repo/iterator.c
+++ b/tests/repo/iterator.c
@@ -1455,7 +1455,7 @@ void test_repo_iterator__treefilelist(void)
 	git_repository_head_tree(&tree, g_repo);
 
 	/* All indexfilelist iterator tests are "autoexpand with no tree entries" */
-	/* In this test we DO NOT force a case on the iteratords and verify default behavior. */
+	/* In this test we DO NOT force a case on the iterators and verify default behavior. */
 
 	i_opts.pathlist.strings = (char **)filelist.contents;
 	i_opts.pathlist.count = filelist.length;