Optimize the uf_find() function to enhance its efficiency by
implementing a more effective path compression strategy. The original
implementation only updated the parent pointer of the current node to
its grandparent, resulting in a relatively shallow tree.

In the updated version, once the root of the node is identified, all
nodes along the search path are updated to directly point to the root.
This change minimizes the height of the tree and improves the
efficiency for subsequent find operations, providing better performance
for the Union-Find data structure.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Note: Tested with the KUnit tests introduced in the previous patch.

 lib/union_find.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/lib/union_find.c b/lib/union_find.c
index a20678da0220..7c553fa622c8 100644
--- a/lib/union_find.c
+++ b/lib/union_find.c
@@ -13,14 +13,19 @@
  */
 struct uf_node *uf_find(struct uf_node *node)
 {
+	struct uf_node *root = node;
 	struct uf_node *parent;
 
+	while (root->parent != root)
+		root = root->parent;
+
 	while (node->parent != node) {
 		parent = node->parent;
-		node->parent = parent->parent;
+		node->parent = root;
 		node = parent;
 	}
-	return node;
+
+	return root;
 }
 EXPORT_SYMBOL(uf_find);
 
-- 
2.34.1

At 2024-10-06 05:49:37, "Kuan-Wei Chiu" <visitorckw@gmail.com> wrote:
>Optimize the uf_find() function to enhance its efficiency by
>implementing a more effective path compression strategy. The original
>implementation only updated the parent pointer of the current node to
>its grandparent, resulting in a relatively shallow tree.
>
>In the updated version, once the root of the node is identified, all
>nodes along the search path are updated to directly point to the root.
>This change minimizes the height of the tree and improves the
>efficiency for subsequent find operations, providing better performance
>for the Union-Find data structure.
>
>Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
>---
>Note: Tested with the KUnit tests introduced in the previous patch.
>
> lib/union_find.c | 9 +++++++--
> 1 file changed, 7 insertions(+), 2 deletions(-)
>
>diff --git a/lib/union_find.c b/lib/union_find.c
>index a20678da0220..7c553fa622c8 100644
>--- a/lib/union_find.c
>+++ b/lib/union_find.c
>@@ -13,14 +13,19 @@
>  */
> struct uf_node *uf_find(struct uf_node *node)
> {
>+	struct uf_node *root = node;
> 	struct uf_node *parent;
> 
>+	while (root->parent != root)
>+		root = root->parent;
>+
> 	while (node->parent != node) {

Using “root” for this judgment might be better, as it could
reduce unnecessary entering.
        while (node->parent != root) {

> 		parent = node->parent;
>-		node->parent = parent->parent;
>+		node->parent = root;
> 		node = parent;
> 	}
>-	return node;
>+
>+	return root;
> }
> EXPORT_SYMBOL(uf_find);
> 
>-- 
>2.34.1