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 */ 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 */ 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