aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/fstree/Makemodule.am2
-rw-r--r--lib/fstree/fstree_sort.c60
-rw-r--r--lib/fstree/internal.h3
-rw-r--r--lib/fstree/mknode.c27
-rw-r--r--lib/fstree/post_process.c12
-rw-r--r--tests/libfstree/fstree_sort.c89
-rw-r--r--tests/libfstree/mknode_dir.c6
7 files changed, 62 insertions, 137 deletions
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 <goliath@infraroot.at>
- * Copyright (C) 2019 Zachary Dremann <dremann@gmail.com>
- */
-#include "internal.h"
-
-#include <string.h>
-
-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 <stdlib.h>
#include <errno.h>
+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);
generated by cgit v1.2.3 (git 2.39.1) at 2025-11-04 16:16:30 +0000