aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/fstree.h9
-rw-r--r--lib/fstree/fstree_sort.c60
-rw-r--r--lib/sqfs/deserialize_fstree.c2
-rw-r--r--mkfs/mkfs.c2
-rw-r--r--tar/tar2sqfs.c2
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;