clustering::AtomicUnionFind< Idx > Class Template Reference

Lock-free disjoint-set-union for concurrent edge folding. More...

#include <clustering/math/dsu.h>

Public Member Functions
	AtomicUnionFind (std::size_t n)
	Construct n singleton components numbered [0, n).
Idx	find (Idx x) noexcept
	Root of the component containing x at some point during the call.
bool	unite (Idx a, Idx b) noexcept
	Merge the components containing a and b; larger root links under smaller.
std::size_t	size () const noexcept
	Total number of elements under management (fixed at construction).

Detailed Description

template<class Idx = std::uint32_t>
class clustering::AtomicUnionFind< Idx >

Lock-free disjoint-set-union for concurrent edge folding.

Threads call unite concurrently with no external locking: a root is linked under another only through a compare-and-swap on its own parent slot, which can succeed only while it is still a root, so merges linearize. find applies path halving whose racing writes are benign – parent pointers only ever move toward a root.

Links are ordered by index: the larger root always attaches under the smaller, so once every unite has completed (and the callers have synchronized), the root of each component is exactly its minimum member. Flattened roots are therefore reproducible across runs regardless of thread interleaving.

Template Parameters

Idx	Unsigned integer index type; defaults to uint32_t.

Definition at line 162 of file dsu.h.

Constructor & Destructor Documentation

AtomicUnionFind()

template<class Idx = std::uint32_t>

clustering::AtomicUnionFind< Idx >::AtomicUnionFind ( std::size_t n )

inlineexplicit

Construct n singleton components numbered [0, n).

Definition at line 167 of file dsu.h.

Member Function Documentation

find()

template<class Idx = std::uint32_t>

Idx clustering::AtomicUnionFind< Idx >::find ( Idx x )

inlinenoexcept

Root of the component containing x at some point during the call.

Safe to run concurrently with unite; a concurrent merge may retarget the returned root, so quiescent callers (after a join) read the final component root while racing callers read a then-current one.

Parameters

x	Element index; must satisfy x < size().

Returns

Root index of x's component.

Definition at line 183 of file dsu.h.

size()

template<class Idx = std::uint32_t>

std::size_t clustering::AtomicUnionFind< Idx >::size ( ) const

inlinenodiscardnoexcept

Total number of elements under management (fixed at construction).

Definition at line 231 of file dsu.h.

unite()

template<class Idx = std::uint32_t>

bool clustering::AtomicUnionFind< Idx >::unite ( Idx a, Idx b )

inlinenoexcept

Merge the components containing a and b; larger root links under smaller.

Returns

true if the call merged two distinct components, false if they were already joined when observed.

Definition at line 209 of file dsu.h.

---

The documentation for this class was generated from the following file:

• include/clustering/math/dsu.h