diff options
Diffstat (limited to '')
| -rw-r--r-- | mfbt/tests/TestSegmentedVector.cpp | 388 |
1 files changed, 388 insertions, 0 deletions
diff --git a/mfbt/tests/TestSegmentedVector.cpp b/mfbt/tests/TestSegmentedVector.cpp new file mode 100644 index 0000000000..dd569ea7b6 --- /dev/null +++ b/mfbt/tests/TestSegmentedVector.cpp @@ -0,0 +1,388 @@ +/* -*- Mode: C++; tab-width: 9; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// This is included first to ensure it doesn't implicitly depend on anything +// else. +#include "mozilla/SegmentedVector.h" + +#include "mozilla/Alignment.h" +#include "mozilla/Assertions.h" + +using mozilla::SegmentedVector; + +// It would be nice if we could use the InfallibleAllocPolicy from mozalloc, +// but MFBT cannot use mozalloc. +class InfallibleAllocPolicy { + public: + template <typename T> + T* pod_malloc(size_t aNumElems) { + if (aNumElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) { + MOZ_CRASH("TestSegmentedVector.cpp: overflow"); + } + T* rv = static_cast<T*>(malloc(aNumElems * sizeof(T))); + if (!rv) { + MOZ_CRASH("TestSegmentedVector.cpp: out of memory"); + } + return rv; + } + + template <typename T> + void free_(T* aPtr, size_t aNumElems = 0) { + free(aPtr); + } +}; + +template <typename Vector> +void CheckContents(Vector& vector, size_t expectedLength) { + MOZ_RELEASE_ASSERT(vector.Length() == expectedLength); + size_t n = 0; + for (auto iter = vector.Iter(); !iter.Done(); iter.Next()) { + MOZ_RELEASE_ASSERT(iter.Get() == int(n)); + n++; + } + MOZ_RELEASE_ASSERT(n == expectedLength); +} + +// We want to test Append(), which is fallible and marked with +// [[nodiscard]]. But we're using an infallible alloc policy, and so +// don't really need to check the result. Casting to |void| works with clang +// but not GCC, so we instead use this dummy variable which works with both +// compilers. +static int gDummy; + +// This tests basic segmented vector construction and iteration. +void TestBasics() { + // A SegmentedVector with a POD element type. + typedef SegmentedVector<int, 1024, InfallibleAllocPolicy> MyVector; + MyVector v; + int i; + + MOZ_RELEASE_ASSERT(v.IsEmpty()); + + // Add 100 elements, then check various things. + i = 0; + for (; i < 100; i++) { + gDummy = v.Append(std::move(i)); + } + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + CheckContents(v, 100); + + // Add another 900 elements, then re-check. + for (; i < 1000; i++) { + v.InfallibleAppend(std::move(i)); + } + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + CheckContents(v, 1000); + + // Pop off all of the elements. + MOZ_RELEASE_ASSERT(v.Length() == 1000); + for (int len = (int)v.Length(); len > 0; len--) { + MOZ_RELEASE_ASSERT(v.GetLast() == len - 1); + v.PopLast(); + } + MOZ_RELEASE_ASSERT(v.IsEmpty()); + MOZ_RELEASE_ASSERT(v.Length() == 0); + + // Fill the vector up again to prepare for the clear. + for (i = 0; i < 1000; i++) { + v.InfallibleAppend(std::move(i)); + } + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + MOZ_RELEASE_ASSERT(v.Length() == 1000); + + v.Clear(); + MOZ_RELEASE_ASSERT(v.IsEmpty()); + MOZ_RELEASE_ASSERT(v.Length() == 0); + + // Fill the vector up to verify PopLastN works. + for (i = 0; i < 1000; ++i) { + v.InfallibleAppend(std::move(i)); + } + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + MOZ_RELEASE_ASSERT(v.Length() == 1000); + + // Verify we pop the right amount of elements. + v.PopLastN(300); + MOZ_RELEASE_ASSERT(v.Length() == 700); + + // Verify the contents are what we expect. + CheckContents(v, 700); +} + +void TestMoveAndSwap() { + typedef SegmentedVector<int, 32, InfallibleAllocPolicy> MyVector; + MyVector v; + + for (int i = 0; i < 100; i++) { + (void)v.Append(i); + } + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + CheckContents(v, 100); + + // Test move constructor. + MyVector w(std::move(v)); + CheckContents(w, 100); + MOZ_RELEASE_ASSERT(v.IsEmpty()); + + // Test move assignment. + v = std::move(w); + CheckContents(v, 100); + MOZ_RELEASE_ASSERT(w.IsEmpty()); + + // Test swap. + std::swap(v, w); + CheckContents(w, 100); + MOZ_RELEASE_ASSERT(v.IsEmpty()); +} + +static size_t gNumDefaultCtors; +static size_t gNumExplicitCtors; +static size_t gNumCopyCtors; +static size_t gNumMoveCtors; +static size_t gNumDtors; + +struct NonPOD { + NonPOD() { gNumDefaultCtors++; } + explicit NonPOD(int x) { gNumExplicitCtors++; } + NonPOD(NonPOD&) { gNumCopyCtors++; } + NonPOD(NonPOD&&) { gNumMoveCtors++; } + ~NonPOD() { gNumDtors++; } +}; + +// This tests how segmented vectors with non-POD elements construct and +// destruct those elements. +void TestConstructorsAndDestructors() { + size_t defaultCtorCalls = 0; + size_t explicitCtorCalls = 0; + size_t copyCtorCalls = 0; + size_t moveCtorCalls = 0; + size_t dtorCalls = 0; + + { + static const size_t segmentSize = 64; + + // A SegmentedVector with a non-POD element type. + NonPOD x(1); // explicit constructor called + explicitCtorCalls++; + SegmentedVector<NonPOD, segmentSize, InfallibleAllocPolicy> v; + // default constructor called 0 times + MOZ_RELEASE_ASSERT(v.IsEmpty()); + gDummy = v.Append(x); // copy constructor called + copyCtorCalls++; + NonPOD y(1); // explicit constructor called + explicitCtorCalls++; + gDummy = v.Append(std::move(y)); // move constructor called + moveCtorCalls++; + NonPOD z(1); // explicit constructor called + explicitCtorCalls++; + v.InfallibleAppend(std::move(z)); // move constructor called + moveCtorCalls++; + v.PopLast(); // destructor called 1 time + dtorCalls++; + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); + v.Clear(); // destructor called 2 times + dtorCalls += 2; + + // Test that PopLastN() correctly calls the destructors of all the + // elements in the segments it destroys. + // + // We depend on the size of NonPOD when determining how many things + // to push onto the vector. It would be nicer to get this information + // from SegmentedVector itself... + static_assert(sizeof(NonPOD) == 1, "Fix length calculations!"); + + size_t nonFullLastSegmentSize = segmentSize - 1; + for (size_t i = 0; i < nonFullLastSegmentSize; ++i) { + gDummy = v.Append(x); // copy constructor called + copyCtorCalls++; + } + MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls); + + // Pop some of the elements. + { + size_t partialPopAmount = 5; + MOZ_RELEASE_ASSERT(nonFullLastSegmentSize > partialPopAmount); + v.PopLastN(partialPopAmount); // destructor called partialPopAmount times + dtorCalls += partialPopAmount; + MOZ_RELEASE_ASSERT(v.Length() == + nonFullLastSegmentSize - partialPopAmount); + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); + } + + // Pop a full segment. + { + size_t length = v.Length(); + v.PopLastN(length); + dtorCalls += length; + // These two tests *are* semantically different given the underlying + // implementation; Length sums up the sizes of the internal segments, + // while IsEmpty looks at the sequence of internal segments. + MOZ_RELEASE_ASSERT(v.Length() == 0); + MOZ_RELEASE_ASSERT(v.IsEmpty()); + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); + } + + size_t multipleSegmentsSize = (segmentSize * 3) / 2; + for (size_t i = 0; i < multipleSegmentsSize; ++i) { + gDummy = v.Append(x); // copy constructor called + copyCtorCalls++; + } + MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls); + + // Pop across segment boundaries. + { + v.PopLastN(segmentSize); + dtorCalls += segmentSize; + MOZ_RELEASE_ASSERT(v.Length() == (multipleSegmentsSize - segmentSize)); + MOZ_RELEASE_ASSERT(!v.IsEmpty()); + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); + } + + // Clear everything here to make calculations easier. + { + size_t length = v.Length(); + v.Clear(); + dtorCalls += length; + MOZ_RELEASE_ASSERT(v.IsEmpty()); + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); + } + + MOZ_RELEASE_ASSERT(gNumDefaultCtors == defaultCtorCalls); + MOZ_RELEASE_ASSERT(gNumExplicitCtors == explicitCtorCalls); + MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls); + MOZ_RELEASE_ASSERT(gNumMoveCtors == moveCtorCalls); + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); + } // destructor called for x, y, z + dtorCalls += 3; + MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls); +} + +struct A { + int mX; + int mY; +}; +struct B { + int mX; + char mY; + double mZ; +}; +struct C { + A mA; + B mB; +}; +struct D { + char mBuf[101]; +}; +struct E {}; + +// This tests that we get the right segment capacities for specified segment +// sizes, and that the elements are aligned appropriately. +void TestSegmentCapacitiesAndAlignments() { + // When SegmentedVector's constructor is passed a size, it asserts that the + // vector's segment capacity results in a segment size equal to (or very + // close to) the passed size. + // + // Also, SegmentedVector has a static assertion that elements are + // appropriately aligned. + SegmentedVector<double, 512> v1(512); + SegmentedVector<A, 1024> v2(1024); + SegmentedVector<B, 999> v3(999); + SegmentedVector<C, 10> v4(10); + SegmentedVector<D, 1234> v5(1234); + SegmentedVector<E> v6(4096); // 4096 is the default segment size + SegmentedVector<mozilla::AlignedElem<16>, 100> v7(100); +} + +void TestIterator() { + SegmentedVector<int, 4> v; + + auto iter = v.Iter(); + auto iterFromLast = v.IterFromLast(); + MOZ_RELEASE_ASSERT(iter.Done()); + MOZ_RELEASE_ASSERT(iterFromLast.Done()); + + gDummy = v.Append(1); + iter = v.Iter(); + iterFromLast = v.IterFromLast(); + MOZ_RELEASE_ASSERT(!iter.Done()); + MOZ_RELEASE_ASSERT(!iterFromLast.Done()); + + iter.Next(); + MOZ_RELEASE_ASSERT(iter.Done()); + iterFromLast.Next(); + MOZ_RELEASE_ASSERT(iterFromLast.Done()); + + iter = v.Iter(); + iterFromLast = v.IterFromLast(); + MOZ_RELEASE_ASSERT(!iter.Done()); + MOZ_RELEASE_ASSERT(!iterFromLast.Done()); + + iter.Prev(); + MOZ_RELEASE_ASSERT(iter.Done()); + iterFromLast.Prev(); + MOZ_RELEASE_ASSERT(iterFromLast.Done()); + + // Append enough entries to ensure we have at least two segments. + gDummy = v.Append(1); + gDummy = v.Append(1); + gDummy = v.Append(1); + gDummy = v.Append(1); + + iter = v.Iter(); + iterFromLast = v.IterFromLast(); + MOZ_RELEASE_ASSERT(!iter.Done()); + MOZ_RELEASE_ASSERT(!iterFromLast.Done()); + + iter.Prev(); + MOZ_RELEASE_ASSERT(iter.Done()); + iterFromLast.Next(); + MOZ_RELEASE_ASSERT(iterFromLast.Done()); + + iter = v.Iter(); + iterFromLast = v.IterFromLast(); + MOZ_RELEASE_ASSERT(!iter.Done()); + MOZ_RELEASE_ASSERT(!iterFromLast.Done()); + + iter.Next(); + MOZ_RELEASE_ASSERT(!iter.Done()); + iterFromLast.Prev(); + MOZ_RELEASE_ASSERT(!iterFromLast.Done()); + + iter = v.Iter(); + iterFromLast = v.IterFromLast(); + int count = 0; + for (; !iter.Done() && !iterFromLast.Done(); + iter.Next(), iterFromLast.Prev()) { + ++count; + } + MOZ_RELEASE_ASSERT(count == 5); + + // Modify the vector while using the iterator. + iterFromLast = v.IterFromLast(); + gDummy = v.Append(2); + gDummy = v.Append(3); + gDummy = v.Append(4); + iterFromLast.Next(); + MOZ_RELEASE_ASSERT(!iterFromLast.Done()); + MOZ_RELEASE_ASSERT(iterFromLast.Get() == 2); + iterFromLast.Next(); + MOZ_RELEASE_ASSERT(iterFromLast.Get() == 3); + iterFromLast.Next(); + MOZ_RELEASE_ASSERT(iterFromLast.Get() == 4); + iterFromLast.Next(); + MOZ_RELEASE_ASSERT(iterFromLast.Done()); +} + +int main(void) { + TestBasics(); + TestMoveAndSwap(); + TestConstructorsAndDestructors(); + TestSegmentCapacitiesAndAlignments(); + TestIterator(); + + return 0; +} |