Refactor SkDeque's iterator and allocation method
http://codereview.appspot.com/6353098/
git-svn-id: http://skia.googlecode.com/svn/trunk@4624 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkDeque.cpp b/src/core/SkDeque.cpp
index 385b48d..52c3c2e 100644
--- a/src/core/SkDeque.cpp
+++ b/src/core/SkDeque.cpp
@@ -9,11 +9,9 @@
#include "SkDeque.h"
-#define INIT_ELEM_COUNT 1 // should we let the caller set this?
-
-struct SkDeque::Head {
- Head* fNext;
- Head* fPrev;
+struct SkDeque::Block {
+ Block* fNext;
+ Block* fPrev;
char* fBegin; // start of used section in this chunk
char* fEnd; // end of used section in this chunk
char* fStop; // end of the allocated chunk
@@ -28,17 +26,25 @@
}
};
-SkDeque::SkDeque(size_t elemSize)
- : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) {
+SkDeque::SkDeque(size_t elemSize, int allocCount)
+ : fElemSize(elemSize)
+ , fInitialStorage(NULL)
+ , fCount(0)
+ , fAllocCount(allocCount) {
+ SkASSERT(allocCount >= 1);
fFront = fBack = NULL;
}
-SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize)
- : fElemSize(elemSize), fInitialStorage(storage), fCount(0) {
+SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount)
+ : fElemSize(elemSize)
+ , fInitialStorage(storage)
+ , fCount(0)
+ , fAllocCount(allocCount) {
SkASSERT(storageSize == 0 || storage != NULL);
+ SkASSERT(allocCount >= 1);
- if (storageSize >= sizeof(Head) + elemSize) {
- fFront = (Head*)storage;
+ if (storageSize >= sizeof(Block) + elemSize) {
+ fFront = (Block*)storage;
fFront->init(storageSize);
} else {
fFront = NULL;
@@ -47,20 +53,20 @@
}
SkDeque::~SkDeque() {
- Head* head = fFront;
- Head* initialHead = (Head*)fInitialStorage;
+ Block* head = fFront;
+ Block* initialHead = (Block*)fInitialStorage;
while (head) {
- Head* next = head->fNext;
+ Block* next = head->fNext;
if (head != initialHead) {
- sk_free(head);
+ this->freeBlock(head);
}
head = next;
}
}
const void* SkDeque::front() const {
- Head* front = fFront;
+ Block* front = fFront;
if (NULL == front) {
return NULL;
@@ -76,7 +82,7 @@
}
const void* SkDeque::back() const {
- Head* back = fBack;
+ Block* back = fBack;
if (NULL == back) {
return NULL;
@@ -95,13 +101,11 @@
fCount += 1;
if (NULL == fFront) {
- fFront = (Head*)sk_malloc_throw(sizeof(Head) +
- INIT_ELEM_COUNT * fElemSize);
- fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
+ fFront = this->allocateBlock(fAllocCount);
fBack = fFront; // update our linklist
}
- Head* first = fFront;
+ Block* first = fFront;
char* begin;
if (NULL == first->fBegin) {
@@ -112,10 +116,7 @@
begin = first->fBegin - fElemSize;
if (begin < first->start()) { // no more room in this chunk
// should we alloc more as we accumulate more elements?
- size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize;
-
- first = (Head*)sk_malloc_throw(size);
- first->init(size);
+ first = this->allocateBlock(fAllocCount);
first->fNext = fFront;
fFront->fPrev = first;
fFront = first;
@@ -131,13 +132,11 @@
fCount += 1;
if (NULL == fBack) {
- fBack = (Head*)sk_malloc_throw(sizeof(Head) +
- INIT_ELEM_COUNT * fElemSize);
- fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
+ fBack = this->allocateBlock(fAllocCount);
fFront = fBack; // update our linklist
}
- Head* last = fBack;
+ Block* last = fBack;
char* end;
if (NULL == last->fBegin) {
@@ -148,10 +147,7 @@
end = last->fEnd + fElemSize;
if (end > last->fStop) { // no more room in this chunk
// should we alloc more as we accumulate more elements?
- size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize;
-
- last = (Head*)sk_malloc_throw(size);
- last->init(size);
+ last = this->allocateBlock(fAllocCount);
last->fPrev = fBack;
fBack->fNext = last;
fBack = last;
@@ -167,14 +163,14 @@
SkASSERT(fCount > 0);
fCount -= 1;
- Head* first = fFront;
+ Block* first = fFront;
SkASSERT(first != NULL);
if (first->fBegin == NULL) { // we were marked empty from before
first = first->fNext;
first->fPrev = NULL;
- sk_free(fFront);
+ this->freeBlock(fFront);
fFront = first;
SkASSERT(first != NULL); // else we popped too far
}
@@ -193,14 +189,14 @@
SkASSERT(fCount > 0);
fCount -= 1;
- Head* last = fBack;
+ Block* last = fBack;
SkASSERT(last != NULL);
if (last->fEnd == NULL) { // we were marked empty from before
last = last->fPrev;
last->fNext = NULL;
- sk_free(fBack);
+ this->freeBlock(fBack);
fBack = last;
SkASSERT(last != NULL); // else we popped too far
}
@@ -215,36 +211,93 @@
}
}
-///////////////////////////////////////////////////////////////////////////////
+int SkDeque::numBlocksAllocated() const {
+ int numBlocks = 0;
-SkDeque::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {}
+ for (const Block* temp = fFront; temp; temp = temp->fNext) {
+ ++numBlocks;
+ }
-SkDeque::F2BIter::F2BIter(const SkDeque& d) {
- this->reset(d);
+ return numBlocks;
}
-void* SkDeque::F2BIter::next() {
+SkDeque::Block* SkDeque::allocateBlock(int allocCount) {
+ Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize);
+ newBlock->init(sizeof(Block) + allocCount * fElemSize);
+ return newBlock;
+}
+
+void SkDeque::freeBlock(Block* block) {
+ sk_free(block);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+SkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {}
+
+SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
+ this->reset(d, startLoc);
+}
+
+// Due to how reset and next work, next actually returns the current element
+// pointed to by fPos and then updates fPos to point to the next one.
+void* SkDeque::Iter::next() {
char* pos = fPos;
if (pos) { // if we were valid, try to move to the next setting
char* next = pos + fElemSize;
- SkASSERT(next <= fHead->fEnd);
- if (next == fHead->fEnd) { // exhausted this chunk, move to next
+ SkASSERT(next <= fCurBlock->fEnd);
+ if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next
do {
- fHead = fHead->fNext;
- } while (fHead != NULL && fHead->fBegin == NULL);
- next = fHead ? fHead->fBegin : NULL;
+ fCurBlock = fCurBlock->fNext;
+ } while (fCurBlock != NULL && fCurBlock->fBegin == NULL);
+ next = fCurBlock ? fCurBlock->fBegin : NULL;
}
fPos = next;
}
return pos;
}
-void SkDeque::F2BIter::reset(const SkDeque& d) {
- fElemSize = d.fElemSize;
- fHead = d.fFront;
- while (fHead != NULL && fHead->fBegin == NULL) {
- fHead = fHead->fNext;
+// Like next, prev actually returns the current element pointed to by fPos and
+// then makes fPos point to the previous element.
+void* SkDeque::Iter::prev() {
+ char* pos = fPos;
+
+ if (pos) { // if we were valid, try to move to the prior setting
+ char* prev = pos - fElemSize;
+ SkASSERT(prev >= fCurBlock->fBegin - fElemSize);
+ if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior
+ do {
+ fCurBlock = fCurBlock->fPrev;
+ } while (fCurBlock != NULL && fCurBlock->fEnd == NULL);
+ prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL;
+ }
+ fPos = prev;
}
- fPos = fHead ? fHead->fBegin : NULL;
+ return pos;
+}
+
+// reset works by skipping through the spare blocks at the start (or end)
+// of the doubly linked list until a non-empty one is found. The fPos
+// member is then set to the first (or last) element in the block. If
+// there are no elements in the deque both fCurBlock and fPos will come
+// out of this routine NULL.
+void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) {
+ fElemSize = d.fElemSize;
+
+ if (kFront_IterStart == startLoc) {
+ // initialize the iterator to start at the front
+ fCurBlock = d.fFront;
+ 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;
+ while (NULL != fCurBlock && NULL == fCurBlock->fEnd) {
+ fCurBlock = fCurBlock->fPrev;
+ }
+ fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL;
+ }
}