Blender V5.3
BLI_offset_indices_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include <algorithm>
6
7#include "testing/testing.h"
8
9#include "BLI_index_mask.hh"
10#include "BLI_offset_indices.hh"
11#include "BLI_rand.hh"
12#include "BLI_task_c.hh"
13#include "BLI_vector.hh"
14
15#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
16
18
20{
21 Vector<int> data = {3, 2, 1, 5, -1};
23 EXPECT_EQ(sum_group_sizes(offsets, {0, 1, 2, 3}), 11);
24 EXPECT_EQ(sum_group_sizes(offsets, {3, 2, 1, 0}), 11);
25 EXPECT_EQ(sum_group_sizes(offsets, {3, 0}), 8);
26 EXPECT_EQ(sum_group_sizes(offsets, IndexRange(4)), 11);
27 EXPECT_EQ(sum_group_sizes(offsets, IndexMask(4)), 11);
28 EXPECT_EQ(sum_group_sizes(offsets, IndexMask(1)), 3);
29}
30
32{
33 Vector<int> data = {3, 2, 1, 3, 4, 1, 1, 6, 8, 1, 8, 0};
34 const int groups_num = 10;
35
36 Array<int> offset_data;
37 Array<int> index_data;
39 data, groups_num, offset_data, index_data);
40
41 EXPECT_EQ(groups.size(), groups_num);
42 EXPECT_EQ(groups.offsets.total_size(), data.size());
43 EXPECT_EQ_SPAN(groups[1], {2, 5, 6, 9});
44 EXPECT_TRUE(groups[5].is_empty());
45}
46
52static void test_build_groups_from_indices(const int64_t groups_num,
53 const int64_t indices_num,
54 const bool clustered)
55{
57
59 Array<int> indices(indices_num);
60 for (const int64_t i : indices.index_range()) {
61 if (clustered) {
62 /* Approximately sorted, similar to real topology. */
63 const int64_t center = i * groups_num / indices_num;
64 const int64_t jitter = std::max<int64_t>(groups_num / 64, 1);
65 indices[i] = int(std::clamp(
66 center + random.get_int32(int32_t(2 * jitter)) - jitter, int64_t(0), groups_num - 1));
67 }
68 else {
69 indices[i] = random.get_int32(int32_t(groups_num));
70 }
71 }
72
73 Array<int> offset_data;
74 Array<int> index_data;
76 indices, int(groups_num), offset_data, index_data);
77
78 ASSERT_EQ(groups.size(), groups_num);
79 ASSERT_EQ(groups.offsets.total_size(), indices_num);
80
81 /* Every index must appear in the group it points to, and groups must be sorted. */
82 Array<int> expected_counts(groups_num, 0);
83 for (const int group : indices) {
84 expected_counts[group]++;
85 }
86 for (const int64_t group : IndexRange(groups_num)) {
87 const Span<int> group_indices = groups[group];
88 ASSERT_EQ(group_indices.size(), expected_counts[group]);
89 for (const int64_t i : group_indices.index_range()) {
90 ASSERT_EQ(indices[group_indices[i]], group);
91 if (i > 0) {
92 ASSERT_LT(group_indices[i - 1], group_indices[i]);
93 }
94 }
95 }
96}
97
98TEST(offset_indices, build_groups_from_indices_few_groups)
99{
100 test_build_groups_from_indices(64, 200000, false);
101 test_build_groups_from_indices(64, 200000, true);
102}
103
104TEST(offset_indices, build_groups_from_indices_many_groups)
105{
106 test_build_groups_from_indices(150000, 200000, false);
107 test_build_groups_from_indices(150000, 200000, true);
108}
109
110TEST(offset_indices, build_groups_from_indices_atomic)
111{
112 test_build_groups_from_indices(2000000, 200000, false);
113 test_build_groups_from_indices(2000000, 200000, true);
114}
115
116TEST(offset_indices, build_groups_from_indices_small)
117{
118 test_build_groups_from_indices(64, 1000, false);
119 test_build_groups_from_indices(1000, 1000, false);
120}
121
122static void test_build_groups_from_indices_mask(const int64_t groups_num,
123 const int64_t indices_num)
124{
126
127 Array<int> indices(indices_num);
128 for (const int64_t i : indices.index_range()) {
129 indices[i] = int((i * 4241) % groups_num);
130 }
131
132 /* A mask with gaps, so that the original indices differ from the positions. */
133 IndexMaskMemory memory;
134 const IndexMask mask = IndexMask::from_every_nth(3, indices_num, 1, memory);
135
136 Array<int> offset_data;
137 Array<int> index_data;
139 indices, int(groups_num), offset_data, index_data);
140
141 Array<int> mask_offset_data;
142 Array<int> mask_index_data;
144 indices, int(groups_num), mask_offset_data, mask_index_data, mask);
145
146 ASSERT_EQ(mask_groups.offsets.total_size(), groups.offsets.total_size());
147 for (const int64_t i : index_data.index_range()) {
148 ASSERT_EQ(mask_index_data[i], mask[index_data[i]]);
149 }
150}
151
152TEST(offset_indices, build_groups_from_indices_mask)
153{
157}
158
160 const int64_t indices_num)
161{
163
164 Array<int> indices(indices_num);
165 Array<int> offset_data(groups_num + 1, 0);
166 for (const int64_t i : indices.index_range()) {
167 indices[i] = int((i * 4241) % groups_num);
168 offset_data[indices[i]]++;
169 }
170 const OffsetIndices<int> offsets = accumulate_counts_to_offsets(offset_data);
171
172 /* Build irregular "face"-like groups spanning the same index space as `indices`, each covering
173 * a handful of consecutive positions, mimicking mesh faces referencing corners. */
174 Array<int> value_group_offset_data;
175 {
176 Vector<int> sizes;
177 int64_t remaining = indices_num;
178 while (remaining > 0) {
179 sizes.append(int(std::min<int64_t>(remaining, 3 + sizes.size() % 4)));
180 remaining -= sizes.last();
181 }
182 value_group_offset_data.reinitialize(sizes.size() + 1);
183 value_group_offset_data.as_mutable_span().drop_back(1).copy_from(sizes);
184 }
185 const OffsetIndices<int> value_groups = accumulate_counts_to_offsets(value_group_offset_data);
186 ASSERT_EQ(value_groups.total_size(), indices_num);
187
188 Array<int> positions(indices_num);
189 reverse_indices_in_groups(indices, offsets, positions);
190
191 Array<int> results(indices_num);
192 reverse_indices_in_groups(indices, offsets, results, value_groups);
193
194 const Span<int> value_group_offsets = value_group_offset_data;
195 for (const int64_t i : results.index_range()) {
196 const int64_t expected = std::ranges::upper_bound(value_group_offsets, positions[i]) -
197 value_group_offsets.begin() - 1;
198 ASSERT_EQ(results[i], expected);
199 }
200}
201
202TEST(offset_indices, reverse_indices_in_value_groups)
203{
207}
208
210 const int64_t pairs_num)
211{
213
214 Array<int> indices(pairs_num * 2);
215 Array<int> offset_data(groups_num + 1, 0);
216 for (const int64_t i : indices.index_range()) {
217 indices[i] = int((i * 4241) % groups_num);
218 offset_data[indices[i]]++;
219 }
220 const OffsetIndices<int> offsets = accumulate_counts_to_offsets(offset_data);
221
222 Array<int> positions(indices.size());
223 reverse_indices_in_groups(indices, offsets, positions);
224
225 Array<int> results(indices.size());
226 reverse_indices_in_groups(indices, offsets, results, 2);
227
228 for (const int64_t i : results.index_range()) {
229 ASSERT_EQ(results[i], positions[i] / 2);
230 }
231}
232
233TEST(offset_indices, reverse_indices_in_uniform_value_groups)
234{
238}
239
240} // namespace blender::offset_indices::tests
int64_t size() const
Definition BLI_array.hh:267
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
IndexRange index_range() const
Definition BLI_array.hh:371
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
static IndexMask from_every_nth(int64_t n, int64_t indices_num, const int64_t initial_offset, LinearAllocator<> &memory)
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
int64_t size() const
void append(const T &value)
const T & last(const int64_t n=0) const
#define EXPECT_TRUE(result)
static void test_build_groups_from_indices_mask(const int64_t groups_num, const int64_t indices_num)
static void test_reverse_indices_in_uniform_value_groups(const int64_t groups_num, const int64_t pairs_num)
static void test_build_groups_from_indices(const int64_t groups_num, const int64_t indices_num, const bool clustered)
static void test_reverse_indices_in_value_groups(const int64_t groups_num, const int64_t indices_num)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
void reverse_indices_in_groups(Span< int > group_indices, OffsetIndices< int > offsets, MutableSpan< int > results, bool sort=true)
int sum_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask)
__int64 int64_t
Definition BKE_text.h:90
BMesh const char void * data
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
signed int int32_t
Definition BKE_text.h:78
void BLI_task_scheduler_init(bool use_flush_denormals_to_zero=true)