Blender V5.3
BLI_array_utils_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include "testing/testing.h"
6
7#include "BLI_array_utils.hh"
9#include "BLI_utildefines.hh"
11#include "BLI_vector_set.hh"
12#include "BLI_virtual_array.hh"
13
14namespace blender {
15
16/* -------------------------------------------------------------------- */
17/* tests */
18
19/* BLI_array_reverse */
20TEST(array_utils, ReverseStringEmpty)
21{
22 char data[] = "";
24 EXPECT_STREQ("", data);
25}
26
27TEST(array_utils, ReverseStringSingle)
28{
29 char data[] = "0";
31 EXPECT_STREQ("0", data);
32}
33
34TEST(array_utils, ReverseString4)
35{
36 char data[] = "0123";
38 EXPECT_STREQ("3210", data);
39}
40
41TEST(array_utils, ReverseInt4)
42{
43 const int data_cmp[] = {3, 2, 1, 0};
44 int data[] = {0, 1, 2, 3};
46 EXPECT_EQ_ARRAY(data_cmp, data, ARRAY_SIZE(data));
47}
48
49/* BLI_array_findindex */
50TEST(array_utils, FindIndexStringEmpty)
51{
52 char data[] = "", find = '0';
55}
56
57TEST(array_utils, FindIndexStringSingle)
58{
59 char data[] = "0", find = '0';
62}
63
64TEST(array_utils, FindIndexStringSingleMissing)
65{
66 char data[] = "1", find = '0';
69}
70
71TEST(array_utils, FindIndexString4)
72{
73 char data[] = "0123", find = '3';
76}
77
78TEST(array_utils, FindIndexInt4)
79{
80 int data[] = {0, 1, 2, 3}, find = 3;
83}
84
85TEST(array_utils, FindIndexInt4_DupeEnd)
86{
87 int data[] = {0, 1, 2, 0}, find = 0;
90}
91
92TEST(array_utils, FindIndexInt4_DupeMid)
93{
94 int data[] = {1, 0, 0, 3}, find = 0;
97}
98
99TEST(array_utils, FindIndexPointer)
100{
101 const char *data[4] = {nullptr};
103
105
106 const char *a = "a", *b = "b", *c = "c", *d = "d";
107
108#define STACK_PUSH_AND_CHECK_FORWARD(v, i) \
109 { \
110 STACK_PUSH(data, v); \
111 EXPECT_EQ(BLI_array_findindex(data, STACK_SIZE(data), &(v)), i); \
112 } \
113 ((void)0)
114
115#define STACK_PUSH_AND_CHECK_BACKWARD(v, i) \
116 { \
117 STACK_PUSH(data, v); \
118 EXPECT_EQ(BLI_array_rfindindex(data, STACK_SIZE(data), &(v)), i); \
119 } \
120 ((void)0)
121
122#define STACK_PUSH_AND_CHECK_BOTH(v, i) \
123 { \
124 STACK_PUSH(data, v); \
125 EXPECT_EQ(BLI_array_findindex(data, STACK_SIZE(data), &(v)), i); \
126 EXPECT_EQ(BLI_array_rfindindex(data, STACK_SIZE(data), &(v)), i); \
127 } \
128 ((void)0)
129
134
137
140
143
146
147#undef STACK_PUSH_AND_CHECK_FORWARD
148#undef STACK_PUSH_AND_CHECK_BACKWARD
149#undef STACK_PUSH_AND_CHECK_BOTH
150}
151
152/* BLI_array_binary_and */
153#define BINARY_AND_TEST(data_cmp, data_a, data_b, data_combine, length) \
154 { \
155 BLI_array_binary_and(data_combine, data_a, data_b, length); \
156 EXPECT_EQ_ARRAY(data_cmp, data_combine, length); \
157 } \
158 ((void)0)
159
160TEST(array_utils, BinaryAndInt4Zero)
161{
162 const int data_cmp[] = {0, 0, 0, 0};
163 int data_a[] = {0, 1, 0, 1}, data_b[] = {1, 0, 1, 0};
164 int data_combine[ARRAY_SIZE(data_cmp)];
165 BINARY_AND_TEST(data_cmp, data_a, data_b, data_combine, ARRAY_SIZE(data_cmp));
166}
167
168TEST(array_utils, BinaryAndInt4Mix)
169{
170 const int data_cmp[] = {1, 0, 1, 0};
171 int data_a[] = {1, 1, 1, 1}, data_b[] = {1, 0, 1, 0};
172 int data_combine[ARRAY_SIZE(data_cmp)];
173 BINARY_AND_TEST(data_cmp, data_a, data_b, data_combine, ARRAY_SIZE(data_cmp));
174}
175#undef BINARY_AND_TEST
176
177/* BLI_array_binary_or */
178#define BINARY_OR_TEST(data_cmp, data_a, data_b, data_combine, length) \
179 { \
180 BLI_array_binary_or(data_combine, data_a, data_b, length); \
181 EXPECT_EQ_ARRAY(data_combine, data_cmp, length); \
182 } \
183 ((void)0)
184
185TEST(array_utils, BinaryOrInt4Alternate)
186{
187 int data_a[] = {0, 1, 0, 1}, data_b[] = {1, 0, 1, 0}, data_cmp[] = {1, 1, 1, 1};
188 int data_combine[ARRAY_SIZE(data_cmp)];
189 BINARY_OR_TEST(data_cmp, data_a, data_b, data_combine, ARRAY_SIZE(data_cmp));
190}
191
192TEST(array_utils, BinaryOrInt4Mix)
193{
194 int data_a[] = {1, 1, 0, 0}, data_b[] = {0, 0, 1, 0}, data_cmp[] = {1, 1, 1, 0};
195 int data_combine[ARRAY_SIZE(data_cmp)];
196 BINARY_OR_TEST(data_cmp, data_a, data_b, data_combine, ARRAY_SIZE(data_cmp));
197}
198#undef BINARY_OR_TEST
199
200/* BLI_array_deduplicate_ordered */
201#define DEDUPLICATE_ORDERED_TEST(data, data_cmp) \
202 { \
203 const uint data_len_new = BLI_array_deduplicate_ordered(data, ARRAY_SIZE(data)); \
204 EXPECT_EQ(data_len_new, ARRAY_SIZE(data_cmp)); \
205 EXPECT_EQ_ARRAY(data, data_cmp, data_len_new); \
206 /* Ensure running a second time does nothing. */ \
207 const uint data_len_test = BLI_array_deduplicate_ordered(data, data_len_new); \
208 EXPECT_EQ(data_len_test, ARRAY_SIZE(data_cmp)); \
209 EXPECT_EQ_ARRAY(data, data_cmp, data_len_new); \
210 } \
211 ((void)0)
212
213TEST(array_utils, DeduplicateOrdered1)
214{
215 int data[] = {0};
216 const int data_cmp[] = {0};
218}
219
220TEST(array_utils, DeduplicateOrdered2)
221{
222 int data[] = {1, 2};
223 const int data_cmp[] = {1, 2};
225}
226
227TEST(array_utils, DeduplicateOrdered2Same)
228{
229 int data[] = {1, 1};
230 const int data_cmp[] = {1};
232}
233
234TEST(array_utils, DeduplicateOrdered3Same)
235{
236 int data[] = {1, 1, 1};
237 const int data_cmp[] = {1};
239}
240
241TEST(array_utils, DeduplicateOrdered3)
242{
243 int data[] = {3, 3, 2, 2, 1, 1};
244 const int data_cmp[] = {3, 2, 1};
246}
247
248#undef DEDUPLICATE_ORDERED_TEST
249
250static void find_all_ranges_test(const Span<bool> data, const Span<IndexRange> data_cmp)
251{
253 EXPECT_EQ(ranges.size(), data_cmp.size());
254 EXPECT_EQ_ARRAY(data_cmp.data(), ranges.as_span().data(), data_cmp.size());
255}
256
257TEST(array_utils, FindAllRanges1)
258{
259 const std::array data = {false};
260 Vector<IndexRange> ranges = array_utils::find_all_ranges(Span(data.data(), data.size()), true);
261 EXPECT_EQ(ranges.size(), 0);
262}
263
264TEST(array_utils, FindAllRanges2)
265{
266 const std::array data = {true, true, true};
267 const std::array data_cmp = {IndexRange(0, 3)};
268 find_all_ranges_test(data, data_cmp);
269}
270
271TEST(array_utils, FindAllRanges3)
272{
273 const std::array data = {true, false};
274 const std::array data_cmp = {IndexRange(0, 1)};
275 find_all_ranges_test(data, data_cmp);
276}
277
278TEST(array_utils, FindAllRanges4)
279{
280 const std::array data = {false, true};
281 const std::array data_cmp = {IndexRange(1, 1)};
282 find_all_ranges_test(data, data_cmp);
283}
284
285TEST(array_utils, FindAllRanges5)
286{
287 const std::array data = {true, false, false, true, true, false, true};
288 const std::array data_cmp = {IndexRange(0, 1), IndexRange(3, 2), IndexRange(6, 1)};
289 find_all_ranges_test(data, data_cmp);
290}
291
292static void find_max_element_test(const VArray<int> &values,
293 const std::optional<int64_t> expect_index)
294{
295 const std::optional<int64_t> result_index = array_utils::max_element_index(values);
296 EXPECT_TRUE(result_index.has_value() == expect_index.has_value());
297 if (result_index.has_value() && expect_index.has_value()) {
298 EXPECT_EQ(result_index.value(), expect_index.value());
299 }
300}
301
302TEST(array_utils, FindMaxElement1)
303{
305}
306
307TEST(array_utils, FindMaxElement2)
308{
309 const std::array data{1};
311}
312
313TEST(array_utils, FindMaxElement3)
314{
315 const std::array data{1, 2, 2, 1};
317}
318
319TEST(array_utils, FindMaxElement4)
320{
321 /* Inverted parabola with roots 0 and 9 and a peak at (x = 4.5, y = 20.25). */
322 find_max_element_test(VArray<int>::from_func(10, [](const int x) { return -x * x + 9 * x; }), 4);
323}
324
325static void group_ids_to_indices_test(const Span<int> ids, const IndexMask &mask)
326{
327 /* Compare with the simpler #VectorSet implementation. */
328 VectorSet<int> expected_ids;
329 Vector<int> expected_first_indices;
330 Vector<int> expected_group_indices;
331 mask.foreach_index([&](const int i) {
332 if (expected_ids.add(ids[i])) {
333 expected_first_indices.append(i);
334 }
335 expected_group_indices.append(expected_ids.index_of(ids[i]));
336 });
337
338 Array<int> group_indices(mask.size());
339 Vector<int> first_indices;
340 const int groups_num = array_utils::group_ids_to_indices(
341 ids, mask, group_indices, &first_indices);
342 EXPECT_EQ(groups_num, expected_ids.size());
343 EXPECT_EQ(first_indices.as_span(), expected_first_indices.as_span());
344 Array<int> group_indices_only(mask.size());
345 EXPECT_EQ(array_utils::group_ids_to_indices(ids, mask, group_indices_only), groups_num);
346 EXPECT_EQ(group_indices_only.as_span(), expected_group_indices.as_span());
347 EXPECT_EQ(group_indices.as_span(), expected_group_indices.as_span());
348}
349
350TEST(array_utils, GroupIdsToIndicesEmpty)
351{
353}
354
355TEST(array_utils, GroupIdsToIndicesDense)
356{
357 const std::array ids{5, 3, 5, -2, 3, 3, 0, -2};
358 group_ids_to_indices_test(ids, IndexMask(ids.size()));
359}
360
361TEST(array_utils, GroupIdsToIndicesSparse)
362{
363 const std::array ids{1000000, 3, 1000000, -2000000, 3, 7};
364 group_ids_to_indices_test(ids, IndexMask(ids.size()));
365}
366
367TEST(array_utils, GroupIdsToIndicesMask)
368{
369 const std::array ids{4, 1, 4, 2, 1, 2, 4, 3};
370 IndexMaskMemory memory;
371 group_ids_to_indices_test(ids, IndexMask::from_indices<int>({1, 2, 5, 6, 7}, memory));
372}
373
374TEST(array_utils, GroupIdsToIndicesLarge)
375{
376 Array<int> dense_ids(100000);
377 Array<int> sparse_ids(100000);
378 for (const int i : dense_ids.index_range()) {
379 dense_ids[i] = (i * 7919) % 20011;
380 sparse_ids[i] = ((i * 7919) % 1009) * 1000003;
381 }
382 IndexMaskMemory memory;
384 dense_ids.index_range(), memory, [](const int i) { return i % 3 != 0; });
385 group_ids_to_indices_test(dense_ids, IndexMask(dense_ids.size()));
387 group_ids_to_indices_test(sparse_ids, IndexMask(sparse_ids.size()));
388 group_ids_to_indices_test(sparse_ids, mask);
389}
390
391} // namespace blender
Generic array manipulation API.
#define BLI_array_reverse(arr, arr_len)
#define BLI_array_findindex(arr, arr_len, p)
#define BLI_array_rfindindex(arr, arr_len, p)
#define BINARY_OR_TEST(data_cmp, data_a, data_b, data_combine, length)
#define STACK_PUSH_AND_CHECK_FORWARD(v, i)
#define DEDUPLICATE_ORDERED_TEST(data, data_cmp)
#define STACK_PUSH_AND_CHECK_BOTH(v, i)
#define STACK_PUSH_AND_CHECK_BACKWARD(v, i)
#define BINARY_AND_TEST(data_cmp, data_a, data_b, data_combine, length)
#define STACK_POP(stack)
#define STACK_DECLARE(stack)
#define STACK_INIT(stack, stack_num)
int64_t size() const
Definition BLI_array.hh:267
Span< T > as_span() const
Definition BLI_array.hh:254
IndexRange index_range() const
Definition BLI_array.hh:371
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange()=default
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr Span()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
static VArray from_func(const int64_t size, GetFunc get_func)
static VArray from_span(Span< T > values)
bool add(const Key &key)
int64_t size() const
int64_t index_of(const Key &key) const
int64_t size() const
void append(const T &value)
Span< T > as_span() const
#define EXPECT_TRUE(result)
Vector< IndexRange > find_all_ranges(const Span< T > span, const T &value)
std::optional< int64_t > max_element_index(const Span< T > &span, const int64_t grain_size=8192)
int group_ids_to_indices(Span< int > ids, const IndexMask &mask, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices=nullptr)
BMesh Iterators.
static void find_all_ranges_test(const Span< bool > data, const Span< IndexRange > data_cmp)
TEST(array_store, Nop)
BMesh const char void * data
static void find_max_element_test(const VArray< int > &values, const std::optional< int64_t > expect_index)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
static void group_ids_to_indices_test(const Span< int > ids, const IndexMask &mask)