 |
Blender V4.3
|
|
Blender V4.3
|
#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 |
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 22 of file BLI_atomic_disjoint_set.hh.
| 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 13 of file atomic_disjoint_set.cc.
References blender::threading::parallel_for(), and range.
| 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).
Definition at line 34 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(), 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(), range, blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::reserve(), blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), blender::Array< T, InlineBufferCapacity, Allocator >::size(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::size(), blender::Vector< T, InlineBufferCapacity, Allocator >::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(), and blender::ed::sculpt_paint::islands::vert_disjoint_set_to_islands().
| int blender::AtomicDisjointSet::count_sets | ( | ) | const |
Count the number of disjoint sets.
Definition at line 94 of file atomic_disjoint_set.cc.
References count, blender::Array< T, InlineBufferCapacity, Allocator >::index_range(), 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 the element that represents the set containing x currently.
Definition at line 112 of file BLI_atomic_disjoint_set.hh.
References x.
Referenced by calc_reduced_ids(), in_same_set(), and join().
Return true when x and y are in the same set.
Definition at line 95 of file BLI_atomic_disjoint_set.hh.
References find_root().
|
inline |
True when x represents a set.
Definition at line 134 of file BLI_atomic_disjoint_set.hh.
References x.
Join the sets containing elements x and y. Nothing happens when they were in the same set before.
Definition at line 47 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(), and blender::nodes::node_geo_scale_elements_cc::face_to_vert_islands().