Blender V5.3
BLI_map_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 <memory>
6#include <unordered_map>
7
8#include "testing/testing.h"
9
11#include "BLI_map.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::tests {
20
21static_assert(get_default_hash(0.0f) == get_default_hash(-0.0f));
22static_assert(get_default_hash(0.0) == get_default_hash(-0.0));
23
24TEST(map, DefaultConstructor)
25{
27 EXPECT_EQ(map.size(), 0);
28 EXPECT_TRUE(map.is_empty());
29}
30
31TEST(map, ItemsConstructor)
32{
33 {
34 Map<int, std::string> map = {{1, "where"}, {3, "when"}, {5, "why"}};
35 EXPECT_EQ(map.size(), 3);
36 EXPECT_EQ(map.lookup(1), "where");
37 EXPECT_EQ(map.lookup(3), "when");
38 EXPECT_EQ(map.lookup(5), "why");
39 }
40 {
41 Map<int, std::string> map{{1, "where"}, {3, "when"}, {5, "why"}};
42 EXPECT_EQ(map.size(), 3);
43 EXPECT_EQ(map.lookup(1), "where");
44 EXPECT_EQ(map.lookup(3), "when");
45 EXPECT_EQ(map.lookup(5), "why");
46 }
47 {
48 Map<int, std::string> map{{{1, "where"}, {3, "when"}, {5, "why"}}};
49 EXPECT_EQ(map.size(), 3);
50 EXPECT_EQ(map.lookup(1), "where");
51 EXPECT_EQ(map.lookup(3), "when");
52 EXPECT_EQ(map.lookup(5), "why");
53 }
54 {
55 const Array<std::pair<int, std::string>> items = {{1, "where"}, {3, "when"}, {5, "why"}};
56 Map<int, std::string> map{items};
57 EXPECT_EQ(map.size(), 3);
58 EXPECT_EQ(map.lookup(1), "where");
59 EXPECT_EQ(map.lookup(3), "when");
60 EXPECT_EQ(map.lookup(5), "why");
61 }
62}
63
64TEST(map, ItemsConstructorDuplicates)
65{
66 Map<int, int> map = {{1, 2}, {3, 4}, {1, 4}, {2, 5}, {2, 6}};
67 EXPECT_EQ(map.size(), 3);
68 EXPECT_EQ(map.lookup(1), 2);
69 EXPECT_EQ(map.lookup(2), 5);
70 EXPECT_EQ(map.lookup(3), 4);
71}
72
73TEST(map, AddIncreasesSize)
74{
76 EXPECT_EQ(map.size(), 0);
77 EXPECT_TRUE(map.is_empty());
78 map.add(2, 5.0f);
79 EXPECT_EQ(map.size(), 1);
81 map.add(6, 2.0f);
82 EXPECT_EQ(map.size(), 2);
84}
85
86TEST(map, Contains)
87{
89 EXPECT_FALSE(map.contains(4));
90 map.add(5, 6.0f);
91 EXPECT_FALSE(map.contains(4));
92 map.add(4, 2.0f);
93 EXPECT_TRUE(map.contains(4));
94}
95
96TEST(map, LookupExisting)
97{
99 map.add(2, 6.0f);
100 map.add(4, 1.0f);
101 EXPECT_EQ(map.lookup(2), 6.0f);
102 EXPECT_EQ(map.lookup(4), 1.0f);
103}
104
105TEST(map, LookupNotExisting)
106{
107 Map<int, float> map;
108 map.add(2, 4.0f);
109 map.add(1, 1.0f);
110 EXPECT_EQ(map.lookup_ptr(0), nullptr);
111 EXPECT_EQ(map.lookup_ptr(5), nullptr);
112}
113
114TEST(map, AddMany)
115{
116 Map<int, int> map;
117 for (int i = 0; i < 100; i++) {
118 map.add(i * 30, i);
119 map.add(i * 31, i);
120 }
121}
122
123TEST(map, PopItem)
124{
125 Map<int, float> map;
126 map.add(2, 3.0f);
127 map.add(1, 9.0f);
128 EXPECT_TRUE(map.contains(2));
129 EXPECT_TRUE(map.contains(1));
130
131 EXPECT_EQ(map.pop(1), 9.0f);
132 EXPECT_TRUE(map.contains(2));
133 EXPECT_FALSE(map.contains(1));
134
135 EXPECT_EQ(map.pop(2), 3.0f);
136 EXPECT_FALSE(map.contains(2));
137 EXPECT_FALSE(map.contains(1));
138}
139
140TEST(map, PopTry)
141{
142 Map<int, int> map;
143 map.add(1, 5);
144 map.add(2, 7);
145 EXPECT_EQ(map.size(), 2);
146 std::optional<int> value = map.pop_try(4);
147 EXPECT_EQ(map.size(), 2);
148 EXPECT_FALSE(value.has_value());
149 value = map.pop_try(2);
150 EXPECT_EQ(map.size(), 1);
151 EXPECT_TRUE(value.has_value());
152 EXPECT_EQ(*value, 7);
153 EXPECT_EQ(*map.pop_try(1), 5);
154 EXPECT_EQ(map.size(), 0);
155}
156
157TEST(map, PopDefault)
158{
159 Map<int, int> map;
160 map.add(1, 4);
161 map.add(2, 7);
162 map.add(3, 8);
163 EXPECT_EQ(map.size(), 3);
164 EXPECT_EQ(map.pop_default(4, 10), 10);
165 EXPECT_EQ(map.size(), 3);
166 EXPECT_EQ(map.pop_default(1, 10), 4);
167 EXPECT_EQ(map.size(), 2);
168 EXPECT_EQ(map.pop_default(2, 20), 7);
169 EXPECT_EQ(map.size(), 1);
170 EXPECT_EQ(map.pop_default(2, 20), 20);
171 EXPECT_EQ(map.size(), 1);
172 EXPECT_EQ(map.pop_default(3, 0), 8);
173 EXPECT_EQ(map.size(), 0);
174}
175
176TEST(map, PopItemMany)
177{
178 Map<int, int> map;
179 for (int i = 0; i < 100; i++) {
180 map.add_new(i, i);
181 }
182 for (int i = 25; i < 80; i++) {
183 EXPECT_EQ(map.pop(i), i);
184 }
185 for (int i = 0; i < 100; i++) {
186 EXPECT_EQ(map.contains(i), i < 25 || i >= 80);
187 }
188}
189
190TEST(map, ValueIterator)
191{
192 Map<int, float> map;
193 map.add(3, 5.0f);
194 map.add(1, 2.0f);
195 map.add(7, -2.0f);
196
197 Set<float> values;
198
199 int iterations = 0;
200 for (float value : map.values()) {
201 values.add(value);
202 iterations++;
203 }
204
205 EXPECT_EQ(iterations, 3);
206 EXPECT_TRUE(values.contains(5.0f));
207 EXPECT_TRUE(values.contains(-2.0f));
208 EXPECT_TRUE(values.contains(2.0f));
209}
210
211TEST(map, KeyIterator)
212{
213 Map<int, float> map;
214 map.add(6, 3.0f);
215 map.add(2, 4.0f);
216 map.add(1, 3.0f);
217
218 Set<int> keys;
219
220 int iterations = 0;
221 for (int key : map.keys()) {
222 keys.add(key);
223 iterations++;
224 }
225
226 EXPECT_EQ(iterations, 3);
227 EXPECT_TRUE(keys.contains(1));
228 EXPECT_TRUE(keys.contains(2));
229 EXPECT_TRUE(keys.contains(6));
230}
231
233{
234 Map<int, float> map;
235 map.add(5, 3.0f);
236 map.add(2, 9.0f);
237 map.add(1, 0.0f);
238
239 Set<int> keys;
240 Set<float> values;
241
242 int iterations = 0;
243 const Map<int, float> &const_map = map;
244 for (auto item : const_map.items()) {
245 keys.add(item.key);
246 values.add(item.value);
247 iterations++;
248 }
249
250 EXPECT_EQ(iterations, 3);
251 EXPECT_TRUE(keys.contains(5));
252 EXPECT_TRUE(keys.contains(2));
253 EXPECT_TRUE(keys.contains(1));
254 EXPECT_TRUE(values.contains(3.0f));
255 EXPECT_TRUE(values.contains(9.0f));
256 EXPECT_TRUE(values.contains(0.0f));
257}
258
259TEST(map, MutableValueIterator)
260{
261 Map<int, int> map;
262 map.add(3, 6);
263 map.add(2, 1);
264
265 for (int &value : map.values()) {
266 value += 10;
267 }
268
269 EXPECT_EQ(map.lookup(3), 16);
270 EXPECT_EQ(map.lookup(2), 11);
271}
272
273TEST(map, MutableItemIterator)
274{
275 Map<int, int> map;
276 map.add(3, 6);
277 map.add(2, 1);
278
279 for (auto item : map.items()) {
280 item.value += item.key;
281 }
282
283 EXPECT_EQ(map.lookup(3), 9.0f);
284 EXPECT_EQ(map.lookup(2), 3.0f);
285}
286
287TEST(map, MutableItemToItemConversion)
288{
289 Map<int, int> map;
290 map.add(3, 6);
291 map.add(2, 1);
292
293 Vector<int> keys, values;
294 for (MapItem<int, int> item : map.items()) {
295 keys.append(item.key);
296 values.append(item.value);
297 }
298
299 EXPECT_EQ(keys.size(), 2);
300 EXPECT_EQ(values.size(), 2);
301 EXPECT_TRUE(keys.contains(3));
302 EXPECT_TRUE(keys.contains(2));
303 EXPECT_TRUE(values.contains(6));
304 EXPECT_TRUE(values.contains(1));
305}
306
307static float return_42()
308{
309 return 42.0f;
310}
311
312TEST(map, LookupOrAddCB_SeparateFunction)
313{
314 Map<int, float> map;
315 EXPECT_EQ(map.lookup_or_add_cb(0, return_42), 42.0f);
316 EXPECT_EQ(map.lookup(0), 42);
317
318 map.keys();
319}
320
321TEST(map, LookupOrAddCB_Lambdas)
322{
323 Map<int, float> map;
324 auto lambda1 = []() { return 11.0f; };
325 EXPECT_EQ(map.lookup_or_add_cb(0, lambda1), 11.0f);
326 auto lambda2 = []() { return 20.0f; };
327 EXPECT_EQ(map.lookup_or_add_cb(1, lambda2), 20.0f);
328
329 EXPECT_EQ(map.lookup_or_add_cb(0, lambda2), 11.0f);
330 EXPECT_EQ(map.lookup_or_add_cb(1, lambda1), 20.0f);
331}
332
333TEST(map, AddOrModify)
334{
335 Map<int, float> map;
336 auto create_func = [](float *value) {
337 *value = 10.0f;
338 return true;
339 };
340 auto modify_func = [](float *value) {
341 *value += 5;
342 return false;
343 };
344 EXPECT_TRUE(map.add_or_modify(1, create_func, modify_func));
345 EXPECT_EQ(map.lookup(1), 10.0f);
346 EXPECT_FALSE(map.add_or_modify(1, create_func, modify_func));
347 EXPECT_EQ(map.lookup(1), 15.0f);
348}
349
350TEST(map, AddOrModifyReference)
351{
353 auto create_func = [](std::unique_ptr<int> *value) -> int & {
354 new (value) std::unique_ptr<int>(new int{10});
355 return **value;
356 };
357 auto modify_func = [](std::unique_ptr<int> *value) -> int & {
358 **value += 5;
359 return **value;
360 };
361 EXPECT_EQ(map.add_or_modify(1, create_func, modify_func), 10);
362 int &a = map.add_or_modify(1, create_func, modify_func);
363 EXPECT_EQ(a, 15);
364 a = 100;
365 EXPECT_EQ(*map.lookup(1), 100);
366}
367
368TEST(map, AddOverwrite)
369{
370 Map<int, float> map;
371 EXPECT_FALSE(map.contains(3));
372 EXPECT_TRUE(map.add_overwrite(3, 6.0f));
373 EXPECT_EQ(map.lookup(3), 6.0f);
374 EXPECT_FALSE(map.add_overwrite(3, 7.0f));
375 EXPECT_EQ(map.lookup(3), 7.0f);
376 EXPECT_FALSE(map.add(3, 8.0f));
377 EXPECT_EQ(map.lookup(3), 7.0f);
378}
379
380TEST(map, LookupOrAddDefault)
381{
382 Map<int, float> map;
383 map.lookup_or_add_default(3) = 6;
384 EXPECT_EQ(map.lookup(3), 6);
385 map.lookup_or_add_default(5) = 2;
386 EXPECT_EQ(map.lookup(5), 2);
387 map.lookup_or_add_default(3) += 4;
388 EXPECT_EQ(map.lookup(3), 10);
389}
390
391TEST(map, LookupOrAdd)
392{
393 Map<int, int> map;
394 EXPECT_EQ(map.lookup_or_add(6, 4), 4);
395 EXPECT_EQ(map.lookup_or_add(6, 5), 4);
396 map.lookup_or_add(6, 4) += 10;
397 EXPECT_EQ(map.lookup(6), 14);
398}
399
400TEST(map, LookupTry)
401{
402 Map<int, int> map;
403 map.add(1, 10);
404 map.add(2, 20);
405 EXPECT_EQ(map.lookup_try(1), 10);
406 EXPECT_EQ(map.lookup_try(2), 20);
407 EXPECT_EQ(map.lookup_try(3), std::nullopt);
408}
409
410TEST(map, MoveConstructorSmall)
411{
412 Map<int, float> map1;
413 map1.add(1, 2.0f);
414 map1.add(4, 1.0f);
415 Map<int, float> map2(std::move(map1));
416 EXPECT_EQ(map2.size(), 2);
417 EXPECT_EQ(map2.lookup(1), 2.0f);
418 EXPECT_EQ(map2.lookup(4), 1.0f);
419 EXPECT_EQ(map1.size(), 0); /* NOLINT: bugprone-use-after-move */
420 EXPECT_EQ(map1.lookup_ptr(4), nullptr);
421}
422
423TEST(map, MoveConstructorLarge)
424{
425 Map<int, int> map1;
426 for (int i = 0; i < 100; i++) {
427 map1.add_new(i, i);
428 }
429 Map<int, int> map2(std::move(map1));
430 EXPECT_EQ(map2.size(), 100);
431 EXPECT_EQ(map2.lookup(1), 1);
432 EXPECT_EQ(map2.lookup(4), 4);
433 EXPECT_EQ(map1.size(), 0); /* NOLINT: bugprone-use-after-move */
434 EXPECT_EQ(map1.lookup_ptr(4), nullptr);
435}
436
437TEST(map, MoveAssignment)
438{
439 Map<int, float> map1;
440 map1.add(1, 2.0f);
441 map1.add(4, 1.0f);
442 Map<int, float> map2;
443 map2 = std::move(map1);
444 EXPECT_EQ(map2.size(), 2);
445 EXPECT_EQ(map2.lookup(1), 2.0f);
446 EXPECT_EQ(map2.lookup(4), 1.0f);
447 EXPECT_EQ(map1.size(), 0); /* NOLINT: bugprone-use-after-move */
448 EXPECT_EQ(map1.lookup_ptr(4), nullptr);
449}
450
451TEST(map, CopyAssignment)
452{
453 Map<int, float> map1;
454 map1.add(1, 2.0f);
455 map1.add(4, 1.0f);
456 Map<int, float> map2;
457 map2 = map1;
458 EXPECT_EQ(map2.size(), 2);
459 EXPECT_EQ(map2.lookup(1), 2.0f);
460 EXPECT_EQ(map2.lookup(4), 1.0f);
461 EXPECT_EQ(map1.size(), 2);
462 EXPECT_EQ(*map1.lookup_ptr(4), 1.0f);
463}
464
466{
467 Map<int, float> map;
468 map.add(1, 1.0f);
469 map.add(2, 5.0f);
470
471 EXPECT_EQ(map.size(), 2);
472 EXPECT_TRUE(map.contains(1));
473 EXPECT_TRUE(map.contains(2));
474
475 map.clear();
476
477 EXPECT_EQ(map.size(), 0);
478 EXPECT_FALSE(map.contains(1));
479 EXPECT_FALSE(map.contains(2));
480}
481
482TEST(map, UniquePtrValue)
483{
484 auto value1 = std::make_unique<int>();
485 auto value2 = std::make_unique<int>();
486 auto value3 = std::make_unique<int>();
487
488 int *value1_ptr = value1.get();
489
491 map.add_new(1, std::move(value1));
492 map.add(2, std::move(value2));
493 map.add_overwrite(3, std::move(value3));
494 map.lookup_or_add_cb(4, []() { return std::make_unique<int>(); });
495 map.add_new(5, std::make_unique<int>());
496 map.add(6, std::make_unique<int>());
497 map.add_overwrite(7, std::make_unique<int>());
498 map.lookup_or_add(8, std::make_unique<int>());
499 map.pop_default(9, std::make_unique<int>());
500
501 EXPECT_EQ(map.lookup(1).get(), value1_ptr);
502 EXPECT_EQ(map.lookup_ptr(100), nullptr);
503}
504
505TEST(map, Remove)
506{
507 Map<int, int> map;
508 map.add(2, 4);
509 EXPECT_EQ(map.size(), 1);
510 EXPECT_FALSE(map.remove(3));
511 EXPECT_EQ(map.size(), 1);
512 EXPECT_TRUE(map.remove(2));
513 EXPECT_EQ(map.size(), 0);
514}
515
516TEST(map, PointerKeys)
517{
518 char a, b, c, d;
519
521 EXPECT_TRUE(map.add(&a, 5));
522 EXPECT_FALSE(map.add(&a, 4));
523 map.add_new(&b, 1);
524 map.add_new(&c, 1);
525 EXPECT_EQ(map.size(), 3);
526 EXPECT_TRUE(map.remove(&b));
527 EXPECT_TRUE(map.add(&b, 8));
528 EXPECT_FALSE(map.remove(&d));
529 EXPECT_TRUE(map.remove(&a));
530 EXPECT_TRUE(map.remove(&b));
531 EXPECT_TRUE(map.remove(&c));
532 EXPECT_TRUE(map.is_empty());
533}
534
535TEST(map, ConstKeysAndValues)
536{
538 map.reserve(10);
539 map.add("45", "643");
540 EXPECT_TRUE(map.contains("45"));
541 EXPECT_FALSE(map.contains("54"));
542}
543
544TEST(map, ForeachItem)
545{
546 Map<int, int> map;
547 map.add(3, 4);
548 map.add(1, 8);
549
550 Vector<int> keys;
551 Vector<int> values;
552 map.foreach_item([&](int key, int value) {
553 keys.append(key);
554 values.append(value);
555 });
556
557 EXPECT_EQ(keys.size(), 2);
558 EXPECT_EQ(values.size(), 2);
559 EXPECT_EQ(keys.first_index_of(3), values.first_index_of(4));
560 EXPECT_EQ(keys.first_index_of(1), values.first_index_of(8));
561}
562
563TEST(map, CopyConstructorExceptions)
564{
566 MapType map;
567 map.add(2, 2);
568 map.add(4, 4);
569 map.lookup(2).throw_during_copy = true;
570 EXPECT_ANY_THROW({ MapType map_copy(map); });
571}
572
573TEST(map, MoveConstructorExceptions)
574{
576 MapType map;
577 map.add(1, 1);
578 map.add(2, 2);
579 map.lookup(1).throw_during_move = true;
580 EXPECT_ANY_THROW({ MapType map_moved(std::move(map)); });
581 map.add(5, 5); /* NOLINT: bugprone-use-after-move */
582}
583
584TEST(map, AddNewExceptions)
585{
587 ExceptionThrower key1 = 1;
588 key1.throw_during_copy = true;
589 ExceptionThrower value1;
590 EXPECT_ANY_THROW({ map.add_new(key1, value1); });
591 EXPECT_EQ(map.size(), 0);
592 ExceptionThrower key2 = 2;
593 ExceptionThrower value2;
594 value2.throw_during_copy = true;
595 EXPECT_ANY_THROW({ map.add_new(key2, value2); });
596}
597
598TEST(map, ReserveExceptions)
599{
601 map.add(3, 3);
602 map.add(5, 5);
603 map.add(2, 2);
604 map.lookup(2).throw_during_move = true;
605 EXPECT_ANY_THROW({ map.reserve(100); });
606 map.add(1, 1);
607 map.add(5, 5);
608}
609
610TEST(map, PopExceptions)
611{
613 map.add(3, 3);
614 map.lookup(3).throw_during_move = true;
615 EXPECT_ANY_THROW({ map.pop(3); }); /* NOLINT: bugprone-throw-keyword-missing */
616 EXPECT_EQ(map.size(), 1);
617 map.add(1, 1);
618 EXPECT_EQ(map.size(), 2);
619}
620
621TEST(map, AddOrModifyExceptions)
622{
624 auto create_fn = [](ExceptionThrower * /*v*/) { throw std::runtime_error(""); };
625 auto modify_fn = [](ExceptionThrower * /*v*/) {};
626 EXPECT_ANY_THROW({ map.add_or_modify(3, create_fn, modify_fn); });
627}
628
629namespace {
630enum class TestEnum {
631 A = 0,
632 B = 1,
633 C = 2,
634 D = 1,
635};
636}
637
638TEST(map, EnumKey)
639{
641 map.add(TestEnum::A, 4);
642 map.add(TestEnum::B, 6);
643 EXPECT_EQ(map.lookup(TestEnum::A), 4);
644 EXPECT_EQ(map.lookup(TestEnum::B), 6);
645 EXPECT_EQ(map.lookup(TestEnum::D), 6);
646 EXPECT_FALSE(map.contains(TestEnum::C));
647 map.lookup(TestEnum::D) = 10;
648 EXPECT_EQ(map.lookup(TestEnum::B), 10);
649}
650
651TEST(map, GenericAlgorithms)
652{
653 Map<int, int> map;
654 map.add(5, 2);
655 map.add(1, 4);
656 map.add(2, 2);
657 map.add(7, 1);
658 map.add(8, 6);
659 EXPECT_TRUE(std::any_of(map.keys().begin(), map.keys().end(), [](int v) { return v == 1; }));
660 EXPECT_TRUE(std::any_of(map.values().begin(), map.values().end(), [](int v) { return v == 1; }));
661 EXPECT_TRUE(std::any_of(
662 map.items().begin(), map.items().end(), [](auto item) { return item.value == 1; }));
663 EXPECT_EQ(std::count(map.values().begin(), map.values().end(), 2), 2);
664 EXPECT_EQ(std::count(map.values().begin(), map.values().end(), 4), 1);
665 EXPECT_EQ(std::count(map.keys().begin(), map.keys().end(), 7), 1);
666}
667
668TEST(map, AddAsVariadic)
669{
671 map.add_as(3, "hello", 2);
672 map.add_as(2, "test", 1);
673 EXPECT_EQ(map.lookup(3), "he");
674 EXPECT_EQ(map.lookup(2), "t");
675}
676
677TEST(map, RemoveDuringIteration)
678{
679 Map<int, int> map;
680 map.add(2, 1);
681 map.add(5, 2);
682 map.add(1, 2);
683 map.add(6, 0);
684 map.add(3, 3);
685
686 EXPECT_EQ(map.size(), 5);
687
689 Iter begin = map.items().begin();
690 Iter end = map.items().end();
691 for (Iter iter = begin; iter != end; ++iter) {
692 MutableMapItem<int, int> item = *iter;
693 if (item.value == 2) {
694 map.remove(iter);
695 }
696 }
697
698 EXPECT_EQ(map.size(), 3);
699 EXPECT_EQ(map.lookup(2), 1);
700 EXPECT_EQ(map.lookup(6), 0);
701 EXPECT_EQ(map.lookup(3), 3);
702}
703
704TEST(map, RemoveIf)
705{
707 for (const int64_t i : IndexRange(100)) {
708 map.add(i * i, i);
709 }
710 const int64_t removed = map.remove_if([](auto item) { return item.key > 100; });
711 EXPECT_EQ(map.size() + removed, 100);
712 for (const int64_t i : IndexRange(100)) {
713 if (i <= 10) {
714 EXPECT_EQ(map.lookup(i * i), i);
715 }
716 else {
717 EXPECT_FALSE(map.contains(i * i));
718 }
719 }
720}
721
722TEST(map, LookupKey)
723{
725 map.add("a", 0);
726 map.add("b", 1);
727 map.add("c", 2);
728 EXPECT_EQ(map.lookup_key("a"), "a");
729 EXPECT_EQ(map.lookup_key_as("c"), "c");
730 EXPECT_EQ(map.lookup_key_ptr_as("d"), nullptr);
731 EXPECT_EQ(map.lookup_key_ptr_as("b")->size(), 1);
732 EXPECT_EQ(map.lookup_key_ptr("a"), map.lookup_key_ptr_as("a"));
733}
734
735TEST(map, VectorKey)
736{
737 Map<Vector<int>, int> map;
738 map.add({1, 2, 3}, 100);
739 map.add({3, 2, 1}, 200);
740
741 EXPECT_EQ(map.size(), 2);
742 EXPECT_EQ(map.lookup({1, 2, 3}), 100);
743 EXPECT_EQ(map.lookup({3, 2, 1}), 200);
744 EXPECT_FALSE(map.contains({1, 2}));
745
746 std::array<int, 3> array = {1, 2, 3};
747 EXPECT_EQ(map.lookup_as(array), 100);
748
749 map.remove_as(Vector<int>({1, 2, 3}).as_mutable_span());
750 EXPECT_EQ(map.size(), 1);
751}
752
753TEST(map, Equality)
754{
757
758 EXPECT_EQ(a, b);
759 a.add(3, 4);
760 EXPECT_NE(a, b);
761 b.add(3, 4);
762 EXPECT_EQ(a, b);
763
764 a.add(4, 10);
765 b.add(4, 11);
766 EXPECT_NE(a, b);
767}
768
769TEST(map, AddCbMove)
770{
772 std::string value = "a";
773 bool value_checked = false;
774 map.lookup_or_add_cb(std::move(value), [&]() {
775 EXPECT_EQ(value, "a");
776 value_checked = true;
777 return 10;
778 });
779 EXPECT_TRUE(value_checked);
780 EXPECT_EQ(value, "");
781}
782
783struct IntMapKey {
784 int value;
785};
786
788 uint64_t operator()(const IntMapKey *key) const
789 {
790 return uint64_t(key->value);
791 }
792};
793
795 bool operator()(const IntMapKey *a, const IntMapKey *b) const
796 {
797 return a->value == b->value;
798 }
799};
800
801TEST(map, PointerKeyCustomEq)
802{
803 IntMapKey key1a{1};
804 IntMapKey key1b{1};
805 IntMapKey key2{2};
807 EXPECT_TRUE(map.add(&key1a, 10));
808 EXPECT_FALSE(map.add(&key1b, 11));
809 EXPECT_EQ(map.lookup(&key1a), 10);
810 EXPECT_EQ(map.lookup(&key1b), 10);
811 EXPECT_TRUE(map.add(&key2, 20));
812 EXPECT_TRUE(map.remove(&key1b));
813 EXPECT_FALSE(map.contains(&key1a));
814 EXPECT_FALSE(map.contains(&key1b));
815 EXPECT_TRUE(map.remove(&key2));
816 EXPECT_FALSE(map.remove(&key1a));
817 EXPECT_FALSE(map.remove(&key2));
818}
819
823#if 0
824template<typename MapT>
825BLI_NOINLINE void benchmark_random_ints(StringRef name, int amount, int factor)
826{
827 RNG *rng = BLI_rng_new(0);
828 Vector<int> values;
829 for (int i = 0; i < amount; i++) {
830 values.append(BLI_rng_get_int(rng) * factor);
831 }
832 BLI_rng_free(rng);
833
834 MapT map;
835 {
836 SCOPED_TIMER(name + " Add");
837 for (int value : values) {
838 map.add(value, value);
839 }
840 }
841 int count = 0;
842 {
843 SCOPED_TIMER(name + " Contains");
844 for (int value : values) {
845 count += map.contains(value);
846 }
847 }
848 {
849 SCOPED_TIMER(name + " Remove");
850 for (int value : values) {
851 count += map.remove(value);
852 }
853 }
854
855 /* Print the value for simple error checking and to avoid some compiler optimizations. */
856 std::cout << "Count: " << count << "\n";
857}
858
863template<typename Key, typename Value> class StdUnorderedMapWrapper {
864 private:
865 using MapType = std::unordered_map<Key, Value, DefaultHash<Key>>;
866 MapType map_;
867
868 public:
869 int64_t size() const
870 {
871 return int64_t(map_.size());
872 }
873
874 bool is_empty() const
875 {
876 return map_.empty();
877 }
878
879 void reserve(int64_t n)
880 {
881 map_.reserve(n);
882 }
883
884 template<typename ForwardKey, typename... ForwardValue>
885 void add_new(ForwardKey &&key, ForwardValue &&...value)
886 {
887 map_.insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)});
888 }
889
890 template<typename ForwardKey, typename... ForwardValue>
891 bool add(ForwardKey &&key, ForwardValue &&...value)
892 {
893 return map_
894 .insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)})
895 .second;
896 }
897
898 bool contains(const Key &key) const
899 {
900 return map_.find(key) != map_.end();
901 }
902
903 bool remove(const Key &key)
904 {
905 return bool(map_.erase(key));
906 }
907
908 Value &lookup(const Key &key)
909 {
910 return map_.find(key)->second;
911 }
912
913 const Value &lookup(const Key &key) const
914 {
915 return map_.find(key)->second;
916 }
917
918 void clear()
919 {
920 map_.clear();
921 }
922
923 void print_stats(StringRef /*name*/ = "") const {}
924};
925
926TEST(map, Benchmark)
927{
928 for (int i = 0; i < 3; i++) {
929 benchmark_random_ints<Map<int, int>>("Map ", 1000000, 1);
930 benchmark_random_ints<StdUnorderedMapWrapper<int, int>>("std::unordered_map", 1000000, 1);
931 }
932 std::cout << "\n";
933 for (int i = 0; i < 3; i++) {
934 uint32_t factor = (3 << 10);
935 benchmark_random_ints<Map<int, int>>("Map ", 1000000, factor);
936 benchmark_random_ints<StdUnorderedMapWrapper<int, int>>("std::unordered_map", 1000000, factor);
937 }
938}
939
991
992#endif /* Benchmark */
993
994} // namespace blender::tests
Random number functions.
#define SCOPED_TIMER(name)
Definition BLI_timeit.hh:64
#define C
Definition RandGen.cpp:29
#define BLI_NOINLINE
#define A
long long int int64_t
constexpr IndexRange()=default
SubIterator begin() const
Definition BLI_map.hh:768
SubIterator end() const
Definition BLI_map.hh:778
void clear()
Definition BLI_map.hh:1038
const Value * lookup_ptr(const Key &key) const
Definition BLI_map.hh:508
Value pop(const Key &key)
Definition BLI_map.hh:402
std::optional< Value > lookup_try(const Key &key) const
Definition BLI_map.hh:531
std::optional< Value > pop_try(const Key &key)
Definition BLI_map.hh:419
Value & lookup_or_add_default(const Key &key)
Definition BLI_map.hh:639
const Key & lookup_key_as(const ForwardKey &key) const
Definition BLI_map.hh:660
bool remove_as(const ForwardKey &key)
Definition BLI_map.hh:372
bool add_overwrite(const Key &key, const Value &value)
Definition BLI_map.hh:325
ValueIterator values() const &
Definition BLI_map.hh:884
bool add(const Key &key, const Value &value)
Definition BLI_map.hh:295
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
const Key * lookup_key_ptr_as(const ForwardKey &key) const
Definition BLI_map.hh:674
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
void foreach_item(const FuncT &func) const
Definition BLI_map.hh:687
const Key & lookup_key(const Key &key) const
Definition BLI_map.hh:656
bool add_as(ForwardKey &&key, ForwardValue &&...value)
Definition BLI_map.hh:312
const Key * lookup_key_ptr(const Key &key) const
Definition BLI_map.hh:670
void add_new(const Key &key, const Value &value)
Definition BLI_map.hh:265
const Value & lookup_as(const ForwardKey &key) const
Definition BLI_map.hh:553
bool remove(const Key &key)
Definition BLI_map.hh:368
int64_t size() const
Definition BLI_map.hh:976
KeyIterator keys() const &
Definition BLI_map.hh:875
bool is_empty() const
Definition BLI_map.hh:986
void reserve(int64_t n)
Definition BLI_map.hh:1028
bool contains(const Key &key) const
Definition BLI_map.hh:353
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition BLI_map.hh:481
int64_t remove_if(Predicate &&predicate)
Definition BLI_map.hh:948
Value pop_default(const Key &key, const Value &default_value)
Definition BLI_map.hh:439
ItemIterator items() const &
Definition BLI_map.hh:902
Value & lookup_or_add(const Key &key, const Value &value)
Definition BLI_map.hh:588
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
int64_t size() const
bool contains(const T &value) const
void append(const T &value)
int64_t first_index_of(const T &value) const
MutableSpan< T > as_mutable_span()
#define EXPECT_FALSE(result)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define B
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)
const MultiFunction & lookup(UString id)
TEST(any_virtual, DefaultConstructor)
static float return_42()
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
BLI_INLINE float D(const float *data, const int res[3], int x, int y, int z)
Definition voxel.cc:16
Vector< nodes::ItemDeclarationPtr >::const_iterator ItemIterator
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
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
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)
constexpr uint64_t get_default_hash(const T &v, const Args &...args)
Definition BLI_hash.hh:252
bool operator()(const IntMapKey *a, const IntMapKey *b) const
uint64_t operator()(const IntMapKey *key) const