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@xxxxxxxxx>
---
Note: Tested with the KUnit tests introduced in the previous patch.
lib/union_find.c | 11 ++++++++---
1 file changed, 8 insertions(+), 3 deletions(-)
diff --git a/lib/union_find.c b/lib/union_find.c
index a20678da0220..d2b79065cbc8 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 (node->parent != node) {
+ while (root->parent != root)
+ root = root->parent;
+
+ 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
