From 77bc1dd2116696b6d187cc3bf76de583f4f804fc Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sat, 22 Jun 2019 21:07:30 +0200 Subject: Add test case for tree node sort Signed-off-by: David Oberhollenzer --- tests/Makemodule.am | 7 ++-- tests/fstree_sort.c | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 101 insertions(+), 2 deletions(-) create mode 100644 tests/fstree_sort.c 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 +#include +#include + +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; +} -- cgit v1.2.3