Blender V5.3
BLI_vector_set_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
6#include "BLI_vector_set.hh"
7
8#include "testing/testing.h"
9
10#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
11
12namespace blender::tests {
13
14TEST(vector_set, DefaultConstructor)
15{
17 EXPECT_EQ(set.size(), 0);
18 EXPECT_TRUE(set.is_empty());
19}
20
21TEST(vector_set, InitializerListConstructor_WithoutDuplicates)
22{
23 VectorSet<int> set = {1, 4, 5};
24 EXPECT_EQ(set.size(), 3);
25 EXPECT_EQ(set[0], 1);
26 EXPECT_EQ(set[1], 4);
27 EXPECT_EQ(set[2], 5);
28 VectorSet<int> set_bigger_than_inline = {1, 4, 5, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19};
29 EXPECT_EQ(set_bigger_than_inline.size(), 14);
30 EXPECT_EQ(set_bigger_than_inline[0], 1);
31 EXPECT_EQ(set_bigger_than_inline[1], 4);
32 EXPECT_EQ(set_bigger_than_inline[2], 5);
33 EXPECT_EQ(set_bigger_than_inline.as_span().last(), 19);
34}
35
36TEST(vector_set, InitializerListConstructor_WithDuplicates)
37{
38 VectorSet<int> set = {1, 3, 3, 2, 1, 5};
39 EXPECT_EQ(set.size(), 4);
40 EXPECT_EQ(set[0], 1);
41 EXPECT_EQ(set[1], 3);
42 EXPECT_EQ(set[2], 2);
43 EXPECT_EQ(set[3], 5);
44}
45
46TEST(vector_set, Copy)
47{
48 VectorSet<int> set1 = {1, 2, 3};
49 VectorSet<int> set2 = set1;
50 EXPECT_EQ(set1.size(), 3);
51 EXPECT_EQ(set2.size(), 3);
52 EXPECT_EQ(set1.index_of(2), 1);
53 EXPECT_EQ(set2.index_of(2), 1);
54}
55
56TEST(vector_set, CopyAssignment)
57{
58 VectorSet<int> set1 = {1, 2, 3};
59 VectorSet<int> set2 = {};
60 set2 = set1;
61 EXPECT_EQ(set1.size(), 3);
62 EXPECT_EQ(set2.size(), 3);
63 EXPECT_EQ(set1.index_of(2), 1);
64 EXPECT_EQ(set2.index_of(2), 1);
65}
66
67TEST(vector_set, Move)
68{
69 {
70 VectorSet<int> set1 = {1, 2, 3};
71 VectorSet<int> set2 = std::move(set1);
72 EXPECT_EQ(set1.size(), 0); /* NOLINT: bugprone-use-after-move */
73 EXPECT_EQ(set2.size(), 3);
74 }
75 {
76 VectorSet<int, 24> set1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
77 VectorSet<int> set2 = std::move(set1);
78 EXPECT_EQ(set1.size(), 0); /* NOLINT: bugprone-use-after-move */
79 EXPECT_EQ(set2.size(), 9);
80 }
81}
82
83TEST(vector_set, MoveNonInline)
84{
85 VectorSet<int> set1 = {1, 2, 3, 5, 1, 6, 7, 8, 1, 4, 57, 8, 7, 34, 57, 8, 1231};
86 VectorSet<int> set2 = std::move(set1);
87 EXPECT_EQ(set1.size(), 0); /* NOLINT: bugprone-use-after-move */
88 EXPECT_EQ(set2.size(), 11);
89}
90
91TEST(vector_set, MoveAssignment)
92{
93 VectorSet<int> set1 = {1, 2, 3};
94 VectorSet<int> set2 = {};
95 set2 = std::move(set1);
96 EXPECT_EQ(set1.size(), 0); /* NOLINT: bugprone-use-after-move */
97 EXPECT_EQ(set2.size(), 3);
98}
99
100TEST(vector_set, AddNewIncreasesSize)
101{
102 VectorSet<int> set;
103 EXPECT_TRUE(set.is_empty());
104 EXPECT_EQ(set.size(), 0);
105 set.add(5);
106 EXPECT_FALSE(set.is_empty());
107 EXPECT_EQ(set.size(), 1);
108}
109
110TEST(vector_set, AddExistingDoesNotIncreaseSize)
111{
112 VectorSet<int> set;
113 EXPECT_EQ(set.size(), 0);
114 EXPECT_TRUE(set.add(5));
115 EXPECT_EQ(set.size(), 1);
116 EXPECT_FALSE(set.add(5));
117 EXPECT_EQ(set.size(), 1);
118}
119
120TEST(vector_set, Index)
121{
122 VectorSet<int> set = {3, 6, 4};
123 EXPECT_EQ(set.index_of(6), 1);
124 EXPECT_EQ(set.index_of(3), 0);
125 EXPECT_EQ(set.index_of(4), 2);
126}
127
128TEST(vector_set, IndexTry)
129{
130 VectorSet<int> set = {3, 6, 4};
131 EXPECT_EQ(set.index_of_try(5), -1);
132 EXPECT_EQ(set.index_of_try(3), 0);
133 EXPECT_EQ(set.index_of_try(6), 1);
134 EXPECT_EQ(set.index_of_try(2), -1);
135}
136
137TEST(vector_set, RemoveContained)
138{
139 VectorSet<int> set = {4, 5, 6, 7};
140 EXPECT_EQ(set.size(), 4);
141 set.remove_contained(5);
142 EXPECT_EQ(set.size(), 3);
143 EXPECT_EQ(set[0], 4);
144 EXPECT_EQ(set[1], 7);
145 EXPECT_EQ(set[2], 6);
146 set.remove_contained(6);
147 EXPECT_EQ(set.size(), 2);
148 EXPECT_EQ(set[0], 4);
149 EXPECT_EQ(set[1], 7);
150 set.remove_contained(4);
151 EXPECT_EQ(set.size(), 1);
152 EXPECT_EQ(set[0], 7);
153 set.remove_contained(7);
154 EXPECT_EQ(set.size(), 0);
155}
156
157TEST(vector_set, RemoveIf)
158{
160 for (const int64_t i : IndexRange(100)) {
161 set.add(i * i);
162 }
163 const int64_t removed = set.remove_if([](const int64_t key) { return key % 2 == 0; });
164 EXPECT_EQ(set.size() + removed, 100);
165 for (const int64_t i : IndexRange(100)) {
166 EXPECT_EQ(set.contains(i * i), i % 2 == 1);
167 }
168}
169
170TEST(vector_set, AddMultipleTimes)
171{
172 VectorSet<int> set;
173 for (int i = 0; i < 100; i++) {
174 EXPECT_FALSE(set.contains(i * 13));
175 set.add(i * 12);
176 set.add(i * 13);
177 EXPECT_TRUE(set.contains(i * 13));
178 }
179}
180
181TEST(vector_set, UniquePtrValue)
182{
184 set.add_new(std::make_unique<int>());
185 set.add(std::make_unique<int>());
186 set.index_of_try(std::make_unique<int>());
187 std::unique_ptr<int> value = set.pop();
188 UNUSED_VARS(value);
189}
190
191TEST(vector_set, Remove)
192{
193 VectorSet<int> set;
194 EXPECT_TRUE(set.add(5));
195 EXPECT_TRUE(set.contains(5));
196 EXPECT_FALSE(set.remove(6));
197 EXPECT_TRUE(set.contains(5));
198 EXPECT_TRUE(set.remove(5));
199 EXPECT_FALSE(set.contains(5));
200 EXPECT_FALSE(set.remove(5));
201 EXPECT_FALSE(set.contains(5));
202}
203
204TEST(vector_set, OrderPreservation)
205{
206 Vector<int> ref_vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
207 VectorSet<int> set = {ref_vec.as_span().take_front(5)};
208 EXPECT_EQ(set.as_span(), ref_vec.as_span().take_front(5));
209
210 /* Only adding items always preserve to full order. */
211 set.add(ref_vec[5]);
212 set.add_multiple(ref_vec.as_span().slice(6, 4));
213 EXPECT_EQ(set.as_span(), ref_vec.as_span());
214
215 /* Removing items and adding others should not affect the order of items added before the oldest
216 * removed one. */
217 set.remove(ref_vec[8]);
218 EXPECT_NE(set.as_span(), ref_vec.as_span());
219 EXPECT_EQ(set.as_span().take_front(8), ref_vec.as_span().take_front(8));
220
221 set.remove(ref_vec[5]);
222 EXPECT_EQ(set.as_span().take_front(5), ref_vec.as_span().take_front(5));
223
224 set.add(ref_vec[5]);
225 set.add(ref_vec[8]);
226 EXPECT_NE(set.as_span(), ref_vec.as_span());
227 EXPECT_EQ(set.as_span().take_front(5), ref_vec.as_span().take_front(5));
228
229 /* Add enough elements to ensure that some re-allocation happens in the VectorSet. */
230 for (int i = 10; i < 1000; i++) {
231 set.add(i);
232 }
233 EXPECT_EQ(set.as_span().take_front(5), ref_vec.as_span().take_front(5));
234}
235
236TEST(vector_set, SpanConstructorExceptions)
237{
238 std::array<ExceptionThrower, 5> array = {1, 2, 3, 4, 5};
239 array[3].throw_during_copy = true;
241
242 EXPECT_ANY_THROW({ VectorSet<ExceptionThrower> set(span); });
243}
244
245TEST(vector_set, CopyConstructorExceptions)
246{
247 VectorSet<ExceptionThrower> set = {1, 2, 3, 4, 5};
248 set[3].throw_during_copy = true;
249
250 EXPECT_ANY_THROW({ VectorSet<ExceptionThrower> set_copy(set); });
251}
252
253TEST(vector_set, MoveConstructorExceptions)
254{
255 VectorSet<ExceptionThrower> set = {1, 2, 3, 4, 5};
256 set[3].throw_during_copy = true;
257 set[3].throw_during_move = true;
258 /* Currently never throws on move, because values are separately allocated. */
259 VectorSet<ExceptionThrower> set_moved(std::move(set));
260 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
261 set.add_multiple({4, 5, 6, 7, 8});
262 EXPECT_EQ(set.size(), 5);
263}
264
265TEST(vector_set, AddNewExceptions)
266{
268 ExceptionThrower value;
269 value.throw_during_copy = true;
270 EXPECT_ANY_THROW({ set.add_new(value); });
271 EXPECT_EQ(set.size(), 0);
272 EXPECT_ANY_THROW({ set.add_new(value); });
273 EXPECT_EQ(set.size(), 0);
274}
275
276TEST(vector_set, AddExceptions)
277{
279 ExceptionThrower value;
280 value.throw_during_copy = true;
281 EXPECT_ANY_THROW({ set.add(value); });
282 EXPECT_EQ(set.size(), 0);
283 EXPECT_ANY_THROW({ set.add(value); });
284 EXPECT_EQ(set.size(), 0);
285}
286
287TEST(vector_set, ReserveExceptions)
288{
290 set.add_multiple({1, 2, 3, 4, 5});
291 set[2].throw_during_move = true;
292 EXPECT_ANY_THROW({ set.reserve(100); });
293}
294
295TEST(vector_set, PopExceptions)
296{
297 VectorSet<ExceptionThrower> set = {1, 2, 3};
298 set.as_span().last().throw_during_move = true;
299 EXPECT_EQ(set.size(), 3);
300 EXPECT_ANY_THROW({ set.pop(); }); /* NOLINT: bugprone-throw-keyword-missing */
301 EXPECT_EQ(set.size(), 3);
302 set.add(10);
303 EXPECT_EQ(set.size(), 4);
304}
305
306TEST(vector_set, IndexOfOrAdd)
307{
308 VectorSet<int> set;
309 EXPECT_EQ(set.index_of_or_add(3), 0);
310 EXPECT_EQ(set.index_of_or_add(3), 0);
311 EXPECT_EQ(set.index_of_or_add(2), 1);
312 EXPECT_EQ(set.index_of_or_add(0), 2);
313 EXPECT_EQ(set.index_of_or_add(2), 1);
314 EXPECT_EQ(set.index_of_or_add(3), 0);
315 EXPECT_EQ(set.index_of_or_add(5), 3);
316 EXPECT_EQ(set.index_of_or_add(8), 4);
317 EXPECT_EQ(set.index_of_or_add(5), 3);
318}
319
320TEST(vector_set, Clear)
321{
322 VectorSet<int> set = {4, 6, 2, 4};
323 EXPECT_EQ(set.size(), 3);
324 set.clear();
325 EXPECT_EQ(set.size(), 0);
326 set.add_multiple({4, 1, 6, 8, 3, 6, 9, 3});
327 EXPECT_EQ(set.size(), 6);
328 set.clear();
329 EXPECT_EQ(set.size(), 0);
330}
331
332TEST(vector_set, LookupKey)
333{
335 set.add("a");
336 set.add("b");
337 set.add("c");
338 EXPECT_EQ(set.lookup_key("a"), "a");
339 EXPECT_EQ(set.lookup_key_as("c"), "c");
340 EXPECT_EQ(set.lookup_key_ptr_as("d"), nullptr);
341 EXPECT_EQ(set.lookup_key_ptr_as("b")->size(), 1);
342 EXPECT_EQ(set.lookup_key_ptr("a"), set.lookup_key_ptr_as("a"));
343 EXPECT_EQ(set.lookup_key_default("d", "default"), "default");
344 EXPECT_EQ(set.lookup_key_default("c", "default"), "c");
345}
346
347TEST(vector_set, GrowWhenEmpty)
348{
349 /* Tests that the internal keys array is freed correctly when growing an empty set. */
350 VectorSet<int> set;
351 set.add(4);
352 set.remove(4);
353 EXPECT_TRUE(set.is_empty());
354 set.reserve(100);
355}
356
357TEST(vector_set, ExtractVector)
358{
359 VectorSet<int> set;
360 set.add_multiple({5, 2, 7, 4, 8, 5, 4, 5});
361 EXPECT_EQ(set.size(), 5);
362 const int *data_ptr = set.data();
363
364 Vector<int> vec = set.extract_vector();
365 EXPECT_EQ(vec.size(), 5);
366 EXPECT_EQ(vec.data(), data_ptr);
367 EXPECT_TRUE(set.is_empty());
368}
369
370TEST(vector_set, ExtractVectorInline)
371{
373 set.add_multiple({5, 2, 7, 4, 8, 5, 4, 5});
374 EXPECT_EQ(set.size(), 5);
375
376 Vector<int> vec = set.extract_vector();
377 EXPECT_EQ(vec.size(), 5);
378 EXPECT_EQ(vec[2], 7);
379 EXPECT_TRUE(set.is_empty());
380}
381
382TEST(vector_set, ExtractVectorInlineExceptions)
383{
385 set.add_multiple({5, 2, 7, 4, 8, 5, 4, 5});
386 set[3].throw_during_copy = true;
387 set[3].throw_during_move = true;
388 EXPECT_EQ(set.size(), 5);
389
390 EXPECT_ANY_THROW({ Vector<ExceptionThrower> vec = set.extract_vector(); });
391 EXPECT_EQ(set.size(), 5);
392}
393
394TEST(vector_set, ExtractVectorEmpty)
395{
396 VectorSet<int> set;
397 Vector<int> vec = set.extract_vector();
398 EXPECT_TRUE(vec.is_empty());
399}
400
402{
403 struct ThingWithID {
404 int a;
405 std::string b;
406 int c;
407 };
408 struct ThingGetter {
409 StringRef operator()(const ThingWithID &value) const
410 {
411 return value.b;
412 }
413 };
415 set.add_new(ThingWithID{0, "test", 54});
416 EXPECT_TRUE(set.contains_as("test"));
417 set.add_new(ThingWithID{4333, "other", 2});
418 EXPECT_EQ(set.size(), 2);
419 set.add(ThingWithID{3333, "test", 27});
420 EXPECT_EQ(set.size(), 2);
421
422 /* Add more elements than the inline capacity. */
424 larger_set.add_new(ThingWithID{12, "test", 9});
425 EXPECT_EQ(larger_set.index_of_as("test"), 0);
426 larger_set.add_new(ThingWithID{123, "other", 8});
427 larger_set.add(ThingWithID{1234, "test", 7});
428 larger_set.add_new(ThingWithID{12345, "test_2", 6});
429 larger_set.add_new(ThingWithID{123456, "test_4", 5});
430 larger_set.add_new(ThingWithID{1234567, "test_5", 4});
431 EXPECT_EQ(larger_set.index_of_as("test_4"), 3);
432 larger_set.add_new(ThingWithID{12345678, "test_6", 3});
433 EXPECT_TRUE(larger_set.size() == 6);
434}
435
436TEST(vector_set, CustomIDVectorSetMove)
437{
438
439 struct ThingWithID {
440 int a;
441 std::string b;
442 int c;
443 };
444 struct ThingGetter {
445 StringRef operator()(const std::unique_ptr<ThingWithID> &value) const
446 {
447 return value->b;
448 }
449 };
451 set.add(std::make_unique<ThingWithID>(ThingWithID{1, "hug", 2}));
452 set.add(std::make_unique<ThingWithID>(ThingWithID{2, "a", 2}));
453 set.add(std::make_unique<ThingWithID>(ThingWithID{3, "bug", 4}));
454 auto set_new = std::move(set);
455 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
456 EXPECT_EQ(set_new.size(), 3);
457}
458
459namespace {
460struct KeyWithData {
461 int key;
462 std::string data;
463
464 KeyWithData(int key, std::string data) : key(key), data(data) {}
465 KeyWithData(const StringRef data) : key(0), data(data) {}
466
467 uint64_t hash() const
468 {
469 return uint64_t(this->key);
470 }
471
472 friend bool operator==(const KeyWithData &a, const KeyWithData &b)
473 {
474 return a.key == b.key;
475 }
476};
477} // namespace
478
479TEST(vector_set, AddOverwrite)
480{
482 EXPECT_TRUE(set.add_overwrite(KeyWithData{1, "a"}));
483 EXPECT_EQ(set.size(), 1);
484 EXPECT_EQ(set[0].data, "a");
485 EXPECT_FALSE(set.add(KeyWithData{1, "b"}));
486 EXPECT_EQ(set.size(), 1);
487 EXPECT_EQ(set[0].data, "a");
488 EXPECT_EQ(set.lookup_key(KeyWithData{1, "_"}).data, "a");
489 EXPECT_FALSE(set.add_overwrite(KeyWithData{1, "c"}));
490 EXPECT_EQ(set.size(), 1);
491 EXPECT_EQ(set[0].data, "c");
492 EXPECT_EQ(set.lookup_key(KeyWithData{1, "_"}).data, "c");
493
494 const KeyWithData key{2, "d"};
495 EXPECT_TRUE(set.add_overwrite(key));
496 EXPECT_EQ(set.size(), 2);
497 EXPECT_EQ(set[0].data, "c");
498 EXPECT_EQ(set[1].data, "d");
499 EXPECT_EQ(set.lookup_key(key).data, "d");
500}
501
502TEST(vector_set, LookupDefault)
503{
505 EXPECT_TRUE(set.add(KeyWithData{1, "b"}));
506 EXPECT_TRUE(set.add(KeyWithData{423, "s"}));
507 EXPECT_TRUE(set.add(KeyWithData{2, "t"}));
508 KeyWithData default_key{1, "default"};
509 EXPECT_EQ(set.lookup_key_default(KeyWithData{1221, "3"}, default_key), default_key);
510 KeyWithData other_s{0, "testing"};
511 EXPECT_EQ(set.lookup_key_default(KeyWithData{2398745, "fffff"}, StringRef("testing")), other_s);
512 EXPECT_EQ(set.lookup_key_default(KeyWithData{1, "s"}, StringRef("testing")), set[0]);
513 EXPECT_EQ(set.lookup_key_default(KeyWithData{2, "t"}, {1, "default"}), set[2]);
514}
515
516} // namespace blender::tests
#define UNUSED_VARS(...)
SIMD_FORCE_INLINE btVector3 operator()(const btVector3 &x) const
Return the transform of the vector.
Definition btTransform.h:90
constexpr IndexRange()=default
int64_t index_of_try(const Key &key) const
const Key & lookup_key_as(const ForwardKey &key) const
bool contains_as(const ForwardKey &key) const
const Key * data() const
bool remove(const Key &key)
bool add(const Key &key)
int64_t index_of_as(const ForwardKey &key) const
const Key * lookup_key_ptr(const Key &key) const
int64_t index_of_or_add(const Key &key)
const Key & lookup_key(const Key &key) const
const Key * lookup_key_ptr_as(const ForwardKey &key) const
Key lookup_key_default(const Key &key, const Key &default_value) const
void reserve(const int64_t n)
void add_multiple(Span< Key > keys)
int64_t size() const
bool add_overwrite(const Key &key)
int64_t index_of(const Key &key) const
bool contains(const Key &key) const
int64_t remove_if(Predicate &&predicate)
Span< Key > as_span() const
void add_new(const Key &key)
void remove_contained(const Key &key)
int64_t size() const
bool is_empty() const
Span< T > as_span() const
#define EXPECT_FALSE(result)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
bool operator==(const Error &left, const Error &right)
TEST(any_virtual, DefaultConstructor)
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
BMesh const char void * data
VectorSet< T, InlineBufferCapacity, DefaultProbingStrategy, CustomIDHash< T, GetIDFn >, CustomIDEqual< T, GetIDFn > > CustomIDVectorSet
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
#define hash
Definition noise_c.cc:156