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