3 files changed, 114 insertions, 1 deletions

diff --git a/include/common.h b/include/common.h
index bdb3837..9938ba0 100644
--- a/include/common.h
+++ b/include/common.h
@@ -75,6 +75,12 @@ typedef struct {
 	bool quiet;
 } sqfs_writer_cfg_t;
 
+typedef struct sqfs_hard_link_t {
+	struct sqfs_hard_link_t *next;
+	sqfs_u32 inode_number;
+	char *target;
+} sqfs_hard_link_t;
+
 #define container_of(ptr, type, member) \
 	((type *)((char *)ptr - offsetof(type, member)))
 
@@ -132,6 +138,9 @@ void sqfs_writer_cleanup(sqfs_writer_t *sqfs);
 
 void sqfs_perror(const char *file, const char *action, int error_code);
 
+int sqfs_tree_find_hard_links(const sqfs_tree_node_t *root,
+			      sqfs_hard_link_t **out);
+
 /*
   A wrapper around mkdir() that behaves like 'mkdir -p'. It tries to create
   every component of the given path and skips already existing entries.
diff --git a/lib/common/Makemodule.am b/lib/common/Makemodule.am
index 696a169..635c342 100644
--- a/lib/common/Makemodule.am
+++ b/lib/common/Makemodule.am
@@ -1,5 +1,5 @@
 libcommon_a_SOURCES = lib/common/serialize_fstree.c lib/common/statistics.c
-libcommon_a_SOURCES += lib/common/inode_stat.c
+libcommon_a_SOURCES += lib/common/inode_stat.c lib/common/hardlink.c
 libcommon_a_SOURCES += lib/common/print_version.c lib/common/data_reader_dump.c
 libcommon_a_SOURCES += lib/common/compress.c lib/common/comp_opt.c
 libcommon_a_SOURCES += lib/common/data_writer.c include/common.h
diff --git a/lib/common/hardlink.c b/lib/common/hardlink.c
new file mode 100644
index 0000000..c1fca8a
--- /dev/null
+++ b/lib/common/hardlink.c
@@ -0,0 +1,104 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * hardlink.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "common.h"
+
+#include <stdlib.h>
+#include <assert.h>
+#include <stdio.h>
+
+static size_t count_nodes(const sqfs_tree_node_t *n)
+{
+	size_t count = n->children == NULL ? 1 : 0;
+
+	for (n = n->children; n != NULL; n = n->next)
+		count += count_nodes(n);
+
+	return count;
+}
+
+static size_t map_nodes(const sqfs_tree_node_t **list,
+			const sqfs_tree_node_t *n,
+			size_t idx)
+{
+	if (n->children == NULL)
+		list[idx++] = n;
+
+	for (n = n->children; n != NULL; n = n->next)
+		idx = map_nodes(list, n, idx);
+
+	return idx;
+}
+
+int sqfs_tree_find_hard_links(const sqfs_tree_node_t *root,
+			      sqfs_hard_link_t **out)
+{
+	sqfs_hard_link_t *hardlinks = NULL, *lnk = NULL;
+	const sqfs_tree_node_t **list = NULL;
+	size_t i, j, count;
+	const char *name;
+	bool is_dup;
+
+	count = count_nodes(root);
+	list = malloc(sizeof(list[0]) * count);
+	if (list == NULL)
+		goto fail;
+
+	map_nodes(list, root, 0);
+
+	for (i = 0; i < count; ++i) {
+		name = (const char *)list[i]->name;
+		if (!is_filename_sane(name, false))
+			continue;
+
+		is_dup = false;
+
+		for (j = 0; j < i; ++j) {
+			if (list[j]->inode->base.inode_number ==
+			    list[i]->inode->base.inode_number) {
+				name = (const char *)list[j]->name;
+				if (!is_filename_sane(name, false))
+					continue;
+
+				is_dup = true;
+				break;
+			}
+		}
+
+		if (is_dup) {
+			lnk = calloc(1, sizeof(*lnk));
+			if (lnk == NULL)
+				goto fail;
+
+			lnk->inode_number = list[j]->inode->base.inode_number;
+			lnk->target = sqfs_tree_node_get_path(list[j]);
+			if (lnk->target == NULL)
+				goto fail;
+
+			if (canonicalize_name(lnk->target) == 0) {
+				lnk->next = hardlinks;
+				hardlinks = lnk;
+			} else {
+				free(lnk->target);
+				free(lnk);
+			}
+		}
+	}
+
+	*out = hardlinks;
+	return 0;
+fail:
+	perror("detecting hard links in file system tree");
+	free(lnk);
+	while (hardlinks != NULL) {
+		lnk = hardlinks;
+		hardlinks = hardlinks->next;
+		free(lnk->target);
+		free(lnk);
+	}
+	free(list);
+	return -1;
+}