From e5fa9d585ed090602bcc045689046702199def86 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sat, 16 Oct 2021 21:50:40 +0200 Subject: Cleanup: remove node sorting from libfstree Always insert the tree nodes in the correct oder and remove the post-process sorting step. Signed-off-by: David Oberhollenzer --- lib/fstree/Makemodule.am | 2 +- lib/fstree/fstree_sort.c | 60 ----------------------------- lib/fstree/internal.h | 3 -- lib/fstree/mknode.c | 27 ++++++++++--- lib/fstree/post_process.c | 12 ------ tests/libfstree/fstree_sort.c | 89 ++++++++++++++++++------------------------- tests/libfstree/mknode_dir.c | 6 +-- 7 files changed, 62 insertions(+), 137 deletions(-) delete mode 100644 lib/fstree/fstree_sort.c diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am index 97a2e6b..4bdea27 100644 --- a/lib/fstree/Makemodule.am +++ b/lib/fstree/Makemodule.am @@ -1,5 +1,5 @@ libfstree_a_SOURCES = lib/fstree/fstree.c lib/fstree/fstree_from_file.c -libfstree_a_SOURCES += lib/fstree/fstree_sort.c lib/fstree/hardlink.c +libfstree_a_SOURCES += lib/fstree/hardlink.c libfstree_a_SOURCES += lib/fstree/post_process.c lib/fstree/get_path.c libfstree_a_SOURCES += lib/fstree/mknode.c lib/fstree/fstree_from_dir.c libfstree_a_SOURCES += lib/fstree/add_by_path.c lib/fstree/get_by_path.c diff --git a/lib/fstree/fstree_sort.c b/lib/fstree/fstree_sort.c deleted file mode 100644 index 58ffadf..0000000 --- a/lib/fstree/fstree_sort.c +++ /dev/null @@ -1,60 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * fstree_sort.c - * - * Copyright (C) 2019 David Oberhollenzer - * Copyright (C) 2019 Zachary Dremann - */ -#include "internal.h" - -#include - -static tree_node_t *merge(tree_node_t *lhs, tree_node_t *rhs) -{ - tree_node_t *it; - tree_node_t *head = NULL; - tree_node_t **next_ptr = &head; - - while (lhs != NULL && rhs != NULL) { - if (strcmp(lhs->name, rhs->name) <= 0) { - it = lhs; - lhs = lhs->next; - } else { - it = rhs; - rhs = rhs->next; - } - - *next_ptr = it; - next_ptr = &it->next; - } - - it = (lhs != NULL ? lhs : rhs); - *next_ptr = it; - return head; -} - -tree_node_t *tree_node_list_sort(tree_node_t *head) -{ - tree_node_t *it, *half, *prev; - - it = half = prev = head; - while (it != NULL) { - prev = half; - half = half->next; - it = it->next; - if (it != NULL) { - it = it->next; - } - } - - // half refers to the (count/2)'th element ROUNDED UP. - // It will be null therefore only in the empty and the - // single element list - if (half == NULL) { - return head; - } - - prev->next = NULL; - - return merge(tree_node_list_sort(head), tree_node_list_sort(half)); -} diff --git a/lib/fstree/internal.h b/lib/fstree/internal.h index e8e5eef..c594f64 100644 --- a/lib/fstree/internal.h +++ b/lib/fstree/internal.h @@ -10,9 +10,6 @@ #include "config.h" #include "fstree.h" -/* ASCIIbetically sort a linked list of tree nodes */ -tree_node_t *tree_node_list_sort(tree_node_t *head); - /* If the environment variable SOURCE_DATE_EPOCH is set to a parsable number that fits into an unsigned 32 bit value, return its value. Otherwise, diff --git a/lib/fstree/mknode.c b/lib/fstree/mknode.c index f836c67..75fa46a 100644 --- a/lib/fstree/mknode.c +++ b/lib/fstree/mknode.c @@ -12,6 +12,25 @@ #include #include +static void insert_sorted(tree_node_t *root, tree_node_t *n) +{ + tree_node_t *it = root->data.dir.children, *prev = NULL; + + while (it != NULL && strcmp(it->name, n->name) < 0) { + prev = it; + it = it->next; + } + + n->parent = root; + n->next = it; + + if (prev == NULL) { + root->data.dir.children = n; + } else { + prev->next = n; + } +} + tree_node_t *fstree_mknode(tree_node_t *parent, const char *name, size_t name_len, const char *extra, const struct stat *sb) @@ -33,12 +52,6 @@ tree_node_t *fstree_mknode(tree_node_t *parent, const char *name, if (n == NULL) return NULL; - if (parent != NULL) { - n->next = parent->data.dir.children; - parent->data.dir.children = n; - n->parent = parent; - } - n->xattr_idx = 0xFFFFFFFF; n->uid = sb->st_uid; n->gid = sb->st_gid; @@ -75,6 +88,8 @@ tree_node_t *fstree_mknode(tree_node_t *parent, const char *name, } if (parent != NULL) { + insert_sorted(parent, n); + if (parent->link_count == 0x0FFFF) { free(n); errno = EMLINK; diff --git a/lib/fstree/post_process.c b/lib/fstree/post_process.c index 87b3d4c..93a7664 100644 --- a/lib/fstree/post_process.c +++ b/lib/fstree/post_process.c @@ -100,16 +100,6 @@ fail_link_loop: { return -1; } -static void sort_recursive(tree_node_t *n) -{ - 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)) - sort_recursive(n); - } -} - static file_info_t *file_list_dfs(tree_node_t *n) { if (S_ISREG(n->mode)) { @@ -196,8 +186,6 @@ int fstree_post_process(fstree_t *fs) { size_t inum; - sort_recursive(fs->root); - if (resolve_hard_links_dfs(fs, fs->root)) return -1; diff --git a/tests/libfstree/fstree_sort.c b/tests/libfstree/fstree_sort.c index 618ae9f..6db607d 100644 --- a/tests/libfstree/fstree_sort.c +++ b/tests/libfstree/fstree_sort.c @@ -7,7 +7,6 @@ #include "config.h" #include "fstree.h" -#include "internal.h" #include "../test.h" int main(int argc, char **argv) @@ -18,86 +17,72 @@ int main(int argc, char **argv) int ret; (void)argc; (void)argv; - memset(&fs, 0, sizeof(fs)); memset(&sb, 0, sizeof(sb)); sb.st_mode = S_IFBLK | 0600; sb.st_rdev = 1337; - a = fstree_mknode(NULL, "a", 1, NULL, &sb); - b = fstree_mknode(NULL, "b", 1, NULL, &sb); - c = fstree_mknode(NULL, "c", 1, NULL, &sb); - d = fstree_mknode(NULL, "d", 1, NULL, &sb); - TEST_ASSERT(a != NULL && b != NULL && c != NULL && d != NULL); + /* in order */ + ret = fstree_init(&fs, NULL); + TEST_EQUAL_I(ret, 0); - /* empty list */ - TEST_NULL(tree_node_list_sort(NULL)); - - /* single element */ - TEST_ASSERT(tree_node_list_sort(a) == a); + a = fstree_mknode(fs.root, "a", 1, NULL, &sb); + TEST_NOT_NULL(a); + TEST_ASSERT(fs.root->data.dir.children == a); TEST_NULL(a->next); - /* two elements, reverse order */ - b->next = a; - TEST_ASSERT(tree_node_list_sort(b) == a); - TEST_ASSERT(a->next == b); - TEST_NULL(b->next); - - /* two elements, sorted order */ - TEST_ASSERT(tree_node_list_sort(a) == a); + b = fstree_mknode(fs.root, "b", 1, NULL, &sb); + TEST_NOT_NULL(a); + TEST_ASSERT(fs.root->data.dir.children == a); TEST_ASSERT(a->next == b); TEST_NULL(b->next); - /* three elements, reverse order */ - c->next = b; - b->next = a; - a->next = NULL; - - TEST_ASSERT(tree_node_list_sort(c) == a); + c = fstree_mknode(fs.root, "c", 1, NULL, &sb); + TEST_NOT_NULL(c); + TEST_ASSERT(fs.root->data.dir.children == a); TEST_ASSERT(a->next == b); TEST_ASSERT(b->next == c); TEST_NULL(c->next); - /* three elements, ordered */ - TEST_ASSERT(tree_node_list_sort(a) == a); + d = fstree_mknode(fs.root, "d", 1, NULL, &sb); + TEST_NOT_NULL(d); + TEST_ASSERT(fs.root->data.dir.children == a); TEST_ASSERT(a->next == b); TEST_ASSERT(b->next == c); - TEST_NULL(c->next); + TEST_ASSERT(c->next == d); + TEST_NULL(d->next); - /* four elements, reverse order */ - d->next = c; - c->next = b; - b->next = a; - a->next = NULL; + fstree_cleanup(&fs); - TEST_ASSERT(tree_node_list_sort(d) == a); - TEST_ASSERT(a->next == b); - TEST_ASSERT(b->next == c); + /* out-of-order */ + ret = fstree_init(&fs, NULL); + TEST_EQUAL_I(ret, 0); + + d = fstree_mknode(fs.root, "d", 1, NULL, &sb); + TEST_NOT_NULL(d); + TEST_ASSERT(fs.root->data.dir.children == d); + TEST_NULL(d->next); + + c = fstree_mknode(fs.root, "c", 1, NULL, &sb); + TEST_NOT_NULL(c); + TEST_ASSERT(fs.root->data.dir.children == c); TEST_ASSERT(c->next == d); TEST_NULL(d->next); - /* four elements, sorted order */ - TEST_ASSERT(tree_node_list_sort(a) == a); - TEST_ASSERT(a->next == b); + b = fstree_mknode(fs.root, "b", 1, NULL, &sb); + TEST_NOT_NULL(b); + TEST_ASSERT(fs.root->data.dir.children == b); TEST_ASSERT(b->next == c); TEST_ASSERT(c->next == d); TEST_NULL(d->next); - /* force merge sort to go through LRLR pattern */ - b->next = a; - a->next = d; - d->next = c; - c->next = NULL; - - TEST_ASSERT(tree_node_list_sort(b) == a); + a = fstree_mknode(fs.root, "a", 1, NULL, &sb); + TEST_NOT_NULL(a); + TEST_ASSERT(fs.root->data.dir.children == a); TEST_ASSERT(a->next == b); TEST_ASSERT(b->next == c); TEST_ASSERT(c->next == d); TEST_NULL(d->next); - /* cleanup and done */ - free(a); - free(b); - free(c); - free(d); + fstree_cleanup(&fs); return EXIT_SUCCESS; } diff --git a/tests/libfstree/mknode_dir.c b/tests/libfstree/mknode_dir.c index 900edaa..63e01c1 100644 --- a/tests/libfstree/mknode_dir.c +++ b/tests/libfstree/mknode_dir.c @@ -48,10 +48,10 @@ int main(int argc, char **argv) TEST_ASSERT(a->parent == root); TEST_ASSERT(b->parent == root); TEST_EQUAL_UI(b->link_count, 2); - TEST_ASSERT(root->data.dir.children == b); + TEST_ASSERT(root->data.dir.children == a); + TEST_ASSERT(a->next == b); TEST_EQUAL_UI(root->link_count, 4); - TEST_ASSERT(b->next == a); - TEST_NULL(a->next); + TEST_NULL(b->next); TEST_NULL(root->parent); TEST_NULL(root->next); -- cgit v1.2.3