Blender V5.3
BLI_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
5#include <set>
6#include <unordered_set>
7
8#include "testing/testing.h"
9
11#include "BLI_ghash.hh"
12#include "BLI_rand_c.hh"
13#include "BLI_set.hh"
14#include "BLI_timeit.hh"
15#include "BLI_vector.hh"
16
17#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
18
19namespace blender {
20
21namespace tests {
22
23TEST(set, DefaultConstructor)
24{
25 Set<int> set;
26 EXPECT_EQ(set.size(), 0);
27 EXPECT_TRUE(set.is_empty());
28}
29
30TEST(set, ContainsNotExistant)
31{
32 Set<int> set;
33 EXPECT_FALSE(set.contains(3));
34}
35
36TEST(set, ContainsExistant)
37{
38 Set<int> set;
39 EXPECT_FALSE(set.contains(5));
40 EXPECT_TRUE(set.is_empty());
41 set.add(5);
42 EXPECT_TRUE(set.contains(5));
44}
45
46TEST(set, AddMany)
47{
48 Set<int> set;
49 for (int i = 0; i < 100; i++) {
50 set.add(i);
51 }
52
53 for (int i = 50; i < 100; i++) {
54 EXPECT_TRUE(set.contains(i));
55 }
56 for (int i = 100; i < 150; i++) {
57 EXPECT_FALSE(set.contains(i));
58 }
59}
60
61TEST(set, InitializerListConstructor)
62{
63 Set<int> set = {4, 5, 6};
64 EXPECT_EQ(set.size(), 3);
65 EXPECT_TRUE(set.contains(4));
66 EXPECT_TRUE(set.contains(5));
67 EXPECT_TRUE(set.contains(6));
68 EXPECT_FALSE(set.contains(2));
69 EXPECT_FALSE(set.contains(3));
70}
71
72TEST(set, CopyConstructor)
73{
74 Set<int> set = {3};
75 EXPECT_TRUE(set.contains(3));
76 EXPECT_FALSE(set.contains(4));
77
78 Set<int> set2(set);
79 set2.add(4);
80 EXPECT_TRUE(set2.contains(3));
81 EXPECT_TRUE(set2.contains(4));
82
83 EXPECT_FALSE(set.contains(4));
84}
85
86TEST(set, MoveConstructor)
87{
88 Set<int> set = {1, 2, 3};
89 EXPECT_EQ(set.size(), 3);
90 Set<int> set2(std::move(set));
91 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
92 EXPECT_EQ(set2.size(), 3);
93}
94
95TEST(set, CopyAssignment)
96{
97 Set<int> set = {3};
98 EXPECT_TRUE(set.contains(3));
99 EXPECT_FALSE(set.contains(4));
100
101 Set<int> set2;
102 set2 = set;
103 set2.add(4);
104 EXPECT_TRUE(set2.contains(3));
105 EXPECT_TRUE(set2.contains(4));
106
107 EXPECT_FALSE(set.contains(4));
108}
109
110TEST(set, MoveAssignment)
111{
112 Set<int> set = {1, 2, 3};
113 EXPECT_EQ(set.size(), 3);
114 Set<int> set2;
115 set2 = std::move(set);
116 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
117 EXPECT_EQ(set2.size(), 3);
118}
119
120TEST(set, RemoveContained)
121{
122 Set<int> set = {3, 4, 5};
123 EXPECT_TRUE(set.contains(3));
124 EXPECT_TRUE(set.contains(4));
125 EXPECT_TRUE(set.contains(5));
126 set.remove_contained(4);
127 EXPECT_TRUE(set.contains(3));
128 EXPECT_FALSE(set.contains(4));
129 EXPECT_TRUE(set.contains(5));
130 set.remove_contained(3);
131 EXPECT_FALSE(set.contains(3));
132 EXPECT_FALSE(set.contains(4));
133 EXPECT_TRUE(set.contains(5));
134 set.remove_contained(5);
135 EXPECT_FALSE(set.contains(3));
136 EXPECT_FALSE(set.contains(4));
137 EXPECT_FALSE(set.contains(5));
138}
139
140TEST(set, RemoveContainedMany)
141{
142 Set<int> set;
143 for (int i = 0; i < 1000; i++) {
144 set.add(i);
145 }
146 for (int i = 100; i < 1000; i++) {
147 set.remove_contained(i);
148 }
149 for (int i = 900; i < 1000; i++) {
150 set.add(i);
151 }
152
153 for (int i = 0; i < 1000; i++) {
154 if (i < 100 || i >= 900) {
155 EXPECT_TRUE(set.contains(i));
156 }
157 else {
158 EXPECT_FALSE(set.contains(i));
159 }
160 }
161}
162
163TEST(set, Intersects)
164{
165 Set<int> a = {3, 4, 5, 6};
166 Set<int> b = {1, 2, 5};
169}
170
171TEST(set, Disjoint)
172{
173 Set<int> a = {5, 6, 7, 8};
174 Set<int> b = {2, 3, 4, 9};
177}
178
179TEST(set, AddMultiple)
180{
181 Set<int> a;
182 a.add_multiple({5, 7});
183 EXPECT_TRUE(a.contains(5));
184 EXPECT_TRUE(a.contains(7));
186 a.add_multiple({2, 4, 7});
187 EXPECT_TRUE(a.contains(4));
188 EXPECT_TRUE(a.contains(2));
189 EXPECT_EQ(a.size(), 4);
190}
191
192TEST(set, AddMultipleNew)
193{
194 Set<int> a;
195 a.add_multiple_new({5, 6});
196 EXPECT_TRUE(a.contains(5));
197 EXPECT_TRUE(a.contains(6));
198}
199
200TEST(set, Iterator)
201{
202 Set<int> set = {1, 3, 2, 5, 4};
203 Vector<int> vec;
204 for (int value : set) {
205 vec.append(value);
206 }
207 EXPECT_EQ(vec.size(), 5);
208 EXPECT_TRUE(vec.contains(1));
209 EXPECT_TRUE(vec.contains(3));
210 EXPECT_TRUE(vec.contains(2));
211 EXPECT_TRUE(vec.contains(5));
212 EXPECT_TRUE(vec.contains(4));
213}
214
215TEST(set, OftenAddRemoveContained)
216{
217 Set<int> set;
218 for (int i = 0; i < 100; i++) {
219 set.add(42);
220 EXPECT_EQ(set.size(), 1);
221 set.remove_contained(42);
222 EXPECT_EQ(set.size(), 0);
223 }
224}
225
226TEST(set, UniquePtrValues)
227{
229 set.add_new(std::make_unique<int>());
230 auto value1 = std::make_unique<int>();
231 set.add_new(std::move(value1));
232 set.add(std::make_unique<int>());
233
234 EXPECT_EQ(set.size(), 3);
235}
236
238{
239 Set<int> set = {3, 4, 6, 7};
240 EXPECT_EQ(set.size(), 4);
241 set.clear();
242 EXPECT_EQ(set.size(), 0);
243}
244
245TEST(set, StringSet)
246{
248 set.add("hello");
249 set.add("world");
250 EXPECT_EQ(set.size(), 2);
251 EXPECT_TRUE(set.contains("hello"));
252 EXPECT_TRUE(set.contains("world"));
253 EXPECT_FALSE(set.contains("world2"));
254}
255
256TEST(set, PointerSet)
257{
258 int a, b, c;
259 Set<int *> set;
260 set.add(&a);
261 set.add(&b);
262 EXPECT_EQ(set.size(), 2);
263 EXPECT_TRUE(set.contains(&a));
264 EXPECT_TRUE(set.contains(&b));
265 EXPECT_FALSE(set.contains(&c));
266}
267
268TEST(set, Remove)
269{
270 Set<int> set = {1, 2, 3, 4, 5, 6};
271 EXPECT_EQ(set.size(), 6);
272 EXPECT_TRUE(set.remove(2));
273 EXPECT_EQ(set.size(), 5);
274 EXPECT_FALSE(set.contains(2));
275 EXPECT_FALSE(set.remove(2));
276 EXPECT_EQ(set.size(), 5);
277 EXPECT_TRUE(set.remove(5));
278 EXPECT_EQ(set.size(), 4);
279}
280
281TEST(set, AddRemoveSameHash)
282{
283 Set<int> set;
284 set.add(0);
285 set.add(1 << 16);
286 EXPECT_TRUE(set.contains(0));
287 EXPECT_TRUE(set.contains(1 << 16));
288 set.remove(0);
289 EXPECT_FALSE(set.contains(0));
290 EXPECT_TRUE(set.contains(1 << 16));
291 set.add(1 << 16);
292 EXPECT_TRUE(set.contains(1 << 16));
293 set.remove(1 << 16);
294 EXPECT_FALSE(set.contains(1 << 16));
295}
296
297struct Type1 {
299};
300
301struct Type2 {
303};
304
305static bool operator==(const Type1 &a, const Type1 &b)
306{
307 return a.value == b.value;
308}
309static bool operator==(const Type2 &a, const Type1 &b)
310{
311 return a.value == b.value;
312}
313
314} // namespace tests
315
316/* This has to be defined in ::blender namespace. */
317template<> struct DefaultHash<blender::tests::Type1> {
319 {
320 return value.value;
321 }
322
324 {
325 return value.value;
326 }
327};
328
329namespace tests {
330
331TEST(set, ContainsAs)
332{
333 Set<Type1> set;
334 set.add(Type1{5});
339}
340
341TEST(set, ContainsAsString)
342{
344 set.add("test");
345 EXPECT_TRUE(set.contains_as("test"));
346 EXPECT_TRUE(set.contains_as(StringRef("test")));
347 EXPECT_FALSE(set.contains_as("string"));
348 EXPECT_FALSE(set.contains_as(StringRef("string")));
349}
350
351TEST(set, RemoveContainedAs)
352{
353 Set<Type1> set;
354 set.add(Type1{5});
358}
359
360TEST(set, RemoveAs)
361{
362 Set<Type1> set;
363 set.add(Type1{5});
365 set.remove_as(Type2{6});
367 set.remove_as(Type2{5});
369 set.remove_as(Type2{5});
371}
372
373TEST(set, AddAs)
374{
376 EXPECT_TRUE(set.add_as("test"));
377 EXPECT_TRUE(set.add_as(StringRef("qwe")));
378 EXPECT_FALSE(set.add_as(StringRef("test")));
379 EXPECT_FALSE(set.add_as("qwe"));
380}
381
382template<uint N> struct EqualityIntModN {
383 bool operator()(uint a, uint b) const
384 {
385 return (a % N) == (b % N);
386 }
387};
388
389template<uint N> struct HashIntModN {
391 {
392 return value % N;
393 }
394};
395
396TEST(set, CustomizeHashAndEquality)
397{
399 set.add(4);
400 EXPECT_TRUE(set.contains(4));
401 EXPECT_TRUE(set.contains(14));
402 EXPECT_TRUE(set.contains(104));
403 EXPECT_FALSE(set.contains(5));
404 set.add(55);
405 EXPECT_TRUE(set.contains(5));
406 EXPECT_TRUE(set.contains(14));
407 set.remove(1004);
408 EXPECT_FALSE(set.contains(14));
409}
410
411TEST(set, IntrusiveIntKey)
412{
413 Set<int,
414 2,
419 set;
420 EXPECT_TRUE(set.add(4));
421 EXPECT_TRUE(set.add(3));
422 EXPECT_TRUE(set.add(11));
423 EXPECT_TRUE(set.add(8));
424 EXPECT_FALSE(set.add(3));
425 EXPECT_FALSE(set.add(4));
426 EXPECT_TRUE(set.remove(4));
427 EXPECT_FALSE(set.remove(7));
428 EXPECT_TRUE(set.add(4));
429 EXPECT_TRUE(set.remove(4));
430}
431
433 uint64_t operator()(const int key) const
434 {
435 EXPECT_GE(key, 0);
436 return uint64_t(key % 10);
437 }
438};
439
441 bool operator()(const int a, const int b) const
442 {
443 EXPECT_GE(a, 0);
444 EXPECT_GE(b, 0);
445 return a % 10 == b % 10;
446 }
447};
448
449TEST(set, IntrusiveIntKeyCustomEq)
450{
452 EXPECT_TRUE(set.add(1));
453 EXPECT_TRUE(set.add(2));
454 EXPECT_FALSE(set.add(1));
455 EXPECT_FALSE(set.add(11));
456 EXPECT_FALSE(set.add(101));
457 EXPECT_TRUE(set.add(103));
458 EXPECT_TRUE(set.contains(3));
459 EXPECT_FALSE(set.remove(54));
460 EXPECT_TRUE(set.remove(52));
461 EXPECT_FALSE(set.contains(2));
462}
463
464struct MyKeyType {
467
469 {
470 return key;
471 }
472
473 friend bool operator==(const MyKeyType &a, const MyKeyType &b)
474 {
475 return a.key == b.key;
476 }
477};
478
479TEST(set, LookupKey)
480{
481 Set<MyKeyType> set;
482 set.add({1, 10});
483 set.add({2, 20});
484 EXPECT_EQ(set.lookup_key({1, 30}).attached_data, 10);
485 EXPECT_EQ(set.lookup_key({2, 0}).attached_data, 20);
486}
487
488TEST(set, LookupKeyDefault)
489{
490 Set<MyKeyType> set;
491 set.add({1, 10});
492 set.add({2, 20});
493
494 MyKeyType fallback{5, 50};
495 EXPECT_EQ(set.lookup_key_default({1, 66}, fallback).attached_data, 10);
496 EXPECT_EQ(set.lookup_key_default({4, 40}, fallback).attached_data, 50);
497}
498
499TEST(set, LookupKeyPtr)
500{
501 Set<MyKeyType> set;
502 set.add({1, 10});
503 set.add({2, 20});
504 EXPECT_EQ(set.lookup_key_ptr({1, 50})->attached_data, 10);
505 EXPECT_EQ(set.lookup_key_ptr({2, 50})->attached_data, 20);
506 EXPECT_EQ(set.lookup_key_ptr({3, 50}), nullptr);
507}
508
509TEST(set, LookupKeyOrAdd)
510{
511 Set<MyKeyType> set;
512 set.lookup_key_or_add({1, 10});
513 set.lookup_key_or_add({2, 20});
514 EXPECT_EQ(set.size(), 2);
515 EXPECT_EQ(set.lookup_key_or_add({2, 40}).attached_data, 20);
516 EXPECT_EQ(set.size(), 2);
517 EXPECT_EQ(set.lookup_key_or_add({3, 40}).attached_data, 40);
518 EXPECT_EQ(set.size(), 3);
519 EXPECT_EQ(set.lookup_key_or_add({3, 60}).attached_data, 40);
520 EXPECT_EQ(set.size(), 3);
521}
522
523TEST(set, LookupKeyOrAddCb)
524{
525 Set<MyKeyType> set;
526 EXPECT_EQ(set.lookup_key_or_add_cb({1, 10}, [&]() { return MyKeyType{1, 100}; }).attached_data,
527 100);
528 EXPECT_EQ(set.lookup_key_or_add_cb({1, 5}, [&]() { return MyKeyType{1, 50}; }).attached_data,
529 100);
530 EXPECT_EQ(set.lookup_key_or_add_cb({2, 20}, [&]() { return MyKeyType{2, 200}; }).attached_data,
531 200);
532}
533
534TEST(set, StringViewKeys)
535{
537 set.add("hello");
538 set.add("world");
539 EXPECT_FALSE(set.contains("worlds"));
540 EXPECT_TRUE(set.contains("world"));
541 EXPECT_TRUE(set.contains("hello"));
542}
543
544TEST(set, SpanConstructorExceptions)
545{
546 std::array<ExceptionThrower, 5> array = {1, 2, 3, 4, 5};
547 array[3].throw_during_copy = true;
549
550 EXPECT_ANY_THROW({ Set<ExceptionThrower> set(span); });
551}
552
553TEST(set, CopyConstructorExceptions)
554{
555 Set<ExceptionThrower> set = {1, 2, 3, 4, 5};
556 set.lookup_key(3).throw_during_copy = true;
557 EXPECT_ANY_THROW({ Set<ExceptionThrower> set_copy(set); });
558}
559
560TEST(set, MoveConstructorExceptions)
561{
562 using SetType = Set<ExceptionThrower, 4>;
563 SetType set = {1, 2, 3};
564 set.lookup_key(2).throw_during_move = true;
565 EXPECT_ANY_THROW({ SetType set_moved(std::move(set)); });
566 EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
567 set.add_multiple({3, 6, 7});
568 EXPECT_EQ(set.size(), 3);
569}
570
571TEST(set, AddNewExceptions)
572{
574 ExceptionThrower value;
575 value.throw_during_copy = true;
576 EXPECT_ANY_THROW({ set.add_new(value); });
577 EXPECT_EQ(set.size(), 0);
578 EXPECT_ANY_THROW({ set.add_new(value); });
579 EXPECT_EQ(set.size(), 0);
580}
581
582TEST(set, AddExceptions)
583{
585 ExceptionThrower value;
586 value.throw_during_copy = true;
587 EXPECT_ANY_THROW({ set.add(value); });
588 EXPECT_EQ(set.size(), 0);
589 EXPECT_ANY_THROW({ set.add(value); });
590 EXPECT_EQ(set.size(), 0);
591}
592
593TEST(set, ForwardIterator)
594{
595 Set<int> set = {5, 2, 6, 4, 1};
596 Set<int>::iterator iter1 = set.begin();
597 int value1 = *iter1;
598 Set<int>::iterator iter2 = iter1++;
599 EXPECT_EQ(*iter2, value1);
600 EXPECT_EQ(*(++iter2), *iter1);
601 /* Interesting find: On GCC & MSVC this will succeed, as the 2nd argument is evaluated before the
602 * 1st. On Apple Clang it's the other way around, and the test fails. */
603 // EXPECT_EQ(*iter1, *(++iter1));
604 Set<int>::iterator iter3 = ++iter1;
605 /* Check that #iter1 itself changed. */
606 EXPECT_EQ(*iter3, *iter1);
607}
608
609TEST(set, GenericAlgorithms)
610{
611 Set<int> set = {1, 20, 30, 40};
612 EXPECT_FALSE(std::any_of(set.begin(), set.end(), [](int v) { return v == 5; }));
613 EXPECT_TRUE(std::any_of(set.begin(), set.end(), [](int v) { return v == 30; }));
614 EXPECT_EQ(std::count(set.begin(), set.end(), 20), 1);
615}
616
617TEST(set, RemoveDuringIteration)
618{
619 Set<int> set;
620 set.add(6);
621 set.add(5);
622 set.add(2);
623 set.add(3);
624
625 EXPECT_EQ(set.size(), 4);
626
627 using Iter = Set<int>::Iterator;
628 Iter begin = set.begin();
629 Iter end = set.end();
630 for (Iter iter = begin; iter != end; ++iter) {
631 int item = *iter;
632 if (item == 2) {
633 set.remove(iter);
634 }
635 }
636
637 EXPECT_EQ(set.size(), 3);
638 EXPECT_TRUE(set.contains(5));
639 EXPECT_TRUE(set.contains(6));
640 EXPECT_TRUE(set.contains(3));
641}
642
643TEST(set, RemoveIf)
644{
645 Set<int64_t> set;
646 for (const int64_t i : IndexRange(100)) {
647 set.add(i * i);
648 }
649 const int64_t removed = set.remove_if([](const int64_t key) { return key > 100; });
650 EXPECT_EQ(set.size() + removed, 100);
651 for (const int64_t i : IndexRange(100)) {
652 EXPECT_EQ(set.contains(i * i), i <= 10);
653 }
654}
655
656TEST(set, RemoveUniquePtrWithRaw)
657{
659 std::unique_ptr<int> a = std::make_unique<int>(5);
660 int *a_ptr = a.get();
661 set.add(std::move(a));
662 EXPECT_EQ(set.size(), 1);
663 set.remove_as(a_ptr);
664 EXPECT_TRUE(set.is_empty());
665}
666
667TEST(set, Equality)
668{
669 const Set<int> a = {1, 2, 3, 4, 5};
670 const Set<int> b = {5, 2, 3, 1, 4};
671 const Set<int> c = {1, 2, 3};
672 const Set<int> d = {1, 2, 3, 4, 5, 6};
673 const Set<int> e = {};
674 const Set<int> f = {10, 11, 12, 13, 14};
675
676 EXPECT_EQ(a, a);
677 EXPECT_EQ(a, b);
678 EXPECT_EQ(b, a);
679 EXPECT_NE(a, c);
680 EXPECT_NE(a, d);
681 EXPECT_NE(a, e);
682 EXPECT_NE(a, f);
683 EXPECT_NE(c, a);
684 EXPECT_NE(d, a);
685 EXPECT_NE(e, a);
686 EXPECT_NE(f, a);
687}
688
689namespace {
690struct KeyWithData {
691 int key;
692 std::string data;
693
694 uint64_t hash() const
695 {
696 return uint64_t(this->key);
697 }
698
699 friend bool operator==(const KeyWithData &a, const KeyWithData &b)
700 {
701 return a.key == b.key;
702 }
703};
704} // namespace
705
706TEST(set, AddOverwrite)
707{
709 EXPECT_TRUE(set.add_overwrite(KeyWithData{1, "a"}));
710 EXPECT_EQ(set.size(), 1);
711 EXPECT_FALSE(set.add(KeyWithData{1, "b"}));
712 EXPECT_EQ(set.size(), 1);
713 EXPECT_EQ(set.lookup_key(KeyWithData{1, "_"}).data, "a");
714 EXPECT_FALSE(set.add_overwrite(KeyWithData{1, "c"}));
715 EXPECT_EQ(set.size(), 1);
716 EXPECT_EQ(set.lookup_key(KeyWithData{1, "_"}).data, "c");
717
718 const KeyWithData key{2, "d"};
719 EXPECT_TRUE(set.add_overwrite(key));
720 EXPECT_EQ(set.size(), 2);
721 EXPECT_EQ(set.lookup_key(key).data, "d");
722}
723
727#if 0
728template<typename SetT>
729BLI_NOINLINE void benchmark_random_ints(StringRef name, int amount, int factor)
730{
731 RNG *rng = BLI_rng_new(0);
732 Vector<int> values;
733 for (int i = 0; i < amount; i++) {
734 values.append(BLI_rng_get_int(rng) * factor);
735 }
736 BLI_rng_free(rng);
737
738 SetT set;
739 // set.reserve(amount);
740 {
741 SCOPED_TIMER(name + " Add");
742 for (int value : values) {
743 set.add(value);
744 }
745 }
746 int count = 0;
747 {
748 SCOPED_TIMER(name + " Contains");
749 for (int value : values) {
750 count += set.contains(value);
751 }
752 }
753 {
754 SCOPED_TIMER(name + " Remove");
755 for (int value : values) {
756 count += set.remove(value);
757 }
758 }
759
760 /* Print the value for simple error checking and to avoid some compiler optimizations. */
761 std::cout << "Count: " << count << "\n";
762}
763
768template<typename Key> class StdUnorderedSetWrapper {
769 private:
770 using SetType = std::unordered_set<Key, DefaultHash<Key>>;
771 SetType set_;
772
773 public:
774 int64_t size() const
775 {
776 return int64_t(set_.size());
777 }
778
779 bool is_empty() const
780 {
781 return set_.empty();
782 }
783
784 void reserve(int64_t n)
785 {
786 set_.reserve(size_t(n));
787 }
788
789 void add_new(const Key &key)
790 {
791 set_.insert(key);
792 }
793 void add_new(Key &&key)
794 {
795 set_.insert(std::move(key));
796 }
797
798 bool add(const Key &key)
799 {
800 return set_.insert(key).second;
801 }
802 bool add(Key &&key)
803 {
804 return set_.insert(std::move(key)).second;
805 }
806
807 void add_multiple(Span<Key> keys)
808 {
809 for (const Key &key : keys) {
810 set_.insert(key);
811 }
812 }
813
814 bool contains(const Key &key) const
815 {
816 return set_.find(key) != set_.end();
817 }
818
819 bool remove(const Key &key)
820 {
821 return bool(set_.erase(key));
822 }
823
824 void remove_contained(const Key &key)
825 {
826 return set_.erase(key);
827 }
828
829 void clear()
830 {
831 set_.clear();
832 }
833
834 typename SetType::iterator begin() const
835 {
836 return set_.begin();
837 }
838
839 typename SetType::iterator end() const
840 {
841 return set_.end();
842 }
843};
844
845TEST(set, Benchmark)
846{
847 for (int i = 0; i < 3; i++) {
848 benchmark_random_ints<Set<int>>("Set ", 100000, 1);
849 benchmark_random_ints<StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, 1);
850 }
851 std::cout << "\n";
852 for (int i = 0; i < 3; i++) {
853 uint32_t factor = (3 << 10);
854 benchmark_random_ints<Set<int>>("Set ", 100000, int(factor));
855 benchmark_random_ints<StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, int(factor));
856 }
857}
858
914
915#endif /* Benchmark */
916
917} // namespace tests
918} // namespace blender
Random number functions.
#define SCOPED_TIMER(name)
Definition BLI_timeit.hh:64
#define BLI_NOINLINE
long long int int64_t
const Key & lookup_key_default(const Key &key, const Key &default_value) const
Definition BLI_set.hh:336
bool remove_as(const ForwardKey &key)
Definition BLI_set.hh:408
Iterator begin() const
Definition BLI_set.hh:499
const Key & lookup_key_or_add(const Key &key)
Definition BLI_set.hh:367
void add_multiple_new(Span< Key > keys)
Definition BLI_set.hh:298
const Key & lookup_key(const Key &key) const
Definition BLI_set.hh:323
Iterator iterator
Definition BLI_set.hh:114
static bool Disjoint(const Set &a, const Set &b)
Definition BLI_set.hh:684
int64_t size() const
Definition BLI_set.hh:606
bool add_as(ForwardKey &&key)
Definition BLI_set.hh:256
bool contains_as(const ForwardKey &key) const
Definition BLI_set.hh:314
Iterator end() const
Definition BLI_set.hh:509
void remove_contained(const Key &key)
Definition BLI_set.hh:416
bool contains(const Key &key) const
Definition BLI_set.hh:310
static bool Intersects(const Set &a, const Set &b)
Definition BLI_set.hh:666
const Key & lookup_key_or_add_cb(const Key &key, CreateValueF &&create_value)
Definition BLI_set.hh:388
bool add(const Key &key)
Definition BLI_set.hh:248
bool is_empty() const
Definition BLI_set.hh:614
void add_multiple(Span< Key > keys)
Definition BLI_set.hh:287
void add_new(const Key &key)
Definition BLI_set.hh:233
bool add_overwrite(const Key &key)
Definition BLI_set.hh:267
int64_t remove_if(Predicate &&predicate)
Definition BLI_set.hh:534
void clear()
Definition BLI_set.hh:570
void remove_contained_as(const ForwardKey &key)
Definition BLI_set.hh:420
const Key * lookup_key_ptr(const Key &key) const
Definition BLI_set.hh:354
bool remove(const Key &key)
Definition BLI_set.hh:404
int64_t size() const
bool contains(const T &value) const
void append(const T &value)
#define EXPECT_FALSE(result)
#define EXPECT_GE(result, expect)
#define TEST(a, b)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_EQ(result, expect)
ccl_device_inline bool operator==(const float2 a, const float2 b)
#define N
bool contains(const VArray< bool > &varray, const IndexMask &indices_to_check, bool value)
void add(Depsgraph &depsgraph, std::function< void()> fn)
int size(const AssetLibraryReference *library_reference)
TEST(any_virtual, DefaultConstructor)
static bool operator==(const Type1 &a, const Type1 &b)
BMesh Iterators.
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
unsigned int uint
Definition BKE_text.h:55
IntrusiveSetSlot< Int, TemplatedKeyInfo< Int, EmptyValue, RemovedValue > > IntegerSetSlot
ATTR_WARN_UNUSED_RESULT const BMVert * v
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
unsigned int uint32_t
Definition BKE_text.h:81
BMesh const char void * data
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void int BLI_rng_get_int(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:75
iter begin(iter)
PythonProbingStrategy<> DefaultProbingStrategy
signed int int32_t
Definition BKE_text.h:78
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define hash
Definition noise_c.cc:156
uint32_t operator()(const blender::tests::Type1 &value) const
uint32_t operator()(const blender::tests::Type2 &value) const
bool operator()(uint a, uint b) const
uint64_t operator()(uint value) const
bool operator()(const int a, const int b) const
uint64_t operator()(const int key) const
friend bool operator==(const MyKeyType &a, const MyKeyType &b)