/*
    Copyright 2005-2010 Intel Corporation.  All Rights Reserved.

    This file is part of Threading Building Blocks.

    Threading Building Blocks is free software; you can redistribute it
    and/or modify it under the terms of the GNU General Public License
    version 2 as published by the Free Software Foundation.

    Threading Building Blocks is distributed in the hope that it will be
    useful, but WITHOUT ANY WARRANTY; without even the implied warranty
    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Threading Building Blocks; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    As a special exception, you may use this file as part of a free software
    library without restriction.  Specifically, if other files instantiate
    templates or use macros or inline functions from this file, or you compile
    this file and link it with other files to produce an executable, this
    file does not by itself cause the resulting executable to be covered by
    the GNU General Public License.  This exception does not however
    invalidate any other reasons why the executable file might be covered by
    the GNU General Public License.
*/

#include "tbb/concurrent_vector.h"
#include "tbb/tbb_allocator.h"
#include "tbb/cache_aligned_allocator.h"
#include "tbb/tbb_exception.h"
#include <cstdio>
#include <cstdlib>
#include "harness_report.h"
#include "harness_assert.h"
#include "harness_allocator.h"

#if TBB_USE_EXCEPTIONS
static bool known_issue_verbose = false;
#define KNOWN_ISSUE(msg) if(!known_issue_verbose) known_issue_verbose = true, REPORT(msg)
#endif /* TBB_USE_EXCEPTIONS */

tbb::atomic<long> FooCount;
long MaxFooCount = 0;

//! Problem size
const size_t N = 500000;

//! Exception for concurrent_vector
class Foo_exception : public std::bad_alloc {
public:
    virtual const char *what() const noexcept { return "out of Foo limit"; }
    virtual ~Foo_exception() noexcept {}
};

static const int initial_value_of_bar = 42;
struct Foo {
    int my_bar;
public:
    enum State {
        ZeroInitialized=0,
        DefaultInitialized=0xDEFAUL,
        CopyInitialized=0xC0314,
        Destroyed=0xDEADF00
    } state;
    bool is_valid() const {
        return state==DefaultInitialized||state==CopyInitialized;
    }
    bool is_valid_or_zero() const {
        return is_valid()||(state==ZeroInitialized && !my_bar);
    }
    int& zero_bar() {
        ASSERT( is_valid_or_zero(), NULL );
        return my_bar;
    }
    int& bar() {
        ASSERT( is_valid(), NULL );
        return my_bar;
    }
    int bar() const {
        ASSERT( is_valid(), NULL );
        return my_bar;
    }
    Foo( int barr = initial_value_of_bar ) {
        my_bar = barr;
        if(MaxFooCount && FooCount >= MaxFooCount)
            __TBB_THROW( Foo_exception() );
        FooCount++;
        state = DefaultInitialized;
    }
    Foo( const Foo& foo ) {
        my_bar = foo.my_bar;
        ASSERT( foo.is_valid_or_zero(), "bad source for copy" );
        if(MaxFooCount && FooCount >= MaxFooCount)
            __TBB_THROW( Foo_exception() );
        FooCount++;
        state = CopyInitialized;
    }
    ~Foo() {
        ASSERT( is_valid_or_zero(), NULL );
        my_bar = ~initial_value_of_bar;
        if(state != ZeroInitialized) --FooCount;
        state = Destroyed;
    }
    bool operator==(const Foo &f) const { return my_bar == f.my_bar; }
    bool operator<(const Foo &f) const { return my_bar < f.my_bar; }
    bool is_const() const {return true;}
    bool is_const() {return false;}
protected:
    char reserve[1];
    void operator=( const Foo& ) {}
};

class FooWithAssign: public Foo {
public:
    void operator=( const FooWithAssign& x ) {
        my_bar = x.my_bar;
        ASSERT( x.is_valid_or_zero(), "bad source for assignment" );
        ASSERT( is_valid(), NULL );
    } 
    bool operator==(const Foo &f) const { return my_bar == f.my_bar; }
    bool operator<(const Foo &f) const { return my_bar < f.my_bar; }
};

class FooIterator: public std::iterator<std::input_iterator_tag,FooWithAssign> {
    int x_bar;
public:
    FooIterator(int x) {
        x_bar = x;
    }
    FooIterator &operator++() {
        x_bar++; return *this;
    }
    FooWithAssign operator*() {
        FooWithAssign foo; foo.bar() = x_bar;
        return foo;
    }
    bool operator!=(const FooIterator &i) { return x_bar != i.x_bar; }
};

inline void NextSize( int& s ) {
    if( s<=32 ) ++s;
    else s += s/10;
}

//! Check vector have expected size and filling
template<typename vector_t>
static void CheckVector( const vector_t& cv, size_t expected_size, size_t old_size ) {
    ASSERT( cv.capacity()>=expected_size, NULL );
    ASSERT( cv.size()==expected_size, NULL );
    ASSERT( cv.empty()==(expected_size==0), NULL );
    for( int j=0; j<int(expected_size); ++j ) {
        if( cv[j].bar()!=~j )
            REPORT("ERROR on line %d for old_size=%ld expected_size=%ld j=%d\n",__LINE__,long(old_size),long(expected_size),j);
    }
}

//! Test of assign, grow, copying with various sizes
void TestResizeAndCopy() {
    typedef static_counting_allocator<debug_allocator<Foo,std::allocator>, std::size_t> allocator_t;
    typedef tbb::concurrent_vector<Foo, allocator_t> vector_t;
    allocator_t::init_counters();
    for( int old_size=0; old_size<=128; NextSize( old_size ) ) {
        for( int new_size=0; new_size<=1280; NextSize( new_size ) ) {
            long count = FooCount;
            vector_t v;
            ASSERT( count==FooCount, NULL );
            v.assign(old_size/2, Foo() );
            ASSERT( count+old_size/2==FooCount, NULL );
            for( int j=0; j<old_size/2; ++j )
                ASSERT( v[j].state == Foo::CopyInitialized, NULL);
            v.assign(FooIterator(0), FooIterator(old_size));
            v.resize(new_size, Foo(33) );
            ASSERT( count+new_size==FooCount, NULL );
            for( int j=0; j<new_size; ++j ) {
                int expected = j<old_size ? j : 33;
                if( v[j].bar()!=expected ) 
                    REPORT("ERROR on line %d for old_size=%ld new_size=%ld v[%ld].bar()=%d != %d\n",__LINE__,long(old_size),long(new_size),long(j),v[j].bar(), expected);
            }
            ASSERT( v.size()==size_t(new_size), NULL );
            for( int j=0; j<new_size; ++j ) {
                v[j].bar() = ~j;
            }
            const vector_t& cv = v;
            // Try copy constructor
            vector_t copy_of_v(cv);
            CheckVector(cv,new_size,old_size);
            ASSERT( !(v != copy_of_v), NULL );
            v.clear();
            ASSERT( v.empty(), NULL );
            swap(v, copy_of_v);
            ASSERT( copy_of_v.empty(), NULL );
            CheckVector(v,new_size,old_size);
        }
    }
    ASSERT( allocator_t::items_allocated == allocator_t::items_freed, NULL);
    ASSERT( allocator_t::allocations == allocator_t::frees, NULL);
}

//! Test reserve, compact, capacity
void TestCapacity() {
    typedef static_counting_allocator<debug_allocator<Foo,tbb::cache_aligned_allocator>, std::size_t> allocator_t;
    typedef tbb::concurrent_vector<Foo, allocator_t> vector_t;
    allocator_t::init_counters();
    for( size_t old_size=0; old_size<=11000; old_size=(old_size<5 ? old_size+1 : 3*old_size) ) {
        for( size_t new_size=0; new_size<=11000; new_size=(new_size<5 ? new_size+1 : 3*new_size) ) {
            long count = FooCount; 
            {
                vector_t v; v.reserve(old_size);
                ASSERT( v.capacity()>=old_size, NULL );
                v.reserve( new_size );
                ASSERT( v.capacity()>=old_size, NULL );
                ASSERT( v.capacity()>=new_size, NULL );
                ASSERT( v.empty(), NULL );
                size_t fill_size = 2*new_size;
                for( size_t i=0; i<fill_size; ++i ) {
                    ASSERT( size_t(FooCount)==count+i, NULL );
#if TBB_DEPRECATED
                    size_t j = v.grow_by(1);
#else
                    size_t j = v.grow_by(1) - v.begin();
#endif
                    ASSERT( j==i, NULL );
                    v[j].bar() = int(~j);
                }
                vector_t copy_of_v(v); // should allocate first segment with same size as for shrink_to_fit()
                if(__TBB_Log2(/*reserved size*/old_size|1) > __TBB_Log2(fill_size|1) )
                    ASSERT( v.capacity() != copy_of_v.capacity(), NULL );
                v.shrink_to_fit();
                ASSERT( v.capacity() == copy_of_v.capacity(), NULL );
                CheckVector(v, new_size*2, old_size); // check vector correctness
                ASSERT( v==copy_of_v, NULL ); // TODO: check also segments layout equality
            }
            ASSERT( FooCount==count, NULL );
        }
    } 
    ASSERT( allocator_t::items_allocated == allocator_t::items_freed, NULL);
    ASSERT( allocator_t::allocations == allocator_t::frees, NULL);
}

struct AssignElement {
    typedef tbb::concurrent_vector<int>::range_type::iterator iterator;
    iterator base;
    void operator()( const tbb::concurrent_vector<int>::range_type& range ) const {
        for( iterator i=range.begin(); i!=range.end(); ++i ) {
            if( *i!=0 )
                REPORT("ERROR for v[%ld]\n", long(i-base));
            *i = int(i-base);
        }
    }
    AssignElement( iterator base_ ) : base(base_) {}
};

struct CheckElement {
    typedef tbb::concurrent_vector<int>::const_range_type::iterator iterator;
    iterator base;
    void operator()( const tbb::concurrent_vector<int>::const_range_type& range ) const {
        for( iterator i=range.begin(); i!=range.end(); ++i )
            if( *i != int(i-base) )
                REPORT("ERROR for v[%ld]\n", long(i-base));
    }
    CheckElement( iterator base_ ) : base(base_) {}
};

#include "tbb/tick_count.h"
#include "tbb/parallel_for.h"
#include "harness.h"

//! Test parallel access by iterators
void TestParallelFor( int nthread ) {
    typedef tbb::concurrent_vector<int> vector_t;
    vector_t v;
    v.resize(N);
    tbb::tick_count t0 = tbb::tick_count::now();
    REMARK("Calling parallel_for with %ld threads\n",long(nthread));
    tbb::parallel_for( v.range(10000), AssignElement(v.begin()) );
    tbb::tick_count t1 = tbb::tick_count::now();
    const vector_t& u = v;
    tbb::parallel_for( u.range(10000), CheckElement(u.begin()) );
    tbb::tick_count t2 = tbb::tick_count::now();
    REMARK("Time for parallel_for: assign time = %8.5f, check time = %8.5f\n",
               (t1-t0).seconds(),(t2-t1).seconds());
    for( long i=0; size_t(i)<v.size(); ++i )
        if( v[i]!=i )
            REPORT("ERROR for v[%ld]\n", i);
}

template<typename Iterator1, typename Iterator2>
void TestIteratorAssignment( Iterator2 j ) {
    Iterator1 i(j);
    ASSERT( i==j, NULL );
    ASSERT( !(i!=j), NULL );
    Iterator1 k;
    k = j;
    ASSERT( k==j, NULL );
    ASSERT( !(k!=j), NULL );
}

template<typename Range1, typename Range2>
void TestRangeAssignment( Range2 r2 ) {
    Range1 r1(r2); r1 = r2;
}

template<typename Iterator, typename T>
void TestIteratorTraits() {
    AssertSameType( static_cast<typename Iterator::difference_type*>(0), static_cast<ptrdiff_t*>(0) ); 
    AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) ); 
    AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) ); 
    AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::random_access_iterator_tag*>(0) );
    T x;
    typename Iterator::reference xr = x;
    typename Iterator::pointer xp = &x;
    ASSERT( &xr==xp, NULL );
}

template<typename Vector, typename Iterator>
void CheckConstIterator( const Vector& u, int i, const Iterator& cp ) {
    typename Vector::const_reference pref = *cp;
    if( pref.bar()!=i )
        REPORT("ERROR for u[%ld] using const_iterator\n", long(i));
    typename Vector::difference_type delta = cp-u.begin();
    ASSERT( delta==i, NULL );
    if( u[i].bar()!=i )
        REPORT("ERROR for u[%ld] using subscripting\n", long(i));
    ASSERT( u.begin()[i].bar()==i, NULL );
}

template<typename Iterator1, typename Iterator2, typename V> 
void CheckIteratorComparison( V& u ) {
    V u2 = u;
    Iterator1 i = u.begin();

    for( int i_count=0; i_count<100; ++i_count ) {
        Iterator2 j = u.begin();
        Iterator2 i2 = u2.begin();
        for( int j_count=0; j_count<100; ++j_count ) {
            ASSERT( (i==j)==(i_count==j_count), NULL );
            ASSERT( (i!=j)==(i_count!=j_count), NULL );
            ASSERT( (i-j)==(i_count-j_count), NULL );
            ASSERT( (i<j)==(i_count<j_count), NULL );
            ASSERT( (i>j)==(i_count>j_count), NULL );
            ASSERT( (i<=j)==(i_count<=j_count), NULL );
            ASSERT( (i>=j)==(i_count>=j_count), NULL );
            ASSERT( !(i==i2), NULL ); 
            ASSERT( i!=i2, NULL ); 
            ++j;
            ++i2;
        }
        ++i;
    }
}

//! Test sequential iterators for vector type V.
/** Also does timing. */
template<typename T>
void TestSequentialFor() {
    typedef tbb::concurrent_vector<FooWithAssign> V;
    V v(N);
    ASSERT(v.grow_by(0) == v.grow_by(0, FooWithAssign()), NULL);

    // Check iterator 
    tbb::tick_count t0 = tbb::tick_count::now();
    typename V::iterator p = v.begin();
    ASSERT( !(*p).is_const(), NULL );
    ASSERT( !p->is_const(), NULL );
    for( int i=0; size_t(i)<v.size(); ++i, ++p ) {
        if( (*p).state!=Foo::DefaultInitialized )
            REPORT("ERROR for v[%ld]\n", long(i));
        typename V::reference pref = *p;
        pref.bar() = i;
        typename V::difference_type delta = p-v.begin();
        ASSERT( delta==i, NULL );
        ASSERT( -delta<=0, "difference type not signed?" );
    }
    tbb::tick_count t1 = tbb::tick_count::now();
    
    // Check const_iterator going forwards
    const V& u = v;
    typename V::const_iterator cp = u.begin();
    ASSERT( cp == v.cbegin(), NULL );
    ASSERT( (*cp).is_const(), NULL );
    ASSERT( cp->is_const(), NULL );
    ASSERT( *cp == v.front(), NULL);
    for( int i=0; size_t(i)<u.size(); ++i ) {
        CheckConstIterator(u,i,cp);
        V::const_iterator &cpr = ++cp;
        ASSERT( &cpr == &cp, "preincrement not returning a reference?");
    }
    tbb::tick_count t2 = tbb::tick_count::now();
    REMARK("Time for serial for:  assign time = %8.5f, check time = %8.5f\n",
               (t1-t0).seconds(),(t2-t1).seconds());

    // Now go backwards
    cp = u.end();
    ASSERT( cp == v.cend(), NULL );
    for( int i=int(u.size()); i>0; ) {
        --i;
        V::const_iterator &cpr = --cp;
        ASSERT( &cpr == &cp, "predecrement not returning a reference?");
        if( i>0 ) {
            typename V::const_iterator cp_old = cp--;
            int here = (*cp_old).bar();
            ASSERT( here==u[i].bar(), NULL );
            typename V::const_iterator cp_new = cp++;
            int prev = (*cp_new).bar();
            ASSERT( prev==u[i-1].bar(), NULL );
        }
        CheckConstIterator(u,i,cp);
    }

    // Now go forwards and backwards
    ptrdiff_t k = 0;
    cp = u.begin();
    for( size_t i=0; i<u.size(); ++i ) {
        CheckConstIterator(u,int(k),cp);
        typename V::difference_type delta = i*3 % u.size();
        if( 0<=k+delta && size_t(k+delta)<u.size() ) {
            V::const_iterator &cpr = (cp += delta);
            ASSERT( &cpr == &cp, "+= not returning a reference?");
            k += delta; 
        } 
        delta = i*7 % u.size();
        if( 0<=k-delta && size_t(k-delta)<u.size() ) {
            if( i&1 ) { 
                V::const_iterator &cpr = (cp -= delta);
                ASSERT( &cpr == &cp, "-= not returning a reference?");
            } else
                cp = cp - delta;        // Test operator-
            k -= delta; 
        } 
    }
    
    for( int i=0; size_t(i)<u.size(); i=(i<50?i+1:i*3) )
        for( int j=-i; size_t(i+j)<u.size(); j=(j<50?j+1:j*5) ) {
            ASSERT( (u.begin()+i)[j].bar()==i+j, NULL );
            ASSERT( (v.begin()+i)[j].bar()==i+j, NULL );
            ASSERT((v.cbegin()+i)[j].bar()==i+j, NULL );
            ASSERT( (i+u.begin())[j].bar()==i+j, NULL );
            ASSERT( (i+v.begin())[j].bar()==i+j, NULL );
            ASSERT((i+v.cbegin())[j].bar()==i+j, NULL );
        }

    CheckIteratorComparison<typename V::iterator, typename V::iterator>(v);
    CheckIteratorComparison<typename V::iterator, typename V::const_iterator>(v);
    CheckIteratorComparison<typename V::const_iterator, typename V::iterator>(v);
    CheckIteratorComparison<typename V::const_iterator, typename V::const_iterator>(v);

    TestIteratorAssignment<typename V::const_iterator>( u.begin() );
    TestIteratorAssignment<typename V::const_iterator>( v.begin() );
    TestIteratorAssignment<typename V::const_iterator>( v.cbegin() );
    TestIteratorAssignment<typename V::iterator>( v.begin() );
    // doesn't compile as expected: TestIteratorAssignment<typename V::iterator>( u.begin() );

    TestRangeAssignment<typename V::const_range_type>( u.range() );
    TestRangeAssignment<typename V::const_range_type>( v.range() );
    TestRangeAssignment<typename V::range_type>( v.range() );
    // doesn't compile as expected: TestRangeAssignment<typename V::range_type>( u.range() );

    // Check reverse_iterator 
    typename V::reverse_iterator rp = v.rbegin();
    for( size_t i=v.size(); i>0; --i, ++rp ) {
        typename V::reference pref = *rp;
        ASSERT( size_t(pref.bar())==i-1, NULL );
        ASSERT( rp!=v.rend(), NULL );
    }
    ASSERT( rp==v.rend(), NULL );
    
    // Check const_reverse_iterator 
    typename V::const_reverse_iterator crp = u.rbegin();
    ASSERT( crp == v.crbegin(), NULL );
    ASSERT( *crp == v.back(), NULL);
    for( size_t i=v.size(); i>0; --i, ++crp ) {
        typename V::const_reference cpref = *crp;
        ASSERT( size_t(cpref.bar())==i-1, NULL );
        ASSERT( crp!=u.rend(), NULL );
    }
    ASSERT( crp == u.rend(), NULL );
    ASSERT( crp == v.crend(), NULL );

    TestIteratorAssignment<typename V::const_reverse_iterator>( u.rbegin() );
    TestIteratorAssignment<typename V::reverse_iterator>( v.rbegin() );

    // test compliance with C++ Standard 2003, clause 23.1.1p9
    {
        tbb::concurrent_vector<int> v1, v2(1, 100);
        v1.assign(1, 100); ASSERT(v1 == v2, NULL);
        ASSERT(v1.size() == 1 && v1[0] == 100, "used integral iterators");
    }

    // cross-allocator tests
#if !defined(_WIN64) || defined(_CPPLIB_VER)
    typedef local_counting_allocator<std::allocator<int>, size_t> allocator1_t;
    typedef tbb::cache_aligned_allocator<void> allocator2_t;
    typedef tbb::concurrent_vector<FooWithAssign, allocator1_t> V1;
    typedef tbb::concurrent_vector<FooWithAssign, allocator2_t> V2;
    V1 v1( v ); // checking cross-allocator copying
    V2 v2( 10 ); v2 = v1; // checking cross-allocator assignment
    ASSERT( (v1 == v) && !(v2 != v), NULL);
    ASSERT( !(v1 < v) && !(v2 > v), NULL);
    ASSERT( (v1 <= v) && (v2 >= v), NULL);
#endif
}

static const size_t Modulus = 7;

typedef static_counting_allocator<debug_allocator<Foo> > MyAllocator;
typedef tbb::concurrent_vector<Foo, MyAllocator> MyVector;

template<typename MyVector>
class GrowToAtLeast: NoAssign {
    MyVector& my_vector;
public:
    void operator()( const tbb::blocked_range<size_t>& range ) const {
        for( size_t i=range.begin(); i!=range.end(); ++i ) {
            size_t n = my_vector.size();
            size_t req = (i % (2*n+1))+1;
#if TBB_DEPRECATED
            my_vector.grow_to_at_least(req);
#else
            typename MyVector::iterator p = my_vector.grow_to_at_least(req);
            if( p-my_vector.begin() < typename MyVector::difference_type(req) )
                ASSERT( p->state == Foo::DefaultInitialized || p->state == Foo::ZeroInitialized, NULL);
#endif
            ASSERT( my_vector.size()>=req, NULL );
        }
    }
    GrowToAtLeast( MyVector& vector ) : my_vector(vector) {}
};

void TestConcurrentGrowToAtLeast() {
    typedef static_counting_allocator< tbb::zero_allocator<Foo> > MyAllocator;
    typedef tbb::concurrent_vector<Foo, MyAllocator> MyVector;
    MyAllocator::init_counters();
    MyVector v(2, Foo(), MyAllocator());
    for( size_t s=1; s<1000; s*=10 ) {
        tbb::parallel_for( tbb::blocked_range<size_t>(0,10000*s,s), GrowToAtLeast<MyVector>(v), tbb::simple_partitioner() );
    }
    v.clear();
    ASSERT( 0 == v.get_allocator().frees, NULL);
    v.shrink_to_fit();
    size_t items_allocated = v.get_allocator().items_allocated,
           items_freed = v.get_allocator().items_freed;
    size_t allocations = v.get_allocator().allocations,
           frees = v.get_allocator().frees;
    ASSERT( items_allocated == items_freed, NULL);
    ASSERT( allocations == frees, NULL);
}

//! Test concurrent invocations of method concurrent_vector::grow_by
template<typename MyVector>
class GrowBy: NoAssign {
    MyVector& my_vector;
public:
    void operator()( const tbb::blocked_range<int>& range ) const {
        ASSERT( range.begin() < range.end(), NULL );
#if TBB_DEPRECATED
        for( int i=range.begin(); i!=range.end(); ++i )
#else
        int i = range.begin(), h = (range.end() - i) / 2;
        typename MyVector::iterator s = my_vector.grow_by(h);
        for( h += i; i < h; ++i, ++s )
            s->bar() = i;
        for(; i!=range.end(); ++i )
#endif
        {
            if( i&1 ) {
#if TBB_DEPRECATED
                typename MyVector::reference element = my_vector[my_vector.grow_by(1)]; 
                element.bar() = i;
#else
                my_vector.grow_by(1)->bar() = i;
#endif
            } else {
                typename MyVector::value_type f;
                f.bar() = i;
#if TBB_DEPRECATED
                size_t r;
#else
                typename MyVector::iterator r;
#endif
                if( i&2 )
                    r = my_vector.push_back( f );
                else
                    r = my_vector.grow_by(1, f);
#if TBB_DEPRECATED
                ASSERT( my_vector[r].bar()==i, NULL );
#else
                ASSERT( r->bar()==i, NULL );
#endif
            }
        }
    }
    GrowBy( MyVector& vector ) : my_vector(vector) {}
};

//! Test concurrent invocations of method concurrent_vector::grow_by
void TestConcurrentGrowBy( int nthread ) {
    MyAllocator::init_counters();
    {
        int m = 100000; MyAllocator a;
        MyVector v( a );
        tbb::parallel_for( tbb::blocked_range<int>(0,m,100), GrowBy<MyVector>(v), tbb::simple_partitioner() );
        ASSERT( v.size()==size_t(m), NULL );

        // Verify that v is a permutation of 0..m
        int inversions = 0, def_inits = 0, copy_inits = 0;
        bool* found = new bool[m];
        memset( found, 0, m );
        for( int i=0; i<m; ++i ) {
            if( v[i].state == Foo::DefaultInitialized ) ++def_inits;
            else if( v[i].state == Foo::CopyInitialized ) ++copy_inits;
            else {
                REMARK("i: %d ", i);
                ASSERT( false, "v[i] seems not initialized");
            }
            int index = v[i].bar();
            ASSERT( !found[index], NULL );
            found[index] = true;
            if( i>0 )
                inversions += v[i].bar()<v[i-1].bar();
        }
        for( int i=0; i<m; ++i ) {
            ASSERT( found[i], NULL );
            ASSERT( nthread>1 || v[i].bar()==i, "sequential execution is wrong" );
        }
        delete[] found;
        REMARK("Initialization by default constructor: %d, by copy: %d\n", def_inits, copy_inits);
        ASSERT( def_inits >= m/2, NULL );
        ASSERT( copy_inits >= m/4, NULL );
        if( nthread>1 && inversions<m/20 )
            REPORT("Warning: not much concurrency in TestConcurrentGrowBy (%d inversions)\n", inversions);
    }
    size_t items_allocated = MyAllocator::items_allocated,
           items_freed = MyAllocator::items_freed;
    size_t allocations = MyAllocator::allocations,
           frees = MyAllocator::frees;
    ASSERT( items_allocated == items_freed, NULL);
    ASSERT( allocations == frees, NULL);
}

//! Test the assignment operator and swap
void TestAssign() {
    typedef tbb::concurrent_vector<FooWithAssign, local_counting_allocator<std::allocator<FooWithAssign>, size_t > > vector_t;
    local_counting_allocator<std::allocator<FooWithAssign>, size_t > init_alloc;
    init_alloc.allocations = 100;
    for( int dst_size=1; dst_size<=128; NextSize( dst_size ) ) {
        for( int src_size=2; src_size<=128; NextSize( src_size ) ) {
            vector_t u(FooIterator(0), FooIterator(src_size), init_alloc);
            for( int i=0; i<src_size; ++i )
                ASSERT( u[i].bar()==i, NULL );
            vector_t v(dst_size, FooWithAssign(), init_alloc);
            for( int i=0; i<dst_size; ++i ) {
                ASSERT( v[i].state==Foo::CopyInitialized, NULL );
                v[i].bar() = ~i;
            }
            ASSERT( v != u, NULL);
            v.swap(u);
            CheckVector(u, dst_size, src_size);
            u.swap(v);
            // using assignment
            v = u;
            ASSERT( v == u, NULL);
            u.clear();
            ASSERT( u.size()==0, NULL );
            ASSERT( v.size()==size_t(src_size), NULL );
            for( int i=0; i<src_size; ++i )
                ASSERT( v[i].bar()==i, NULL );
            ASSERT( 0 == u.get_allocator().frees, NULL);
            u.shrink_to_fit(); // deallocate unused memory
            size_t items_allocated = u.get_allocator().items_allocated,
                   items_freed = u.get_allocator().items_freed;
            size_t allocations = u.get_allocator().allocations,
                   frees = u.get_allocator().frees + 100;
            ASSERT( items_allocated == items_freed, NULL);
            ASSERT( allocations == frees, NULL);
        }
    }
}

// Test the comparison operators
#if !TBB_USE_EXCEPTIONS && _MSC_VER
    // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
    #pragma warning (push)
    #pragma warning (disable: 4530)
#endif

#include <string>

#if !TBB_USE_EXCEPTIONS && _MSC_VER
    #pragma warning (pop)
#endif

void TestComparison() {
    std::string str[3]; str[0] = "abc";
    str[1].assign("cba");
    str[2].assign("abc"); // same as 0th
    tbb::concurrent_vector<char> var[3];
    var[0].assign(str[0].begin(), str[0].end());
    var[1].assign(str[0].rbegin(), str[0].rend());
    var[2].assign(var[1].rbegin(), var[1].rend()); // same as 0th
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            ASSERT( (var[i] == var[j]) == (str[i] == str[j]), NULL );
            ASSERT( (var[i] != var[j]) == (str[i] != str[j]), NULL );
            ASSERT( (var[i] < var[j]) == (str[i] < str[j]), NULL );
            ASSERT( (var[i] > var[j]) == (str[i] > str[j]), NULL );
            ASSERT( (var[i] <= var[j]) == (str[i] <= str[j]), NULL );
            ASSERT( (var[i] >= var[j]) == (str[i] >= str[j]), NULL );
        }
    }
}

//------------------------------------------------------------------------
// Regression test for problem where on oversubscription caused
// concurrent_vector::grow_by to run very slowly (TR#196).
//------------------------------------------------------------------------

#include "tbb/task_scheduler_init.h"
#include <math.h>

typedef unsigned long Number;

static tbb::concurrent_vector<Number> Primes;

class FindPrimes {
    bool is_prime( Number val ) const {
        int limit, factor = 3;
        if( val<5u ) 
            return val==2;
        else {
            limit = long(sqrtf(float(val))+0.5f);
            while( factor<=limit && val % factor )
                ++factor;
            return factor>limit;
        }
    }
public:
    void operator()( const tbb::blocked_range<Number>& r ) const {
        for( Number i=r.begin(); i!=r.end(); ++i ) { 
            if( i%2 && is_prime(i) ) {
#if TBB_DEPRECATED
                Primes[Primes.grow_by(1)] = i;
#else
                Primes.push_back( i );
#endif
            }
        }
    }
};

double TimeFindPrimes( int nthread ) {
    Primes.clear();
    Primes.reserve(1000000);// TODO: or compact()?
    tbb::task_scheduler_init init(nthread);
    tbb::tick_count t0 = tbb::tick_count::now();
    tbb::parallel_for( tbb::blocked_range<Number>(0,1000000,500), FindPrimes() );
    tbb::tick_count t1 = tbb::tick_count::now();
    return (t1-t0).seconds();
}

void TestFindPrimes() {
    // Time fully subscribed run.
    double t2 = TimeFindPrimes( tbb::task_scheduler_init::automatic );

    // Time parallel run that is very likely oversubscribed.  
#if _XBOX
    double t128 = TimeFindPrimes(32);  //XBOX360 can't handle too many threads
#else    
    double t128 = TimeFindPrimes(128);
#endif
    REMARK("TestFindPrimes: t2==%g t128=%g k=%g\n", t2, t128, t128/t2);

    // We allow the 128-thread run a little extra time to allow for thread overhead.
    // Theoretically, following test will fail on machine with >128 processors.
    // But that situation is not going to come up in the near future,
    // and the generalization to fix the issue is not worth the trouble.
    if( t128 > 1.3*t2 ) {
        REPORT("Warning: grow_by is pathetically slow: t2==%g t128=%g k=%g\n", t2, t128, t128/t2);
    } 
}

//------------------------------------------------------------------------
// Test compatibility with STL sort.
//------------------------------------------------------------------------

#include <algorithm>

void TestSort() {
    for( int n=0; n<100; n=n*3+1 ) {
        tbb::concurrent_vector<int> array(n);
        for( int i=0; i<n; ++i )
            array.at(i) = (i*7)%n;
        std::sort( array.begin(), array.end() );
        for( int i=0; i<n; ++i )
            ASSERT( array[i]==i, NULL );
    }
}

#if TBB_USE_EXCEPTIONS
//------------------------------------------------------------------------
// Test exceptions safety (from allocator and items constructors)
//------------------------------------------------------------------------
void TestExceptions() {
    typedef static_counting_allocator<debug_allocator<FooWithAssign>, std::size_t> allocator_t;
    typedef tbb::concurrent_vector<FooWithAssign, allocator_t> vector_t;

    enum methods {
        zero_method = 0,
        ctor_copy, ctor_size, assign_nt, assign_ir, op_equ, reserve, compact, grow,
        all_methods
    };
    ASSERT( !FooCount, NULL );

    try {
        vector_t src(FooIterator(0), FooIterator(N)); // original data

        for(int t = 0; t < 2; ++t) // exception type
        for(int m = zero_method+1; m < all_methods; ++m)
        {
            ASSERT( FooCount == N, "Previous iteration miss some Foo's de-/initialization" );
            allocator_t::init_counters();
            if(t) MaxFooCount = FooCount + N/4;
            else allocator_t::set_limits(N/4);
            vector_t victim;
            try {
                switch(m) {
                case ctor_copy: {
                        vector_t acopy(src);
                    } break; // auto destruction after exception is checked by ~Foo
                case ctor_size: {
                        vector_t sized(N);
                    } break; // auto destruction after exception is checked by ~Foo
                // Do not test assignment constructor due to reusing of same methods as below 
                case assign_nt: {
                        victim.assign(N, FooWithAssign());
                    } break;
                case assign_ir: {
                        victim.assign(FooIterator(0), FooIterator(N));
                    } break;
                case op_equ: {
                        victim.reserve(2); victim = src; // fragmented assignment
                    } break;
                case reserve: {
                        try {
                            victim.reserve(victim.max_size()+1);
                        } catch(std::length_error &) {
                        } catch(...) {
                            KNOWN_ISSUE("ERROR: unrecognized exception - known compiler issue\n");
                        }
                        victim.reserve(N);
                    } break;
                case compact: {
                        if(t) MaxFooCount = 0; else allocator_t::set_limits(); // reset limits
                        victim.reserve(2); victim = src; // fragmented assignment
                        if(t) MaxFooCount = FooCount + 10; else allocator_t::set_limits(1, false); // block any allocation, check NULL return from allocator
                        victim.shrink_to_fit(); // should start defragmenting first segment
                    } break;
                case grow: {
                        tbb::task_scheduler_init init(2);
                        if(t) MaxFooCount = FooCount + 31; // these numbers help to reproduce the live lock for versions < TBB2.2
                        try {
                            tbb::parallel_for( tbb::blocked_range<int>(0, N, 70), GrowBy<vector_t>(victim) );
                        } catch(...) {
#if TBB_USE_CAPTURED_EXCEPTION
                            throw tbb::bad_last_alloc();
#else
                            throw;
#endif
                        }
                    } break;
                default:;
                }
                if(!t || m != reserve) ASSERT(false, "should throw an exception");
            } catch(std::bad_alloc &e) {
                allocator_t::set_limits(); MaxFooCount = 0;
                size_t capacity = victim.capacity();
                size_t size = victim.size();
#if TBB_DEPRECATED
                size_t req_size = victim.grow_by(0);
#else
                size_t req_size = victim.grow_by(0) - victim.begin();
#endif
                ASSERT( size <= capacity, NULL);
                ASSERT( req_size >= size, NULL);
                switch(m) {
                case reserve:
                    if(t) ASSERT(false, NULL);
                case assign_nt:
                case assign_ir:
                    if(!t) {
                        ASSERT(capacity < N/2, "unexpected capacity");
                        ASSERT(size == 0, "unexpected size");
                        break;
                    } else {
                        ASSERT(size == N, "unexpected size");
                        ASSERT(capacity >= N, "unexpected capacity");
                        int i;
                        for(i = 1; ; ++i)
                            if(!victim[i].zero_bar()) break;
                            else ASSERT(victim[i].bar() == (m == assign_ir)? i : initial_value_of_bar, NULL);
                        for(; size_t(i) < size; ++i) ASSERT(!victim[i].zero_bar(), NULL);
                        ASSERT(size_t(i) == size, NULL);
                        break;
                    }
                case grow:
                case op_equ:
                    if(!t) {
                        ASSERT(capacity > 0, NULL);
                        ASSERT(capacity < N, "unexpected capacity");
                    }
                    {
                        vector_t copy_of_victim(victim);
                        ASSERT(copy_of_victim.size() > 0, NULL);
                        for(int i = 0; ; ++i) {
                            try {
                                FooWithAssign &foo = victim.at(i);
                                if( !foo.is_valid_or_zero() ) {
                                    std::printf("i: %d size: %u req_size: %u  state: %d\n", i, unsigned(size), unsigned(req_size), foo.state);
                                }
                                int bar = foo.zero_bar();
                                if(m != grow) ASSERT( bar == i || (t && bar == 0), NULL);
                                if(size_t(i) < copy_of_victim.size()) ASSERT( copy_of_victim[i].bar() == bar, NULL);
                            } catch(std::range_error &) { // skip broken segment
                                ASSERT( size_t(i) < req_size, NULL );
                                if(m == op_equ) break;
                            } catch(std::out_of_range &){
                                ASSERT( i > 0, NULL ); break;
                            } catch(...) {
                                KNOWN_ISSUE("ERROR: unrecognized exception - known compiler issue\n"); break;
                            }
                        }
                        vector_t copy_of_victim2(10); copy_of_victim2 = victim;
                        ASSERT(copy_of_victim == copy_of_victim2, "assignment doesn't match copying");
                        if(m == op_equ) {
                            try {
                                victim = copy_of_victim2;
                            } catch(tbb::bad_last_alloc &) { break;
                            } catch(...) {
                                KNOWN_ISSUE("ERROR: unrecognized exception - known compiler issue\n"); break;
                            }
                            ASSERT(t, NULL);
                        }
                    } break;
                case compact:
                    ASSERT(capacity > 0, "unexpected capacity");
                    ASSERT(victim == src, "shrink_to_fit() is broken");
                    break;

                default:; // nothing to check here
                }
                REMARK("Exception %d: %s\t- ok\n", m, e.what());
            }
        }
    } catch(...) {
        ASSERT(false, "unexpected exception");
    }
}
#endif /* TBB_USE_EXCEPTIONS */

//------------------------------------------------------------------------
// Test SSE
//------------------------------------------------------------------------
#include "harness_m128.h"

#if HAVE_m128

void TestSSE() {
    tbb::concurrent_vector<ClassWithSSE> v;
    for( int i=0; i<100; ++i ) {
        v.push_back(ClassWithSSE(i));
        for( int j=0; i<i; ++j ) 
            ASSERT( v[j]==ClassWithSSE(j), NULL );
    }
}
#endif /* HAVE_m128 */

//------------------------------------------------------------------------

int TestMain () {
    if( MinThread<1 ) {
        REPORT("ERROR: MinThread=%d, but must be at least 1\n",MinThread); MinThread = 1;
    }
#if !TBB_DEPRECATED
    TestIteratorTraits<tbb::concurrent_vector<Foo>::iterator,Foo>();
    TestIteratorTraits<tbb::concurrent_vector<Foo>::const_iterator,const Foo>();
    TestSequentialFor<FooWithAssign> ();
    TestResizeAndCopy();
    TestAssign();
#if HAVE_m128
    TestSSE();
#endif /* HAVE_m128 */    
#endif
    TestCapacity();
    ASSERT( !FooCount, NULL );
    for( int nthread=MinThread; nthread<=MaxThread; ++nthread ) {
        tbb::task_scheduler_init init( nthread );
        TestParallelFor( nthread );
        TestConcurrentGrowToAtLeast();
        TestConcurrentGrowBy( nthread );
    }
    ASSERT( !FooCount, NULL );
#if !TBB_DEPRECATED
    TestComparison();
#if !__TBB_FLOATING_POINT_BROKEN
    TestFindPrimes();
#endif
    TestSort();
#if __TBB_THROW_ACROSS_MODULE_BOUNDARY_BROKEN
    REPORT("Known issue: exception safety test is skipped.\n");
#elif TBB_USE_EXCEPTIONS
    TestExceptions();
#endif /* TBB_USE_EXCEPTIONS */
#endif /* !TBB_DEPRECATED */
    ASSERT( !FooCount, NULL );
    REMARK("sizeof(concurrent_vector<int>) == %d\n", (int)sizeof(tbb::concurrent_vector<int>));
    return Harness::Done;
}