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*>(0), static_cast<std::ptrdiff_t*>(0) );
600     AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) );
601     AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) );
602     AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::random_access_iterator_tag*>(0) );
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 inversions = 0, 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             if( i>0 )
1007                 inversions += v[i].bar()<v[i-1].bar();
1008         }
1009 
1010         std::size_t expected_direct_inits = 0, expected_def_inits = 0, expected_copy_inits = 0, expected_move_inits = 0;
1011         for (std::size_t i=0; i < utils::array_length(concurrent_grow_single_range_map); ++i){
1012             const grain_map::range_part& rp =concurrent_grow_single_range_map[i];
1013             switch (rp.expected_element_state){
1014             case move_support_tests::Foo::DefaultInitialized: { expected_def_inits += rp.number_of_parts ; } break;
1015             case move_support_tests::Foo::DirectInitialized:  { expected_direct_inits += rp.number_of_parts ;} break;
1016             case move_support_tests::Foo::MoveInitialized:    { expected_move_inits += rp.number_of_parts ;} break;
1017             case move_support_tests::Foo::CopyInitialized:    { expected_copy_inits += rp.number_of_parts ;} break;
1018             default: {REQUIRE_MESSAGE(false, "unexpected expected state");}break;
1019             };
1020         }
1021 
1022         expected_def_inits    *= part_weight * number_of_grains;
1023         expected_move_inits   *= part_weight * number_of_grains;
1024         expected_copy_inits   *= part_weight * number_of_grains;
1025         expected_direct_inits *= part_weight * number_of_grains;
1026 
1027         REQUIRE( def_inits == expected_def_inits );
1028         REQUIRE( copy_inits == expected_copy_inits );
1029         REQUIRE( move_inits == expected_move_inits );
1030         REQUIRE( direct_inits == expected_direct_inits );
1031     }
1032     //TODO: factor this into separate thing, as it seems to used in big number of tests
1033     std::size_t items_allocated = MyAllocator::items_allocated,
1034            items_freed = MyAllocator::items_freed;
1035     std::size_t allocations = MyAllocator::allocations,
1036            frees = MyAllocator::frees;
1037     REQUIRE(items_allocated == items_freed);
1038     REQUIRE(allocations == frees);
1039 }
1040 
1041 void TestComparison() {
1042     std::string str[3];
1043     str[0] = "abc";
1044     str[1].assign("cba");
1045     str[2].assign("abc"); // same as 0th
1046     oneapi::tbb::concurrent_vector<char> var[3];
1047     var[0].assign(str[0].begin(), str[0].end());
1048     var[1].assign(str[0].rbegin(), str[0].rend());
1049     var[2].assign(var[1].rbegin(), var[1].rend()); // same as 0th
1050     for (int i = 0; i < 3; ++i) {
1051         for (int j = 0; j < 3; ++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             REQUIRE( (var[i] <= var[j]) == (str[i] <= str[j]) );
1057             REQUIRE( (var[i] >= var[j]) == (str[i] >= str[j]) );
1058         }
1059     }
1060 }
1061 
1062 #if TBB_USE_EXCEPTIONS
1063 void test_ex_move_assignment_memory_failure() {
1064     using fixture_type = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type, /*POCMA = */std::false_type>::type;
1065     using arena_allocator_fixture_type = move_support_tests::ArenaAllocatorFixture<move_support_tests::FooWithAssign, /*POCMA = */std::false_type>;
1066     using allocator_type = fixture_type::allocator_type;
1067     using vector_type = fixture_type::container_type;
1068 
1069     fixture_type fixture;
1070     arena_allocator_fixture_type arena_allocator_fixture(4 * fixture.container_size);
1071 
1072     const std::size_t allocation_limit = fixture.container_size/4;
1073 
1074     vector_type victim(arena_allocator_fixture.allocator);
1075     victim.reserve(2); // for fragmented assignment
1076 
1077     REQUIRE_THROWS_AS(
1078         [&]() {
1079             move_support_tests::LimitAllocatedItemsInScope<allocator_type> allocator_limit(allocator_type::items_allocated + allocation_limit);
1080             victim = std::move(fixture.source); // fragmented assignment
1081         }(),
1082         std::bad_alloc
1083     );
1084 
1085     verify_c_vector_size(victim);
1086     verify_c_vector_capacity_is_below(victim.capacity(), allocation_limit + 2);
1087     fixture.verify_part_of_content_deep_moved(victim, victim.size());
1088 
1089     verify_last_segment_allocation_failed(victim);
1090     verify_copy_and_assign_from_produce_the_same(victim);
1091     verify_assignment_operator_throws_bad_last_alloc(victim);
1092 }
1093 
1094 void test_ex_move_assignment_element_ctor_exception(){
1095     using fixture_type = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type, std::false_type>::type;
1096     using arena_allocator_fixture_type = move_support_tests::ArenaAllocatorFixture<move_support_tests::FooWithAssign, std::false_type>;
1097     using vector_type = fixture_type::container_type;
1098 
1099     fixture_type fixture;
1100     const size_t planned_victim_size = fixture.container_size/4;
1101     arena_allocator_fixture_type arena_allocator_fixture(4 * fixture.container_size);
1102 
1103     vector_type victim(arena_allocator_fixture.allocator);
1104     victim.reserve(2); // get fragmented assignment
1105 
1106     REQUIRE_THROWS_AS(
1107         [&](){
1108             move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + planned_victim_size);
1109             victim = std::move(fixture.source); // fragmented assignment
1110         }(),
1111         std::bad_alloc
1112     );
1113 
1114     verify_c_vector_size(victim);
1115 
1116     fixture.verify_part_of_content_deep_moved(victim, planned_victim_size);
1117 
1118     verify_last_segment_allocation_failed(victim);
1119     verify_copy_and_assign_from_produce_the_same(victim);
1120     verify_assignment_operator_throws_bad_last_alloc(victim);
1121 }
1122 
1123 void test_ex_move_assignment() {
1124     test_ex_move_assignment_memory_failure();
1125     test_ex_move_assignment_element_ctor_exception();
1126 }
1127 #endif
1128 
1129 template <typename Type, typename Allocator>
1130 class test_grow_by_and_resize {
1131     oneapi::tbb::concurrent_vector<Type, Allocator> &my_c;
1132 public:
1133     test_grow_by_and_resize( oneapi::tbb::concurrent_vector<Type, Allocator> &c ) : my_c(c) {}
1134     void operator()() const {
1135         const typename oneapi::tbb::concurrent_vector<Type, Allocator>::size_type sz = my_c.size();
1136         my_c.grow_by( 5 );
1137         REQUIRE( my_c.size() == sz + 5 );
1138         my_c.resize( sz );
1139         REQUIRE( my_c.size() == sz );
1140     }
1141 };
1142 
1143 namespace push_back_exception_safety_helpers {
1144     //TODO: remove code duplication with emplace_helpers::wrapper_type
1145     struct throwing_foo:move_support_tests::Foo {
1146         int value1;
1147         int value2;
1148         explicit throwing_foo(int v1, int v2) : value1 (v1), value2(v2) {}
1149     };
1150 
1151     template< typename foo_t = throwing_foo>
1152     struct fixture {
1153         using vector_t = oneapi::tbb::concurrent_vector<foo_t, std::allocator<foo_t> >;
1154         vector_t v;
1155 
1156         void test( void(*p_test)(vector_t&)){
1157             utils::suppress_unused_warning(p_test);
1158             move_support_tests::track_foo_count<__LINE__> verify_no_foo_leaked_during_exception{};
1159             utils::suppress_unused_warning(verify_no_foo_leaked_during_exception);
1160             REQUIRE_MESSAGE(v.empty(),"incorrect test setup?" );
1161             REQUIRE_THROWS_AS(p_test(v), move_support_tests::FooException);
1162             REQUIRE_MESSAGE(is_state<move_support_tests::Foo::ZeroInitialized>(v[0]),"incorrectly filled item during exception in emplace_back?");
1163         }
1164     };
1165 }
1166 
1167 void TestPushBackMoveExceptionSafety() {
1168     using fixture_t = push_back_exception_safety_helpers::fixture<move_support_tests::Foo>;
1169     fixture_t t;
1170 
1171     move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + 1);
1172 
1173     struct test {
1174         static void test_move_push_back(fixture_t::vector_t& v) {
1175             move_support_tests::Foo f;
1176             v.push_back(std::move(f));
1177         }
1178     };
1179     t.test(&test::test_move_push_back);
1180 }
1181 
1182 void TestEmplaceBackExceptionSafety(){
1183     using fixture_t = push_back_exception_safety_helpers::fixture<>;
1184     fixture_t t;
1185 
1186     move_support_tests::Foo dummy; //make FooCount non zero;
1187     utils::suppress_unused_warning(dummy);
1188     move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count);
1189 
1190     struct test {
1191         static void test_emplace(fixture_t::vector_t& v) {
1192             v.emplace_back(1,2);
1193         }
1194     };
1195     t.test(&test::test_emplace);
1196 }
1197 
1198 namespace move_semantics_helpers {
1199     struct move_only_type {
1200         const int* my_pointer;
1201         move_only_type(move_only_type && other): my_pointer(other.my_pointer){other.my_pointer=nullptr;}
1202         explicit move_only_type(const int* value): my_pointer(value) {}
1203     };
1204 }
1205 
1206 void TestPushBackMoveOnlyContainer(){
1207     using namespace move_semantics_helpers;
1208     using vector_t = oneapi::tbb::concurrent_vector<move_only_type >;
1209     vector_t v;
1210     static const int magic_number = 7;
1211     move_only_type src(&magic_number);
1212     v.push_back(std::move(src));
1213     REQUIRE_MESSAGE((v[0].my_pointer == &magic_number),"item was incorrectly moved during push_back?");
1214     REQUIRE_MESSAGE(src.my_pointer == nullptr,"item was incorrectly moved during push_back?");
1215 }
1216 
1217 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1218 template <template <typename...> typename TVector>
1219 void TestDeductionGuides() {
1220     using ComplexType = const std::string*;
1221     std::vector<ComplexType> v;
1222     std::string s = "s";
1223     auto l = {ComplexType(&s), ComplexType(&s)};
1224 
1225     // check TVector(InputIterator, InputIterator)
1226     TVector v1(v.begin(), v.end());
1227     static_assert(std::is_same<decltype(v1), TVector<ComplexType>>::value);
1228 
1229     // check TVector(InputIterator, InputIterator, Alocator)
1230     TVector v2(v.begin(), v.end(), std::allocator<ComplexType>());
1231     static_assert(std::is_same<decltype(v2),
1232        TVector<ComplexType, std::allocator<ComplexType>>>::value);
1233 
1234     // check TVector(std::initializer_list<T>)
1235     TVector v3(l);
1236     static_assert(std::is_same<decltype(v3),
1237         TVector<ComplexType>>::value);
1238 
1239     // check TVector(std::initializer_list, Alocator)
1240     TVector v4(l, std::allocator<ComplexType>());
1241     static_assert(std::is_same<decltype(v4), TVector<ComplexType, std::allocator<ComplexType>>>::value);
1242 
1243     // check TVector(TVector&)
1244     TVector v5(v1);
1245     static_assert(std::is_same<decltype(v5), TVector<ComplexType>>::value);
1246 
1247     // check TVector(TVector&, Allocator)
1248     TVector v6(v5, oneapi::tbb::cache_aligned_allocator<ComplexType>());
1249     static_assert(std::is_same<decltype(v6), TVector<ComplexType, oneapi::tbb::cache_aligned_allocator<ComplexType>>>::value);
1250 
1251     // check TVector(TVector&&)
1252     TVector v7(std::move(v1));
1253     static_assert(std::is_same<decltype(v7), decltype(v1)>::value);
1254 
1255     // check TVector(TVector&&, Allocator)
1256     TVector v8(std::move(v5), oneapi::tbb::cache_aligned_allocator<ComplexType>());
1257     static_assert(std::is_same<decltype(v8), TVector<ComplexType, oneapi::tbb::cache_aligned_allocator<ComplexType>>>::value);
1258 
1259 }
1260 #endif
1261 
1262 template <template <typename... > class ContainerType>
1263 void test_member_types() {
1264     using default_container_type = ContainerType<int>;
1265 
1266     static_assert(std::is_same<typename default_container_type::allocator_type,
1267                                oneapi::tbb::cache_aligned_allocator<int>>::value,
1268                   "Incorrect default template allocator");
1269 
1270 
1271     using test_allocator_type = oneapi::tbb::cache_aligned_allocator<int>;
1272     using container_type = ContainerType<int, test_allocator_type>;
1273 
1274     static_assert(std::is_same<typename container_type::value_type, int>::value,
1275                   "Incorrect container value_type member type");
1276 
1277     static_assert(std::is_unsigned<typename container_type::size_type>::value,
1278                   "Incorrect container size_type member type");
1279     static_assert(std::is_signed<typename container_type::difference_type>::value,
1280                   "Incorrect container difference_type member type");
1281 
1282     using value_type = typename container_type::value_type;
1283     static_assert(std::is_same<typename container_type::reference, value_type&>::value,
1284                   "Incorrect container reference member type");
1285     static_assert(std::is_same<typename container_type::const_reference, const value_type&>::value,
1286                   "Incorrect container const_reference member type");
1287     using allocator_type = typename container_type::allocator_type;
1288     static_assert(std::is_same<typename container_type::pointer, typename std::allocator_traits<allocator_type>::pointer>::value,
1289                   "Incorrect container pointer member type");
1290     static_assert(std::is_same<typename container_type::const_pointer, typename std::allocator_traits<allocator_type>::const_pointer>::value,
1291                   "Incorrect container const_pointer member type");
1292 
1293     static_assert(utils::is_random_access_iterator<typename container_type::iterator>::value,
1294                   "Incorrect container iterator member type");
1295     static_assert(!std::is_const<typename container_type::iterator::value_type>::value,
1296                   "Incorrect container iterator member type");
1297     static_assert(utils::is_random_access_iterator<typename container_type::const_iterator>::value,
1298                   "Incorrect container const_iterator member type");
1299     static_assert(std::is_const<typename container_type::const_iterator::value_type>::value,
1300                   "Incorrect container iterator member type");
1301 }
1302 
1303 void TestConcurrentGrowToAtLeast() {
1304     TestConcurrentGrowToAtLeastImpl<false>();
1305     TestConcurrentGrowToAtLeastImpl<true>();
1306 }
1307 
1308 template <typename Vector>
1309 void test_comparisons_basic() {
1310     using comparisons_testing::testEqualityAndLessComparisons;
1311     Vector v1, v2;
1312     testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(v1, v2);
1313 
1314     v1.emplace_back(1);
1315     testEqualityAndLessComparisons</*ExpectEqual = */false, /*ExpectLess = */false>(v1, v2);
1316 
1317     v2.emplace_back(1);
1318     testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(v1, v2);
1319 
1320     v2.emplace_back(2);
1321     testEqualityAndLessComparisons</*ExpectEqual = */false, /*ExpectLess = */true>(v1, v2);
1322 
1323     v1.clear();
1324     v2.clear();
1325     testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(v1, v2);
1326 }
1327 
1328 template <typename TwoWayComparableVectorType>
1329 void test_two_way_comparable_vector() {
1330     TwoWayComparableVectorType v1, v2;
1331     v1.emplace_back(1);
1332     v2.emplace_back(1);
1333     comparisons_testing::TwoWayComparable::reset();
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     REQUIRE_MESSAGE(v1 >= v2, "Incorrect operator >= result");
1341     comparisons_testing::check_two_way_comparison();
1342 }
1343 
1344 #if __TBB_TEST_CPP20_COMPARISONS
1345 template <typename ThreeWayComparableVectorType>
1346 void test_three_way_comparable_vector() {
1347     ThreeWayComparableVectorType v1, v2;
1348     v1.emplace_back(1);
1349     v2.emplace_back(1);
1350     comparisons_testing::ThreeWayComparable::reset();
1351     REQUIRE_MESSAGE(!(v1 <=> v2 < 0), "Incorrect operator<=> result");
1352     comparisons_testing::check_three_way_comparison();
1353 
1354     REQUIRE_MESSAGE(!(v1 < v2), "Incorrect operator< result");
1355     comparisons_testing::check_three_way_comparison();
1356 
1357     REQUIRE_MESSAGE(!(v1 > v2), "Incorrect operator> result");
1358     comparisons_testing::check_three_way_comparison();
1359 
1360     REQUIRE_MESSAGE(v1 <= v2, "Incorrect operator>= result");
1361     comparisons_testing::check_three_way_comparison();
1362 
1363     REQUIRE_MESSAGE(v1 >= v2, "Incorrect operator>= result");
1364     comparisons_testing::check_three_way_comparison();
1365 }
1366 #endif // __TBB_TEST_CPP20_COMPARISONS
1367 
1368 void TestVectorComparisons() {
1369     using integral_vector = oneapi::tbb::concurrent_vector<int>;
1370     using two_way_comparable_vector = oneapi::tbb::concurrent_vector<comparisons_testing::TwoWayComparable>;
1371 
1372     test_comparisons_basic<integral_vector>();
1373     test_comparisons_basic<two_way_comparable_vector>();
1374     test_two_way_comparable_vector<two_way_comparable_vector>();
1375 
1376 #if __TBB_TEST_CPP20_COMPARISONS
1377     using two_way_less_only_vector = oneapi::tbb::concurrent_vector<comparisons_testing::LessComparableOnly>;
1378     using three_way_only_vector = oneapi::tbb::concurrent_vector<comparisons_testing::ThreeWayComparableOnly>;
1379     using three_way_comparable_vector = oneapi::tbb::concurrent_vector<comparisons_testing::ThreeWayComparable>;
1380 
1381     test_comparisons_basic<two_way_less_only_vector>();
1382     test_comparisons_basic<three_way_only_vector>();
1383     test_comparisons_basic<three_way_comparable_vector>();
1384     test_three_way_comparable_vector<three_way_comparable_vector>();
1385 #endif // __TBB_CPP20_COMPARISONS_PRESENT && __TBB_CPP20_CONVEPTS_PRESENT
1386 }
1387 
1388 template <bool ExpectEqual, bool ExpectLess, typename Iterator>
1389 void DoVectorIteratorComparisons( const Iterator& lhs, const Iterator& rhs ) {
1390     // TODO: replace with testEqualityAndLessComparisons after adding <=> operator for concurrent_vector iterator
1391     using namespace comparisons_testing;
1392     testEqualityComparisons<ExpectEqual>(lhs, rhs);
1393     testTwoWayComparisons<ExpectEqual, ExpectLess>(lhs, rhs);
1394 }
1395 
1396 template <typename Iterator, typename VectorType>
1397 void TestVectorIteratorComparisonsBasic( VectorType& vec ) {
1398     REQUIRE_MESSAGE(!vec.empty(), "Incorrect test setup");
1399     Iterator it1, it2;
1400     DoVectorIteratorComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(it1, it2);
1401     it1 = vec.begin();
1402     it2 = vec.begin();
1403     DoVectorIteratorComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(it1, it2);
1404     it2 = std::prev(vec.end());
1405     DoVectorIteratorComparisons</*ExpectEqual = */false, /*ExpectLess = */true>(it1, it2);
1406 }
1407 
1408 void TestVectorIteratorComparisons() {
1409     using vector_type = oneapi::tbb::concurrent_vector<int>;
1410     vector_type vec = {1, 2, 3, 4, 5};
1411     TestVectorIteratorComparisonsBasic<typename vector_type::iterator>(vec);
1412     const vector_type& cvec = vec;
1413     TestVectorIteratorComparisonsBasic<typename vector_type::const_iterator>(cvec);
1414 }
1415 
1416 //! Test type matching
1417 //! \brief \ref interface \ref requirement
1418 TEST_CASE("test type matching") {
1419     test_member_types<oneapi::tbb::concurrent_vector>();
1420 }
1421 
1422 //! Test sequential access to elements
1423 //! \brief \ref interface \ref requirement
1424 TEST_CASE("testing sequential for") {
1425     TestSequentialFor<move_support_tests::FooWithAssign> ();
1426 }
1427 
1428 //! Test of assign, grow, copying with various sizes
1429 //! \brief \ref interface \ref requirement
1430 TEST_CASE("testing resize and copy"){
1431     TestResizeAndCopy();
1432 }
1433 
1434 //! Test the assignment operator and swap
1435 //! \brief \ref interface \ref requirement
1436 TEST_CASE("testing copy assignment"){
1437     TestCopyAssignment();
1438 }
1439 
1440 //! Testing grow_to_at_least operations
1441 //! \brief \ref interface
1442 TEST_CASE("testing grow_to_at_least with source parameter"){
1443     TestGrowToAtLeastWithSourceParameter<oneapi::tbb::concurrent_vector<int>>(12345);
1444 }
1445 
1446 //! Test of capacity, reserve, and shrink_to_fit
1447 //! \brief \ref interface \ref requirement
1448 TEST_CASE("testing capacity"){
1449    TestCapacity();
1450 }
1451 
1452 #if TBB_USE_EXCEPTIONS
1453 //! Test exceptions
1454 //! \brief \ref requirement
1455 TEST_CASE("testing exceptions"){
1456     TestExceptions();
1457 }
1458 
1459 //! Test of push_back move exception safety
1460 //! \brief \ref requirement
1461 TEST_CASE("testing push_back move exception safety"){
1462     TestPushBackMoveExceptionSafety();
1463 }
1464 
1465 //! Test of emplace back move exception safety
1466 //! \brief \ref requirement
1467 TEST_CASE("testing emplace back exception safety"){
1468     TestEmplaceBackExceptionSafety();
1469 }
1470 
1471 //! Test exceptions guarantees for assign operator
1472 //! \brief \ref requirement
1473 TEST_CASE("testing exception safety guaranteees for assign operator"){
1474     test_ex_assign_operator();
1475 }
1476 
1477 //! Test exceptions safety guarantees for concurrent_vector move constructor
1478 //! \brief \ref requirement
1479 TEST_CASE("exception safety guarantees for concurrent_vector move constructor") {
1480     move_support_tests::test_ex_move_constructor<c_vector_type>();
1481 }
1482 
1483 //! Test exceptions safety guarantees for concurrent_vector move assignment
1484 //! \brief \ref requirement
1485 TEST_CASE("test exception safety on concurrent_vector move assignment") {
1486     test_ex_move_assignment();
1487 }
1488 #endif
1489 //! Test push_back in move only container
1490 //! \brief \ref requirement
1491 TEST_CASE("testing push_back move only container"){
1492     TestPushBackMoveOnlyContainer();
1493 }
1494 
1495 //! Test types for std::iterator_traits in concurrent_vector::iterator
1496 //! \brief \ref requirement
1497 TEST_CASE("testing std::iterator_traits for concurrent_vector::iterator"){
1498     TestIteratorTraits<oneapi::tbb::concurrent_vector<move_support_tests::Foo>::iterator,move_support_tests::Foo>();
1499 }
1500 
1501 //! Test types for std::iterator_traits in concurrent_vector::const_iterator
1502 //! \brief \ref requirement
1503 TEST_CASE("testing std::iterator_traits for concurrent_vector::const_iterator"){
1504     TestIteratorTraits<oneapi::tbb::concurrent_vector<move_support_tests::Foo>::const_iterator,const move_support_tests::Foo>();
1505 }
1506 
1507 //! Test initializer_list support
1508 //! \brief \ref interface \ref requirement
1509 TEST_CASE("testing initializer_list support"){
1510     TestInitList();
1511 }
1512 
1513 //! Test move constructor
1514 //! \brief \ref interface \ref requirement
1515 TEST_CASE("testing move constructor"){
1516     move_support_tests::test_move_constructor<c_vector_type>();
1517 }
1518 
1519 //! Test move assign operator
1520 //! \brief \ref interface \ref requirement
1521 TEST_CASE("testing move assign operator"){
1522     move_support_tests::test_move_assignment<c_vector_type>();
1523 }
1524 
1525 //! Test constructor with move iterators
1526 //! \brief \ref requirement
1527 TEST_CASE("testing constructor with move iterators"){
1528     move_support_tests::test_constructor_with_move_iterators<c_vector_type>();
1529 }
1530 
1531 //! Test assign with move iterators
1532 //! \brief \ref interface \ref requirement
1533 TEST_CASE("testing assign with move iterators"){
1534     move_support_tests::test_assign_with_move_iterators<c_vector_type>();
1535 }
1536 
1537 //! Test grow_by with move iterator
1538 //! \brief \ref requirement
1539 TEST_CASE("testing serial grow_by with move iterator"){
1540     TestSerialGrowByWithMoveIterators();
1541 }
1542 
1543 //! Test grow_by with move iterator
1544 //! \brief \ref requirement
1545 TEST_CASE("testing serial move in shrink_to_fit"){
1546     TestSerialMoveInShrinkToFit();
1547 }
1548 
1549 //! Test concurrent grow
1550 //! \brief \ref requirement
1551 TEST_CASE("testing concurrency"){
1552     REQUIRE(!move_support_tests::foo_count);
1553     for (std::size_t p = 1; p <= 4; ++p) {
1554         oneapi::tbb::global_control limit(oneapi::tbb::global_control::max_allowed_parallelism, p);
1555         TestParallelFor(p);
1556         TestConcurrentGrowToAtLeast();
1557         TestConcurrentGrowBy();
1558     }
1559 
1560     REQUIRE(!move_support_tests::foo_count);
1561 }
1562 
1563 //! Test assign operations
1564 //! \brief \ref interface \ref requirement
1565 TEST_CASE("testing comparison on assign operations"){
1566     TestComparison();
1567 }
1568 
1569 //! Test allocator_traits support in concurrent_vector
1570 //! \brief \ref requirement
1571 TEST_CASE("test allocator_traits support in concurrent_vector") {
1572     test_allocator_traits_support<c_vector_type>();
1573 }
1574 
1575 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1576 //! Test deduction guides
1577 //! \brief \ref requirement
1578 TEST_CASE("testing deduction guides"){
1579     TestDeductionGuides<oneapi::tbb::concurrent_vector>();
1580 }
1581 #endif
1582 
1583 //! Test concurrent_vector comparisons
1584 //! \brief \ref interface \ref requirement
1585 TEST_CASE("concurrent_vector comparisons") {
1586     TestVectorComparisons();
1587 }
1588 
1589 //! Test concurrent_vector iterators comparisons
1590 //! \brief \ref interface \ref requirement
1591 TEST_CASE("concurrent_vector iterators comparisons") {
1592     TestVectorIteratorComparisons();
1593 }
1594