tree: Add traversal in post-order

2 files changed, 84 insertions, 2 deletions

diff --git a/include/git2/tree.h b/include/git2/tree.h
index 8d638f723..68d82351a 100644
--- a/include/git2/tree.h
+++ b/include/git2/tree.h
@@ -282,6 +282,36 @@ GIT_EXTERN(int) git_treebuilder_write(git_oid *oid, git_repository *repo, git_tr
  * entry, GIT_EINVALIDPATH or an error code
  */
 GIT_EXTERN(int) git_tree_frompath(git_tree **parent_out, git_tree *root, const char *treeentry_path);
+
+/** Callback for the tree traversal method */
+typedef int (*git_treewalk_cb)(const char *root, git_tree_entry *entry);
+
+/** Tree traversal modes */
+enum git_treewalk_mode {
+	GIT_TREEWALK_PRE = 0, /* Pre-order */
+	GIT_TREEWALK_POST = 1, /* Post-order */
+};
+
+/**
+ * Traverse the entries in a tree and its subtrees in
+ * post or pre order
+ *
+ * The entries will be traversed in the specified order,
+ * children subtrees will be automatically loaded as required,
+ * and the `callback` will be called once per entry with
+ * the current (relative) root for the entry and the entry
+ * data itself.
+ *
+ * If the callback returns a negative value, the passed entry
+ * will be skiped on the traversal.
+ *
+ * @param tree The tree to walk
+ * @param callback Function to call on each tree entry
+ * @param mode Traversal mode (pre or post-order)
+ * @return GIT_SUCCESS or an error code
+ */
+GIT_EXTERN(int) git_tree_walk(git_tree *walk, git_treewalk_cb callback, int mode);
+
 /** @} */
 GIT_END_DECL
 #endif
diff --git a/src/tree.c b/src/tree.c
index 00aefc295..77034fa43 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -15,6 +15,8 @@
 #define MAX_FILEMODE 0777777
 #define MAX_FILEMODE_BYTES 6
 
+#define ENTRY_IS_TREE(e) ((e)->attr & 040000)
+
 static int valid_attributes(const int attributes)
 {
 	return attributes >= 0 && attributes <= MAX_FILEMODE;
@@ -31,8 +33,8 @@ static int entry_sort_cmp(const void *a, const void *b)
 	const git_tree_entry *entry_b = (const git_tree_entry *)(b);
 
 	return git_futils_cmp_path(
-		entry_a->filename, entry_a->filename_len, entry_a->attr & 040000,
-		entry_b->filename, entry_b->filename_len, entry_b->attr & 040000);
+		entry_a->filename, entry_a->filename_len, ENTRY_IS_TREE(entry_a),
+		entry_b->filename, entry_b->filename_len, ENTRY_IS_TREE(entry_b));
 }
 
 
@@ -654,3 +656,53 @@ int git_tree_frompath(git_tree **parent_out, git_tree *root, const char *treeent
 	strcpy(buffer, treeentry_path);
 	return tree_frompath(parent_out, root, buffer, 0);
 }
+
+static int tree_walk_post(git_tree *tree, git_treewalk_cb callback, char *root, size_t root_len)
+{
+	int error;
+	unsigned int i;
+
+	for (i = 0; i < tree->entries.length; ++i) {
+		git_tree_entry *entry = tree->entries.contents[i];
+
+		root[root_len] = '\0';
+
+		if (callback(root, entry) < 0)
+			continue;
+
+		if (ENTRY_IS_TREE(entry)) {
+			git_tree *subtree;
+
+			if ((error = git_tree_lookup(&subtree, tree->object.repo, &entry->oid)) < 0)
+				return error;
+
+			strcpy(root + root_len, entry->filename);
+			root[root_len + entry->filename_len] = '/';
+
+			tree_walk_post(subtree, callback, root, root_len + entry->filename_len + 1);
+
+			git_tree_close(subtree);
+		}
+	}
+
+	return GIT_SUCCESS;
+}
+
+int git_tree_walk(git_tree *tree, git_treewalk_cb callback, int mode)
+{
+	char root_path[GIT_PATH_MAX];
+
+	root_path[0] = '\0';
+	switch (mode) {
+		case GIT_TREEWALK_POST:
+			return tree_walk_post(tree, callback, root_path, 0);
+
+		case GIT_TREEWALK_PRE:
+			return git__throw(GIT_ENOTIMPLEMENTED,
+				"Preorder tree walking is still not implemented");
+
+		default:
+			return git__throw(GIT_EINVALIDARGS,
+				"Invalid walking mode for tree walk");
+	}
+}