Blender V5.3
BLI_index_mask.hh
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#pragma once
10
11#include <array>
12#include <optional>
13#include <variant>
14
15#include "BLI_bit_span.hh"
16#include "BLI_execution_mode.hh"
17#include "BLI_function_ref.hh"
18#include "BLI_index_mask_fwd.hh"
21#include "BLI_offset_indices.hh"
22#include "BLI_offset_span.hh"
23#include "BLI_task.hh"
25#include "BLI_vector.hh"
27
28namespace blender {
29
30namespace index_mask {
31
47static constexpr int64_t max_segment_size_shift = 14;
48static constexpr int64_t max_segment_size = (1 << max_segment_size_shift); /* 16384 */
51
63
107
115 private:
117 AlignedBuffer<1024, 8> inline_buffer_;
118
119 public:
121 {
122 this->provide_buffer(inline_buffer_);
123 }
124};
125
130class IndexMaskSegment : public OffsetSpan<int64_t, int16_t> {
131 public:
133
135
136 IndexMaskSegment slice(const IndexRange &range) const;
137 IndexMaskSegment slice(const int64_t start, const int64_t size) const;
138
143 IndexMaskSegment shift(const int64_t shift) const;
144};
145
146template<typename Fn>
147concept IndexFn = std::invocable<Fn, int64_t>;
148template<typename Fn>
149concept IndexPosFn = std::invocable<Fn, int64_t, int64_t>;
150template<typename Fn>
152
153template<typename Fn>
154concept SegmentFn = std::invocable<Fn, IndexMaskSegment>;
155template<typename Fn>
156concept SegmentPosFn = std::invocable<Fn, IndexMaskSegment, int64_t>;
157template<typename Fn>
159
160template<typename Fn>
161concept RangeFn = std::invocable<Fn, IndexRange>;
162template<typename Fn>
163concept RangePosFn = std::invocable<Fn, IndexRange, int64_t>;
164template<typename Fn>
166
167template<typename Fn>
169template<typename Fn>
171template<typename Fn>
173
218class IndexMask : private IndexMaskData {
219 public:
221 IndexMask();
223 explicit IndexMask(int64_t size);
225 IndexMask(IndexRange range);
226
228 template<typename T> static IndexMask from_indices(Span<T> indices, LinearAllocator<> &memory);
232 static IndexMask from_bits(const IndexMask &universe, BitSpan bits, LinearAllocator<> &memory);
234 static IndexMask from_bools(Span<bool> bools, LinearAllocator<> &memory);
235 static IndexMask from_bools(const VArray<bool> &bools, LinearAllocator<> &memory);
237 static IndexMask from_bools_inverse(const VArray<bool> &bools, LinearAllocator<> &memory);
239 static IndexMask from_bools(const IndexMask &universe,
240 Span<bool> bools,
241 LinearAllocator<> &memory);
242 static IndexMask from_bools_inverse(const IndexMask &universe,
243 Span<bool> bools,
244 LinearAllocator<> &memory);
245 static IndexMask from_bools(const IndexMask &universe,
246 const VArray<bool> &bools,
247 LinearAllocator<> &memory);
248 static IndexMask from_bools_inverse(const IndexMask &universe,
249 const VArray<bool> &bools,
250 LinearAllocator<> &memory);
252 template<typename T>
254 const IndexMask &mask,
255 LinearAllocator<> &memory);
261 static IndexMask from_repeating(const IndexMask &mask_to_repeat,
262 int64_t repetitions,
263 int64_t stride,
264 int64_t initial_offset,
265 LinearAllocator<> &memory);
270 int64_t indices_num,
271 const int64_t initial_offset,
272 LinearAllocator<> &memory);
282 using Initializer = std::variant<IndexRange, Span<int64_t>, Span<int>, int64_t>;
283 static IndexMask from_initializers(const Span<Initializer> initializers,
284 LinearAllocator<> &memory);
286 static IndexMask from_union(const IndexMask &mask_a,
287 const IndexMask &mask_b,
288 LinearAllocator<> &memory);
292 static IndexMask from_difference(const IndexMask &mask_a,
293 const IndexMask &mask_b,
294 LinearAllocator<> &memory);
296 static IndexMask from_intersection(const IndexMask &mask_a,
297 const IndexMask &mask_b,
298 LinearAllocator<> &memory);
300 template<typename Fn>
301 static IndexMask from_predicate(const IndexMask &universe,
302 LinearAllocator<> &memory,
303 Fn &&predicate,
314 const IndexMask &universe,
315 LinearAllocator<> &memory,
316 FunctionRef<int64_t(const IndexMaskSegment &universe_segment,
317 IndexRangesBuilder<int16_t> &builder)> batch_predicate,
320 template<typename T, typename Fn>
321 static void from_groups(const IndexMask &universe,
322 LinearAllocator<> &memory,
323 Fn &&get_group_index,
324 MutableSpan<IndexMask> r_masks);
325
330 static Vector<IndexMask, 4> from_group_ids(const VArray<int> &group_ids,
331 LinearAllocator<> &memory);
332 static Vector<IndexMask, 4> from_group_ids(const IndexMask &universe,
333 const VArray<int> &group_ids,
334 LinearAllocator<> &memory);
335
336 int64_t size() const;
337 bool is_empty() const;
338 IndexRange index_range() const;
339 int64_t first() const;
340 int64_t last() const;
341
345 IndexRange bounds() const;
346
351 int64_t min_array_size() const;
352
356 std::optional<RawMaskIterator> find(int64_t query_index) const;
357 std::optional<RawMaskIterator> find_larger_equal(int64_t query_index) const;
358 std::optional<RawMaskIterator> find_smaller_equal(int64_t query_index) const;
362 bool contains(int64_t query_index) const;
363
368
373 int64_t operator[](int64_t i) const;
378 int64_t operator[](const RawMaskIterator &it) const;
379
384 IndexMask slice(IndexRange range) const;
385 IndexMask slice(int64_t start, int64_t size) const;
386 IndexMask slice(RawMaskIterator first_it, RawMaskIterator last_it, int64_t size) const;
397 IndexMask slice_and_shift(IndexRange range, int64_t offset, LinearAllocator<> &memory) const;
400 int64_t offset,
401 LinearAllocator<> &memory) const;
402
406 IndexMask shift(const int64_t offset, LinearAllocator<> &memory) const;
407
412 IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const;
413
417 int64_t segments_num() const;
421 IndexMaskSegment segment(int64_t segment_i) const;
422
436 static void foreach_segment_zipped(Span<IndexMask> masks,
437 FunctionRef<bool(Span<IndexMaskSegment> segments)> fn);
438
449 template<ForeachIndexFn Fn, exec_mode::Tag Mode = exec_mode::Serial>
450 void foreach_index(Fn &&fn, Mode mode = exec_mode::serial) const;
451
457 template<typename IndexT, ForeachIndexFn Fn, exec_mode::Tag Mode = exec_mode::Serial>
458 void foreach_index_optimized(Fn &&fn, Mode mode = exec_mode::serial) const;
459
471 template<ForeachSegmentFn Fn, exec_mode::Tag Mode = exec_mode::Serial>
472 void foreach_segment(Fn &&fn, Mode mode = exec_mode::serial) const;
473
483 template<ForeachSegmentOrRangePosFn Fn, exec_mode::Tag Mode = exec_mode::Serial>
484 void foreach_segment_optimized(Fn &&fn, Mode mode = exec_mode::serial) const;
485
494 void foreach_range(ForeachRangeFn auto &&fn) const;
495
500 template<typename T> void to_indices(MutableSpan<T> r_indices) const;
501 template<typename T> Vector<T> to_indices() const;
505 void set_bits(MutableBitSpan r_bits, int64_t offset = 0) const;
509 void to_bits(MutableBitSpan r_bits, int64_t offset = 0) const;
513 void to_bools(MutableSpan<bool> r_bools) const;
518 std::optional<IndexRange> to_range() const;
533 template<int64_t N = 4>
535
540
541 friend bool operator==(const IndexMask &a, const IndexMask &b);
542 friend bool operator!=(const IndexMask &a, const IndexMask &b);
543};
544
551 private:
552 int64_t segment_offset_;
553 const int16_t *segment_indices_;
554 std::array<int64_t, 2> cumulative_segment_sizes_;
555 IndexMask mask_;
556
557 public:
559 const IndexMask &update(IndexMaskSegment segment);
560};
561
563{
564 IndexMaskData &data = mask_.data_for_inplace_construction();
565 cumulative_segment_sizes_[0] = 0;
566 data.segments_num_ = 1;
567 data.indices_by_segment_ = &segment_indices_;
568 data.segment_offsets_ = &segment_offset_;
569 data.cumulative_segment_sizes_ = cumulative_segment_sizes_.data();
570 data.begin_index_in_segment_ = 0;
571}
572
574{
575 const Span<int16_t> indices = segment.base_span();
576 BLI_assert(!indices.is_empty());
577 BLI_assert(std::is_sorted(indices.begin(), indices.end()));
578 BLI_assert(indices[0] >= 0);
579 BLI_assert(indices.last() < max_segment_size);
580 const int64_t indices_num = indices.size();
581
582 IndexMaskData &data = mask_.data_for_inplace_construction();
583 segment_offset_ = segment.offset();
584 segment_indices_ = indices.data();
585 cumulative_segment_sizes_[1] = int16_t(indices_num);
586 data.indices_num_ = indices_num;
587 data.end_index_in_segment_ = indices_num;
588
589 return mask_;
590}
591
592std::array<int16_t, max_segment_size> build_static_indices_array();
594std::ostream &operator<<(std::ostream &stream, const IndexMask &mask);
595
596/* -------------------------------------------------------------------- */
599
600inline const std::array<int16_t, max_segment_size> &get_static_indices_array()
601{
602 alignas(64) static const std::array<int16_t, max_segment_size> data =
604 return data;
605}
606
608template<typename T>
609inline void masked_fill(MutableSpan<T> data, const T &value, const IndexMask &mask);
610
612template<typename T>
613inline void copy_assign(const Span<T> src, const IndexMask &mask, const MutableSpan<T> dst);
614
616template<typename T>
617inline void gather_assign(const Span<T> src, const IndexMask &mask, const MutableSpan<T> dst);
618
624template<typename T> void build_reverse_map(const IndexMask &mask, MutableSpan<T> r_map);
625
634 LinearAllocator<> &memory);
635
640template<int64_t N>
642
644
645/* -------------------------------------------------------------------- */
648
649inline bool operator!=(const RawMaskIterator &a, const RawMaskIterator &b)
650{
651 return a.segment_i != b.segment_i || a.index_in_segment != b.index_in_segment;
652}
653
654inline bool operator==(const RawMaskIterator &a, const RawMaskIterator &b)
655{
656 return !(a != b);
657}
658
660
661/* -------------------------------------------------------------------- */
664
669
671{
672 return IndexMaskSegment(static_cast<const OffsetSpan<int64_t, int16_t> *>(this)->slice(range));
673}
674
676{
677 return IndexMaskSegment(
678 static_cast<const OffsetSpan<int64_t, int16_t> *>(this)->slice(start, size));
679}
680
682{
683 BLI_assert(this->is_empty() || (*this)[0] + shift >= 0);
684 return IndexMaskSegment(this->offset() + shift, this->base_span());
685}
686
688
689/* -------------------------------------------------------------------- */
692
694{
695 static constexpr int64_t cumulative_sizes_for_empty_mask[1] = {0};
696
697 data.indices_num_ = 0;
698 data.segments_num_ = 0;
699 data.cumulative_segment_sizes_ = cumulative_sizes_for_empty_mask;
700 /* Intentionally leave some pointers uninitialized which must not be accessed on empty masks
701 * anyway. */
702}
703
705{
706 init_empty_mask(*this);
707}
708
721
723{
724 if (range.is_empty()) {
725 init_empty_mask(*this);
726 return;
727 }
728 const int64_t one_after_last = range.one_after_last();
729 *this = get_static_index_mask_for_min_size(one_after_last);
730
731 const int64_t first_segment_i = range.first() >> max_segment_size_shift;
732 const int64_t last_segment_i = range.last() >> max_segment_size_shift;
733
734 indices_num_ = range.size();
735 segments_num_ = last_segment_i - first_segment_i + 1;
736 indices_by_segment_ += first_segment_i;
737 segment_offsets_ += first_segment_i;
738 cumulative_segment_sizes_ += first_segment_i;
740 end_index_in_segment_ = one_after_last - ((one_after_last - 1) & max_segment_size_mask_high);
741}
742
744{
745 return indices_num_;
746}
747
748inline bool IndexMask::is_empty() const
749{
750 return indices_num_ == 0;
751}
752
754{
755 return IndexRange(indices_num_);
756}
757
759{
760 if (this->is_empty()) {
761 return IndexRange();
762 }
763 const int64_t first = this->first();
764 const int64_t last = this->last();
766}
767
773
775{
777 const int64_t last_segment_i = segments_num_ - 1;
778 return segment_offsets_[last_segment_i] +
779 indices_by_segment_[last_segment_i][end_index_in_segment_ - 1];
780}
781
783{
784 if (indices_num_ == 0) {
785 return 0;
786 }
787 return this->last() + 1;
788}
789
791{
792 BLI_assert(index >= 0);
799 [&](const int64_t cumulative_size) { return cumulative_size <= full_index; });
801 return it;
802}
803
814
816{
817 const RawMaskIterator it = this->index_to_iterator(i);
818 return (*this)[it];
819}
820
825
827{
828 return segments_num_;
829}
830
831inline IndexMaskSegment IndexMask::segment(const int64_t segment_i) const
832{
833 BLI_assert(segment_i >= 0);
834 BLI_assert(segment_i < segments_num_);
835 const int64_t full_segment_size = cumulative_segment_sizes_[segment_i + 1] -
836 cumulative_segment_sizes_[segment_i];
837 const int64_t begin_index = (segment_i == 0) ? begin_index_in_segment_ : 0;
838 const int64_t end_index = (segment_i == segments_num_ - 1) ? end_index_in_segment_ :
839 full_segment_size;
840 const int64_t segment_size = end_index - begin_index;
841 return IndexMaskSegment{segment_offsets_[segment_i],
842 {indices_by_segment_[segment_i] + begin_index, segment_size}};
843}
844
845inline IndexMask IndexMask::slice(const IndexRange range) const
846{
847 return this->slice(range.start(), range.size());
848}
849
851{
852 return *this;
853}
854
855template<ForeachIndexFn Fn, exec_mode::Tag Mode>
856inline void IndexMask::foreach_index(Fn &&fn, const Mode mode) const
857{
858 if constexpr (mode.is_parallel) {
860 this->index_range(), mode.grain_size(4096), [&](const IndexRange range) {
861 const IndexMask sub_mask = this->slice(range);
862 sub_mask.foreach_index([&](const int64_t i, [[maybe_unused]] const int64_t index_pos) {
863 if constexpr (std::is_invocable_r_v<void, Fn, int64_t, int64_t>) {
864 fn(i, index_pos + range.start());
865 }
866 else {
867 fn(i);
868 }
869 });
870 });
871 }
872 else {
873 this->foreach_segment(
874 [&](const IndexMaskSegment indices, [[maybe_unused]] const int64_t start_segment_pos) {
875 if constexpr (IndexPosFn<Fn>) {
876 for (const int64_t i : indices.index_range()) {
877 fn(indices[i], start_segment_pos + i);
878 }
879 }
880 else {
881 for (const int64_t index : indices) {
882 fn(index);
883 }
884 }
885 });
886 }
887}
888
889template<typename T, typename Fn>
890#if (defined(__GNUC__) && !defined(__clang__))
891[[gnu::optimize("O3")]]
892#endif
893inline void optimized_foreach_index(const IndexMaskSegment segment, const Fn fn)
894{
895 BLI_assert(segment.last() < std::numeric_limits<T>::max());
896 if (unique_sorted_indices::non_empty_is_range(segment.base_span())) {
897 const T start = T(segment[0]);
898 const T last = T(segment.last());
899 for (T i = start; i <= last; i++) {
900 fn(i);
901 }
902 }
903 else {
904 for (const int64_t i : segment) {
905 fn(T(i));
906 }
907 }
908}
909
910template<typename T, typename Fn>
911#if (defined(__GNUC__) && !defined(__clang__))
912[[gnu::optimize("O3")]]
913#endif
915 const int64_t segment_pos,
916 const Fn fn)
917{
918 BLI_assert(segment.last() < std::numeric_limits<T>::max());
919 BLI_assert(segment.size() + segment_pos < std::numeric_limits<T>::max());
920 if (unique_sorted_indices::non_empty_is_range(segment.base_span())) {
921 const T start = T(segment[0]);
922 const T last = T(segment.last());
923 for (T i = start, pos = T(segment_pos); i <= last; i++, pos++) {
924 fn(i, pos);
925 }
926 }
927 else {
928 T pos = T(segment_pos);
929 for (const int64_t i : segment.index_range()) {
930 const T index = T(segment[i]);
931 fn(index, pos);
932 pos++;
933 }
934 }
935}
936
937template<typename IndexT, ForeachIndexFn Fn, exec_mode::Tag Mode>
938inline void IndexMask::foreach_index_optimized(Fn &&fn, Mode mode) const
939{
940 if constexpr (mode.is_parallel) {
942 this->index_range(), mode.grain_size(4096), [&](const IndexRange range) {
943 const IndexMask sub_mask = this->slice(range);
944 sub_mask.foreach_segment([&](const IndexMaskSegment segment,
945 [[maybe_unused]] const int64_t segment_pos) {
946 if constexpr (IndexPosFn<Fn>) {
947 optimized_foreach_index_with_pos<IndexT>(segment, segment_pos + range.start(), fn);
948 }
949 else {
950 optimized_foreach_index<IndexT>(segment, fn);
951 }
952 });
953 });
954 }
955 else {
956 this->foreach_segment(
957 [&](const IndexMaskSegment segment, [[maybe_unused]] const int64_t segment_pos) {
958 if constexpr (IndexPosFn<Fn>) {
959 optimized_foreach_index_with_pos<IndexT>(segment, segment_pos, fn);
960 }
961 else {
963 }
964 });
965 }
966}
967
968template<ForeachSegmentOrRangePosFn Fn, exec_mode::Tag Mode>
969inline void IndexMask::foreach_segment_optimized(Fn &&fn, Mode mode) const
970{
971 if constexpr (mode.is_parallel) {
973 this->index_range(), mode.grain_size(4096), [&](const IndexRange range) {
974 const IndexMask sub_mask = this->slice(range);
975 sub_mask.foreach_segment_optimized(
976 [&fn, range_start = range.start()](
977 const auto segment, [[maybe_unused]] const int64_t start_segment_pos) {
978 if constexpr (SegmentOrRangePosFn<Fn>) {
979 fn(segment, start_segment_pos + range_start);
980 }
981 else {
982 fn(segment);
983 }
984 });
985 });
986 }
987 else {
988 this->foreach_segment(
989 [&](const IndexMaskSegment segment, [[maybe_unused]] const int64_t start_segment_pos) {
990 if (unique_sorted_indices::non_empty_is_range(segment.base_span())) {
991 const IndexRange range(segment[0], segment.size());
992 if constexpr (SegmentOrRangePosFn<Fn>) {
993 fn(range, start_segment_pos);
994 }
995 else {
996 fn(range);
997 }
998 }
999 else {
1000 if constexpr (SegmentOrRangePosFn<Fn>) {
1001 fn(segment, start_segment_pos);
1002 }
1003 else {
1004 fn(segment);
1005 }
1006 }
1007 },
1008 mode);
1009 }
1010}
1011
1012template<ForeachSegmentFn Fn>
1013inline void IndexMask::foreach_segment(Fn &&fn, const exec_mode::Tag auto mode) const
1014{
1015 if constexpr (mode.is_parallel) {
1017 this->index_range(), mode.grain_size(256), [&](const IndexRange range) {
1018 const IndexMask sub_mask = this->slice(range);
1019 sub_mask.foreach_segment(
1020 [&fn, range_start = range.start()](const IndexMaskSegment mask_segment,
1021 [[maybe_unused]] const int64_t segment_pos) {
1022 if constexpr (SegmentPosFn<Fn>) {
1023 fn(mask_segment, segment_pos + range_start);
1024 }
1025 else {
1026 fn(mask_segment);
1027 }
1028 });
1029 });
1030 }
1031 else {
1032 [[maybe_unused]] int64_t segment_pos = 0;
1033 for (const int64_t segment_i : IndexRange(segments_num_)) {
1034 const IndexMaskSegment segment = this->segment(segment_i);
1035 if constexpr (SegmentPosFn<Fn>) {
1036 fn(segment, segment_pos);
1037 segment_pos += segment.size();
1038 }
1039 else {
1040 fn(segment);
1041 }
1042 }
1043 }
1044}
1045
1046template<ForeachRangeFn Fn> inline void IndexMask::foreach_range(Fn &&fn) const
1047{
1048 this->foreach_segment([&](const IndexMaskSegment indices, [[maybe_unused]] int64_t segment_pos) {
1049 Span<int16_t> base_indices = indices.base_span();
1050 while (!base_indices.is_empty()) {
1051 const int64_t next_range_size = unique_sorted_indices::find_size_of_next_range(base_indices);
1052 const IndexRange range(int64_t(base_indices[0]) + indices.offset(), next_range_size);
1053 if constexpr (RangePosFn<Fn>) {
1054 fn(range, segment_pos);
1055 }
1056 else {
1057 fn(range);
1058 }
1059 segment_pos += next_range_size;
1060 base_indices = base_indices.drop_front(next_range_size);
1061 }
1062 });
1063}
1064
1065namespace detail {
1067 const IndexMask &universe,
1068 LinearAllocator<> &memory,
1069 FunctionRef<int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices,
1070 exec_mode::Mode mode);
1071}
1072
1073template<typename Fn>
1075 LinearAllocator<> &memory,
1076 Fn &&predicate,
1077 const exec_mode::Mode mode)
1078{
1080 universe,
1081 memory,
1082 [&](const IndexMaskSegment indices, int16_t *__restrict r_true_indices) {
1083 int16_t *r_current = r_true_indices;
1084 const int16_t *in_end = indices.base_span().end();
1085 const int64_t offset = indices.offset();
1086 for (const int16_t *in_current = indices.base_span().data(); in_current < in_end;
1087 in_current++)
1088 {
1089 const int16_t local_index = *in_current;
1090 const int64_t global_index = int64_t(local_index) + offset;
1091 const bool condition = predicate(global_index);
1092 *r_current = local_index;
1093 /* This expects the boolean to be either 0 or 1 which is generally the case but may not
1094 * be if the values are uninitialized. */
1096 /* Branchless conditional increment. */
1097 r_current += condition;
1098 }
1099 const int16_t true_indices_num = int16_t(r_current - r_true_indices);
1100 return true_indices_num;
1101 },
1102 mode);
1103}
1104
1105template<typename T, typename Fn>
1107 LinearAllocator<> &memory,
1108 Fn &&get_group_index,
1109 MutableSpan<IndexMask> r_masks)
1110{
1111 if (r_masks.size() == 1) {
1112#ifndef NDEBUG
1113 universe.foreach_index([&](const int i) { BLI_assert(get_group_index(i) == 0); });
1114#endif
1115 r_masks[0] = universe;
1116 return;
1117 }
1118
1119 Vector<Vector<T>> indices_by_group(r_masks.size());
1120 universe.foreach_index([&](const int64_t i) {
1121 const int group_index = get_group_index(i);
1122 indices_by_group[group_index].append(T(i));
1123 });
1124 for (const int64_t i : r_masks.index_range()) {
1125 r_masks[i] = IndexMask::from_indices<T>(indices_by_group[i], memory);
1126 }
1127}
1128
1129template<typename T> inline Vector<T> IndexMask::to_indices() const
1130{
1131 Vector<T> indices(indices_num_);
1132 this->to_indices<T>(indices);
1133 return indices;
1134}
1135
1136std::optional<IndexRange> inline IndexMask::to_range() const
1137{
1138 if (indices_num_ == 0) {
1139 return IndexRange{};
1140 }
1141 const int64_t first_index = this->first();
1142 const int64_t last_index = this->last();
1143 if (last_index - first_index == indices_num_ - 1) {
1144 return IndexRange(first_index, indices_num_);
1145 }
1146 return std::nullopt;
1147}
1148
1149template<int64_t N>
1151{
1153 this->foreach_segment_optimized([&](const auto segment) { segments.append(segment); });
1154 return segments;
1155}
1156
1157inline bool operator!=(const IndexMask &a, const IndexMask &b)
1158{
1159 return !(a == b);
1160}
1161
1162template<int64_t N>
1164 Vector<IndexMaskSegment, N> &r_segments)
1165{
1166 const std::array<int16_t, max_segment_size> &static_indices_array = get_static_indices_array();
1167
1168 const int64_t full_size = range.size();
1169 for (int64_t i = 0; i < full_size; i += max_segment_size) {
1170 const int64_t size = std::min(i + max_segment_size, full_size) - i;
1171 r_segments.append(
1172 IndexMaskSegment(range.first() + i, Span(static_indices_array).take_front(size)));
1173 }
1174}
1175
1176namespace detail {
1177
1178template<typename T, typename SegmentT>
1179#if (defined(__GNUC__) && !defined(__clang__))
1180[[gnu::optimize("-funroll-loops")]] [[gnu::optimize("O3")]]
1181#endif
1182inline void gather_assign_segment(const T *__restrict src,
1183 const SegmentT segment,
1184 T *__restrict dst)
1185{
1186 for (int16_t i = 0; i < segment.size(); i++) {
1187 dst[i] = src[segment[i]];
1188 }
1189}
1190
1191template<typename T, typename SegmentT>
1192#if (defined(__GNUC__) && !defined(__clang__))
1193[[gnu::optimize("-funroll-loops")]] [[gnu::optimize("O3")]]
1194#endif
1195inline void copy_assign_segment(const T *__restrict src, const SegmentT segment, T *__restrict dst)
1196{
1197 for (const int64_t i : segment) {
1198 dst[i] = src[i];
1199 }
1200}
1201
1202template<typename T, typename SegmentT>
1203#if (defined(__GNUC__) && !defined(__clang__))
1204[[gnu::optimize("-funroll-loops")]] [[gnu::optimize("O3")]]
1205#endif
1206inline void fill_segment(T *__restrict data, const T &value, const SegmentT segment)
1207{
1208 if constexpr (std::is_same_v<SegmentT, IndexRange>) {
1209 if constexpr (std::is_trivially_copy_assignable_v<T>) {
1210 if (value_is_zero_memory(value)) {
1211 const IndexRange range = segment;
1212/* GCC warns about memset on types without trivial copy-assignment even when guarded by
1213 * `if constexpr (std::is_trivially_copy_assignable_v<T>)`. Quiet the compiler bug. */
1214#if defined(__GNUC__) && !defined(__clang__)
1215# pragma GCC diagnostic push
1216# pragma GCC diagnostic ignored "-Wclass-memaccess"
1217#endif
1218 memset(data + range.start(), 0, range.size() * sizeof(T));
1219#if defined(__GNUC__) && !defined(__clang__)
1220# pragma GCC diagnostic pop
1221#endif
1222 return;
1223 }
1224 }
1225 }
1226 for (const int64_t i : segment) {
1227 data[i] = value;
1228 }
1229}
1230
1231template<typename T>
1232BLI_NOINLINE void copy_assign(const T *__restrict src, const IndexMask &mask, T *__restrict dst)
1233{
1234 mask.foreach_segment_optimized(
1235 [src, dst](const auto segment) { copy_assign_segment(src, segment, dst); },
1237}
1238
1239template<typename T>
1240BLI_NOINLINE void gather_assign(const T *__restrict src,
1241 const IndexMask &indices,
1242 T *__restrict dst)
1243{
1245 [src, dst](const auto segment, const int64_t segment_pos) {
1246 gather_assign_segment(src, segment, dst + segment_pos);
1247 },
1249}
1250
1251template<typename T>
1252BLI_NOINLINE void fill(T *__restrict data, const T &value, const IndexMask &mask)
1253{
1254 mask.foreach_segment_optimized(
1255 [data, value](const auto segment) { fill_segment(data, value, segment); },
1257}
1258
1259} // namespace detail
1260
1261template<typename T>
1262inline void masked_fill(MutableSpan<T> data, const T &value, const IndexMask &mask)
1263{
1264 BLI_assert(data.size() >= mask.min_array_size());
1265 detail::fill(data.data(), value, mask);
1266}
1267
1269template<typename T>
1270inline void copy_assign(const Span<T> src, const IndexMask &mask, const MutableSpan<T> dst)
1271{
1272 BLI_assert(src.size() >= mask.min_array_size());
1273 BLI_assert(dst.size() >= mask.min_array_size());
1274 detail::copy_assign(src.data(), mask, dst.data());
1275}
1276
1278template<typename T>
1279inline void gather_assign(const Span<T> src, const IndexMask &mask, const MutableSpan<T> dst)
1280{
1281 BLI_assert(src.size() >= mask.min_array_size());
1282 BLI_assert(dst.size() == mask.size());
1283 detail::gather_assign(src.data(), mask, dst.data());
1284}
1285
1296 const int64_t universe_size,
1297 const uint32_t random_seed,
1298 const float probability,
1299 LinearAllocator<> &memory);
1300
1301IndexMask random_mask(const int64_t universe_size,
1302 const uint32_t random_seed,
1303 const float probability,
1304 LinearAllocator<> &memory);
1305
1307
1308} // namespace index_mask
1309
1310using index_mask::IndexMask;
1311using index_mask::IndexMaskFromSegment;
1312using index_mask::IndexMaskMemory;
1313using index_mask::IndexMaskSegment;
1314
1315} // namespace blender
#define BLI_NOINLINE
#define ELEM(...)
long long int int64_t
const IndexMask & update(IndexMaskSegment segment)
IndexMaskSegment slice(const IndexRange &range) const
IndexMaskSegment shift(const int64_t shift) const
IndexMaskSegment(const OffsetSpan< int64_t, int16_t > span)
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)
int64_t last() const
std::optional< IndexRange > to_range() const
IndexMask slice(IndexRange range) const
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
IndexRange bounds() const
Vector< T > to_indices() const
int64_t operator[](int64_t i) const
int64_t iterator_to_index(const RawMaskIterator &it) const
void foreach_segment_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
int64_t min_array_size() const
IndexRange index_range() const
Vector< std::variant< IndexRange, IndexMaskSegment >, N > to_spans_and_ranges() const
IndexMaskData & data_for_inplace_construction()
static void from_groups(const IndexMask &universe, LinearAllocator<> &memory, Fn &&get_group_index, MutableSpan< IndexMask > r_masks)
int64_t size() const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
int64_t first() const
RawMaskIterator index_to_iterator(int64_t index) const
int64_t segments_num() const
constexpr int64_t first() const
constexpr int64_t one_after_last() const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
constexpr bool is_empty() const
constexpr IndexRange()=default
constexpr int64_t start() const
static constexpr IndexRange from_begin_end_inclusive(const int64_t begin, const int64_t last)
void provide_buffer(void *buffer, const int64_t size)
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr T * data() const
Definition BLI_span.hh:545
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
IndexRange index_range() const
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
constexpr const T * data() const
Definition BLI_span.hh:219
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 const T * begin() const
Definition BLI_span.hh:224
constexpr bool is_empty() const
Definition BLI_span.hh:264
void append(const T &value)
NonCopyable(const NonCopyable &other)=delete
NonMovable(NonMovable &&other)=delete
const IndexMask & update(IndexMaskSegment segment)
IndexMaskSegment slice(const IndexRange &range) const
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 operator[](int64_t i) const
int64_t iterator_to_index(const RawMaskIterator &it) const
static IndexMask from_union(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
void to_indices(MutableSpan< T > r_indices) const
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)
Vector< std::variant< IndexRange, IndexMaskSegment >, N > to_spans_and_ranges() const
std::optional< RawMaskIterator > find_smaller_equal(int64_t query_index) const
friend bool operator!=(const IndexMask &a, const IndexMask &b)
IndexMaskData & data_for_inplace_construction()
bool contains(int64_t query_index) const
static void from_groups(const IndexMask &universe, LinearAllocator<> &memory, Fn &&get_group_index, MutableSpan< IndexMask > r_masks)
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) 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 index(i)
#define condition(cond)
#define N
#define T
int64_t last_if(const Range &range, Predicate &&predicate)
constexpr Serial serial
constexpr Parallel parallel
void gather_assign_segment(const T *__restrict src, const SegmentT segment, T *__restrict dst)
void copy_assign_segment(const T *__restrict src, const SegmentT segment, T *__restrict dst)
void fill_segment(T *__restrict data, const T &value, const SegmentT segment)
BLI_NOINLINE void fill(T *__restrict data, const T &value, const IndexMask &mask)
BLI_NOINLINE void copy_assign(const T *__restrict src, const IndexMask &mask, T *__restrict dst)
BLI_NOINLINE void gather_assign(const T *__restrict src, const IndexMask &indices, T *__restrict dst)
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)
void copy_assign(const Span< T > src, const IndexMask &mask, const MutableSpan< T > dst)
IndexMask random_mask(const IndexMask &mask, const int64_t universe_size, const uint32_t random_seed, const float probability, LinearAllocator<> &memory)
void index_range_to_mask_segments(const IndexRange range, Vector< IndexMaskSegment, N > &r_segments)
static constexpr int64_t max_segment_size
static constexpr int64_t max_segment_size_mask_high
void gather_assign(const Span< T > src, const IndexMask &mask, const MutableSpan< T > dst)
void build_reverse_map(const IndexMask &mask, MutableSpan< T > r_map)
Definition index_mask.cc:36
static constexpr int64_t max_segment_size_mask_low
std::ostream & operator<<(std::ostream &stream, const IndexMask &mask)
void optimized_foreach_index(const IndexMaskSegment segment, const Fn fn)
bool operator==(const RawMaskIterator &a, const RawMaskIterator &b)
std::array< int16_t, max_segment_size > build_static_indices_array()
Definition index_mask.cc:49
void optimized_foreach_index_with_pos(const IndexMaskSegment segment, const int64_t segment_pos, const Fn fn)
const IndexMask & get_static_index_mask_for_min_size(const int64_t min_size)
Definition index_mask.cc:58
bool operator!=(const RawMaskIterator &a, const RawMaskIterator &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)
void init_empty_mask(IndexMaskData &data)
static constexpr int64_t max_segment_size_shift
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
int64_t find_size_of_next_range(const Span< T > indices)
bool non_empty_is_range(const Span< T > indices)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
constexpr bool value_is_zero_memory(const VecBase< T, Size > &v)
unsigned int uint32_t
Definition BKE_text.h:81
BMesh const char void * data
signed char int8_t
Definition BKE_text.h:76
signed short int16_t
Definition BKE_text.h:77