1 /* Apache License, Version 2.0 */
2
3 #include <set>
4 #include <unordered_set>
5
6 #include "BLI_exception_safety_test_utils.hh"
7 #include "BLI_ghash.h"
8 #include "BLI_rand.h"
9 #include "BLI_set.hh"
10 #include "BLI_strict_flags.h"
11 #include "BLI_timeit.hh"
12 #include "BLI_vector.hh"
13 #include "testing/testing.h"
14
15 namespace blender {
16 namespace tests {
17
TEST(set,DefaultConstructor)18 TEST(set, DefaultConstructor)
19 {
20 Set<int> set;
21 EXPECT_EQ(set.size(), 0);
22 EXPECT_TRUE(set.is_empty());
23 }
24
TEST(set,ContainsNotExistant)25 TEST(set, ContainsNotExistant)
26 {
27 Set<int> set;
28 EXPECT_FALSE(set.contains(3));
29 }
30
TEST(set,ContainsExistant)31 TEST(set, ContainsExistant)
32 {
33 Set<int> set;
34 EXPECT_FALSE(set.contains(5));
35 EXPECT_TRUE(set.is_empty());
36 set.add(5);
37 EXPECT_TRUE(set.contains(5));
38 EXPECT_FALSE(set.is_empty());
39 }
40
TEST(set,AddMany)41 TEST(set, AddMany)
42 {
43 Set<int> set;
44 for (int i = 0; i < 100; i++) {
45 set.add(i);
46 }
47
48 for (int i = 50; i < 100; i++) {
49 EXPECT_TRUE(set.contains(i));
50 }
51 for (int i = 100; i < 150; i++) {
52 EXPECT_FALSE(set.contains(i));
53 }
54 }
55
TEST(set,InitializerListConstructor)56 TEST(set, InitializerListConstructor)
57 {
58 Set<int> set = {4, 5, 6};
59 EXPECT_EQ(set.size(), 3);
60 EXPECT_TRUE(set.contains(4));
61 EXPECT_TRUE(set.contains(5));
62 EXPECT_TRUE(set.contains(6));
63 EXPECT_FALSE(set.contains(2));
64 EXPECT_FALSE(set.contains(3));
65 }
66
TEST(set,CopyConstructor)67 TEST(set, CopyConstructor)
68 {
69 Set<int> set = {3};
70 EXPECT_TRUE(set.contains(3));
71 EXPECT_FALSE(set.contains(4));
72
73 Set<int> set2(set);
74 set2.add(4);
75 EXPECT_TRUE(set2.contains(3));
76 EXPECT_TRUE(set2.contains(4));
77
78 EXPECT_FALSE(set.contains(4));
79 }
80
TEST(set,MoveConstructor)81 TEST(set, MoveConstructor)
82 {
83 Set<int> set = {1, 2, 3};
84 EXPECT_EQ(set.size(), 3);
85 Set<int> set2(std::move(set));
86 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
87 EXPECT_EQ(set2.size(), 3);
88 }
89
TEST(set,CopyAssignment)90 TEST(set, CopyAssignment)
91 {
92 Set<int> set = {3};
93 EXPECT_TRUE(set.contains(3));
94 EXPECT_FALSE(set.contains(4));
95
96 Set<int> set2;
97 set2 = set;
98 set2.add(4);
99 EXPECT_TRUE(set2.contains(3));
100 EXPECT_TRUE(set2.contains(4));
101
102 EXPECT_FALSE(set.contains(4));
103 }
104
TEST(set,MoveAssignment)105 TEST(set, MoveAssignment)
106 {
107 Set<int> set = {1, 2, 3};
108 EXPECT_EQ(set.size(), 3);
109 Set<int> set2;
110 set2 = std::move(set);
111 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
112 EXPECT_EQ(set2.size(), 3);
113 }
114
TEST(set,RemoveContained)115 TEST(set, RemoveContained)
116 {
117 Set<int> set = {3, 4, 5};
118 EXPECT_TRUE(set.contains(3));
119 EXPECT_TRUE(set.contains(4));
120 EXPECT_TRUE(set.contains(5));
121 set.remove_contained(4);
122 EXPECT_TRUE(set.contains(3));
123 EXPECT_FALSE(set.contains(4));
124 EXPECT_TRUE(set.contains(5));
125 set.remove_contained(3);
126 EXPECT_FALSE(set.contains(3));
127 EXPECT_FALSE(set.contains(4));
128 EXPECT_TRUE(set.contains(5));
129 set.remove_contained(5);
130 EXPECT_FALSE(set.contains(3));
131 EXPECT_FALSE(set.contains(4));
132 EXPECT_FALSE(set.contains(5));
133 }
134
TEST(set,RemoveContainedMany)135 TEST(set, RemoveContainedMany)
136 {
137 Set<int> set;
138 for (int i = 0; i < 1000; i++) {
139 set.add(i);
140 }
141 for (int i = 100; i < 1000; i++) {
142 set.remove_contained(i);
143 }
144 for (int i = 900; i < 1000; i++) {
145 set.add(i);
146 }
147
148 for (int i = 0; i < 1000; i++) {
149 if (i < 100 || i >= 900) {
150 EXPECT_TRUE(set.contains(i));
151 }
152 else {
153 EXPECT_FALSE(set.contains(i));
154 }
155 }
156 }
157
TEST(set,Intersects)158 TEST(set, Intersects)
159 {
160 Set<int> a = {3, 4, 5, 6};
161 Set<int> b = {1, 2, 5};
162 EXPECT_TRUE(Set<int>::Intersects(a, b));
163 EXPECT_FALSE(Set<int>::Disjoint(a, b));
164 }
165
TEST(set,Disjoint)166 TEST(set, Disjoint)
167 {
168 Set<int> a = {5, 6, 7, 8};
169 Set<int> b = {2, 3, 4, 9};
170 EXPECT_FALSE(Set<int>::Intersects(a, b));
171 EXPECT_TRUE(Set<int>::Disjoint(a, b));
172 }
173
TEST(set,AddMultiple)174 TEST(set, AddMultiple)
175 {
176 Set<int> a;
177 a.add_multiple({5, 7});
178 EXPECT_TRUE(a.contains(5));
179 EXPECT_TRUE(a.contains(7));
180 EXPECT_FALSE(a.contains(4));
181 a.add_multiple({2, 4, 7});
182 EXPECT_TRUE(a.contains(4));
183 EXPECT_TRUE(a.contains(2));
184 EXPECT_EQ(a.size(), 4);
185 }
186
TEST(set,AddMultipleNew)187 TEST(set, AddMultipleNew)
188 {
189 Set<int> a;
190 a.add_multiple_new({5, 6});
191 EXPECT_TRUE(a.contains(5));
192 EXPECT_TRUE(a.contains(6));
193 }
194
TEST(set,Iterator)195 TEST(set, Iterator)
196 {
197 Set<int> set = {1, 3, 2, 5, 4};
198 blender::Vector<int> vec;
199 for (int value : set) {
200 vec.append(value);
201 }
202 EXPECT_EQ(vec.size(), 5);
203 EXPECT_TRUE(vec.contains(1));
204 EXPECT_TRUE(vec.contains(3));
205 EXPECT_TRUE(vec.contains(2));
206 EXPECT_TRUE(vec.contains(5));
207 EXPECT_TRUE(vec.contains(4));
208 }
209
TEST(set,OftenAddRemoveContained)210 TEST(set, OftenAddRemoveContained)
211 {
212 Set<int> set;
213 for (int i = 0; i < 100; i++) {
214 set.add(42);
215 EXPECT_EQ(set.size(), 1);
216 set.remove_contained(42);
217 EXPECT_EQ(set.size(), 0);
218 }
219 }
220
TEST(set,UniquePtrValues)221 TEST(set, UniquePtrValues)
222 {
223 Set<std::unique_ptr<int>> set;
224 set.add_new(std::unique_ptr<int>(new int()));
225 auto value1 = std::unique_ptr<int>(new int());
226 set.add_new(std::move(value1));
227 set.add(std::unique_ptr<int>(new int()));
228
229 EXPECT_EQ(set.size(), 3);
230 }
231
TEST(set,Clear)232 TEST(set, Clear)
233 {
234 Set<int> set = {3, 4, 6, 7};
235 EXPECT_EQ(set.size(), 4);
236 set.clear();
237 EXPECT_EQ(set.size(), 0);
238 }
239
TEST(set,StringSet)240 TEST(set, StringSet)
241 {
242 Set<std::string> set;
243 set.add("hello");
244 set.add("world");
245 EXPECT_EQ(set.size(), 2);
246 EXPECT_TRUE(set.contains("hello"));
247 EXPECT_TRUE(set.contains("world"));
248 EXPECT_FALSE(set.contains("world2"));
249 }
250
TEST(set,PointerSet)251 TEST(set, PointerSet)
252 {
253 int a, b, c;
254 Set<int *> set;
255 set.add(&a);
256 set.add(&b);
257 EXPECT_EQ(set.size(), 2);
258 EXPECT_TRUE(set.contains(&a));
259 EXPECT_TRUE(set.contains(&b));
260 EXPECT_FALSE(set.contains(&c));
261 }
262
TEST(set,Remove)263 TEST(set, Remove)
264 {
265 Set<int> set = {1, 2, 3, 4, 5, 6};
266 EXPECT_EQ(set.size(), 6);
267 EXPECT_TRUE(set.remove(2));
268 EXPECT_EQ(set.size(), 5);
269 EXPECT_FALSE(set.contains(2));
270 EXPECT_FALSE(set.remove(2));
271 EXPECT_EQ(set.size(), 5);
272 EXPECT_TRUE(set.remove(5));
273 EXPECT_EQ(set.size(), 4);
274 }
275
276 struct Type1 {
277 uint32_t value;
278 };
279
280 struct Type2 {
281 uint32_t value;
282 };
283
operator ==(const Type1 & a,const Type1 & b)284 static bool operator==(const Type1 &a, const Type1 &b)
285 {
286 return a.value == b.value;
287 }
operator ==(const Type2 & a,const Type1 & b)288 static bool operator==(const Type2 &a, const Type1 &b)
289 {
290 return a.value == b.value;
291 }
292
293 } // namespace tests
294
295 /* This has to be defined in ::blender namespace. */
296 template<> struct DefaultHash<tests::Type1> {
operator ()blender::DefaultHash297 uint32_t operator()(const tests::Type1 &value) const
298 {
299 return value.value;
300 }
301
operator ()blender::DefaultHash302 uint32_t operator()(const tests::Type2 &value) const
303 {
304 return value.value;
305 }
306 };
307
308 namespace tests {
309
TEST(set,ContainsAs)310 TEST(set, ContainsAs)
311 {
312 Set<Type1> set;
313 set.add(Type1{5});
314 EXPECT_TRUE(set.contains_as(Type1{5}));
315 EXPECT_TRUE(set.contains_as(Type2{5}));
316 EXPECT_FALSE(set.contains_as(Type1{6}));
317 EXPECT_FALSE(set.contains_as(Type2{6}));
318 }
319
TEST(set,ContainsAsString)320 TEST(set, ContainsAsString)
321 {
322 Set<std::string> set;
323 set.add("test");
324 EXPECT_TRUE(set.contains_as("test"));
325 EXPECT_TRUE(set.contains_as(StringRef("test")));
326 EXPECT_FALSE(set.contains_as("string"));
327 EXPECT_FALSE(set.contains_as(StringRef("string")));
328 }
329
TEST(set,RemoveContainedAs)330 TEST(set, RemoveContainedAs)
331 {
332 Set<Type1> set;
333 set.add(Type1{5});
334 EXPECT_TRUE(set.contains_as(Type2{5}));
335 set.remove_contained_as(Type2{5});
336 EXPECT_FALSE(set.contains_as(Type2{5}));
337 }
338
TEST(set,RemoveAs)339 TEST(set, RemoveAs)
340 {
341 Set<Type1> set;
342 set.add(Type1{5});
343 EXPECT_TRUE(set.contains_as(Type2{5}));
344 set.remove_as(Type2{6});
345 EXPECT_TRUE(set.contains_as(Type2{5}));
346 set.remove_as(Type2{5});
347 EXPECT_FALSE(set.contains_as(Type2{5}));
348 set.remove_as(Type2{5});
349 EXPECT_FALSE(set.contains_as(Type2{5}));
350 }
351
TEST(set,AddAs)352 TEST(set, AddAs)
353 {
354 Set<std::string> set;
355 EXPECT_TRUE(set.add_as("test"));
356 EXPECT_TRUE(set.add_as(StringRef("qwe")));
357 EXPECT_FALSE(set.add_as(StringRef("test")));
358 EXPECT_FALSE(set.add_as("qwe"));
359 }
360
361 template<uint N> struct EqualityIntModN {
operator ()blender::tests::EqualityIntModN362 bool operator()(uint a, uint b) const
363 {
364 return (a % N) == (b % N);
365 }
366 };
367
368 template<uint N> struct HashIntModN {
operator ()blender::tests::HashIntModN369 uint64_t operator()(uint value) const
370 {
371 return value % N;
372 }
373 };
374
TEST(set,CustomizeHashAndEquality)375 TEST(set, CustomizeHashAndEquality)
376 {
377 Set<uint, 0, DefaultProbingStrategy, HashIntModN<10>, EqualityIntModN<10>> set;
378 set.add(4);
379 EXPECT_TRUE(set.contains(4));
380 EXPECT_TRUE(set.contains(14));
381 EXPECT_TRUE(set.contains(104));
382 EXPECT_FALSE(set.contains(5));
383 set.add(55);
384 EXPECT_TRUE(set.contains(5));
385 EXPECT_TRUE(set.contains(14));
386 set.remove(1004);
387 EXPECT_FALSE(set.contains(14));
388 }
389
TEST(set,IntrusiveIntKey)390 TEST(set, IntrusiveIntKey)
391 {
392 Set<int,
393 2,
394 DefaultProbingStrategy,
395 DefaultHash<int>,
396 DefaultEquality,
397 IntegerSetSlot<int, 100, 200>>
398 set;
399 EXPECT_TRUE(set.add(4));
400 EXPECT_TRUE(set.add(3));
401 EXPECT_TRUE(set.add(11));
402 EXPECT_TRUE(set.add(8));
403 EXPECT_FALSE(set.add(3));
404 EXPECT_FALSE(set.add(4));
405 EXPECT_TRUE(set.remove(4));
406 EXPECT_FALSE(set.remove(7));
407 EXPECT_TRUE(set.add(4));
408 EXPECT_TRUE(set.remove(4));
409 }
410
411 struct MyKeyType {
412 uint32_t key;
413 int32_t attached_data;
414
hashblender::tests::MyKeyType415 uint64_t hash() const
416 {
417 return key;
418 }
419
operator ==(const MyKeyType & a,const MyKeyType & b)420 friend bool operator==(const MyKeyType &a, const MyKeyType &b)
421 {
422 return a.key == b.key;
423 }
424 };
425
TEST(set,LookupKey)426 TEST(set, LookupKey)
427 {
428 Set<MyKeyType> set;
429 set.add({1, 10});
430 set.add({2, 20});
431 EXPECT_EQ(set.lookup_key({1, 30}).attached_data, 10);
432 EXPECT_EQ(set.lookup_key({2, 0}).attached_data, 20);
433 }
434
TEST(set,LookupKeyDefault)435 TEST(set, LookupKeyDefault)
436 {
437 Set<MyKeyType> set;
438 set.add({1, 10});
439 set.add({2, 20});
440
441 MyKeyType fallback{5, 50};
442 EXPECT_EQ(set.lookup_key_default({1, 66}, fallback).attached_data, 10);
443 EXPECT_EQ(set.lookup_key_default({4, 40}, fallback).attached_data, 50);
444 }
445
TEST(set,LookupKeyPtr)446 TEST(set, LookupKeyPtr)
447 {
448 Set<MyKeyType> set;
449 set.add({1, 10});
450 set.add({2, 20});
451 EXPECT_EQ(set.lookup_key_ptr({1, 50})->attached_data, 10);
452 EXPECT_EQ(set.lookup_key_ptr({2, 50})->attached_data, 20);
453 EXPECT_EQ(set.lookup_key_ptr({3, 50}), nullptr);
454 }
455
TEST(set,LookupKeyOrAdd)456 TEST(set, LookupKeyOrAdd)
457 {
458 Set<MyKeyType> set;
459 set.add({1, 10});
460 set.add({2, 20});
461 EXPECT_EQ(set.size(), 2);
462 EXPECT_EQ(set.lookup_key_or_add({2, 40}).attached_data, 20);
463 EXPECT_EQ(set.size(), 2);
464 EXPECT_EQ(set.lookup_key_or_add({3, 40}).attached_data, 40);
465 EXPECT_EQ(set.size(), 3);
466 EXPECT_EQ(set.lookup_key_or_add({3, 60}).attached_data, 40);
467 EXPECT_EQ(set.size(), 3);
468 }
469
TEST(set,StringViewKeys)470 TEST(set, StringViewKeys)
471 {
472 Set<std::string_view> set;
473 set.add("hello");
474 set.add("world");
475 EXPECT_FALSE(set.contains("worlds"));
476 EXPECT_TRUE(set.contains("world"));
477 EXPECT_TRUE(set.contains("hello"));
478 }
479
TEST(set,SpanConstructorExceptions)480 TEST(set, SpanConstructorExceptions)
481 {
482 std::array<ExceptionThrower, 5> array = {1, 2, 3, 4, 5};
483 array[3].throw_during_copy = true;
484 Span<ExceptionThrower> span = array;
485
486 EXPECT_ANY_THROW({ Set<ExceptionThrower> set(span); });
487 }
488
TEST(set,CopyConstructorExceptions)489 TEST(set, CopyConstructorExceptions)
490 {
491 Set<ExceptionThrower> set = {1, 2, 3, 4, 5};
492 set.lookup_key(3).throw_during_copy = true;
493 EXPECT_ANY_THROW({ Set<ExceptionThrower> set_copy(set); });
494 }
495
TEST(set,MoveConstructorExceptions)496 TEST(set, MoveConstructorExceptions)
497 {
498 using SetType = Set<ExceptionThrower, 4>;
499 SetType set = {1, 2, 3};
500 set.lookup_key(2).throw_during_move = true;
501 EXPECT_ANY_THROW({ SetType set_moved(std::move(set)); });
502 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
503 set.add_multiple({3, 6, 7});
504 EXPECT_EQ(set.size(), 3);
505 }
506
TEST(set,AddNewExceptions)507 TEST(set, AddNewExceptions)
508 {
509 Set<ExceptionThrower> set;
510 ExceptionThrower value;
511 value.throw_during_copy = true;
512 EXPECT_ANY_THROW({ set.add_new(value); });
513 EXPECT_EQ(set.size(), 0);
514 EXPECT_ANY_THROW({ set.add_new(value); });
515 EXPECT_EQ(set.size(), 0);
516 }
517
TEST(set,AddExceptions)518 TEST(set, AddExceptions)
519 {
520 Set<ExceptionThrower> set;
521 ExceptionThrower value;
522 value.throw_during_copy = true;
523 EXPECT_ANY_THROW({ set.add(value); });
524 EXPECT_EQ(set.size(), 0);
525 EXPECT_ANY_THROW({ set.add(value); });
526 EXPECT_EQ(set.size(), 0);
527 }
528
529 /**
530 * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
531 */
532 #if 0
533 template<typename SetT>
534 BLI_NOINLINE void benchmark_random_ints(StringRef name, int amount, int factor)
535 {
536 RNG *rng = BLI_rng_new(0);
537 Vector<int> values;
538 for (int i = 0; i < amount; i++) {
539 values.append(BLI_rng_get_int(rng) * factor);
540 }
541 BLI_rng_free(rng);
542
543 SetT set;
544 {
545 SCOPED_TIMER(name + " Add");
546 for (int value : values) {
547 set.add(value);
548 }
549 }
550 int count = 0;
551 {
552 SCOPED_TIMER(name + " Contains");
553 for (int value : values) {
554 count += set.contains(value);
555 }
556 }
557 {
558 SCOPED_TIMER(name + " Remove");
559 for (int value : values) {
560 count += set.remove(value);
561 }
562 }
563
564 /* Print the value for simple error checking and to avoid some compiler optimizations. */
565 std::cout << "Count: " << count << "\n";
566 }
567
568 TEST(set, Benchmark)
569 {
570 for (int i = 0; i < 3; i++) {
571 benchmark_random_ints<blender::Set<int>>("blender::Set ", 100000, 1);
572 benchmark_random_ints<blender::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, 1);
573 }
574 std::cout << "\n";
575 for (int i = 0; i < 3; i++) {
576 uint32_t factor = (3 << 10);
577 benchmark_random_ints<blender::Set<int>>("blender::Set ", 100000, factor);
578 benchmark_random_ints<blender::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, factor);
579 }
580 }
581
582 /**
583 * Output of the rudimentary benchmark above on my hardware.
584 *
585 * Timer 'blender::Set Add' took 5.5573 ms
586 * Timer 'blender::Set Contains' took 0.807384 ms
587 * Timer 'blender::Set Remove' took 0.953436 ms
588 * Count: 199998
589 * Timer 'std::unordered_set Add' took 12.551 ms
590 * Timer 'std::unordered_set Contains' took 2.3323 ms
591 * Timer 'std::unordered_set Remove' took 5.07082 ms
592 * Count: 199998
593 * Timer 'blender::Set Add' took 2.62526 ms
594 * Timer 'blender::Set Contains' took 0.407499 ms
595 * Timer 'blender::Set Remove' took 0.472981 ms
596 * Count: 199998
597 * Timer 'std::unordered_set Add' took 6.26945 ms
598 * Timer 'std::unordered_set Contains' took 1.17236 ms
599 * Timer 'std::unordered_set Remove' took 3.77402 ms
600 * Count: 199998
601 * Timer 'blender::Set Add' took 2.59152 ms
602 * Timer 'blender::Set Contains' took 0.415254 ms
603 * Timer 'blender::Set Remove' took 0.477559 ms
604 * Count: 199998
605 * Timer 'std::unordered_set Add' took 6.28129 ms
606 * Timer 'std::unordered_set Contains' took 1.17562 ms
607 * Timer 'std::unordered_set Remove' took 3.77811 ms
608 * Count: 199998
609 *
610 * Timer 'blender::Set Add' took 3.16514 ms
611 * Timer 'blender::Set Contains' took 0.732895 ms
612 * Timer 'blender::Set Remove' took 1.08171 ms
613 * Count: 198790
614 * Timer 'std::unordered_set Add' took 6.57377 ms
615 * Timer 'std::unordered_set Contains' took 1.17008 ms
616 * Timer 'std::unordered_set Remove' took 3.7946 ms
617 * Count: 198790
618 * Timer 'blender::Set Add' took 3.11439 ms
619 * Timer 'blender::Set Contains' took 0.740159 ms
620 * Timer 'blender::Set Remove' took 1.06749 ms
621 * Count: 198790
622 * Timer 'std::unordered_set Add' took 6.35597 ms
623 * Timer 'std::unordered_set Contains' took 1.17713 ms
624 * Timer 'std::unordered_set Remove' took 3.77826 ms
625 * Count: 198790
626 * Timer 'blender::Set Add' took 3.09876 ms
627 * Timer 'blender::Set Contains' took 0.742072 ms
628 * Timer 'blender::Set Remove' took 1.06622 ms
629 * Count: 198790
630 * Timer 'std::unordered_set Add' took 6.4469 ms
631 * Timer 'std::unordered_set Contains' took 1.16515 ms
632 * Timer 'std::unordered_set Remove' took 3.80639 ms
633 * Count: 198790
634 */
635
636 #endif /* Benchmark */
637
638 } // namespace tests
639 } // namespace blender
640