blender::AtomicDisjointSet Class Reference

#include <BLI_atomic_disjoint_set.hh>

Public Member Functions
	AtomicDisjointSet (const int size)
void	join (int x, int y)
bool	in_same_set (int x, int y) const
int	find_root (int x) const
bool	is_root (const int x) const
int	calc_reduced_ids (MutableSpan< int > result) const
int	count_sets () const

Detailed Description

Same as DisjointSet but is thread safe (at slightly higher cost for the single threaded case).

The implementation is based on the following paper: "Wait-free Parallel Algorithms for the Union-Find Problem" by Richard J. Anderson and Heather Woll.

It's also inspired by this implementation: https://github.com/wjakob/dset.

Definition at line 26 of file BLI_atomic_disjoint_set.hh.

Constructor & Destructor Documentation

AtomicDisjointSet()

blender::AtomicDisjointSet::AtomicDisjointSet

(

const int

size

)

Create a new disjoing set with the given set. Initially, every element is in a separate set.

Definition at line 19 of file atomic_disjoint_set.cc.

References i, blender::threading::parallel_for(), and size().

Member Function Documentation

calc_reduced_ids()

int blender::AtomicDisjointSet::calc_reduced_ids

(

MutableSpan< int >

result

)

const

Get an identifier for each id. This is deterministic and does not depend on the order of joins. The ids are ordered by their first occurrence. Consequently, result[0] is always zero (unless there are no elements).

Returns

The total number of unique IDs.

Definition at line 36 of file atomic_disjoint_set.cc.

References blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add_new(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), b, blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), BLI_assert, blender::Vector< T, InlineBufferCapacity, Allocator >::end(), find_root(), i, blender::Vector< T, InlineBufferCapacity, Allocator >::index_range(), blender::threading::EnumerableThreadSpecific< T >::local(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::lookup(), blender::threading::parallel_for(), blender::parallel_sort(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::reserve(), blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), result, blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::size(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), size(), and blender::update_first_occurrence().

Referenced by blender::nodes::node_geo_scale_elements_cc::edge_to_vert_islands(), blender::nodes::node_geo_scale_elements_cc::face_to_vert_islands(), blender::nodes::node_geo_edges_to_face_groups_cc::FaceSetFromBoundariesInput::get_varray_for_context(), and blender::ed::sculpt_paint::islands::vert_disjoint_set_to_islands().

count_sets()

int blender::AtomicDisjointSet::count_sets

(

)

const

Count the number of disjoint sets.

Definition at line 96 of file atomic_disjoint_set.cc.

References count, and blender::threading::parallel_reduce().

Referenced by blender::nodes::node_geo_scale_elements_cc::edge_to_vert_islands(), and blender::nodes::node_geo_scale_elements_cc::face_to_vert_islands().

find_root()

int blender::AtomicDisjointSet::find_root ( int x ) const

inline

Find the element that represents the set containing x currently.

Definition at line 116 of file BLI_atomic_disjoint_set.hh.

References x.

Referenced by calc_reduced_ids(), in_same_set(), join(), and paintface_select_linked_faces().

in_same_set()

bool blender::AtomicDisjointSet::in_same_set ( int x, int y ) const

inline

Return true when x and y are in the same set.

Definition at line 99 of file BLI_atomic_disjoint_set.hh.

References find_root(), x, and y.

is_root()

bool blender::AtomicDisjointSet::is_root ( const int x ) const

inline

True when x represents a set.

Definition at line 138 of file BLI_atomic_disjoint_set.hh.

References x.

join()

void blender::AtomicDisjointSet::join ( int x, int y )

inline

Join the sets containing elements x and y. Nothing happens when they were in the same set before.

Definition at line 51 of file BLI_atomic_disjoint_set.hh.

References find_root(), x, and y.

Referenced by blender::ed::sculpt_paint::islands::calc_topology_islands_bmesh(), blender::ed::sculpt_paint::islands::calc_topology_islands_mesh(), blender::nodes::node_geo_scale_elements_cc::edge_to_vert_islands(), blender::nodes::node_geo_scale_elements_cc::face_to_vert_islands(), and blender::nodes::node_geo_edges_to_face_groups_cc::join_indices().

---

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

• BLI_atomic_disjoint_set.hh
• atomic_disjoint_set.cc