aboutsummaryrefslogtreecommitdiff
path: root/test/source/TestHeap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'test/source/TestHeap.cpp')
-rw-r--r--test/source/TestHeap.cpp295
1 files changed, 0 insertions, 295 deletions
diff --git a/test/source/TestHeap.cpp b/test/source/TestHeap.cpp
deleted file mode 100644
index 4709ecf..0000000
--- a/test/source/TestHeap.cpp
+++ /dev/null
@@ -1,295 +0,0 @@
-/////////////////////////////////////////////////////////////////////////////
-// Copyright (c) Electronic Arts Inc. All rights reserved.
-/////////////////////////////////////////////////////////////////////////////
-
-
-#include "EASTLTest.h"
-#include <EASTL/heap.h>
-#include <EASTL/vector.h>
-#include <EASTL/algorithm.h>
-#include <EASTL/sort.h>
-#include <EABase/eabase.h>
-#include <algorithm> //std::pop_heap
-
-#ifdef _MSC_VER
- #pragma warning(push, 0)
-#endif
-
-#ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY
- #include <algorithm>
-#endif
-
-#if defined(_MSC_VER)
- #pragma warning(pop)
-#endif
-
-
-using namespace eastl;
-
-
-
-
-int VerifyHeaps(uint32_t* pArray2, uint32_t* pArray3, uint32_t nArraySize)
-{
- int nErrorCount = 0;
- bool bResult;
-
- bResult = is_heap(pArray2, pArray2 + nArraySize);
- EATEST_VERIFY(bResult);
-
- bResult = is_heap(pArray3, pArray3 + nArraySize);
- EATEST_VERIFY(bResult);
-
- // bResult = (memcmp(pArray2, pArray3, nArraySize * sizeof(uint32_t)) == 0);
- // EATEST_VERIFY(bResult);
- //
- // The above does not work on iOS since CM added -stdlib=libc++ to the linker switch
- // even though it was already used in our compile switches.
- // It would appear that on clang or iOS the heap is actually structured in a unique way,
- // possibly for optimization. Iterating over the array and using pop_heap verifies
- // that the heaps have the same elements and are retrieved in the same manner.
- // The underlying storage may be different.
- uint32_t* pArray2_copy = new uint32_t[nArraySize];
- uint32_t* pArray3_copy = new uint32_t[nArraySize];
-
- memcpy(pArray2_copy, pArray2, sizeof(uint32_t) * nArraySize);
- memcpy(pArray3_copy, pArray3, sizeof(uint32_t) * nArraySize);
-
- for(uint32_t i = 0; i < nArraySize; i++)
- {
- EATEST_VERIFY(pArray2_copy[0] == pArray3_copy[0]);
- std::pop_heap(pArray2_copy, pArray2_copy + nArraySize - i);
- pop_heap(pArray3_copy, pArray3_copy + nArraySize - i);
- }
- delete[] pArray2_copy;
- delete[] pArray3_copy;
- return nErrorCount;
-}
-
-
-
-int TestHeap()
-{
- int nErrorCount = 0;
-
- // We do a bit of our heap testing by simply doing rng operations and comparing
- // to a standard STL implementation of the heap functions.
-
- {
- #ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY
-
- EA::UnitTest::Rand rng(EA::UnitTest::GetRandSeed());
-
- const int32_t kMinArraySize = 2;
- const int32_t kMaxArraySize = 1000;
- const int32_t kMinValue = 0;
- const int32_t kMaxValue = 500;
-
- // To consider, instead of using 25, try conditioning on EA::UnitTest::GetSystemSpeed().
- // I tried this, but even though Caps and PC are the same system speed, Caps was quite slower
- // than PC doing 75 loops
- for(int i = 0; (i < 25) && (nErrorCount == 0); i++)
- {
- //
- // Set up an array of data to work with as a heap.
- uint32_t nArraySizeInitial = (uint32_t)rng.RandRange(kMinArraySize, kMaxArraySize);
- uint32_t nArraySize = nArraySizeInitial;
- uint32_t* pArray1 = new uint32_t[nArraySize + 1]; // Array1 is the original data. // +1 because we append an additional element in the is_heap_until test below.
- uint32_t* pArray2 = new uint32_t[nArraySize + 1]; // Array2 is the data in std::make_heap
- uint32_t* pArray3 = new uint32_t[nArraySize + 1]; // Array3 is the data in eastl::make_heap.
-
- for(uint32_t j = 0; j < nArraySize; j++)
- pArray1[j] = pArray2[j] = pArray3[j] = (uint32_t)rng.RandRange(kMinValue, kMaxValue);
-
-
- // make_heap
- std::make_heap(pArray2, pArray2 + nArraySize);
- make_heap(pArray3, pArray3 + nArraySize);
- VerifyHeaps(pArray2, pArray3, nArraySize);
-
-
- // is_heap_until
- {
- pArray3[nArraySize] = kMaxValue + 1; // Append a value which is guaranteed to break the heap.
- uint32_t* pUntil = is_heap_until(pArray3, pArray3 + (nArraySize + 1));
- EATEST_VERIFY_F(pUntil == (pArray3 + nArraySize), "is_heap_until failure in iteration %d for array size %I32u.", nArraySize);
- }
-
-
- // pop_heap
- const int popCount = min<uint32_t>(200, nArraySize);
- for(int k = 0; (k < popCount) && (nErrorCount == 0); k++, nArraySize--)
- {
- std::pop_heap(pArray2, pArray2 + nArraySize);
- pArray2[nArraySize - 1] = 0xffffffff; // Set it to some value so we can recognize it in a debugger.
-
- pop_heap(pArray3, pArray3 + nArraySize);
- pArray3[nArraySize - 1] = 0xffffffff;
-
- VerifyHeaps(pArray2, pArray3, nArraySize - 1);
- }
-
-
- // push_heap
- const int pushCount = popCount;
- for(int m = 0; (m < pushCount) && (nErrorCount == 0); m++, nArraySize++)
- {
- const uint32_t n = (uint32_t)rng.RandRange(kMinValue, kMaxValue);
-
- pArray2[nArraySize] = n;
- std::push_heap(pArray2, pArray2 + nArraySize + 1);
-
- pArray3[nArraySize] = n;
- push_heap(pArray3, pArray3 + nArraySize + 1);
-
- VerifyHeaps(pArray2, pArray3, nArraySize + 1);
- }
-
- uint32_t originalSize = nArraySize;
- // remove_heap
- // Because the heap that stdlib on iOS and other platforms differs, different elements
- // will be removed. After calling remove heap, we cannot call VerifyHeaps anymore, but
- // can still check that heap format is retained.
- const int eraseCount = popCount;
- for(int e = 0; (e < eraseCount) && (nErrorCount == 0); e++, nArraySize--)
- {
- const uint32_t position = (uint32_t)rng.RandRange(0, nArraySize);
-
- remove_heap(pArray2, nArraySize, position);
- pArray2[nArraySize - 1] = 0xffffffff;
-
- remove_heap(pArray3, nArraySize, position);
- pArray3[nArraySize - 1] = 0xffffffff;
-
- //use is_heap_until to verify remove_heap is working.
- if(nArraySize > 1) //If we just popped last element, don't use is_heap_until
- {
- uint32_t* pUntil = is_heap_until(pArray2, pArray2 + (nArraySize));
- EATEST_VERIFY_F(pUntil == (pArray2 + nArraySize - 1), "pUntil failure for pArray2 with array size %I32u.", nArraySize);
-
- pUntil = is_heap_until(pArray3, pArray3 + (nArraySize));
- EATEST_VERIFY_F(pUntil == (pArray3 + nArraySize - 1), "failure for pArray3 with array size %I32u.", nArraySize);
- }
- }
-
- // push_heap -- increase the heap size back to the original size.
- for(int m = 0; (m < pushCount) && (nErrorCount == 0); m++, nArraySize++)
- {
- const uint32_t n = (uint32_t)rng.RandRange(kMinValue, kMaxValue);
-
- pArray2[nArraySize] = n;
- std::push_heap(pArray2, pArray2 + nArraySize + 1);
-
- pArray3[nArraySize] = n;
- push_heap(pArray3, pArray3 + nArraySize + 1);
- }
-
- EATEST_VERIFY_F(nArraySize == originalSize, "Array size is %d not original size %d", nArraySize , originalSize);
-
- uint32_t* pUntil = is_heap_until(pArray2, pArray2 + (nArraySize));
- EATEST_VERIFY_F(pUntil == (pArray2 + nArraySize), "failure for pArray2 with array size %I32u.", nArraySize);
- pUntil = is_heap_until(pArray3, pArray3 + (nArraySize));
- EATEST_VERIFY_F(pUntil == (pArray3 + nArraySize), "failure for pArray3 with array size %I32u.", nArraySize);
-
-
- // change_heap
- const int changeCount = popCount;
- for(int r = 0; (r < changeCount) && (nErrorCount == 0); r++, nArraySize--)
- {
- uint32_t position = (uint32_t)rng.RandRange(0, nArraySize);
- uint32_t newValue = (uint32_t)rng.RandRange(kMinValue, kMaxValue);
-
- if(rng.RandLimit(5) == 0) // One in five chance that we use the heap top position.
- position = 0;
- if(rng.RandLimit(5) != 0) // One in five chance that we do no change.
- pArray2[position] = pArray3[position] = newValue;
-
- // There is no std::change_heap, so we just use ours for this test.
- change_heap(pArray2, nArraySize, position);
- pArray2[nArraySize - 1] = 0xffffffff;
-
- change_heap(pArray3, nArraySize, position);
- pArray3[nArraySize - 1] = 0xffffffff;
-
- if(nArraySize > 1) //If we just removed last element, don't use is_heap_until
- {
- uint32_t* pUntilChanged = is_heap_until(pArray2, pArray2 + (nArraySize));
- EATEST_VERIFY_F(pUntilChanged == (pArray2 + nArraySize - 1), "failure for pArray2 with array size %I32u.", nArraySize);
- pUntilChanged = is_heap_until(pArray3, pArray3 + (nArraySize));
- EATEST_VERIFY_F(pUntilChanged == (pArray3 + nArraySize - 1), "failure for pArray3 with array size %I32u.", nArraySize);
- }
- }
-
-
- // sort_heap
- std::sort_heap(pArray2, pArray2 + nArraySize);
- sort_heap(pArray3, pArray3 + nArraySize);
-
- for(uint32_t q = 1; (q < nArraySize) && (nErrorCount == 0); q++)
- {
- EATEST_VERIFY(pArray2[q-1] <= pArray2[q]);
- EATEST_VERIFY(pArray3[q-1] <= pArray3[q]);
- }
- // Free our heap data.
- delete[] pArray1;
- delete[] pArray2;
- delete[] pArray3;
- }
-
- #endif // EA_COMPILER_NO_STANDARD_CPP_LIBRARY
- }
-
- {
- // Test aligned types.
-
- // Aligned objects should be CustomAllocator instead of the default, because the
- // EASTL default might be unable to do aligned allocations, but CustomAllocator always can.
- eastl::vector<Align64, CustomAllocator> heap;
-
- for(int i = 0; i < 16; i++)
- heap.push_back(Align64(i));
-
- eastl::make_heap(heap.begin(), heap.end());
- EATEST_VERIFY(is_heap(heap.begin(), heap.end()));
-
- heap.push_back(Align64(7));
- eastl::push_heap(heap.begin(), heap.end());
- EATEST_VERIFY(is_heap(heap.begin(), heap.end()));
-
- heap.push_back(Align64(7));
- eastl::push_heap(heap.begin(), heap.end());
- heap.pop_back();
- EATEST_VERIFY(is_heap(heap.begin(), heap.end()));
-
- eastl::remove_heap(heap.begin(), heap.size(), (eastl_size_t)4);
- heap.pop_back();
- EATEST_VERIFY(is_heap(heap.begin(), heap.end()));
-
- eastl::sort_heap(heap.begin(), heap.end());
- EATEST_VERIFY(is_sorted(heap.begin(), heap.end()));
- }
-
- {
- Align16 heap[5];
-
- eastl::make_heap(heap, heap + 5);
- EATEST_VERIFY(is_heap(heap, heap + 5));
-
- eastl::partial_sort(heap, heap + 3, heap + 5);
- }
-
- return nErrorCount;
-}
-
-
-
-
-
-
-
-
-
-
-
-
-
Powered by cgit, Themed by Ted Yin.