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