blender::index_mask Namespace Reference

Namespaces
namespace	detail
namespace	tests

Classes
struct	AtomicExpr
struct	CoarseResult
struct	CoarseSegment
struct	CourseBoundary
struct	DifferenceCourseBoundary
struct	DifferenceExpr
struct	EvaluatedSegment
struct	Expr
class	ExprBuilder
class	IndexMask
struct	IndexMaskData
class	IndexMaskFromSegment
class	IndexMaskMemory
class	IndexMaskSegment
struct	IntersectionExpr
struct	ParallelSegmentsCollector
struct	RawMaskIterator
struct	UnionExpr

Enumerations
enum class	ExactEvalMode { Indices , Bits }

Functions
std::array< int16_t, max_segment_size >	build_static_indices_array ()
const IndexMask &	get_static_index_mask_for_min_size (const int64_t min_size)
std::ostream &	operator<< (std::ostream &stream, const IndexMask &mask)
IndexMask	evaluate_expression (const Expr &expression, IndexMaskMemory &memory)
template void	build_reverse_map< int > (const IndexMask &mask, MutableSpan< int > r_map)
template<typename T , int64_t InlineBufferSize>
static void	segments_from_indices (const Span< T > indices, LinearAllocator<> &allocator, Vector< IndexMaskSegment, InlineBufferSize > &r_segments)
static int64_t	from_bits_batch_predicate (const IndexMaskSegment universe_segment, IndexRangesBuilder< int16_t > &builder, const BitSpan bits_slice)
static void	segments_from_batch_predicate (const IndexMaskSegment universe_segment, LinearAllocator<> &allocator, const FunctionRef< int64_t(const IndexMaskSegment &universe_segment, IndexRangesBuilder< int16_t > &builder)> batch_predicate, Vector< IndexMaskSegment, 16 > &r_segments)
static Array< int16_t >	build_every_nth_index_array (const int64_t n)
static Span< int16_t >	get_every_nth_index (const int64_t n, const int64_t repetitions, IndexMaskMemory &memory)
static bool	segments_is_equal (const IndexMaskSegment &a, const IndexMaskSegment &b)
bool	operator== (const IndexMask &a, const IndexMask &b)
static void	sort_course_boundaries (MutableSpan< CourseBoundary > boundaries)
static void	sort_course_boundaries (MutableSpan< DifferenceCourseBoundary > boundaries)
static CoarseSegment &	add_coarse_segment__full (CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult &result)
static CoarseSegment &	add_coarse_segment__unknown (CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult &result)
static CoarseSegment &	add_coarse_segment__copy (CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, const IndexMask &copy_from_mask, CoarseResult &result)
static void	evaluate_coarse_union (const Span< CourseBoundary > boundaries, CoarseResult &r_result)
static void	evaluate_coarse_intersection (const Span< CourseBoundary > boundaries, const int64_t terms_num, CoarseResult &r_result)
static void	evaluate_coarse_difference (const Span< DifferenceCourseBoundary > boundaries, CoarseResult &r_result)
static CoarseResult	evaluate_coarse (const Expr &root_expression, const Span< const Expr * > eval_order, const std::optional< IndexRange > eval_bounds=std::nullopt)
static Span< int16_t >	bits_to_indices (const BoundedBitSpan bits, LinearAllocator<> &allocator)
static IndexMaskSegment	evaluate_exact_with_bits (const Expr &root_expression, LinearAllocator<> &allocator, const IndexRange bounds, const Span< const Expr * > eval_order)
static IndexMaskSegment	union_index_mask_segments (const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t *r_values)
static IndexMaskSegment	intersect_index_mask_segments (const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t *r_values)
static IndexMaskSegment	difference_index_mask_segments (const IndexMaskSegment main_segment, const Span< IndexMaskSegment > subtract_segments, const int64_t bounds_min, int16_t *r_values)
static IndexMaskSegment	evaluate_exact_with_indices (const Expr &root_expression, LinearAllocator<> &allocator, const IndexRange bounds, const Span< const Expr * > eval_order)
static Vector< IndexMaskSegment >	build_result_mask_segments (const Span< EvaluatedSegment > evaluated_segments)
static Vector< const Expr *, inline_expr_array_size >	compute_eval_order (const Expr &root_expression)
static ExactEvalMode	determine_exact_eval_mode (const Expr &root_expression)
static void	evaluate_coarse_and_split_until_segments_are_short (const Expr &root_expression, const Span< const Expr * > eval_order, Vector< EvaluatedSegment, 16 > &r_evaluated_segments, Vector< IndexRange, 16 > &r_short_unknown_segments)
static void	evaluate_short_unknown_segments_exactly (const Expr &root_expression, const ExactEvalMode exact_eval_mode, const Span< const Expr * > eval_order, const Span< IndexRange > short_unknown_segments, IndexMaskMemory &memory, Vector< EvaluatedSegment, 16 > &r_evaluated_segments)
static IndexMask	evaluated_segments_to_index_mask (MutableSpan< EvaluatedSegment > evaluated_segments, IndexMaskMemory &memory)
static IndexMask	evaluate_expression_impl (const Expr &root_expression, IndexMaskMemory &memory, const ExactEvalMode exact_eval_mode)
Utilities
const std::array< int16_t, max_segment_size > &	get_static_indices_array ()
template<typename T >
void	masked_fill (MutableSpan< T > data, const T &value, const IndexMask &mask)
template<typename T >
void	build_reverse_map (const IndexMask &mask, MutableSpan< T > r_map)
int64_t	consolidate_index_mask_segments (MutableSpan< IndexMaskSegment > segments, IndexMaskMemory &memory)
#RawMaskIterator Inline Methods
bool	operator!= (const RawMaskIterator &a, const RawMaskIterator &b)
bool	operator== (const RawMaskIterator &a, const RawMaskIterator &b)

Variables
static constexpr int64_t	max_segment_size_shift = 14
static constexpr int64_t	max_segment_size = (1 << max_segment_size_shift)
static constexpr int64_t	max_segment_size_mask_low = max_segment_size - 1
static constexpr int64_t	max_segment_size_mask_high = ~max_segment_size_mask_low
constexpr int64_t	inline_expr_array_size = 16
static constexpr int64_t	segment_size_threshold = 32

#IndexMask Inline Methods
template<typename Fn >
constexpr bool	has_segment_and_start_parameter
void	init_empty_mask (IndexMaskData &data)
template<typename T , typename Fn >
void	optimized_foreach_index (const IndexMaskSegment segment, const Fn fn)
template<typename T , typename Fn >
void	optimized_foreach_index_with_pos (const IndexMaskSegment segment, const int64_t segment_pos, const Fn fn)
bool	operator!= (const IndexMask &a, const IndexMask &b)

Detailed Description

Expression evaluation has multiple phases:

1. A coarse evaluation that tries to find segments which can be trivially evaluated. For example, taking the union of two overlapping ranges can be done in O(1) time.
2. For all segments which can't be fully evaluated using coarse evaluation, an exact evaluation is done. This uses either an index-based or bit-based approach depending on a heuristic.
3. Construct the final index mask based on the resulting intermediate segments.

Enumeration Type Documentation

ExactEvalMode

enum class blender::index_mask::ExactEvalMode

strong

There are different ways to do the exact evaluation. Depending on the expression or data, one or the other is more efficient.

Enumerator
Indices	Does the evaluation by working directly with arrays of sorted indices. This is usually best when the expression does not have intermediate results, i.e. it is very simple.
Bits	The evaluation works with bits. There is extra overhead to convert the input masks to bit arrays and to convert the final result back into indices. In exchange, the actual expression evaluation is significantly cheaper because it's just a bunch of bit operations. For larger expressions, this is typically much more efficient.

Definition at line 102 of file index_mask_expression.cc.

Function Documentation

add_coarse_segment__copy()

static CoarseSegment & blender::index_mask::add_coarse_segment__copy ( CoarseSegment * prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, const IndexMask & copy_from_mask, CoarseResult & result )

static

Extends a previous copy segment or appends a new one.

Definition at line 185 of file index_mask_expression.cc.

References blender::index_mask::CoarseSegment::bounds, blender::index_mask::CoarseSegment::Copy, blender::IndexRange::from_begin_end(), blender::index_mask::CoarseSegment::mask, blender::IndexRange::one_after_last(), segment_size_threshold, blender::IndexRange::start(), blender::index_mask::CoarseSegment::type, blender::index_mask::CoarseSegment::Unknown, and blender::IndexRange::with_new_end().

Referenced by evaluate_coarse_difference(), evaluate_coarse_intersection(), and evaluate_coarse_union().

add_coarse_segment__full()

static CoarseSegment & blender::index_mask::add_coarse_segment__full ( CoarseSegment * prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult & result )

static

Extends a previous full segment or appends a new one.

Definition at line 137 of file index_mask_expression.cc.

References blender::index_mask::CoarseSegment::bounds, blender::IndexRange::from_begin_size(), blender::index_mask::CoarseSegment::Full, max_segment_size, blender::IndexRange::one_after_last(), segment_size_threshold, blender::IndexRange::size(), blender::IndexRange::start(), blender::index_mask::CoarseSegment::type, blender::index_mask::CoarseSegment::Unknown, and blender::IndexRange::with_new_end().

Referenced by evaluate_coarse_difference(), evaluate_coarse_intersection(), and evaluate_coarse_union().

add_coarse_segment__unknown()

static CoarseSegment & blender::index_mask::add_coarse_segment__unknown ( CoarseSegment * prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult & result )

static

Extends a previous unknown segment or appends a new one.

Definition at line 165 of file index_mask_expression.cc.

References blender::index_mask::CoarseSegment::bounds, blender::IndexRange::from_begin_end(), segment_size_threshold, blender::IndexRange::start(), blender::index_mask::CoarseSegment::type, blender::index_mask::CoarseSegment::Unknown, and blender::IndexRange::with_new_end().

Referenced by evaluate_coarse_difference(), evaluate_coarse_intersection(), and evaluate_coarse_union().

bits_to_indices()

static Span< int16_t > blender::index_mask::bits_to_indices ( const BoundedBitSpan bits, LinearAllocator<> & allocator )

static

Definition at line 564 of file index_mask_expression.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append_unchecked(), BLI_assert, blender::LinearAllocator< Allocator >::construct_array_copy(), blender::bits::foreach_1_index(), and max_segment_size.

Referenced by evaluate_exact_with_bits().

build_every_nth_index_array()

static Array< int16_t > blender::index_mask::build_every_nth_index_array ( const int64_t n )

static

Definition at line 900 of file index_mask.cc.

References BLI_assert, data, and max_segment_size.

Referenced by get_every_nth_index().

build_result_mask_segments()

static Vector< IndexMaskSegment > blender::index_mask::build_result_mask_segments ( const Span< EvaluatedSegment > evaluated_segments )

static

Turn the evaluated segments into index mask segments that are then used to initialize the resulting index mask.

Definition at line 974 of file index_mask_expression.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::index_mask::EvaluatedSegment::Copy, blender::index_mask::IndexMask::foreach_segment(), blender::index_mask::EvaluatedSegment::Full, get_static_indices_array(), blender::index_mask::EvaluatedSegment::Indices, max_segment_size, blender::Vector< T, InlineBufferCapacity, Allocator >::size(), and blender::index_mask::IndexMask::slice_content().

Referenced by evaluated_segments_to_index_mask().

build_reverse_map()

template<typename T >

void blender::index_mask::build_reverse_map	(	const IndexMask &	mask,
		MutableSpan< T >	r_map )

Fill masked indices of r_mask with the index of that item in the mask such that r_map[mask[i]] == i for the whole mask. The size of r_map needs to be at least mask.min_array_size().

Definition at line 31 of file index_mask.cc.

References BLI_assert, blender::MutableSpan< T >::fill(), and blender::MutableSpan< T >::size().

build_reverse_map< int >()

template void blender::index_mask::build_reverse_map< int >	(	const IndexMask &	mask,
		MutableSpan< int >	r_map )

Referenced by blender::geometry::remap_verts().

build_static_indices_array()

std::array< int16_t, max_segment_size > blender::index_mask::build_static_indices_array

(

)

Definition at line 44 of file index_mask.cc.

References data, and max_segment_size.

Referenced by get_static_indices_array().

compute_eval_order()

static Vector< const Expr *, inline_expr_array_size > blender::index_mask::compute_eval_order ( const Expr & root_expression )

static

Computes an evaluation order of the expression. The important aspect is that all child terms come before the term that uses them.

Definition at line 1011 of file index_mask_expression.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::index_mask::Expr::Atomic, blender::index_mask::Expr::expression_array_size(), blender::index_mask::Expr::index, blender::Stack< T, InlineBufferCapacity, Allocator >::is_empty(), blender::Stack< T, InlineBufferCapacity, Allocator >::peek(), blender::Stack< T, InlineBufferCapacity, Allocator >::pop(), blender::Stack< T, InlineBufferCapacity, Allocator >::push(), blender::index_mask::Expr::terms, and blender::index_mask::Expr::type.

Referenced by evaluate_expression_impl().

consolidate_index_mask_segments()

int64_t blender::index_mask::consolidate_index_mask_segments	(	MutableSpan< IndexMaskSegment >	segments,
		IndexMaskMemory &	memory )

Joins segments together based on heuristics. Generally, one wants as few segments as possible, but one also wants full-range-segments if possible and we don't want to copy too many indices around to reduce the number of segments.

Returns

Number of consolidated segments. Those are ordered to the beginning of the span.

Definition at line 221 of file index_mask.cc.

References blender::MutableSpan< T >::begin(), blender::IndexRange::drop_front(), blender::MutableSpan< T >::end(), blender::IndexRange::from_begin_end_inclusive(), get_static_indices_array(), blender::MutableSpan< T >::index_range(), blender::MutableSpan< T >::is_empty(), blender::MutableSpan< T >::last(), max_segment_size, blender::unique_sorted_indices::non_empty_as_range_try(), blender::unique_sorted_indices::non_empty_is_range(), blender::MutableSpan< T >::size(), and blender::Span< T >::take_front().

Referenced by blender::index_mask::IndexMask::from_indices(), and blender::index_mask::detail::from_predicate_impl().

determine_exact_eval_mode()

static ExactEvalMode blender::index_mask::determine_exact_eval_mode ( const Expr & root_expression )

static

Uses a heuristic to decide which exact evaluation mode probably works best.

Definition at line 1056 of file index_mask_expression.cc.

References Bits, Indices, and blender::index_mask::Expr::terms.

Referenced by evaluate_expression().

difference_index_mask_segments()

static IndexMaskSegment blender::index_mask::difference_index_mask_segments ( const IndexMaskSegment main_segment, const Span< IndexMaskSegment > subtract_segments, const int64_t bounds_min, int16_t * r_values )

static

Compute a new set of indices that is the difference between the main-segment and all the subtract-segments.

Definition at line 757 of file index_mask_expression.cc.

References b, blender::OffsetSpan< T, BaseT >::begin(), blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), count, blender::Span< T >::data(), blender::IndexRange::drop_front(), blender::OffsetSpan< T, BaseT >::end(), blender::Vector< T, InlineBufferCapacity, Allocator >::end(), blender::Vector< T, InlineBufferCapacity, Allocator >::index_range(), blender::OffsetSpan< T, BaseT >::is_empty(), blender::Span< T >::is_empty(), blender::index_mask::IndexMaskSegment::shift(), blender::OffsetSpan< T, BaseT >::size(), blender::Span< T >::size(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), and union_index_mask_segments().

Referenced by evaluate_exact_with_indices().

evaluate_coarse()

static CoarseResult blender::index_mask::evaluate_coarse ( const Expr & root_expression, const Span< const Expr * > eval_order, const std::optional< IndexRange > eval_bounds = std::nullopt )

static

The coarse evaluation only looks at the index masks as a whole within the given bounds. This limitation allows it to do many operations in constant time independent of the number of indices within each mask. For example, it can detect that two full index masks that overlap result in a new full index mask when the union of intersection is computed.

For more complex index-masks, coarse evaluation outputs segments with type CoarseSegment::Type::Unknown. Those segments can be evaluated in more detail afterwards.

Parameters

root_expression	Expression to be evaluated.
eval_order	Pre-computed evaluation order. All children of a term must come before the term itself.
eval_bounds	If given, the evaluation is restricted to those bounds. Otherwise, the full referenced masks are used.

Definition at line 476 of file index_mask_expression.cc.

References blender::index_mask::Expr::as_atomic(), blender::index_mask::Expr::as_difference(), blender::index_mask::Expr::as_intersection(), blender::index_mask::Expr::as_union(), blender::index_mask::Expr::Atomic, blender::index_mask::CoarseSegment::Copy, blender::index_mask::Expr::Difference, evaluate_coarse_difference(), evaluate_coarse_intersection(), evaluate_coarse_union(), blender::index_mask::Expr::expression_array_size(), blender::index_mask::CoarseSegment::Full, blender::index_mask::Expr::index, inline_expr_array_size, blender::index_mask::Expr::Intersection, blender::index_mask::AtomicExpr::mask, mask(), blender::index_mask::CoarseResult::segments, blender::index_mask::IndexMask::slice_content(), sort_course_boundaries(), blender::index_mask::Expr::terms, and blender::index_mask::Expr::Union.

Referenced by evaluate_coarse_and_split_until_segments_are_short().

evaluate_coarse_and_split_until_segments_are_short()

static void blender::index_mask::evaluate_coarse_and_split_until_segments_are_short ( const Expr & root_expression, const Span< const Expr * > eval_order, Vector< EvaluatedSegment, 16 > & r_evaluated_segments, Vector< IndexRange, 16 > & r_short_unknown_segments )

static

Definition at line 1067 of file index_mask_expression.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, blender::index_mask::CoarseSegment::Copy, blender::index_mask::EvaluatedSegment::Copy, blender::IndexRange::drop_front(), evaluate_coarse(), blender::index_mask::CoarseSegment::Full, blender::index_mask::EvaluatedSegment::Full, blender::Stack< T, InlineBufferCapacity, Allocator >::is_empty(), max_segment_size, blender::Stack< T, InlineBufferCapacity, Allocator >::pop(), blender::Stack< T, InlineBufferCapacity, Allocator >::push(), blender::IndexRange::size(), blender::IndexRange::take_front(), and blender::index_mask::CoarseSegment::Unknown.

Referenced by evaluate_expression_impl().

evaluate_coarse_difference()

static void blender::index_mask::evaluate_coarse_difference ( const Span< DifferenceCourseBoundary > boundaries, CoarseResult & r_result )

static

Definition at line 352 of file index_mask_expression.cc.

References add_coarse_segment__copy(), add_coarse_segment__full(), add_coarse_segment__unknown(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, blender::index_mask::CoarseSegment::Copy, blender::index_mask::CoarseSegment::Full, blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::index_mask::CoarseSegment::mask, blender::Vector< T, InlineBufferCapacity, Allocator >::remove_first_occurrence_and_reorder(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), blender::index_mask::CoarseSegment::type, and blender::index_mask::CoarseSegment::Unknown.

Referenced by evaluate_coarse().

evaluate_coarse_intersection()

static void blender::index_mask::evaluate_coarse_intersection ( const Span< CourseBoundary > boundaries, const int64_t terms_num, CoarseResult & r_result )

static

Definition at line 278 of file index_mask_expression.cc.

References add_coarse_segment__copy(), add_coarse_segment__full(), add_coarse_segment__unknown(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, blender::index_mask::CoarseSegment::Copy, ELEM, blender::index_mask::CoarseSegment::Full, blender::Vector< T, InlineBufferCapacity, Allocator >::remove_first_occurrence_and_reorder(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), and blender::index_mask::CoarseSegment::Unknown.

Referenced by evaluate_coarse().

evaluate_coarse_union()

static void blender::index_mask::evaluate_coarse_union ( const Span< CourseBoundary > boundaries, CoarseResult & r_result )

static

Definition at line 213 of file index_mask_expression.cc.

References add_coarse_segment__copy(), add_coarse_segment__full(), add_coarse_segment__unknown(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::index_mask::CoarseSegment::Copy, ELEM, blender::index_mask::CoarseSegment::Full, blender::Vector< T, InlineBufferCapacity, Allocator >::remove_first_occurrence_and_reorder(), and blender::index_mask::CoarseSegment::Unknown.

Referenced by evaluate_coarse().

evaluate_exact_with_bits()

static IndexMaskSegment blender::index_mask::evaluate_exact_with_bits ( const Expr & root_expression, LinearAllocator<> & allocator, const IndexRange bounds, const Span< const Expr * > eval_order )

static

Does an exact evaluation of the expression within the given bounds. The evaluation generally works in three steps:

1. Convert input indices into bit spans.
2. Use bit operations to evaluate the expression.
3. Convert resulting bit span back to indices.

The trade-off here is that the actual expression evaluation is much faster but the conversions take some extra time. Therefore, this approach is best when the evaluation would otherwise take longer than the conversions which is usually the case for non-trivial expressions.

Definition at line 586 of file index_mask_expression.cc.

References blender::index_mask::Expr::as_atomic(), blender::index_mask::Expr::Atomic, b, bits_to_indices(), blender::bits::BitsPerInt, BLI_assert, blender::ceil_division(), blender::bits::copy_from_or(), blender::index_mask::Expr::Difference, blender::index_mask::Expr::expression_array_size(), blender::index_mask::Expr::index, blender::index_mask::Expr::Intersection, blender::index_mask::AtomicExpr::mask, max_segment_size, blender::bits::mix_into_first_expr(), blender::IndexRange::size(), blender::index_mask::IndexMask::slice_content(), blender::IndexRange::start(), blender::index_mask::IndexMask::to_bits(), and blender::index_mask::Expr::Union.

Referenced by evaluate_short_unknown_segments_exactly().

evaluate_exact_with_indices()

static IndexMaskSegment blender::index_mask::evaluate_exact_with_indices ( const Expr & root_expression, LinearAllocator<> & allocator, const IndexRange bounds, const Span< const Expr * > eval_order )

static

Does an exact evaluation of the expression with in the given bounds. The evaluation builds on top of algorithms like std::set_union. This approach is especially useful if the expression is simple and doesn't have many intermediate values.

Definition at line 849 of file index_mask_expression.cc.

References blender::LinearAllocator< Allocator >::allocate_array(), blender::index_mask::Expr::as_atomic(), blender::index_mask::Expr::as_difference(), blender::index_mask::Expr::as_intersection(), blender::index_mask::Expr::as_union(), blender::index_mask::Expr::Atomic, BLI_assert, blender::MutableSpan< T >::data(), blender::index_mask::Expr::Difference, difference_index_mask_segments(), blender::index_mask::Expr::expression_array_size(), blender::LinearAllocator< Allocator >::free_end_of_previous_allocation(), blender::index_mask::Expr::index, intersect_index_mask_segments(), blender::index_mask::Expr::Intersection, blender::OffsetSpan< T, BaseT >::is_empty(), blender::index_mask::AtomicExpr::mask, max_segment_size, blender::IndexRange::size(), blender::OffsetSpan< T, BaseT >::size(), blender::MutableSpan< T >::size_in_bytes(), blender::index_mask::IndexMask::slice_content(), blender::IndexRange::start(), blender::index_mask::Expr::terms, blender::index_mask::Expr::Union, and union_index_mask_segments().

Referenced by evaluate_short_unknown_segments_exactly().

evaluate_expression()

IndexMask blender::index_mask::evaluate_expression	(	const Expr &	expression,
		IndexMaskMemory &	memory )

Definition at line 1287 of file index_mask_expression.cc.

References BLI_assert, determine_exact_eval_mode(), evaluate_expression(), evaluate_expression_impl(), and mask().

Referenced by blender::index_mask::IndexMask::complement(), evaluate_expression(), blender::index_mask::IndexMask::from_difference(), blender::index_mask::IndexMask::from_intersection(), blender::index_mask::IndexMask::from_union(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), blender::index_mask::tests::TEST(), and blender::index_mask::tests::TEST().

evaluate_expression_impl()

static IndexMask blender::index_mask::evaluate_expression_impl ( const Expr & root_expression, IndexMaskMemory & memory, const ExactEvalMode exact_eval_mode )

static

Definition at line 1262 of file index_mask_expression.cc.

References compute_eval_order(), evaluate_coarse_and_split_until_segments_are_short(), evaluate_expression_impl(), evaluate_short_unknown_segments_exactly(), and evaluated_segments_to_index_mask().

Referenced by evaluate_expression(), and evaluate_expression_impl().

evaluate_short_unknown_segments_exactly()

static void blender::index_mask::evaluate_short_unknown_segments_exactly ( const Expr & root_expression, const ExactEvalMode exact_eval_mode, const Span< const Expr * > eval_order, const Span< IndexRange > short_unknown_segments, IndexMaskMemory & memory, Vector< EvaluatedSegment, 16 > & r_evaluated_segments )

static

Definition at line 1127 of file index_mask_expression.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::index_mask::Expr::as_atomic(), blender::index_mask::Expr::Atomic, blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), Bits, blender::IndexRange::drop_back(), blender::IndexRange::drop_front(), blender::Vector< T, InlineBufferCapacity, Allocator >::end(), evaluate_exact_with_bits(), evaluate_exact_with_indices(), blender::Vector< T, InlineBufferCapacity, Allocator >::extend(), blender::IndexRange::first(), blender::IndexRange::from_begin_end(), blender::Span< T >::index_range(), blender::Vector< T, InlineBufferCapacity, Allocator >::index_range(), blender::index_mask::EvaluatedSegment::Indices, Indices, blender::IndexRange::is_empty(), blender::index_mask::AtomicExpr::mask, blender::IndexRange::one_after_last(), blender::threading::parallel_for(), blender::Span< T >::size(), blender::index_mask::IndexMask::slice_content(), blender::LinearAllocator< Allocator >::transfer_ownership_from(), and blender::index_mask::Expr::type.

Referenced by evaluate_expression_impl().

evaluated_segments_to_index_mask()

static IndexMask blender::index_mask::evaluated_segments_to_index_mask ( MutableSpan< EvaluatedSegment > evaluated_segments, IndexMaskMemory & memory )

static

Definition at line 1231 of file index_mask_expression.cc.

References b, blender::MutableSpan< T >::begin(), blender::index_mask::EvaluatedSegment::bounds, build_result_mask_segments(), blender::index_mask::EvaluatedSegment::copy_mask, blender::MutableSpan< T >::end(), evaluated_segments_to_index_mask(), blender::index_mask::EvaluatedSegment::indices, blender::MutableSpan< T >::is_empty(), blender::MutableSpan< T >::size(), blender::index_mask::IndexMask::slice_content(), and blender::index_mask::EvaluatedSegment::type.

Referenced by evaluate_expression_impl(), and evaluated_segments_to_index_mask().

from_bits_batch_predicate()

static int64_t blender::index_mask::from_bits_batch_predicate ( const IndexMaskSegment universe_segment, IndexRangesBuilder< int16_t > & builder, const BitSpan bits_slice )

static

Definition at line 451 of file index_mask.cc.

References blender::OffsetSpan< T, BaseT >::base_span(), blender::bits::bits_to_index_ranges(), BLI_assert, blender::OffsetSpan< T, BaseT >::index_range(), blender::OffsetSpan< T, BaseT >::last(), max_segment_size, and blender::unique_sorted_indices::non_empty_is_range().

Referenced by blender::index_mask::IndexMask::from_bits(), and blender::index_mask::IndexMask::from_bools().

get_every_nth_index()

static Span< int16_t > blender::index_mask::get_every_nth_index ( const int64_t n, const int64_t repetitions, IndexMaskMemory & memory )

static

Returns a span containing every nth index. This is optimized for a few special values of n which are cached. The returned indices have either static life-time, or they are freed when the given memory is feed.

Definition at line 916 of file index_mask.cc.

References blender::LinearAllocator< Allocator >::allocate_array(), BLI_assert, build_every_nth_index_array(), data, and max_segment_size.

Referenced by blender::index_mask::IndexMask::from_repeating().

get_static_index_mask_for_min_size()

const IndexMask & blender::index_mask::get_static_index_mask_for_min_size

(

const int64_t

min_size

)

Definition at line 53 of file index_mask.cc.

References BLI_assert, blender::Array< T, InlineBufferCapacity, Allocator >::data(), get_static_indices_array(), blender::index_mask::IndexMaskData::indices_num_, blender::threading::isolate_task(), blender::Array< T, InlineBufferCapacity, Allocator >::last(), mask(), max_segment_size, blender::threading::parallel_for(), range, and UNUSED_VARS_NDEBUG.

Referenced by blender::index_mask::IndexMask::IndexMask(), and blender::index_mask::IndexMask::IndexMask().

get_static_indices_array()

const std::array< int16_t, max_segment_size > & blender::index_mask::get_static_indices_array ( )

inline

Definition at line 553 of file BLI_index_mask.hh.

References build_static_indices_array(), and data.

Referenced by build_result_mask_segments(), consolidate_index_mask_segments(), get_static_index_mask_for_min_size(), segments_from_batch_predicate(), segments_from_indices(), blender::index_mask::detail::segments_from_predicate_filter(), and blender::index_mask::tests::TEST().

init_empty_mask()

void blender::index_mask::init_empty_mask ( IndexMaskData & data )

inline

Definition at line 627 of file BLI_index_mask.hh.

Referenced by blender::index_mask::IndexMask::IndexMask(), blender::index_mask::IndexMask::IndexMask(), and blender::index_mask::IndexMask::IndexMask().

intersect_index_mask_segments()

static IndexMaskSegment blender::index_mask::intersect_index_mask_segments ( const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t * r_values )

static

Compute a new set of indices that is the intersection of the given segments.

Definition at line 701 of file index_mask_expression.cc.

References b, blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), count, blender::IndexRange::drop_front(), blender::Vector< T, InlineBufferCapacity, Allocator >::end(), blender::Vector< T, InlineBufferCapacity, Allocator >::index_range(), blender::Span< T >::is_empty(), blender::Span< T >::size(), and blender::Vector< T, InlineBufferCapacity, Allocator >::size().

Referenced by evaluate_exact_with_indices().

masked_fill()

template<typename T >

void blender::index_mask::masked_fill ( MutableSpan< T > data, const T & value, const IndexMask & mask )

inline

Definition at line 561 of file BLI_index_mask.hh.

Referenced by blender::nodes::node_geo_set_material_cc::assign_material_to_id_geometry(), BKE_pbvh_sync_visibility_from_verts(), blender::fn::multi_function::tests::OptionalOutputsFunction::call(), blender::nodes::node_geo_curve_sample_cc::SampleCurveFunction::call(), blender::nodes::node_geo_sample_nearest_cc::SampleNearestFunction::call(), blender::geometry::convert_curves_to_nurbs(), blender::bke::CurvesGeometry::fill_curve_types(), blender::ed::curves::fill_selection_false(), blender::ed::curves::fill_selection_true(), blender::draw::grease_pencil_edit_batch_ensure(), and blender::nodes::node_geo_curve_set_handle_type_cc::set_handle_type().

operator!=() [1/2]

bool blender::index_mask::operator!= ( const IndexMask & a, const IndexMask & b )

inline

Definition at line 1079 of file BLI_index_mask.hh.

operator!=() [2/2]

bool blender::index_mask::operator!= ( const RawMaskIterator & a, const RawMaskIterator & b )

inline

Definition at line 587 of file BLI_index_mask.hh.

References b.

operator<<()

std::ostream & blender::index_mask::operator<<	(	std::ostream &	stream,
		const IndexMask &	mask )

Definition at line 99 of file index_mask.cc.

References indices, and blender::unique_sorted_indices::split_to_ranges_and_spans().

operator==() [1/2]

bool blender::index_mask::operator==	(	const IndexMask &	a,
		const IndexMask &	b )

Definition at line 1118 of file index_mask.cc.

operator==() [2/2]

bool blender::index_mask::operator== ( const RawMaskIterator & a, const RawMaskIterator & b )

inline

Definition at line 592 of file BLI_index_mask.hh.

References b.

optimized_foreach_index()

template<typename T , typename Fn >

void blender::index_mask::optimized_foreach_index ( const IndexMaskSegment segment, const Fn fn )

inline

Definition at line 833 of file BLI_index_mask.hh.

References BLI_assert, blender::unique_sorted_indices::non_empty_is_range(), optimized_foreach_index(), and T.

Referenced by blender::index_mask::IndexMask::foreach_index_optimized(), and optimized_foreach_index().

optimized_foreach_index_with_pos()

template<typename T , typename Fn >

void blender::index_mask::optimized_foreach_index_with_pos ( const IndexMaskSegment segment, const int64_t segment_pos, const Fn fn )

inline

Definition at line 855 of file BLI_index_mask.hh.

References BLI_assert, blender::unique_sorted_indices::non_empty_is_range(), optimized_foreach_index_with_pos(), pos, and T.

Referenced by blender::index_mask::IndexMask::foreach_index_optimized(), and optimized_foreach_index_with_pos().

segments_from_batch_predicate()

static void blender::index_mask::segments_from_batch_predicate ( const IndexMaskSegment universe_segment, LinearAllocator<> & allocator, const FunctionRef< int64_t(const IndexMaskSegment &universe_segment, IndexRangesBuilder< int16_t > &builder)> batch_predicate, Vector< IndexMaskSegment, 16 > & r_segments )

static

Definition at line 496 of file index_mask.cc.

References blender::LinearAllocator< Allocator >::allocate_array(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::array_utils::fill_index_range(), blender::IndexRange::from_begin_end(), get_static_indices_array(), blender::IndexRangesBuilder< T >::index_range(), blender::IndexRangesBuilder< T >::is_empty(), blender::IndexRangesBuilder< T >::size(), and blender::Span< T >::slice().

Referenced by blender::index_mask::IndexMask::from_batch_predicate().

segments_from_indices()

template<typename T , int64_t InlineBufferSize>

static void blender::index_mask::segments_from_indices ( const Span< T > indices, LinearAllocator<> & allocator, Vector< IndexMaskSegment, InlineBufferSize > & r_segments )

static

Split the indices into segments. Afterwards, the indices referenced by #r_segments are either owned by #allocator or statically allocated.

Definition at line 333 of file index_mask.cc.

References blender::LinearAllocator< Allocator >::allocate_array(), blender::Vector< T, InlineBufferCapacity, Allocator >::append_as(), BLI_assert, blender::Span< T >::drop_front(), blender::binary_search::find_predicate_begin(), get_static_indices_array(), blender::Span< T >::is_empty(), max_segment_size, blender::IndexRange::size(), blender::Span< T >::size(), blender::Span< T >::slice_safe(), blender::unique_sorted_indices::split_to_ranges_and_spans(), blender::IndexRange::start(), and blender::Span< T >::take_front().

Referenced by blender::index_mask::IndexMask::from_indices().

segments_is_equal()

static bool blender::index_mask::segments_is_equal ( const IndexMaskSegment & a, const IndexMaskSegment & b )

static

Definition at line 1083 of file index_mask.cc.

References b, blender::Span< T >::begin(), BLI_assert, blender::Span< T >::end(), and blender::unique_sorted_indices::non_empty_is_range().

sort_course_boundaries() [1/2]

static void blender::index_mask::sort_course_boundaries ( MutableSpan< CourseBoundary > boundaries )

static

Definition at line 117 of file index_mask_expression.cc.

References b.

Referenced by evaluate_coarse().

sort_course_boundaries() [2/2]

static void blender::index_mask::sort_course_boundaries ( MutableSpan< DifferenceCourseBoundary > boundaries )

static

Definition at line 124 of file index_mask_expression.cc.

References b.

union_index_mask_segments()

static IndexMaskSegment blender::index_mask::union_index_mask_segments ( const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t * r_values )

static

Compute a new set of indices that is the union of the given segments.

Definition at line 641 of file index_mask_expression.cc.

References b, blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), count, blender::IndexRange::drop_front(), blender::Vector< T, InlineBufferCapacity, Allocator >::end(), blender::Vector< T, InlineBufferCapacity, Allocator >::index_range(), blender::Span< T >::is_empty(), blender::Span< T >::size(), and blender::Vector< T, InlineBufferCapacity, Allocator >::size().

Referenced by difference_index_mask_segments(), and evaluate_exact_with_indices().

Variable Documentation

has_segment_and_start_parameter

template<typename Fn >

bool blender::index_mask::has_segment_and_start_parameter

constexpr

Initial value:

=
    std::is_invocable_r_v<void, Fn, IndexMaskSegment, int64_t> ||
    std::is_invocable_r_v<void, Fn, IndexRange, int64_t>

Definition at line 791 of file BLI_index_mask.hh.

Referenced by blender::index_mask::IndexMask::foreach_segment(), and blender::index_mask::IndexMask::foreach_segment_optimized().

inline_expr_array_size

int64_t blender::index_mask::inline_expr_array_size = 16

constexpr

Number of expression terms which don't require extra allocations in some places.

Definition at line 29 of file index_mask_expression.cc.

Referenced by evaluate_coarse().

max_segment_size

int64_t blender::index_mask::max_segment_size = (1 << max_segment_size_shift)

staticconstexpr

Definition at line 42 of file BLI_index_mask.hh.

Referenced by add_coarse_segment__full(), bits_to_indices(), build_every_nth_index_array(), build_result_mask_segments(), build_static_indices_array(), consolidate_index_mask_segments(), evaluate_coarse_and_split_until_segments_are_short(), evaluate_exact_with_bits(), evaluate_exact_with_indices(), blender::index_mask::IndexMask::find_larger_equal(), blender::index_mask::IndexMask::from_bits(), from_bits_batch_predicate(), blender::index_mask::IndexMask::from_bools(), blender::index_mask::IndexMask::from_indices(), blender::index_mask::IndexMask::from_repeating(), get_every_nth_index(), get_static_index_mask_for_min_size(), blender::index_mask::IndexMask::IndexMask(), segments_from_indices(), blender::index_mask::tests::TEST(), and blender::index_mask::IndexMaskFromSegment::update().

max_segment_size_mask_high

int64_t blender::index_mask::max_segment_size_mask_high = ~max_segment_size_mask_low

staticconstexpr

Definition at line 44 of file BLI_index_mask.hh.

Referenced by blender::index_mask::IndexMask::IndexMask(), and blender::index_mask::IndexMask::IndexMask().

max_segment_size_mask_low

int64_t blender::index_mask::max_segment_size_mask_low = max_segment_size - 1

staticconstexpr

Definition at line 43 of file BLI_index_mask.hh.

Referenced by blender::index_mask::IndexMask::IndexMask().

max_segment_size_shift

int64_t blender::index_mask::max_segment_size_shift = 14

staticconstexpr

Constants that define the maximum segment size. Segment sizes are limited so that the indices within each segment can be stored as int16_t, which allows the mask to stored much more compactly than if 32 or 64 bit ints would be used.

• Using 8 bit ints does not work well, because then the maximum segment size would be too small for eliminate per-segment overhead in many cases and also leads to many more segments.
• The most-significant-bit is not used so that signed integers can be used which avoids common issues when mixing signed and unsigned ints.
• The second most-significant bit is not used for indices so that max_segment_size itself can be stored in the int16_t.
• The maximum number of indices in a segment is 16384, which is generally enough to make the overhead per segment negligible when processing large index masks.
• A power of two is used for max_segment_size, because that allows for faster construction of index masks for index ranges.

Definition at line 41 of file BLI_index_mask.hh.

Referenced by blender::index_mask::IndexMask::IndexMask(), and blender::index_mask::IndexMask::IndexMask().

segment_size_threshold

int64_t blender::index_mask::segment_size_threshold = 32

staticconstexpr

Smaller segments should generally be merged together.

Definition at line 134 of file index_mask_expression.cc.

Referenced by add_coarse_segment__copy(), add_coarse_segment__full(), and add_coarse_segment__unknown().