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 #include "oneapi/tbb/concurrent_unordered_map.h"
22 #include <common/test.h>
23 #include <common/utils.h>
24 #include <common/concurrent_unordered_common.h>
25 #include <memory>
26 #include <type_traits>
27 
28 //! \file conformance_concurrent_unordered_map.cpp
29 //! \brief Test for [containers.concurrent_unordered_map containers.concurrent_unordered_multimap] specifications
30 
31 template <typename... Args>
32 struct AllowMultimapping<oneapi::tbb::concurrent_unordered_multimap<Args...>> : std::true_type {};
33 
34 template <typename Key, typename Mapped>
35 using Allocator = LocalCountingAllocator<std::allocator<std::pair<const Key, Mapped>>>;
36 
37 using map_type = oneapi::tbb::concurrent_unordered_map<int, int, std::hash<int>, std::equal_to<int>, Allocator<int, int>>;
38 using multimap_type = oneapi::tbb::concurrent_unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, Allocator<int, int>>;
39 
40 template <>
41 struct SpecialTests<map_type> {
TestSpecialTests42     static void Test() {
43         SpecialMapTests<map_type>();
44     }
45 };
46 
47 template <>
48 struct SpecialTests<multimap_type> {
TestSpecialTests49     static void Test() {
50         SpecialMultiMapTests<multimap_type>();
51     }
52 };
53 
54 template <template <typename... > class ContainerType>
test_member_types()55 void test_member_types() {
56     using default_container_type = ContainerType<int, int>;
57     static_assert(std::is_same<typename default_container_type::hasher, std::hash<int>>::value,
58                   "Incorrect default template hasher");
59     static_assert(std::is_same<typename default_container_type::key_equal, std::equal_to<int>>::value,
60                   "Incorrect default template key equality");
61     static_assert(std::is_same<typename default_container_type::allocator_type,
62                                oneapi::tbb::tbb_allocator<std::pair<const int, int>>>::value,
63                   "Incorrect default template allocator");
64 
65     auto test_hasher = [](const int&)->std::size_t { return 0; };
66     auto test_equality = [](const int&, const int&)->bool { return true; };
67     using test_allocator_type = std::allocator<std::pair<const int, int>>;
68 
69     using container_type = ContainerType<int, int, decltype(test_hasher),
70                                          decltype(test_equality), test_allocator_type>;
71 
72     static_assert(std::is_same<typename container_type::key_type, int>::value,
73                   "Incorrect container key_type member type");
74     static_assert(std::is_same<typename container_type::mapped_type, int>::value,
75                   "Incorrect container mapped_type member type");
76     static_assert(std::is_same<typename container_type::value_type, std::pair<const int, int>>::value,
77                   "Incorrect container value_type member type");
78 
79     static_assert(std::is_unsigned<typename container_type::size_type>::value,
80                   "Incorrect container size_type member type");
81     static_assert(std::is_signed<typename container_type::difference_type>::value,
82                   "Incorrect container difference_type member type");
83 
84     static_assert(std::is_same<typename container_type::hasher, decltype(test_hasher)>::value,
85                   "Incorrect container hasher member type");
86     static_assert(std::is_same<typename container_type::key_equal, decltype(test_equality)>::value,
87                   "Incorrect container key_equal member type");
88 
89     using transparent_container_type = ContainerType<int, int, hasher_with_transparent_key_equal,
90                                                      std::equal_to<int>, test_allocator_type>;
91 
92     static_assert(std::is_same<typename transparent_container_type::key_equal, transparent_key_equality>::value,
93                   "Incorrect container key_equal member type");
94     static_assert(std::is_same<typename container_type::allocator_type, test_allocator_type>::value,
95                   "Incorrect container allocator_type member type");
96 
97     using value_type = typename container_type::value_type;
98     static_assert(std::is_same<typename container_type::reference, value_type&>::value,
99                   "Incorrect container reference member type");
100     static_assert(std::is_same<typename container_type::const_reference, const value_type&>::value,
101                   "Incorrect container const_reference member type");
102     using allocator_type = typename container_type::allocator_type;
103     static_assert(std::is_same<typename container_type::pointer, typename std::allocator_traits<allocator_type>::pointer>::value,
104                   "Incorrect container pointer member type");
105     static_assert(std::is_same<typename container_type::const_pointer, typename std::allocator_traits<allocator_type>::const_pointer>::value,
106                   "Incorrect container const_pointer member type");
107 
108     static_assert(utils::is_forward_iterator<typename container_type::iterator>::value,
109                   "Incorrect container iterator member type");
110     static_assert(!std::is_const<typename container_type::iterator::value_type>::value,
111                   "Incorrect container iterator member type");
112     static_assert(utils::is_forward_iterator<typename container_type::const_iterator>::value,
113                   "Incorrect container const_iterator member type");
114     static_assert(std::is_const<typename container_type::const_iterator::value_type>::value,
115                   "Incorrect container iterator member type");
116     static_assert(utils::is_forward_iterator<typename container_type::local_iterator>::value,
117                   "Incorrect container local_iterator member type");
118     static_assert(!std::is_const<typename container_type::local_iterator::value_type>::value,
119                   "Incorrect container local_iterator member type");
120     static_assert(utils::is_forward_iterator<typename container_type::const_local_iterator>::value,
121                   "Incorrect container const_local_iterator member type");
122     static_assert(std::is_const<typename container_type::const_local_iterator::value_type>::value,
123                   "Incorrect container const_local_iterator member type");
124 }
125 
126 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
127 template <template <typename...> typename TMap>
test_deduction_guides()128 void test_deduction_guides() {
129     using ComplexType = std::pair<int, std::string>;
130     using ComplexTypeConst = std::pair<const int, std::string>;
131     std::vector<ComplexType> v;
132     auto l = { ComplexTypeConst(1, "one"), ComplexTypeConst(2, "two")};
133     using custom_allocator_type = std::allocator<ComplexTypeConst>;
134 
135     // check TMap(InputIterator, InputIterator)
136     TMap m0(v.begin(), v.end());
137     static_assert(std::is_same<decltype(m0), TMap<int, std::string>>::value);
138 
139     // check TMap(InputIterator, InputIterator, size_t)
140     TMap m1(v.begin(), v.end(), 1);
141     static_assert(std::is_same<decltype(m1), TMap<int, std::string>>::value);
142 
143     // check TMap(InputIterator, InputIterator, size_t, Hasher)
144     TMap m2(v.begin(), v.end(), 4, degenerate_hash<int>());
145     static_assert(std::is_same<decltype(m2), TMap<int, std::string, degenerate_hash<int>>>::value);
146 
147     // check TMap(InputIterator, InputIterator, size_t, Hasher, Equality)
148     TMap m3(v.begin(), v.end(), 4, degenerate_hash<int>(), std::less<int>());
149     static_assert(std::is_same<decltype(m3), TMap<int, std::string, degenerate_hash<int>, std::less<int>>>::value);
150 
151     // check TMap(InputIterator, InputIterator, size_t, Hasher, Equality, Allocator)
152     TMap m4(v.begin(), v.end(), 4, degenerate_hash<int>(), std::less<int>(), custom_allocator_type{});
153     static_assert(std::is_same<decltype(m4), TMap<int, std::string, degenerate_hash<int>,
154         std::less<int>, custom_allocator_type>>::value);
155 
156     // check TMap(InputIterator, InputIterator, size_t, Allocator)
157     TMap m5(v.begin(), v.end(), 5, custom_allocator_type{});
158     static_assert(std::is_same<decltype(m5), TMap<int, std::string, std::hash<int>,
159         std::equal_to<int>, custom_allocator_type>>::value);
160 
161     // check TMap(InputIterator, InputIterator, size_t, Hasher, Allocator)
162     TMap m6(v.begin(), v.end(), 4, degenerate_hash<int>(), custom_allocator_type{});
163     static_assert(std::is_same<decltype(m6), TMap<int, std::string, degenerate_hash<int>,
164         std::equal_to<int>, custom_allocator_type>>::value);
165 
166     // check TMap(std::initializer_list)
167     TMap m7(l);
168     static_assert(std::is_same<decltype(m7), TMap<int, std::string>>::value);
169 
170     // check TMap(std::initializer_list, size_t)
171     TMap m8(l, 1);
172     static_assert(std::is_same<decltype(m8), TMap<int, std::string>>::value);
173 
174     // check TMap(std::initializer_list, size_t, Hasher)
175     TMap m9(l, 4, degenerate_hash<int>());
176     static_assert(std::is_same<decltype(m9), TMap<int, std::string, degenerate_hash<int>>>::value);
177 
178     // check TMap(std::initializer_list, size_t, Hasher, Equality)
179     TMap m10(l, 4, degenerate_hash<int>(), std::less<int>());
180     static_assert(std::is_same<decltype(m10), TMap<int, std::string, degenerate_hash<int>, std::less<int>>>::value);
181 
182     // check TMap(std::initializer_list, size_t, Hasher, Equality, Allocator)
183     TMap m11(l, 4, degenerate_hash<int>(), std::less<int>(), custom_allocator_type{});
184     static_assert(std::is_same<decltype(m11), TMap<int, std::string, degenerate_hash<int>,
185         std::less<int>, custom_allocator_type>>::value);
186 
187     // check TMap(std::initializer_list, size_t, Allocator)
188     TMap m12(l, 4, custom_allocator_type{});
189     static_assert(std::is_same<decltype(m12), TMap<int, std::string, std::hash<int>,
190         std::equal_to<int>, custom_allocator_type>>::value);
191 
192     // check TMap(std::initializer_list, size_t, Hasher, Allocator)
193     TMap m13(l, 4, degenerate_hash<int>(), custom_allocator_type{});
194     static_assert(std::is_same<decltype(m13), TMap<int, std::string, degenerate_hash<int>,
195         std::equal_to<int>, custom_allocator_type>>::value);
196 
197     // check TMap(TMap &)
198     TMap m14(m1);
199     static_assert(std::is_same<decltype(m14), decltype(m1)>::value);
200 
201     // check TMap(TMap &, Allocator)
202     // TODO: investigate why no implicit deduction guides generated for this ctor
203     TMap m15(m5, custom_allocator_type{});
204     static_assert(std::is_same<decltype(m15), decltype(m5)>::value);
205 
206     // check TMap(TMap &&)
207     TMap m16(std::move(m1));
208     static_assert(std::is_same<decltype(m16), decltype(m1)>::value);
209 
210     // check TMap(TMap &&, Allocator)
211     // TODO: investigate why no implicit deduction guides generated for this ctor
212     TMap m17(std::move(m5), custom_allocator_type{});
213     static_assert(std::is_same<decltype(m17), decltype(m5)>::value);
214 }
215 #endif
216 
test_heterogeneous_functions()217 void test_heterogeneous_functions() {
218     check_heterogeneous_functions_key_int<oneapi::tbb::concurrent_unordered_map, int, int>();
219     check_heterogeneous_functions_key_int<oneapi::tbb::concurrent_unordered_multimap, int, int>();
220     check_heterogeneous_functions_key_string<oneapi::tbb::concurrent_unordered_map, std::string, std::string>();
221     check_heterogeneous_functions_key_string<oneapi::tbb::concurrent_unordered_multimap, std::string, std::string>();
222 }
223 
224 struct CumapTraits : UnorderedMoveTraitsBase {
225     template <typename T, typename Allocator>
226     using container_type = oneapi::tbb::concurrent_unordered_map<T, T, std::hash<T>, std::equal_to<T>, Allocator>;
227 
228     template <typename T>
229     using container_value_type = std::pair<const T, T>;
230 
231     using init_iterator_type = move_support_tests::FooPairIterator;
232 }; // struct CumapTraits
233 
234 struct CumultimapTraits : UnorderedMoveTraitsBase {
235     template <typename T, typename Allocator>
236     using container_type = oneapi::tbb::concurrent_unordered_multimap<T, T, std::hash<T>, std::equal_to<T>, Allocator>;
237 
238     template <typename T>
239     using container_value_type = std::pair<const T, T>;
240 
241     using init_iterator_type = move_support_tests::FooPairIterator;
242 }; // struct CumultimapTraits
243 
244 //! Testing concurrent_unordered_map member types
245 //! \brief \ref interface \ref requirement
246 TEST_CASE("concurrent_unordered_map member types") {
247     test_member_types<oneapi::tbb::concurrent_unordered_map>();
248 }
249 
250 //! Testing requirements of concurrent_unordered_map
251 //! \brief \ref interface \ref requirement
252 TEST_CASE("concurrent_unordered_map requirements") {
253     test_basic<map_type>();
254 }
255 
256 //! Testing multithreading support in concurrent_unordered_map
257 //! \brief \ref requirement
258 TEST_CASE("concurrent_unordered_map multithreading support") {
259     test_concurrent<map_type>();
260 }
261 
262 //! Testing move constructors and assignment operator in concurrent_unordered_map
263 //! \brief \ref interface \ref requirement
264 TEST_CASE("concurrent_unordered_map move semantics support") {
265     test_rvalue_ref_support<CumapTraits>();
266 }
267 
268 //! Testing std::initializer_list constructors and modifiers in concurrent_unordered_map
269 //! \brief \ref interface \ref requirement
270 TEST_CASE("std::initializer_list support in concurrent_unordered_map") {
271     test_initializer_list_support<map_type>({{1, 1}, {2, 2}, {3, 3}, {4, 4}});
272 }
273 
274 //! Testing node handling in concurrent_unordered_map
275 //! \brief \ref interface \ref requirement
276 TEST_CASE("node handling support in concurrent_unordered_map") {
277     node_handling_tests::test_node_handling_support<map_type>();
278 }
279 
280 //! Testing std::allocator_traits support in concurrent_unordered_map
281 //! \brief \ref interface \ref requirement
282 TEST_CASE("std::allocator_traits support in concurrent_unordered_map") {
283     test_allocator_traits_support<CumapTraits>();
284 }
285 
286 //! Testing heterogeneous overloads in concurrent_unordered_map
287 //! \brief \ref interface \ref requirement
288 TEST_CASE("heterogeneous overloads in concurrent_unordered_map") {
289     check_heterogeneous_functions_key_int<oneapi::tbb::concurrent_unordered_map, int, int>();
290     check_heterogeneous_functions_key_string<oneapi::tbb::concurrent_unordered_map, std::string, std::string>();
291 }
292 
293 //! Testing insert overloads with generic pair in concurrent_unordered_map
294 //! \brief \ref interface \ref requirement
295 TEST_CASE("insertion by generic pair in concurrent_unordered_map") {
296     test_insert_by_generic_pair<oneapi::tbb::concurrent_unordered_map>();
297 }
298 
299 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
300 //! Testing Class Template Argument Deduction in concurrent_unordered_map
301 //! \brief \ref interface \ref requirement
302 TEST_CASE("CTAD support in concurrent_unordered_map") {
303     test_deduction_guides<oneapi::tbb::concurrent_unordered_map>();
304 }
305 #endif
306 
307 //! Testing comparisons in concurrent_unordered_map
308 //! \brief \ref interface \ref requirement
309 TEST_CASE("concurrent_unordered_map comparisons") {
310     test_map_comparisons<oneapi::tbb::concurrent_unordered_map>();
311 }
312 
313 //! Testing concurrent_unordered_multimap member types
314 //! \brief \ref interface \ref requirement
315 TEST_CASE("concurrent_unordered_multimap member types") {
316     test_member_types<oneapi::tbb::concurrent_unordered_multimap>();
317 }
318 
319 //! Testing requirements of concurrent_unordered_multimap
320 //! \brief \ref interface \ref requirement
321 TEST_CASE("concurrent_unordered_multimap requirements") {
322     test_basic<multimap_type>();
323 }
324 
325 //! Testing multithreading support in concurrent_unordered_multimap
326 //! \brief \ref requirement
327 TEST_CASE("concurrent_unordered_multimap multithreading support") {
328     test_concurrent<multimap_type>();
329 }
330 
331 //! Testing move constructors and assignment operator in concurrent_unordered_multimap
332 //! \brief \ref interface \ref requirement
333 TEST_CASE("concurrent_unordered_multimap move semantics support") {
334     test_rvalue_ref_support<CumultimapTraits>();
335 }
336 
337 //! Testing std::initializer_list constructors and modifiers in concurrent_unordered_multimap
338 //! \brief \ref interface \ref requirement
339 TEST_CASE("std::initializer_list support in concurrent_unordered_multimap") {
340     test_initializer_list_support<multimap_type>({{1, 1}, {2, 2}, {3, 3}, {4, 4}, {4, 40}});
341 }
342 
343 //! Testing node handling support in concurrent_unordered_multimap
344 //! \brief \ref interface \ref requirement
345 TEST_CASE("node handling support in concurrent_unordered_multimap") {
346     node_handling_tests::test_node_handling_support<multimap_type>();
347 }
348 
349 //! Testing std::allocator_traits support in concurrent_unordered_multimap
350 //! \brief \ref interface \ref requirement
351 TEST_CASE("std::allocator_traits support in concurrent_unordered_multimap") {
352     test_allocator_traits_support<CumultimapTraits>();
353 }
354 
355 //! Testing heterogeneous overloads in concurrent_unordered_multimap
356 //! \brief \ref interface \ref requirement
357 TEST_CASE("heterogeneous overloads in concurrent_unordered_multimap") {
358     check_heterogeneous_functions_key_int<oneapi::tbb::concurrent_unordered_multimap, int, int>();
359     check_heterogeneous_functions_key_string<oneapi::tbb::concurrent_unordered_multimap, std::string, std::string>();
360 }
361 
362 //! Testing insert overloads with generic pair in concurrent_unordered_multimap
363 //! \brief \ref interface \ref requirement
364 TEST_CASE("insertion by generic pair in concurrent_unordered_multimap") {
365     test_insert_by_generic_pair<oneapi::tbb::concurrent_unordered_multimap>();
366 }
367 
368 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
369 //! Testing Class Template Argument Deduction in concurrent_unordered_multimap
370 //! \brief \ref interface \ref requirement
371 TEST_CASE("CTAD support in concurrent_unordered_multimap") {
372     test_deduction_guides<oneapi::tbb::concurrent_unordered_multimap>();
373 }
374 #endif
375 
376 //! Testing comparisons in concurrent_unordered_multimap
377 //! \brief \ref interface \ref requirement
378 TEST_CASE("concurrent_unordered_multimap comparisons") {
379     test_map_comparisons<oneapi::tbb::concurrent_unordered_multimap>();
380 }
381 
382 //! Testing of merge operations in concurrent_unordered_map and concurrent_unordered_multimap
383 //! \brief \ref interface \ref requirement
384 TEST_CASE("merge operations") {
385     node_handling_tests::test_merge<map_type, multimap_type>(1000);
386 }
387