summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-06-22 20:02:10 +0200
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-06-22 20:04:25 +0200
commit6cbc85c018187a2b28bf0607f52bc258cc273253 (patch)
tree1081a7da4afef0236e9ef963bf43cfd2f0d02fba
parent8edee9c4967ed9f3ce53cdc752cd2c02ca585bfe (diff)
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>
-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;