[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <b511173c-53fe-4a93-8030-d99ed1b65bd6@redhat.com>
Date: Thu, 20 Jun 2024 10:54:46 -0400
From: Waiman Long <longman@...hat.com>
To: Xavier <xavier_qy@....com>, mkoutny@...e.com
Cc: lizefan.x@...edance.com, tj@...nel.org, hannes@...xchg.org,
cgroups@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v4 v4 1/2] Union-Find: add a new module in kernel library
On 6/20/24 04:52, Xavier wrote:
> 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>
I would suggest that you briefly document what is a union-find algorithm
and data structure and what is it good for.
Cheers,
Longman
> +
> +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++;
> + }
> + }
> +}
Powered by blists - more mailing lists