5 files changed, 37 insertions, 38 deletions

diff --git a/include/fstree.h b/include/fstree.h
index f23ab70..74d1c7f 100644
--- a/include/fstree.h
+++ b/include/fstree.h
@@ -236,9 +236,6 @@ int fstree_from_file(fstree_t *fs, const char *filename, const char *rootdir);
  */
 int fstree_from_dir(fstree_t *fs, const char *path);
 
-/* Lexicographically sort all directory contents. */
-void fstree_sort(fstree_t *fs);
-
 /* Add labels from an SELinux labeling file to all tree nodes.
    Returns 0 on success. Internally prints errors to stderr. */
 int fstree_relabel_selinux(fstree_t *fs, const char *filename);
@@ -257,4 +254,10 @@ char *fstree_get_path(tree_node_t *node);
 /* get a struct stat from a tree node */
 void fstree_node_stat(fstree_t *fs, tree_node_t *node, struct stat *sb);
 
+/* ASCIIbetically sort a linked list of tree nodes */
+tree_node_t *tree_node_list_sort(tree_node_t *head);
+
+/* ASCIIbetically sort all sub directories recursively */
+void tree_node_sort_recursive(tree_node_t *root);
+
 #endif /* FSTREE_H */
diff --git a/lib/fstree/fstree_sort.c b/lib/fstree/fstree_sort.c
index 9f07c92..cd01235 100644
--- a/lib/fstree/fstree_sort.c
+++ b/lib/fstree/fstree_sort.c
@@ -3,32 +3,9 @@
 
 #include <string.h>
 
-static tree_node_t *sort_list(tree_node_t *head)
+static tree_node_t *merge(tree_node_t *lhs, tree_node_t *rhs)
 {
-	tree_node_t *it, *prev, *lhs, *rhs;
-	size_t i, count = 0;
-
-	for (it = head; it != NULL; it = it->next)
-		++count;
-
-	if (count < 2)
-		return head;
-
-	prev = NULL;
-	it = head;
-
-	for (i = 0; i < count / 2; ++i) {
-		prev = it;
-		it = it->next;
-	}
-
-	prev->next = NULL;
-
-	lhs = sort_list(head);
-	rhs = sort_list(it);
-
-	head = NULL;
-	prev = NULL;
+	tree_node_t *head = NULL, *prev = NULL, *it;
 
 	while (lhs != NULL && rhs != NULL) {
 		if (strcmp(lhs->name, rhs->name) <= 0) {
@@ -60,17 +37,36 @@ static tree_node_t *sort_list(tree_node_t *head)
 	return head;
 }
 
-static void sort_directory(tree_node_t *n)
+tree_node_t *tree_node_list_sort(tree_node_t *head)
 {
-	n->data.dir->children = sort_list(n->data.dir->children);
+	tree_node_t *it, *prev;
+	size_t i, count = 0;
 
-	for (n = n->data.dir->children; n != NULL; n = n->next) {
-		if (S_ISDIR(n->mode))
-			sort_directory(n);
+	for (it = head; it != NULL; it = it->next)
+		++count;
+
+	if (count < 2)
+		return head;
+
+	prev = NULL;
+	it = head;
+
+	for (i = 0; i < count / 2; ++i) {
+		prev = it;
+		it = it->next;
 	}
+
+	prev->next = NULL;
+
+	return merge(tree_node_list_sort(head), tree_node_list_sort(it));
 }
 
-void fstree_sort(fstree_t *fs)
+void tree_node_sort_recursive(tree_node_t *n)
 {
-	sort_directory(fs->root);
+	n->data.dir->children = tree_node_list_sort(n->data.dir->children);
+
+	for (n = n->data.dir->children; n != NULL; n = n->next) {
+		if (S_ISDIR(n->mode))
+			tree_node_sort_recursive(n);
+	}
 }
diff --git a/lib/sqfs/deserialize_fstree.c b/lib/sqfs/deserialize_fstree.c
index 2994007..e90e1c1 100644
--- a/lib/sqfs/deserialize_fstree.c
+++ b/lib/sqfs/deserialize_fstree.c
@@ -175,7 +175,7 @@ int deserialize_fstree(fstree_t *out, sqfs_super_t *super, compressor_t *cmp,
 	if (fill_dir(ir, dr, out->root, super, &idtbl, flags))
 		goto fail_fs;
 
-	fstree_sort(out);
+	tree_node_sort_recursive(out->root);
 
 	status = 0;
 out_id:
diff --git a/mkfs/mkfs.c b/mkfs/mkfs.c
index 08744f8..12b4de9 100644
--- a/mkfs/mkfs.c
+++ b/mkfs/mkfs.c
@@ -109,7 +109,7 @@ int main(int argc, char **argv)
 			goto out_fstree;
 	}
 
-	fstree_sort(&fs);
+	tree_node_sort_recursive(fs.root);
 
 	if (fstree_gen_inode_table(&fs))
 		goto out_fstree;
diff --git a/tar/tar2sqfs.c b/tar/tar2sqfs.c
index 0c23b61..6f6ba21 100644
--- a/tar/tar2sqfs.c
+++ b/tar/tar2sqfs.c
@@ -214,7 +214,7 @@ int main(int argc, char **argv)
 	if (data_writer_flush_fragments(data))
 		goto out;
 
-	fstree_sort(&fs);
+	tree_node_sort_recursive(fs.root);
 	if (fstree_gen_inode_table(&fs))
 		goto out;