Blender  V3.3
BLI_set_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include <set>
4 #include <unordered_set>
5 
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 
18 TEST(set, DefaultConstructor)
19 {
20  Set<int> set;
21  EXPECT_EQ(set.size(), 0);
22  EXPECT_TRUE(set.is_empty());
23 }
24 
25 TEST(set, ContainsNotExistant)
26 {
27  Set<int> set;
28  EXPECT_FALSE(set.contains(3));
29 }
30 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
195 TEST(set, Iterator)
196 {
197  Set<int> set = {1, 3, 2, 5, 4};
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 
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 
221 TEST(set, UniquePtrValues)
222 {
224  set.add_new(std::make_unique<int>());
225  auto value1 = std::make_unique<int>();
226  set.add_new(std::move(value1));
227  set.add(std::make_unique<int>());
228 
229  EXPECT_EQ(set.size(), 3);
230 }
231 
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 
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 
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 
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 {
278 };
279 
280 struct Type2 {
282 };
283 
284 static bool operator==(const Type1 &a, const Type1 &b)
285 {
286  return a.value == b.value;
287 }
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> {
297  uint32_t operator()(const tests::Type1 &value) const
298  {
299  return value.value;
300  }
301 
302  uint32_t operator()(const tests::Type2 &value) const
303  {
304  return value.value;
305  }
306 };
307 
308 namespace tests {
309 
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 
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 
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 
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 
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 {
362  bool operator()(uint a, uint b) const
363  {
364  return (a % N) == (b % N);
365  }
366 };
367 
368 template<uint N> struct HashIntModN {
369  uint64_t operator()(uint value) const
370  {
371  return value % N;
372  }
373 };
374 
375 TEST(set, CustomizeHashAndEquality)
376 {
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 
390 TEST(set, IntrusiveIntKey)
391 {
392  Set<int,
393  2,
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 {
414 
415  uint64_t hash() const
416  {
417  return key;
418  }
419 
420  friend bool operator==(const MyKeyType &a, const MyKeyType &b)
421  {
422  return a.key == b.key;
423  }
424 };
425 
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 
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 
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 
456 TEST(set, LookupKeyOrAdd)
457 {
458  Set<MyKeyType> set;
459  set.lookup_key_or_add({1, 10});
460  set.lookup_key_or_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 
470 TEST(set, StringViewKeys)
471 {
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 
480 TEST(set, SpanConstructorExceptions)
481 {
482  std::array<ExceptionThrower, 5> array = {1, 2, 3, 4, 5};
483  array[3].throw_during_copy = true;
485 
486  EXPECT_ANY_THROW({ Set<ExceptionThrower> set(span); });
487 }
488 
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 
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 
507 TEST(set, AddNewExceptions)
508 {
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 
518 TEST(set, AddExceptions)
519 {
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 TEST(set, ForwardIterator)
530 {
531  Set<int> set = {5, 2, 6, 4, 1};
532  Set<int>::iterator iter1 = set.begin();
533  int value1 = *iter1;
534  Set<int>::iterator iter2 = iter1++;
535  EXPECT_EQ(*iter1, value1);
536  EXPECT_EQ(*iter2, *(++iter1));
537 }
538 
539 TEST(set, GenericAlgorithms)
540 {
541  Set<int> set = {1, 20, 30, 40};
542  EXPECT_FALSE(std::any_of(set.begin(), set.end(), [](int v) { return v == 5; }));
543  EXPECT_TRUE(std::any_of(set.begin(), set.end(), [](int v) { return v == 30; }));
544  EXPECT_EQ(std::count(set.begin(), set.end(), 20), 1);
545 }
546 
547 TEST(set, RemoveDuringIteration)
548 {
549  Set<int> set;
550  set.add(6);
551  set.add(5);
552  set.add(2);
553  set.add(3);
554 
555  EXPECT_EQ(set.size(), 4);
556 
557  using Iter = Set<int>::Iterator;
558  Iter begin = set.begin();
559  Iter end = set.end();
560  for (Iter iter = begin; iter != end; ++iter) {
561  int item = *iter;
562  if (item == 2) {
563  set.remove(iter);
564  }
565  }
566 
567  EXPECT_EQ(set.size(), 3);
568  EXPECT_TRUE(set.contains(5));
569  EXPECT_TRUE(set.contains(6));
570  EXPECT_TRUE(set.contains(3));
571 }
572 
576 #if 0
577 template<typename SetT>
578 BLI_NOINLINE void benchmark_random_ints(StringRef name, int amount, int factor)
579 {
580  RNG *rng = BLI_rng_new(0);
581  Vector<int> values;
582  for (int i = 0; i < amount; i++) {
583  values.append(BLI_rng_get_int(rng) * factor);
584  }
585  BLI_rng_free(rng);
586 
587  SetT set;
588  {
589  SCOPED_TIMER(name + " Add");
590  for (int value : values) {
591  set.add(value);
592  }
593  }
594  int count = 0;
595  {
596  SCOPED_TIMER(name + " Contains");
597  for (int value : values) {
598  count += set.contains(value);
599  }
600  }
601  {
602  SCOPED_TIMER(name + " Remove");
603  for (int value : values) {
604  count += set.remove(value);
605  }
606  }
607 
608  /* Print the value for simple error checking and to avoid some compiler optimizations. */
609  std::cout << "Count: " << count << "\n";
610 }
611 
612 TEST(set, Benchmark)
613 {
614  for (int i = 0; i < 3; i++) {
615  benchmark_random_ints<blender::Set<int>>("blender::Set ", 100000, 1);
616  benchmark_random_ints<blender::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, 1);
617  }
618  std::cout << "\n";
619  for (int i = 0; i < 3; i++) {
620  uint32_t factor = (3 << 10);
621  benchmark_random_ints<blender::Set<int>>("blender::Set ", 100000, factor);
622  benchmark_random_ints<blender::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, factor);
623  }
624 }
625 
680 #endif /* Benchmark */
681 
682 } // namespace tests
683 } // namespace blender
#define BLI_NOINLINE
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
Random number functions.
void int BLI_rng_get_int(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: rand.cc:78
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition: rand.cc:58
struct RNG * BLI_rng_new(unsigned int seed)
Definition: rand.cc:39
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define SCOPED_TIMER(name)
Definition: BLI_timeit.hh:68
ATTR_WARN_UNUSED_RESULT const BMVert * v
bool remove_as(const ForwardKey &key)
Definition: BLI_set.hh:375
Iterator begin() const
Definition: BLI_set.hh:466
const Key * lookup_key_ptr(const Key &key) const
Definition: BLI_set.hh:340
const Key & lookup_key(const Key &key) const
Definition: BLI_set.hh:309
int64_t size() const
Definition: BLI_set.hh:539
bool add_as(ForwardKey &&key)
Definition: BLI_set.hh:261
bool contains_as(const ForwardKey &key) const
Definition: BLI_set.hh:300
Iterator end() const
Definition: BLI_set.hh:476
void remove_contained(const Key &key)
Definition: BLI_set.hh:383
bool contains(const Key &key) const
Definition: BLI_set.hh:296
const Key & lookup_key_or_add(const Key &key)
Definition: BLI_set.hh:353
bool add(const Key &key)
Definition: BLI_set.hh:253
bool is_empty() const
Definition: BLI_set.hh:547
void add_new(const Key &key)
Definition: BLI_set.hh:238
void clear()
Definition: BLI_set.hh:516
void remove_contained_as(const ForwardKey &key)
Definition: BLI_set.hh:387
const Key & lookup_key_default(const Key &key, const Key &default_value) const
Definition: BLI_set.hh:322
bool remove(const Key &key)
Definition: BLI_set.hh:371
int64_t size() const
Definition: BLI_vector.hh:694
bool contains(const T &value) const
Definition: BLI_vector.hh:837
void append(const T &value)
Definition: BLI_vector.hh:433
int count
#define N
static unsigned c
Definition: RandGen.cpp:83
static unsigned a[3]
Definition: RandGen.cpp:78
static bool operator==(const Type1 &a, const Type1 &b)
TEST(any, DefaultConstructor)
Definition: BLI_any_test.cc:10
PythonProbingStrategy<> DefaultProbingStrategy
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
unsigned int uint32_t
Definition: stdint.h:80
signed int int32_t
Definition: stdint.h:77
unsigned __int64 uint64_t
Definition: stdint.h:90
Definition: rand.cc:33
uint32_t operator()(const tests::Type1 &value) const
uint32_t operator()(const tests::Type2 &value) const
bool operator()(uint a, uint b) const
uint64_t operator()(uint value) const
friend bool operator==(const MyKeyType &a, const MyKeyType &b)