From nobody Wed Dec 17 14:13:36 2025 Received: from m16.mail.163.com (m16.mail.163.com [117.135.210.2]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 81DEC1A01D4; Thu, 4 Jul 2024 06:28:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=117.135.210.2 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720074497; cv=none; b=NFKdFZAP+PjWGKQg4QhDk9tT+Vj6YjMV+V3PBDW6zkuvNfJZdPSVEA2ldD7R3lrYfldj4mzrvH5ih21hpPduh+X0ZEmFhKYsQEyeltIkXx2aVEpqS4VPRyWqMzT1KiVE4fcCDrnDL0El+ZgUq4pB7447qAiBymZsVBzkKLERjG8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720074497; c=relaxed/simple; bh=kplW0kimTIit4XDwDpITKPd1EYrOar/Bpo6fErrWpKU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version:Content-Type; b=rGlshb3cNdH5EiC5xe+EAt/XDriGAhciXnOZIOjWqXbYLRyuJlhIpBO9ZTQLhe69lW53HfHr0djS8azOpifH8nWWNtmu3BwdtLNOIWnoYN8u7+GJB3z+Hz8jG2SqkX2Sk25TcIhM/ru40ijUg/o/gF0PmeTNfjjHD+Ha1a69Qcs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com; spf=pass smtp.mailfrom=163.com; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b=TvHWcV/I; arc=none smtp.client-ip=117.135.210.2 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=163.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b="TvHWcV/I" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version: Content-Type; bh=xgOy7J8lGlrACKI0I+9kb/kJr8SxxiYg7g94kmyQ0wI=; b=TvHWcV/IgpgQJA6KiS0QMaO2pVPoj2Sa/NehMVFR4IbJVxJHF3Fbk5MdIGKVxS wsBXv8Cq5v+pfdSxJrBlNM26H9tFJlwz92hXRN3mxZQE5K2igKdEydKW5PG0y3z2 n315dojR/2FtjOi2LC/Ej8vnGpUo0hf3ybdStjmDS3fqs= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g2-3 (Coremail) with SMTP id _____wD334IvQIZmF8xjBQ--.53023S2; Thu, 04 Jul 2024 14:24:47 +0800 (CST) From: Xavier To: tj@kernel.org, longman@redhat.com, mkoutny@suse.com Cc: akpm@linux-foundation.org, lizefan.x@bytedance.com, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org, Xavier Subject: [PATCH-cpuset v11 1/2] Union-Find: add a new module in kernel library Date: Thu, 4 Jul 2024 14:24:43 +0800 Message-Id: <20240704062444.262211-2-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240704062444.262211-1-xavier_qy@163.com> References: <20240704062444.262211-1-xavier_qy@163.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-CM-TRANSID: _____wD334IvQIZmF8xjBQ--.53023S2 X-Coremail-Antispam: 1Uf129KBjvJXoWfJw48ur4DKr1xJw1kKw48Zwb_yoWkuF48pF sxG34fZw4DJryUC340krW5Zw4SvayrGrWUGa1xJa10yrsayr10qF4jyw1rtr95GryIkFy8 XF4aqw1rZw1jy3DanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07Ur5rsUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/xtbBchMSEGWXwA24JwAAsD This patch implements a union-find data structure in the kernel library, which includes operations for allocating nodes, freeing nodes, finding the root of a node, and merging two nodes. Signed-off-by: Xavier --- Documentation/core-api/union_find.rst | 102 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 +++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 41 +++++++ lib/Makefile | 2 +- lib/union_find.c | 49 +++++++++ 6 files changed, 289 insertions(+), 1 deletion(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api= /union_find.rst new file mode 100644 index 0000000000..2bf0290c91 --- /dev/null +++ b/Documentation/core-api/union_find.rst @@ -0,0 +1,102 @@ +.. SPDX-License-Identifier: GPL-2.0 + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +Union-Find in Linux +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + + +:Date: June 21, 2024 +:Author: Xavier + +What is union-find, and what is it used for? +------------------------------------------------ + +Union-find is a data structure used to handle the merging and querying +of disjoint sets. The primary operations supported by union-find are: + + Initialization: Resetting each element as an individual set, with + each set's initial parent node pointing to itself. + Find: Determine which set a particular element belongs to, usually by + returning a =E2=80=9Crepresentative element=E2=80=9D of that set. This o= peration + is used to check if two elements are in the same set. + Union: Merge two sets into one. + +As a data structure used to maintain sets (groups), union-find is commonly +utilized to solve problems related to offline queries, dynamic connectivit= y, +and graph theory. It is also a key component in Kruskal's algorithm for +computing the minimum spanning tree, which is crucial in scenarios like +network routing. Consequently, union-find is widely referenced. Additional= ly, +union-find has applications in symbolic computation, register allocation, +and more. + +Space Complexity: O(n), where n is the number of nodes. + +Time Complexity: Using path compression can reduce the time complexity of +the find operation, and using union by rank can reduce the time complexity +of the union operation. These optimizations reduce the average time +complexity of each find and union operation to O(=CE=B1(n)), where =CE=B1(= n) is the +inverse Ackermann function. This can be roughly considered a constant time +complexity for practical purposes. + +This document covers use of the Linux union-find implementation. For more +information on the nature and implementation of union-find, see: + + Wikipedia entry on union-find + https://en.wikipedia.org/wiki/Disjoint-set_data_structure + +Linux implementation of union-find +----------------------------------- + +Linux's union-find implementation resides in the file "lib/union_find.c". +To use it, "#include ". + +The union-find data structure is defined as follows:: + + struct uf_node { + struct uf_node *parent; + unsigned int rank; + }; + +In this structure, parent points to the parent node of the current node. +The rank field represents the height of the current tree. During a union +operation, the tree with the smaller rank is attached under the tree with = the +larger rank to maintain balance. + +Initializing union-find +-------------------- + +You can complete the initialization using either static or initialization +interface. Initialize the parent pointer to point to itself and set the ra= nk +to 0. +Example:: + + struct uf_node my_node =3D UF_INIT_NODE(my_node); +or + uf_node_init(&my_node); + +Find the Root Node of union-find +-------------------------------- + +This operation is mainly used to determine whether two nodes belong to the= same +set in the union-find. If they have the same root, they are in the same se= t. +During the find operation, path compression is performed to improve the +efficiency of subsequent find operations. +Example:: + + int connected; + struct uf_node *root1 =3D uf_find(&node_1); + struct uf_node *root2 =3D uf_find(&node_2); + if (root1 =3D=3D root2) + connected =3D 1; + else + connected =3D 0; + +Union Two Sets in union-find +---------------------------- + +To union two sets in the union-find, you first find their respective root = nodes +and then link the smaller node to the larger node based on the rank of the= root +nodes. +Example:: + + uf_union(&node_1, &node_2); diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Doc= umentation/translations/zh_CN/core-api/union_find.rst new file mode 100644 index 0000000000..a56de57147 --- /dev/null +++ b/Documentation/translations/zh_CN/core-api/union_find.rst @@ -0,0 +1,87 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/core-api/union_find.rst + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D +Linux=E4=B8=AD=E7=9A=84=E5=B9=B6=E6=9F=A5=E9=9B=86=EF=BC=88Union-Find=EF= =BC=89 +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D + + +:=E6=97=A5=E6=9C=9F: 2024=E5=B9=B46=E6=9C=8821=E6=97=A5 +:=E4=BD=9C=E8=80=85: Xavier + +=E4=BD=95=E4=B8=BA=E5=B9=B6=E6=9F=A5=E9=9B=86=EF=BC=8C=E5=AE=83=E6=9C=89= =E4=BB=80=E4=B9=88=E7=94=A8=EF=BC=9F +--------------------- + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=98=AF=E4=B8=80=E7=A7=8D=E6=95=B0=E6=8D=AE= =E7=BB=93=E6=9E=84=EF=BC=8C=E7=94=A8=E4=BA=8E=E5=A4=84=E7=90=86=E4=B8=80=E4= =BA=9B=E4=B8=8D=E4=BA=A4=E9=9B=86=E7=9A=84=E5=90=88=E5=B9=B6=E5=8F=8A=E6=9F= =A5=E8=AF=A2=E9=97=AE=E9=A2=98=E3=80=82=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=94=AF= =E6=8C=81=E7=9A=84=E4=B8=BB=E8=A6=81=E6=93=8D=E4=BD=9C=EF=BC=9A + =E5=88=9D=E5=A7=8B=E5=8C=96=EF=BC=9A=E5=B0=86=E6=AF=8F=E4=B8=AA=E5=85=83= =E7=B4=A0=E5=88=9D=E5=A7=8B=E5=8C=96=E4=B8=BA=E5=8D=95=E7=8B=AC=E7=9A=84=E9= =9B=86=E5=90=88=EF=BC=8C=E6=AF=8F=E4=B8=AA=E9=9B=86=E5=90=88=E7=9A=84=E5=88= =9D=E5=A7=8B=E7=88=B6=E8=8A=82=E7=82=B9=E6=8C=87=E5=90=91=E8=87=AA=E8=BA=AB + =E6=9F=A5=E8=AF=A2=EF=BC=9A=E6=9F=A5=E8=AF=A2=E6=9F=90=E4=B8=AA=E5=85=83= =E7=B4=A0=E5=B1=9E=E4=BA=8E=E5=93=AA=E4=B8=AA=E9=9B=86=E5=90=88=EF=BC=8C=E9= =80=9A=E5=B8=B8=E6=98=AF=E8=BF=94=E5=9B=9E=E9=9B=86=E5=90=88=E4=B8=AD=E7=9A= =84=E4=B8=80=E4=B8=AA=E2=80=9C=E4=BB=A3=E8=A1=A8=E5=85=83=E7=B4=A0=E2=80=9D= =E3=80=82=E8=BF=99=E4=B8=AA=E6=93=8D=E4=BD=9C=E6=98=AF=E4=B8=BA + =E4=BA=86=E5=88=A4=E6=96=AD=E4=B8=A4=E4=B8=AA=E5=85=83=E7=B4=A0=E6=98=AF= =E5=90=A6=E5=9C=A8=E5=90=8C=E4=B8=80=E4=B8=AA=E9=9B=86=E5=90=88=E4=B9=8B=E4= =B8=AD=E3=80=82 + =E5=90=88=E5=B9=B6=EF=BC=9A=E5=B0=86=E4=B8=A4=E4=B8=AA=E9=9B=86=E5=90=88= =E5=90=88=E5=B9=B6=E4=B8=BA=E4=B8=80=E4=B8=AA=E3=80=82 + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E4=BD=9C=E4=B8=BA=E4=B8=80=E7=A7=8D=E7=94=A8= =E4=BA=8E=E7=BB=B4=E6=8A=A4=E9=9B=86=E5=90=88=EF=BC=88=E7=BB=84=EF=BC=89=E7= =9A=84=E6=95=B0=E6=8D=AE=E7=BB=93=E6=9E=84=EF=BC=8C=E5=AE=83=E9=80=9A=E5=B8= =B8=E7=94=A8=E4=BA=8E=E8=A7=A3=E5=86=B3=E4=B8=80=E4=BA=9B=E7=A6=BB=E7=BA=BF= =E6=9F=A5=E8=AF=A2=E3=80=81=E5=8A=A8=E6=80=81=E8=BF=9E=E9=80=9A=E6=80=A7=E5= =92=8C +=E5=9B=BE=E8=AE=BA=E7=AD=89=E7=9B=B8=E5=85=B3=E9=97=AE=E9=A2=98=EF=BC=8C= =E5=90=8C=E6=97=B6=E4=B9=9F=E6=98=AF=E7=94=A8=E4=BA=8E=E8=AE=A1=E7=AE=97=E6= =9C=80=E5=B0=8F=E7=94=9F=E6=88=90=E6=A0=91=E7=9A=84=E5=85=8B=E9=B2=81=E6=96= =AF=E5=85=8B=E5=B0=94=E7=AE=97=E6=B3=95=E4=B8=AD=E7=9A=84=E5=85=B3=E9=94=AE= =EF=BC=8C=E7=94=B1=E4=BA=8E=E6=9C=80=E5=B0=8F=E7=94=9F=E6=88=90=E6=A0=91=E5= =9C=A8 +=E7=BD=91=E7=BB=9C=E8=B7=AF=E7=94=B1=E7=AD=89=E5=9C=BA=E6=99=AF=E4=B8=8B= =E5=8D=81=E5=88=86=E9=87=8D=E8=A6=81=EF=BC=8C=E5=B9=B6=E6=9F=A5=E9=9B=86=E4= =B9=9F=E5=BE=97=E5=88=B0=E4=BA=86=E5=B9=BF=E6=B3=9B=E7=9A=84=E5=BC=95=E7=94= =A8=E3=80=82=E6=AD=A4=E5=A4=96=EF=BC=8C=E5=B9=B6=E6=9F=A5=E9=9B=86=E5=9C=A8= =E7=AC=A6=E5=8F=B7=E8=AE=A1=E7=AE=97=EF=BC=8C=E5=AF=84=E5=AD=98=E5=99=A8=E5= =88=86 +=E9=85=8D=E7=AD=89=E6=96=B9=E9=9D=A2=E4=B9=9F=E6=9C=89=E5=BA=94=E7=94=A8= =E3=80=82 + +=E7=A9=BA=E9=97=B4=E5=A4=8D=E6=9D=82=E5=BA=A6: O(n)=EF=BC=8Cn=E4=B8=BA=E8= =8A=82=E7=82=B9=E6=95=B0=E3=80=82 + +=E6=97=B6=E9=97=B4=E5=A4=8D=E6=9D=82=E5=BA=A6=EF=BC=9A=E4=BD=BF=E7=94=A8= =E8=B7=AF=E5=BE=84=E5=8E=8B=E7=BC=A9=E5=8F=AF=E4=BB=A5=E5=87=8F=E5=B0=91=E6= =9F=A5=E6=89=BE=E6=93=8D=E4=BD=9C=E7=9A=84=E6=97=B6=E9=97=B4=E5=A4=8D=E6=9D= =82=E5=BA=A6=EF=BC=8C=E4=BD=BF=E7=94=A8=E6=8C=89=E7=A7=A9=E5=90=88=E5=B9=B6= =E5=8F=AF=E4=BB=A5=E5=87=8F=E5=B0=91=E5=90=88=E5=B9=B6=E6=93=8D=E4=BD=9C=E7= =9A=84 +=E6=97=B6=E9=97=B4=E5=A4=8D=E6=9D=82=E5=BA=A6=EF=BC=8C=E4=BD=BF=E5=BE=97= =E5=B9=B6=E6=9F=A5=E9=9B=86=E6=AF=8F=E4=B8=AA=E6=9F=A5=E8=AF=A2=E5=92=8C=E5= =90=88=E5=B9=B6=E6=93=8D=E4=BD=9C=E7=9A=84=E5=B9=B3=E5=9D=87=E6=97=B6=E9=97= =B4=E5=A4=8D=E6=9D=82=E5=BA=A6=E4=BB=85=E4=B8=BAO(=CE=B1(n))=EF=BC=8C=E5=85= =B6=E4=B8=AD=CE=B1(n)=E6=98=AF=E5=8F=8D=E9=98=BF +=E5=85=8B=E6=9B=BC=E5=87=BD=E6=95=B0=EF=BC=8C=E5=8F=AF=E4=BB=A5=E7=B2=97= =E7=95=A5=E5=9C=B0=E8=AE=A4=E4=B8=BA=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E6= =93=8D=E4=BD=9C=E6=9C=89=E5=B8=B8=E6=95=B0=E7=9A=84=E6=97=B6=E9=97=B4=E5=A4= =8D=E6=9D=82=E5=BA=A6=E3=80=82 + +=E6=9C=AC=E6=96=87=E6=A1=A3=E6=B6=B5=E7=9B=96=E4=BA=86=E5=AF=B9Linux=E5=B9= =B6=E6=9F=A5=E9=9B=86=E5=AE=9E=E7=8E=B0=E7=9A=84=E4=BD=BF=E7=94=A8=E6=96=B9= =E6=B3=95=E3=80=82=E6=9B=B4=E5=A4=9A=E5=85=B3=E4=BA=8E=E5=B9=B6=E6=9F=A5=E9= =9B=86=E7=9A=84=E6=80=A7=E8=B4=A8=E5=92=8C=E5=AE=9E=E7=8E=B0=E7=9A=84=E4=BF= =A1=E6=81=AF=EF=BC=8C=E5=8F=82=E8=A7=81=EF=BC=9A + + =E7=BB=B4=E5=9F=BA=E7=99=BE=E7=A7=91=E5=B9=B6=E6=9F=A5=E9=9B=86=E8=AF=8D= =E6=9D=A1 + https://en.wikipedia.org/wiki/Disjoint-set_data_structure + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84Linux=E5=AE=9E=E7=8E=B0 +---------------- + +Linux=E7=9A=84=E5=B9=B6=E6=9F=A5=E9=9B=86=E5=AE=9E=E7=8E=B0=E5=9C=A8=E6=96= =87=E4=BB=B6=E2=80=9Clib/union_find.c=E2=80=9D=E4=B8=AD=E3=80=82=E8=A6=81= =E4=BD=BF=E7=94=A8=E5=AE=83=EF=BC=8C=E9=9C=80=E8=A6=81 +=E2=80=9C#include =E2=80=9D=E3=80=82 + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E6=95=B0=E6=8D=AE=E7=BB=93=E6=9E=84= =E5=AE=9A=E4=B9=89=E5=A6=82=E4=B8=8B:: + + struct uf_node { + struct uf_node *parent; + unsigned int rank; + }; +=E5=85=B6=E4=B8=ADparent=E4=B8=BA=E5=BD=93=E5=89=8D=E8=8A=82=E7=82=B9=E7= =9A=84=E7=88=B6=E8=8A=82=E7=82=B9=EF=BC=8Crank=E4=B8=BA=E5=BD=93=E5=89=8D= =E6=A0=91=E7=9A=84=E9=AB=98=E5=BA=A6=EF=BC=8C=E5=9C=A8=E5=90=88=E5=B9=B6=E6= =97=B6=E5=B0=86rank=E5=B0=8F=E7=9A=84=E8=8A=82=E7=82=B9=E6=8E=A5=E5=88=B0ra= nk=E5=A4=A7 +=E7=9A=84=E8=8A=82=E7=82=B9=E4=B8=8B=E9=9D=A2=E4=BB=A5=E5=A2=9E=E5=8A=A0= =E5=B9=B3=E8=A1=A1=E6=80=A7=E3=80=82 + +=E5=88=9D=E5=A7=8B=E5=8C=96=E5=B9=B6=E6=9F=A5=E9=9B=86 +--------- + +=E5=8F=AF=E4=BB=A5=E9=87=87=E7=94=A8=E9=9D=99=E6=80=81=E6=88=96=E5=88=9D= =E5=A7=8B=E5=8C=96=E6=8E=A5=E5=8F=A3=E5=AE=8C=E6=88=90=E5=88=9D=E5=A7=8B=E5= =8C=96=E6=93=8D=E4=BD=9C=E3=80=82=E5=88=9D=E5=A7=8B=E5=8C=96=E6=97=B6=EF=BC= =8Cparent =E6=8C=87=E9=92=88=E6=8C=87=E5=90=91=E8=87=AA=E8=BA=AB=EF=BC=8Cra= nk =E8=AE=BE=E7=BD=AE +=E4=B8=BA 0=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + + struct uf_node my_node =3D UF_INIT_NODE(my_node); +=E6=88=96 + uf_node_init(&my_node); + +=E6=9F=A5=E6=89=BE=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E6=A0=B9=E8=8A=82= =E7=82=B9 +---------------- + +=E4=B8=BB=E8=A6=81=E7=94=A8=E4=BA=8E=E5=88=A4=E6=96=AD=E4=B8=A4=E4=B8=AA= =E5=B9=B6=E6=9F=A5=E9=9B=86=E6=98=AF=E5=90=A6=E5=B1=9E=E4=BA=8E=E4=B8=80=E4= =B8=AA=E9=9B=86=E5=90=88=EF=BC=8C=E5=A6=82=E6=9E=9C=E6=A0=B9=E7=9B=B8=E5=90= =8C=EF=BC=8C=E9=82=A3=E4=B9=88=E4=BB=96=E4=BB=AC=E5=B0=B1=E6=98=AF=E4=B8=80= =E4=B8=AA=E9=9B=86=E5=90=88=E3=80=82=E5=9C=A8=E6=9F=A5=E6=89=BE=E8=BF=87=E7= =A8=8B=E4=B8=AD +=E4=BC=9A=E5=AF=B9=E8=B7=AF=E5=BE=84=E8=BF=9B=E8=A1=8C=E5=8E=8B=E7=BC=A9= =EF=BC=8C=E6=8F=90=E9=AB=98=E5=90=8E=E7=BB=AD=E6=9F=A5=E6=89=BE=E6=95=88=E7= =8E=87=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + + int connected; + struct uf_node *root1 =3D uf_find(&node_1); + struct uf_node *root2 =3D uf_find(&node_2); + if (root1 =3D=3D root2) + connected =3D 1; + else + connected =3D 0; + +=E5=90=88=E5=B9=B6=E4=B8=A4=E4=B8=AA=E5=B9=B6=E6=9F=A5=E9=9B=86 +------------- + +=E5=AF=B9=E4=BA=8E=E4=B8=A4=E4=B8=AA=E7=9B=B8=E4=BA=A4=E7=9A=84=E5=B9=B6= =E6=9F=A5=E9=9B=86=E8=BF=9B=E8=A1=8C=E5=90=88=E5=B9=B6=EF=BC=8C=E4=BC=9A=E9= =A6=96=E5=85=88=E6=9F=A5=E6=89=BE=E5=AE=83=E4=BB=AC=E5=90=84=E8=87=AA=E7=9A= =84=E6=A0=B9=E8=8A=82=E7=82=B9=EF=BC=8C=E7=84=B6=E5=90=8E=E6=A0=B9=E6=8D=AE= =E6=A0=B9=E8=8A=82=E7=82=B9=E7=A7=A9=E5=A4=A7=E5=B0=8F=EF=BC=8C=E5=B0=86=E5= =B0=8F=E7=9A=84 +=E8=8A=82=E7=82=B9=E8=BF=9E=E6=8E=A5=E5=88=B0=E5=A4=A7=E7=9A=84=E8=8A=82= =E7=82=B9=E4=B8=8B=E9=9D=A2=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + + uf_union(&node_1, &node_2); diff --git a/MAINTAINERS b/MAINTAINERS index 2ca8f35dfe..16171dbca3 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -23051,6 +23051,15 @@ F: drivers/cdrom/cdrom.c F: include/linux/cdrom.h F: include/uapi/linux/cdrom.h =20 +UNION-FIND +M: Xavier +L: linux-kernel@vger.kernel.org +S: Maintained +F: Documentation/core-api/union_find.rst +F: Documentation/translations/zh_CN/core-api/union_find.rst +F: include/linux/union_find.h +F: lib/union_find.c + UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER R: Alim Akhtar R: Avri Altman diff --git a/include/linux/union_find.h b/include/linux/union_find.h new file mode 100644 index 0000000000..cfd49263c1 --- /dev/null +++ b/include/linux/union_find.h @@ -0,0 +1,41 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_UNION_FIND_H +#define __LINUX_UNION_FIND_H +/** + * union_find.h - union-find data structure implementation + * + * This header provides functions and structures to implement the union-fi= nd + * data structure. The union-find data structure is used to manage disjoint + * sets and supports efficient union and find operations. + * + * See Documentation/core-api/union_find.rst for documentation and samples. + */ + +struct uf_node { + struct uf_node *parent; + unsigned int rank; +}; + +/* This macro is used for static initialization of a union-find node. */ +#define UF_INIT_NODE(node) {.parent =3D &node, .rank =3D 0} + +/** + * uf_node_init - Initialize a union-find node + * @node: pointer to the union-find node to be initialized + * + * This function sets the parent of the node to itself and + * initializes its rank to 0. + */ +static inline void uf_node_init(struct uf_node *node) +{ + node->parent =3D node; + node->rank =3D 0; +} + +/* find the root of a node */ +struct uf_node *uf_find(struct uf_node *node); + +/* Merge two intersecting nodes */ +void uf_union(struct uf_node *node1, struct uf_node *node2); + +#endif /* __LINUX_UNION_FIND_H */ diff --git a/lib/Makefile b/lib/Makefile index 3b17690456..e1769e6f03 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -34,7 +34,7 @@ lib-y :=3D ctype.o string.o vsprintf.o cmdline.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ nmi_backtrace.o win_minmax.o memcat_p.o \ - buildid.o objpool.o + buildid.o objpool.o union_find.o =20 lib-$(CONFIG_PRINTK) +=3D dump_stack.o lib-$(CONFIG_SMP) +=3D cpumask.o diff --git a/lib/union_find.c b/lib/union_find.c new file mode 100644 index 0000000000..413b0f8adf --- /dev/null +++ b/lib/union_find.c @@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-2.0 +#include + +/** + * uf_find - Find the root of a node and perform path compression + * @node: the node to find the root of + * + * This function returns the root of the node by following the parent + * pointers. It also performs path compression, making the tree shallower. + * + * Returns the root node of the set containing node. + */ +struct uf_node *uf_find(struct uf_node *node) +{ + struct uf_node *parent; + + while (node->parent !=3D node) { + parent =3D node->parent; + node->parent =3D parent->parent; + node =3D parent; + } + return node; +} + +/** + * uf_union - Merge two sets, using union by rank + * @node1: the first node + * @node2: the second node + * + * This function merges the sets containing node1 and node2, by comparing + * the ranks to keep the tree balanced. + */ +void uf_union(struct uf_node *node1, struct uf_node *node2) +{ + struct uf_node *root1 =3D uf_find(node1); + struct uf_node *root2 =3D uf_find(node2); + + if (root1 =3D=3D root2) + return; + + if (root1->rank < root2->rank) { + root1->parent =3D root2; + } else if (root1->rank > root2->rank) { + root2->parent =3D root1; + } else { + root2->parent =3D root1; + root1->rank++; + } +} --=20 2.45.0