Bug 1170045 - part 1 - add bulk pop support to SegmentedVector; r=erahm
authorNathan Froyd <froydnj@mozilla.com>
Fri, 04 Mar 2016 12:02:24 -0500
changeset 709581 d0ffc4e614bc1cf868a1dd1fbb657aa01b851b2a
parent 709280 cfe627dbe845d008f1d8042eae36a424d8073556
child 709582 b25b5b84c55828ebeb1cd1590e2d0254a29e2ca9
push id112880
push usernfroyd@mozilla.com
push dateFri, 04 Mar 2016 22:50:26 +0000
treeherdertry@b25b5b84c558 [default view] [failures only]
reviewerserahm
bugs1170045
milestone47.0a1
Bug 1170045 - part 1 - add bulk pop support to SegmentedVector; r=erahm Writing PopLastN in this way is probably a bit of a micro-optimization, but at least it comes with tests and some comments for verifying the goodness of the code.
mfbt/SegmentedVector.h
mfbt/tests/TestSegmentedVector.cpp
--- a/mfbt/SegmentedVector.h
+++ b/mfbt/SegmentedVector.h
@@ -213,16 +213,66 @@ public:
     last->PopLast();
     if (!last->Length()) {
       mSegments.popLast();
       last->~Segment();
       this->free_(last);
     }
   }
 
+  // Equivalent to calling |PopLast| |aNumElements| times, but potentially
+  // more efficient.
+  void PopLastN(uint32_t aNumElements)
+  {
+    MOZ_ASSERT(aNumElements <= Length());
+
+    Segment* last;
+
+    // Pop full segments for as long as we can.  Note that this loop
+    // cleanly handles the case when the initial last segment is not
+    // full and we are popping more elements than said segment contains.
+    do {
+      last = mSegments.getLast();
+
+      // The list is empty.  We're all done.
+      if (!last) {
+        return;
+      }
+
+      // Check to see if the list contains too many elements.  Handle
+      // that in the epilogue.
+      uint32_t segmentLen = last->Length();
+      if (segmentLen > aNumElements) {
+        break;
+      }
+
+      // Destroying the segment destroys all elements contained therein.
+      mSegments.popLast();
+      last->~Segment();
+      this->free_(last);
+
+      MOZ_ASSERT(aNumElements >= segmentLen);
+      aNumElements -= segmentLen;
+      if (aNumElements == 0) {
+        return;
+      }
+    } while (true);
+
+    // Handle the case where the last segment contains more elements
+    // than we want to pop.
+    MOZ_ASSERT(last);
+    MOZ_ASSERT(last == mSegments.getLast());
+    MOZ_ASSERT(aNumElements != 0);
+    MOZ_ASSERT(aNumElements < last->Length());
+    for (uint32_t i = 0; i < aNumElements; ++i) {
+      last->PopLast();
+    }
+    MOZ_ASSERT(last->Length() != 0);
+  }
+
   // Use this class to iterate over a SegmentedVector, like so:
   //
   //  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
   //    MyElem& elem = iter.Get();
   //    f(elem);
   //  }
   //
   class IterImpl
--- a/mfbt/tests/TestSegmentedVector.cpp
+++ b/mfbt/tests/TestSegmentedVector.cpp
@@ -94,16 +94,35 @@ void TestBasics()
     v.InfallibleAppend(mozilla::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(mozilla::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.
+  n = 0;
+  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
+    MOZ_RELEASE_ASSERT(iter.Get() == n);
+    n++;
+  }
+  MOZ_RELEASE_ASSERT(n == 700);
 }
 
 static size_t gNumDefaultCtors;
 static size_t gNumExplicitCtors;
 static size_t gNumCopyCtors;
 static size_t gNumMoveCtors;
 static size_t gNumDtors;
 
@@ -122,20 +141,22 @@ 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, 64, InfallibleAllocPolicy> v;
+    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(mozilla::Move(y));  // move constructor called
     moveCtorCalls++;
@@ -144,16 +165,80 @@ void TestConstructorsAndDestructors()
     v.InfallibleAppend(mozilla::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);