[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <20240620085233.205690-2-xavier_qy@163.com>
Date: Thu, 20 Jun 2024 16:52:32 +0800
From: Xavier <xavier_qy@....com>
To: longman@...hat.com,
mkoutny@...e.com
Cc: lizefan.x@...edance.com,
tj@...nel.org,
hannes@...xchg.org,
cgroups@...r.kernel.org,
linux-kernel@...r.kernel.org,
Xavier <xavier_qy@....com>
Subject: [PATCH v4 v4 1/2] Union-Find: add a new module in kernel library
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@....com>
---
MAINTAINERS | 7 +++++++
include/linux/union_find.h | 30 ++++++++++++++++++++++++++++++
lib/Makefile | 2 +-
lib/union_find.c | 38 ++++++++++++++++++++++++++++++++++++++
4 files changed, 76 insertions(+), 1 deletion(-)
create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c
diff --git a/MAINTAINERS b/MAINTAINERS
index d6c90161c7..602d8c6f42 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23054,6 +23054,13 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@....com>
+L: linux-kernel@...r.kernel.org
+S: Maintained
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@...sung.com>
R: Avri Altman <avri.altman@....com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..67e9f62bb3
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+#include <linux/slab.h>
+
+/* Define a union-find node struct */
+struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+};
+
+/* Allocate nodes and initialize to 0 */
+static inline struct uf_node *uf_nodes_alloc(unsigned int node_num)
+{
+ return kzalloc(sizeof(struct uf_node) * node_num, GFP_KERNEL);
+}
+
+/* Free nodes*/
+static inline void uf_nodes_free(struct uf_node *nodes)
+{
+ kfree(nodes);
+}
+
+/* find the root of a node*/
+struct uf_node *uf_find(struct uf_node *node);
+
+/* Merge two intersecting nodes */
+void uf_union(struct uf_node *node1, struct uf_node *node2);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..2f77bae1ca
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+ struct uf_node *parent;
+
+ if (!node->parent) {
+ node->parent = node;
+ return node;
+ }
+
+ /*Find the root node and perform path compression at the same time*/
+ while (node->parent != node) {
+ parent = node->parent;
+ node->parent = parent->parent;
+ node = parent;
+ }
+ return node;
+}
+
+/*Function to merge two sets, using union by rank*/
+void uf_union(struct uf_node *node1, struct uf_node *node2)
+{
+ struct uf_node *root1 = uf_find(node1);
+ struct uf_node *root2 = uf_find(node2);
+
+ if (root1 != root2) {
+ if (root1->rank < root2->rank) {
+ root1->parent = root2;
+ } else if (root1->rank > root2->rank) {
+ root2->parent = root1;
+ } else {
+ root2->parent = root1;
+ root1->rank++;
+ }
+ }
+}
--
2.45.2
Powered by blists - more mailing lists