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 */
13struct 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 */
33void 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}