aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--tests/Makemodule.am7
-rw-r--r--tests/fstree_sort.c96
2 files changed, 101 insertions, 2 deletions
diff --git a/tests/Makemodule.am b/tests/Makemodule.am
index 860cc49..4e8314a 100644
--- a/tests/Makemodule.am
+++ b/tests/Makemodule.am
@@ -22,10 +22,13 @@ test_add_by_path_LDADD = libfstree.a libutil.a
test_get_path_SOURCES = tests/get_path.c
test_get_path_LDADD = libfstree.a libutil.a
+test_fstree_sort_SOURCES = tests/fstree_sort.c
+test_fstree_sort_LDADD = libfstree.a libutil.a
+
check_PROGRAMS += test_canonicalize_name test_mknode_simple test_mknode_slink
check_PROGRAMS += test_mknode_reg test_mknode_dir test_gen_inode_table
-check_PROGRAMS += test_add_by_path test_get_path
+check_PROGRAMS += test_add_by_path test_get_path test_fstree_sort
TESTS += test_canonicalize_name test_mknode_simple test_mknode_slink
TESTS += test_mknode_reg test_mknode_dir test_gen_inode_table
-TESTS += test_add_by_path test_get_path
+TESTS += test_add_by_path test_get_path test_fstree_sort
diff --git a/tests/fstree_sort.c b/tests/fstree_sort.c
new file mode 100644
index 0000000..8faa514
--- /dev/null
+++ b/tests/fstree_sort.c
@@ -0,0 +1,96 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "fstree.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+int main(void)
+{
+ tree_node_t *a, *b, *c, *d;
+ struct stat sb;
+ fstree_t fs;
+
+ memset(&fs, 0, sizeof(fs));
+ memset(&sb, 0, sizeof(sb));
+ sb.st_mode = S_IFBLK | 0600;
+ sb.st_rdev = 1337;
+
+ a = fstree_mknode(&fs, NULL, "a", 1, NULL, &sb);
+ b = fstree_mknode(&fs, NULL, "b", 1, NULL, &sb);
+ c = fstree_mknode(&fs, NULL, "c", 1, NULL, &sb);
+ d = fstree_mknode(&fs, NULL, "d", 1, NULL, &sb);
+ assert(a != NULL && b != NULL && c != NULL && d != NULL);
+
+ /* empty list */
+ assert(tree_node_list_sort(NULL) == NULL);
+
+ /* single element */
+ assert(tree_node_list_sort(a) == a);
+ assert(a->next == NULL);
+
+ /* two elements, reverse order */
+ b->next = a;
+ assert(tree_node_list_sort(b) == a);
+ assert(a->next == b);
+ assert(b->next == NULL);
+
+ /* two elements, sorted order */
+ assert(tree_node_list_sort(a) == a);
+ assert(a->next == b);
+ assert(b->next == NULL);
+
+ /* three elements, reverse order */
+ c->next = b;
+ b->next = a;
+ a->next = NULL;
+
+ assert(tree_node_list_sort(c) == a);
+ assert(a->next == b);
+ assert(b->next == c);
+ assert(c->next == NULL);
+
+ /* three elements, ordered */
+ assert(tree_node_list_sort(a) == a);
+ assert(a->next == b);
+ assert(b->next == c);
+ assert(c->next == NULL);
+
+ /* four elements, reverse order */
+ d->next = c;
+ c->next = b;
+ b->next = a;
+ a->next = NULL;
+
+ assert(tree_node_list_sort(d) == a);
+ assert(a->next == b);
+ assert(b->next == c);
+ assert(c->next == d);
+ assert(d->next == NULL);
+
+ /* four elements, sorted order */
+ assert(tree_node_list_sort(a) == a);
+ assert(a->next == b);
+ assert(b->next == c);
+ assert(c->next == d);
+ assert(d->next == NULL);
+
+ /* force merge sort to go through LRLR pattern */
+ b->next = a;
+ a->next = d;
+ d->next = c;
+ c->next = NULL;
+
+ assert(tree_node_list_sort(b) == a);
+ assert(a->next == b);
+ assert(b->next == c);
+ assert(c->next == d);
+ assert(d->next == NULL);
+
+ /* cleanup and done */
+ free(a);
+ free(b);
+ free(c);
+ free(d);
+ return EXIT_SUCCESS;
+}