Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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,
// 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;
}