On Wed, Jul 03, 2024 at 02:37:26PM GMT, Xavier <xavier_qy@xxxxxxx> 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@xxxxxxx>
> ---
> 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
Attachment:
signature.asc
Description: PGP signature
