| 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(node: node1); |
| 36 | struct uf_node *root2 = uf_find(node: 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 |