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>

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;