1/*
2 Copyright (c) 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/* Some tests in this source file are based on PPL tests provided by Microsoft. */
18#include "tbb/parallel_for.h"
19#include "tbb/tick_count.h"
20#include "harness.h"
21#include "test_container_move_support.h"
22// Test that unordered containers do not require keys have default constructors.
23#define __HARNESS_CHECKTYPE_DEFAULT_CTOR 0
24#include "harness_checktype.h"
25#undef __HARNESS_CHECKTYPE_DEFAULT_CTOR
26#include "harness_allocator.h"
27
28#if _MSC_VER
29#pragma warning(disable: 4189) // warning 4189 -- local variable is initialized but not referenced
30#pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it
31#endif
32
33// TestInitListSupportWithoutAssign with an empty initializer list causes internal error in Intel Compiler.
34#define __TBB_ICC_EMPTY_INIT_LIST_TESTS_BROKEN (__INTEL_COMPILER && __INTEL_COMPILER <= 1500)
35
36typedef local_counting_allocator<debug_allocator<std::pair<const int,int>,std::allocator> > MyAllocator;
37
38template<typename Table>
39inline void CheckAllocator(typename Table::allocator_type& a, size_t expected_allocs, size_t expected_frees,
40 bool exact = true) {
41 if(exact) {
42 ASSERT( a.allocations == expected_allocs, NULL); ASSERT( a.frees == expected_frees, NULL);
43 } else {
44 ASSERT( a.allocations >= expected_allocs, NULL); ASSERT( a.frees >= expected_frees, NULL);
45 ASSERT( a.allocations - a.frees == expected_allocs - expected_frees, NULL );
46 }
47}
48
49// Check that only dummy node allocated if table is empty
50// Specialize this function for custom container, if it node allocation size > 1
51#define CheckEmptyContainerAllocatorE(t,a,f) CheckEmptyContainerAllocator(t,a,f,true,__LINE__)
52#define CheckEmptyContainerAllocatorA(t,a,f) CheckEmptyContainerAllocator(t,a,f,false,__LINE__)
53template<typename MyTable>
54inline void CheckEmptyContainerAllocator(MyTable &table, size_t expected_allocs, size_t expected_frees, bool exact = true, int line = 0);
55
56template<typename T>
57struct strip_const { typedef T type; };
58
59template<typename T>
60struct strip_const<const T> { typedef T type; };
61
62// value generator for map
63template <typename K, typename V = std::pair<const K, K> >
64struct ValueFactory {
65 typedef typename strip_const<K>::type Kstrip;
66 static V make(const K &value) { return V(value, value); }
67 static Kstrip key(const V &value) { return value.first; }
68 static Kstrip get(const V &value) { return (Kstrip)value.second; }
69 template< typename U >
70 static U convert(const V &value) { return U(value.second); }
71};
72
73// generator for set
74template <typename T>
75struct ValueFactory<T, T> {
76 static T make(const T &value) { return value; }
77 static T key(const T &value) { return value; }
78 static T get(const T &value) { return value; }
79 template< typename U >
80 static U convert(const T &value) { return U(value); }
81};
82
83template <typename T>
84struct Value : ValueFactory<typename T::key_type, typename T::value_type> {
85 template<typename U>
86 static bool compare( const typename T::iterator& it, U val ) {
87 return (Value::template convert<U>(*it) == val);
88 }
89};
90
91template<Harness::StateTrackableBase::StateValue desired_state, typename T>
92void check_value_state(/* typename do_check_element_state =*/ tbb::internal::true_type, T const& t, const char* filename, int line )
93{
94 ASSERT_CUSTOM(is_state_f<desired_state>()(t), "", filename, line);
95}
96
97template<Harness::StateTrackableBase::StateValue desired_state, typename T>
98void check_value_state(/* typename do_check_element_state =*/ tbb::internal::false_type, T const&, const char* , int ) {/*do nothing*/}
99
100#define ASSERT_VALUE_STATE(do_check_element_state,state,value) check_value_state<state>(do_check_element_state,value,__FILE__,__LINE__)
101
102#if __TBB_CPP11_RVALUE_REF_PRESENT
103template<typename T, typename do_check_element_state, typename V>
104void test_rvalue_insert(V v1, V v2)
105{
106 typedef T container_t;
107
108 container_t cont;
109
110 std::pair<typename container_t::iterator, bool> ins = cont.insert(Value<container_t>::make(v1));
111 ASSERT(ins.second == true && Value<container_t>::get(*(ins.first)) == v1, "Element 1 has not been inserted properly");
112 ASSERT_VALUE_STATE(do_check_element_state(),Harness::StateTrackableBase::MoveInitialized,*ins.first);
113
114 typename container_t::iterator it2 = cont.insert(ins.first, Value<container_t>::make(v2));
115 ASSERT(Value<container_t>::get(*(it2)) == v2, "Element 2 has not been inserted properly");
116 ASSERT_VALUE_STATE(do_check_element_state(),Harness::StateTrackableBase::MoveInitialized,*it2);
117
118}
119#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
120// The test does not use variadic templates, but emplace() does.
121
122namespace emplace_helpers {
123template<typename container_t, typename arg_t, typename value_t>
124std::pair<typename container_t::iterator, bool> call_emplace_impl(container_t& c, arg_t&& k, value_t *){
125 // this is a set
126 return c.emplace(std::forward<arg_t>(k));
127}
128
129template<typename container_t, typename arg_t, typename first_t, typename second_t>
130std::pair<typename container_t::iterator, bool> call_emplace_impl(container_t& c, arg_t&& k, std::pair<first_t, second_t> *){
131 // this is a map
132 return c.emplace(k, std::forward<arg_t>(k));
133}
134
135template<typename container_t, typename arg_t>
136std::pair<typename container_t::iterator, bool> call_emplace(container_t& c, arg_t&& k){
137 typename container_t::value_type * selector = NULL;
138 return call_emplace_impl(c, std::forward<arg_t>(k), selector);
139}
140
141template<typename container_t, typename arg_t, typename value_t>
142typename container_t::iterator call_emplace_hint_impl(container_t& c, typename container_t::const_iterator hint, arg_t&& k, value_t *){
143 // this is a set
144 return c.emplace_hint(hint, std::forward<arg_t>(k));
145}
146
147template<typename container_t, typename arg_t, typename first_t, typename second_t>
148typename container_t::iterator call_emplace_hint_impl(container_t& c, typename container_t::const_iterator hint, arg_t&& k, std::pair<first_t, second_t> *){
149 // this is a map
150 return c.emplace_hint(hint, k, std::forward<arg_t>(k));
151}
152
153template<typename container_t, typename arg_t>
154typename container_t::iterator call_emplace_hint(container_t& c, typename container_t::const_iterator hint, arg_t&& k){
155 typename container_t::value_type * selector = NULL;
156 return call_emplace_hint_impl(c, hint, std::forward<arg_t>(k), selector);
157}
158}
159template<typename T, typename do_check_element_state, typename V>
160void test_emplace_insert(V v1, V v2){
161 typedef T container_t;
162 container_t cont;
163
164 std::pair<typename container_t::iterator, bool> ins = emplace_helpers::call_emplace(cont, v1);
165 ASSERT(ins.second == true && Value<container_t>::compare(ins.first, v1), "Element 1 has not been inserted properly");
166 ASSERT_VALUE_STATE(do_check_element_state(),Harness::StateTrackableBase::DirectInitialized,*ins.first);
167
168 typename container_t::iterator it2 = emplace_helpers::call_emplace_hint(cont, ins.first, v2);
169 ASSERT(Value<container_t>::compare(it2, v2), "Element 2 has not been inserted properly");
170 ASSERT_VALUE_STATE(do_check_element_state(),Harness::StateTrackableBase::DirectInitialized,*it2);
171}
172#endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
173#endif // __TBB_CPP11_RVALUE_REF_PRESENT
174
175template<typename ContainerType, typename Iterator, typename RangeType>
176std::pair<intptr_t,intptr_t> CheckRecursiveRange(RangeType range) {
177 std::pair<intptr_t,intptr_t> sum(0, 0); // count, sum
178 for( Iterator i = range.begin(), e = range.end(); i != e; ++i ) {
179 ++sum.first; sum.second += Value<ContainerType>::get(*i);
180 }
181 if( range.is_divisible() ) {
182 RangeType range2( range, tbb::split() );
183 std::pair<intptr_t,intptr_t> sum1 = CheckRecursiveRange<ContainerType,Iterator, RangeType>( range );
184 std::pair<intptr_t,intptr_t> sum2 = CheckRecursiveRange<ContainerType,Iterator, RangeType>( range2 );
185 sum1.first += sum2.first; sum1.second += sum2.second;
186 ASSERT( sum == sum1, "Mismatched ranges after division");
187 }
188 return sum;
189}
190
191template <typename Map>
192void SpecialMapTests( const char *str ){
193 Map cont;
194 const Map &ccont( cont );
195
196 // mapped_type& operator[](const key_type& k);
197 cont[1] = 2;
198
199 // bool empty() const;
200 ASSERT( !ccont.empty( ), "Concurrent container empty after adding an element" );
201
202 // size_type size() const;
203 ASSERT( ccont.size( ) == 1, "Concurrent container size incorrect" );
204 ASSERT( cont[1] == 2, "Concurrent container value incorrect" );
205
206 // mapped_type& at( const key_type& k );
207 // const mapped_type& at(const key_type& k) const;
208 ASSERT( cont.at( 1 ) == 2, "Concurrent container value incorrect" );
209 ASSERT( ccont.at( 1 ) == 2, "Concurrent container value incorrect" );
210
211 // iterator find(const key_type& k);
212 typename Map::iterator it = cont.find( 1 );
213 ASSERT( it != cont.end( ) && Value<Map>::get( *(it) ) == 2, "Element with key 1 not properly found" );
214 cont.unsafe_erase( it );
215
216 it = cont.find( 1 );
217 ASSERT( it == cont.end( ), "Element with key 1 not properly erased" );
218 REMARK( "passed -- specialized %s tests\n", str );
219}
220
221template <typename MultiMap>
222void CheckMultiMap(MultiMap &m, int *targets, int tcount, int key) {
223 std::vector<bool> vfound(tcount,false);
224 std::pair<typename MultiMap::iterator, typename MultiMap::iterator> range = m.equal_range( key );
225 for(typename MultiMap::iterator it = range.first; it != range.second; ++it) {
226 bool found = false;
227 for( int i = 0; i < tcount; ++i) {
228 if((*it).second == targets[i]) {
229 if(!vfound[i]) { // we can insert duplicate values
230 vfound[i] = found = true;
231 break;
232 }
233 }
234 }
235 // just in case an extra value in equal_range...
236 ASSERT(found, "extra value from equal range");
237 }
238 for(int i = 0; i < tcount; ++i) ASSERT(vfound[i], "missing value");
239}
240
241template <typename MultiMap>
242void SpecialMultiMapTests( const char *str ){
243 int one_values[] = { 7, 2, 13, 23, 13 };
244 int zero_values[] = { 4, 9, 13, 29, 42, 111};
245 int n_zero_values = sizeof(zero_values) / sizeof(int);
246 int n_one_values = sizeof(one_values) / sizeof(int);
247 MultiMap cont;
248 const MultiMap &ccont( cont );
249 // mapped_type& operator[](const key_type& k);
250 cont.insert( std::make_pair( 1, one_values[0] ) );
251
252 // bool empty() const;
253 ASSERT( !ccont.empty( ), "Concurrent container empty after adding an element" );
254
255 // size_type size() const;
256 ASSERT( ccont.size( ) == 1, "Concurrent container size incorrect" );
257 ASSERT( (*(cont.begin( ))).second == one_values[0], "Concurrent container value incorrect" );
258 ASSERT( (*(cont.equal_range( 1 )).first).second == one_values[0], "Improper value from equal_range" );
259 ASSERT( (cont.equal_range( 1 )).second == cont.end( ), "Improper iterator from equal_range" );
260
261 cont.insert( std::make_pair( 1, one_values[1] ) );
262
263 // bool empty() const;
264 ASSERT( !ccont.empty( ), "Concurrent container empty after adding an element" );
265
266 // size_type size() const;
267 ASSERT( ccont.size( ) == 2, "Concurrent container size incorrect" );
268 CheckMultiMap(cont, one_values, 2, 1);
269
270 // insert the other {1,x} values
271 for( int i = 2; i < n_one_values; ++i ) {
272 cont.insert( std::make_pair( 1, one_values[i] ) );
273 }
274
275 CheckMultiMap(cont, one_values, n_one_values, 1);
276 ASSERT( (cont.equal_range( 1 )).second == cont.end( ), "Improper iterator from equal_range" );
277
278 cont.insert( std::make_pair( 0, zero_values[0] ) );
279
280 // bool empty() const;
281 ASSERT( !ccont.empty( ), "Concurrent container empty after adding an element" );
282
283 // size_type size() const;
284 ASSERT( ccont.size( ) == (size_t)(n_one_values+1), "Concurrent container size incorrect" );
285 CheckMultiMap(cont, one_values, n_one_values, 1);
286 CheckMultiMap(cont, zero_values, 1, 0);
287 ASSERT( (*(cont.begin( ))).second == zero_values[0], "Concurrent container value incorrect" );
288 // insert the rest of the zero values
289 for( int i = 1; i < n_zero_values; ++i) {
290 cont.insert( std::make_pair( 0, zero_values[i] ) );
291 }
292 CheckMultiMap(cont, one_values, n_one_values, 1);
293 CheckMultiMap(cont, zero_values, n_zero_values, 0);
294
295 // clear, reinsert interleaved
296 cont.clear();
297 int bigger_num = ( n_one_values > n_zero_values ) ? n_one_values : n_zero_values;
298 for( int i = 0; i < bigger_num; ++i ) {
299 if(i < n_one_values) cont.insert( std::make_pair( 1, one_values[i] ) );
300 if(i < n_zero_values) cont.insert( std::make_pair( 0, zero_values[i] ) );
301 }
302 CheckMultiMap(cont, one_values, n_one_values, 1);
303 CheckMultiMap(cont, zero_values, n_zero_values, 0);
304
305
306 REMARK( "passed -- specialized %s tests\n", str );
307}
308
309template <typename T>
310struct SpecialTests {
311 static void Test(const char *str) {REMARK("skipped -- specialized %s tests\n", str);}
312};
313
314
315
316#if __TBB_RANGE_BASED_FOR_PRESENT
317#include "test_range_based_for.h"
318
319template <typename Container>
320void TestRangeBasedFor() {
321 using namespace range_based_for_support_tests;
322
323 REMARK( "testing range based for loop compatibility \n" );
324 Container cont;
325 const int sequence_length = 100;
326 for ( int i = 1; i <= sequence_length; ++i ) {
327 cont.insert( Value<Container>::make(i) );
328 }
329
330 ASSERT( range_based_for_accumulate( cont, unified_summer(), 0 ) ==
331 gauss_summ_of_int_sequence( sequence_length ),
332 "incorrect accumulated value generated via range based for ?" );
333}
334#endif /* __TBB_RANGE_BASED_FOR_PRESENT */
335
336#if __TBB_INITIALIZER_LISTS_PRESENT
337// Required by test_initializer_list.h
338template<typename container_type>
339bool equal_containers(container_type const& lhs, container_type const& rhs) {
340 if ( lhs.size() != rhs.size() ) {
341 return false;
342 }
343 return std::equal( lhs.begin(), lhs.end(), rhs.begin(), Harness::IsEqual() );
344}
345
346#include "test_initializer_list.h"
347
348template <typename Table, typename MultiTable>
349void TestInitList( std::initializer_list<typename Table::value_type> il ) {
350 using namespace initializer_list_support_tests;
351 REMARK("testing initializer_list methods \n");
352
353 TestInitListSupportWithoutAssign<Table,test_special_insert>(il);
354 TestInitListSupportWithoutAssign<MultiTable, test_special_insert>( il );
355
356#if __TBB_ICC_EMPTY_INIT_LIST_TESTS_BROKEN
357 REPORT( "Known issue: TestInitListSupportWithoutAssign with an empty initializer list is skipped.\n");
358#else
359 TestInitListSupportWithoutAssign<Table, test_special_insert>( {} );
360 TestInitListSupportWithoutAssign<MultiTable, test_special_insert>( {} );
361#endif
362}
363#endif //if __TBB_INITIALIZER_LISTS_PRESENT
364
365template<typename T, typename do_check_element_state>
366void test_basic_common(const char * str, do_check_element_state)
367{
368 T cont;
369 const T &ccont(cont);
370 CheckEmptyContainerAllocatorE(cont, 1, 0); // one dummy is always allocated
371 // bool empty() const;
372 ASSERT(ccont.empty(), "Concurrent container is not empty after construction");
373
374 // size_type size() const;
375 ASSERT(ccont.size() == 0, "Concurrent container is not empty after construction");
376
377 // size_type max_size() const;
378 ASSERT(ccont.max_size() > 0, "Concurrent container max size is invalid");
379
380 //iterator begin();
381 //iterator end();
382 ASSERT(cont.begin() == cont.end(), "Concurrent container iterators are invalid after construction");
383 ASSERT(ccont.begin() == ccont.end(), "Concurrent container iterators are invalid after construction");
384 ASSERT(cont.cbegin() == cont.cend(), "Concurrent container iterators are invalid after construction");
385
386 //std::pair<iterator, bool> insert(const value_type& obj);
387 std::pair<typename T::iterator, bool> ins = cont.insert(Value<T>::make(1));
388 ASSERT(ins.second == true && Value<T>::get(*(ins.first)) == 1, "Element 1 has not been inserted properly");
389
390#if __TBB_CPP11_RVALUE_REF_PRESENT
391 test_rvalue_insert<T,do_check_element_state>(1,2);
392#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
393 test_emplace_insert<T,do_check_element_state>(1,2);
394#endif // __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
395#endif // __TBB_CPP11_RVALUE_REF_PRESENT
396
397 // bool empty() const;
398 ASSERT(!ccont.empty(), "Concurrent container is empty after adding an element");
399
400 // size_type size() const;
401 ASSERT(ccont.size() == 1, "Concurrent container size is incorrect");
402
403 std::pair<typename T::iterator, bool> ins2 = cont.insert(Value<T>::make(1));
404
405 if (T::allow_multimapping)
406 {
407 // std::pair<iterator, bool> insert(const value_type& obj);
408 ASSERT(ins2.second == true && Value<T>::get(*(ins2.first)) == 1, "Element 1 has not been inserted properly");
409
410 // size_type size() const;
411 ASSERT(ccont.size() == 2, "Concurrent container size is incorrect");
412
413 // size_type count(const key_type& k) const;
414 ASSERT(ccont.count(1) == 2, "Concurrent container count(1) is incorrect");
415 // std::pair<iterator, iterator> equal_range(const key_type& k);
416 std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
417 typename T::iterator it = range.first;
418 ASSERT(it != cont.end() && Value<T>::get(*it) == 1, "Element 1 has not been found properly");
419 unsigned int count = 0;
420 for (; it != range.second; it++)
421 {
422 count++;
423 ASSERT(Value<T>::get(*it) == 1, "Element 1 has not been found properly");
424 }
425
426 ASSERT(count == 2, "Range doesn't have the right number of elements");
427 }
428 else
429 {
430 // std::pair<iterator, bool> insert(const value_type& obj);
431 ASSERT(ins2.second == false && ins2.first == ins.first, "Element 1 should not be re-inserted");
432
433 // size_type size() const;
434 ASSERT(ccont.size() == 1, "Concurrent container size is incorrect");
435
436 // size_type count(const key_type& k) const;
437 ASSERT(ccont.count(1) == 1, "Concurrent container count(1) is incorrect");
438
439 // std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
440 // std::pair<iterator, iterator> equal_range(const key_type& k);
441 std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
442 typename T::iterator it = range.first;
443 ASSERT(it != cont.end() && Value<T>::get(*it) == 1, "Element 1 has not been found properly");
444 ASSERT(++it == range.second, "Range doesn't have the right number of elements");
445 }
446
447 // const_iterator find(const key_type& k) const;
448 // iterator find(const key_type& k);
449 typename T::iterator it = cont.find(1);
450 ASSERT(it != cont.end() && Value<T>::get(*(it)) == 1, "Element 1 has not been found properly");
451 ASSERT(ccont.find(1) == it, "Element 1 has not been found properly");
452
453 // Will be implemented in unordered containers later
454#if !__TBB_UNORDERED_TEST
455 //bool contains(const key_type&k) const
456 ASSERT(cont.contains(1), "contains() cannot detect existing element");
457 ASSERT(!cont.contains(0), "contains() detect not existing element");
458#endif /*__TBB_UNORDERED_TEST*/
459
460 // iterator insert(const_iterator hint, const value_type& obj);
461 typename T::iterator it2 = cont.insert(ins.first, Value<T>::make(2));
462 ASSERT(Value<T>::get(*it2) == 2, "Element 2 has not been inserted properly");
463
464 // T(const T& _Umap)
465 T newcont = ccont;
466 ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Copy construction has not copied the elements properly");
467
468 // this functionality not implemented yet
469 // size_type unsafe_erase(const key_type& k);
470 typename T::size_type size = cont.unsafe_erase(1);
471 ASSERT(T::allow_multimapping ? (size == 2) : (size == 1), "Erase has not removed the right number of elements");
472
473 // iterator unsafe_erase(const_iterator position);
474 typename T::iterator it4 = cont.unsafe_erase(cont.find(2));
475 ASSERT(it4 == cont.end() && cont.size() == 0, "Erase has not removed the last element properly");
476
477 // template<class InputIterator> void insert(InputIterator first, InputIterator last);
478 cont.insert(newcont.begin(), newcont.end());
479 ASSERT(T::allow_multimapping ? (cont.size() == 3) : (cont.size() == 2), "Range insert has not copied the elements properly");
480
481 // this functionality not implemented yet
482 // iterator unsafe_erase(const_iterator first, const_iterator last);
483 std::pair<typename T::iterator, typename T::iterator> range2 = newcont.equal_range(1);
484 newcont.unsafe_erase(range2.first, range2.second);
485 ASSERT(newcont.size() == 1, "Range erase has not erased the elements properly");
486
487 // void clear();
488 newcont.clear();
489 ASSERT(newcont.begin() == newcont.end() && newcont.size() == 0, "Clear has not cleared the container");
490
491#if __TBB_INITIALIZER_LISTS_PRESENT
492#if __TBB_CPP11_INIT_LIST_TEMP_OBJS_LIFETIME_BROKEN
493 REPORT("Known issue: the test for insert with initializer_list is skipped.\n");
494#else
495 // void insert(const std::initializer_list<value_type> &il);
496 newcont.insert( { Value<T>::make( 1 ), Value<T>::make( 2 ), Value<T>::make( 1 ) } );
497 if (T::allow_multimapping) {
498 ASSERT(newcont.size() == 3, "Concurrent container size is incorrect");
499 ASSERT(newcont.count(1) == 2, "Concurrent container count(1) is incorrect");
500 ASSERT(newcont.count(2) == 1, "Concurrent container count(2) is incorrect");
501 std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
502 it = range.first;
503 ASSERT(it != newcont.end() && Value<T>::get(*it) == 1, "Element 1 has not been found properly");
504 unsigned int count = 0;
505 for (; it != range.second; it++) {
506 count++;
507 ASSERT(Value<T>::get(*it) == 1, "Element 1 has not been found properly");
508 }
509 ASSERT(count == 2, "Range doesn't have the right number of elements");
510 range = newcont.equal_range(2); it = range.first;
511 ASSERT(it != newcont.end() && Value<T>::get(*it) == 2, "Element 2 has not been found properly");
512 count = 0;
513 for (; it != range.second; it++) {
514 count++;
515 ASSERT(Value<T>::get(*it) == 2, "Element 2 has not been found properly");
516 }
517 ASSERT(count == 1, "Range doesn't have the right number of elements");
518 } else {
519 ASSERT(newcont.size() == 2, "Concurrent container size is incorrect");
520 ASSERT(newcont.count(1) == 1, "Concurrent container count(1) is incorrect");
521 ASSERT(newcont.count(2) == 1, "Concurrent container count(2) is incorrect");
522 std::pair<typename T::iterator, typename T::iterator> range = newcont.equal_range(1);
523 it = range.first;
524 ASSERT(it != newcont.end() && Value<T>::get(*it) == 1, "Element 1 has not been found properly");
525 ASSERT(++it == range.second, "Range doesn't have the right number of elements");
526 range = newcont.equal_range(2); it = range.first;
527 ASSERT(it != newcont.end() && Value<T>::get(*it) == 2, "Element 2 has not been found properly");
528 ASSERT(++it == range.second, "Range doesn't have the right number of elements");
529 }
530#endif /* __TBB_CPP11_INIT_LIST_TEMP_OBJS_COMPILATION_BROKEN */
531#endif /* __TBB_INITIALIZER_LISTS_PRESENT */
532
533 // T& operator=(const T& _Umap)
534 newcont = ccont;
535 ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Assignment operator has not copied the elements properly");
536
537 REMARK("passed -- basic %s tests\n", str);
538
539#if defined (VERBOSE)
540 REMARK("container dump debug:\n");
541 cont._Dump();
542 REMARK("container dump release:\n");
543 cont.dump();
544 REMARK("\n");
545#endif
546
547 cont.clear();
548 CheckEmptyContainerAllocatorA(cont, 1, 0); // one dummy is always allocated
549 for (int i = 0; i < 256; i++)
550 {
551 std::pair<typename T::iterator, bool> ins3 = cont.insert(Value<T>::make(i));
552 ASSERT(ins3.second == true && Value<T>::get(*(ins3.first)) == i, "Element 1 has not been inserted properly");
553 }
554 ASSERT(cont.size() == 256, "Wrong number of elements have been inserted");
555 ASSERT((256 == CheckRecursiveRange<T,typename T::iterator>(cont.range()).first), NULL);
556 ASSERT((256 == CheckRecursiveRange<T,typename T::const_iterator>(ccont.range()).first), NULL);
557
558 // void swap(T&);
559 cont.swap(newcont);
560 ASSERT(newcont.size() == 256, "Wrong number of elements after swap");
561 ASSERT(newcont.count(200) == 1, "Element with key 200 is not present after swap");
562 ASSERT(newcont.count(16) == 1, "Element with key 16 is not present after swap");
563 ASSERT(newcont.count(99) == 1, "Element with key 99 is not present after swap");
564 ASSERT(T::allow_multimapping ? (cont.size() == 3) : (cont.size() == 2), "Assignment operator has not copied the elements properly");
565
566 // Need to be enabled
567 SpecialTests<T>::Test(str);
568}
569
570template<typename T>
571void test_basic_common(const char * str){
572 test_basic_common<T>(str, tbb::internal::false_type());
573}
574
575void test_machine() {
576 ASSERT(__TBB_ReverseByte(0)==0, NULL );
577 ASSERT(__TBB_ReverseByte(1)==0x80, NULL );
578 ASSERT(__TBB_ReverseByte(0xFE)==0x7F, NULL );
579 ASSERT(__TBB_ReverseByte(0xFF)==0xFF, NULL );
580}
581
582template<typename T>
583class FillTable: NoAssign {
584 T &table;
585 const int items;
586 bool my_asymptotic;
587 typedef std::pair<typename T::iterator, bool> pairIB;
588public:
589 FillTable(T &t, int i, bool asymptotic) : table(t), items(i), my_asymptotic(asymptotic) {
590 ASSERT( !(items&1) && items > 100, NULL);
591 }
592 void operator()(int threadn) const {
593 if( threadn == 0 ) { // Fill even keys forward (single thread)
594 bool last_inserted = true;
595 for( int i = 0; i < items; i+=2 ) {
596 pairIB pib = table.insert(Value<T>::make(my_asymptotic?1:i));
597 ASSERT(Value<T>::get(*(pib.first)) == (my_asymptotic?1:i), "Element not properly inserted");
598 ASSERT( last_inserted || !pib.second, "Previous key was not inserted but this is inserted" );
599 last_inserted = pib.second;
600 }
601 } else if( threadn == 1 ) { // Fill even keys backward (single thread)
602 bool last_inserted = true;
603 for( int i = items-2; i >= 0; i-=2 ) {
604 pairIB pib = table.insert(Value<T>::make(my_asymptotic?1:i));
605 ASSERT(Value<T>::get(*(pib.first)) == (my_asymptotic?1:i), "Element not properly inserted");
606 ASSERT( last_inserted || !pib.second, "Previous key was not inserted but this is inserted" );
607 last_inserted = pib.second;
608 }
609 } else if( !(threadn&1) ) { // Fill odd keys forward (multiple threads)
610 for( int i = 1; i < items; i+=2 )
611#if __TBB_INITIALIZER_LISTS_PRESENT && !__TBB_CPP11_INIT_LIST_TEMP_OBJS_LIFETIME_BROKEN
612 if ( i % 32 == 1 && i + 6 < items ) {
613 if (my_asymptotic) {
614 table.insert({ Value<T>::make(1), Value<T>::make(1), Value<T>::make(1) });
615 ASSERT(Value<T>::get(*table.find(1)) == 1, "Element not properly inserted");
616 }
617 else {
618 table.insert({ Value<T>::make(i), Value<T>::make(i + 2), Value<T>::make(i + 4) });
619 ASSERT(Value<T>::get(*table.find(i)) == i, "Element not properly inserted");
620 ASSERT(Value<T>::get(*table.find(i + 2)) == i + 2, "Element not properly inserted");
621 ASSERT(Value<T>::get(*table.find(i + 4)) == i + 4, "Element not properly inserted");
622 }
623 i += 4;
624 } else
625#endif
626 {
627 pairIB pib = table.insert(Value<T>::make(my_asymptotic ? 1 : i));
628 ASSERT(Value<T>::get(*(pib.first)) == (my_asymptotic ? 1 : i), "Element not properly inserted");
629 }
630 } else { // Check odd keys backward (multiple threads)
631 if (!my_asymptotic) {
632 bool last_found = false;
633 for( int i = items-1; i >= 0; i-=2 ) {
634 typename T::iterator it = table.find(i);
635 if( it != table.end() ) { // found
636 ASSERT(Value<T>::get(*it) == i, "Element not properly inserted");
637 last_found = true;
638 } else {
639 ASSERT( !last_found, "Previous key was found but this is not" );
640 }
641 }
642 }
643 }
644 }
645};
646
647typedef tbb::atomic<unsigned char> AtomicByte;
648
649template<typename ContainerType, typename RangeType>
650struct ParallelTraverseBody: NoAssign {
651 const int n;
652 AtomicByte* const array;
653 ParallelTraverseBody( AtomicByte an_array[], int a_n ) :
654 n(a_n), array(an_array)
655 {}
656 void operator()( const RangeType& range ) const {
657 for( typename RangeType::iterator i = range.begin(); i!=range.end(); ++i ) {
658 int k = static_cast<int>(Value<ContainerType>::key(*i));
659 ASSERT( k == Value<ContainerType>::get(*i), NULL );
660 ASSERT( 0<=k && k<n, NULL );
661 array[k]++;
662 }
663 }
664};
665
666// if multimapping, oddCount is the value that each odd-indexed array element should have.
667// not meaningful for non-multimapped case.
668void CheckRange( AtomicByte array[], int n, bool allowMultiMapping, int oddCount ) {
669 if(allowMultiMapping) {
670 for( int k = 0; k<n; ++k) {
671 if(k%2) {
672 if( array[k] != oddCount ) {
673 REPORT("array[%d]=%d (should be %d)\n", k, int(array[k]), oddCount);
674 ASSERT(false,NULL);
675 }
676 }
677 else {
678 if(array[k] != 2) {
679 REPORT("array[%d]=%d\n", k, int(array[k]));
680 ASSERT(false,NULL);
681 }
682 }
683 }
684 }
685 else {
686 for( int k=0; k<n; ++k ) {
687 if( array[k] != 1 ) {
688 REPORT("array[%d]=%d\n", k, int(array[k]));
689 ASSERT(false,NULL);
690 }
691 }
692 }
693}
694
695template<typename T>
696class CheckTable: NoAssign {
697 T &table;
698public:
699 CheckTable(T &t) : NoAssign(), table(t) {}
700 void operator()(int i) const {
701 int c = (int)table.count( i );
702 ASSERT( c, "must exist" );
703 }
704};
705
706template<typename T>
707void test_concurrent_common(const char *tablename, bool asymptotic = false) {
708#if TBB_USE_ASSERT
709 int items = 2000;
710#else
711 int items = 20000;
712#endif
713 int nItemsInserted = 0;
714 int nThreads = 0;
715#if __TBB_UNORDERED_TEST
716 T table(items/1000);
717#else
718 T table;
719#endif
720 #if __bgp__
721 nThreads = 6;
722 #else
723 nThreads = 16;
724 #endif
725 if(T::allow_multimapping) {
726 // even passes (threads 0 & 1) put N/2 items each
727 // odd passes (threads > 1) put N/2 if thread is odd, else checks if even.
728 items = 4*items / (nThreads + 2); // approximately same number of items inserted.
729 nItemsInserted = items + (nThreads-2) * items / 4;
730 }
731 else {
732 nItemsInserted = items;
733 }
734 REMARK("%s items == %d\n", tablename, items);
735 tbb::tick_count t0 = tbb::tick_count::now();
736 NativeParallelFor( nThreads, FillTable<T>(table, items, asymptotic) );
737 tbb::tick_count t1 = tbb::tick_count::now();
738 REMARK( "time for filling '%s' by %d items = %g\n", tablename, table.size(), (t1-t0).seconds() );
739 ASSERT( int(table.size()) == nItemsInserted, NULL);
740
741 if(!asymptotic) {
742 AtomicByte* array = new AtomicByte[items];
743 memset( static_cast<void*>(array), 0, items*sizeof(AtomicByte) );
744
745 typename T::range_type r = table.range();
746 std::pair<intptr_t,intptr_t> p = CheckRecursiveRange<T,typename T::iterator>(r);
747 ASSERT((nItemsInserted == p.first), NULL);
748 tbb::parallel_for( r, ParallelTraverseBody<T, typename T::const_range_type>( array, items ));
749 CheckRange( array, items, T::allow_multimapping, (nThreads - 1)/2 );
750
751 const T &const_table = table;
752 memset( static_cast<void*>(array), 0, items*sizeof(AtomicByte) );
753 typename T::const_range_type cr = const_table.range();
754 ASSERT((nItemsInserted == CheckRecursiveRange<T,typename T::const_iterator>(cr).first), NULL);
755 tbb::parallel_for( cr, ParallelTraverseBody<T, typename T::const_range_type>( array, items ));
756 CheckRange( array, items, T::allow_multimapping, (nThreads - 1) / 2 );
757 delete[] array;
758
759 tbb::parallel_for( 0, items, CheckTable<T>( table ) );
760 }
761
762 table.clear();
763 CheckEmptyContainerAllocatorA(table, items+1, items); // one dummy is always allocated
764
765}
766
767#if __TBB_CPP11_RVALUE_REF_PRESENT
768#include "test_container_move_support.h"
769
770template<typename container_traits>
771void test_rvalue_ref_support(const char* container_name){
772 TestMoveConstructor<container_traits>();
773 TestMoveAssignOperator<container_traits>();
774#if TBB_USE_EXCEPTIONS
775 TestExceptionSafetyGuaranteesMoveConstructorWithUnEqualAllocatorMemoryFailure<container_traits>();
776 TestExceptionSafetyGuaranteesMoveConstructorWithUnEqualAllocatorExceptionInElementCtor<container_traits>();
777#endif //TBB_USE_EXCEPTIONS
778 REMARK("passed -- %s move support tests\n", container_name);
779}
780#endif //__TBB_CPP11_RVALUE_REF_PRESENT
781
782namespace test_select_size_t_constant{
783 __TBB_STATIC_ASSERT((tbb::internal::select_size_t_constant<1234,1234>::value == 1234),"select_size_t_constant::value is not compile time constant");
784// There will be two constant used in the test 32 bit and 64 bit one.
785// The 64 bit constant should chosen so that it 32 bit halves adds up to the 32 bit one ( first constant used in the test).
786// % ~0U is used to sum up 32bit halves of the 64 constant. ("% ~0U" essentially adds the 32-bit "digits", like "%9" adds
787// the digits (modulo 9) of a number in base 10).
788// So iff select_size_t_constant is correct result of the calculation below will be same on both 32bit and 64bit platforms.
789 __TBB_STATIC_ASSERT((tbb::internal::select_size_t_constant<0x12345678U,0x091A2B3C091A2B3CULL>::value % ~0U == 0x12345678U),
790 "select_size_t_constant have chosen the wrong constant");
791}
792
793#if __TBB_CPP11_SMART_POINTERS_PRESENT
794// For the sake of simplified testing, make unique_ptr implicitly convertible to/from the pointer
795namespace test {
796 template<typename T>
797 class unique_ptr : public std::unique_ptr<T> {
798 public:
799 typedef typename std::unique_ptr<T>::pointer pointer;
800 unique_ptr( pointer p ) : std::unique_ptr<T>(p) {}
801 operator pointer() const { return this->get(); }
802 };
803}
804#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
805
806#include <vector>
807#include <list>
808#include <algorithm>
809
810template <typename ValueType>
811class TestRange : NoAssign {
812 const std::list<ValueType> &my_lst;
813 std::vector< tbb::atomic<bool> > &my_marks;
814public:
815 TestRange( const std::list<ValueType> &lst, std::vector< tbb::atomic<bool> > &marks ) : my_lst( lst ), my_marks( marks ) {
816 std::fill( my_marks.begin(), my_marks.end(), false );
817 }
818 template <typename Range>
819 void operator()( const Range &r ) const { doTestRange( r.begin(), r.end() ); }
820 template<typename Iterator>
821 void doTestRange( Iterator i, Iterator j ) const {
822 for ( Iterator it = i; it != j; ) {
823 Iterator prev_it = it++;
824 typename std::list<ValueType>::const_iterator it2 = std::search( my_lst.begin(), my_lst.end(), prev_it, it, Harness::IsEqual() );
825 ASSERT( it2 != my_lst.end(), NULL );
826 typename std::list<ValueType>::difference_type dist = std::distance( my_lst.begin( ), it2 );
827 ASSERT( !my_marks[dist], NULL );
828 my_marks[dist] = true;
829 }
830 }
831};
832
833// The helper to call a function only when a doCall == true.
834template <bool doCall> struct CallIf {
835 template<typename FuncType> void operator() ( FuncType func ) const { func(); }
836};
837template <> struct CallIf<false> {
838 template<typename FuncType> void operator()( FuncType ) const {}
839};
840
841template <typename Table>
842class TestOperatorSquareBrackets : NoAssign {
843 typedef typename Table::value_type ValueType;
844 Table &my_c;
845 const ValueType &my_value;
846public:
847 TestOperatorSquareBrackets( Table &c, const ValueType &value ) : my_c( c ), my_value( value ) {}
848 void operator()() const {
849 ASSERT( Harness::IsEqual()(my_c[my_value.first], my_value.second), NULL );
850 }
851};
852
853template <bool defCtorPresent, typename Table, typename Value>
854void TestMapSpecificMethodsImpl(Table &c, const Value &value){
855 CallIf<defCtorPresent>()(TestOperatorSquareBrackets<Table>( c, value ));
856 ASSERT( Harness::IsEqual()(c.at( value.first ), value.second), NULL );
857 const Table &constC = c;
858 ASSERT( Harness::IsEqual()(constC.at( value.first ), value.second), NULL );
859}
860
861// do nothing for common case
862template <bool defCtorPresent, typename Table, typename Value>
863void TestMapSpecificMethods( Table&, const Value& ) {}
864
865template <bool defCtorPresent, typename Table>
866class CheckValue : NoAssign {
867 Table &my_c;
868public:
869 CheckValue( Table &c ) : my_c( c ) {}
870 void operator()( const typename Table::value_type &value ) {
871 typedef typename Table::iterator Iterator;
872 typedef typename Table::const_iterator ConstIterator;
873 const Table &constC = my_c;
874 ASSERT( my_c.count( Value<Table>::key( value ) ) == 1, NULL );
875 // find
876 ASSERT( Harness::IsEqual()(*my_c.find( Value<Table>::key( value ) ), value), NULL );
877 ASSERT( Harness::IsEqual()(*constC.find( Value<Table>::key( value ) ), value), NULL );
878 // erase
879 ASSERT( my_c.unsafe_erase( Value<Table>::key( value ) ), NULL );
880 ASSERT( my_c.count( Value<Table>::key( value ) ) == 0, NULL );
881 // insert
882 std::pair<Iterator, bool> res = my_c.insert( value );
883 ASSERT( Harness::IsEqual()(*res.first, value), NULL );
884 ASSERT( res.second, NULL);
885 // erase
886 Iterator it = res.first;
887 it++;
888 ASSERT( my_c.unsafe_erase( res.first ) == it, NULL );
889 // insert
890 ASSERT( Harness::IsEqual()(*my_c.insert( my_c.begin(), value ), value), NULL );
891 // equal_range
892 std::pair<Iterator, Iterator> r1 = my_c.equal_range( Value<Table>::key( value ) );
893 ASSERT( Harness::IsEqual()(*r1.first, value) && ++r1.first == r1.second, NULL );
894 std::pair<ConstIterator, ConstIterator> r2 = constC.equal_range( Value<Table>::key( value ) );
895 ASSERT( Harness::IsEqual()(*r2.first, value) && ++r2.first == r2.second, NULL );
896
897 TestMapSpecificMethods<defCtorPresent>( my_c, value );
898 }
899};
900
901#include "tbb/task_scheduler_init.h"
902
903template <bool defCtorPresent, typename Table>
904void CommonExamine( Table c, const std::list<typename Table::value_type> lst) {
905 typedef typename Table::value_type ValueType;
906
907 ASSERT( !c.empty() && c.size() == lst.size() && c.max_size() >= c.size(), NULL );
908
909 std::for_each( lst.begin(), lst.end(), CheckValue<defCtorPresent, Table>( c ) );
910
911 std::vector< tbb::atomic<bool> > marks( lst.size() );
912
913 TestRange<ValueType>( lst, marks ).doTestRange( c.begin(), c.end() );
914 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
915
916 TestRange<ValueType>( lst, marks ).doTestRange( c.begin(), c.end() );
917 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
918
919 const Table constC = c;
920 ASSERT( c.size() == constC.size(), NULL );
921
922 TestRange<ValueType>( lst, marks ).doTestRange( constC.cbegin(), constC.cend() );
923 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
924
925 tbb::task_scheduler_init init;
926
927 tbb::parallel_for( c.range(), TestRange<ValueType>( lst, marks ) );
928 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
929
930 tbb::parallel_for( constC.range( ), TestRange<ValueType>( lst, marks ) );
931 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
932
933 Table c2;
934 typename std::list<ValueType>::const_iterator begin5 = lst.begin();
935 std::advance( begin5, 5 );
936 c2.insert( lst.begin(), begin5 );
937 std::for_each( lst.begin(), begin5, CheckValue<defCtorPresent, Table>( c2 ) );
938
939 c2.swap( c );
940 ASSERT( c2.size() == lst.size(), NULL );
941 ASSERT( c.size() == 5, NULL );
942 std::for_each( lst.begin(), lst.end(), CheckValue<defCtorPresent, Table>( c2 ) );
943
944 c2.clear();
945 ASSERT( c2.size() == 0, NULL );
946
947 typename Table::allocator_type a = c.get_allocator();
948 ValueType *ptr = a.allocate( 1 );
949 ASSERT( ptr, NULL );
950 a.deallocate( ptr, 1 );
951}
952
953// overload for set and multiset
954// second argument is needed just for right deduction
955template <typename Checker>
956void TestSetCommonTypes() {
957 Checker CheckTypes;
958 const int NUMBER = 10;
959
960 std::list<int> arrInt;
961 for ( int i = 0; i<NUMBER; ++i ) arrInt.push_back( i );
962 CheckTypes.template check</*defCtorPresent = */true>( arrInt );
963
964 std::list< tbb::atomic<int> > arrTbb(NUMBER);
965 int seq = 0;
966 for ( std::list< tbb::atomic<int> >::iterator it = arrTbb.begin(); it != arrTbb.end(); ++it, ++seq ) *it = seq;
967 CheckTypes.template check</*defCtorPresent = */true>( arrTbb );
968
969#if __TBB_CPP11_REFERENCE_WRAPPER_PRESENT && !__TBB_REFERENCE_WRAPPER_COMPILATION_BROKEN
970 std::list< std::reference_wrapper<int> > arrRef;
971 for ( std::list<int>::iterator it = arrInt.begin( ); it != arrInt.end( ); ++it )
972 arrRef.push_back( std::reference_wrapper<int>(*it) );
973 CheckTypes.template check</*defCtorPresent = */false>( arrRef );
974#endif /* __TBB_CPP11_REFERENCE_WRAPPER_PRESENT && !__TBB_REFERENCE_WRAPPER_COMPILATION_BROKEN */
975
976#if __TBB_CPP11_SMART_POINTERS_PRESENT
977 std::list< std::shared_ptr<int> > arrShr;
978 for ( int i = 0; i<NUMBER; ++i ) arrShr.push_back( std::make_shared<int>( i ) );
979 CheckTypes.template check</*defCtorPresent = */true>( arrShr );
980
981 std::list< std::weak_ptr<int> > arrWk;
982 std::copy( arrShr.begin( ), arrShr.end( ), std::back_inserter( arrWk ) );
983 CheckTypes.template check</*defCtorPresent = */true>( arrWk );
984#else
985 REPORT( "Known issue: C++11 smart pointer tests are skipped.\n" );
986#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
987}
988
989template <typename Checker>
990void TestMapCommonTypes() {
991 Checker CheckTypes;
992 const int NUMBER = 10;
993
994 std::list< std::pair<const int, int> > arrIntInt;
995 for ( int i = 0; i < NUMBER; ++i ) arrIntInt.push_back( std::make_pair( i, NUMBER - i ) );
996 CheckTypes.template check</*def_ctor_present = */true>( arrIntInt );
997
998 std::list< std::pair< const int, tbb::atomic<int> > > arrIntTbb;
999 for ( int i = 0; i < NUMBER; ++i ) {
1000 tbb::atomic<int> b;
1001 b = NUMBER - i;
1002 arrIntTbb.push_back( std::make_pair( i, b ) );
1003 }
1004 CheckTypes.template check</*defCtorPresent = */true>( arrIntTbb );
1005
1006#if __TBB_CPP11_REFERENCE_WRAPPER_PRESENT && !__TBB_REFERENCE_WRAPPER_COMPILATION_BROKEN
1007 std::list< std::pair<const std::reference_wrapper<const int>, int> > arrRefInt;
1008 for ( std::list< std::pair<const int, int> >::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it )
1009 arrRefInt.push_back( std::make_pair( std::reference_wrapper<const int>( it->first ), it->second ) );
1010 CheckTypes.template check</*defCtorPresent = */true>( arrRefInt );
1011
1012 std::list< std::pair<const int, std::reference_wrapper<int> > > arrIntRef;
1013 for ( std::list< std::pair<const int, int> >::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it ) {
1014 // Using std::make_pair below causes compilation issues with early implementations of std::reference_wrapper.
1015 arrIntRef.push_back( std::pair<const int, std::reference_wrapper<int> >( it->first, std::reference_wrapper<int>( it->second ) ) );
1016 }
1017 CheckTypes.template check</*defCtorPresent = */false>( arrIntRef );
1018#endif /* __TBB_CPP11_REFERENCE_WRAPPER_PRESENT && !__TBB_REFERENCE_WRAPPER_COMPILATION_BROKEN */
1019
1020#if __TBB_CPP11_SMART_POINTERS_PRESENT
1021 std::list< std::pair< const std::shared_ptr<int>, std::shared_ptr<int> > > arrShrShr;
1022 for ( int i = 0; i < NUMBER; ++i ) {
1023 const int NUMBER_minus_i = NUMBER - i;
1024 arrShrShr.push_back( std::make_pair( std::make_shared<int>( i ), std::make_shared<int>( NUMBER_minus_i ) ) );
1025 }
1026 CheckTypes.template check</*defCtorPresent = */true>( arrShrShr );
1027
1028 std::list< std::pair< const std::weak_ptr<int>, std::weak_ptr<int> > > arrWkWk;
1029 std::copy( arrShrShr.begin(), arrShrShr.end(), std::back_inserter( arrWkWk ) );
1030 CheckTypes.template check</*defCtorPresent = */true>( arrWkWk );
1031
1032#else
1033 REPORT( "Known issue: C++11 smart pointer tests are skipped.\n" );
1034#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
1035}
1036
1037
1038#if __TBB_UNORDERED_NODE_HANDLE_PRESENT || __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
1039namespace node_handling{
1040 template<typename Handle>
1041 bool compare_handle_getters(
1042 const Handle& node, const std::pair<typename Handle::key_type, typename Handle::mapped_type>& expected
1043 ) {
1044 return node.key() == expected.first && node.mapped() == expected.second;
1045 }
1046
1047 template<typename Handle>
1048 bool compare_handle_getters( const Handle& node, const typename Handle::value_type& value) {
1049 return node.value() == value;
1050 }
1051
1052 template<typename Handle>
1053 void set_node_handle_value(
1054 Handle& node, const std::pair<typename Handle::key_type, typename Handle::mapped_type>& value
1055 ) {
1056 node.key() = value.first;
1057 node.mapped() = value.second;
1058 }
1059
1060 template<typename Handle>
1061 void set_node_handle_value( Handle& node, const typename Handle::value_type& value) {
1062 node.value() = value;
1063 }
1064
1065 template <typename node_type>
1066 void TestTraits() {
1067 ASSERT( !std::is_copy_constructible<node_type>::value,
1068 "Node handle: Handle is copy constructable" );
1069 ASSERT( !std::is_copy_assignable<node_type>::value,
1070 "Node handle: Handle is copy assignable" );
1071 ASSERT( std::is_move_constructible<node_type>::value,
1072 "Node handle: Handle is not move constructable" );
1073 ASSERT( std::is_move_assignable<node_type>::value,
1074 "Node handle: Handle is not move constructable" );
1075 ASSERT( std::is_default_constructible<node_type>::value,
1076 "Node handle: Handle is not default constructable" );
1077 ASSERT( std::is_destructible<node_type>::value,
1078 "Node handle: Handle is not destructible" );
1079 }
1080
1081 template <typename Table>
1082 void TestHandle( Table test_table ) {
1083 ASSERT( test_table.size()>1, "Node handle: Container must contains 2 or more elements" );
1084 // Initialization
1085 using node_type = typename Table::node_type;
1086
1087 TestTraits<node_type>();
1088
1089 // Default Ctor and empty function
1090 node_type nh;
1091 ASSERT( nh.empty(), "Node handle: Node is not empty after initialization" );
1092
1093 // Move Assign
1094 // key/mapped/value function
1095 auto expected_value = *test_table.begin();
1096
1097 nh = test_table.unsafe_extract(test_table.begin());
1098 ASSERT( !nh.empty(), "Node handle: Node handle is empty after valid move assigning" );
1099 ASSERT( compare_handle_getters(nh,expected_value),
1100 "Node handle: After valid move assigning "
1101 "node handle does not contains expected value");
1102
1103 // Move Ctor
1104 // key/mapped/value function
1105 node_type nh2(std::move(nh));
1106 ASSERT( nh.empty(), "Node handle: After valid move construction node handle is empty" );
1107 ASSERT( !nh2.empty(), "Node handle: After valid move construction "
1108 "argument hode handle was not moved" );
1109 ASSERT( compare_handle_getters(nh2,expected_value),
1110 "Node handle: After valid move construction "
1111 "node handle does not contains expected value" );
1112
1113 // Bool conversion
1114 ASSERT( nh2, "Node handle: Wrong not handle bool conversion" );
1115
1116 // Change key/mapped/value of node handle
1117 auto expected_value2 = *test_table.begin();
1118 set_node_handle_value(nh2, expected_value2);
1119 ASSERT( compare_handle_getters(nh2, expected_value2),
1120 "Node handle: Wrong node handle key/mapped/value changing behavior" );
1121
1122 // Member/non member swap check
1123 node_type empty_node;
1124 // We extract this element for nh2 and nh3 difference
1125 test_table.unsafe_extract(test_table.begin());
1126 auto expected_value3 = *test_table.begin();
1127 node_type nh3(test_table.unsafe_extract(test_table.begin()));
1128
1129 // Both of node handles are not empty
1130 nh3.swap(nh2);
1131 ASSERT( compare_handle_getters(nh3, expected_value2),
1132 "Node handle: Wrong node handle swap behavior" );
1133 ASSERT( compare_handle_getters(nh2, expected_value3),
1134 "Node handle: Wrong node handle swap behavior" );
1135
1136 std::swap(nh2,nh3);
1137 ASSERT( compare_handle_getters(nh3, expected_value3),
1138 "Node handle: Wrong node handle swap behavior" );
1139 ASSERT( compare_handle_getters(nh2, expected_value2),
1140 "Node handle: Wrong node handle swap behavior" );
1141 ASSERT( !nh2.empty(), "Node handle: Wrong node handle swap behavior" );
1142 ASSERT( !nh3.empty(), "Node handle: Wrong node handle swap behavior" );
1143
1144 // One of nodes is empty
1145 nh3.swap(empty_node);
1146 ASSERT( compare_handle_getters(std::move(empty_node), expected_value3),
1147 "Node handle: Wrong node handle swap behavior" );
1148 ASSERT( nh3.empty(), "Node handle: Wrong node handle swap behavior" );
1149
1150 std::swap(empty_node, nh3);
1151 ASSERT( compare_handle_getters(std::move(nh3), expected_value3),
1152 "Node handle: Wrong node handle swap behavior" );
1153 ASSERT( empty_node.empty(), "Node handle: Wrong node handle swap behavior" );
1154
1155 empty_node.swap(nh3);
1156 ASSERT( compare_handle_getters(std::move(empty_node), expected_value3),
1157 "Node handle: Wrong node handle swap behavior" );
1158 ASSERT( nh3.empty(), "Node handle: Wrong node handle swap behavior" );
1159 }
1160
1161 template <typename Table>
1162 typename Table::node_type GenerateNodeHandle(const typename Table::value_type& value) {
1163 Table temp_table;
1164 temp_table.insert(value);
1165 return temp_table.unsafe_extract(temp_table.cbegin());
1166 }
1167
1168 template <typename Table>
1169 void IteratorAssertion( const Table& table,
1170 const typename Table::iterator& result,
1171 const typename Table::value_type* node_value = nullptr ) {
1172 if (node_value==nullptr) {
1173 ASSERT( result==table.end(), "Insert: Result iterator does not "
1174 "contains end pointer after empty node insertion" );
1175 } else {
1176 if (!Table::allow_multimapping) {
1177 ASSERT( result==table.find(Value<Table>::key( *node_value )) &&
1178 result != table.end(),
1179 "Insert: After node insertion result iterator"
1180 " doesn't contains address to equal element in table" );
1181 } else {
1182 ASSERT( *result==*node_value, "Insert: Result iterator contains"
1183 "wrong content after successful insertion" );
1184
1185 for (auto it = table.begin(); it != table.end(); ++it) {
1186 if (it == result) return;
1187 }
1188 ASSERT( false, "Insert: After successful insertion result "
1189 "iterator contains address that is not in the table" );
1190 }
1191 }
1192 }
1193 // overload for multitable or insertion with hint iterator
1194 template <typename Table>
1195 void InsertAssertion( const Table& table,
1196 const typename Table::iterator& result,
1197 bool,
1198 const typename Table::value_type* node_value = nullptr ) {
1199 IteratorAssertion(table, result, node_value);
1200 }
1201
1202 // Not multitable overload
1203 template <typename Table>
1204 void InsertAssertion( const Table& table,
1205 const std::pair<typename Table::iterator, bool>& result,
1206 bool second_value,
1207 const typename Table::value_type* node_value = nullptr ) {
1208 IteratorAssertion(table, result.first, node_value);
1209
1210 ASSERT( result.second == second_value || Table::allow_multimapping,
1211 "Insert: Returned bool wrong value after node insertion" );
1212 }
1213
1214#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1215 // Internal func for testing
1216 // Can't delete ref from "Table" argument because hint must point to element of table
1217 namespace {
1218 template <typename Table, typename... Hint>
1219 void TestInsertOverloads( Table& table_to_insert,
1220 const typename Table::value_type &value, const Hint&... hint ) {
1221 // Insert empty element
1222 typename Table::node_type nh;
1223
1224 auto table_size = table_to_insert.size();
1225 auto result = table_to_insert.insert(hint..., std::move(nh));
1226 InsertAssertion(table_to_insert, result, /*second_value*/ false);
1227 ASSERT( table_to_insert.size() == table_size,
1228 "Insert: After empty node insertion table size changed" );
1229
1230 // Standard insertion
1231 nh = GenerateNodeHandle<Table>(value);
1232
1233 result = table_to_insert.insert(hint..., std::move(nh));
1234 ASSERT( nh.empty(), "Insert: Not empty handle after successful insertion" );
1235 InsertAssertion(table_to_insert, result, /*second_value*/ true, &value);
1236
1237 // Insert existing node
1238 nh = GenerateNodeHandle<Table>(value);
1239
1240 result = table_to_insert.insert(hint..., std::move(nh));
1241
1242 InsertAssertion(table_to_insert, result, /*second_value*/ false, &value);
1243
1244 if (Table::allow_multimapping){
1245 ASSERT( nh.empty(), "Insert: Failed insertion to multitable" );
1246 } else {
1247 ASSERT( !nh.empty() , "Insert: Empty handle after failed insertion" );
1248 ASSERT( compare_handle_getters( std::move(nh), value ),
1249 "Insert: Existing data does not equal to the one being inserted" );
1250 }
1251 }
1252 }
1253
1254 template <typename Table>
1255 void TestInsert( Table table, const typename Table::value_type & value) {
1256 ASSERT( !table.empty(), "Insert: Map should contains 1 or more elements" );
1257 Table table_backup(table);
1258 TestInsertOverloads(table, value);
1259 TestInsertOverloads(table_backup, value, table_backup.begin());
1260 }
1261#endif /*__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT*/
1262
1263 template <typename Table>
1264 void TestExtract( Table table_for_extract, typename Table::key_type new_key ) {
1265 ASSERT( table_for_extract.size()>1, "Extract: Container must contains 2 or more element" );
1266 ASSERT( table_for_extract.find(new_key)==table_for_extract.end(),
1267 "Extract: Table must not contains new element!");
1268
1269 // Extract new element
1270 auto nh = table_for_extract.unsafe_extract(new_key);
1271 ASSERT( nh.empty(), "Extract: Node handle is not empty after wrong key extraction" );
1272
1273 // Valid key extraction
1274 auto expected_value = *table_for_extract.cbegin();
1275 auto key = Value<Table>::key( expected_value );
1276 auto count = table_for_extract.count(key);
1277
1278 nh = table_for_extract.unsafe_extract(key);
1279 ASSERT( !nh.empty(),
1280 "Extract: After successful extraction by key node handle is empty" );
1281 ASSERT( compare_handle_getters(std::move(nh), expected_value),
1282 "Extract: After successful extraction by key node handle contains wrong value" );
1283 ASSERT( table_for_extract.count(key) == count - 1,
1284 "Extract: After successful node extraction by key, table still contains this key" );
1285
1286 // Valid iterator overload
1287 auto expected_value2 = *table_for_extract.cbegin();
1288 auto key2 = Value<Table>::key( expected_value2 );
1289 auto count2 = table_for_extract.count(key2);
1290
1291 nh = table_for_extract.unsafe_extract(table_for_extract.cbegin());
1292 ASSERT( !nh.empty(),
1293 "Extract: After successful extraction by iterator node handle is empty" );
1294 ASSERT( compare_handle_getters(std::move(nh), expected_value2),
1295 "Extract: After successful extraction by iterator node handle contains wrong value" );
1296 ASSERT( table_for_extract.count(key2) == count2 - 1,
1297 "Extract: After successful extraction table also contains this element" );
1298 }
1299
1300 // All test exclude merge
1301 template <typename Table>
1302 void NodeHandlingTests ( const Table& table,
1303 const typename Table::value_type& new_value) {
1304 TestHandle(table);
1305#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1306 TestInsert(table, new_value);
1307#endif /*__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT*/
1308 TestExtract(table, Value<Table>::key( new_value ));
1309 }
1310
1311 template <typename TableType1, typename TableType2>
1312 void TestMerge( TableType1 table1, TableType2&& table2 ) {
1313 using Table2PureType = typename std::decay<TableType2>::type;
1314 // Initialization
1315 TableType1 table1_backup = table1;
1316 // For copying lvalue
1317 Table2PureType table2_backup = table2;
1318
1319 table1.merge(std::forward<TableType2>(table2));
1320 for (auto it: table2) {
1321 ASSERT( table1.find( Value<Table2PureType>::key( it ) ) != table1.end(),
1322 "Merge: Some key(s) was not merged" );
1323 }
1324
1325 // After the following step table1 will contains only merged elements from table2
1326 for (auto it: table1_backup) {
1327 table1.unsafe_extract(Value<TableType1>::key( it ));
1328 }
1329 // After the following step table2_backup will contains only merged elements from table2
1330 for (auto it: table2) {
1331 table2_backup.unsafe_extract(Value<Table2PureType>::key( it ));
1332 }
1333
1334 ASSERT ( table1.size() == table2_backup.size(), "Merge: Size of tables is not equal" );
1335 for (auto it: table2_backup) {
1336 ASSERT( table1.find( Value<Table2PureType>::key( it ) ) != table1.end(),
1337 "Merge: Wrong merge behavior" );
1338 }
1339 }
1340
1341 // Testing of rvalue and lvalue overloads
1342 template <typename TableType1, typename TableType2>
1343 void TestMergeOverloads( const TableType1& table1, TableType2 table2 ) {
1344 TableType2 table_backup(table2);
1345 TestMerge(table1, table2);
1346 TestMerge(table1, std::move(table_backup));
1347 }
1348
1349 template <typename Table, typename MultiTable>
1350 void TestMergeTransposition( Table table1, Table table2,
1351 MultiTable multitable1, MultiTable multitable2 ) {
1352 Table empty_map;
1353 MultiTable empty_multimap;
1354
1355 // Map transpositions
1356 node_handling::TestMergeOverloads(table1, table2);
1357 node_handling::TestMergeOverloads(table1, empty_map);
1358 node_handling::TestMergeOverloads(empty_map, table2);
1359
1360 // Multimap transpositions
1361 node_handling::TestMergeOverloads(multitable1, multitable2);
1362 node_handling::TestMergeOverloads(multitable1, empty_multimap);
1363 node_handling::TestMergeOverloads(empty_multimap, multitable2);
1364
1365 // Map/Multimap transposition
1366 node_handling::TestMergeOverloads(table1, multitable1);
1367 node_handling::TestMergeOverloads(multitable2, table2);
1368 }
1369
1370 template <typename Table>
1371 void AssertionConcurrentMerge ( Table start_data, Table src_table, std::vector<Table> tables,
1372 std::true_type) {
1373 ASSERT( src_table.size() == start_data.size()*tables.size(),
1374 "Merge: Incorrect merge for some elements" );
1375
1376 for(auto it: start_data) {
1377 ASSERT( src_table.count( Value<Table>::key( it ) ) ==
1378 start_data.count( Value<Table>::key( it ) )*tables.size(),
1379 "Merge: Incorrect merge for some element" );
1380 }
1381
1382 for (size_t i = 0; i < tables.size(); i++) {
1383 ASSERT( tables[i].empty(), "Merge: Some elements was not merged" );
1384 }
1385 }
1386
1387 template <typename Table>
1388 void AssertionConcurrentMerge ( Table start_data, Table src_table, std::vector<Table> tables,
1389 std::false_type) {
1390 Table expected_result;
1391 for (auto table: tables)
1392 for (auto it: start_data) {
1393 // If we cannot find some element in some table, then it has been moved
1394 if (table.find( Value<Table>::key( it ) ) == table.end()){
1395 bool result = expected_result.insert( it ).second;
1396 ASSERT( result, "Merge: Some element was merged twice or was not "
1397 "returned to his owner after unsuccessful merge");
1398 }
1399 }
1400
1401 ASSERT( expected_result.size() == src_table.size() && start_data.size() == src_table.size(),
1402 "Merge: wrong size of result table");
1403 for (auto it: expected_result) {
1404 if ( src_table.find( Value<Table>::key( it ) ) != src_table.end() &&
1405 start_data.find( Value<Table>::key( it ) ) != start_data.end() ){
1406 src_table.unsafe_extract(Value<Table>::key( it ));
1407 start_data.unsafe_extract(Value<Table>::key( it ));
1408 } else {
1409 ASSERT( false, "Merge: Incorrect merge for some element" );
1410 }
1411 }
1412
1413 ASSERT( src_table.empty()&&start_data.empty(), "Merge: Some elements were not merged" );
1414 }
1415
1416 template <typename Table>
1417 void TestConcurrentMerge (const Table& table_data) {
1418 for (auto num_threads = MinThread + 1; num_threads <= MaxThread; num_threads++){
1419 std::vector<Table> tables;
1420 Table src_table;
1421
1422 for (auto j = 0; j < num_threads; j++){
1423 tables.push_back(table_data);
1424 }
1425
1426 NativeParallelFor( num_threads, [&](size_t index){ src_table.merge(tables[index]); } );
1427
1428 AssertionConcurrentMerge( table_data, src_table, tables,
1429 std::integral_constant<bool,Table::allow_multimapping>{});
1430 }
1431 }
1432
1433
1434 template <typename Table>
1435 void TestNodeHandling(){
1436 Table table;
1437
1438 for (int i = 1; i < 5; i++)
1439 table.insert(Value<Table>::make(i));
1440
1441 if (Table::allow_multimapping)
1442 table.insert(Value<Table>::make(4));
1443
1444 node_handling::NodeHandlingTests(table, Value<Table>::make(5));
1445 }
1446
1447 template <typename TableType1, typename TableType2>
1448 void TestMerge(int size){
1449 TableType1 table1_1;
1450 TableType1 table1_2;
1451 int i = 1;
1452 for (; i < 5; ++i) {
1453 table1_1.insert(Value<TableType1>::make(i));
1454 table1_2.insert(Value<TableType1>::make(i*i));
1455 }
1456 if (TableType1::allow_multimapping) {
1457 table1_1.insert(Value<TableType1>::make(i));
1458 table1_2.insert(Value<TableType1>::make(i*i));
1459 }
1460
1461 TableType2 table2_1;
1462 TableType2 table2_2;
1463 for (i = 3; i < 7; ++i) {
1464 table1_1.insert(Value<TableType2>::make(i));
1465 table1_2.insert(Value<TableType2>::make(i*i));
1466 }
1467 if (TableType2::allow_multimapping) {
1468 table2_1.insert(Value<TableType2>::make(i));
1469 table2_2.insert(Value<TableType2>::make(i*i));
1470 }
1471
1472 node_handling::TestMergeTransposition(table1_1, table1_2,
1473 table2_1, table2_2);
1474
1475 TableType1 table1_3;
1476 for (i = 0; i<size; ++i){
1477 table1_3.insert(Value<TableType1>::make(i));
1478 }
1479 node_handling::TestConcurrentMerge(table1_3);
1480
1481 TableType2 table2_3;
1482 for (i = 0; i<size; ++i){
1483 table2_3.insert(Value<TableType2>::make(i));
1484 }
1485 node_handling::TestConcurrentMerge(table2_3);
1486}
1487}
1488#endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT || __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
1489