linux-kernel - Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <haimyc4y2trcyvbnkpw2gkfoiaunykb2q2d5ybr6qgt6upf3lm@afhcevtyjcjl>
Date: Wed, 3 Jul 2024 11:40:25 +0200
From: Michal Koutný <mkoutny@...e.com>
To: Xavier <xavier_qy@....com>
Cc: tj@...nel.org, longman@...hat.com, akpm@...ux-foundation.org, 
	lizefan.x@...edance.com, hannes@...xchg.org, cgroups@...r.kernel.org, 
	linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org
Subject: Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel
 library

On Wed, Jul 03, 2024 at 02:37:26PM GMT, Xavier <xavier_qy@....com> 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>
> ---
>  Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
>  .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
>  MAINTAINERS                                   |   9 ++
>  include/linux/union_find.h                    |  41 +++++++
>  lib/Makefile                                  |   2 +-
>  lib/union_find.c                              |  48 +++++++++
>  6 files changed, 288 insertions(+), 1 deletion(-)
>  create mode 100644 Documentation/core-api/union_find.rst
>  create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
>  create mode 100644 include/linux/union_find.h
>  create mode 100644 lib/union_find.c
> 

Nice.
I'd so s/Union-Find/union-find/ both in the docs and the code
(comments), I didn't find any rule why two capitalizations are used.

> +struct uf_node {
> +	struct uf_node *parent;
> +	unsigned int rank;
> +};
> +
> +/* This macro is used for static initialization of a union-find node. */
> +#define UF_INIT_NODE(node)	{.parent = &node, .rank = 0}
> +
> +/**
> + * uf_node_init - Initialize a union-find node
> + * @node: pointer to the union-find node to be initialized
> + *
> + * This function sets the parent of the node to itself and
> + * initializes its rank to 0.
> + */
> +static inline void uf_node_init(struct uf_node *node)
> +{
> +	node->parent = node;
> +	node->rank = 0;
> +}

Xavier, not sure if you responded to my suggestion of considered zeroed
object a valid initialized one. That could save some init work (and
move it to alternative uf_find, see below).

> + * This function returns the root of the node by following the parent
> + * pointers. It also performs path compression, making the tree shallower.
> + *
> + * Returns the root node of the set containing node.
> + */
> +struct uf_node *uf_find(struct uf_node *node)
> +{
> +	struct uf_node *parent;
> +

With uf_find body checking for NULL:

	while (node->parent != node) {
		parent = node->parent;
		node->parent = parent ? parent->parent : node;
		node = node->parent;
	}

> +/**
> + * uf_union - Merge two sets, using union by rank
> + * @node1: the first node
> + * @node2: the second node
> + *
> + * This function merges the sets containing node1 and node2, by comparing
> + * the ranks to keep the tree balanced.
> + */
> +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 == root2)
	return;
then the rest can be one level less nested ;-)

Michal

Download attachment "signature.asc" of type "application/pgp-signature" (229 bytes)