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_UNORDERED_TEST 1
18
19#include "test_concurrent_associative_common.h"
20
21template<typename MyTable>
22inline void CheckEmptyContainerAllocator(MyTable &table, size_t expected_allocs, size_t expected_frees, bool exact, int line) {
23 typename MyTable::allocator_type a = table.get_allocator();
24 REMARK("#%d checking allocators: items %u/%u, allocs %u/%u\n", line,
25 unsigned(a.items_allocated), unsigned(a.items_freed), unsigned(a.allocations), unsigned(a.frees) );
26 ASSERT( a.items_allocated == a.allocations, NULL); ASSERT( a.items_freed == a.frees, NULL);
27 ASSERT( a.items_allocated == a.items_freed + 1, NULL);
28 CheckAllocator<MyTable>(a, expected_allocs, expected_frees, exact);
29}
30
31template<typename T>
32struct degenerate_hash {
33 size_t operator()(const T& /*a*/) const {
34 return 1;
35 }
36};
37
38template <typename T>
39void test_unordered_methods(){
40 T cont;
41 cont.insert(Value<T>::make(1));
42 cont.insert(Value<T>::make(2));
43 // unordered_specific
44 // void rehash(size_type n);
45 cont.rehash(16);
46
47 // float load_factor() const;
48 // float max_load_factor() const;
49 ASSERT(cont.load_factor() <= cont.max_load_factor(), "Load factor is invalid");
50
51 // void max_load_factor(float z);
52 cont.max_load_factor(16.0f);
53 ASSERT(cont.max_load_factor() == 16.0f, "Max load factor has not been changed properly");
54
55 // hasher hash_function() const;
56 cont.hash_function();
57
58 // key_equal key_eq() const;
59 cont.key_eq();
60
61 cont.clear();
62 CheckEmptyContainerAllocatorA(cont, 1, 0); // one dummy is always allocated
63 for (int i = 0; i < 256; i++)
64 {
65 std::pair<typename T::iterator, bool> ins3 = cont.insert(Value<T>::make(i));
66 ASSERT(ins3.second == true && Value<T>::get(*(ins3.first)) == i, "Element 1 has not been inserted properly");
67 }
68 ASSERT(cont.size() == 256, "Wrong number of elements have been inserted");
69 // size_type unsafe_bucket_count() const;
70 ASSERT(cont.unsafe_bucket_count() == 16, "Wrong number of buckets");
71
72 // size_type unsafe_max_bucket_count() const;
73 ASSERT(cont.unsafe_max_bucket_count() > 65536, "Wrong max number of buckets");
74
75 for (unsigned int i = 0; i < 256; i++)
76 {
77 typename T::size_type buck = cont.unsafe_bucket(i);
78
79 // size_type unsafe_bucket(const key_type& k) const;
80 ASSERT(buck < 16, "Wrong bucket mapping");
81 }
82
83 typename T::size_type bucketSizeSum = 0;
84 typename T::size_type iteratorSizeSum = 0;
85
86 for (unsigned int i = 0; i < 16; i++)
87 {
88 bucketSizeSum += cont.unsafe_bucket_size(i);
89 for (typename T::iterator bit = cont.unsafe_begin(i); bit != cont.unsafe_end(i); bit++) iteratorSizeSum++;
90 }
91 ASSERT(bucketSizeSum == 256, "sum of bucket counts incorrect");
92 ASSERT(iteratorSizeSum == 256, "sum of iterator counts incorrect");
93}
94
95template<typename T, typename do_check_element_state>
96void test_basic(const char * str, do_check_element_state)
97{
98 test_basic_common<T>(str, do_check_element_state());
99 test_unordered_methods<T>();
100}
101
102template<typename T>
103void test_basic(const char * str){
104 test_basic_common<T>(str, tbb::internal::false_type());
105 test_unordered_methods<T>();
106}
107
108template<typename T>
109void test_concurrent(const char *tablename, bool asymptotic = false) {
110 test_concurrent_common<T>(tablename, asymptotic);
111}
112
113#if __TBB_CPP11_RVALUE_REF_PRESENT
114struct unordered_move_traits_base {
115 enum{ expected_number_of_items_to_allocate_for_steal_move = 3 };
116
117 template <typename unordered_type, typename iterator_type>
118 static unordered_type& construct_container(tbb::aligned_space<unordered_type> & storage, iterator_type begin, iterator_type end){
119 new (storage.begin()) unordered_type(begin, end);
120 return * storage.begin();
121 }
122
123 template <typename unordered_type, typename iterator_type, typename allocator_type>
124 static unordered_type& construct_container(tbb::aligned_space<unordered_type> & storage, iterator_type begin, iterator_type end, allocator_type const& a ){
125 size_t deault_n_of_buckets = 8; //can not use concurrent_unordered_base::n_of_buckets as it is inaccessible
126 new (storage.begin()) unordered_type(begin, end, deault_n_of_buckets, typename unordered_type::hasher(), typename unordered_type::key_equal(), a);
127 return * storage.begin();
128 }
129
130 template<typename unordered_type, typename iterator>
131 static bool equal(unordered_type const& c, iterator begin, iterator end){
132 bool equal_sizes = ( static_cast<size_t>(std::distance(begin, end)) == c.size() );
133 if (!equal_sizes)
134 return false;
135
136 for (iterator it = begin; it != end; ++it ){
137 if (c.find( Value<unordered_type>::key(*it)) == c.end()){
138 return false;
139 }
140 }
141 return true;
142 }
143};
144#endif /* __TBB_CPP11_RVALUE_REF_PRESENT*/
145
146#if __TBB_CPP11_SMART_POINTERS_PRESENT
147namespace tbb {
148 template<> class tbb_hash< std::shared_ptr<int> > {
149 public:
150 size_t operator()( const std::shared_ptr<int>& key ) const { return tbb_hasher( *key ); }
151 };
152 template<> class tbb_hash< const std::shared_ptr<int> > {
153 public:
154 size_t operator()( const std::shared_ptr<int>& key ) const { return tbb_hasher( *key ); }
155 };
156 template<> class tbb_hash< std::weak_ptr<int> > {
157 public:
158 size_t operator()( const std::weak_ptr<int>& key ) const { return tbb_hasher( *key.lock( ) ); }
159 };
160 template<> class tbb_hash< const std::weak_ptr<int> > {
161 public:
162 size_t operator()( const std::weak_ptr<int>& key ) const { return tbb_hasher( *key.lock( ) ); }
163 };
164 template<> class tbb_hash< test::unique_ptr<int> > {
165 public:
166 size_t operator()( const test::unique_ptr<int>& key ) const { return tbb_hasher( *key ); }
167 };
168 template<> class tbb_hash< const test::unique_ptr<int> > {
169 public:
170 size_t operator()( const test::unique_ptr<int>& key ) const { return tbb_hasher( *key ); }
171 };
172}
173#endif /*__TBB_CPP11_SMART_POINTERS_PRESENT*/
174
175template <bool defCtorPresent, typename Table>
176void CustomExamine( Table c, const std::list<typename Table::value_type> lst) {
177 typedef typename Table::value_type ValueType;
178 typedef typename Table::size_type SizeType;
179 const Table constC = c;
180
181 const SizeType bucket_count = c.unsafe_bucket_count();
182 ASSERT( c.unsafe_max_bucket_count() >= bucket_count, NULL );
183 SizeType counter = SizeType( 0 );
184 for ( SizeType i = 0; i < bucket_count; ++i ) {
185 const SizeType size = c.unsafe_bucket_size( i );
186 typedef typename Table::difference_type diff_type;
187 ASSERT( std::distance( c.unsafe_begin( i ), c.unsafe_end( i ) ) == diff_type( size ), NULL );
188 ASSERT( std::distance( c.unsafe_cbegin( i ), c.unsafe_cend( i ) ) == diff_type( size ), NULL );
189 ASSERT( std::distance( constC.unsafe_begin( i ), constC.unsafe_end( i ) ) == diff_type( size ), NULL );
190 ASSERT( std::distance( constC.unsafe_cbegin( i ), constC.unsafe_cend( i ) ) == diff_type( size ), NULL );
191 counter += size;
192 }
193 ASSERT( counter == lst.size(), NULL );
194
195 for ( typename std::list<ValueType>::const_iterator it = lst.begin(); it != lst.end(); ) {
196 const SizeType index = c.unsafe_bucket( Value<Table>::key( *it ) );
197 typename std::list<ValueType>::const_iterator prev_it = it++;
198 ASSERT( std::search( c.unsafe_begin( index ), c.unsafe_end( index ), prev_it, it, Harness::IsEqual() ) != c.unsafe_end( index ), NULL );
199 }
200
201 c.rehash( 2 * bucket_count );
202 ASSERT( c.unsafe_bucket_count() > bucket_count, NULL );
203
204 ASSERT( c.load_factor() <= c.max_load_factor(), NULL );
205
206 c.max_load_factor( 1.0f );
207 c.hash_function();
208 c.key_eq();
209}
210
211template <bool defCtorPresent, typename Table>
212void Examine( Table c, const std::list<typename Table::value_type> &lst) {
213 CommonExamine<defCtorPresent>(c, lst);
214 CustomExamine<defCtorPresent>(c, lst);
215}
216
217template <bool defCtorPresent, typename Table, typename TableDebugAlloc>
218void TypeTester( const std::list<typename Table::value_type> &lst ) {
219 ASSERT( lst.size() >= 5, "Array should have at least 5 elements" );
220 ASSERT( lst.size() <= 100, "The test has O(n^2) complexity so a big number of elements can lead long execution time" );
221 // Construct an empty table.
222 Table c1;
223 c1.insert( lst.begin(), lst.end() );
224 Examine<defCtorPresent>( c1, lst );
225
226 typename Table::size_type initial_bucket_number = 8;
227 typename Table::allocator_type allocator;
228 typename Table::hasher hasher;
229#if __TBB_INITIALIZER_LISTS_PRESENT && !__TBB_CPP11_INIT_LIST_TEMP_OBJS_LIFETIME_BROKEN
230 // Constructor from an initializer_list.
231 typename std::list<typename Table::value_type>::const_iterator it = lst.begin();
232 Table c2( { *it++, *it++, *it++ } );
233 c2.insert( it, lst.end( ) );
234 Examine<defCtorPresent>( c2, lst );
235
236 it = lst.begin();
237 // Constructor from an initializer_list, default hasher and key equality and non-default allocator
238 Table c2_alloc( { *it++, *it++, *it++ }, initial_bucket_number, allocator);
239 c2_alloc.insert( it, lst.end() );
240 Examine<defCtorPresent>( c2_alloc, lst );
241
242 it = lst.begin();
243 // Constructor from an initializer_list, default key equality and non-default hasher and allocator
244 Table c2_hash_alloc( { *it++, *it++, *it++ }, initial_bucket_number, hasher, allocator );
245 c2_hash_alloc.insert( it, lst.end() );
246 Examine<defCtorPresent>( c2_hash_alloc, lst );
247#endif
248 // Copying constructor.
249 Table c3( c1 );
250 Examine<defCtorPresent>( c3, lst );
251 // Construct with non-default allocator
252 TableDebugAlloc c4;
253 c4.insert( lst.begin(), lst.end() );
254 Examine<defCtorPresent>( c4, lst );
255 // Copying constructor for a container with a different allocator type.
256 TableDebugAlloc c5( c4 );
257 Examine<defCtorPresent>( c5, lst );
258 // Construction empty table with n preallocated buckets.
259 Table c6( lst.size() );
260 c6.insert( lst.begin(), lst.end() );
261 Examine<defCtorPresent>( c6, lst );
262
263 // Construction empty table with n preallocated buckets, default hasher and key equality and non-default allocator
264 Table c6_alloc( lst.size(), allocator );
265 c6_alloc.insert( lst.begin(), lst.end() );
266 Examine<defCtorPresent>( c6_alloc, lst );
267
268 // Construction empty table with n preallocated buckets, default key equality and non-default hasher and allocator
269 Table c6_hash_alloc( lst.size(), hasher, allocator );
270 c6_hash_alloc.insert( lst.begin(), lst.end() );
271 Examine<defCtorPresent>( c6_hash_alloc, lst );
272
273 TableDebugAlloc c7( lst.size( ) );
274 c7.insert( lst.begin(), lst.end() );
275 Examine<defCtorPresent>( c7, lst );
276 // Construction with a copying iteration range and a given allocator instance.
277 Table c8( c1.begin(), c1.end() );
278 Examine<defCtorPresent>( c8, lst );
279
280 // Construction with a copying iteration range, default hasher and key equality and non-default allocator
281 Table c8_alloc( c1.begin(), c1.end(), initial_bucket_number, allocator );
282 Examine<defCtorPresent>( c8_alloc, lst );
283
284 // Construction with a copying iteration range, default key equality and non-default hasher and allocator
285 Table c8_hash_alloc( c1.begin(), c1.end(), initial_bucket_number, hasher, allocator );
286 Examine<defCtorPresent>( c8_hash_alloc, lst);
287
288 // Construction with an instance of non-default allocator
289 typename TableDebugAlloc::allocator_type a;
290 TableDebugAlloc c9( a );
291 c9.insert( c7.begin(), c7.end() );
292 Examine<defCtorPresent>( c9, lst );
293}
294