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