1/*
2 Copyright (c) 2005-2019 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_EXTRA_DEBUG 1
18#if _MSC_VER
19#define _SCL_SECURE_NO_WARNINGS
20#endif
21
22#include "tbb/concurrent_unordered_map.h"
23#if __TBB_INITIALIZER_LISTS_PRESENT
24// These operator== are used implicitly in test_initializer_list.h.
25// For some unknown reason clang is not able to find the if they a declared after the
26// inclusion of test_initializer_list.h.
27template<typename container_type>
28bool equal_containers( container_type const& lhs, container_type const& rhs );
29template<typename Key, typename Value>
30bool operator==( tbb::concurrent_unordered_map<Key, Value> const& lhs, tbb::concurrent_unordered_map<Key, Value> const& rhs ) {
31 return equal_containers( lhs, rhs );
32}
33template<typename Key, typename Value>
34bool operator==( tbb::concurrent_unordered_multimap<Key, Value> const& lhs, tbb::concurrent_unordered_multimap<Key, Value> const& rhs ) {
35 return equal_containers( lhs, rhs );
36}
37#endif /* __TBB_INITIALIZER_LISTS_PRESENT */
38#include "test_concurrent_unordered_common.h"
39
40typedef tbb::concurrent_unordered_map<int, int, tbb::tbb_hash<int>, std::equal_to<int>, MyAllocator> MyMap;
41typedef tbb::concurrent_unordered_map<int, int, degenerate_hash<int>, std::equal_to<int>, MyAllocator> MyDegenerateMap;
42typedef tbb::concurrent_unordered_map<int, check_type<int>, tbb::tbb_hash<int>, std::equal_to<int>, MyAllocator> MyCheckedMap;
43typedef tbb::concurrent_unordered_map<intptr_t, FooWithAssign, tbb::tbb_hash<intptr_t>, std::equal_to<intptr_t>, MyAllocator> MyCheckedStateMap;
44typedef tbb::concurrent_unordered_multimap<int, int, tbb::tbb_hash<int>, std::equal_to<int>, MyAllocator> MyMultiMap;
45typedef tbb::concurrent_unordered_multimap<int, int, degenerate_hash<int>, std::equal_to<int>, MyAllocator> MyDegenerateMultiMap;
46typedef tbb::concurrent_unordered_multimap<int, check_type<int>, tbb::tbb_hash<int>, std::equal_to<int>, MyAllocator> MyCheckedMultiMap;
47
48template <>
49struct SpecialTests <MyMap> {
50 static void Test( const char *str ) {
51 SpecialMapTests<MyMap>(str);
52 }
53};
54
55template <>
56struct SpecialTests <MyMultiMap> {
57 static void Test( const char *str ) {
58 SpecialMultiMapTests<MyMultiMap>(str);
59 }
60};
61
62#if __TBB_CPP11_RVALUE_REF_PRESENT
63struct cu_map_type : unordered_move_traits_base {
64 template<typename element_type, typename allocator_type>
65 struct apply {
66 typedef tbb::concurrent_unordered_map<element_type, element_type, tbb::tbb_hash<element_type>, std::equal_to<element_type>, allocator_type > type;
67 };
68
69 typedef FooPairIterator init_iterator_type;
70};
71
72struct cu_multimap_type : unordered_move_traits_base {
73 template<typename element_type, typename allocator_type>
74 struct apply {
75 typedef tbb::concurrent_unordered_multimap<element_type, element_type, tbb::tbb_hash<element_type>, std::equal_to<element_type>, allocator_type > type;
76 };
77
78 typedef FooPairIterator init_iterator_type;
79};
80#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
81
82template <bool defCtorPresent, typename Key, typename Element, typename Hasher, typename Equality, typename Allocator>
83void TestMapSpecificMethods( tbb::concurrent_unordered_map<Key, Element, Hasher, Equality, Allocator> &c,
84 const typename tbb::concurrent_unordered_map<Key, Element, Hasher, Equality, Allocator>::value_type &value ) {
85 TestMapSpecificMethodsImpl<defCtorPresent>(c, value);
86 }
87
88struct UnorderedMapTypesTester{
89 template <bool defCtorPresent, typename ValueType>
90 void check( const std::list<ValueType> &lst ) {
91 typedef typename ValueType::first_type KeyType;
92 typedef typename ValueType::second_type ElemType;
93 TypeTester< defCtorPresent, tbb::concurrent_unordered_map< KeyType, ElemType, tbb::tbb_hash<KeyType>, Harness::IsEqual>,
94 tbb::concurrent_unordered_map< KeyType, ElemType, tbb::tbb_hash<KeyType>, Harness::IsEqual, debug_allocator<ValueType> > >( lst );
95 TypeTester< defCtorPresent, tbb::concurrent_unordered_multimap< KeyType, ElemType, tbb::tbb_hash<KeyType>, Harness::IsEqual>,
96 tbb::concurrent_unordered_multimap< KeyType, ElemType, tbb::tbb_hash<KeyType>, Harness::IsEqual, debug_allocator<ValueType> > >( lst );
97 }
98};
99
100void TestTypes() {
101 TestMapCommonTypes<UnorderedMapTypesTester>();
102
103 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_SMART_POINTERS_PRESENT
104 // Regression test for a problem with excessive requirements of emplace()
105 test_emplace_insert<tbb::concurrent_unordered_map< int*, test::unique_ptr<int> >,
106 tbb::internal::false_type>( new int, new int );
107 test_emplace_insert<tbb::concurrent_unordered_multimap< int*, test::unique_ptr<int> >,
108 tbb::internal::false_type>( new int, new int );
109 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_SMART_POINTERS_PRESENT*/
110}
111
112#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
113template <template <typename...> typename TMap>
114void TestDeductionGuides() {
115 using ComplexType = std::pair<int, std::string>;
116 using ComplexTypeConst = std::pair<const int, std::string>;
117 std::vector<ComplexType> v;
118 auto l = { ComplexTypeConst(1, "one"), ComplexTypeConst(2, "two")};
119
120 // check TMap(InputIterator, InputIterator)
121 TMap m0(v.begin(), v.end());
122 static_assert(std::is_same<decltype(m0), TMap<int, std::string>>::value);
123
124 // check TMap(InputIterator, InputIterator, size_t)
125 TMap m1(v.begin(), v.end(), 1);
126 static_assert(std::is_same<decltype(m1), TMap<int, std::string>>::value);
127
128
129 // check TMap(InputIterator, InputIterator, size_t, Hasher)
130 TMap m2(v.begin(), v.end(), 4, std::hash<int>());
131 static_assert(std::is_same<decltype(m2), TMap<int, std::string, std::hash<int>>>::value);
132
133 // check TMap(InputIterator, InputIterator, size_t, Hasher, Equality)
134 TMap m3(v.begin(), v.end(), 4, std::hash<int>(), std::less<int>());
135 static_assert(std::is_same<decltype(m3), TMap<int, std::string, std::hash<int>, std::less<int>>>::value);
136
137 // check TMap(InputIterator, InputIterator, size_t, Hasher, Equality, Allocator)
138 TMap m4(v.begin(), v.end(), 4, std::hash<int>(), std::less<int>(), std::allocator<int>());
139 static_assert(std::is_same<decltype(m4), TMap<int, std::string, std::hash<int>,
140 std::less<int>, std::allocator<int>>>::value);
141
142 // check TMap(InputIterator, InputIterator, size_t, Allocator)
143 TMap m5(v.begin(), v.end(), 5, std::allocator<int>());
144 static_assert(std::is_same<decltype(m5), TMap<int, std::string, tbb::tbb_hash<int>,
145 std::equal_to<int>, std::allocator<int>>>::value);
146
147 // check TMap(InputIterator, InputIterator, size_t, Hasher, Allocator)
148 TMap m6(v.begin(), v.end(), 4, std::hash<int>(), std::allocator<int>());
149 static_assert(std::is_same<decltype(m6), TMap<int, std::string, std::hash<int>,
150 std::equal_to<int>, std::allocator<int>>>::value);
151
152 // check TMap(std::initializer_list)
153 TMap m7(l);
154 static_assert(std::is_same<decltype(m7), TMap<int, std::string>>::value);
155
156 // check TMap(std::initializer_list, size_t)
157 TMap m8(l, 1);
158 static_assert(std::is_same<decltype(m8), TMap<int, std::string>>::value);
159
160 // check TMap(std::initializer_list, size_t, Hasher)
161 TMap m9(l, 4, std::hash<int>());
162 static_assert(std::is_same<decltype(m9), TMap<int, std::string, std::hash<int>>>::value);
163
164 // check TMap(std::initializer_list, size_t, Hasher, Equality)
165 TMap m10(l, 4, std::hash<int>(), std::less<int>());
166 static_assert(std::is_same<decltype(m10), TMap<int, std::string, std::hash<int>, std::less<int>>>::value);
167
168 // check TMap(std::initializer_list, size_t, Hasher, Equality, Allocator)
169 TMap m11(l, 4, std::hash<int>(), std::less<int>(), std::allocator<int>());
170 static_assert(std::is_same<decltype(m11), TMap<int, std::string, std::hash<int>,
171 std::less<int>, std::allocator<int>>>::value);
172
173 // check TMap(std::initializer_list, size_t, Allocator)
174 TMap m12(l, 4, std::allocator<int>());
175 static_assert(std::is_same<decltype(m12), TMap<int, std::string, tbb::tbb_hash<int>,
176 std::equal_to<int>, std::allocator<int>>>::value);
177
178 // check TMap(std::initializer_list, size_t, Hasher, Allocator)
179 TMap m13(l, 4, std::hash<int>(), std::allocator<int>());
180 static_assert(std::is_same<decltype(m13), TMap<int, std::string, std::hash<int>,
181 std::equal_to<int>, std::allocator<int>>>::value);
182
183 // check TMap(TMap &)
184 TMap m14(m1);
185 static_assert(std::is_same<decltype(m14), decltype(m1)>::value);
186
187 // check TMap(TMap &, Allocator)
188 TMap m15(m5, std::allocator<int>());
189 static_assert(std::is_same<decltype(m15), decltype(m5)>::value);
190
191 // check TMap(TMap &&)
192 TMap m16(std::move(m1));
193 static_assert(std::is_same<decltype(m16), decltype(m1)>::value);
194
195 // check TMap(TMap &&, Allocator)
196 TMap m17(std::move(m5), std::allocator<int>());
197 static_assert(std::is_same<decltype(m17), decltype(m5)>::value);
198}
199#endif
200
201int TestMain() {
202 test_machine();
203
204 test_basic<MyMap>( "concurrent unordered Map" );
205 test_basic<MyDegenerateMap>( "concurrent unordered degenerate Map" );
206 test_concurrent<MyMap>( "concurrent unordered Map" );
207 test_concurrent<MyDegenerateMap>( "concurrent unordered degenerate Map" );
208 test_basic<MyMultiMap>( "concurrent unordered MultiMap" );
209 test_basic<MyDegenerateMultiMap>( "concurrent unordered degenerate MultiMap" );
210 test_concurrent<MyMultiMap>( "concurrent unordered MultiMap" );
211 test_concurrent<MyDegenerateMultiMap>( "concurrent unordered degenerate MultiMap" );
212 test_concurrent<MyMultiMap>( "concurrent unordered MultiMap asymptotic", true );
213
214 { Check<MyCheckedMap::value_type> checkit; test_basic<MyCheckedMap>( "concurrent unordered map (checked)" ); }
215 { Check<MyCheckedMap::value_type> checkit; test_concurrent<MyCheckedMap>( "concurrent unordered map (checked)" ); }
216 test_basic<MyCheckedStateMap>("concurrent unordered map (checked state of elements)", tbb::internal::true_type());
217 test_concurrent<MyCheckedStateMap>("concurrent unordered map (checked state of elements)");
218
219 { Check<MyCheckedMultiMap::value_type> checkit; test_basic<MyCheckedMultiMap>( "concurrent unordered MultiMap (checked)" ); }
220 { Check<MyCheckedMultiMap::value_type> checkit; test_concurrent<MyCheckedMultiMap>( "concurrent unordered MultiMap (checked)" ); }
221
222#if __TBB_INITIALIZER_LISTS_PRESENT
223 TestInitList< tbb::concurrent_unordered_map<int, int>,
224 tbb::concurrent_unordered_multimap<int, int> >( {{1,1},{2,2},{3,3},{4,4},{5,5}} );
225#endif /* __TBB_INITIALIZER_LISTS_PRESENT */
226
227#if __TBB_RANGE_BASED_FOR_PRESENT
228 TestRangeBasedFor<MyMap>();
229 TestRangeBasedFor<MyMultiMap>();
230#endif
231
232#if __TBB_CPP11_RVALUE_REF_PRESENT
233 test_rvalue_ref_support<cu_map_type>( "concurrent unordered map" );
234 test_rvalue_ref_support<cu_multimap_type>( "concurrent unordered multimap" );
235#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
236
237#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
238 TestDeductionGuides<tbb::concurrent_unordered_map>();
239 TestDeductionGuides<tbb::concurrent_unordered_multimap>();
240#endif
241
242 TestTypes();
243
244#if __TBB_UNORDERED_NODE_HANDLE_PRESENT
245 node_handling::TestNodeHandling<MyMap>();
246 node_handling::TestNodeHandling<MyMultiMap>();
247 node_handling::TestMerge<MyMap, MyMultiMap>(10000);
248 node_handling::TestMerge<MyMap, MyDegenerateMap>(10000);
249#endif /*__TBB_UNORDERED_NODE_HANDLE_PRESENT*/
250
251 return Harness::Done;
252}
253