Add pop_back to GrTRecorder.h

Review URL: https://codereview.chromium.org/750613002

2 files changed, 110 insertions, 29 deletions

diff --git a/src/gpu/GrTRecorder.h b/src/gpu/GrTRecorder.h
index ab559e4a59..bddf1978d8 100644
--- a/src/gpu/GrTRecorder.h
+++ b/src/gpu/GrTRecorder.h
@@ -54,7 +54,7 @@ public:
                                   and after calls to reset().
      */
     GrTRecorder(int initialSizeInBytes)
-        : fHeadBlock(MemBlock::Alloc(LengthOf(initialSizeInBytes))),
+        : fHeadBlock(MemBlock::Alloc(LengthOf(initialSizeInBytes), NULL)),
           fTailBlock(fHeadBlock),
           fLastItem(NULL) {}
 
@@ -71,6 +71,12 @@ public:
     }
 
     /**
+     * Removes and destroys the last block added to the recorder. It may not be called when the
+     * recorder is empty.
+     */
+    void pop_back();
+
+    /**
      * Destruct all items in the list and reset to empty.
      */
     void reset();
@@ -100,35 +106,49 @@ private:
     static int LengthOf(int bytes) { return (bytes + sizeof(TAlign) - 1) / sizeof(TAlign); }
 
     struct Header {
-        int fTotalLength;
+        int fTotalLength; // The length of an entry including header, item, and data in TAligns.
+        int fPrevLength;  // Same but for the previous entry. Used for iterating backwards.
     };
     template<typename TItem> TItem* alloc_back(int dataLength);
 
     struct MemBlock : SkNoncopyable {
-        static MemBlock* Alloc(int length) {
+        /** Allocates a new block and appends it to prev if not NULL. The length param is in units
+            of TAlign. */
+        static MemBlock* Alloc(int length, MemBlock* prev) {
             MemBlock* block = reinterpret_cast<MemBlock*>(
                 sk_malloc_throw(sizeof(TAlign) * (length_of<MemBlock>::kValue + length)));
             block->fLength = length;
             block->fBack = 0;
             block->fNext = NULL;
+            block->fPrev = prev;
+            if (prev) {
+                SkASSERT(NULL == prev->fNext);
+                prev->fNext = block;
+            }
             return block;
         }
 
+        // Frees from this block forward. Also adjusts prev block's next ptr.
         static void Free(MemBlock* block) {
-            if (!block) {
-                return;
+            if (block && block->fPrev) {
+                SkASSERT(block->fPrev->fNext == block);
+                block->fPrev->fNext = NULL;
+            }
+            while (block) {
+                MemBlock* next = block->fNext;
+                sk_free(block);
+                block = next;
             }
-            Free(block->fNext);
-            sk_free(block);
         }
 
         TAlign& operator [](int i) {
             return reinterpret_cast<TAlign*>(this)[length_of<MemBlock>::kValue + i];
         }
 
-        int       fLength;
-        int       fBack;
+        int       fLength; // Length in units of TAlign of the block.
+        int       fBack;   // Offset, in TAligns, to unused portion of the memory block.
         MemBlock* fNext;
+        MemBlock* fPrev;
     };
     MemBlock* const fHeadBlock;
     MemBlock* fTailBlock;
@@ -147,15 +167,54 @@ private:
 ////////////////////////////////////////////////////////////////////////////////
 
 template<typename TBase, typename TAlign>
+void GrTRecorder<TBase, TAlign>::pop_back() {
+    SkASSERT(fLastItem);
+    Header* header = reinterpret_cast<Header*>(
+        reinterpret_cast<TAlign*>(fLastItem) - length_of<Header>::kValue);
+    fTailBlock->fBack -= header->fTotalLength;
+    fLastItem->~TBase();
+
+    int lastItemLength = header->fPrevLength;
+
+    if (!header->fPrevLength) {
+        // We popped the first entry in the recorder.
+        SkASSERT(0 == fTailBlock->fBack);
+        fLastItem = NULL;
+        return;
+    }
+    if (!fTailBlock->fBack) {
+        // We popped the last entry in a block that isn't the head block. Move back a block but
+        // don't free it since we'll probably grow into it shortly.
+        fTailBlock = fTailBlock->fPrev;
+        SkASSERT(fTailBlock);
+    }
+    fLastItem = reinterpret_cast<TBase*>(
+        &(*fTailBlock)[fTailBlock->fBack - lastItemLength + length_of<Header>::kValue]);
+}
+
+template<typename TBase, typename TAlign>
 template<typename TItem>
 TItem* GrTRecorder<TBase, TAlign>::alloc_back(int dataLength) {
+    // Find the header of the previous entry and get its length. We need to store that in the new
+    // header for backwards iteration (pop_back()).
+    int prevLength = 0;
+    if (fLastItem) {
+        Header* lastHeader = reinterpret_cast<Header*>(
+            reinterpret_cast<TAlign*>(fLastItem) - length_of<Header>::kValue);
+        prevLength = lastHeader->fTotalLength;
+    }
+
     const int totalLength = length_of<Header>::kValue + length_of<TItem>::kValue + dataLength;
 
+    // Check if there is room in the current block and if not walk to next (allocating if
+    // necessary). Note that pop_back() and reset() can leave the recorder in a state where it
+    // has preallocated blocks hanging off the tail that are currently unused.
     while (fTailBlock->fBack + totalLength > fTailBlock->fLength) {
         if (!fTailBlock->fNext) {
-            fTailBlock->fNext = MemBlock::Alloc(SkTMax(2 * fTailBlock->fLength, totalLength));
+            fTailBlock = MemBlock::Alloc(SkTMax(2 * fTailBlock->fLength, totalLength), fTailBlock);
+        } else {
+            fTailBlock = fTailBlock->fNext;
         }
-        fTailBlock = fTailBlock->fNext;
         SkASSERT(0 == fTailBlock->fBack);
     }
 
@@ -164,6 +223,7 @@ TItem* GrTRecorder<TBase, TAlign>::alloc_back(int dataLength) {
                         &(*fTailBlock)[fTailBlock->fBack + length_of<Header>::kValue]);
 
     header->fTotalLength = totalLength;
+    header->fPrevLength = prevLength;
     fLastItem = rawPtr;
     fTailBlock->fBack += totalLength;
 
@@ -225,7 +285,6 @@ void GrTRecorder<TBase, TAlign>::reset() {
     // everything else.
     if (fTailBlock->fBack <= fTailBlock->fLength / 2) {
         MemBlock::Free(fTailBlock->fNext);
-        fTailBlock->fNext = NULL;
     } else if (fTailBlock->fNext) {
         MemBlock::Free(fTailBlock->fNext->fNext);
         fTailBlock->fNext->fNext = NULL;
diff --git a/tests/GrTRecorderTest.cpp b/tests/GrTRecorderTest.cpp
index 83bc445b5f..fde70ac8e8 100644
--- a/tests/GrTRecorderTest.cpp
+++ b/tests/GrTRecorderTest.cpp
@@ -7,9 +7,10 @@
 
 #if SK_SUPPORT_GPU
 
+#include "GrTRecorder.h"
 #include "SkMatrix.h"
+#include "SkRandom.h"
 #include "SkString.h"
-#include "GrTRecorder.h"
 #include "Test.h"
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -25,22 +26,43 @@ private:
     int fValue;
 };
 
-static void test_empty_back(skiatest::Reporter* reporter) {
-    GrTRecorder<IntWrapper, int> recorder(0);
-
-    REPORTER_ASSERT(reporter, recorder.empty());
-
-    for (int i = 0; i < 100; ++i) {
-        REPORTER_ASSERT(reporter, i == *GrNEW_APPEND_TO_RECORDER(recorder, IntWrapper, (i)));
-        REPORTER_ASSERT(reporter, !recorder.empty());
-        REPORTER_ASSERT(reporter, i == recorder.back());
+static void test_empty_back_and_pop(skiatest::Reporter* reporter) {
+    SkRandom rand;
+    for (int data = 0; data < 2; ++data) {
+        // Do this with different starting sizes to have different alignment between blocks and pops.
+        // pops. We want to test poping the first guy off, guys in the middle of the block, and the
+        // first guy on a non-head block.
+        for (int j = 0; j < 8; ++j) {
+            GrTRecorder<IntWrapper, int> recorder(j);
+
+            REPORTER_ASSERT(reporter, recorder.empty());
+
+            for (int i = 0; i < 100; ++i) {
+                if (data) {
+                    REPORTER_ASSERT(reporter, i == *GrNEW_APPEND_TO_RECORDER(recorder, 
+                                                                             IntWrapper, (i)));
+                } else {
+                    REPORTER_ASSERT(reporter, i ==
+                                    *GrNEW_APPEND_WITH_DATA_TO_RECORDER(recorder,
+                                                                        IntWrapper, (i),
+                                                                        rand.nextULessThan(10)));
+                }
+                REPORTER_ASSERT(reporter, !recorder.empty());
+                REPORTER_ASSERT(reporter, i == recorder.back());
+                if (0 == (i % 7)) {
+                    recorder.pop_back();
+                    if (i > 0) {
+                        REPORTER_ASSERT(reporter, !recorder.empty());
+                        REPORTER_ASSERT(reporter, i-1 == recorder.back());
+                    }
+                }
+            }
+
+            REPORTER_ASSERT(reporter, !recorder.empty());
+            recorder.reset();
+            REPORTER_ASSERT(reporter, recorder.empty());
+        }
     }
-
-    REPORTER_ASSERT(reporter, !recorder.empty());
-
-    recorder.reset();
-
-    REPORTER_ASSERT(reporter, recorder.empty());
 }
 
 struct ExtraData {
@@ -233,7 +255,7 @@ static void test_subclasses(skiatest::Reporter* reporter) {
 }
 
 DEF_GPUTEST(GrTRecorder, reporter, factory) {
-    test_empty_back(reporter);
+    test_empty_back_and_pop(reporter);
 
     test_extra_data(reporter);
     REPORTER_ASSERT(reporter, 0 == activeRecorderItems); // test_extra_data should call reset().