Bug 1113300 - Add a way to use SegmentedVector like a stack. r=froydnj
authorAndrew McCreight <continuation@gmail.com>
Thu, 07 May 2015 09:11:00 +0200
changeset 243370 68eca487cb376116052477ca1fdec3aec6b551cc
parent 243369 aaa0f79dfefedb19368b17002cafcc0432a28490
child 243371 02ce8bf96014f5432bd7f65ddb84bd1268ad6c7e
push id59665
push usercbook@mozilla.com
push dateTue, 12 May 2015 06:59:23 +0000
treeherdermozilla-inbound@928a48a1e116 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1113300
milestone40.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1113300 - Add a way to use SegmentedVector like a stack. r=froydnj
mfbt/SegmentedVector.h
mfbt/tests/TestSegmentedVector.cpp
--- a/mfbt/SegmentedVector.h
+++ b/mfbt/SegmentedVector.h
@@ -87,16 +87,23 @@ class SegmentedVector : private AllocPol
     {
       MOZ_ASSERT(mLength < SegmentCapacity);
       // Pre-increment mLength so that the bounds-check in operator[] passes.
       mLength++;
       T* elem = &(*this)[mLength - 1];
       new (elem) T(mozilla::Forward<U>(aU));
     }
 
+    void PopLast()
+    {
+      MOZ_ASSERT(mLength > 0);
+      (*this)[mLength - 1].~T();
+      mLength--;
+    }
+
     uint32_t mLength;
 
     // The union ensures that the elements are appropriately aligned.
     union Storage
     {
       char mBuf[sizeof(T) * SegmentCapacity];
       mozilla::AlignedElem<MOZ_ALIGNOF(T)> mAlign;
     } mStorage;
@@ -180,16 +187,42 @@ public:
   {
     Segment* segment;
     while ((segment = mSegments.popFirst())) {
       segment->~Segment();
       this->free_(segment);
     }
   }
 
+  T& GetLast()
+  {
+    MOZ_ASSERT(!IsEmpty());
+    Segment* last = mSegments.getLast();
+    return (*last)[last->Length() - 1];
+  }
+
+  const T& GetLast() const
+  {
+    MOZ_ASSERT(!IsEmpty());
+    Segment* last = mSegments.getLast();
+    return (*last)[last->Length() - 1];
+  }
+
+  void PopLast()
+  {
+    MOZ_ASSERT(!IsEmpty());
+    Segment* last = mSegments.getLast();
+    last->PopLast();
+    if (!last->Length()) {
+      mSegments.popLast();
+      last->~Segment();
+      this->free_(last);
+    }
+  }
+
   // 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
@@ -75,16 +75,32 @@ void TestBasics()
 
   n = 0;
   for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
     MOZ_RELEASE_ASSERT(iter.Get() == n);
     n++;
   }
   MOZ_RELEASE_ASSERT(n == 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(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);
 }
 
 static size_t gNumDefaultCtors;
 static size_t gNumExplicitCtors;
 static size_t gNumCopyCtors;
@@ -110,17 +126,19 @@ void TestConstructorsAndDestructors()
     SegmentedVector<NonPOD, 64, InfallibleAllocPolicy> v;
                                           // default constructor called 0 times
     MOZ_RELEASE_ASSERT(v.IsEmpty());
     gDummy = v.Append(x);                 // copy constructor called
     NonPOD y(1);                          // explicit constructor called
     gDummy = v.Append(mozilla::Move(y));  // move constructor called
     NonPOD z(1);                          // explicit constructor called
     v.InfallibleAppend(mozilla::Move(z)); // move constructor called
-    v.Clear();                            // destructor called 3 times
+    v.PopLast();                          // destructor called 1 time
+    MOZ_RELEASE_ASSERT(gNumDtors == 1);
+    v.Clear();                            // destructor called 2 times
 
     MOZ_RELEASE_ASSERT(gNumDefaultCtors  == 0);
     MOZ_RELEASE_ASSERT(gNumExplicitCtors == 3);
     MOZ_RELEASE_ASSERT(gNumCopyCtors     == 1);
     MOZ_RELEASE_ASSERT(gNumMoveCtors     == 2);
     MOZ_RELEASE_ASSERT(gNumDtors         == 3);
   }                                       // destructor called for x, y, z
   MOZ_RELEASE_ASSERT(gNumDtors == 6);