1 // SPDX-License-Identifier: GPL-2.0
2 #include <linux/union_find.h>
3 
4 /**
5  * uf_find - Find the root of a node and perform path compression
6  * @node: the node to find the root of
7  *
8  * This function returns the root of the node by following the parent
9  * pointers. It also performs path compression, making the tree shallower.
10  *
11  * Returns the root node of the set containing node.
12  */
uf_find(struct uf_node * node)13 struct uf_node *uf_find(struct uf_node *node)
14 {
15 	struct uf_node *parent;
16 
17 	while (node->parent != node) {
18 		parent = node->parent;
19 		node->parent = parent->parent;
20 		node = parent;
21 	}
22 	return node;
23 }
24 
25 /**
26  * uf_union - Merge two sets, using union by rank
27  * @node1: the first node
28  * @node2: the second node
29  *
30  * This function merges the sets containing node1 and node2, by comparing
31  * the ranks to keep the tree balanced.
32  */
uf_union(struct uf_node * node1,struct uf_node * node2)33 void uf_union(struct uf_node *node1, struct uf_node *node2)
34 {
35 	struct uf_node *root1 = uf_find(node1);
36 	struct uf_node *root2 = uf_find(node2);
37 
38 	if (root1 == root2)
39 		return;
40 
41 	if (root1->rank < root2->rank) {
42 		root1->parent = root2;
43 	} else if (root1->rank > root2->rank) {
44 		root2->parent = root1;
45 	} else {
46 		root2->parent = root1;
47 		root1->rank++;
48 	}
49 }
50