1 /*
2     Copyright (c) 2005-2021 Intel Corporation
3 
4     Licensed under the Apache License, Version 2.0 (the "License");
5     you may not use this file except in compliance with the License.
6     You may obtain a copy of the License at
7 
8         http://www.apache.org/licenses/LICENSE-2.0
9 
10     Unless required by applicable law or agreed to in writing, software
11     distributed under the License is distributed on an "AS IS" BASIS,
12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13     See the License for the specific language governing permissions and
14     limitations under the License.
15 */
16 
17 #if __INTEL_COMPILER && _MSC_VER
18 #pragma warning(disable : 2586) // decorated name length exceeded, name was truncated
19 #endif
20 
21 #define TBB_DEFINE_STD_HASH_SPECIALIZATIONS 1
22 #include <tbb/concurrent_unordered_map.h>
23 #include "common/concurrent_unordered_common.h"
24 
25 //! \file test_concurrent_unordered_map.cpp
26 //! \brief Test for [containers.concurrent_unordered_map containers.concurrent_unordered_multimap] specifications
27 
28 template <typename... Args>
29 struct AllowMultimapping<tbb::concurrent_unordered_multimap<Args...>> : std::true_type {};
30 
31 template <typename Key, typename Mapped>
32 using MyAllocator = LocalCountingAllocator<std::allocator<std::pair<const Key, Mapped>>>;
33 
34 using move_support_tests::FooWithAssign;
35 
36 using map_type = tbb::concurrent_unordered_map<int, int, std::hash<int>, std::equal_to<int>, MyAllocator<int, int>>;
37 using multimap_type = tbb::concurrent_unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, MyAllocator<int, int>>;
38 using degenerate_map_type = tbb::concurrent_unordered_map<int, int, degenerate_hash<int>, std::equal_to<int>, MyAllocator<int, int>>;
39 using degenerate_multimap_type = tbb::concurrent_unordered_multimap<int, int, degenerate_hash<int>, std::equal_to<int>, MyAllocator<int, int>>;
40 
41 using checked_map_type = tbb::concurrent_unordered_map<int, CheckType<int>, std::hash<int>, std::equal_to<int>, MyAllocator<int, CheckType<int>>>;
42 using checked_multimap_type = tbb::concurrent_unordered_multimap<int, CheckType<int>, std::hash<int>, std::equal_to<int>, MyAllocator<int, CheckType<int>>>;
43 using checked_state_map_type = tbb::concurrent_unordered_map<intptr_t, FooWithAssign, std::hash<intptr_t>,
44                                                              std::equal_to<intptr_t>, MyAllocator<intptr_t, FooWithAssign>>;
45 using checked_state_multimap_type = tbb::concurrent_unordered_multimap<intptr_t, FooWithAssign, std::hash<intptr_t>,
46                                                                        std::equal_to<intptr_t>, MyAllocator<intptr_t, FooWithAssign>>;
47 
48 struct CumapTraits : UnorderedMoveTraitsBase {
49     template <typename T, typename Allocator>
50     using container_type = tbb::concurrent_unordered_map<T, T, std::hash<T>, std::equal_to<T>, Allocator>;
51 
52     template <typename T>
53     using container_value_type = std::pair<const T, T>;
54 
55     using init_iterator_type = move_support_tests::FooPairIterator;
56 }; // struct CumapTraits
57 
58 struct CumultimapTraits : UnorderedMoveTraitsBase {
59     template <typename T, typename Allocator>
60     using container_type = tbb::concurrent_unordered_multimap<T, T, std::hash<T>, std::equal_to<T>, Allocator>;
61 
62     template <typename T>
63     using container_value_type = std::pair<const T, T>;
64 
65     using init_iterator_type = move_support_tests::FooPairIterator;
66 }; // struct CumultimapTraits
67 
68 template <>
69 struct SpecialTests<map_type> {
70     static void Test() {
71         SpecialMapTests<map_type>();
72     }
73 };
74 
75 template <>
76 struct SpecialTests<multimap_type> {
77     static void Test() {
78         SpecialMultiMapTests<multimap_type>();
79     }
80 };
81 
82 struct UnorderedMapTypesTester {
83     template <template <typename...> class GeneralTableType, typename Key, typename Mapped>
84     using table_type = GeneralTableType<Key, Mapped, std::hash<Key>, utils::IsEqual>;
85 
86     template <bool DefCtorPresent, typename ValueType>
87     void check( const std::list<ValueType>& lst ) {
88         using key_type = typename std::remove_const<typename ValueType::first_type>::type;
89         using mapped_type = typename ValueType::second_type;
90 
91         TypeTester<DefCtorPresent, table_type<tbb::concurrent_unordered_map, key_type, mapped_type>>(lst);
92         TypeTester<DefCtorPresent, table_type<tbb::concurrent_unordered_multimap, key_type, mapped_type>>(lst);
93     }
94 }; // struct UnorderedMapTypesTester
95 
96 void test_specific_types() {
97     test_map_specific_types<UnorderedMapTypesTester>();
98 
99     // Regression test for a problem with excessive requirements of emplace()
100     test_emplace_insert<tbb::concurrent_unordered_map<int*, test::unique_ptr<int>>, std::false_type>
101                        (new int, new int);
102     test_emplace_insert<tbb::concurrent_unordered_multimap<int*, test::unique_ptr<int>>, std::false_type>
103                        (new int, new int);
104 }
105 
106 //! \brief \ref stress \ref error_guessing
107 TEST_CASE("basic test for concurrent_unordered_map with degenerate hash") {
108     test_basic<degenerate_map_type>();
109 }
110 
111 //! \brief \ref stress \ref error_guessing
112 TEST_CASE("basic test for concurrent_unordered_multimap with degenerate hash") {
113     test_basic<degenerate_multimap_type>();
114 }
115 
116 //! \brief \ref resource_usage
117 TEST_CASE("basic test for concurrent_unordered_map with elements ctor and dtor check") {
118     Checker<checked_map_type::mapped_type> checker;
119     test_basic<checked_map_type>();
120 }
121 
122 //! \brief \ref resource_usage
123 TEST_CASE("basic test for concurrent_unordered_multimap with elements ctor and dtor check") {
124     Checker<checked_multimap_type::mapped_type> checker;
125     test_basic<checked_multimap_type>();
126 }
127 
128 //! \brief \ref resource_usage
129 TEST_CASE("basic test for concurrent_unordered_map with elements state check") {
130     test_basic<checked_state_map_type, /*CheckState = */std::true_type>();
131 }
132 
133 //! \brief \ref resource_usage
134 TEST_CASE("basic test for concurrent_unordered_multimap with elements state check") {
135     test_basic<checked_state_multimap_type, /*CheckState = */std::true_type>();
136 }
137 
138 //! \brief \ref stress \ref error_guessing
139 TEST_CASE("multithreading support in concurrent_unordered_map with degenerate hash") {
140     test_concurrent<degenerate_map_type>();
141 }
142 
143 //! \brief \ref stress \ref error_guessing
144 TEST_CASE("multithreading support in concurrent_unordered_multimap with degenerate hash") {
145     test_concurrent<degenerate_multimap_type>();
146 }
147 
148 //! \brief \ref stress \ref error_guessing
149 TEST_CASE("multithreading support in concurrent_unordered_multimap no unique keys") {
150     test_concurrent<multimap_type>(true);
151 }
152 
153 //! \brief \ref stress \ref error_guessing
154 TEST_CASE("multithreading support in concurrent_unordered_multimap with degenerate hash and no unique keys") {
155     test_concurrent<degenerate_multimap_type>(true);
156 }
157 
158 //! \brief \ref resource_usage
159 TEST_CASE("multithreading support in concurrent_unordered_map with elements ctor and dtor check") {
160     Checker<checked_map_type::mapped_type> checker;
161     test_concurrent<checked_map_type>();
162 }
163 
164 //! \brief \ref resource_usage
165 TEST_CASE("multithreading support in concurrent_unordered_multimap with elements ctor and dtor check") {
166     Checker<checked_multimap_type::mapped_type> checker;
167     test_concurrent<checked_multimap_type>();
168 }
169 
170 //! \brief \ref resource_usage
171 TEST_CASE("multithreading support in concurrent_unordered_map with elements state check") {
172     test_concurrent<checked_state_map_type>();
173 }
174 
175 //! \brief \ref resource_usage
176 TEST_CASE("multithreading support in concurrent_unordered_multimap with elements state check") {
177     test_concurrent<checked_state_multimap_type>();
178 }
179 
180 //! \brief \ref interface \ref error_guessing
181 TEST_CASE("range based for support in concurrent_unordered_map") {
182     test_range_based_for_support<map_type>();
183 }
184 
185 //! \brief \ref interface \ref error_guessing
186 TEST_CASE("range based for support in concurrent_unordered_multimap") {
187     test_range_based_for_support<multimap_type>();
188 }
189 
190 //! \brief \ref stress \ref error_guessing
191 TEST_CASE("merge and concurrent merge in concurrent_unordered_map with degenerative hash") {
192     node_handling_tests::test_merge<map_type, degenerate_multimap_type>(1000);
193 }
194 
195 //! \brief \ref regression
196 TEST_CASE("concurrent_unordered map/multimap with specific key/mapped types") {
197     test_specific_types();
198 }
199 
200 //! \brief \ref error_guessing
201 TEST_CASE("concurrent_unordered_map::swap with not always equal allocator") {
202     using not_always_equal_alloc_map_type = tbb::concurrent_unordered_map<int, int, std::hash<int>, std::equal_to<int>,
203                                                                           NotAlwaysEqualAllocator<std::pair<const int, int>>>;
204     test_swap_not_always_equal_allocator<not_always_equal_alloc_map_type>();
205 }
206 
207 //! \brief \ref error_guessing
208 TEST_CASE("concurrent_unordered_multimap::swap with not always equal allocator") {
209     using not_always_equal_alloc_mmap_type = tbb::concurrent_unordered_multimap<int, int, std::hash<int>, std::equal_to<int>,
210                                                                                 NotAlwaysEqualAllocator<std::pair<const int, int>>>;
211     test_swap_not_always_equal_allocator<not_always_equal_alloc_mmap_type>();
212 }
213 
214 #if TBB_USE_EXCEPTIONS
215 //! \brief \ref error_guessing
216 TEST_CASE("concurrent_unordered_map throwing copy constructor") {
217     using exception_map_type = tbb::concurrent_unordered_map<ThrowOnCopy, ThrowOnCopy>;
218     test_exception_on_copy_ctor<exception_map_type>();
219 }
220 
221 //! \brief \ref error_guessing
222 TEST_CASE("concurrent_unordered_multimap throwing copy constructor") {
223     using exception_mmap_type = tbb::concurrent_unordered_multimap<ThrowOnCopy, ThrowOnCopy>;
224     test_exception_on_copy_ctor<exception_mmap_type>();
225 }
226 
227 //! \brief \ref error_guessing
228 TEST_CASE("concurrent_unordered_map whitebox throwing copy constructor") {
229     using allocator_type = StaticSharedCountingAllocator<std::allocator<std::pair<const int, int>>>;
230     using exception_mmap_type = tbb::concurrent_unordered_map<int, int, std::hash<int>, std::equal_to<int>, allocator_type>;
231 
232     exception_mmap_type map;
233     for (int i = 0; i < 10; ++i) {
234         map.insert(std::pair<const int, int>(i, 42));
235     }
236 
237     allocator_type::set_limits(1);
238     REQUIRE_THROWS_AS( [&] {
239         exception_mmap_type map1(map);
240         utils::suppress_unused_warning(map1);
241     }(), const std::bad_alloc);
242 }
243 
244 #endif // TBB_USE_EXCEPTIONS
245 
246 // TODO: add test_scoped_allocator support with broken macro
247