Make SkDeque::back faster & inline
http://codereview.appspot.com/6462073/
git-svn-id: http://skia.googlecode.com/svn/trunk@5149 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/include/core/SkDeque.h b/include/core/SkDeque.h
index 3bf0bdd..d29f72a 100644
--- a/include/core/SkDeque.h
+++ b/include/core/SkDeque.h
@@ -12,6 +12,17 @@
#include "SkTypes.h"
+/*
+ * The deque class works by blindly creating memory space of a specified element
+ * size. It manages the memory as a doubly linked list of blocks each of which
+ * can contain multiple elements. Pushes and pops add/remove blocks from the
+ * beginning/end of the list as necessary while each block tracks the used
+ * portion of its memory.
+ * One behavior to be aware of is that the pops do not immediately remove an
+ * empty block from the beginning/end of the list (Presumably so push/pop pairs
+ * on the block boundaries don't cause thrashing). This can result in the first/
+ * last element not residing in the first/last block.
+ */
class SK_API SkDeque : SkNoncopyable {
public:
/**
@@ -26,8 +37,8 @@
int count() const { return fCount; }
size_t elemSize() const { return fElemSize; }
- const void* front() const;
- const void* back() const;
+ const void* front() const { return fFront; }
+ const void* back() const { return fBack; }
void* front() {
return (void*)((const SkDeque*)this)->front();
@@ -37,6 +48,10 @@
return (void*)((const SkDeque*)this)->back();
}
+ /**
+ * push_front and push_back return a pointer to the memory space
+ * for the new element
+ */
void* push_front();
void* push_back();
@@ -100,8 +115,11 @@
// allow unit test to call numBlocksAllocated
friend class DequeUnitTestHelper;
- Block* fFront;
- Block* fBack;
+ void* fFront;
+ void* fBack;
+
+ Block* fFrontBlock;
+ Block* fBackBlock;
size_t fElemSize;
void* fInitialStorage;
int fCount; // number of elements in the deque
diff --git a/src/core/SkClipStack.cpp b/src/core/SkClipStack.cpp
index 8857244..add46e4 100644
--- a/src/core/SkClipStack.cpp
+++ b/src/core/SkClipStack.cpp
@@ -565,6 +565,7 @@
int32_t genID = GetNextGenID();
+ // Use reverse iterator instead of back because Rect path may need previous
SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
Rec* rec = (Rec*) iter.prev();
@@ -647,10 +648,9 @@
}
void SkClipStack::clipEmpty() {
-
- SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
- Rec* rec = (Rec*) iter.prev();
-
+
+ Rec* rec = (Rec*) fDeque.back();
+
if (rec && rec->canBeIntersectedInPlace(fSaveCount, SkRegion::kIntersect_Op)) {
switch (rec->fState) {
case Rec::kEmpty_State:
diff --git a/src/core/SkDeque.cpp b/src/core/SkDeque.cpp
index 52c3c2e..83c9f97 100644
--- a/src/core/SkDeque.cpp
+++ b/src/core/SkDeque.cpp
@@ -32,6 +32,7 @@
, fCount(0)
, fAllocCount(allocCount) {
SkASSERT(allocCount >= 1);
+ fFrontBlock = fBackBlock = NULL;
fFront = fBack = NULL;
}
@@ -44,16 +45,17 @@
SkASSERT(allocCount >= 1);
if (storageSize >= sizeof(Block) + elemSize) {
- fFront = (Block*)storage;
- fFront->init(storageSize);
+ fFrontBlock = (Block*)storage;
+ fFrontBlock->init(storageSize);
} else {
- fFront = NULL;
+ fFrontBlock = NULL;
}
- fBack = fFront;
+ fBackBlock = fFrontBlock;
+ fFront = fBack = NULL;
}
SkDeque::~SkDeque() {
- Block* head = fFront;
+ Block* head = fFrontBlock;
Block* initialHead = (Block*)fInitialStorage;
while (head) {
@@ -65,47 +67,15 @@
}
}
-const void* SkDeque::front() const {
- Block* front = fFront;
-
- if (NULL == front) {
- return NULL;
- }
- if (NULL == front->fBegin) {
- front = front->fNext;
- if (NULL == front) {
- return NULL;
- }
- }
- SkASSERT(front->fBegin);
- return front->fBegin;
-}
-
-const void* SkDeque::back() const {
- Block* back = fBack;
-
- if (NULL == back) {
- return NULL;
- }
- if (NULL == back->fEnd) { // marked as deleted
- back = back->fPrev;
- if (NULL == back) {
- return NULL;
- }
- }
- SkASSERT(back->fEnd);
- return back->fEnd - fElemSize;
-}
-
void* SkDeque::push_front() {
fCount += 1;
- if (NULL == fFront) {
- fFront = this->allocateBlock(fAllocCount);
- fBack = fFront; // update our linklist
+ if (NULL == fFrontBlock) {
+ fFrontBlock = this->allocateBlock(fAllocCount);
+ fBackBlock = fFrontBlock; // update our linklist
}
- Block* first = fFront;
+ Block* first = fFrontBlock;
char* begin;
if (NULL == first->fBegin) {
@@ -117,26 +87,35 @@
if (begin < first->start()) { // no more room in this chunk
// should we alloc more as we accumulate more elements?
first = this->allocateBlock(fAllocCount);
- first->fNext = fFront;
- fFront->fPrev = first;
- fFront = first;
+ first->fNext = fFrontBlock;
+ fFrontBlock->fPrev = first;
+ fFrontBlock = first;
goto INIT_CHUNK;
}
}
first->fBegin = begin;
+
+ if (NULL == fFront) {
+ SkASSERT(NULL == fBack);
+ fFront = fBack = begin;
+ } else {
+ SkASSERT(NULL != fBack);
+ fFront = begin;
+ }
+
return begin;
}
void* SkDeque::push_back() {
fCount += 1;
- if (NULL == fBack) {
- fBack = this->allocateBlock(fAllocCount);
- fFront = fBack; // update our linklist
+ if (NULL == fBackBlock) {
+ fBackBlock = this->allocateBlock(fAllocCount);
+ fFrontBlock = fBackBlock; // update our linklist
}
- Block* last = fBack;
+ Block* last = fBackBlock;
char* end;
if (NULL == last->fBegin) {
@@ -148,40 +127,58 @@
if (end > last->fStop) { // no more room in this chunk
// should we alloc more as we accumulate more elements?
last = this->allocateBlock(fAllocCount);
- last->fPrev = fBack;
- fBack->fNext = last;
- fBack = last;
+ last->fPrev = fBackBlock;
+ fBackBlock->fNext = last;
+ fBackBlock = last;
goto INIT_CHUNK;
}
}
last->fEnd = end;
- return end - fElemSize;
+ end -= fElemSize;
+
+ if (NULL == fBack) {
+ SkASSERT(NULL == fFront);
+ fFront = fBack = end;
+ } else {
+ SkASSERT(NULL != fFront);
+ fBack = end;
+ }
+
+ return end;
}
void SkDeque::pop_front() {
SkASSERT(fCount > 0);
fCount -= 1;
- Block* first = fFront;
+ Block* first = fFrontBlock;
SkASSERT(first != NULL);
if (first->fBegin == NULL) { // we were marked empty from before
first = first->fNext;
first->fPrev = NULL;
- this->freeBlock(fFront);
- fFront = first;
+ this->freeBlock(fFrontBlock);
+ fFrontBlock = first;
SkASSERT(first != NULL); // else we popped too far
}
char* begin = first->fBegin + fElemSize;
SkASSERT(begin <= first->fEnd);
- if (begin < fFront->fEnd) {
+ if (begin < fFrontBlock->fEnd) {
first->fBegin = begin;
+ SkASSERT(NULL != first->fBegin);
+ fFront = first->fBegin;
} else {
first->fBegin = first->fEnd = NULL; // mark as empty
+ if (NULL == first->fNext) {
+ fFront = fBack = NULL;
+ } else {
+ SkASSERT(NULL != first->fNext->fBegin);
+ fFront = first->fNext->fBegin;
+ }
}
}
@@ -189,15 +186,15 @@
SkASSERT(fCount > 0);
fCount -= 1;
- Block* last = fBack;
+ Block* last = fBackBlock;
SkASSERT(last != NULL);
if (last->fEnd == NULL) { // we were marked empty from before
last = last->fPrev;
last->fNext = NULL;
- this->freeBlock(fBack);
- fBack = last;
+ this->freeBlock(fBackBlock);
+ fBackBlock = last;
SkASSERT(last != NULL); // else we popped too far
}
@@ -206,15 +203,23 @@
if (end > last->fBegin) {
last->fEnd = end;
+ SkASSERT(NULL != last->fEnd);
+ fBack = last->fEnd - fElemSize;
} else {
last->fBegin = last->fEnd = NULL; // mark as empty
+ if (NULL == last->fPrev) {
+ fFront = fBack = NULL;
+ } else {
+ SkASSERT(NULL != last->fPrev->fEnd);
+ fBack = last->fPrev->fEnd - fElemSize;
+ }
}
}
int SkDeque::numBlocksAllocated() const {
int numBlocks = 0;
- for (const Block* temp = fFront; temp; temp = temp->fNext) {
+ for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) {
++numBlocks;
}
@@ -287,14 +292,14 @@
if (kFront_IterStart == startLoc) {
// initialize the iterator to start at the front
- fCurBlock = d.fFront;
+ fCurBlock = d.fFrontBlock;
while (NULL != fCurBlock && NULL == fCurBlock->fBegin) {
fCurBlock = fCurBlock->fNext;
}
fPos = fCurBlock ? fCurBlock->fBegin : NULL;
} else {
// initialize the iterator to start at the back
- fCurBlock = d.fBack;
+ fCurBlock = d.fBackBlock;
while (NULL != fCurBlock && NULL == fCurBlock->fEnd) {
fCurBlock = fCurBlock->fPrev;
}