lib/union_find.c

   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 }