Cleanup: split fstree sort into 2 fstree independend functions

Make tree node list sort and recursive variant available and independend
of the fstree_t.

This is considered cleaner, since the fstree_t actually isn't needed for
any of this and we can just call the recusvie sort on the root instead,
and we can use the sort implementation directly for things like the
upcoming unit test.

Also this commit splits up the merge/sort implementation into a seperate
split and merge functions to make the code somewhat more readable.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

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;