tor-browser

TestSegmentedVector.cpp (11930B)

---

/* -*- 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"
#include "mozilla/CheckedArithmetic.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) {
   size_t size;
   if (!mozilla::SafeMul(aNumElems, sizeof(T), &size)) {
     MOZ_CRASH("TestSegmentedVector.cpp: overflow");
   }
   T* rv = static_cast<T*>(malloc(size));
   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);

 // Verify PopLastN can take larger than .Length() value as an argument.
 v.PopLastN(1000);
 MOZ_RELEASE_ASSERT(v.Length() == 0);
 MOZ_RELEASE_ASSERT(v.IsEmpty());

 // Fill the vector again.
 for (i = 0; i < 1000; ++i) {
   v.InfallibleAppend(std::move(i));
 }
 MOZ_RELEASE_ASSERT(!v.IsEmpty());
 MOZ_RELEASE_ASSERT(v.Length() == 1000);

 // Verify that calling PopLastN with Length() empties the vector.
 v.PopLastN(v.Length());
 MOZ_RELEASE_ASSERT(v.Length() == 0);
 MOZ_RELEASE_ASSERT(v.IsEmpty());
}

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;
}