50 lines · c
1// SPDX-License-Identifier: GPL-2.02#include <linux/union_find.h>3 4/**5 * uf_find - Find the root of a node and perform path compression6 * @node: the node to find the root of7 *8 * This function returns the root of the node by following the parent9 * 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 rank27 * @node1: the first node28 * @node2: the second node29 *30 * This function merges the sets containing node1 and node2, by comparing31 * 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}50