Generate a flat inode table from the fstree ahead of time

Instead of allocating inode numbers as we go, generate and populat an
inode table from the fstree ahead of time. This makes processing nodes
a little bit simpler and we will need that table anyway for NFS export
support later on.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

3 files changed, 69 insertions, 1 deletions

diff --git a/lib/Makemodule.am b/lib/Makemodule.am
index 0120347..536cad0 100644
--- a/lib/Makemodule.am
+++ b/lib/Makemodule.am
@@ -1,6 +1,6 @@
 libfstree_a_SOURCES = lib/fstree/fstree.c lib/fstree/fstree_from_file.c
 libfstree_a_SOURCES += lib/fstree/fstree_sort.c lib/fstree/fstree_from_dir.c
-libfstree_a_SOURCES += include/fstree.h
+libfstree_a_SOURCES += lib/fstree/gen_inode_table.c include/fstree.h
 libfstree_a_CFLAGS = $(AM_CFLAGS)
 libfstree_a_CPPFLAGS = $(AM_CPPFLAGS)
 
diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c
index 0c3f13d..56ca528 100644
--- a/lib/fstree/fstree.c
+++ b/lib/fstree/fstree.c
@@ -352,5 +352,6 @@ void fstree_cleanup(fstree_t *fs)
 	str_table_cleanup(&fs->xattr_keys);
 	str_table_cleanup(&fs->xattr_values);
 	free_recursive(fs->root);
+	free(fs->inode_table);
 	memset(fs, 0, sizeof(*fs));
 }
diff --git a/lib/fstree/gen_inode_table.c b/lib/fstree/gen_inode_table.c
new file mode 100644
index 0000000..2782c6d
--- /dev/null
+++ b/lib/fstree/gen_inode_table.c
@@ -0,0 +1,67 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "fstree.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+static size_t count_nodes(tree_node_t *root)
+{
+	tree_node_t *n = root->data.dir->children;
+	size_t count = 1;
+
+	while (n != NULL) {
+		if (S_ISDIR(n->mode)) {
+			count += count_nodes(n);
+		} else {
+			++count;
+		}
+		n = n->next;
+	}
+
+	return count;
+}
+
+static void map_child_nodes(fstree_t *fs, tree_node_t *root, size_t *counter)
+{
+	bool has_subdirs = false;
+	tree_node_t *it;
+
+	for (it = root->data.dir->children; it != NULL; it = it->next) {
+		if (S_ISDIR(it->mode)) {
+			has_subdirs = true;
+			break;
+		}
+	}
+
+	if (has_subdirs) {
+		for (it = root->data.dir->children; it != NULL; it = it->next) {
+			if (S_ISDIR(it->mode))
+				map_child_nodes(fs, it, counter);
+		}
+	}
+
+	for (it = root->data.dir->children; it != NULL; it = it->next) {
+		it->inode_num = *counter;
+		*counter += 1;
+
+		fs->inode_table[it->inode_num] = it;
+	}
+}
+
+int fstree_gen_inode_table(fstree_t *fs)
+{
+	size_t inum = 2;
+
+	fs->inode_tbl_size = count_nodes(fs->root) + 2;
+	fs->inode_table = calloc(sizeof(tree_node_t *), fs->inode_tbl_size);
+
+	if (fs->inode_table == NULL) {
+		perror("allocating inode table");
+		return -1;
+	}
+
+	map_child_nodes(fs, fs->root, &inum);
+	fs->root->inode_num = inum;
+	fs->inode_table[inum] = fs->root;
+	return 0;
+}