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 //TODO: split into two separate tests
539 //TODO: remove code duplication in exception safety tests
540 void test_ex_assign_operator(){
541     //TODO: use __FUNCTION__ for test name
542     using allocator_t = StaticCountingAllocator<std::allocator<move_support_tests::FooWithAssign>>;
543     using vector_t = oneapi::tbb::concurrent_vector<move_support_tests::FooWithAssign, allocator_t>;
544 
545     move_support_tests::track_foo_count<__LINE__> check_all_foo_destroyed_on_exit{};
546     move_support_tests::track_allocator_memory<allocator_t> verify_no_leak_at_exit{};
547 
548     vector_t src(move_support_tests::FooIterator(0), move_support_tests::FooIterator(N)); // original data
549 
550     const size_t planned_victim_size = N/4;
551 
552     for(int t = 0; t < 2; ++t) { // exception type
553         vector_t victim;
554         victim.reserve(2); // get fragmented assignment
555         REQUIRE_THROWS_AS([&](){
556             move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + planned_victim_size, t);
557             move_support_tests::LimitAllocatedItemsInScope<allocator_t> allocator_limit(allocator_t::items_allocated + planned_victim_size, !t);
558 
559             victim = src; // fragmented assignment
560         }(), const std::bad_alloc);
561 
562         verify_c_vector_size(victim);
563 
564         if(!t) {
565             verify_c_vector_capacity_is_below(victim.capacity(), N);
566         }
567 
568         verify_vector_partially_copied(victim, planned_victim_size, src, !t);
569         verify_last_segment_allocation_failed(victim);
570         verify_copy_and_assign_from_produce_the_same(victim);
571         verify_assignment_operator_throws_bad_last_alloc(victim); //TODO exceptions support
572     }
573 }
574 
575 template<typename T>
576 void AssertSameType( const T& /*x*/, const T& /*y*/ ) {}
577 
578 struct test_grow_by {
579     template<typename container_type, typename element_type>
580     static void test( std::initializer_list<element_type> const& il, container_type const& expected ) {
581         container_type vd;
582         vd.grow_by( il );
583         REQUIRE_MESSAGE( vd == expected, "grow_by with an initializer list failed" );
584     }
585 };
586 
587 template<typename Iterator, typename T>
588 void TestIteratorTraits() {
589     AssertSameType( static_cast<typename Iterator::difference_type*>(0), static_cast<std::ptrdiff_t*>(0) );
590     AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) );
591     AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) );
592     AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::random_access_iterator_tag*>(0) );
593     T x;
594     typename Iterator::reference xr = x;
595     typename Iterator::pointer xp = &x;
596     REQUIRE( &xr==xp );
597 }
598 
599 void TestInitList() {
600     using namespace initializer_list_support_tests;
601     test_initializer_list_support<oneapi::tbb::concurrent_vector<char>, test_grow_by>( { 1, 2, 3, 4, 5 } );
602     test_initializer_list_support<oneapi::tbb::concurrent_vector<int>, test_grow_by>( {} );
603 }
604 
605 namespace TestMoveInShrinkToFitHelpers {
606     struct dummy : StateTrackable<>{
607         int i;
608         dummy(int an_i) noexcept : StateTrackable<>(0), i(an_i) {}
609 
610         friend bool operator== (const dummy &lhs, const dummy &rhs){ return lhs.i == rhs.i; }
611     };
612 }
613 
614 void TestSerialMoveInShrinkToFit(){
615     using TestMoveInShrinkToFitHelpers::dummy;
616 
617     static_assert(std::is_nothrow_move_constructible<dummy>::value,"incorrect test setup or broken configuration?");
618     {
619         dummy src(0);
620         REQUIRE_MESSAGE(is_state<StateTrackableBase::MoveInitialized>(dummy(std::move_if_noexcept(src))),"broken configuration ?");
621     }
622     static const std::size_t sequence_size = 15;
623     using c_vector_t = oneapi::tbb::concurrent_vector<dummy>;
624     std::vector<dummy> source(sequence_size, 0);
625     std::generate_n(source.begin(), source.size(), std::rand);
626 
627     c_vector_t c_vector;
628     c_vector.reserve(1); //make it fragmented
629 
630     c_vector.assign(source.begin(), source.end());
631     move_support_tests::MemoryLocations c_vector_before_shrink(c_vector);
632     c_vector.shrink_to_fit();
633 
634     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");
635     REQUIRE_MESSAGE((std::all_of(c_vector.begin(), c_vector.end(), is_state_predicate<StateTrackableBase::MoveInitialized>())), "container did not move construct some elements?");
636     REQUIRE((c_vector == c_vector_t(source.begin(),source.end())));
637 }
638 
639 struct default_container_traits {
640     template <typename container_type, typename iterator_type>
641     static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end){
642         container_type* ptr = reinterpret_cast<container_type*>(&storage);
643         new (ptr) container_type(begin, end);
644         return *ptr;
645     }
646 
647     template <typename container_type, typename iterator_type, typename allocator_type>
648     static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end, allocator_type const& a){
649         container_type* ptr = reinterpret_cast<container_type*>(&storage);
650         new (ptr) container_type(begin, end, a);
651         return *ptr;
652     }
653 };
654 
655 struct c_vector_type : default_container_traits {
656     template <typename T, typename Allocator>
657     using container_type = oneapi::tbb::concurrent_vector<T, Allocator>;
658 
659     template <typename T>
660     using container_value_type = T;
661 
662     using init_iterator_type = move_support_tests::FooIterator;
663     template<typename element_type, typename allocator_type>
664     struct apply{
665         using type = oneapi::tbb::concurrent_vector<element_type,  allocator_type >;
666     };
667 
668     enum{ expected_number_of_items_to_allocate_for_steal_move = 0 };
669 
670     template<typename element_type, typename allocator_type, typename iterator>
671     static bool equal(oneapi::tbb::concurrent_vector<element_type, allocator_type > const& c, iterator begin, iterator end){
672         bool equal_sizes = (std::size_t)std::distance(begin, end) == c.size();
673         return  equal_sizes && std::equal(c.begin(), c.end(), begin);
674     }
675 };
676 
677 void TestSerialGrowByWithMoveIterators(){
678     using fixture_t = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type>::type;
679     using vector_t = fixture_t::container_type;
680 
681     fixture_t fixture;
682 
683     vector_t dst(fixture.dst_allocator);
684     dst.grow_by(std::make_move_iterator(fixture.source.begin()), std::make_move_iterator(fixture.source.end()));
685 
686     fixture.verify_content_deep_moved(dst);
687 }
688 
689 namespace test_grow_to_at_least_helpers {
690     template<typename MyVector >
691     class GrowToAtLeast {
692         using const_reference = typename MyVector::const_reference;
693 
694         const bool my_use_two_args_form ;
695         MyVector& my_vector;
696         const_reference my_init_from;
697     public:
698         void operator()( const oneapi::tbb::blocked_range<std::size_t>& range ) const {
699             for( std::size_t i=range.begin(); i!=range.end(); ++i ) {
700                 std::size_t n = my_vector.size();
701                 std::size_t req = (i % (2*n+1))+1;
702 
703                 typename MyVector::iterator p;
704                 move_support_tests::Foo::State desired_state;
705                 if (my_use_two_args_form){
706                     p = my_vector.grow_to_at_least(req,my_init_from);
707                     desired_state = move_support_tests::Foo::CopyInitialized;
708                 }else{
709                     p = my_vector.grow_to_at_least(req);
710                     desired_state = move_support_tests::Foo::DefaultInitialized;
711                 }
712                 if( p-my_vector.begin() < typename MyVector::difference_type(req) )
713                     CHECK((p->state == desired_state || p->state == move_support_tests::Foo::ZeroInitialized));
714                 CHECK(my_vector.size() >= req);
715             }
716         }
717         GrowToAtLeast(bool use_two_args_form, MyVector& vector, const_reference init_from )
718             : my_use_two_args_form(use_two_args_form), my_vector(vector), my_init_from(init_from) {}
719     };
720 }
721 
722 template<bool use_two_arg_form>
723 void TestConcurrentGrowToAtLeastImpl() {
724     using namespace test_grow_to_at_least_helpers;
725     using MyAllocator = StaticCountingAllocator<std::allocator<move_support_tests::Foo>>;
726     using MyVector = oneapi::tbb::concurrent_vector<move_support_tests::Foo, MyAllocator>;
727     move_support_tests::Foo copy_from;
728     MyAllocator::init_counters();
729     MyVector v(2, move_support_tests::Foo(), MyAllocator());
730     for (std::size_t s=1; s<1000; s*=10) {
731         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());
732     }
733 
734     v.clear();
735     v.shrink_to_fit();
736     std::size_t items_allocated = v.get_allocator().items_allocated,
737            items_freed = v.get_allocator().items_freed;
738     std::size_t allocations = v.get_allocator().allocations,
739            frees = v.get_allocator().frees;
740     REQUIRE( items_allocated == items_freed );
741     REQUIRE( allocations == frees );
742 }
743 
744 struct AssignElement {
745     using iterator = oneapi::tbb::concurrent_vector<int>::range_type::iterator;
746     iterator base;
747     void operator()( const oneapi::tbb::concurrent_vector<int>::range_type& range ) const {
748         for (iterator i = range.begin(); i != range.end(); ++i) {
749             if (*i != 0) {
750                 REPORT("ERROR for v[%ld]\n", long(i - base));
751             }
752             *i = int(i-base);
753         }
754     }
755     AssignElement( iterator base_ ) : base(base_) {}
756 };
757 
758 struct CheckElement {
759     using iterator = oneapi::tbb::concurrent_vector<int>::const_range_type::iterator;
760     iterator base;
761     void operator()( const oneapi::tbb::concurrent_vector<int>::const_range_type& range ) const {
762         for (iterator i = range.begin(); i != range.end(); ++i) {
763             if (*i != int(i-base)) {
764                 REPORT("ERROR for v[%ld]\n", long(i-base));
765             }
766         }
767     }
768     CheckElement( iterator base_ ) : base(base_) {}
769 };
770 
771 // Test parallel access by iterators
772 void TestParallelFor( std::size_t nthread ) {
773     using vector_type = oneapi::tbb::concurrent_vector<int>;
774     vector_type v;
775     v.resize(N);
776     oneapi::tbb::tick_count t0 = oneapi::tbb::tick_count::now();
777     INFO("Calling parallel_for with " << nthread << " threads");
778     oneapi::tbb::parallel_for(v.range(10000), AssignElement(v.begin()));
779     oneapi::tbb::tick_count t1 = oneapi::tbb::tick_count::now();
780     const vector_type& u = v;
781     oneapi::tbb::parallel_for(u.range(10000), CheckElement(u.begin()));
782     oneapi::tbb::tick_count t2 = oneapi::tbb::tick_count::now();
783     INFO("Time for parallel_for: assign time = " << (t1 - t0).seconds() <<
784         " , check time = " << (t2 - t1).seconds());
785     for (int i = 0; std::size_t(i) < v.size(); ++i) {
786         if (v[i] != i) {
787             REPORT("ERROR for v[%ld]\n", i);
788         }
789     }
790 }
791 
792 
793 struct grain_map {
794     enum grow_method_enum {
795         grow_by_range = 1,
796         grow_by_default,
797         grow_by_copy,
798         grow_by_init_list,
799         push_back,
800         push_back_move,
801         emplace_back,
802         last_method
803     };
804 
805     struct range_part {
806         std::size_t number_of_parts;
807         grain_map::grow_method_enum method;
808         bool distribute;
809         move_support_tests::Foo::State expected_element_state;
810     };
811 
812     const std::vector<range_part> distributed;
813     const std::vector<range_part> batched;
814     const std::size_t total_number_of_parts;
815 
816     grain_map(const range_part* begin, const range_part* end)
817     : distributed(separate(begin,end, &distributed::is_not))
818     , batched(separate(begin,end, &distributed::is_yes))
819     , total_number_of_parts(std::accumulate(begin, end, (std::size_t)0, &sum_number_of_parts::sum))
820     {}
821 
822 private:
823     struct sum_number_of_parts{
824         static std::size_t sum(std::size_t accumulator, grain_map::range_part const& rp){ return accumulator + rp.number_of_parts;}
825     };
826 
827     template <typename functor_t>
828     static std::vector<range_part> separate(const range_part* begin, const range_part* end, functor_t f){
829         std::vector<range_part> part;
830         part.reserve(std::distance(begin,end));
831         //copy all that false==f(*it)
832         std::remove_copy_if(begin, end, std::back_inserter(part), f);
833 
834         return part;
835     }
836 
837     struct distributed {
838         static bool is_not(range_part const& rp){ return !rp.distribute;}
839         static bool is_yes(range_part const& rp){ return rp.distribute;}
840     };
841 };
842 
843 
844 //! Test concurrent invocations of method concurrent_vector::grow_by
845 template<typename MyVector>
846 class GrowBy {
847     MyVector& my_vector;
848     const grain_map& my_grain_map;
849     std::size_t my_part_weight;
850 public:
851     void operator()( const oneapi::tbb::blocked_range<std::size_t>& range ) const {
852         CHECK(range.begin() < range.end());
853 
854         std::size_t current_adding_index_in_cvector = range.begin();
855 
856         for (std::size_t index = 0; index < my_grain_map.batched.size(); ++index){
857             const grain_map::range_part& batch_part = my_grain_map.batched[index];
858             const std::size_t number_of_items_to_add = batch_part.number_of_parts * my_part_weight;
859             const std::size_t end = current_adding_index_in_cvector + number_of_items_to_add;
860 
861             switch(batch_part.method){
862             case grain_map::grow_by_range : {
863                     my_vector.grow_by(move_support_tests::FooIterator(current_adding_index_in_cvector), move_support_tests::FooIterator(end));
864                 } break;
865             case grain_map::grow_by_default : {
866                     typename MyVector::iterator const s = my_vector.grow_by(number_of_items_to_add);
867                     for (std::size_t k = 0; k < number_of_items_to_add; ++k) {
868                         s[k].bar() = current_adding_index_in_cvector + k;
869                     }
870                 } break;
871             case grain_map::grow_by_init_list : {
872                     move_support_tests::FooIterator curr(current_adding_index_in_cvector);
873                     for (std::size_t k = 0; k < number_of_items_to_add; ++k) {
874                         if (k + 4 < number_of_items_to_add) {
875                             my_vector.grow_by( { *curr++, *curr++, *curr++, *curr++, *curr++ } );
876                             k += 4;
877                         } else {
878                             my_vector.grow_by( { *curr++ } );
879                         }
880                     }
881                     CHECK(curr == move_support_tests::FooIterator(end));
882                 } break;
883             default : { REQUIRE_MESSAGE(false, "using unimplemented method of batch add in ConcurrentGrow test.");} break;
884             };
885 
886             current_adding_index_in_cvector = end;
887         }
888 
889         std::vector<std::size_t> items_left_to_add(my_grain_map.distributed.size());
890         for (std::size_t i=0; i < my_grain_map.distributed.size(); ++i) {
891             items_left_to_add[i] = my_grain_map.distributed[i].number_of_parts * my_part_weight;
892         }
893 
894         for (;current_adding_index_in_cvector < range.end(); ++current_adding_index_in_cvector) {
895             std::size_t method_index = current_adding_index_in_cvector % my_grain_map.distributed.size();
896 
897             if (!items_left_to_add[method_index]) {
898                 struct not_zero{
899                     static bool is(std::size_t items_to_add){ return items_to_add;}
900                 };
901                 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));
902                 REQUIRE_MESSAGE(method_index < my_grain_map.distributed.size(), "incorrect test setup - wrong expected distribution: left free space but no elements to add?");
903             };
904 
905             REQUIRE_MESSAGE(items_left_to_add[method_index], "logic error ?");
906             const grain_map::range_part& distributed_part = my_grain_map.distributed[method_index];
907 
908             typename MyVector::iterator r;
909             typename MyVector::value_type source;
910             source.bar() = current_adding_index_in_cvector;
911 
912             switch(distributed_part.method){
913             case grain_map::grow_by_default : {
914                     (r = my_vector.grow_by(1))->bar() = current_adding_index_in_cvector;
915                 } break;
916             case grain_map::grow_by_copy : {
917                     r = my_vector.grow_by(1, source);
918                 } break;
919             case grain_map::push_back : {
920                     r = my_vector.push_back(source);
921                 } break;
922             case grain_map::push_back_move : {
923                     r = my_vector.push_back(std::move(source));
924                 } break;
925             case grain_map::emplace_back : {
926                     r = my_vector.emplace_back(current_adding_index_in_cvector);
927                 } break;
928 
929             default : { REQUIRE_MESSAGE(false, "using unimplemented method of batch add in ConcurrentGrow test.");} break;
930             };
931 
932             CHECK(static_cast<std::size_t>(r->bar()) == current_adding_index_in_cvector);
933             }
934 
935         }
936 
937     GrowBy( MyVector& vector, const grain_map& m, std::size_t part_weight )
938     : my_vector(vector), my_grain_map(m), my_part_weight(part_weight)
939     {}
940 };
941 
942 //! Test concurrent invocations of grow methods
943 void TestConcurrentGrowBy() {
944 
945     const grain_map::range_part concurrent_grow_single_range_map [] = {
946     //  number_of_parts,         method,             distribute,   expected_element_state
947             {3,           grain_map::grow_by_range,     false,   move_support_tests::Foo::MoveInitialized},
948 
949             {1,           grain_map::grow_by_init_list, false,   move_support_tests::Foo::CopyInitialized},
950 
951             {2,           grain_map::grow_by_default,   false,   move_support_tests::Foo::DefaultInitialized},
952             {1,           grain_map::grow_by_default,   true,    move_support_tests::Foo::DefaultInitialized},
953             {1,           grain_map::grow_by_copy,      true,    move_support_tests::Foo::CopyInitialized},
954             {1,           grain_map::push_back,         true,    move_support_tests::Foo::CopyInitialized},
955 
956             {1,           grain_map::push_back_move,    true,    move_support_tests::Foo::MoveInitialized},
957 
958             {1,           grain_map::emplace_back,      true,    move_support_tests::Foo::DirectInitialized},
959 
960     };
961 
962     using MyAllocator = StaticCountingAllocator<std::allocator<move_support_tests::Foo> >;
963     using MyVector = oneapi::tbb::concurrent_vector<move_support_tests::Foo, MyAllocator>;
964 
965     MyAllocator::init_counters();
966     {
967         grain_map m(concurrent_grow_single_range_map, end(concurrent_grow_single_range_map));
968 
969         static const std::size_t desired_grain_size = 100;
970 
971         static const std::size_t part_weight = desired_grain_size / m.total_number_of_parts;
972         static const std::size_t grain_size = part_weight * m.total_number_of_parts;
973         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
974         static const std::size_t range_size = grain_size * number_of_grains;
975 
976         MyAllocator a;
977         MyVector v(a);
978         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());
979 
980         REQUIRE( v.size() == std::size_t(range_size) );
981 
982         // Verify that v is a permutation of 0..m
983         size_t inversions = 0, direct_inits = 0, def_inits = 0, copy_inits = 0, move_inits = 0;
984         std::vector<bool> found(range_size, 0);
985         for( std::size_t i=0; i<range_size; ++i ) {
986             if( v[i].state == move_support_tests::Foo::DefaultInitialized ) ++def_inits;
987             else if( v[i].state == move_support_tests::Foo::DirectInitialized ) ++direct_inits;
988             else if( v[i].state == move_support_tests::Foo::CopyInitialized ) ++copy_inits;
989             else if( v[i].state == move_support_tests::Foo::MoveInitialized ) ++move_inits;
990             else {
991                 REQUIRE_MESSAGE( false, "v[i] seems not initialized");
992             }
993             intptr_t index = v[i].bar();
994             REQUIRE( !found[index] );
995             found[index] = true;
996             if( i>0 )
997                 inversions += v[i].bar()<v[i-1].bar();
998         }
999 
1000         std::size_t expected_direct_inits = 0, expected_def_inits = 0, expected_copy_inits = 0, expected_move_inits = 0;
1001         for (std::size_t i=0; i < utils::array_length(concurrent_grow_single_range_map); ++i){
1002             const grain_map::range_part& rp =concurrent_grow_single_range_map[i];
1003             switch (rp.expected_element_state){
1004             case move_support_tests::Foo::DefaultInitialized: { expected_def_inits += rp.number_of_parts ; } break;
1005             case move_support_tests::Foo::DirectInitialized:  { expected_direct_inits += rp.number_of_parts ;} break;
1006             case move_support_tests::Foo::MoveInitialized:    { expected_move_inits += rp.number_of_parts ;} break;
1007             case move_support_tests::Foo::CopyInitialized:    { expected_copy_inits += rp.number_of_parts ;} break;
1008             default: {REQUIRE_MESSAGE(false, "unexpected expected state");}break;
1009             };
1010         }
1011 
1012         expected_def_inits    *= part_weight * number_of_grains;
1013         expected_move_inits   *= part_weight * number_of_grains;
1014         expected_copy_inits   *= part_weight * number_of_grains;
1015         expected_direct_inits *= part_weight * number_of_grains;
1016 
1017         REQUIRE( def_inits == expected_def_inits );
1018         REQUIRE( copy_inits == expected_copy_inits );
1019         REQUIRE( move_inits == expected_move_inits );
1020         REQUIRE( direct_inits == expected_direct_inits );
1021     }
1022     //TODO: factor this into separate thing, as it seems to used in big number of tests
1023     std::size_t items_allocated = MyAllocator::items_allocated,
1024            items_freed = MyAllocator::items_freed;
1025     std::size_t allocations = MyAllocator::allocations,
1026            frees = MyAllocator::frees;
1027     REQUIRE(items_allocated == items_freed);
1028     REQUIRE(allocations == frees);
1029 }
1030 
1031 void TestComparison() {
1032     std::string str[3];
1033     str[0] = "abc";
1034     str[1].assign("cba");
1035     str[2].assign("abc"); // same as 0th
1036     oneapi::tbb::concurrent_vector<char> var[3];
1037     var[0].assign(str[0].begin(), str[0].end());
1038     var[1].assign(str[0].rbegin(), str[0].rend());
1039     var[2].assign(var[1].rbegin(), var[1].rend()); // same as 0th
1040     for (int i = 0; i < 3; ++i) {
1041         for (int j = 0; j < 3; ++j) {
1042             REQUIRE( (var[i] == var[j]) == (str[i] == str[j]) );
1043             REQUIRE( (var[i] != var[j]) == (str[i] != str[j]) );
1044             REQUIRE( (var[i] < var[j]) == (str[i] < str[j]) );
1045             REQUIRE( (var[i] > var[j]) == (str[i] > str[j]) );
1046             REQUIRE( (var[i] <= var[j]) == (str[i] <= str[j]) );
1047             REQUIRE( (var[i] >= var[j]) == (str[i] >= str[j]) );
1048         }
1049     }
1050 }
1051 
1052 #if TBB_USE_EXCEPTIONS
1053 void test_ex_move_assignment_memory_failure() {
1054     using fixture_type = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type, /*POCMA = */std::false_type>::type;
1055     using arena_allocator_fixture_type = move_support_tests::ArenaAllocatorFixture<move_support_tests::FooWithAssign, /*POCMA = */std::false_type>;
1056     using allocator_type = fixture_type::allocator_type;
1057     using vector_type = fixture_type::container_type;
1058 
1059     fixture_type fixture;
1060     arena_allocator_fixture_type arena_allocator_fixture(4 * fixture.container_size);
1061 
1062     const std::size_t allocation_limit = fixture.container_size/4;
1063 
1064     vector_type victim(arena_allocator_fixture.allocator);
1065     victim.reserve(2); // for fragmented assignment
1066 
1067     REQUIRE_THROWS_AS(
1068         [&]() {
1069             move_support_tests::LimitAllocatedItemsInScope<allocator_type> allocator_limit(allocator_type::items_allocated + allocation_limit);
1070             victim = std::move(fixture.source); // fragmented assignment
1071         }(),
1072         std::bad_alloc
1073     );
1074 
1075     verify_c_vector_size(victim);
1076     verify_c_vector_capacity_is_below(victim.capacity(), allocation_limit + 2);
1077     fixture.verify_part_of_content_deep_moved(victim, victim.size());
1078 
1079     verify_last_segment_allocation_failed(victim);
1080     verify_copy_and_assign_from_produce_the_same(victim);
1081     verify_assignment_operator_throws_bad_last_alloc(victim);
1082 }
1083 
1084 void test_ex_move_assignment_element_ctor_exception(){
1085     using fixture_type = move_support_tests::DefaultStatefulFixtureHelper<c_vector_type, std::false_type>::type;
1086     using arena_allocator_fixture_type = move_support_tests::ArenaAllocatorFixture<move_support_tests::FooWithAssign, std::false_type>;
1087     using vector_type = fixture_type::container_type;
1088 
1089     fixture_type fixture;
1090     const size_t planned_victim_size = fixture.container_size/4;
1091     arena_allocator_fixture_type arena_allocator_fixture(4 * fixture.container_size);
1092 
1093     vector_type victim(arena_allocator_fixture.allocator);
1094     victim.reserve(2); // get fragmented assignment
1095 
1096     REQUIRE_THROWS_AS(
1097         [&](){
1098             move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + planned_victim_size);
1099             victim = std::move(fixture.source); // fragmented assignment
1100         }(),
1101         std::bad_alloc
1102     );
1103 
1104     verify_c_vector_size(victim);
1105 
1106     fixture.verify_part_of_content_deep_moved(victim, planned_victim_size);
1107 
1108     verify_last_segment_allocation_failed(victim);
1109     verify_copy_and_assign_from_produce_the_same(victim);
1110     verify_assignment_operator_throws_bad_last_alloc(victim);
1111 }
1112 
1113 void test_ex_move_assignment() {
1114     test_ex_move_assignment_memory_failure();
1115     test_ex_move_assignment_element_ctor_exception();
1116 }
1117 #endif
1118 
1119 template <typename Type, typename Allocator>
1120 class test_grow_by_and_resize {
1121     oneapi::tbb::concurrent_vector<Type, Allocator> &my_c;
1122 public:
1123     test_grow_by_and_resize( oneapi::tbb::concurrent_vector<Type, Allocator> &c ) : my_c(c) {}
1124     void operator()() const {
1125         const typename oneapi::tbb::concurrent_vector<Type, Allocator>::size_type sz = my_c.size();
1126         my_c.grow_by( 5 );
1127         REQUIRE( my_c.size() == sz + 5 );
1128         my_c.resize( sz );
1129         REQUIRE( my_c.size() == sz );
1130     }
1131 };
1132 
1133 namespace push_back_exception_safety_helpers {
1134     //TODO: remove code duplication with emplace_helpers::wrapper_type
1135     struct throwing_foo:move_support_tests::Foo {
1136         int value1;
1137         int value2;
1138         explicit throwing_foo(int v1, int v2) : value1 (v1), value2(v2) {}
1139     };
1140 
1141     template< typename foo_t = throwing_foo>
1142     struct fixture {
1143         using vector_t = oneapi::tbb::concurrent_vector<foo_t, std::allocator<foo_t> >;
1144         vector_t v;
1145 
1146         void test( void(*p_test)(vector_t&)){
1147             utils::suppress_unused_warning(p_test);
1148             move_support_tests::track_foo_count<__LINE__> verify_no_foo_leaked_during_exception{};
1149             utils::suppress_unused_warning(verify_no_foo_leaked_during_exception);
1150             REQUIRE_MESSAGE(v.empty(),"incorrect test setup?" );
1151             REQUIRE_THROWS_AS(p_test(v), move_support_tests::FooException);
1152             REQUIRE_MESSAGE(is_state<move_support_tests::Foo::ZeroInitialized>(v[0]),"incorrectly filled item during exception in emplace_back?");
1153         }
1154     };
1155 }
1156 
1157 void TestPushBackMoveExceptionSafety() {
1158     using fixture_t = push_back_exception_safety_helpers::fixture<move_support_tests::Foo>;
1159     fixture_t t;
1160 
1161     move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count + 1);
1162 
1163     struct test {
1164         static void test_move_push_back(fixture_t::vector_t& v) {
1165             move_support_tests::Foo f;
1166             v.push_back(std::move(f));
1167         }
1168     };
1169     t.test(&test::test_move_push_back);
1170 }
1171 
1172 void TestEmplaceBackExceptionSafety(){
1173     using fixture_t = push_back_exception_safety_helpers::fixture<>;
1174     fixture_t t;
1175 
1176     move_support_tests::Foo dummy; //make FooCount non zero;
1177     utils::suppress_unused_warning(dummy);
1178     move_support_tests::LimitFooCountInScope foo_limit(move_support_tests::foo_count);
1179 
1180     struct test {
1181         static void test_emplace(fixture_t::vector_t& v) {
1182             v.emplace_back(1,2);
1183         }
1184     };
1185     t.test(&test::test_emplace);
1186 }
1187 
1188 namespace move_semantics_helpers {
1189     struct move_only_type {
1190         const int* my_pointer;
1191         move_only_type(move_only_type && other): my_pointer(other.my_pointer){other.my_pointer=nullptr;}
1192         explicit move_only_type(const int* value): my_pointer(value) {}
1193     };
1194 }
1195 
1196 void TestPushBackMoveOnlyContainer(){
1197     using namespace move_semantics_helpers;
1198     using vector_t = oneapi::tbb::concurrent_vector<move_only_type >;
1199     vector_t v;
1200     static const int magic_number = 7;
1201     move_only_type src(&magic_number);
1202     v.push_back(std::move(src));
1203     REQUIRE_MESSAGE((v[0].my_pointer == &magic_number),"item was incorrectly moved during push_back?");
1204     REQUIRE_MESSAGE(src.my_pointer == nullptr,"item was incorrectly moved during push_back?");
1205 }
1206 
1207 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1208 template <template <typename...> typename TVector>
1209 void TestDeductionGuides() {
1210     using ComplexType = const std::string*;
1211     std::vector<ComplexType> v;
1212     std::string s = "s";
1213     auto l = {ComplexType(&s), ComplexType(&s)};
1214 
1215     // check TVector(InputIterator, InputIterator)
1216     TVector v1(v.begin(), v.end());
1217     static_assert(std::is_same<decltype(v1), TVector<ComplexType>>::value);
1218 
1219     // check TVector(InputIterator, InputIterator, Alocator)
1220     TVector v2(v.begin(), v.end(), std::allocator<ComplexType>());
1221     static_assert(std::is_same<decltype(v2),
1222        TVector<ComplexType, std::allocator<ComplexType>>>::value);
1223 
1224     // check TVector(std::initializer_list<T>)
1225     TVector v3(l);
1226     static_assert(std::is_same<decltype(v3),
1227         TVector<ComplexType>>::value);
1228 
1229     // check TVector(std::initializer_list, Alocator)
1230     TVector v4(l, std::allocator<ComplexType>());
1231     static_assert(std::is_same<decltype(v4), TVector<ComplexType, std::allocator<ComplexType>>>::value);
1232 
1233     // check TVector(TVector&)
1234     TVector v5(v1);
1235     static_assert(std::is_same<decltype(v5), TVector<ComplexType>>::value);
1236 
1237     // check TVector(TVector&, Allocator)
1238     TVector v6(v5, oneapi::tbb::cache_aligned_allocator<ComplexType>());
1239     static_assert(std::is_same<decltype(v6), TVector<ComplexType, oneapi::tbb::cache_aligned_allocator<ComplexType>>>::value);
1240 
1241     // check TVector(TVector&&)
1242     TVector v7(std::move(v1));
1243     static_assert(std::is_same<decltype(v7), decltype(v1)>::value);
1244 
1245     // check TVector(TVector&&, Allocator)
1246     TVector v8(std::move(v5), oneapi::tbb::cache_aligned_allocator<ComplexType>());
1247     static_assert(std::is_same<decltype(v8), TVector<ComplexType, oneapi::tbb::cache_aligned_allocator<ComplexType>>>::value);
1248 
1249 }
1250 #endif
1251 
1252 template <template <typename... > class ContainerType>
1253 void test_member_types() {
1254     using default_container_type = ContainerType<int>;
1255 
1256     static_assert(std::is_same<typename default_container_type::allocator_type,
1257                                oneapi::tbb::cache_aligned_allocator<int>>::value,
1258                   "Incorrect default template allocator");
1259 
1260 
1261     using test_allocator_type = oneapi::tbb::cache_aligned_allocator<int>;
1262     using container_type = ContainerType<int, test_allocator_type>;
1263 
1264     static_assert(std::is_same<typename container_type::value_type, int>::value,
1265                   "Incorrect container value_type member type");
1266 
1267     static_assert(std::is_unsigned<typename container_type::size_type>::value,
1268                   "Incorrect container size_type member type");
1269     static_assert(std::is_signed<typename container_type::difference_type>::value,
1270                   "Incorrect container difference_type member type");
1271 
1272     using value_type = typename container_type::value_type;
1273     static_assert(std::is_same<typename container_type::reference, value_type&>::value,
1274                   "Incorrect container reference member type");
1275     static_assert(std::is_same<typename container_type::const_reference, const value_type&>::value,
1276                   "Incorrect container const_reference member type");
1277     using allocator_type = typename container_type::allocator_type;
1278     static_assert(std::is_same<typename container_type::pointer, typename std::allocator_traits<allocator_type>::pointer>::value,
1279                   "Incorrect container pointer member type");
1280     static_assert(std::is_same<typename container_type::const_pointer, typename std::allocator_traits<allocator_type>::const_pointer>::value,
1281                   "Incorrect container const_pointer member type");
1282 
1283     static_assert(utils::is_random_access_iterator<typename container_type::iterator>::value,
1284                   "Incorrect container iterator member type");
1285     static_assert(!std::is_const<typename container_type::iterator::value_type>::value,
1286                   "Incorrect container iterator member type");
1287     static_assert(utils::is_random_access_iterator<typename container_type::const_iterator>::value,
1288                   "Incorrect container const_iterator member type");
1289     static_assert(std::is_const<typename container_type::const_iterator::value_type>::value,
1290                   "Incorrect container iterator member type");
1291 }
1292 
1293 void TestConcurrentGrowToAtLeast() {
1294     TestConcurrentGrowToAtLeastImpl<false>();
1295     TestConcurrentGrowToAtLeastImpl<true>();
1296 }
1297 
1298 template <typename Vector>
1299 void test_comparisons_basic() {
1300     using comparisons_testing::testEqualityAndLessComparisons;
1301     Vector v1, v2;
1302     testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(v1, v2);
1303 
1304     v1.emplace_back(1);
1305     testEqualityAndLessComparisons</*ExpectEqual = */false, /*ExpectLess = */false>(v1, v2);
1306 
1307     v2.emplace_back(1);
1308     testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(v1, v2);
1309 
1310     v2.emplace_back(2);
1311     testEqualityAndLessComparisons</*ExpectEqual = */false, /*ExpectLess = */true>(v1, v2);
1312 
1313     v1.clear();
1314     v2.clear();
1315     testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(v1, v2);
1316 }
1317 
1318 template <typename TwoWayComparableVectorType>
1319 void test_two_way_comparable_vector() {
1320     TwoWayComparableVectorType v1, v2;
1321     v1.emplace_back(1);
1322     v2.emplace_back(1);
1323     comparisons_testing::TwoWayComparable::reset();
1324     REQUIRE_MESSAGE(!(v1 < v2), "Incorrect operator < result");
1325     comparisons_testing::check_two_way_comparison();
1326     REQUIRE_MESSAGE(!(v1 > v2), "Incorrect operator > result");
1327     comparisons_testing::check_two_way_comparison();
1328     REQUIRE_MESSAGE(v1 <= v2, "Incorrect operator <= result");
1329     comparisons_testing::check_two_way_comparison();
1330     REQUIRE_MESSAGE(v1 >= v2, "Incorrect operator >= result");
1331     comparisons_testing::check_two_way_comparison();
1332 }
1333 
1334 #if __TBB_TEST_CPP20_COMPARISONS
1335 template <typename ThreeWayComparableVectorType>
1336 void test_three_way_comparable_vector() {
1337     ThreeWayComparableVectorType v1, v2;
1338     v1.emplace_back(1);
1339     v2.emplace_back(1);
1340     comparisons_testing::ThreeWayComparable::reset();
1341     REQUIRE_MESSAGE(!(v1 <=> v2 < 0), "Incorrect operator<=> result");
1342     comparisons_testing::check_three_way_comparison();
1343 
1344     REQUIRE_MESSAGE(!(v1 < v2), "Incorrect operator< result");
1345     comparisons_testing::check_three_way_comparison();
1346 
1347     REQUIRE_MESSAGE(!(v1 > v2), "Incorrect operator> result");
1348     comparisons_testing::check_three_way_comparison();
1349 
1350     REQUIRE_MESSAGE(v1 <= v2, "Incorrect operator>= result");
1351     comparisons_testing::check_three_way_comparison();
1352 
1353     REQUIRE_MESSAGE(v1 >= v2, "Incorrect operator>= result");
1354     comparisons_testing::check_three_way_comparison();
1355 }
1356 #endif // __TBB_TEST_CPP20_COMPARISONS
1357 
1358 void TestVectorComparisons() {
1359     using integral_vector = oneapi::tbb::concurrent_vector<int>;
1360     using two_way_comparable_vector = oneapi::tbb::concurrent_vector<comparisons_testing::TwoWayComparable>;
1361 
1362     test_comparisons_basic<integral_vector>();
1363     test_comparisons_basic<two_way_comparable_vector>();
1364     test_two_way_comparable_vector<two_way_comparable_vector>();
1365 
1366 #if __TBB_TEST_CPP20_COMPARISONS
1367     using two_way_less_only_vector = oneapi::tbb::concurrent_vector<comparisons_testing::LessComparableOnly>;
1368     using three_way_only_vector = oneapi::tbb::concurrent_vector<comparisons_testing::ThreeWayComparableOnly>;
1369     using three_way_comparable_vector = oneapi::tbb::concurrent_vector<comparisons_testing::ThreeWayComparable>;
1370 
1371     test_comparisons_basic<two_way_less_only_vector>();
1372     test_comparisons_basic<three_way_only_vector>();
1373     test_comparisons_basic<three_way_comparable_vector>();
1374     test_three_way_comparable_vector<three_way_comparable_vector>();
1375 #endif // __TBB_CPP20_COMPARISONS_PRESENT && __TBB_CPP20_CONVEPTS_PRESENT
1376 }
1377 
1378 template <bool ExpectEqual, bool ExpectLess, typename Iterator>
1379 void DoVectorIteratorComparisons( const Iterator& lhs, const Iterator& rhs ) {
1380     // TODO: replace with testEqualityAndLessComparisons after adding <=> operator for concurrent_vector iterator
1381     using namespace comparisons_testing;
1382     testEqualityComparisons<ExpectEqual>(lhs, rhs);
1383     testTwoWayComparisons<ExpectEqual, ExpectLess>(lhs, rhs);
1384 }
1385 
1386 template <typename Iterator, typename VectorType>
1387 void TestVectorIteratorComparisonsBasic( VectorType& vec ) {
1388     REQUIRE_MESSAGE(!vec.empty(), "Incorrect test setup");
1389     Iterator it1, it2;
1390     DoVectorIteratorComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(it1, it2);
1391     it1 = vec.begin();
1392     it2 = vec.begin();
1393     DoVectorIteratorComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(it1, it2);
1394     it2 = std::prev(vec.end());
1395     DoVectorIteratorComparisons</*ExpectEqual = */false, /*ExpectLess = */true>(it1, it2);
1396 }
1397 
1398 void TestVectorIteratorComparisons() {
1399     using vector_type = oneapi::tbb::concurrent_vector<int>;
1400     vector_type vec = {1, 2, 3, 4, 5};
1401     TestVectorIteratorComparisonsBasic<typename vector_type::iterator>(vec);
1402     const vector_type& cvec = vec;
1403     TestVectorIteratorComparisonsBasic<typename vector_type::const_iterator>(cvec);
1404 }
1405 
1406 //! Test type matching
1407 //! \brief \ref interface \ref requirement
1408 TEST_CASE("test type matching") {
1409     test_member_types<oneapi::tbb::concurrent_vector>();
1410 }
1411 
1412 //! Test sequential access to elements
1413 //! \brief \ref interface \ref requirement
1414 TEST_CASE("testing sequential for") {
1415     TestSequentialFor<move_support_tests::FooWithAssign> ();
1416 }
1417 
1418 //! Test of assign, grow, copying with various sizes
1419 //! \brief \ref interface \ref requirement
1420 TEST_CASE("testing resize and copy"){
1421     TestResizeAndCopy();
1422 }
1423 
1424 //! Test the assignment operator and swap
1425 //! \brief \ref interface \ref requirement
1426 TEST_CASE("testing copy assignment"){
1427     TestCopyAssignment();
1428 }
1429 
1430 //! Testing grow_to_at_least operations
1431 //! \brief \ref interface
1432 TEST_CASE("testing grow_to_at_least with source parameter"){
1433     TestGrowToAtLeastWithSourceParameter<oneapi::tbb::concurrent_vector<int>>(12345);
1434 }
1435 
1436 //! Test of capacity, reserve, and shrink_to_fit
1437 //! \brief \ref interface \ref requirement
1438 TEST_CASE("testing capacity"){
1439    TestCapacity();
1440 }
1441 
1442 #if TBB_USE_EXCEPTIONS
1443 //! Test exceptions
1444 //! \brief \ref requirement
1445 TEST_CASE("testing exceptions"){
1446     TestExceptions();
1447 }
1448 
1449 //! Test of push_back move exception safety
1450 //! \brief \ref requirement
1451 TEST_CASE("testing push_back move exception safety"){
1452     TestPushBackMoveExceptionSafety();
1453 }
1454 
1455 //! Test of emplace back move exception safety
1456 //! \brief \ref requirement
1457 TEST_CASE("testing emplace back exception safety"){
1458     TestEmplaceBackExceptionSafety();
1459 }
1460 
1461 //! Test exceptions guarantees for assign operator
1462 //! \brief \ref requirement
1463 TEST_CASE("testing exception safety guaranteees for assign operator"){
1464     test_ex_assign_operator();
1465 }
1466 
1467 //! Test exceptions safety guarantees for concurrent_vector move constructor
1468 //! \brief \ref requirement
1469 TEST_CASE("exception safety guarantees for concurrent_vector move constructor") {
1470     move_support_tests::test_ex_move_constructor<c_vector_type>();
1471 }
1472 
1473 //! Test exceptions safety guarantees for concurrent_vector move assignment
1474 //! \brief \ref requirement
1475 TEST_CASE("test exception safety on concurrent_vector move assignment") {
1476     test_ex_move_assignment();
1477 }
1478 #endif
1479 //! Test push_back in move only container
1480 //! \brief \ref requirement
1481 TEST_CASE("testing push_back move only container"){
1482     TestPushBackMoveOnlyContainer();
1483 }
1484 
1485 //! Test types for std::iterator_traits in concurrent_vector::iterator
1486 //! \brief \ref requirement
1487 TEST_CASE("testing std::iterator_traits for concurrent_vector::iterator"){
1488     TestIteratorTraits<oneapi::tbb::concurrent_vector<move_support_tests::Foo>::iterator,move_support_tests::Foo>();
1489 }
1490 
1491 //! Test types for std::iterator_traits in concurrent_vector::const_iterator
1492 //! \brief \ref requirement
1493 TEST_CASE("testing std::iterator_traits for concurrent_vector::const_iterator"){
1494     TestIteratorTraits<oneapi::tbb::concurrent_vector<move_support_tests::Foo>::const_iterator,const move_support_tests::Foo>();
1495 }
1496 
1497 //! Test initializer_list support
1498 //! \brief \ref interface \ref requirement
1499 TEST_CASE("testing initializer_list support"){
1500     TestInitList();
1501 }
1502 
1503 //! Test move constructor
1504 //! \brief \ref interface \ref requirement
1505 TEST_CASE("testing move constructor"){
1506     move_support_tests::test_move_constructor<c_vector_type>();
1507 }
1508 
1509 //! Test move assign operator
1510 //! \brief \ref interface \ref requirement
1511 TEST_CASE("testing move assign operator"){
1512     move_support_tests::test_move_assignment<c_vector_type>();
1513 }
1514 
1515 //! Test constructor with move iterators
1516 //! \brief \ref requirement
1517 TEST_CASE("testing constructor with move iterators"){
1518     move_support_tests::test_constructor_with_move_iterators<c_vector_type>();
1519 }
1520 
1521 //! Test assign with move iterators
1522 //! \brief \ref interface \ref requirement
1523 TEST_CASE("testing assign with move iterators"){
1524     move_support_tests::test_assign_with_move_iterators<c_vector_type>();
1525 }
1526 
1527 //! Test grow_by with move iterator
1528 //! \brief \ref requirement
1529 TEST_CASE("testing serial grow_by with move iterator"){
1530     TestSerialGrowByWithMoveIterators();
1531 }
1532 
1533 //! Test grow_by with move iterator
1534 //! \brief \ref requirement
1535 TEST_CASE("testing serial move in shrink_to_fit"){
1536     TestSerialMoveInShrinkToFit();
1537 }
1538 
1539 //! Test concurrent grow
1540 //! \brief \ref requirement
1541 TEST_CASE("testing concurrency"){
1542     REQUIRE(!move_support_tests::foo_count);
1543     for (std::size_t p = 1; p <= 4; ++p) {
1544         oneapi::tbb::global_control limit(oneapi::tbb::global_control::max_allowed_parallelism, p);
1545         TestParallelFor(p);
1546         TestConcurrentGrowToAtLeast();
1547         TestConcurrentGrowBy();
1548     }
1549 
1550     REQUIRE(!move_support_tests::foo_count);
1551 }
1552 
1553 //! Test assign operations
1554 //! \brief \ref interface \ref requirement
1555 TEST_CASE("testing comparison on assign operations"){
1556     TestComparison();
1557 }
1558 
1559 //! Test allocator_traits support in concurrent_vector
1560 //! \brief \ref requirement
1561 TEST_CASE("test allocator_traits support in concurrent_vector") {
1562     test_allocator_traits_support<c_vector_type>();
1563 }
1564 
1565 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1566 //! Test deduction guides
1567 //! \brief \ref requirement
1568 TEST_CASE("testing deduction guides"){
1569     TestDeductionGuides<oneapi::tbb::concurrent_vector>();
1570 }
1571 #endif
1572 
1573 //! Test concurrent_vector comparisons
1574 //! \brief \ref interface \ref requirement
1575 TEST_CASE("concurrent_vector comparisons") {
1576     TestVectorComparisons();
1577 }
1578 
1579 //! Test concurrent_vector iterators comparisons
1580 //! \brief \ref interface \ref requirement
1581 TEST_CASE("concurrent_vector iterators comparisons") {
1582     TestVectorIteratorComparisons();
1583 }
1584