summaryrefslogtreecommitdiff
path: root/lib/fstree
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-10-16 21:50:40 +0200
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2022-03-30 22:31:30 +0200
commite5fa9d585ed090602bcc045689046702199def86 (patch)
tree2b391a68d67972686db86f5d44a90a416695c058 /lib/fstree
parent5e54880a2db2aeb7a6c301a69ee2bef9a09a237f (diff)
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 <david.oberhollenzer@sigma-star.at>
Diffstat (limited to 'lib/fstree')
-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
5 files changed, 22 insertions, 82 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;