diff options
Diffstat (limited to 'EASTL/test/source/TestDeque.cpp')
| -rw-r--r-- | EASTL/test/source/TestDeque.cpp | 1146 |
1 files changed, 1146 insertions, 0 deletions
diff --git a/EASTL/test/source/TestDeque.cpp b/EASTL/test/source/TestDeque.cpp new file mode 100644 index 0000000..e3f4ab6 --- /dev/null +++ b/EASTL/test/source/TestDeque.cpp @@ -0,0 +1,1146 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLTest.h" +#include <EABase/eabase.h> +#include <EASTL/deque.h> +#include <EASTL/list.h> +#include <EASTL/vector.h> +#include <EASTL/string.h> +#include <EASTL/algorithm.h> +#include <EASTL/unique_ptr.h> +#include "ConceptImpls.h" + +#if !defined(EA_COMPILER_NO_STANDARD_CPP_LIBRARY) + EA_DISABLE_ALL_VC_WARNINGS() + #include <deque> + #include <list> + #include <vector> + #include <algorithm> + #include <stdio.h> + EA_RESTORE_ALL_VC_WARNINGS() +#endif + + +using namespace eastl; + + + + +/////////////////////////////////////////////////////////////////////////////// +// DequeObject +// +struct DequeObject +{ + int mX; // Value for the DequeObject. + uint32_t mMagicValue; // + static int sDOCount; // Count of all current existing DequeObjects. + static int sMagicErrorCount; // Number of magic number mismatch errors. + + DequeObject(int x = 0) : mX(x), mMagicValue(kMagicValue) + { ++sDOCount; } + + DequeObject(const DequeObject& dequeObject) : mX(dequeObject.mX), mMagicValue(kMagicValue) + { ++sDOCount; } + + DequeObject& operator=(const DequeObject& dequeObject) + { + mX = dequeObject.mX; + return *this; + } + + ~DequeObject() + { + if(mMagicValue != kMagicValue) + ++sMagicErrorCount; + mMagicValue = 0; + --sDOCount; + } +}; + +int DequeObject::sDOCount = 0; +int DequeObject::sMagicErrorCount = 0; + + +bool operator==(const DequeObject& de1, const DequeObject& de2) + { return de1.mX == de2.mX; } + +bool operator<(const DequeObject& de1, const DequeObject& de2) + { return de1.mX < de2.mX; } +/////////////////////////////////////////////////////////////////////////////// + + + +// Template instantations. +// These tell the compiler to compile all the functions for the given class. +template class eastl::deque<int>; +template class eastl::deque<DequeObject>; + + +// Test compiler issue that appeared in VS2012 relating to deque::kAlignment. +struct StructWithContainerOfStructs +{ + eastl::deque<StructWithContainerOfStructs, EASTLAllocatorType, 16> children; +}; + +// The following will not compile because the default value of kDequeSubarraySize +// relies on sizeof(T). Thus, a non-default value must be provided, or the full type +// will be required at the time of instantiation, but it is not available. +// struct StructWithContainerOfStructsDefault +// { +// eastl::deque<StructWithContainerOfStructsDefault> children; +// }; + + +/////////////////////////////////////////////////////////////////////////////// +typedef eastl::deque<int> EIntDeque; +typedef eastl::deque<int, EASTLAllocatorType, 1> EIntDeque1; +typedef eastl::deque<int, EASTLAllocatorType, 32768> EIntDeque32768; + + +typedef eastl::deque<DequeObject> EDODeque; +typedef eastl::deque<DequeObject, EASTLAllocatorType, 1> EDODeque1; +typedef eastl::deque<DequeObject, EASTLAllocatorType, 32768> EDODeque32768; + + +#ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + typedef std::deque<int> SIntDeque; + typedef std::deque<DequeObject> SDODeque; +#endif +/////////////////////////////////////////////////////////////////////////////// + + + +#ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + + +template <typename D1, typename D2> +int CompareDeques(const D1& d1, const D2& d2, const char* pTestName) +{ + int nErrorCount = 0; + + // Compare emptiness. + VERIFY(d1.empty() == d2.empty()); + + // Compare sizes. + const size_t nSize1 = d1.size(); + const size_t nSize2 = d2.size(); + + VERIFY(nSize1 == nSize2); + if(nSize1 != nSize2) + EASTLTest_Printf("%s: Deque size difference: %u, %u", pTestName, (unsigned)nSize1, (unsigned)nSize2); + + // Compare values. + if(nSize1 == nSize2) + { + // Test operator[] + for(unsigned i = 0; i < nSize1; i++) + { + const typename D1::value_type& t1 = d1[i]; + const typename D2::value_type& t2 = d2[i]; + + VERIFY(t1 == t2); + if(!(t1 == t2)) + { + EASTLTest_Printf("%s: Deque index difference at index %d", pTestName, i); + break; + } + } + + // Test iteration + typename D1::const_iterator it1 = d1.begin(); + typename D2::const_iterator it2 = d2.begin(); + + for(unsigned j = 0; it1 != d1.end(); ++it1, ++it2, ++j) + { + const typename D1::value_type& t1 = *it1; + const typename D2::value_type& t2 = *it2; + + VERIFY(t1 == t2); + if(!(t1 == t2)) + { + EASTLTest_Printf("%s: Deque iterator difference at index %d", pTestName, j); + break; + } + } + + // Test reverse iteration + typename D1::const_reverse_iterator itr1 = d1.rbegin(); + typename D2::const_reverse_iterator itr2 = d2.rbegin(); + + for(typename D1::size_type j = d1.size() - 1; itr1 != d1.rend(); ++itr1, ++itr2, --j) + { + const typename D1::value_type& t1 = *itr1; + const typename D2::value_type& t2 = *itr2; + + VERIFY(t1 == t2); + if(!(t1 == t2)) + { + EASTLTest_Printf("%s: Deque reverse iterator difference at index %u", pTestName, (unsigned)j); + break; + } + } + } + + return nErrorCount; +} + + + +/////////////////////////////////////////////////////////////////////////////// +// TestDequeConstruction +// +template <typename D1, typename D2> +int TestDequeConstruction() +{ + int nErrorCount = 0; + + { + D1 d1A; + D2 d2A; + nErrorCount += CompareDeques(d1A, d2A, "Deque ctor"); + + D1 d1B((typename D1::size_type)0); + D2 d2B((typename D2::size_type)0); + nErrorCount += CompareDeques(d1B, d2B, "Deque ctor"); + + D1 d1C(1000); + D2 d2C(1000); + nErrorCount += CompareDeques(d1C, d2C, "Deque ctor"); + + D1 d1D(2000, 1); + D2 d2D(2000, 1); + nErrorCount += CompareDeques(d1D, d2D, "Deque ctor"); + + D1 d1E(d1C); + D2 d2E(d2C); + nErrorCount += CompareDeques(d1E, d2E, "Deque ctor"); + + D1 d1F(d1C.begin(), d1C.end()); + D2 d2F(d2C.begin(), d2C.end()); + nErrorCount += CompareDeques(d1F, d2F, "Deque ctor"); + + // operator= + d1E = d1D; + d2E = d2D; + nErrorCount += CompareDeques(d1D, d2D, "Deque operator="); + nErrorCount += CompareDeques(d1E, d2E, "Deque operator="); + + // swap + d1E.swap(d1D); + d2E.swap(d2D); + nErrorCount += CompareDeques(d1D, d2D, "Deque swap"); + nErrorCount += CompareDeques(d1E, d2E, "Deque swap"); + + // clear + d1A.clear(); + d2A.clear(); + nErrorCount += CompareDeques(d1A, d2A, "Deque clear"); + + d1B.clear(); + d2B.clear(); + nErrorCount += CompareDeques(d1B, d2B, "Deque clear"); + } + + VERIFY(DequeObject::sDOCount == 0); + VERIFY(DequeObject::sMagicErrorCount == 0); + + return nErrorCount; +} + + + +/////////////////////////////////////////////////////////////////////////////// +// TestDequeSimpleMutation +// +template <typename D1, typename D2> +int TestDequeSimpleMutation() +{ + int nErrorCount = 0; + + { + D1 d1; + D2 d2; + + // push_back(value_type&) + // front + // back + for(int i = 0; i < 1000; i++) + { + d1.push_back(i); + d2.push_back(i); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque push_back(value_type&)"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // push_back() + for(int i = 0; i < 1000; i++) + { + d1.push_back(int()); + typename D2::value_type& ref = d2.push_back(); // d2 here must be the EASTL version. + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + VERIFY(&ref == &d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque push_back()"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // push_front(value_type&) + for(int i = 0; i < 1000; i++) + { + d1.push_front(i); + d2.push_front(i); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque push_front(value_type&)"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // push_front() + for(int i = 0; i < 1000; i++) + { + d1.push_front(int()); + typename D2::value_type& ref = d2.push_front(); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + VERIFY(&ref == &d2.front()); + } + nErrorCount += CompareDeques(d1, d2, "Deque push_front()"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // pop_back() + for(int i = 0; i < 500; i++) + { + d1.pop_back(); + d2.pop_back(); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque pop_back()"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // pop_front() + for(int i = 0; i < 500; i++) + { + d1.pop_front(); + d2.pop_front(); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque pop_front()"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // resize(value_type&) + for(int i = 0; i < 500; i++) + { + d1.resize(d1.size() + 3, i); + d2.resize(d2.size() + 3, i); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque resize(value_type&)"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + + // resize() + for(int i = 0; i < 500; i++) + { + d1.resize(d1.size() - 2); + d2.resize(d2.size() - 2); + VERIFY(d1.front() == d2.front()); + VERIFY(d1.back() == d2.back()); + } + nErrorCount += CompareDeques(d1, d2, "Deque resize()"); + + // operator[] + // at() + for(typename D1::size_type i = 0, iEnd = d1.size(); i < iEnd; i++) + { + VERIFY(d1[(unsigned)i] == d2[(unsigned)i]); + VERIFY(d1.at((unsigned)i) == d2.at((unsigned)i)); + } + } + + VERIFY(DequeObject::sDOCount == 0); + VERIFY(DequeObject::sMagicErrorCount == 0); + + return nErrorCount; +} + + + +/////////////////////////////////////////////////////////////////////////////// +// TestDequeComplexMutation +// +template <typename D1, typename D2> +int TestDequeComplexMutation() +{ + int nErrorCount = 0; + + { + D1 d1; + D2 d2; + + + ////////////////////////////////////////////////////////////////// + // void assign(size_type n, const value_type& value); + ////////////////////////////////////////////////////////////////// + + d1.assign(100, 1); + d2.assign(100, 1); + nErrorCount += CompareDeques(d1, d2, "Deque assign(size_type n, const value_type& value)"); + + d1.assign(50, 2); + d2.assign(50, 2); + nErrorCount += CompareDeques(d1, d2, "Deque assign(size_type n, const value_type& value)"); + + d1.assign(150, 2); + d2.assign(150, 2); + nErrorCount += CompareDeques(d1, d2, "Deque assign(size_type n, const value_type& value)"); + + + + ////////////////////////////////////////////////////////////////// + // template <typename InputIterator> + // void assign(InputIterator first, InputIterator last); + ////////////////////////////////////////////////////////////////// + + std::list<int> intList1; + for(int i = 0; i < 100; i++) + intList1.push_back(i); + + eastl::list<int> intList2; + for(int i = 0; i < 100; i++) + intList2.push_back(i); + + d1.assign(intList1.begin(), intList1.end()); + d2.assign(intList2.begin(), intList2.end()); + nErrorCount += CompareDeques(d1, d2, "Deque assign(InputIterator first, InputIterator last)"); + + + + ////////////////////////////////////////////////////////////////// + // iterator insert(iterator position, const value_type& value); + ////////////////////////////////////////////////////////////////// + + d1.insert(d1.begin(), d1[1]); + d2.insert(d2.begin(), d2[1]); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, const value_type& value)"); + + d1.insert(d1.end(), d1[d1.size() - 2]); + d2.insert(d2.end(), d2[d2.size() - 2]); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, const value_type& value)"); + + typename D1::iterator itD1NearBegin = d1.begin(); + typename D2::iterator itD2NearBegin = d2.begin(); + + std::advance(itD1NearBegin, 1); + eastl::advance(itD2NearBegin, 1); + + d1.insert(itD1NearBegin, d1[3]); + d2.insert(itD2NearBegin, d2[3]); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, const value_type& value)"); + + typename D1::iterator itD1NearEnd = d1.begin(); + typename D2::iterator itD2NearEnd = d2.begin(); + + std::advance(itD1NearEnd, d1.size() - 1); + eastl::advance(itD2NearEnd, d2.size() - 1); + + d1.insert(itD1NearEnd, d1[d1.size() - 2]); + d2.insert(itD2NearEnd, d2[d2.size() - 2]); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, const value_type& value)"); + + + ////////////////////////////////////////////////////////////////// + // void insert(iterator position, size_type n, const value_type& value); + ////////////////////////////////////////////////////////////////// + + d1.insert(d1.begin(), d1.size() * 2, 3); // Insert a large number of items at the front. + d2.insert(d2.begin(), d2.size() * 2, 3); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, size_type n, const value_type& value)"); + + d1.insert(d1.end(), d1.size() * 2, 3); // Insert a large number of items at the end. + d2.insert(d2.end(), d2.size() * 2, 3); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, size_type n, const value_type& value)"); + + itD1NearBegin = d1.begin(); + itD2NearBegin = d2.begin(); + + std::advance(itD1NearBegin, 3); + eastl::advance(itD2NearBegin, 3); + + d1.insert(itD1NearBegin, 3, 4); + d2.insert(itD2NearBegin, 3, 4); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, size_type n, const value_type& value)"); + + itD1NearEnd = d1.begin(); + itD2NearEnd = d2.begin(); + + std::advance(itD1NearEnd, d1.size() - 1); + eastl::advance(itD2NearEnd, d2.size() - 1); + + d1.insert(d1.end(), 5, 6); + d2.insert(d2.end(), 5, 6); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, size_type n, const value_type& value)"); + + + + ////////////////////////////////////////////////////////////////// + // template <typename InputIterator> + // void insert(iterator position, InputIterator first, InputIterator last); + ////////////////////////////////////////////////////////////////// + + itD1NearBegin = d1.begin(); + itD2NearBegin = d2.begin(); + + std::advance(itD1NearBegin, 3); + eastl::advance(itD2NearBegin, 3); + + d1.insert(itD1NearBegin, intList1.begin(), intList1.end()); + d2.insert(itD2NearBegin, intList2.begin(), intList2.end()); + nErrorCount += CompareDeques(d1, d2, "Deque insert(iterator position, InputIterator first, InputIterator last)"); + + + + ////////////////////////////////////////////////////////////////// + // iterator erase(iterator position); + ////////////////////////////////////////////////////////////////// + + itD1NearBegin = d1.begin(); + itD2NearBegin = d2.begin(); + + while(itD1NearBegin != d1.end()) // Run a loop whereby we erase every third element. + { + for(int i = 0; (i < 3) && (itD1NearBegin != d1.end()); ++i) + { + ++itD1NearBegin; + ++itD2NearBegin; + } + + if(itD1NearBegin != d1.end()) + { + itD1NearBegin = d1.erase(itD1NearBegin); + itD2NearBegin = d2.erase(itD2NearBegin); + nErrorCount += CompareDeques(d1, d2, "Deque erase(iterator position)"); + } + } + + + ////////////////////////////////////////////////////////////////// + // iterator erase(iterator first, iterator last); + ////////////////////////////////////////////////////////////////// + + itD1NearBegin = d1.begin(); + itD2NearBegin = d2.begin(); + + while(itD1NearBegin != d1.end()) // Run a loop whereby we erase spans of elements. + { + typename D1::iterator itD1Saved = itD1NearBegin; + typename D2::iterator itD2Saved = itD2NearBegin; + + for(int i = 0; (i < 11) && (itD1NearBegin != d1.end()); ++i) + { + ++itD1NearBegin; + ++itD2NearBegin; + } + + if(itD1NearBegin != d1.end()) + { + itD1NearBegin = d1.erase(itD1Saved, itD1NearBegin); + itD2NearBegin = d2.erase(itD2Saved, itD2NearBegin); + nErrorCount += CompareDeques(d1, d2, "Deque erase(iterator position)"); + } + + for(int i = 0; (i < 17) && (itD1NearBegin != d1.end()); ++i) + { + ++itD1NearBegin; + ++itD2NearBegin; + } + + } + + } + + + { + ////////////////////////////////////////////////////////////////// + // reverse_iterator erase(reverse_iterator position); + // reverse_iterator erase(reverse_iterator first, reverse_iterator last); + ////////////////////////////////////////////////////////////////// + + //D1 d1Erase; + D2 d2Erase; + + for(int i = 0; i < 20; i++) + { + typename D2::value_type val(i); + d2Erase.push_back(val); + } + VERIFY((d2Erase.size() == 20) && (d2Erase[0] == 0) && (d2Erase[19] == 19)); + + + typename D2::reverse_iterator r2A = d2Erase.rbegin(); + typename D2::reverse_iterator r2B = r2A + 3; + d2Erase.erase(r2A, r2B); + VERIFY((d2Erase.size() == 17)); + VERIFY((d2Erase[0] == 0)); + VERIFY((d2Erase[16] == 16)); + + + r2B = d2Erase.rend(); + r2A = r2B - 3; + d2Erase.erase(r2A, r2B); + VERIFY((d2Erase.size() == 14)); + VERIFY((d2Erase[0] == 3)); + VERIFY((d2Erase[13] == 16)); + + + r2B = d2Erase.rend() - 1; + d2Erase.erase(r2B); + VERIFY((d2Erase.size() == 13)); + VERIFY((d2Erase[0] == 4)); + VERIFY((d2Erase[12] == 16)); + + + r2B = d2Erase.rbegin(); + d2Erase.erase(r2B); + VERIFY((d2Erase.size() == 12)); + VERIFY((d2Erase[0] == 4)); + VERIFY((d2Erase[11] == 15)); + + + r2A = d2Erase.rbegin(); + r2B = d2Erase.rend(); + d2Erase.erase(r2A, r2B); + VERIFY(d2Erase.size() == 0); + } + + + VERIFY(DequeObject::sDOCount == 0); + VERIFY(DequeObject::sMagicErrorCount == 0); + + return nErrorCount; +} + +#endif // EA_COMPILER_NO_STANDARD_CPP_LIBRARY + + +int TestDeque() +{ + int nErrorCount = 0; + + #ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + { // Test construction + nErrorCount += TestDequeConstruction<SIntDeque, EIntDeque>(); + nErrorCount += TestDequeConstruction<SIntDeque, EIntDeque1>(); + nErrorCount += TestDequeConstruction<SIntDeque, EIntDeque32768>(); + + nErrorCount += TestDequeConstruction<SIntDeque, EDODeque>(); + nErrorCount += TestDequeConstruction<SIntDeque, EDODeque1>(); + nErrorCount += TestDequeConstruction<SIntDeque, EDODeque32768>(); + } + + + { // Test simple mutating functionality. + nErrorCount += TestDequeSimpleMutation<SIntDeque, EIntDeque>(); + nErrorCount += TestDequeSimpleMutation<SIntDeque, EIntDeque1>(); + nErrorCount += TestDequeSimpleMutation<SIntDeque, EIntDeque32768>(); + + nErrorCount += TestDequeSimpleMutation<SIntDeque, EDODeque>(); + nErrorCount += TestDequeSimpleMutation<SIntDeque, EDODeque1>(); + nErrorCount += TestDequeSimpleMutation<SIntDeque, EDODeque32768>(); + } + + { // Test complex mutating functionality. + nErrorCount += TestDequeComplexMutation<SIntDeque, EIntDeque>(); + nErrorCount += TestDequeComplexMutation<SIntDeque, EIntDeque1>(); + nErrorCount += TestDequeComplexMutation<SIntDeque, EIntDeque32768>(); + + nErrorCount += TestDequeComplexMutation<SIntDeque, EDODeque>(); + nErrorCount += TestDequeComplexMutation<SIntDeque, EDODeque1>(); + nErrorCount += TestDequeComplexMutation<SIntDeque, EDODeque32768>(); + } + #endif // EA_COMPILER_NO_STANDARD_CPP_LIBRARY + + // test deque support of move-only types + { + { + eastl::deque<MoveAssignable> d; + d.emplace_back(MoveAssignable::Create()); + d.emplace_front(MoveAssignable::Create()); + + auto cd = eastl::move(d); + EATEST_VERIFY( d.size() == 0); + EATEST_VERIFY(cd.size() == 2); + } + + { + // User regression but passing end() to deque::erase is not valid. + // Iterator passed to deque::erase but must valid and dereferencable. + // + // eastl::deque<MoveAssignable> d; // empty deque + // d.erase(d.begin()); + // EATEST_VERIFY(d.size() == 0); + } + + // simply test the basic api of deque with a move-only type + { + eastl::deque<MoveAssignable> d; + + // emplace_back + d.emplace_back(MoveAssignable::Create()); + d.emplace_back(MoveAssignable::Create()); + d.emplace_back(MoveAssignable::Create()); + + // erase + d.erase(d.begin()); + EATEST_VERIFY(d.size() == 2); + + // at / front / back / operator[] + EATEST_VERIFY(d[0].value == 42); + EATEST_VERIFY(d.at(0).value == 42); + EATEST_VERIFY(d.front().value == 42); + EATEST_VERIFY(d.back().value == 42); + + // clear + d.clear(); + EATEST_VERIFY(d.size() == 0); + + // emplace + d.emplace(d.begin(), MoveAssignable::Create()); + d.emplace(d.begin(), MoveAssignable::Create()); + EATEST_VERIFY(d.size() == 2); + + // pop_back + d.pop_back(); + EATEST_VERIFY(d.size() == 1); + + // push_back / push_front / resize requires T be 'CopyConstructible' + + { + eastl::deque<MoveAssignable> swapped_d; + + // emplace_front + swapped_d.emplace_front(MoveAssignable::Create()); + swapped_d.emplace_front(MoveAssignable::Create()); + swapped_d.emplace_front(MoveAssignable::Create()); + + // swap + swapped_d.swap(d); + EATEST_VERIFY(swapped_d.size() == 1); + EATEST_VERIFY(d.size() == 3); + } + + // pop_front + d.pop_front(); + EATEST_VERIFY(d.size() == 2); + + // insert + d.insert(d.end(), MoveAssignable::Create()); + EATEST_VERIFY(d.size() == 3); + } + } + + { + // deque(std::initializer_list<value_type> ilist, const allocator_type& allocator = EASTL_DEQUE_DEFAULT_ALLOCATOR); + // this_type& operator=(std::initializer_list<value_type> ilist); + // void assign(std::initializer_list<value_type> ilist); + // iterator insert(iterator position, std::initializer_list<value_type> ilist); + #if !defined(EA_COMPILER_NO_INITIALIZER_LISTS) + eastl::deque<int> intDeque = { 0, 1, 2 }; + EATEST_VERIFY(VerifySequence(intDeque.begin(), intDeque.end(), int(), "deque std::initializer_list", 0, 1, 2, -1)); + + intDeque = { 13, 14, 15 }; + EATEST_VERIFY(VerifySequence(intDeque.begin(), intDeque.end(), int(), "deque std::initializer_list", 13, 14, 15, -1)); + + intDeque.assign({ 16, 17, 18 }); + EATEST_VERIFY(VerifySequence(intDeque.begin(), intDeque.end(), int(), "deque std::initializer_list", 16, 17, 18, -1)); + + eastl::deque<int>::iterator it = intDeque.insert(intDeque.begin(), { 14, 15 }); + EATEST_VERIFY(VerifySequence(intDeque.begin(), intDeque.end(), int(), "deque std::initializer_list", 14, 15, 16, 17, 18, -1)); + EATEST_VERIFY(*it == 14); + #endif + } + + + { // C++11 functionality + // deque(this_type&& x); + // deque(this_type&& x, const allocator_type& allocator); + // this_type& operator=(this_type&& x); + // void push_front(value_type&& value); + // void push_back(value_type&& value); + // iterator insert(const_iterator position, value_type&& value); + + using namespace eastl; + + deque<TestObject> deque3TO33(3, TestObject(33)); + deque<TestObject> toDequeA(eastl::move(deque3TO33)); + EATEST_VERIFY((toDequeA.size() == 3) && (toDequeA.front().mX == 33) && (deque3TO33.size() == 0)); + + // The following is not as strong a test of this ctor as it could be. A stronger test would be to use IntanceAllocator with different instances. + deque<TestObject, MallocAllocator> deque4TO44(4, TestObject(44)); + deque<TestObject, MallocAllocator> toDequeB(eastl::move(deque4TO44), MallocAllocator()); + EATEST_VERIFY((toDequeB.size() == 4) && (toDequeB.front().mX == 44) && (deque4TO44.size() == 0)); + + deque<TestObject, MallocAllocator> deque5TO55(5, TestObject(55)); + toDequeB = eastl::move(deque5TO55); + EATEST_VERIFY((toDequeB.size() == 5) && (toDequeB.front().mX == 55) && (deque5TO55.size() == 0)); + } + + + { // C++11 functionality + // template<class... Args> + // iterator emplace(const_iterator position, Args&&... args); + + // template<class... Args> + // void emplace_front(Args&&... args); + + // template<class... Args> + // void emplace_back(Args&&... args); + TestObject::Reset(); + + deque<TestObject, eastl::allocator, 16> toDequeA; + + toDequeA.emplace_back(2, 3, 4); + EATEST_VERIFY_F((toDequeA.size() == 1) && (toDequeA.back().mX == (2+3+4)) && (TestObject::sTOCtorCount == 1), "size: %u, mX: %u, count: %d", (unsigned)toDequeA.size(), (unsigned)toDequeA.back().mX, (int)TestObject::sTOCtorCount); + + toDequeA.emplace(toDequeA.begin(), 3, 4, 5); // This is 3 because of how subarray allocation works. + EATEST_VERIFY_F((toDequeA.size() == 2) && (toDequeA.front().mX == (3+4+5)) && (TestObject::sTOCtorCount == 3), "size: %u, mX: %u, count: %d", (unsigned)toDequeA.size(), (unsigned)toDequeA.front().mX, (int)TestObject::sTOCtorCount); + + toDequeA.emplace_front(6, 7, 8); + EATEST_VERIFY_F((toDequeA.size() == 3) && (toDequeA.front().mX == (6+7+8)) && (TestObject::sTOCtorCount == 4), "size: %u, mX: %u, count: %d", (unsigned)toDequeA.size(), (unsigned)toDequeA.front().mX, (int)TestObject::sTOCtorCount); + + + // This test is similar to the emplace pathway above. + TestObject::Reset(); + + //void push_front(T&& x); + //void push_back(T&& x); + //iterator insert(const_iterator position, T&& x); + + deque<TestObject, eastl::allocator, 16> toDequeC; // Specify a non-small kSubarrayCount of 16 because the move count tests below assume there is no reallocation. + + toDequeC.push_back(TestObject(2, 3, 4)); + EATEST_VERIFY((toDequeC.size() == 1) && (toDequeC.back().mX == (2+3+4)) && (TestObject::sTOMoveCtorCount == 1)); + + toDequeC.insert(toDequeC.begin(), TestObject(3, 4, 5)); + EATEST_VERIFY((toDequeC.size() == 2) && (toDequeC.front().mX == (3+4+5)) && (TestObject::sTOMoveCtorCount == 3)); + + toDequeC.push_front(TestObject(6, 7, 8)); + EATEST_VERIFY((toDequeC.size() == 3) && (toDequeC.front().mX == (6+7+8)) && (TestObject::sTOMoveCtorCount == 4)); + } + + + { + // Regression of deque::operator= for the case of EASTL_ALLOCATOR_COPY_ENABLED=1 + // For this test we need to use InstanceAllocator to create two containers of the same + // type but with different and unequal allocator instances. The bug was that when + // EASTL_ALLOCATOR_COPY_ENABLED was enabled operator=(this_type& x) assigned x.mAllocator + // to this and then proceeded to assign member elements from x to this. That's invalid + // because the existing elements of this were allocated by a different allocator and + // will be freed in the future with the allocator copied from x. + // The test below should work for the case of EASTL_ALLOCATOR_COPY_ENABLED == 0 or 1. + InstanceAllocator::reset_all(); + + InstanceAllocator ia0((uint8_t)0); + InstanceAllocator ia1((uint8_t)1); + + eastl::deque<int, InstanceAllocator> v0((eastl_size_t)1, (int)0, ia0); + eastl::deque<int, InstanceAllocator> v1((eastl_size_t)1, (int)1, ia1); + + EATEST_VERIFY((v0.front() == 0) && (v1.front() == 1)); + #if EASTL_ALLOCATOR_COPY_ENABLED + EATEST_VERIFY(v0.get_allocator() != v1.get_allocator()); + #endif + v0 = v1; + EATEST_VERIFY((v0.front() == 1) && (v1.front() == 1)); + EATEST_VERIFY(InstanceAllocator::mMismatchCount == 0); + EATEST_VERIFY(v0.validate()); + EATEST_VERIFY(v1.validate()); + #if EASTL_ALLOCATOR_COPY_ENABLED + EATEST_VERIFY(v0.get_allocator() == v1.get_allocator()); + #endif + } + + + { // Regression of kDequeSubarraySize calculations + VERIFY(EIntDeque::kSubarraySize >= 4); + VERIFY(EIntDeque1::kSubarraySize == 1); + VERIFY(EIntDeque32768::kSubarraySize == 32768); + + VERIFY(EDODeque::kSubarraySize >= 2); + VERIFY(EDODeque1::kSubarraySize == 1); + VERIFY(EDODeque32768::kSubarraySize == 32768); + } + + + { // Regression of user-reported bug + + // The following was reported by Nicolas Mercier on April 9, 2008 as causing a crash: + // This code breaks on our machines because it overwrites the + // first 4 bytes before the beginning of the memory that was + // allocated for mpPtrArray. So when temp goes out of scope, + // it will free this pointer and the debug allocator will detect + // that these bytes have been changed. + + eastl::deque<eastl::string> testArray; + eastl::string s("a"); + + for(int j = 0; j < 65; j++) + testArray.push_back(s); + + eastl::deque<eastl::string> temp; + temp = testArray; // This is where the corruption occurred. + } + + + { // Regression of user-reported bug + + // The problem is that the pointer arrays on the deques are growing without bound. + // This is causing our game to crash on a soak test due to its frame event queues + // consuming inordinate amounts of memory. It looks like the current version of + // eastl::deque is missing logic to recenter the pointer array, so it keeps growing + // slowly as blocks are allocated on the tail and removed from the head. + // Note: This bug was introduced by the (mistaken) fix for April 9 bug above. + + eastl::deque<int, MallocAllocator> x; + eastl::deque<int, MallocAllocator> y; + + const MallocAllocator& maX = x.get_allocator(); + const MallocAllocator& maY = y.get_allocator(); + + size_t allocVolumeX1 = 0; + size_t allocVolumeY1 = 0; + size_t allocVolumeX2 = 0; + size_t allocVolumeY2 = 0; + + for(int i = 0; i < 1001; ++i) // With the bug, each time through this loop the containers mistakenly allocate more memory. + { + if(i == 100) // Save the allocated volume after 50 iterations. + { + allocVolumeX1 = maX.mAllocVolume; + allocVolumeY1 = maY.mAllocVolume; + } + + for(int j = 0; j < 5; ++j) + x.push_back(0); + + x.swap(y); + + while(!x.empty()) + x.pop_front(); + } + + allocVolumeX2 = maX.mAllocVolume; // Save the allocated volume after 1001 iterations. + allocVolumeY2 = maY.mAllocVolume; + + VERIFY((allocVolumeX1 == allocVolumeX2) && (allocVolumeX2 < 350)); // Test that the volume has not changed and is below some nominal value. + VERIFY((allocVolumeY1 == allocVolumeY2) && (allocVolumeY2 < 350)); // This value is somewhat arbitrary and slightly hardware dependent (e.g. 32 vs. 64 bit). I bumped it up from 300 to 350 when Linux64 showed it to be 320, which was ~still OK. + } + + + { // Regression of user error report for the case of deque<const type>. + eastl::vector<int> ctorValues; + + for(int v = 0; v < 10; v++) + ctorValues.push_back(v); + + eastl::deque<const ConstType> testStruct(ctorValues.begin(), ctorValues.end()); + eastl::deque<const int> testInt(ctorValues.begin(), ctorValues.end()); + } + + + { // Regression to verify that const deque works. + const eastl::deque<int> constIntDeque1; + VERIFY(constIntDeque1.empty()); + + int intArray[3] = { 37, 38, 39 }; + const eastl::deque<int> constIntDeque2(intArray, intArray + 3); + VERIFY(constIntDeque2.size() == 3); + + const eastl::deque<int> constIntDeque3(4, 37); + VERIFY(constIntDeque3.size() == 4); + + const eastl::deque<int> constIntDeque4; + const eastl::deque<int> constIntDeque5 = constIntDeque4; + } + + { + // test shrink_to_fit + eastl::deque<int, CountingAllocator> d(4096); + d.erase(d.begin(), d.end()); + + auto prev = d.get_allocator().getActiveAllocationSize(); + d.shrink_to_fit(); + VERIFY(d.get_allocator().getActiveAllocationSize() < prev); + } + + { + #ifndef EASTL_OPENSOURCE + auto prevAllocCount = gEASTLTest_AllocationCount; + #endif + { + EA_DISABLE_VC_WARNING(4625 4626) + struct a + { + a(int* p) + : ptr(p) { } + + eastl::unique_ptr<int> ptr; + }; + EA_RESTORE_VC_WARNING() + + static_assert(eastl::has_trivial_relocate<a>::value == false, "failure"); + + eastl::deque<a> d; + + d.emplace_back(new int(1)); + d.emplace_back(new int(2)); + d.emplace_back(new int(3)); + + d.erase(d.begin() + 1); + } + #ifndef EASTL_OPENSOURCE + VERIFY(gEASTLTest_AllocationCount == prevAllocCount); + #endif + } + + + { // Test erase / erase_if + { + eastl::deque<int> d = {1, 2, 3, 4, 5, 6, 7, 8, 9}; + + auto numErased = eastl::erase(d, 2); + VERIFY((d == eastl::deque<int>{1, 3, 4, 5, 6, 7, 8, 9})); + VERIFY(numErased == 1); + + numErased = eastl::erase(d, 7); + VERIFY((d == eastl::deque<int>{1, 3, 4, 5, 6, 8, 9})); + VERIFY(numErased == 1); + + numErased = eastl::erase(d, 9); + VERIFY((d == eastl::deque<int>{1, 3, 4, 5, 6, 8})); + VERIFY(numErased == 1); + + numErased = eastl::erase(d, 5); + VERIFY((d == eastl::deque<int>{1, 3, 4, 6, 8})); + VERIFY(numErased == 1); + + numErased = eastl::erase(d, 3); + VERIFY((d == eastl::deque<int>{1, 4, 6, 8})); + VERIFY(numErased == 1); + } + + { + eastl::deque<int> d = {1, 2, 3, 4, 5, 6, 7, 8, 9}; + auto numErased = eastl::erase_if(d, [](auto i) { return i % 2 == 0; }); + VERIFY((d == eastl::deque<int>{1, 3, 5, 7, 9})); + VERIFY(numErased == 4); + } + } + +#if defined(EA_COMPILER_HAS_THREE_WAY_COMPARISON) + + { // Test <=> + eastl::deque<int> d1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}; + eastl::deque<int> d2 = {9, 8, 7, 6, 5, 4, 3, 2, 1}; + eastl::deque<int> d3 = {1, 2, 3, 4, 5}; + eastl::deque<int> d4 = {10}; + + VERIFY(d1 != d2); + VERIFY(d1 < d2); + VERIFY(d1 != d3); + VERIFY(d1 > d3); + VERIFY(d4 > d1); + VERIFY(d4 > d2); + VERIFY(d4 > d3); + + VERIFY((d1 <=> d2) != 0); + VERIFY((d1 <=> d2) < 0); + VERIFY((d1 <=> d3) != 0); + VERIFY((d1 <=> d3) > 0); + VERIFY((d4 <=> d1) > 0); + VERIFY((d4 <=> d2) > 0); + VERIFY((d4 <=> d3) > 0); + } +#endif + + return nErrorCount; +} + + + + + + + + + + + + + + + + + + + + + + + + |