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