Add pop_back to GrTRecorder.h
Review URL: https://codereview.chromium.org/750613002
diff --git a/src/gpu/GrTRecorder.h b/src/gpu/GrTRecorder.h
index ab559e4..bddf197 100644
--- a/src/gpu/GrTRecorder.h
+++ b/src/gpu/GrTRecorder.h
@@ -54,7 +54,7 @@
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 @@
}
/**
+ * 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 @@
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;
}
- Free(block->fNext);
- sk_free(block);
+ while (block) {
+ MemBlock* next = block->fNext;
+ sk_free(block);
+ block = next;
+ }
}
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 @@
////////////////////////////////////////////////////////////////////////////////
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 @@
&(*fTailBlock)[fTailBlock->fBack + length_of<Header>::kValue]);
header->fTotalLength = totalLength;
+ header->fPrevLength = prevLength;
fLastItem = rawPtr;
fTailBlock->fBack += totalLength;
@@ -225,7 +285,6 @@
// 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 83bc445..fde70ac 100644
--- a/tests/GrTRecorderTest.cpp
+++ b/tests/GrTRecorderTest.cpp
@@ -7,9 +7,10 @@
#if SK_SUPPORT_GPU
-#include "SkMatrix.h"
-#include "SkString.h"
#include "GrTRecorder.h"
+#include "SkMatrix.h"
+#include "SkRandom.h"
+#include "SkString.h"
#include "Test.h"
////////////////////////////////////////////////////////////////////////////////
@@ -25,22 +26,43 @@
int fValue;
};
-static void test_empty_back(skiatest::Reporter* reporter) {
- GrTRecorder<IntWrapper, int> recorder(0);
+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());
+ 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());
+ 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 @@
}
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().