1 /* 2 Copyright (c) 2005-2020 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 #include "common/test.h" 18 #include "common/utils.h" 19 #include "common/utils_report.h" 20 #include "common/state_trackable.h" 21 #include "common/container_move_support.h" 22 #include "common/custom_allocators.h" 23 #include "common/initializer_list_support.h" 24 #include "common/containers_common.h" 25 #include "oneapi/tbb/concurrent_vector.h" 26 #include "oneapi/tbb/parallel_for.h" 27 #include "oneapi/tbb/tick_count.h" 28 #include "oneapi/tbb/global_control.h" 29 #include <initializer_list> 30 #include <numeric> 31 32 //! \file conformance_concurrent_vector.cpp 33 //! \brief Test for [containers.concurrent_vector] specification 34 35 const size_t N = 8192; 36 37 template<typename Vector, typename Iterator> 38 void CheckConstIterator( const Vector& u, int i, const Iterator& cp ) { 39 typename Vector::const_reference pref = *cp; 40 CHECK((pref.bar()==i)); 41 typename Vector::difference_type delta = cp-u.begin(); 42 REQUIRE( delta==i ); 43 CHECK((u[i].bar()==i)); 44 REQUIRE( u.begin()[i].bar()==i ); 45 } 46 47 template<typename Iterator1, typename Iterator2, typename V> 48 void CheckIteratorComparison( V& u ) { 49 V u2 = u; 50 Iterator1 i = u.begin(); 51 52 for( int i_count=0; i_count<100; ++i_count ) { 53 Iterator2 j = u.begin(); 54 Iterator2 i2 = u2.begin(); 55 for( int j_count=0; j_count<100; ++j_count ) { 56 REQUIRE( ((i==j)==(i_count==j_count)) ); 57 REQUIRE( ((i!=j)==(i_count!=j_count)) ); 58 REQUIRE( ((i-j)==(i_count-j_count)) ); 59 REQUIRE( ((i<j)==(i_count<j_count)) ); 60 REQUIRE( ((i>j)==(i_count>j_count)) ); 61 REQUIRE( ((i<=j)==(i_count<=j_count)) ); 62 REQUIRE( ((i>=j)==(i_count>=j_count)) ); 63 REQUIRE( (!(i==i2)) ); 64 REQUIRE( i!=i2 ); 65 ++j; 66 ++i2; 67 } 68 ++i; 69 } 70 } 71 72 template<typename Iterator1, typename Iterator2> 73 void TestIteratorAssignment( Iterator2 j ) { 74 Iterator1 i(j); 75 REQUIRE( i==j ); 76 REQUIRE( !(i!=j) ); 77 Iterator1 k; 78 k = j; 79 REQUIRE( k==j ); 80 REQUIRE( !(k!=j) ); 81 } 82 83 template<typename Range1, typename Range2> 84 void TestRangeAssignment( Range2 r2 ) { 85 Range1 r1(r2); r1 = r2; 86 } 87 88 template<typename T> 89 void TestSequentialFor() { 90 using V = oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign>; 91 V v(N); 92 REQUIRE(v.grow_by(0) == v.grow_by(0, move_support_tests::FooWithAssign())); 93 94 // Check iterator 95 typename V::iterator p = v.begin(); 96 REQUIRE( !(*p).is_const() ); 97 REQUIRE( !p->is_const() ); 98 for( int i=0; std::size_t(i)<v.size(); ++i, ++p ) { 99 CHECK( ((*p).state==move_support_tests::Foo::DefaultInitialized) ); 100 typename V::reference pref = *p; 101 pref.bar() = i; 102 typename V::difference_type delta = p-v.begin(); 103 REQUIRE( delta==i ); 104 REQUIRE_MESSAGE( (-delta<=0), "difference type not signed?" ); 105 } 106 107 // Check const_iterator going forwards 108 const V& u = v; 109 typename V::const_iterator cp = u.begin(); 110 REQUIRE( cp == v.cbegin() ); 111 REQUIRE( (*cp).is_const() ); 112 REQUIRE( (cp->is_const()) ); 113 REQUIRE( (*cp == v.front()) ); 114 for( int i=0; std::size_t(i)<u.size(); ++i ) { 115 CheckConstIterator(u,i,cp); 116 V::const_iterator &cpr = ++cp; 117 REQUIRE_MESSAGE( (&cpr == &cp), "pre-increment not returning a reference?"); 118 } 119 120 // Now go backwards 121 cp = u.end(); 122 REQUIRE( cp == v.cend() ); 123 for( int i=int(u.size()); i>0; ) { 124 --i; 125 V::const_iterator &cpr = --cp; 126 REQUIRE_MESSAGE( &cpr == &cp, "pre-decrement not returning a reference?"); 127 if( i>0 ) { 128 typename V::const_iterator cp_old = cp--; 129 intptr_t here = (*cp_old).bar(); 130 REQUIRE( here==u[i].bar() ); 131 typename V::const_iterator cp_new = cp++; 132 intptr_t prev = (*cp_new).bar(); 133 REQUIRE( prev==u[i-1].bar() ); 134 } 135 CheckConstIterator(u,i,cp); 136 } 137 138 // Now go forwards and backwards 139 std::ptrdiff_t k = 0; 140 cp = u.begin(); 141 for( std::size_t i=0; i<u.size(); ++i ) { 142 CheckConstIterator(u,int(k),cp); 143 typename V::difference_type delta = i*3 % u.size(); 144 if( 0<=k+delta && std::size_t(k+delta)<u.size() ) { 145 V::const_iterator &cpr = (cp += delta); 146 REQUIRE_MESSAGE( (&cpr == &cp), "+= not returning a reference?"); 147 k += delta; 148 } 149 delta = i*7 % u.size(); 150 if( 0<=k-delta && std::size_t(k-delta)<u.size() ) { 151 if( i&1 ) { 152 V::const_iterator &cpr = (cp -= delta); 153 REQUIRE_MESSAGE( (&cpr == &cp), "-= not returning a reference?"); 154 } else 155 cp = cp - delta; // Test operator- 156 k -= delta; 157 } 158 } 159 160 for( int i=0; std::size_t(i)<u.size(); i=(i<50?i+1:i*3) ) 161 for( int j=-i; std::size_t(i+j)<u.size(); j=(j<50?j+1:j*5) ) { 162 REQUIRE( ((u.begin()+i)[j].bar()==i+j) ); 163 REQUIRE( ((v.begin()+i)[j].bar()==i+j) ); 164 REQUIRE( ((v.cbegin()+i)[j].bar()==i+j) ); 165 REQUIRE( ((i+u.begin())[j].bar()==i+j) ); 166 REQUIRE( ((i+v.begin())[j].bar()==i+j) ); 167 REQUIRE(((i+v.cbegin())[j].bar()==i+j) ); 168 } 169 170 CheckIteratorComparison<typename V::iterator, typename V::iterator>(v); 171 CheckIteratorComparison<typename V::iterator, typename V::const_iterator>(v); 172 CheckIteratorComparison<typename V::const_iterator, typename V::iterator>(v); 173 CheckIteratorComparison<typename V::const_iterator, typename V::const_iterator>(v); 174 175 TestIteratorAssignment<typename V::const_iterator>( u.begin() ); 176 TestIteratorAssignment<typename V::const_iterator>( v.begin() ); 177 TestIteratorAssignment<typename V::const_iterator>( v.cbegin() ); 178 TestIteratorAssignment<typename V::iterator>( v.begin() ); 179 // doesn't compile as expected: TestIteratorAssignment<typename V::iterator>( u.begin() ); 180 181 TestRangeAssignment<typename V::const_range_type>( u.range() ); 182 TestRangeAssignment<typename V::const_range_type>( v.range() ); 183 TestRangeAssignment<typename V::range_type>( v.range() ); 184 // doesn't compile as expected: TestRangeAssignment<typename V::range_type>( u.range() ); 185 186 // Check reverse_iterator 187 typename V::reverse_iterator rp = v.rbegin(); 188 for( std::size_t i=v.size(); i>0; --i, ++rp ) { 189 typename V::reference pref = *rp; 190 REQUIRE( (std::size_t(pref.bar())==i-1) ); 191 REQUIRE( (rp!=v.rend()) ); 192 } 193 REQUIRE( rp==v.rend() ); 194 195 // Check const_reverse_iterator 196 typename V::const_reverse_iterator crp = u.rbegin(); 197 REQUIRE( crp == v.crbegin() ); 198 REQUIRE( *crp == v.back() ); 199 for(std::size_t i = v.size(); i>0; --i, ++crp) { 200 typename V::const_reference cpref = *crp; 201 REQUIRE( (std::size_t(cpref.bar())==i-1) ); 202 REQUIRE( crp!=u.rend() ); 203 } 204 REQUIRE( crp == u.rend() ); 205 REQUIRE( crp == v.crend() ); 206 207 TestIteratorAssignment<typename V::const_reverse_iterator>( u.rbegin() ); 208 TestIteratorAssignment<typename V::reverse_iterator>( v.rbegin() ); 209 210 { 211 oneapi::tbb::concurrent_vector<int> v1, v2(1ul, 100); 212 v1.assign(1, 100); 213 REQUIRE(v1 == v2); 214 REQUIRE_MESSAGE((v1.size() == 1 && v1[0] == 100), "used integral iterators"); 215 } 216 } 217 218 inline void NextSize( int& s ) { 219 if( s<=32 ) ++s; 220 else s += s/10; 221 } 222 223 224 template<typename T, std::size_t N> 225 inline T* end( T(& array)[N]) { 226 return array + utils::array_length(array) ; 227 } 228 229 template<typename vector_t> 230 static void CheckVector( const vector_t& cv, std::size_t expected_size, std::size_t /*old_size*/ ) { 231 REQUIRE( cv.capacity()>=expected_size ); 232 REQUIRE( cv.size()==expected_size ); 233 REQUIRE( cv.empty()==(expected_size==0) ); 234 for( int j=0; j<int(expected_size); ++j ) { 235 CHECK((cv[j].bar()==~j)); 236 } 237 } 238 239 void TestResizeAndCopy() { 240 using allocator_t = StaticSharedCountingAllocator<std::allocator<move_support_tests::Foo>>; 241 using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::Foo, allocator_t>; 242 allocator_t::init_counters(); 243 for( int old_size=0; old_size<=0; NextSize( old_size ) ) { 244 for( int new_size=0; new_size<=8; NextSize( new_size ) ) { 245 std::size_t count = move_support_tests::foo_count; 246 247 vector_t v; 248 REQUIRE( count==move_support_tests::foo_count ); 249 v.assign(old_size/2, move_support_tests::Foo() ); 250 REQUIRE( ((count+old_size/2) == move_support_tests::foo_count) ); 251 for( int j=0; j<old_size/2; ++j ){ 252 REQUIRE( v[j].state == move_support_tests::Foo::CopyInitialized); 253 } 254 255 v.assign(move_support_tests::FooIterator(0), move_support_tests::FooIterator(old_size)); 256 v.resize(new_size, move_support_tests::Foo(33) ); 257 REQUIRE(count+new_size==move_support_tests::foo_count); 258 for( int j=0; j<new_size; ++j ) { 259 int expected = j<old_size ? j : 33; 260 CHECK((v[j].bar()==expected)); 261 } 262 REQUIRE( v.size()==std::size_t(new_size) ); 263 for( int j=0; j<new_size; ++j ) { 264 v[j].bar() = ~j; 265 } 266 267 const vector_t& cv = v; 268 // Try copy constructor 269 vector_t copy_of_v(cv); 270 CheckVector(cv,new_size,old_size); 271 272 REQUIRE( !(v != copy_of_v) ); 273 v.clear(); 274 275 REQUIRE( v.empty() ); 276 swap(v, copy_of_v); 277 REQUIRE( copy_of_v.empty() ); 278 CheckVector(v,new_size,old_size); 279 } 280 } 281 REQUIRE( allocator_t::items_constructed == allocator_t::items_destroyed ); 282 REQUIRE( allocator_t::items_allocated == allocator_t::items_freed ); 283 REQUIRE( allocator_t::allocations == allocator_t::frees ); 284 } 285 286 287 void TestCopyAssignment() { 288 using allocator_t = StaticCountingAllocator<std::allocator<move_support_tests::FooWithAssign>>; 289 using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t>; 290 StaticCountingAllocator<std::allocator<move_support_tests::FooWithAssign>> init_alloc; 291 for( int dst_size=1; dst_size<=128; NextSize( dst_size ) ) { 292 for( int src_size=2; src_size<=128; NextSize( src_size ) ) { 293 vector_t u(move_support_tests::FooIterator(0), move_support_tests::FooIterator(src_size), init_alloc); 294 for( int i=0; i<src_size; ++i ) 295 REQUIRE( u[i].bar()==i ); 296 vector_t v(dst_size, move_support_tests::FooWithAssign(), init_alloc); 297 for( int i=0; i<dst_size; ++i ) { 298 REQUIRE( v[i].state==move_support_tests::Foo::CopyInitialized ); 299 v[i].bar() = ~i; 300 } 301 REQUIRE( v != u ); 302 v.swap(u); 303 CheckVector(u, dst_size, src_size); 304 u.swap(v); 305 // using assignment 306 v = u; 307 REQUIRE( v == u ); 308 u.clear(); 309 REQUIRE( u.size()==0 ); 310 REQUIRE( v.size()==std::size_t(src_size) ); 311 for( int i=0; i<src_size; ++i ){ 312 REQUIRE( v[i].bar()==i ); 313 } 314 u.shrink_to_fit(); // deallocate unused memory 315 } 316 } 317 REQUIRE( allocator_t::items_allocated == allocator_t::items_freed ); 318 REQUIRE( allocator_t::allocations == allocator_t::frees ); 319 } 320 321 template<typename Vector, typename T> 322 void TestGrowToAtLeastWithSourceParameter(T const& src){ 323 static const std::size_t vector_size = 10; 324 Vector v1(vector_size,src); 325 Vector v2; 326 v2.grow_to_at_least(vector_size,src); 327 REQUIRE_MESSAGE(v1==v2,"grow_to_at_least(vector_size,src) did not properly initialize new elements ?"); 328 } 329 330 void TestCapacity() { 331 using allocator_t = StaticCountingAllocator<std::allocator<move_support_tests::Foo> /*TODO: oneapi::tbb::cache_aligned_allocator*/>; 332 using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::Foo, allocator_t>; 333 allocator_t::init_counters(); 334 for( std::size_t old_size=0; old_size<=11000; old_size=(old_size<5 ? old_size+1 : 3*old_size) ) { 335 for( std::size_t new_size=0; new_size<=11000; new_size=(new_size<5 ? new_size+1 : 3*new_size) ) { 336 std::size_t count = move_support_tests::foo_count; 337 { 338 vector_t v; v.reserve(old_size); 339 REQUIRE( v.capacity()>=old_size ); 340 v.reserve( new_size ); 341 REQUIRE( v.capacity()>=old_size ); 342 REQUIRE( v.capacity()>=new_size ); 343 REQUIRE( v.empty() ); 344 std::size_t fill_size = 2*new_size; 345 for (std::size_t i=0; i<fill_size; ++i) { 346 REQUIRE( std::size_t(move_support_tests::foo_count)==count+i ); 347 std::size_t j = v.grow_by(1) - v.begin(); 348 REQUIRE( j==i ); 349 v[j].bar() = int(~j); 350 } 351 vector_t copy_of_v(v); // should allocate first segment with same size as for shrink_to_fit() 352 if(oneapi::tbb::detail::log2(/*reserved size*/old_size|1) > oneapi::tbb::detail::log2(fill_size|1) ){ 353 REQUIRE( v.capacity() != copy_of_v.capacity() ); 354 } 355 v.shrink_to_fit(); 356 REQUIRE( v.capacity() == copy_of_v.capacity() ); 357 CheckVector(v, new_size*2, old_size); // check vector correctness 358 REQUIRE( v==copy_of_v ); // TODO: check also segments layout equality 359 } 360 REQUIRE( move_support_tests::foo_count==count ); 361 } 362 } 363 REQUIRE( allocator_t::items_allocated == allocator_t::items_freed ); 364 REQUIRE( allocator_t::allocations == allocator_t::frees ); 365 } 366 367 template<typename c_vector> 368 std::size_t get_early_size(c_vector & v){ 369 return v.grow_by(0) - v.begin(); 370 } 371 372 void verify_c_vector_size(std::size_t size, std::size_t capacity, std::size_t early_size){ 373 REQUIRE( size <= capacity ); 374 REQUIRE( early_size >= size ); 375 } 376 377 template<typename c_vector_t> 378 void verify_c_vector_size(c_vector_t & c_v){ 379 verify_c_vector_size(c_v.size(), c_v.capacity(), get_early_size(c_v)); 380 } 381 382 #if TBB_USE_EXCEPTIONS 383 void TestExceptions() { 384 using allocator_t = StaticSharedCountingAllocator<std::allocator<move_support_tests::FooWithAssign>>; 385 using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t>; 386 387 enum methods { 388 zero_method = 0, 389 ctor_copy, ctor_size, assign_nt, assign_ir, reserve, compact, 390 all_methods 391 }; 392 REQUIRE( !move_support_tests::foo_count ); 393 394 try { 395 vector_t src(move_support_tests::FooIterator(0), move_support_tests::FooIterator(N)); // original data 396 397 for(int t = 0; t < 2; ++t) // exception type 398 for(int m = zero_method+1; m < all_methods; ++m) 399 { 400 move_support_tests::track_foo_count<__LINE__> check_all_foo_destroyed_on_exit{}; 401 move_support_tests::track_allocator_memory<allocator_t> verify_no_leak_at_exit{}; 402 allocator_t::init_counters(); 403 if(t) move_support_tests::max_foo_count = move_support_tests::foo_count + N/4; 404 else allocator_t::set_limits(N/4); 405 vector_t victim; 406 try { 407 switch(m) { 408 case ctor_copy: { 409 vector_t acopy(src); 410 } break; // auto destruction after exception is checked by ~Foo 411 case ctor_size: { 412 vector_t sized(N); 413 } break; // auto destruction after exception is checked by ~Foo 414 // Do not test assignment constructor due to reusing of same methods as below 415 case assign_nt: { 416 victim.assign(N, move_support_tests::FooWithAssign()); 417 } break; 418 case assign_ir: { 419 victim.assign(move_support_tests::FooIterator(0), move_support_tests::FooIterator(N)); 420 } break; 421 case reserve: { 422 try { 423 victim.reserve(victim.max_size()+1); 424 } catch(std::length_error &) { 425 } catch(...) { 426 INFO("ERROR: unrecognized exception - known compiler issue\n"); 427 } 428 victim.reserve(N); 429 } break; 430 case compact: { 431 if(t) move_support_tests::max_foo_count = 0; else allocator_t::set_limits(); // reset limits 432 victim.reserve(2); 433 victim = src; // fragmented assignment 434 if(t) { 435 move_support_tests::max_foo_count = move_support_tests::foo_count + 10; 436 } 437 else { 438 allocator_t::set_limits(1); // block any allocation 439 } 440 victim.shrink_to_fit(); // should start defragmenting first segment 441 } break; 442 default:; 443 } 444 if(!t || m != reserve) REQUIRE_MESSAGE(false, "should throw an exception"); 445 } catch(std::bad_alloc &e) { 446 allocator_t::set_limits(); move_support_tests::max_foo_count = 0; 447 std::size_t capacity = victim.capacity(); 448 std::size_t size = victim.size(); 449 450 std::size_t req_size = get_early_size(victim); 451 452 verify_c_vector_size(size, capacity, req_size); 453 454 switch(m) { 455 case reserve: 456 if(t) REQUIRE(false); 457 utils_fallthrough; 458 case assign_nt: 459 case assign_ir: 460 if(!t) { 461 REQUIRE_MESSAGE(capacity < N/2, "unexpected capacity"); 462 REQUIRE_MESSAGE(size == 0, "unexpected size"); 463 break; 464 } else { 465 REQUIRE_MESSAGE(size == N, "unexpected size"); 466 REQUIRE_MESSAGE(capacity >= N, "unexpected capacity"); 467 int i; 468 for(i = 1; ; ++i) 469 if(!victim[i].zero_bar()) break; 470 else { 471 REQUIRE(victim[i].bar() == (m == assign_ir? i : move_support_tests::initial_bar)); 472 } 473 for(; size_t(i) < size; ++i) { 474 REQUIRE(!victim[i].zero_bar()); 475 } 476 REQUIRE(size_t(i) == size); 477 break; 478 } 479 case compact: 480 REQUIRE_MESSAGE(capacity > 0, "unexpected capacity"); 481 REQUIRE_MESSAGE(victim == src, "shrink_to_fit() is broken"); 482 break; 483 484 default:; // nothing to check here 485 } 486 INFO("Exception " << m << ": " << e.what() << "\t- ok\n"); 487 } 488 } 489 } catch(...) { 490 REQUIRE_MESSAGE(false, "unexpected exception"); 491 } 492 } 493 #endif 494 495 void verify_c_vector_capacity_is_below(size_t capacity, size_t high){ 496 REQUIRE_MESSAGE(capacity > 0, "unexpected capacity"); 497 REQUIRE_MESSAGE(capacity < high, "unexpected capacity"); 498 } 499 500 template<typename allocator_t> 501 void verify_vector_partially_copied( 502 oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t> const& victim, size_t planned_victim_size, 503 oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t> const& src, bool is_memory_allocation_failure) 504 { 505 if (is_memory_allocation_failure) { // allocator generated exception 506 using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t>; 507 REQUIRE_MESSAGE( victim == vector_t(src.begin(), src.begin() + victim.size(), src.get_allocator()), "failed to properly copy of source ?" ); 508 }else{ 509 REQUIRE_MESSAGE( std::equal(victim.begin(), victim.begin() + planned_victim_size, src.begin()), "failed to properly copy items before the exception?" ); 510 REQUIRE_MESSAGE( (std::all_of( victim.begin() + planned_victim_size, victim.end(), is_state_predicate<move_support_tests::Foo::ZeroInitialized>()) ), "failed to zero-initialize items left not constructed after the exception?" ); 511 } 512 } 513 514 template<typename vector_t> 515 void verify_last_segment_allocation_failed(vector_t const& victim){ 516 utils::suppress_unused_warning(victim); 517 CHECK_THROWS_AS((victim.at(victim.size())), std::out_of_range); 518 } 519 520 template<typename vector_t> 521 void verify_copy_and_assign_from_produce_the_same(vector_t const& victim){ 522 //TODO: remove explicit copy of allocator when full support of C++11 allocator_traits in concurrent_vector is present 523 vector_t copy_of_victim(victim, victim.get_allocator()); 524 REQUIRE_MESSAGE(copy_of_victim == victim, "copy doesn't match original"); 525 vector_t copy_of_victim2(10, victim[0], victim.get_allocator()); 526 copy_of_victim2 = victim; 527 REQUIRE_MESSAGE(copy_of_victim == copy_of_victim2, "assignment doesn't match copying"); 528 } 529 530 template<typename vector_t> 531 void verify_assignment_operator_throws_bad_last_alloc(vector_t & victim){ 532 vector_t copy_of_victim(victim, victim.get_allocator()); 533 //CHECK_THROWS_AS(victim = copy_of_victim, oneapi::tbb::bad_last_alloc); //TODO exceptions support 534 } 535 536 //TODO: split into two separate tests 537 //TODO: remove code duplication in exception safety tests 538 void test_ex_assign_operator(){ 539 //TODO: use __FUNCTION__ for test name 540 using allocator_t = StaticCountingAllocator<std::allocator<move_support_tests::FooWithAssign>>; 541 using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t>; 542 543 move_support_tests::track_foo_count<__LINE__> check_all_foo_destroyed_on_exit{}; 544 move_support_tests::track_allocator_memory<allocator_t> verify_no_leak_at_exit{}; 545 546 vector_t src(move_support_tests::FooIterator(0), move_support_tests::FooIterator(N)); // original data 547 548 const size_t planned_victim_size = N/4; 549 550 for(int t = 0; t < 2; ++t) { // exception type 551 vector_t victim; 552 victim.reserve(2); // get fragmented assignment 553 REQUIRE_THROWS_AS([&](){ 554 move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + planned_victim_size, t); 555 move_support_tests::LimitAllocatedItemsInScope<allocator_t> allocator_limit(allocator_t::items_allocated + planned_victim_size, !t); 556 557 victim = src; // fragmented assignment 558 }(), const std::bad_alloc); 559 560 verify_c_vector_size(victim); 561 562 if(!t) { 563 verify_c_vector_capacity_is_below(victim.capacity(), N); 564 } 565 566 verify_vector_partially_copied(victim, planned_victim_size, src, !t); 567 verify_last_segment_allocation_failed(victim); 568 verify_copy_and_assign_from_produce_the_same(victim); 569 verify_assignment_operator_throws_bad_last_alloc(victim); //TODO exceptions support 570 } 571 } 572 573 template<typename T> 574 void AssertSameType( const T& /*x*/, const T& /*y*/ ) {} 575 576 struct test_grow_by { 577 template<typename container_type, typename element_type> 578 static void test( std::initializer_list<element_type> const& il, container_type const& expected ) { 579 container_type vd; 580 vd.grow_by( il ); 581 REQUIRE_MESSAGE( vd == expected, "grow_by with an initializer list failed" ); 582 } 583 }; 584 585 template<typename Iterator, typename T> 586 void TestIteratorTraits() { 587 AssertSameType( static_cast<typename Iterator::difference_type*>(0), static_cast<std::ptrdiff_t*>(0) ); 588 AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) ); 589 AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) ); 590 AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::random_access_iterator_tag*>(0) ); 591 T x; 592 typename Iterator::reference xr = x; 593 typename Iterator::pointer xp = &x; 594 REQUIRE( &xr==xp ); 595 } 596 597 void TestInitList() { 598 using namespace initializer_list_support_tests; 599 test_initializer_list_support<oneapi::tbb::concurrent_vector<char>, test_grow_by>( { 1, 2, 3, 4, 5 } ); 600 test_initializer_list_support<oneapi::tbb::concurrent_vector<int>, test_grow_by>( {} ); 601 } 602 603 namespace TestMoveInShrinkToFitHelpers { 604 struct dummy : StateTrackable<>{ 605 int i; 606 dummy(int an_i) noexcept : StateTrackable<>(0), i(an_i) {} 607 608 friend bool operator== (const dummy &lhs, const dummy &rhs){ return lhs.i == rhs.i; } 609 }; 610 } 611 612 void TestSerialMoveInShrinkToFit(){ 613 using TestMoveInShrinkToFitHelpers::dummy; 614 615 static_assert(std::is_nothrow_move_constructible<dummy>::value,"incorrect test setup or broken configuration?"); 616 { 617 dummy src(0); 618 REQUIRE_MESSAGE(is_state<StateTrackableBase::MoveInitialized>(dummy(std::move_if_noexcept(src))),"broken configuration ?"); 619 } 620 static const std::size_t sequence_size = 15; 621 using c_vector_t = oneapi::tbb::concurrent_vector<dummy>; 622 std::vector<dummy> source(sequence_size, 0); 623 std::generate_n(source.begin(), source.size(), std::rand); 624 625 c_vector_t c_vector; 626 c_vector.reserve(1); //make it fragmented 627 628 c_vector.assign(source.begin(), source.end()); 629 move_support_tests::MemoryLocations c_vector_before_shrink(c_vector); 630 c_vector.shrink_to_fit(); 631 632 REQUIRE_MESSAGE(c_vector_before_shrink.content_location_changed(c_vector), "incorrect test setup? shrink_to_fit should cause moving elements to other memory locations while it is not"); 633 REQUIRE_MESSAGE((std::all_of(c_vector.begin(), c_vector.end(), is_state_predicate<StateTrackableBase::MoveInitialized>())), "container did not move construct some elements?"); 634 REQUIRE((c_vector == c_vector_t(source.begin(),source.end()))); 635 } 636 637 struct default_container_traits { 638 template <typename container_type, typename iterator_type> 639 static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end){ 640 container_type* ptr = reinterpret_cast<container_type*>(&storage); 641 new (ptr) container_type(begin, end); 642 return *ptr; 643 } 644 645 template <typename container_type, typename iterator_type, typename allocator_type> 646 static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end, allocator_type const& a){ 647 container_type* ptr = reinterpret_cast<container_type*>(&storage); 648 new (ptr) container_type(begin, end, a); 649 return *ptr; 650 } 651 }; 652 653 struct c_vector_type : default_container_traits { 654 template <typename T, typename Allocator> 655 using container_type = oneapi::tbb::concurrent_vector<T, Allocator>; 656 657 template <typename T> 658 using container_value_type = T; 659 660 using init_iterator_type = move_support_tests::FooIterator; 661 template<typename element_type, typename allocator_type> 662 struct apply{ 663 using type = oneapi::tbb::concurrent_vector<element_type, allocator_type >; 664 }; 665 666 enum{ expected_number_of_items_to_allocate_for_steal_move = 0 }; 667 668 template<typename element_type, typename allocator_type, typename iterator> 669 static bool equal(oneapi::tbb::concurrent_vector<element_type, allocator_type > const& c, iterator begin, iterator end){ 670 bool equal_sizes = (std::size_t)std::distance(begin, end) == c.size(); 671 return equal_sizes && std::equal(c.begin(), c.end(), begin); 672 } 673 }; 674 675 void TestSerialGrowByWithMoveIterators(){ 676 using fixture_t = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type>::type; 677 using vector_t = fixture_t::container_type; 678 679 fixture_t fixture; 680 681 vector_t dst(fixture.dst_allocator); 682 dst.grow_by(std::make_move_iterator(fixture.source.begin()), std::make_move_iterator(fixture.source.end())); 683 684 fixture.verify_content_deep_moved(dst); 685 } 686 687 namespace test_grow_to_at_least_helpers { 688 template<typename MyVector > 689 class GrowToAtLeast { 690 using const_reference = typename MyVector::const_reference; 691 692 const bool my_use_two_args_form ; 693 MyVector& my_vector; 694 const_reference my_init_from; 695 public: 696 void operator()( const oneapi::tbb::blocked_range<std::size_t>& range ) const { 697 for( std::size_t i=range.begin(); i!=range.end(); ++i ) { 698 std::size_t n = my_vector.size(); 699 std::size_t req = (i % (2*n+1))+1; 700 701 typename MyVector::iterator p; 702 move_support_tests::Foo::State desired_state; 703 if (my_use_two_args_form){ 704 p = my_vector.grow_to_at_least(req,my_init_from); 705 desired_state = move_support_tests::Foo::CopyInitialized; 706 }else{ 707 p = my_vector.grow_to_at_least(req); 708 desired_state = move_support_tests::Foo::DefaultInitialized; 709 } 710 if( p-my_vector.begin() < typename MyVector::difference_type(req) ) 711 CHECK((p->state == desired_state || p->state == move_support_tests::Foo::ZeroInitialized)); 712 CHECK(my_vector.size() >= req); 713 } 714 } 715 GrowToAtLeast(bool use_two_args_form, MyVector& vector, const_reference init_from ) 716 : my_use_two_args_form(use_two_args_form), my_vector(vector), my_init_from(init_from) {} 717 }; 718 } 719 720 template<bool use_two_arg_form> 721 void TestConcurrentGrowToAtLeastImpl() { 722 using namespace test_grow_to_at_least_helpers; 723 using MyAllocator = StaticCountingAllocator<std::allocator<move_support_tests::Foo>>; 724 using MyVector = oneapi::tbb::concurrent_vector<move_support_tests::Foo, MyAllocator>; 725 move_support_tests::Foo copy_from; 726 MyAllocator::init_counters(); 727 MyVector v(2, move_support_tests::Foo(), MyAllocator()); 728 for (std::size_t s=1; s<1000; s*=10) { 729 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<std::size_t>(0, 10000*s, s), GrowToAtLeast<MyVector>(use_two_arg_form, v, copy_from), oneapi::tbb::simple_partitioner()); 730 } 731 732 v.clear(); 733 v.shrink_to_fit(); 734 std::size_t items_allocated = v.get_allocator().items_allocated, 735 items_freed = v.get_allocator().items_freed; 736 std::size_t allocations = v.get_allocator().allocations, 737 frees = v.get_allocator().frees; 738 REQUIRE( items_allocated == items_freed ); 739 REQUIRE( allocations == frees ); 740 } 741 742 struct AssignElement { 743 using iterator = oneapi::tbb::concurrent_vector<int>::range_type::iterator; 744 iterator base; 745 void operator()( const oneapi::tbb::concurrent_vector<int>::range_type& range ) const { 746 for (iterator i = range.begin(); i != range.end(); ++i) { 747 if (*i != 0) { 748 REPORT("ERROR for v[%ld]\n", long(i - base)); 749 } 750 *i = int(i-base); 751 } 752 } 753 AssignElement( iterator base_ ) : base(base_) {} 754 }; 755 756 struct CheckElement { 757 using iterator = oneapi::tbb::concurrent_vector<int>::const_range_type::iterator; 758 iterator base; 759 void operator()( const oneapi::tbb::concurrent_vector<int>::const_range_type& range ) const { 760 for (iterator i = range.begin(); i != range.end(); ++i) { 761 if (*i != int(i-base)) { 762 REPORT("ERROR for v[%ld]\n", long(i-base)); 763 } 764 } 765 } 766 CheckElement( iterator base_ ) : base(base_) {} 767 }; 768 769 // Test parallel access by iterators 770 void TestParallelFor( std::size_t nthread ) { 771 using vector_type = oneapi::tbb::concurrent_vector<int>; 772 vector_type v; 773 v.resize(N); 774 oneapi::tbb::tick_count t0 = oneapi::tbb::tick_count::now(); 775 INFO("Calling parallel_for with " << nthread << " threads"); 776 oneapi::tbb::parallel_for(v.range(10000), AssignElement(v.begin())); 777 oneapi::tbb::tick_count t1 = oneapi::tbb::tick_count::now(); 778 const vector_type& u = v; 779 oneapi::tbb::parallel_for(u.range(10000), CheckElement(u.begin())); 780 oneapi::tbb::tick_count t2 = oneapi::tbb::tick_count::now(); 781 INFO("Time for parallel_for: assign time = " << (t1 - t0).seconds() << 782 " , check time = " << (t2 - t1).seconds()); 783 for (int i = 0; std::size_t(i) < v.size(); ++i) { 784 if (v[i] != i) { 785 REPORT("ERROR for v[%ld]\n", i); 786 } 787 } 788 } 789 790 791 struct grain_map { 792 enum grow_method_enum { 793 grow_by_range = 1, 794 grow_by_default, 795 grow_by_copy, 796 grow_by_init_list, 797 push_back, 798 push_back_move, 799 emplace_back, 800 last_method 801 }; 802 803 struct range_part { 804 std::size_t number_of_parts; 805 grain_map::grow_method_enum method; 806 bool distribute; 807 move_support_tests::Foo::State expected_element_state; 808 }; 809 810 const std::vector<range_part> distributed; 811 const std::vector<range_part> batched; 812 const std::size_t total_number_of_parts; 813 814 grain_map(const range_part* begin, const range_part* end) 815 : distributed(separate(begin,end, &distributed::is_not)) 816 , batched(separate(begin,end, &distributed::is_yes)) 817 , total_number_of_parts(std::accumulate(begin, end, (std::size_t)0, &sum_number_of_parts::sum)) 818 {} 819 820 private: 821 struct sum_number_of_parts{ 822 static std::size_t sum(std::size_t accumulator, grain_map::range_part const& rp){ return accumulator + rp.number_of_parts;} 823 }; 824 825 template <typename functor_t> 826 static std::vector<range_part> separate(const range_part* begin, const range_part* end, functor_t f){ 827 std::vector<range_part> part; 828 part.reserve(std::distance(begin,end)); 829 //copy all that false==f(*it) 830 std::remove_copy_if(begin, end, std::back_inserter(part), f); 831 832 return part; 833 } 834 835 struct distributed { 836 static bool is_not(range_part const& rp){ return !rp.distribute;} 837 static bool is_yes(range_part const& rp){ return rp.distribute;} 838 }; 839 }; 840 841 842 //! Test concurrent invocations of method concurrent_vector::grow_by 843 template<typename MyVector> 844 class GrowBy { 845 MyVector& my_vector; 846 const grain_map& my_grain_map; 847 std::size_t my_part_weight; 848 public: 849 void operator()( const oneapi::tbb::blocked_range<std::size_t>& range ) const { 850 CHECK(range.begin() < range.end()); 851 852 std::size_t current_adding_index_in_cvector = range.begin(); 853 854 for (std::size_t index = 0; index < my_grain_map.batched.size(); ++index){ 855 const grain_map::range_part& batch_part = my_grain_map.batched[index]; 856 const std::size_t number_of_items_to_add = batch_part.number_of_parts * my_part_weight; 857 const std::size_t end = current_adding_index_in_cvector + number_of_items_to_add; 858 859 switch(batch_part.method){ 860 case grain_map::grow_by_range : { 861 my_vector.grow_by(move_support_tests::FooIterator(current_adding_index_in_cvector), move_support_tests::FooIterator(end)); 862 } break; 863 case grain_map::grow_by_default : { 864 typename MyVector::iterator const s = my_vector.grow_by(number_of_items_to_add); 865 for (std::size_t k = 0; k < number_of_items_to_add; ++k) { 866 s[k].bar() = current_adding_index_in_cvector + k; 867 } 868 } break; 869 case grain_map::grow_by_init_list : { 870 move_support_tests::FooIterator curr(current_adding_index_in_cvector); 871 for (std::size_t k = 0; k < number_of_items_to_add; ++k) { 872 if (k + 4 < number_of_items_to_add) { 873 my_vector.grow_by( { *curr++, *curr++, *curr++, *curr++, *curr++ } ); 874 k += 4; 875 } else { 876 my_vector.grow_by( { *curr++ } ); 877 } 878 } 879 CHECK(curr == move_support_tests::FooIterator(end)); 880 } break; 881 default : { REQUIRE_MESSAGE(false, "using unimplemented method of batch add in ConcurrentGrow test.");} break; 882 }; 883 884 current_adding_index_in_cvector = end; 885 } 886 887 std::vector<std::size_t> items_left_to_add(my_grain_map.distributed.size()); 888 for (std::size_t i=0; i < my_grain_map.distributed.size(); ++i) { 889 items_left_to_add[i] = my_grain_map.distributed[i].number_of_parts * my_part_weight; 890 } 891 892 for (;current_adding_index_in_cvector < range.end(); ++current_adding_index_in_cvector) { 893 std::size_t method_index = current_adding_index_in_cvector % my_grain_map.distributed.size(); 894 895 if (!items_left_to_add[method_index]) { 896 struct not_zero{ 897 static bool is(std::size_t items_to_add){ return items_to_add;} 898 }; 899 method_index = std::distance(items_left_to_add.begin(), std::find_if(items_left_to_add.begin(), items_left_to_add.end(), ¬_zero::is)); 900 REQUIRE_MESSAGE(method_index < my_grain_map.distributed.size(), "incorrect test setup - wrong expected distribution: left free space but no elements to add?"); 901 }; 902 903 REQUIRE_MESSAGE(items_left_to_add[method_index], "logic error ?"); 904 const grain_map::range_part& distributed_part = my_grain_map.distributed[method_index]; 905 906 typename MyVector::iterator r; 907 typename MyVector::value_type source; 908 source.bar() = current_adding_index_in_cvector; 909 910 switch(distributed_part.method){ 911 case grain_map::grow_by_default : { 912 (r = my_vector.grow_by(1))->bar() = current_adding_index_in_cvector; 913 } break; 914 case grain_map::grow_by_copy : { 915 r = my_vector.grow_by(1, source); 916 } break; 917 case grain_map::push_back : { 918 r = my_vector.push_back(source); 919 } break; 920 case grain_map::push_back_move : { 921 r = my_vector.push_back(std::move(source)); 922 } break; 923 case grain_map::emplace_back : { 924 r = my_vector.emplace_back(current_adding_index_in_cvector); 925 } break; 926 927 default : { REQUIRE_MESSAGE(false, "using unimplemented method of batch add in ConcurrentGrow test.");} break; 928 }; 929 930 CHECK(static_cast<std::size_t>(r->bar()) == current_adding_index_in_cvector); 931 } 932 933 } 934 935 GrowBy( MyVector& vector, const grain_map& m, std::size_t part_weight ) 936 : my_vector(vector), my_grain_map(m), my_part_weight(part_weight) 937 {} 938 }; 939 940 //! Test concurrent invocations of grow methods 941 void TestConcurrentGrowBy() { 942 943 const grain_map::range_part concurrent_grow_single_range_map [] = { 944 // number_of_parts, method, distribute, expected_element_state 945 {3, grain_map::grow_by_range, false, move_support_tests::Foo::MoveInitialized}, 946 947 {1, grain_map::grow_by_init_list, false, move_support_tests::Foo::CopyInitialized}, 948 949 {2, grain_map::grow_by_default, false, move_support_tests::Foo::DefaultInitialized}, 950 {1, grain_map::grow_by_default, true, move_support_tests::Foo::DefaultInitialized}, 951 {1, grain_map::grow_by_copy, true, move_support_tests::Foo::CopyInitialized}, 952 {1, grain_map::push_back, true, move_support_tests::Foo::CopyInitialized}, 953 954 {1, grain_map::push_back_move, true, move_support_tests::Foo::MoveInitialized}, 955 956 {1, grain_map::emplace_back, true, move_support_tests::Foo::DirectInitialized}, 957 958 }; 959 960 using MyAllocator = StaticCountingAllocator<std::allocator<move_support_tests::Foo> >; 961 using MyVector = oneapi::tbb::concurrent_vector<move_support_tests::Foo, MyAllocator>; 962 963 MyAllocator::init_counters(); 964 { 965 grain_map m(concurrent_grow_single_range_map, end(concurrent_grow_single_range_map)); 966 967 static const std::size_t desired_grain_size = 100; 968 969 static const std::size_t part_weight = desired_grain_size / m.total_number_of_parts; 970 static const std::size_t grain_size = part_weight * m.total_number_of_parts; 971 static const std::size_t number_of_grains = 8; //this should be (power of two) in order to get minimal ranges equal to grain_size 972 static const std::size_t range_size = grain_size * number_of_grains; 973 974 MyAllocator a; 975 MyVector v(a); 976 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<std::size_t>(0, range_size, grain_size), GrowBy<MyVector>(v, m, part_weight), oneapi::tbb::simple_partitioner()); 977 978 REQUIRE( v.size() == std::size_t(range_size) ); 979 980 // Verify that v is a permutation of 0..m 981 size_t inversions = 0, direct_inits = 0, def_inits = 0, copy_inits = 0, move_inits = 0; 982 std::vector<bool> found(range_size, 0); 983 for( std::size_t i=0; i<range_size; ++i ) { 984 if( v[i].state == move_support_tests::Foo::DefaultInitialized ) ++def_inits; 985 else if( v[i].state == move_support_tests::Foo::DirectInitialized ) ++direct_inits; 986 else if( v[i].state == move_support_tests::Foo::CopyInitialized ) ++copy_inits; 987 else if( v[i].state == move_support_tests::Foo::MoveInitialized ) ++move_inits; 988 else { 989 REQUIRE_MESSAGE( false, "v[i] seems not initialized"); 990 } 991 intptr_t index = v[i].bar(); 992 REQUIRE( !found[index] ); 993 found[index] = true; 994 if( i>0 ) 995 inversions += v[i].bar()<v[i-1].bar(); 996 } 997 998 std::size_t expected_direct_inits = 0, expected_def_inits = 0, expected_copy_inits = 0, expected_move_inits = 0; 999 for (std::size_t i=0; i < utils::array_length(concurrent_grow_single_range_map); ++i){ 1000 const grain_map::range_part& rp =concurrent_grow_single_range_map[i]; 1001 switch (rp.expected_element_state){ 1002 case move_support_tests::Foo::DefaultInitialized: { expected_def_inits += rp.number_of_parts ; } break; 1003 case move_support_tests::Foo::DirectInitialized: { expected_direct_inits += rp.number_of_parts ;} break; 1004 case move_support_tests::Foo::MoveInitialized: { expected_move_inits += rp.number_of_parts ;} break; 1005 case move_support_tests::Foo::CopyInitialized: { expected_copy_inits += rp.number_of_parts ;} break; 1006 default: {REQUIRE_MESSAGE(false, "unexpected expected state");}break; 1007 }; 1008 } 1009 1010 expected_def_inits *= part_weight * number_of_grains; 1011 expected_move_inits *= part_weight * number_of_grains; 1012 expected_copy_inits *= part_weight * number_of_grains; 1013 expected_direct_inits *= part_weight * number_of_grains; 1014 1015 REQUIRE( def_inits == expected_def_inits ); 1016 REQUIRE( copy_inits == expected_copy_inits ); 1017 REQUIRE( move_inits == expected_move_inits ); 1018 REQUIRE( direct_inits == expected_direct_inits ); 1019 } 1020 //TODO: factor this into separate thing, as it seems to used in big number of tests 1021 std::size_t items_allocated = MyAllocator::items_allocated, 1022 items_freed = MyAllocator::items_freed; 1023 std::size_t allocations = MyAllocator::allocations, 1024 frees = MyAllocator::frees; 1025 REQUIRE(items_allocated == items_freed); 1026 REQUIRE(allocations == frees); 1027 } 1028 1029 void TestComparison() { 1030 std::string str[3]; 1031 str[0] = "abc"; 1032 str[1].assign("cba"); 1033 str[2].assign("abc"); // same as 0th 1034 oneapi::tbb::concurrent_vector<char> var[3]; 1035 var[0].assign(str[0].begin(), str[0].end()); 1036 var[1].assign(str[0].rbegin(), str[0].rend()); 1037 var[2].assign(var[1].rbegin(), var[1].rend()); // same as 0th 1038 for (int i = 0; i < 3; ++i) { 1039 for (int j = 0; j < 3; ++j) { 1040 REQUIRE( (var[i] == var[j]) == (str[i] == str[j]) ); 1041 REQUIRE( (var[i] != var[j]) == (str[i] != str[j]) ); 1042 REQUIRE( (var[i] < var[j]) == (str[i] < str[j]) ); 1043 REQUIRE( (var[i] > var[j]) == (str[i] > str[j]) ); 1044 REQUIRE( (var[i] <= var[j]) == (str[i] <= str[j]) ); 1045 REQUIRE( (var[i] >= var[j]) == (str[i] >= str[j]) ); 1046 } 1047 } 1048 } 1049 1050 #if TBB_USE_EXCEPTIONS 1051 void test_ex_move_assignment_memory_failure() { 1052 using fixture_type = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type, /*POCMA = */std::false_type>::type; 1053 using arena_allocator_fixture_type = move_support_tests::ArenaAllocatorFixture<move_support_tests::FooWithAssign, /*POCMA = */std::false_type>; 1054 using allocator_type = fixture_type::allocator_type; 1055 using vector_type = fixture_type::container_type; 1056 1057 fixture_type fixture; 1058 arena_allocator_fixture_type arena_allocator_fixture(4 * fixture.container_size); 1059 1060 const std::size_t allocation_limit = fixture.container_size/4; 1061 1062 vector_type victim(arena_allocator_fixture.allocator); 1063 victim.reserve(2); // for fragmented assignment 1064 1065 REQUIRE_THROWS_AS( 1066 [&]() { 1067 move_support_tests::LimitAllocatedItemsInScope<allocator_type> allocator_limit(allocator_type::items_allocated + allocation_limit); 1068 victim = std::move(fixture.source); // fragmented assignment 1069 }(), 1070 std::bad_alloc 1071 ); 1072 1073 verify_c_vector_size(victim); 1074 verify_c_vector_capacity_is_below(victim.capacity(), allocation_limit + 2); 1075 fixture.verify_part_of_content_deep_moved(victim, victim.size()); 1076 1077 verify_last_segment_allocation_failed(victim); 1078 verify_copy_and_assign_from_produce_the_same(victim); 1079 verify_assignment_operator_throws_bad_last_alloc(victim); 1080 } 1081 1082 void test_ex_move_assignment_element_ctor_exception(){ 1083 using fixture_type = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type, std::false_type>::type; 1084 using arena_allocator_fixture_type = move_support_tests::ArenaAllocatorFixture<move_support_tests::FooWithAssign, std::false_type>; 1085 using vector_type = fixture_type::container_type; 1086 1087 fixture_type fixture; 1088 const size_t planned_victim_size = fixture.container_size/4; 1089 arena_allocator_fixture_type arena_allocator_fixture(4 * fixture.container_size); 1090 1091 vector_type victim(arena_allocator_fixture.allocator); 1092 victim.reserve(2); // get fragmented assignment 1093 1094 REQUIRE_THROWS_AS( 1095 [&](){ 1096 move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + planned_victim_size); 1097 victim = std::move(fixture.source); // fragmented assignment 1098 }(), 1099 std::bad_alloc 1100 ); 1101 1102 verify_c_vector_size(victim); 1103 1104 fixture.verify_part_of_content_deep_moved(victim, planned_victim_size); 1105 1106 verify_last_segment_allocation_failed(victim); 1107 verify_copy_and_assign_from_produce_the_same(victim); 1108 verify_assignment_operator_throws_bad_last_alloc(victim); 1109 } 1110 1111 void test_ex_move_assignment() { 1112 test_ex_move_assignment_memory_failure(); 1113 test_ex_move_assignment_element_ctor_exception(); 1114 } 1115 #endif 1116 1117 template <typename Type, typename Allocator> 1118 class test_grow_by_and_resize { 1119 oneapi::tbb::concurrent_vector<Type, Allocator> &my_c; 1120 public: 1121 test_grow_by_and_resize( oneapi::tbb::concurrent_vector<Type, Allocator> &c ) : my_c(c) {} 1122 void operator()() const { 1123 const typename oneapi::tbb::concurrent_vector<Type, Allocator>::size_type sz = my_c.size(); 1124 my_c.grow_by( 5 ); 1125 REQUIRE( my_c.size() == sz + 5 ); 1126 my_c.resize( sz ); 1127 REQUIRE( my_c.size() == sz ); 1128 } 1129 }; 1130 1131 namespace push_back_exception_safety_helpers { 1132 //TODO: remove code duplication with emplace_helpers::wrapper_type 1133 struct throwing_foo:move_support_tests::Foo { 1134 int value1; 1135 int value2; 1136 explicit throwing_foo(int v1, int v2) : value1 (v1), value2(v2) {} 1137 }; 1138 1139 template< typename foo_t = throwing_foo> 1140 struct fixture { 1141 using vector_t = oneapi::tbb::concurrent_vector<foo_t, std::allocator<foo_t> >; 1142 vector_t v; 1143 1144 void test( void(*p_test)(vector_t&)){ 1145 utils::suppress_unused_warning(p_test); 1146 move_support_tests::track_foo_count<__LINE__> verify_no_foo_leaked_during_exception{}; 1147 utils::suppress_unused_warning(verify_no_foo_leaked_during_exception); 1148 REQUIRE_MESSAGE(v.empty(),"incorrect test setup?" ); 1149 REQUIRE_THROWS_AS(p_test(v), move_support_tests::FooException); 1150 REQUIRE_MESSAGE(is_state<move_support_tests::Foo::ZeroInitialized>(v[0]),"incorrectly filled item during exception in emplace_back?"); 1151 } 1152 }; 1153 } 1154 1155 void TestPushBackMoveExceptionSafety() { 1156 using fixture_t = push_back_exception_safety_helpers::fixture<move_support_tests::Foo>; 1157 fixture_t t; 1158 1159 move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + 1); 1160 1161 struct test { 1162 static void test_move_push_back(fixture_t::vector_t& v) { 1163 move_support_tests::Foo f; 1164 v.push_back(std::move(f)); 1165 } 1166 }; 1167 t.test(&test::test_move_push_back); 1168 } 1169 1170 void TestEmplaceBackExceptionSafety(){ 1171 using fixture_t = push_back_exception_safety_helpers::fixture<>; 1172 fixture_t t; 1173 1174 move_support_tests::Foo dummy; //make FooCount non zero; 1175 utils::suppress_unused_warning(dummy); 1176 move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count); 1177 1178 struct test { 1179 static void test_emplace(fixture_t::vector_t& v) { 1180 v.emplace_back(1,2); 1181 } 1182 }; 1183 t.test(&test::test_emplace); 1184 } 1185 1186 namespace move_semantics_helpers { 1187 struct move_only_type { 1188 const int* my_pointer; 1189 move_only_type(move_only_type && other): my_pointer(other.my_pointer){other.my_pointer=nullptr;} 1190 explicit move_only_type(const int* value): my_pointer(value) {} 1191 }; 1192 } 1193 1194 void TestPushBackMoveOnlyContainer(){ 1195 using namespace move_semantics_helpers; 1196 using vector_t = oneapi::tbb::concurrent_vector<move_only_type >; 1197 vector_t v; 1198 static const int magic_number = 7; 1199 move_only_type src(&magic_number); 1200 v.push_back(std::move(src)); 1201 REQUIRE_MESSAGE((v[0].my_pointer == &magic_number),"item was incorrectly moved during push_back?"); 1202 REQUIRE_MESSAGE(src.my_pointer == nullptr,"item was incorrectly moved during push_back?"); 1203 } 1204 1205 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 1206 template <template <typename...> typename TVector> 1207 void TestDeductionGuides() { 1208 using ComplexType = const std::string*; 1209 std::vector<ComplexType> v; 1210 std::string s = "s"; 1211 auto l = {ComplexType(&s), ComplexType(&s)}; 1212 1213 // check TVector(InputIterator, InputIterator) 1214 TVector v1(v.begin(), v.end()); 1215 static_assert(std::is_same<decltype(v1), TVector<ComplexType>>::value); 1216 1217 // check TVector(InputIterator, InputIterator, Alocator) 1218 TVector v2(v.begin(), v.end(), std::allocator<ComplexType>()); 1219 static_assert(std::is_same<decltype(v2), 1220 TVector<ComplexType, std::allocator<ComplexType>>>::value); 1221 1222 // check TVector(std::initializer_list<T>) 1223 TVector v3(l); 1224 static_assert(std::is_same<decltype(v3), 1225 TVector<ComplexType>>::value); 1226 1227 // check TVector(std::initializer_list, Alocator) 1228 TVector v4(l, std::allocator<ComplexType>()); 1229 static_assert(std::is_same<decltype(v4), TVector<ComplexType, std::allocator<ComplexType>>>::value); 1230 1231 // check TVector(TVector&) 1232 TVector v5(v1); 1233 static_assert(std::is_same<decltype(v5), TVector<ComplexType>>::value); 1234 1235 // check TVector(TVector&, Allocator) 1236 TVector v6(v5, oneapi::tbb::cache_aligned_allocator<ComplexType>()); 1237 static_assert(std::is_same<decltype(v6), TVector<ComplexType, oneapi::tbb::cache_aligned_allocator<ComplexType>>>::value); 1238 1239 // check TVector(TVector&&) 1240 TVector v7(std::move(v1)); 1241 static_assert(std::is_same<decltype(v7), decltype(v1)>::value); 1242 1243 // check TVector(TVector&&, Allocator) 1244 TVector v8(std::move(v5), oneapi::tbb::cache_aligned_allocator<ComplexType>()); 1245 static_assert(std::is_same<decltype(v8), TVector<ComplexType, oneapi::tbb::cache_aligned_allocator<ComplexType>>>::value); 1246 1247 } 1248 #endif 1249 1250 template <template <typename... > class ContainerType> 1251 void test_member_types() { 1252 using default_container_type = ContainerType<int>; 1253 1254 static_assert(std::is_same<typename default_container_type::allocator_type, 1255 oneapi::tbb::cache_aligned_allocator<int>>::value, 1256 "Incorrect default template allocator"); 1257 1258 1259 using test_allocator_type = oneapi::tbb::cache_aligned_allocator<int>; 1260 using container_type = ContainerType<int, test_allocator_type>; 1261 1262 static_assert(std::is_same<typename container_type::value_type, int>::value, 1263 "Incorrect container value_type member type"); 1264 1265 static_assert(std::is_unsigned<typename container_type::size_type>::value, 1266 "Incorrect container size_type member type"); 1267 static_assert(std::is_signed<typename container_type::difference_type>::value, 1268 "Incorrect container difference_type member type"); 1269 1270 using value_type = typename container_type::value_type; 1271 static_assert(std::is_same<typename container_type::reference, value_type&>::value, 1272 "Incorrect container reference member type"); 1273 static_assert(std::is_same<typename container_type::const_reference, const value_type&>::value, 1274 "Incorrect container const_reference member type"); 1275 using allocator_type = typename container_type::allocator_type; 1276 static_assert(std::is_same<typename container_type::pointer, typename std::allocator_traits<allocator_type>::pointer>::value, 1277 "Incorrect container pointer member type"); 1278 static_assert(std::is_same<typename container_type::const_pointer, typename std::allocator_traits<allocator_type>::const_pointer>::value, 1279 "Incorrect container const_pointer member type"); 1280 1281 static_assert(utils::is_random_access_iterator<typename container_type::iterator>::value, 1282 "Incorrect container iterator member type"); 1283 static_assert(!std::is_const<typename container_type::iterator::value_type>::value, 1284 "Incorrect container iterator member type"); 1285 static_assert(utils::is_random_access_iterator<typename container_type::const_iterator>::value, 1286 "Incorrect container const_iterator member type"); 1287 static_assert(std::is_const<typename container_type::const_iterator::value_type>::value, 1288 "Incorrect container iterator member type"); 1289 } 1290 1291 void TestConcurrentGrowToAtLeast() { 1292 TestConcurrentGrowToAtLeastImpl<false>(); 1293 TestConcurrentGrowToAtLeastImpl<true>(); 1294 } 1295 1296 1297 //! Test type matching 1298 //! \brief \ref interface \ref requirement 1299 TEST_CASE("test type matching") { 1300 test_member_types<oneapi::tbb::concurrent_vector>(); 1301 } 1302 1303 //! Test sequential access to elements 1304 //! \brief \ref interface \ref requirement 1305 TEST_CASE("testing sequential for") { 1306 TestSequentialFor<move_support_tests::FooWithAssign> (); 1307 } 1308 1309 //! Test of assign, grow, copying with various sizes 1310 //! \brief \ref interface \ref requirement 1311 TEST_CASE("testing resize and copy"){ 1312 TestResizeAndCopy(); 1313 } 1314 1315 //! Test the assignment operator and swap 1316 //! \brief \ref interface \ref requirement 1317 TEST_CASE("testing copy assignment"){ 1318 TestCopyAssignment(); 1319 } 1320 1321 //! Testing grow_to_at_least operations 1322 //! \brief \ref interface 1323 TEST_CASE("testing grow_to_at_least with source parameter"){ 1324 TestGrowToAtLeastWithSourceParameter<oneapi::tbb::concurrent_vector<int>>(12345); 1325 } 1326 1327 //! Test of capacity, reserve, and shrink_to_fit 1328 //! \brief \ref interface \ref requirement 1329 TEST_CASE("testing capacity"){ 1330 TestCapacity(); 1331 } 1332 1333 #if TBB_USE_EXCEPTIONS 1334 //! Test exceptions 1335 //! \brief \ref requirement 1336 TEST_CASE("testing exceptions"){ 1337 TestExceptions(); 1338 } 1339 1340 //! Test of push_back move exception safety 1341 //! \brief \ref requirement 1342 TEST_CASE("testing push_back move exception safety"){ 1343 TestPushBackMoveExceptionSafety(); 1344 } 1345 1346 //! Test of emplace back move exception safety 1347 //! \brief \ref requirement 1348 TEST_CASE("testing emplace back exception safety"){ 1349 TestEmplaceBackExceptionSafety(); 1350 } 1351 1352 //! Test exceptions guarantees for assign operator 1353 //! \brief \ref requirement 1354 TEST_CASE("testing exception safety guaranteees for assign operator"){ 1355 test_ex_assign_operator(); 1356 } 1357 1358 //! Test exceptions safety guarantees for concurrent_vector move constructor 1359 //! \brief \ref requirement 1360 TEST_CASE("exception safety guarantees for concurrent_vector move constructor") { 1361 move_support_tests::test_ex_move_constructor<c_vector_type>(); 1362 } 1363 1364 //! Test exceptions safety guarantees for concurrent_vector move assignment 1365 //! \brief \ref requirement 1366 TEST_CASE("test exception safety on concurrent_vector move assignment") { 1367 test_ex_move_assignment(); 1368 } 1369 #endif 1370 //! Test push_back in move only container 1371 //! \brief \ref requirement 1372 TEST_CASE("testing push_back move only container"){ 1373 TestPushBackMoveOnlyContainer(); 1374 } 1375 1376 //! Test types for std::iterator_traits in concurrent_vector::iterator 1377 //! \brief \ref requirement 1378 TEST_CASE("testing std::iterator_traits for concurrent_vector::iterator"){ 1379 TestIteratorTraits<oneapi::tbb::concurrent_vector<move_support_tests::Foo>::iterator,move_support_tests::Foo>(); 1380 } 1381 1382 //! Test types for std::iterator_traits in concurrent_vector::const_iterator 1383 //! \brief \ref requirement 1384 TEST_CASE("testing std::iterator_traits for concurrent_vector::const_iterator"){ 1385 TestIteratorTraits<oneapi::tbb::concurrent_vector<move_support_tests::Foo>::const_iterator,const move_support_tests::Foo>(); 1386 } 1387 1388 //! Test initializer_list support 1389 //! \brief \ref interface \ref requirement 1390 TEST_CASE("testing initializer_list support"){ 1391 TestInitList(); 1392 } 1393 1394 //! Test move constructor 1395 //! \brief \ref interface \ref requirement 1396 TEST_CASE("testing move constructor"){ 1397 move_support_tests::test_move_constructor<c_vector_type>(); 1398 } 1399 1400 //! Test move assign operator 1401 //! \brief \ref interface \ref requirement 1402 TEST_CASE("testing move assign operator"){ 1403 move_support_tests::test_move_assignment<c_vector_type>(); 1404 } 1405 1406 //! Test constructor with move iterators 1407 //! \brief \ref requirement 1408 TEST_CASE("testing constructor with move iterators"){ 1409 move_support_tests::test_constructor_with_move_iterators<c_vector_type>(); 1410 } 1411 1412 //! Test assign with move iterators 1413 //! \brief \ref interface \ref requirement 1414 TEST_CASE("testing assign with move iterators"){ 1415 move_support_tests::test_assign_with_move_iterators<c_vector_type>(); 1416 } 1417 1418 //! Test grow_by with move iterator 1419 //! \brief \ref requirement 1420 TEST_CASE("testing serial grow_by with move iterator"){ 1421 TestSerialGrowByWithMoveIterators(); 1422 } 1423 1424 //! Test grow_by with move iterator 1425 //! \brief \ref requirement 1426 TEST_CASE("testing serial move in shrink_to_fit"){ 1427 TestSerialMoveInShrinkToFit(); 1428 } 1429 1430 //! Test concurrent grow 1431 //! \brief \ref requirement 1432 TEST_CASE("testing concurrency"){ 1433 REQUIRE(!move_support_tests::foo_count); 1434 for (std::size_t p = 1; p <= 4; ++p) { 1435 oneapi::tbb::global_control limit(oneapi::tbb::global_control::max_allowed_parallelism, p); 1436 TestParallelFor(p); 1437 TestConcurrentGrowToAtLeast(); 1438 TestConcurrentGrowBy(); 1439 } 1440 1441 REQUIRE(!move_support_tests::foo_count); 1442 } 1443 1444 //! Test assign operations 1445 //! \brief \ref interface \ref requirement 1446 TEST_CASE("testing comparison"){ 1447 TestComparison(); 1448 } 1449 1450 //! Test allocator_traits support in concurrent_vector 1451 //! \brief \ref requirement 1452 TEST_CASE("test allocator_traits support in concurrent_vector") { 1453 test_allocator_traits_support<c_vector_type>(); 1454 } 1455 1456 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 1457 //! Test deduction guides 1458 //! \brief \ref requirement 1459 TEST_CASE("testing deduction guides"){ 1460 TestDeductionGuides<oneapi::tbb::concurrent_vector>(); 1461 } 1462 #endif 1463