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