mirror of
https://github.com/grumpycoders/pcsx-redux.git
synced 2025-04-02 10:41:54 -04:00
1114 lines
32 KiB
C++
1114 lines
32 KiB
C++
/////////////////////////////////////////////////////////////////////////////
|
|
// 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};
|
|
|
|
eastl::erase(d, 2);
|
|
VERIFY((d == eastl::deque<int>{1, 3, 4, 5, 6, 7, 8, 9}));
|
|
|
|
eastl::erase(d, 7);
|
|
VERIFY((d == eastl::deque<int>{1, 3, 4, 5, 6, 8, 9}));
|
|
|
|
eastl::erase(d, 9);
|
|
VERIFY((d == eastl::deque<int>{1, 3, 4, 5, 6, 8}));
|
|
|
|
eastl::erase(d, 5);
|
|
VERIFY((d == eastl::deque<int>{1, 3, 4, 6, 8}));
|
|
|
|
eastl::erase(d, 3);
|
|
VERIFY((d == eastl::deque<int>{1, 4, 6, 8}));
|
|
}
|
|
|
|
{
|
|
eastl::deque<int> d = {1, 2, 3, 4, 5, 6, 7, 8, 9};
|
|
eastl::erase_if(d, [](auto i) { return i % 2 == 0; });
|
|
VERIFY((d == eastl::deque<int>{1, 3, 5, 7, 9}));
|
|
}
|
|
}
|
|
|
|
return nErrorCount;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|