Blender V5.3
index_mask.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <fmt/format.h>
10#include <fmt/ranges.h>
11#include <iostream>
12
13#include "BLI_array.hh"
14#include "BLI_array_utils.hh"
16#include "BLI_bit_span_ops.hh"
18#include "BLI_bit_vector.hh"
20#include "BLI_index_mask.hh"
23#include "BLI_math_base.hh"
24#include "BLI_rand.hh"
25#include "BLI_set.hh"
26#include "BLI_sort.hh"
27#include "BLI_task.hh"
28#include "BLI_threads.hh"
29#include "BLI_vector_set.hh"
30#include "BLI_virtual_array.hh"
31
32#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
33
34namespace blender::index_mask {
35
36template<typename T> void build_reverse_map(const IndexMask &mask, MutableSpan<T> r_map)
37{
38#ifndef NDEBUG
39 /* Catch errors with asserts in debug builds. */
40 r_map.fill(-1);
41#endif
42 BLI_assert(r_map.size() >= mask.min_array_size());
43 mask.foreach_index_optimized<T>([&](const T src, const T dst) { r_map[src] = dst; },
45}
46
48
49std::array<int16_t, max_segment_size> build_static_indices_array()
50{
51 std::array<int16_t, max_segment_size> data;
52 for (int16_t i = 0; i < max_segment_size; i++) {
53 data[size_t(i)] = i;
54 }
55 return data;
56}
57
59{
60 static constexpr int64_t size_shift = 31;
61 static constexpr int64_t max_size = (int64_t(1) << size_shift); /* 2'147'483'648 */
62 static constexpr int64_t segments_num = max_size / max_segment_size; /* 131'072 */
63
64 /* Make sure we are never requesting a size that's larger than what was statically allocated.
65 * If that's ever needed, we can either increase #size_shift or dynamically allocate an even
66 * larger mask. */
67 BLI_assert(min_size <= max_size);
68 UNUSED_VARS_NDEBUG(min_size);
69
70 static IndexMask static_mask = []() {
71 static Array<const int16_t *> indices_by_segment(segments_num);
72 /* The offsets and cumulative segment sizes array contain the same values here, so just use a
73 * single array for both. */
74 static Array<int64_t> segment_offsets(segments_num + 1);
75
76 static const int16_t *static_offsets = get_static_indices_array().data();
77
78 /* Isolate because the mutex protecting the initialization of #static_mask is locked. */
80 threading::parallel_for(IndexRange(segments_num), 1024, [&](const IndexRange range) {
81 for (const int64_t segment_i : range) {
82 indices_by_segment[segment_i] = static_offsets;
83 segment_offsets[segment_i] = segment_i * max_segment_size;
84 }
85 });
86 });
87 segment_offsets.last() = max_size;
88
90 IndexMaskData &data = mask.data_for_inplace_construction();
91 data.indices_num_ = max_size;
92 data.segments_num_ = segments_num;
93 data.indices_by_segment_ = indices_by_segment.data();
94 data.segment_offsets_ = segment_offsets.data();
95 data.cumulative_segment_sizes_ = segment_offsets.data();
96 data.begin_index_in_segment_ = 0;
97 data.end_index_in_segment_ = max_segment_size;
98
99 return mask;
100 }();
101 return static_mask;
102}
103
104std::ostream &operator<<(std::ostream &stream, const IndexMask &mask)
105{
106 Array<int64_t> indices(mask.size());
107 mask.to_indices<int64_t>(indices);
111 for (const std::variant<IndexRange, Span<int64_t>> &segment : segments) {
112 if (std::holds_alternative<IndexRange>(segment)) {
113 const IndexRange range = std::get<IndexRange>(segment);
114 parts.append(fmt::format("{}-{}", range.first(), range.last()));
115 }
116 else {
117 const Span<int64_t> segment_indices = std::get<Span<int64_t>>(segment);
118 parts.append(fmt::format("{}", fmt::join(segment_indices, ", ")));
119 }
120 }
121 stream << fmt::format("(Size: {} | {})", mask.size(), fmt::join(parts, ", "));
122 return stream;
123}
124
126{
127 if (size == 0) {
128 return {};
129 }
130 const RawMaskIterator first_it = this->index_to_iterator(start);
131 const RawMaskIterator last_it = this->index_to_iterator(start + size - 1);
132
133 IndexMask sliced = *this;
134 sliced.indices_num_ = size;
135 sliced.segments_num_ = last_it.segment_i - first_it.segment_i + 1;
136 sliced.indices_by_segment_ += first_it.segment_i;
137 sliced.segment_offsets_ += first_it.segment_i;
138 sliced.cumulative_segment_sizes_ += first_it.segment_i;
139 sliced.begin_index_in_segment_ = first_it.index_in_segment;
140 sliced.end_index_in_segment_ = last_it.index_in_segment + 1;
141 return sliced;
142}
143
145 const RawMaskIterator last_it,
146 const int64_t size) const
147{
148 BLI_assert(this->iterator_to_index(last_it) - this->iterator_to_index(first_it) + 1 == size);
149 IndexMask sliced = *this;
150 sliced.indices_num_ = size;
151 sliced.segments_num_ = last_it.segment_i - first_it.segment_i + 1;
152 sliced.indices_by_segment_ += first_it.segment_i;
153 sliced.segment_offsets_ += first_it.segment_i;
154 sliced.cumulative_segment_sizes_ += first_it.segment_i;
155 sliced.begin_index_in_segment_ = first_it.index_in_segment;
156 sliced.end_index_in_segment_ = last_it.index_in_segment + 1;
157 return sliced;
158}
159
161{
162 return this->slice_content(range.start(), range.size());
163}
164
166{
167 if (size <= 0) {
168 return {};
169 }
170 const std::optional<RawMaskIterator> first_it = this->find_larger_equal(start);
171 const std::optional<RawMaskIterator> last_it = this->find_smaller_equal(start + size - 1);
172 if (!first_it || !last_it) {
173 return {};
174 }
175 const int64_t first_index = this->iterator_to_index(*first_it);
176 const int64_t last_index = this->iterator_to_index(*last_it);
177 if (last_index < first_index) {
178 return {};
179 }
180 const int64_t sliced_mask_size = last_index - first_index + 1;
181 return this->slice(*first_it, *last_it, sliced_mask_size);
182}
183
185 const int64_t offset,
186 LinearAllocator<> &memory) const
187{
188 return this->slice_and_shift(range.start(), range.size(), offset, memory);
189}
190
192 const int64_t size,
193 const int64_t offset,
194 LinearAllocator<> &memory) const
195{
196 if (size == 0) {
197 return {};
198 }
199 if (std::optional<IndexRange> range = this->to_range()) {
200 return range->slice(start, size).shift(offset);
201 }
202 return this->slice(start, size).shift(offset, memory);
203}
204
206{
207 if (indices_num_ == 0) {
208 return {};
209 }
210 BLI_assert(this->first() + offset >= 0);
211 if (offset == 0) {
212 return *this;
213 }
214 if (std::optional<IndexRange> range = this->to_range()) {
215 return range->shift(offset);
216 }
217 IndexMask shifted_mask = *this;
218 MutableSpan<int64_t> new_segment_offsets = memory.allocate_array<int64_t>(segments_num_);
219 for (const int64_t i : IndexRange(segments_num_)) {
220 new_segment_offsets[i] = segment_offsets_[i] + offset;
221 }
222 shifted_mask.segment_offsets_ = new_segment_offsets.data();
223 return shifted_mask;
224}
225
227 LinearAllocator<> & /*memory*/)
228{
229 if (segments.is_empty()) {
230 return 0;
231 }
232
233 const Span<int16_t> static_indices = get_static_indices_array();
234
235 /* TODO: Support merging non-range segments in some cases as well. */
236 int64_t group_start_segment_i = 0;
237 int64_t group_first = segments[0][0];
238 int64_t group_last = segments[0].last();
239 bool group_as_range = unique_sorted_indices::non_empty_is_range(segments[0].base_span());
240
241 auto finish_group = [&](const int64_t last_segment_i) {
242 if (group_start_segment_i == last_segment_i) {
243 return;
244 }
245 /* Join multiple ranges together into a bigger range. */
246 const IndexRange range = IndexRange::from_begin_end_inclusive(group_first, group_last);
247 segments[group_start_segment_i] = IndexMaskSegment(range[0],
248 static_indices.take_front(range.size()));
249 for (int64_t i = group_start_segment_i + 1; i <= last_segment_i; i++) {
250 segments[i] = {};
251 }
252 };
253
254 for (const int64_t segment_i : segments.index_range().drop_front(1)) {
255 const IndexMaskSegment segment = segments[segment_i];
256 const std::optional<IndexRange> segment_base_range =
258 const bool segment_is_range = segment_base_range.has_value();
259
260 if (group_as_range && segment_is_range) {
261 if (group_last + 1 == segment[0]) {
262 if (segment.last() - group_first + 1 < max_segment_size) {
263 /* Can combine previous and current range. */
264 group_last = segment.last();
265 continue;
266 }
267 }
268 }
269 finish_group(segment_i - 1);
270
271 group_start_segment_i = segment_i;
272 group_first = segment[0];
273 group_last = segment.last();
274 group_as_range = segment_is_range;
275 }
276 finish_group(segments.size() - 1);
277
278 /* Remove all segments that have been merged into previous segments. */
279 const int64_t new_segments_num = std::remove_if(segments.begin(),
280 segments.end(),
281 [](const IndexMaskSegment segment) {
282 return segment.is_empty();
283 }) -
284 segments.begin();
285 return new_segments_num;
286}
287
289 LinearAllocator<> &memory)
290{
291 if (segments.is_empty()) {
292 return {};
293 }
294#ifndef NDEBUG
295 {
296 int64_t last_index = segments[0].last();
297 for (const IndexMaskSegment &segment : segments.drop_front(1)) {
298 BLI_assert(std::is_sorted(segment.base_span().begin(), segment.base_span().end()));
299 BLI_assert(last_index < segment[0]);
300 last_index = segment.last();
301 }
302 }
303#endif
304 const int64_t segments_num = segments.size();
305
306 /* Allocate buffers for the mask. */
307 MutableSpan<const int16_t *> indices_by_segment = memory.allocate_array<const int16_t *>(
309 MutableSpan<int64_t> segment_offsets = memory.allocate_array<int64_t>(segments_num);
310 MutableSpan<int64_t> cumulative_segment_sizes = memory.allocate_array<int64_t>(segments_num + 1);
311
312 /* Fill buffers. */
313 cumulative_segment_sizes[0] = 0;
314 for (const int64_t segment_i : segments.index_range()) {
315 const IndexMaskSegment segment = segments[segment_i];
316 indices_by_segment[segment_i] = segment.base_span().data();
317 segment_offsets[segment_i] = segment.offset();
318 cumulative_segment_sizes[segment_i + 1] = cumulative_segment_sizes[segment_i] + segment.size();
319 }
320
321 /* Initialize mask. */
323 IndexMaskData &data = mask.data_for_inplace_construction();
324 data.indices_num_ = cumulative_segment_sizes.last();
325 data.segments_num_ = segments_num;
326 data.indices_by_segment_ = indices_by_segment.data();
327 data.segment_offsets_ = segment_offsets.data();
328 data.cumulative_segment_sizes_ = cumulative_segment_sizes.data();
329 data.begin_index_in_segment_ = 0;
330 data.end_index_in_segment_ = segments.last().size();
331 return mask;
332}
333
338template<typename T, int64_t InlineBufferSize>
339static void segments_from_indices(const Span<T> indices,
340 LinearAllocator<> &allocator,
342{
344
345 for (int64_t start = 0; start < indices.size(); start += max_segment_size) {
346 /* Slice to make sure that each segment is no longer than #max_segment_size. */
347 const Span<T> indices_slice = indices.slice_safe(start, max_segment_size);
348 unique_sorted_indices::split_to_ranges_and_spans<T>(indices_slice, 64, segments);
349 }
350
351 const Span<int16_t> static_indices = get_static_indices_array();
352 for (const auto &segment : segments) {
353 if (std::holds_alternative<IndexRange>(segment)) {
354 const IndexRange segment_range = std::get<IndexRange>(segment);
355 r_segments.append_as(segment_range.start(), static_indices.take_front(segment_range.size()));
356 }
357 else {
358 Span<T> segment_indices = std::get<Span<T>>(segment);
360 segment_indices.size());
361 while (!segment_indices.is_empty()) {
362 const int64_t offset = segment_indices[0];
363 const int64_t next_segment_size = binary_search::first_if(
364 segment_indices.take_front(max_segment_size),
365 [&](const T value) { return value - offset >= max_segment_size; });
366 for (const int64_t i : IndexRange(next_segment_size)) {
367 const int64_t offset_index = segment_indices[i] - offset;
368 BLI_assert(offset_index < max_segment_size);
369 offset_indices[i] = int16_t(offset_index);
370 }
371 r_segments.append_as(offset, offset_indices.take_front(next_segment_size));
372 segment_indices = segment_indices.drop_front(next_segment_size);
373 offset_indices = offset_indices.drop_front(next_segment_size);
374 }
375 }
376 }
377}
378
387
389
395 void reduce(LinearAllocator<> &main_allocator, Vector<IndexMaskSegment, 16> &main_segments)
396 {
397 for (LocalData &data : this->data_by_thread) {
398 main_allocator.transfer_ownership_from(data.allocator);
399 main_segments.extend(data.segments);
400 }
401 parallel_sort(main_segments.begin(),
402 main_segments.end(),
403 [](const IndexMaskSegment a, const IndexMaskSegment b) { return a[0] < b[0]; });
404 }
405};
406
408{
409 ExprBuilder builder;
410 const Expr &expr = builder.subtract(&universe, {this});
411 return evaluate_expression(expr, memory);
412}
413
414template<typename T>
416{
417 if (indices.is_empty()) {
418 return {};
419 }
420 if (const std::optional<IndexRange> range = unique_sorted_indices::non_empty_as_range_try(
421 indices))
422 {
423 /* Fast case when the indices encode a single range. */
424 return *range;
425 }
426
428
429 constexpr int64_t min_grain_size = 4096;
430 constexpr int64_t max_grain_size = max_segment_size;
431 if (indices.size() <= min_grain_size) {
432 segments_from_indices(indices, memory, segments);
433 }
434 else {
435 const int64_t threads_num = BLI_system_thread_count();
436 /* Can be faster with a larger grain size, but only when there are enough indices. */
437 const int64_t grain_size = std::clamp(
438 indices.size() / (threads_num * 4), min_grain_size, max_grain_size);
439
440 ParallelSegmentsCollector segments_collector;
441 threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
442 ParallelSegmentsCollector::LocalData &local_data = segments_collector.data_by_thread.local();
443 segments_from_indices(indices.slice(range), local_data.allocator, local_data.segments);
444 });
445 segments_collector.reduce(memory, segments);
446 }
447 const int64_t consolidated_segments_num = consolidate_index_mask_segments(segments, memory);
448 segments.resize(consolidated_segments_num);
449 return IndexMask::from_segments(segments, memory);
450}
451
453{
454 return IndexMask::from_bits(bits.index_range(), bits, memory);
455}
456
459 const BitSpan bits_slice)
460{
461 const int64_t segment_start = universe_segment[0];
463 bits::bits_to_index_ranges<int16_t>(bits_slice, builder);
464 }
465 else {
466 /* If the universe is not a range, we need to create a new bit span first. In it, bits
467 * that are not part of the universe are set to 0. */
468 const int64_t segment_end = universe_segment.last() + 1;
469 BitVector<max_segment_size> local_bits(segment_end - segment_start, false);
470 for (const int64_t i : universe_segment.index_range()) {
471 const int64_t global_index = universe_segment[i];
472 const int64_t local_index = global_index - segment_start;
473 BLI_assert(local_index < max_segment_size);
474 /* It's not great to handle each index separately instead of working with bigger
475 * chunks, but that works well enough for now. */
476 if (bits_slice[local_index]) {
477 local_bits[local_index].set();
478 }
479 }
480 bits::bits_to_index_ranges<int16_t>(local_bits, builder);
481 }
482 return segment_start;
483}
484
486 const BitSpan bits,
487 LinearAllocator<> &memory)
488{
489 BLI_assert(bits.size() >= universe.min_array_size());
490 /* Use #from_batch_predicate because we can process many bits at once. */
492 universe,
493 memory,
494 [&](const IndexMaskSegment universe_segment, IndexRangesBuilder<int16_t> &builder) {
495 const IndexRange slice = IndexRange::from_begin_end_inclusive(universe_segment[0],
496 universe_segment.last());
497 return from_bits_batch_predicate(universe_segment, builder, bits.slice(slice));
498 },
499 exec_mode::grain_size(max_segment_size));
500}
501
503 const IndexMaskSegment universe_segment,
504 LinearAllocator<> &allocator,
505 const FunctionRef<int64_t(const IndexMaskSegment &universe_segment,
506 IndexRangesBuilder<int16_t> &builder)> batch_predicate,
508{
510 IndexRangesBuilder<int16_t> builder{builder_buffer};
511 const int64_t segment_shift = batch_predicate(universe_segment, builder);
512 if (builder.is_empty()) {
513 return;
514 }
515 const Span<int16_t> static_indices = get_static_indices_array();
516
517 /* This threshold trades off the number of segments and the number of ranges. In some cases,
518 * masks with fewer segments can be build more efficiently, but when iterating over a mask it may
519 * be beneficial to have more ranges if that means that there are more ranges which can be
520 * processed more efficiently. This could be exposed to the caller in the future. */
521 constexpr int64_t threshold = 64;
522 int64_t next_range_to_process = 0;
523 int64_t skipped_indices_num = 0;
524
525 /* Builds an index mask segment from a bunch of smaller ranges (which could be individual
526 * indices). */
527 auto consolidate_skipped_ranges = [&](int64_t end_range_i) {
528 if (skipped_indices_num == 0) {
529 return;
530 }
531 MutableSpan<int16_t> indices = allocator.allocate_array<int16_t>(skipped_indices_num);
532 int64_t counter = 0;
533 for (const int64_t i : IndexRange::from_begin_end(next_range_to_process, end_range_i)) {
534 const IndexRange range = builder[i];
535 array_utils::fill_index_range(indices.slice(counter, range.size()), int16_t(range.first()));
536 counter += range.size();
537 }
538 r_segments.append(IndexMaskSegment{segment_shift, indices});
539 };
540
541 for (const int64_t i : builder.index_range()) {
542 const IndexRange range = builder[i];
543 if (range.size() > threshold || builder.size() == 1) {
544 consolidate_skipped_ranges(i);
545 r_segments.append(IndexMaskSegment{segment_shift, static_indices.slice(range)});
546 next_range_to_process = i + 1;
547 skipped_indices_num = 0;
548 }
549 else {
550 skipped_indices_num += range.size();
551 }
552 }
553 consolidate_skipped_ranges(builder.size());
554}
555
557 const IndexMask &universe,
558 LinearAllocator<> &memory,
559 const FunctionRef<int64_t(const IndexMaskSegment &universe_segment,
560 IndexRangesBuilder<int16_t> &builder)> batch_predicate,
561 const exec_mode::Mode mode)
562{
563 if (universe.is_empty()) {
564 return {};
565 }
566
568 constexpr int fallback_grain_size = 4096;
569 /* Avoid ParallelSegmentsCollector overhead when universe is small relative to task size. */
570 if (!mode.is_parallel ||
571 universe.size() <= mode.grain_size_override.value_or(fallback_grain_size))
572 {
573 for (const int64_t segment_i : IndexRange(universe.segments_num())) {
574 const IndexMaskSegment universe_segment = universe.segment(segment_i);
575 segments_from_batch_predicate(universe_segment, memory, batch_predicate, segments);
576 }
577 }
578 else {
579 ParallelSegmentsCollector segments_collector;
580 universe.foreach_segment(
581 [&](const IndexMaskSegment universe_segment) {
584 universe_segment, data.allocator, batch_predicate, data.segments);
585 },
586 exec_mode::grain_size(mode.grain_size(fallback_grain_size)));
587 segments_collector.reduce(memory, segments);
588 }
589
590 return IndexMask::from_segments(segments, memory);
591}
592
594{
595 return IndexMask::from_bools(bools.index_range(), bools, memory);
596}
597
599{
600 return IndexMask::from_bools(bools.index_range(), bools, memory);
601}
602
604{
605 return IndexMask::from_bools_inverse(bools.index_range(), bools, memory);
606}
607
609{
610 return IndexMask::from_bools_inverse(bools.index_range(), bools, memory);
611}
612
614 Span<bool> bools,
615 LinearAllocator<> &memory)
616{
617 BLI_assert(bools.size() >= universe.min_array_size());
619 universe,
620 memory,
621 [&](const IndexMaskSegment universe_segment,
623 const IndexRange slice = IndexRange::from_begin_end_inclusive(universe_segment[0],
624 universe_segment.last());
625 /* +16 to allow for some overshoot when converting bools to bits. */
627 bits.resize(slice.size(), false);
628 const int64_t allowed_overshoot = std::min<int64_t>(bits.capacity() - slice.size(),
629 bools.size() - slice.one_after_last());
630 const bool any_true = bits::or_bools_into_bits(
631 bools.slice(slice), bits, allowed_overshoot);
632 if (!any_true) {
633 return 0;
634 }
635 return from_bits_batch_predicate(universe_segment, builder, bits);
636 },
637 exec_mode::grain_size(max_segment_size));
638}
639
641 Span<bool> bools,
642 LinearAllocator<> &memory)
643{
644 BitVector bits(bools);
646 return IndexMask::from_bits(universe, bits, memory);
647}
648
650 const VArray<bool> &bools,
651 LinearAllocator<> &memory)
652{
653 const CommonVArrayInfo info = bools.common_info();
655 return *static_cast<const bool *>(info.data) ? universe : IndexMask();
656 }
658 const Span<bool> span(static_cast<const bool *>(info.data), bools.size());
659 return IndexMask::from_bools(universe, span, memory);
660 }
662 universe,
663 memory,
664 [&](const int64_t index) { return bools[index]; },
666}
667
669 const VArray<bool> &bools,
670 LinearAllocator<> &memory)
671{
672 const CommonVArrayInfo info = bools.common_info();
674 return *static_cast<const bool *>(info.data) ? IndexMask() : universe;
675 }
677 const Span<bool> span(static_cast<const bool *>(info.data), bools.size());
678 return IndexMask::from_bools_inverse(universe, span, memory);
679 }
681 universe,
682 memory,
683 [&](const int64_t index) { return !bools[index]; },
685}
686
687template<typename T>
689 const IndexMask &mask,
690 LinearAllocator<> &memory)
691{
693 mask.foreach_range([&](const IndexRange mask_range) {
694 const IndexRange range = offsets[mask_range];
695 index_range_to_mask_segments(range, segments);
696 });
697 return IndexMask::from_segments(segments, memory);
698}
699
701 const IndexMask &mask_b,
702 LinearAllocator<> &memory)
703{
704 return IndexMask::from_union({mask_a, mask_b}, memory);
705}
706
708{
709 ExprBuilder builder;
711 for (const IndexMask &mask : masks) {
712 terms.append(&mask);
713 }
714 const Expr &expr = builder.merge(terms);
715 return evaluate_expression(expr, memory);
716}
717
719 const IndexMask &mask_b,
720 LinearAllocator<> &memory)
721{
722 ExprBuilder builder;
723 const Expr &expr = builder.subtract({&mask_a}, {&mask_b});
724 return evaluate_expression(expr, memory);
725}
726
728 const IndexMask &mask_b,
729 LinearAllocator<> &memory)
730{
731 ExprBuilder builder;
732 const Expr &expr = builder.intersect({&mask_a, &mask_b});
733 return evaluate_expression(expr, memory);
734}
735
737 LinearAllocator<> &memory)
738{
739 Set<int64_t> values;
740 for (const Initializer &item : initializers) {
741 if (const auto *range = std::get_if<IndexRange>(&item)) {
742 for (const int64_t i : *range) {
743 values.add(i);
744 }
745 }
746 else if (const auto *span_i64 = std::get_if<Span<int64_t>>(&item)) {
747 for (const int64_t i : *span_i64) {
748 values.add(i);
749 }
750 }
751 else if (const auto *span_i32 = std::get_if<Span<int>>(&item)) {
752 for (const int i : *span_i32) {
753 values.add(i);
754 }
755 }
756 else if (const auto *index = std::get_if<int64_t>(&item)) {
757 values.add(*index);
758 }
759 }
760 Vector<int64_t> values_vec;
761 values_vec.extend(values.begin(), values.end());
762 std::ranges::sort(values_vec);
763 return IndexMask::from_indices(values_vec.as_span(), memory);
764}
765
766template<typename T> void IndexMask::to_indices(MutableSpan<T> r_indices) const
767{
768 BLI_assert(this->size() == r_indices.size());
770 [r_indices = r_indices.data()](const int64_t i, const int64_t pos) {
771 r_indices[pos] = T(i);
772 },
774}
775
776void IndexMask::set_bits(MutableBitSpan r_bits, const int64_t offset) const
777{
778 BLI_assert(r_bits.size() >= this->min_array_size() + offset);
779 this->foreach_segment_optimized([&](const auto segment) {
780 if constexpr (std::is_same_v<std::decay_t<decltype(segment)>, IndexRange>) {
781 const IndexRange range = segment;
782 const IndexRange shifted_range = range.shift(offset);
783 r_bits.slice(shifted_range).set_all();
784 }
785 else {
786 const IndexMaskSegment indices = segment;
787 const IndexMaskSegment shifted_indices = indices.shift(offset);
788 for (const int64_t i : shifted_indices) {
789 r_bits[i].set();
790 }
791 }
792 });
793}
794
795void IndexMask::to_bits(MutableBitSpan r_bits, const int64_t offset) const
796{
797 BLI_assert(r_bits.size() >= this->min_array_size() + offset);
798 r_bits.reset_all();
799 this->set_bits(r_bits, offset);
800}
801
803{
804 BLI_assert(r_bools.size() >= this->min_array_size());
805 r_bools.fill(false);
806 index_mask::masked_fill(r_bools, true, *this);
807}
808
810{
811 Vector<IndexRange> ranges;
812 this->foreach_range([&](const IndexRange range) { ranges.append(range); });
813 return ranges;
814}
815
817{
818 IndexMaskMemory memory;
819 return this->complement(universe, memory).to_ranges();
820}
821
822namespace detail {
823
829 const IndexMaskSegment universe_segment,
830 LinearAllocator<> &allocator,
831 const FunctionRef<int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices,
833{
834 std::array<int16_t, max_segment_size> indices_array;
835 const int64_t true_indices_num = filter_indices(universe_segment, indices_array.data());
836 if (true_indices_num == 0) {
837 return;
838 }
839 const Span<int16_t> true_indices{indices_array.data(), true_indices_num};
841 unique_sorted_indices::split_to_ranges_and_spans<int16_t>(true_indices, 64, true_segments);
842
843 const Span<int16_t> static_indices = get_static_indices_array();
844
845 for (const auto &true_segment : true_segments) {
846 if (std::holds_alternative<IndexRange>(true_segment)) {
847 const IndexRange segment_range = std::get<IndexRange>(true_segment);
848 r_segments.append_as(universe_segment.offset(), static_indices.slice(segment_range));
849 }
850 else {
851 const Span<int16_t> segment_indices = std::get<Span<int16_t>>(true_segment);
852 r_segments.append_as(universe_segment.offset(),
853 allocator.construct_array_copy(segment_indices));
854 }
855 }
856}
857
859 const IndexMask &universe,
860 LinearAllocator<> &memory,
861 const FunctionRef<int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices,
862 const exec_mode::Mode mode)
863{
864 if (universe.is_empty()) {
865 return {};
866 }
867
869 constexpr int fallback_grain_size = 4096;
870 /* Avoid ParallelSegmentsCollector overhead when universe is small relative to task size. */
871 if (!mode.is_parallel &&
872 universe.size() <= mode.grain_size_override.value_or(fallback_grain_size))
873 {
874 for (const int64_t segment_i : IndexRange(universe.segments_num())) {
875 const IndexMaskSegment universe_segment = universe.segment(segment_i);
876 segments_from_predicate_filter(universe_segment, memory, filter_indices, segments);
877 }
878 }
879 else {
880 ParallelSegmentsCollector segments_collector;
881 universe.foreach_segment(
882 [&](const IndexMaskSegment universe_segment) {
885 universe_segment, data.allocator, filter_indices, data.segments);
886 },
887 exec_mode::grain_size(mode.grain_size(fallback_grain_size)));
888 segments_collector.reduce(memory, segments);
889 }
890
891 const int64_t consolidated_segments_num = consolidate_index_mask_segments(segments, memory);
892 segments.resize(consolidated_segments_num);
893 return IndexMask::from_segments(segments, memory);
894}
895} // namespace detail
896
897std::optional<RawMaskIterator> IndexMask::find(const int64_t query_index) const
898{
899 if (const std::optional<RawMaskIterator> it = this->find_larger_equal(query_index)) {
900 if ((*this)[*it] == query_index) {
901 return it;
902 }
903 }
904 return std::nullopt;
905}
906
907std::optional<RawMaskIterator> IndexMask::find_larger_equal(const int64_t query_index) const
908{
909 const int64_t segment_i = binary_search::first_if(
911 [&](const int64_t seg_i) { return this->segment(seg_i).last() >= query_index; });
912 if (segment_i == segments_num_) {
913 /* The query index is larger than the largest index in this mask. */
914 return std::nullopt;
915 }
916 const IndexMaskSegment segment = this->segment(segment_i);
917 const int64_t segment_begin_index = segment.base_span().data() - indices_by_segment_[segment_i];
918 if (query_index < segment[0]) {
919 /* The query index is the first element in this segment. */
920 const int64_t index_in_segment = segment_begin_index;
921 BLI_assert(index_in_segment < max_segment_size);
922 return RawMaskIterator{segment_i, int16_t(index_in_segment)};
923 }
924 /* The query index is somewhere within this segment. */
925 const int64_t local_index = query_index - segment.offset();
926 const int64_t index_in_segment = binary_search::first_if(
927 segment.base_span(), [&](const int16_t i) { return i >= local_index; });
928 const int64_t actual_index_in_segment = index_in_segment + segment_begin_index;
929 BLI_assert(actual_index_in_segment < max_segment_size);
930 return RawMaskIterator{segment_i, int16_t(actual_index_in_segment)};
931}
932
933std::optional<RawMaskIterator> IndexMask::find_smaller_equal(const int64_t query_index) const
934{
935 if (indices_num_ == 0) {
936 return std::nullopt;
937 }
938 const std::optional<RawMaskIterator> larger_equal_it = this->find_larger_equal(query_index);
939 if (!larger_equal_it) {
940 /* Return the last element. */
942 }
943 if ((*this)[*larger_equal_it] == query_index) {
944 /* This is an exact hit. */
945 return larger_equal_it;
946 }
947 if (larger_equal_it->segment_i > 0) {
948 if (larger_equal_it->index_in_segment > 0) {
949 /* Previous element in same segment. */
950 return RawMaskIterator{larger_equal_it->segment_i,
951 int16_t(larger_equal_it->index_in_segment - 1)};
952 }
953 /* Last element in previous segment. */
954 return RawMaskIterator{larger_equal_it->segment_i - 1,
955 int16_t(cumulative_segment_sizes_[larger_equal_it->segment_i] -
956 cumulative_segment_sizes_[larger_equal_it->segment_i - 1] - 1)};
957 }
958 if (larger_equal_it->index_in_segment > begin_index_in_segment_) {
959 /* Previous element in same segment. */
960 return RawMaskIterator{0, int16_t(larger_equal_it->index_in_segment - 1)};
961 }
962 return std::nullopt;
963}
964
965bool IndexMask::contains(const int64_t query_index) const
966{
967 return this->find(query_index).has_value();
968}
969
971{
972 Array<int16_t> data(max_segment_size / n);
973 for (const int64_t i : data.index_range()) {
974 const int64_t index = i * n;
975 BLI_assert(index < max_segment_size);
976 data[i] = int16_t(index);
977 }
978 return data;
979}
980
987 const int64_t repetitions,
988 LinearAllocator<> &memory)
989{
990 BLI_assert(n >= 2);
991 BLI_assert(n * repetitions <= max_segment_size);
992
993 switch (n) {
994 case 2: {
995 static auto data = build_every_nth_index_array(2);
996 return data.as_span().take_front(repetitions);
997 }
998 case 3: {
999 static auto data = build_every_nth_index_array(3);
1000 return data.as_span().take_front(repetitions);
1001 }
1002 case 4: {
1003 static auto data = build_every_nth_index_array(4);
1004 return data.as_span().take_front(repetitions);
1005 }
1006 default: {
1007 MutableSpan<int16_t> data = memory.allocate_array<int16_t>(repetitions);
1008 for (const int64_t i : IndexRange(repetitions)) {
1009 const int64_t index = i * n;
1010 BLI_assert(index < max_segment_size);
1011 data[i] = int16_t(index);
1012 }
1013 return data;
1014 }
1015 }
1016}
1017
1019 const int64_t repetitions,
1020 const int64_t stride,
1021 const int64_t initial_offset,
1022 LinearAllocator<> &memory)
1023{
1024 if (mask_to_repeat.is_empty()) {
1025 return {};
1026 }
1027 BLI_assert(mask_to_repeat.last() < stride);
1028 if (repetitions == 0) {
1029 return {};
1030 }
1031 if (repetitions == 1 && initial_offset == 0) {
1032 /* The output is the same as the input mask. */
1033 return mask_to_repeat;
1034 }
1035 const std::optional<IndexRange> range_to_repeat = mask_to_repeat.to_range();
1036 if (range_to_repeat && range_to_repeat->first() == 0 && range_to_repeat->size() == stride) {
1037 /* The output is a range. */
1038 return IndexRange(initial_offset, repetitions * stride);
1039 }
1040 const int64_t segments_num = mask_to_repeat.segments_num();
1041 const IndexRange bounds = mask_to_repeat.bounds();
1042
1043 /* Avoid having many very small segments by creating a single segment that contains the input
1044 * multiple times already. This way, a lower total number of segments is necessary. */
1045 if (segments_num == 1 && stride <= max_segment_size / 2 && mask_to_repeat.size() <= 256) {
1046 const IndexMaskSegment src_segment = mask_to_repeat.segment(0);
1047 /* Number of repetitions that fit into a single segment. */
1048 const int64_t inline_repetitions_num = std::min(repetitions, max_segment_size / stride);
1049 Span<int16_t> repeated_indices;
1050 if (src_segment.size() == 1) {
1051 /* Optimize the case when a single index is repeated. */
1052 repeated_indices = get_every_nth_index(stride, inline_repetitions_num, memory);
1053 }
1054 else {
1055 /* More general case that repeats multiple indices. */
1056 MutableSpan<int16_t> repeated_indices_mut = memory.allocate_array<int16_t>(
1057 inline_repetitions_num * src_segment.size());
1058 for (const int64_t repetition : IndexRange(inline_repetitions_num)) {
1059 for (const int64_t i : src_segment.index_range()) {
1060 const int64_t index = src_segment[i] - src_segment[0] + repetition * stride;
1061 BLI_assert(index < max_segment_size);
1062 repeated_indices_mut[repetition * src_segment.size() + i] = int16_t(index);
1063 }
1064 }
1065 repeated_indices = repeated_indices_mut;
1066 }
1067 BLI_assert(repeated_indices[0] == 0);
1068
1069 Vector<IndexMaskSegment, 16> repeated_segments;
1070 const int64_t result_segments_num = ceil_division(repetitions, inline_repetitions_num);
1071 for (const int64_t i : IndexRange(result_segments_num)) {
1072 const int64_t used_repetitions = std::min(inline_repetitions_num,
1073 repetitions - i * inline_repetitions_num);
1074 repeated_segments.append(
1075 IndexMaskSegment(initial_offset + bounds.first() + i * stride * inline_repetitions_num,
1076 repeated_indices.take_front(used_repetitions * src_segment.size())));
1077 }
1078 return IndexMask::from_segments(repeated_segments, memory);
1079 }
1080
1081 /* Simply repeat and offset the existing segments in the input mask. */
1082 Vector<IndexMaskSegment, 16> repeated_segments;
1083 for (const int64_t repetition : IndexRange(repetitions)) {
1084 for (const int64_t segment_i : IndexRange(segments_num)) {
1085 const IndexMaskSegment segment = mask_to_repeat.segment(segment_i);
1086 repeated_segments.append(IndexMaskSegment(
1087 segment.offset() + repetition * stride + initial_offset, segment.base_span()));
1088 }
1089 }
1090 return IndexMask::from_segments(repeated_segments, memory);
1091}
1092
1094 const int64_t indices_num,
1095 const int64_t initial_offset,
1096 LinearAllocator<> &memory)
1097{
1098 BLI_assert(n >= 1);
1099 return IndexMask::from_repeating(IndexRange(1), indices_num, n, initial_offset, memory);
1100}
1101
1103 const FunctionRef<bool(Span<IndexMaskSegment> segments)> fn)
1104{
1105 BLI_assert(!masks.is_empty());
1106 BLI_assert(std::all_of(masks.begin() + 1, masks.end(), [&](const IndexMask &maks) {
1107 return masks[0].size() == maks.size();
1108 }));
1109
1110 Array<int64_t, 8> segment_iter(masks.size(), 0);
1111 Array<int16_t, 8> start_iter(masks.size(), 0);
1112
1113 Array<IndexMaskSegment, 8> segments(masks.size());
1114 Array<IndexMaskSegment, 8> sequences(masks.size());
1115
1116 /* This function only take positions of indices in to account.
1117 * Masks with the same size is fragmented in positions space.
1118 * So, all last segments (index in mask does not matter) of all masks will be ended in the same
1119 * position. All segment iterators will be out of range at the same time. */
1120 while (segment_iter[0] != masks[0].segments_num()) {
1121 for (const int64_t mask_i : masks.index_range()) {
1122 if (start_iter[mask_i] == 0) {
1123 segments[mask_i] = masks[mask_i].segment(segment_iter[mask_i]);
1124 }
1125 }
1126
1127 int16_t next_common_sequence_size = std::numeric_limits<int16_t>::max();
1128 for (const int64_t mask_i : masks.index_range()) {
1129 next_common_sequence_size = math::min(next_common_sequence_size,
1130 int16_t(segments[mask_i].size() - start_iter[mask_i]));
1131 }
1132
1133 for (const int64_t mask_i : masks.index_range()) {
1134 sequences[mask_i] = segments[mask_i].slice(start_iter[mask_i], next_common_sequence_size);
1135 }
1136
1137 if (!fn(sequences)) {
1138 break;
1139 }
1140
1141 for (const int64_t mask_i : masks.index_range()) {
1142 if (segments[mask_i].size() - start_iter[mask_i] == next_common_sequence_size) {
1143 segment_iter[mask_i]++;
1144 start_iter[mask_i] = 0;
1145 }
1146 else {
1147 start_iter[mask_i] += next_common_sequence_size;
1148 }
1149 }
1150 }
1151}
1152
1154{
1155 if (a.size() != b.size()) {
1156 return false;
1157 }
1158 if (a.is_empty()) {
1159 /* Both segments are empty. */
1160 return true;
1161 }
1162 if (a[0] != b[0]) {
1163 return false;
1164 }
1165
1166 const bool a_is_range = unique_sorted_indices::non_empty_is_range(a.base_span());
1167 const bool b_is_range = unique_sorted_indices::non_empty_is_range(b.base_span());
1168 if (a_is_range || b_is_range) {
1169 return a_is_range && b_is_range;
1170 }
1171
1172 const Span<int16_t> a_indices = a.base_span();
1173 [[maybe_unused]] const Span<int16_t> b_indices = b.base_span();
1174
1175 const int64_t offset_difference = int16_t(b.offset() - a.offset());
1176
1177 BLI_assert(a_indices[0] >= 0 && b_indices[0] >= 0);
1178 BLI_assert(b_indices[0] == a_indices[0] - offset_difference);
1179
1180 return std::equal(a_indices.begin(),
1181 a_indices.end(),
1182 b.base_span().begin(),
1183 [offset_difference](const int16_t a_index, const int16_t b_index) -> bool {
1184 return a_index - offset_difference == b_index;
1185 });
1186}
1187
1188bool operator==(const IndexMask &a, const IndexMask &b)
1189{
1190 if (a.size() != b.size()) {
1191 return false;
1192 }
1193
1194 const std::optional<IndexRange> a_as_range = a.to_range();
1195 const std::optional<IndexRange> b_as_range = b.to_range();
1196 if (a_as_range.has_value() || b_as_range.has_value()) {
1197 return a_as_range == b_as_range;
1198 }
1199
1200 bool equals = true;
1202 equals &= segments_is_equal(segments[0], segments[1]);
1203 return equals;
1204 });
1205
1206 return equals;
1207}
1208
1210 const VArray<int> &group_ids,
1211 LinearAllocator<> &memory)
1212{
1213 BLI_assert(group_ids.size() >= universe.min_array_size());
1214 if (universe.is_empty()) {
1215 return {};
1216 }
1217 if (group_ids.is_single()) {
1218 /* Optimize for the case when all group ids are the same. */
1219 return {universe};
1220 }
1221
1222 const VArraySpan<int> group_ids_span{group_ids};
1223 Array<int> group_indices(universe.size());
1224 const int groups_num = array_utils::group_ids_to_indices(
1225 group_ids_span, universe, group_indices);
1226
1227 Array<int> offset_data;
1228 Array<int> index_data;
1230 group_indices, groups_num, offset_data, index_data, universe);
1231
1232 /* Create the masks in parallel, with a separate allocator for each thread. */
1233 Vector<IndexMask, 4> result_masks(groups_num);
1236 result_masks.index_range(),
1237 256,
1238 [&](const IndexRange range) {
1239 LinearAllocator<> &allocator = allocators.local();
1240 for (const int64_t group : range) {
1241 result_masks[group] = IndexMask::from_indices(indices_by_group[group], allocator);
1242 }
1243 },
1245 [&](const IndexRange range) { return indices_by_group.offsets[range].size(); }));
1246 for (LinearAllocator<> &allocator : allocators) {
1247 memory.transfer_ownership_from(allocator);
1248 }
1249 return result_masks;
1250}
1251
1253 LinearAllocator<> &memory)
1254{
1255 return IndexMask::from_group_ids(IndexMask(group_ids.size()), group_ids, memory);
1256}
1257
1260template void IndexMask::to_indices(MutableSpan<int32_t>) const;
1261template void IndexMask::to_indices(MutableSpan<int64_t>) const;
1263 const IndexMask &,
1266 const IndexMask &,
1268
1270 const int64_t universe_size,
1271 const uint32_t random_seed,
1272 const float probability,
1273 LinearAllocator<> &memory)
1274{
1275 RandomNumberGenerator rng{random_seed};
1276 const auto next_bool_random_value = [&]() { return rng.get_float() <= probability; };
1277
1278 Array<bool> random(universe_size, false);
1279 mask.foreach_index_optimized<int64_t>(
1280 [&](const int64_t i) { random[i] = next_bool_random_value(); });
1281
1282 return IndexMask::from_bools(IndexRange(universe_size), random, memory);
1283}
1284
1285IndexMask random_mask(const int64_t universe_size,
1286 const uint32_t random_seed,
1287 const float probability,
1288 LinearAllocator<> &memory)
1289{
1290 const IndexRange selection(universe_size);
1291 return random_mask(selection, universe_size, random_seed, probability, memory);
1292}
1293
1294} // namespace blender::index_mask
#define UNUSED_VARS_NDEBUG(...)
const T & last(const int64_t n=0) const
Definition BLI_array.hh:307
const T * data() const
Definition BLI_array.hh:323
static Vector< IndexMask, 4 > from_group_ids(const VArray< int > &group_ids, LinearAllocator<> &memory)
constexpr int64_t first() const
constexpr int64_t one_after_last() const
constexpr IndexRange shift(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange()=default
constexpr int64_t start() const
static constexpr IndexRange from_begin_end_inclusive(const int64_t begin, const int64_t last)
constexpr IndexRange drop_front(int64_t n) const
MutableSpan< T > allocate_array(int64_t size)
MutableSpan< T > construct_array_copy(Span< T > src)
void transfer_ownership_from(LinearAllocator<> &other)
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr bool is_empty() const
Definition BLI_span.hh:515
constexpr T * data() const
Definition BLI_span.hh:545
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr T * end() const
Definition BLI_span.hh:554
constexpr T * begin() const
Definition BLI_span.hh:550
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
int64_t size() const
IndexRange index_range() const
T last(const int64_t n=0) const
Span< BaseT > base_span() const
Iterator begin() const
Definition BLI_set.hh:499
Iterator end() const
Definition BLI_set.hh:509
bool add(const Key &key)
Definition BLI_set.hh:248
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
constexpr Span slice_safe(const int64_t start, const int64_t size) const
Definition BLI_span.hh:158
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T & last(const int64_t n=0) const
Definition BLI_span.hh:329
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
constexpr bool is_empty() const
Definition BLI_span.hh:264
IndexRange index_range() const
CommonVArrayInfo common_info() const
void append(const T &value)
IndexRange index_range() const
void resize(const int64_t new_size)
void extend(Span< T > array)
Span< T > as_span() const
void append_as(ForwardValue &&...value)
MutableBitSpan slice(const IndexRange range) const
const IntersectionExpr & intersect(const Span< Term > terms)
const UnionExpr & merge(const Span< Term > terms)
const DifferenceExpr & subtract(const Term &main_term, const Span< Term > subtract_terms)
IndexMaskSegment shift(const int64_t shift) const
IndexMaskSegment(const OffsetSpan< int64_t, int16_t > span)
static IndexMask from_segments(Span< IndexMaskSegment > segments, LinearAllocator<> &memory)
void foreach_range(ForeachRangeFn auto &&fn) const
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMaskSegment segment(int64_t segment_i) const
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
IndexMask slice_content(IndexRange range) const
Vector< IndexRange > to_ranges_invert(IndexRange universe) const
Vector< IndexRange > to_ranges() const
std::optional< RawMaskIterator > find(int64_t query_index) const
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
std::optional< IndexRange > to_range() const
IndexMask shift(const int64_t offset, LinearAllocator<> &memory) const
static IndexMask from_difference(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static IndexMask from_ranges(OffsetIndices< T > offsets, const IndexMask &mask, LinearAllocator<> &memory)
std::optional< RawMaskIterator > find_larger_equal(int64_t query_index) const
IndexMask slice(IndexRange range) const
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
int64_t iterator_to_index(const RawMaskIterator &it) const
static IndexMask from_union(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static IndexMask from_repeating(const IndexMask &mask_to_repeat, int64_t repetitions, int64_t stride, int64_t initial_offset, LinearAllocator<> &memory)
void foreach_segment_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
void set_bits(MutableBitSpan r_bits, int64_t offset=0) const
static IndexMask from_bits(BitSpan bits, LinearAllocator<> &memory)
std::optional< RawMaskIterator > find_smaller_equal(int64_t query_index) const
bool contains(int64_t query_index) const
static IndexMask from_bools_inverse(Span< bool > bools, LinearAllocator<> &memory)
void to_bits(MutableBitSpan r_bits, int64_t offset=0) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
static IndexMask from_batch_predicate(const IndexMask &universe, LinearAllocator<> &memory, FunctionRef< int64_t(const IndexMaskSegment &universe_segment, IndexRangesBuilder< int16_t > &builder)> batch_predicate, exec_mode::Mode mode=exec_mode::parallel)
friend bool operator==(const IndexMask &a, const IndexMask &b)
static IndexMask from_every_nth(int64_t n, int64_t indices_num, const int64_t initial_offset, LinearAllocator<> &memory)
void to_bools(MutableSpan< bool > r_bools) const
static IndexMask from_initializers(const Span< Initializer > initializers, LinearAllocator<> &memory)
RawMaskIterator index_to_iterator(int64_t index) const
static void foreach_segment_zipped(Span< IndexMask > masks, FunctionRef< bool(Span< IndexMaskSegment > segments)> fn)
std::variant< IndexRange, Span< int64_t >, Span< int >, int64_t > Initializer
IndexMask slice_and_shift(IndexRange range, int64_t offset, LinearAllocator<> &memory) const
static IndexMask from_intersection(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static Vector< IndexMask, 4 > from_group_ids(const VArray< int > &group_ids, LinearAllocator<> &memory)
#define T
void fill_index_range(MutableSpan< T > span, const T start=0)
int group_ids_to_indices(Span< int > ids, const IndexMask &mask, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices=nullptr)
int64_t first_if(const Range &range, Predicate &&predicate)
bool or_bools_into_bits(Span< bool > bools, MutableBitSpan r_bits, int64_t allowed_overshoot=0)
void bits_to_index_ranges(const BitSpan bits, IndexRangesBuilder< IntT > &builder)
void invert(BitSpanT &&data)
constexpr ParallelGrainSize grain_size(int grain_size)
static void segments_from_predicate_filter(const IndexMaskSegment universe_segment, LinearAllocator<> &allocator, const FunctionRef< int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices, Vector< IndexMaskSegment, 16 > &r_segments)
IndexMask from_predicate_impl(const IndexMask &universe, LinearAllocator<> &memory, FunctionRef< int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices, exec_mode::Mode mode)
IndexMask evaluate_expression(const Expr &expression, LinearAllocator<> &memory)
IndexMask random_mask(const IndexMask &mask, const int64_t universe_size, const uint32_t random_seed, const float probability, LinearAllocator<> &memory)
static Span< int16_t > get_every_nth_index(const int64_t n, const int64_t repetitions, LinearAllocator<> &memory)
void index_range_to_mask_segments(const IndexRange range, Vector< IndexMaskSegment, N > &r_segments)
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 void segments_from_indices(const Span< T > indices, LinearAllocator<> &allocator, Vector< IndexMaskSegment, InlineBufferSize > &r_segments)
void build_reverse_map(const IndexMask &mask, MutableSpan< T > r_map)
Definition index_mask.cc:36
std::ostream & operator<<(std::ostream &stream, const IndexMask &mask)
std::array< int16_t, max_segment_size > build_static_indices_array()
Definition index_mask.cc:49
static Array< int16_t > build_every_nth_index_array(const int64_t n)
static int64_t from_bits_batch_predicate(const IndexMaskSegment universe_segment, IndexRangesBuilder< int16_t > &builder, const BitSpan bits_slice)
const IndexMask & get_static_index_mask_for_min_size(const int64_t min_size)
Definition index_mask.cc:58
static bool segments_is_equal(const IndexMaskSegment &a, const IndexMaskSegment &b)
int64_t consolidate_index_mask_segments(MutableSpan< IndexMaskSegment > segments, LinearAllocator<> &memory)
const std::array< int16_t, max_segment_size > & get_static_indices_array()
void masked_fill(MutableSpan< T > data, const T &value, const IndexMask &mask)
T min(const T &a, const T &b)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
auto accumulated_task_sizes(Fn &&fn)
auto isolate_task(const Function &function)
Definition BLI_task.hh:224
std::optional< IndexRange > non_empty_as_range_try(const Span< T > indices)
int64_t split_to_ranges_and_spans(const Span< T > indices, const int64_t range_threshold, Vector< std::variant< IndexRange, Span< T > >, InlineBufferSize > &r_segments)
bool non_empty_is_range(const Span< T > indices)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
Definition BLI_sort.hh:37
int BLI_system_thread_count()
Definition threads.cc:258
unsigned int uint32_t
Definition BKE_text.h:81
BMesh const char void * data
constexpr IntT ceil_division(const IntT x, const IntT y)
signed short int16_t
Definition BKE_text.h:77
constexpr int grain_size(const int fallback) const
std::optional< int > grain_size_override
threading::EnumerableThreadSpecific< LocalData > data_by_thread
void reduce(LinearAllocator<> &main_allocator, Vector< IndexMaskSegment, 16 > &main_segments)