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/include/core/SkDeque.h b/include/core/SkDeque.h
index b4f420d..3bf0bdd 100644
--- a/include/core/SkDeque.h
+++ b/include/core/SkDeque.h
@@ -14,8 +14,12 @@
class SK_API SkDeque : SkNoncopyable {
public:
- explicit SkDeque(size_t elemSize);
- SkDeque(size_t elemSize, void* storage, size_t storageSize);
+ /**
+ * elemSize specifies the size of each individual element in the deque
+ * allocCount specifies how many elements are to be allocated as a block
+ */
+ explicit SkDeque(size_t elemSize, int allocCount = 1);
+ SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1);
~SkDeque();
bool empty() const { return 0 == fCount; }
@@ -40,35 +44,77 @@
void pop_back();
private:
- struct Head;
+ struct Block;
public:
- class F2BIter {
+ class Iter {
public:
+ enum IterStart {
+ kFront_IterStart,
+ kBack_IterStart
+ };
+
/**
* Creates an uninitialized iterator. Must be reset()
*/
- F2BIter();
+ Iter();
- F2BIter(const SkDeque& d);
+ Iter(const SkDeque& d, IterStart startLoc);
void* next();
+ void* prev();
- void reset(const SkDeque& d);
+ void reset(const SkDeque& d, IterStart startLoc);
private:
- SkDeque::Head* fHead;
+ SkDeque::Block* fCurBlock;
char* fPos;
size_t fElemSize;
};
+
+ // Inherit privately from Iter to prevent access to reverse iteration
+ class F2BIter : private Iter {
+ public:
+ F2BIter() {}
+
+ /**
+ * Wrap Iter's 2 parameter ctor to force initialization to the
+ * beginning of the deque
+ */
+ F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
+
+ using Iter::next;
+
+ /**
+ * Wrap Iter::reset to force initialization to the beginning of the
+ * deque
+ */
+ void reset(const SkDeque& d) {
+ this->INHERITED::reset(d, kFront_IterStart);
+ }
+
+ private:
+ typedef Iter INHERITED;
+ };
private:
- Head* fFront;
- Head* fBack;
+ // allow unit test to call numBlocksAllocated
+ friend class DequeUnitTestHelper;
+
+ Block* fFront;
+ Block* fBack;
size_t fElemSize;
void* fInitialStorage;
- int fCount;
+ int fCount; // number of elements in the deque
+ int fAllocCount; // number of elements to allocate per block
- friend class Iter;
+ Block* allocateBlock(int allocCount);
+ void freeBlock(Block* block);
+
+ /**
+ * This returns the number of chunk blocks allocated by the deque. It
+ * can be used to gauge the effectiveness of the selected allocCount.
+ */
+ int numBlocksAllocated() const;
};
#endif
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;
+ }
}
diff --git a/tests/DequeTest.cpp b/tests/DequeTest.cpp
index 4e1c1b7..40fcb5a 100644
--- a/tests/DequeTest.cpp
+++ b/tests/DequeTest.cpp
@@ -29,21 +29,76 @@
}
}
-static void assert_f2biter(skiatest::Reporter* reporter, const SkDeque& deq,
- int max, int min) {
- SkDeque::F2BIter iter(deq);
+static void assert_iter(skiatest::Reporter* reporter, const SkDeque& deq,
+ int max, int min) {
+ // test forward iteration
+ SkDeque::Iter iter(deq, SkDeque::Iter::kFront_IterStart);
void* ptr;
int value = max;
- while ((ptr = iter.next()) != NULL) {
+ while (NULL != (ptr = iter.next())) {
REPORTER_ASSERT(reporter, value == *(int*)ptr);
value -= 1;
}
REPORTER_ASSERT(reporter, value+1 == min);
+
+ // test reverse iteration
+ iter.reset(deq, SkDeque::Iter::kBack_IterStart);
+
+ value = min;
+ while (NULL != (ptr = iter.prev())) {
+ REPORTER_ASSERT(reporter, value == *(int*)ptr);
+ value += 1;
+ }
+ REPORTER_ASSERT(reporter, value-1 == max);
+
+ // test mixed iteration
+ iter.reset(deq, SkDeque::Iter::kFront_IterStart);
+
+ value = max;
+ // forward iteration half-way
+ for (int i = 0; i < deq.count()/2 && NULL != (ptr = iter.next()); i++) {
+ REPORTER_ASSERT(reporter, value == *(int*)ptr);
+ value -= 1;
+ }
+ // then back down w/ reverse iteration
+ while (NULL != (ptr = iter.prev())) {
+ REPORTER_ASSERT(reporter, value == *(int*)ptr);
+ value += 1;
+ }
+ REPORTER_ASSERT(reporter, value-1 == max);
}
-static void TestDeque(skiatest::Reporter* reporter) {
- SkDeque deq(sizeof(int));
+// This helper is intended to only give the unit test access to SkDeque's
+// private numBlocksAllocated method
+class DequeUnitTestHelper {
+public:
+ int fNumBlocksAllocated;
+
+ DequeUnitTestHelper(const SkDeque& deq) {
+ fNumBlocksAllocated = deq.numBlocksAllocated();
+ }
+};
+
+static void assert_blocks(skiatest::Reporter* reporter,
+ const SkDeque& deq,
+ int allocCount) {
+ DequeUnitTestHelper helper(deq);
+
+ if (0 == deq.count()) {
+ REPORTER_ASSERT(reporter, 1 == helper.fNumBlocksAllocated);
+ } else {
+ int expected = (deq.count() + allocCount - 1) / allocCount;
+ // A block isn't freed in the deque when it first becomes empty so
+ // sometimes an extra block lingers around
+ REPORTER_ASSERT(reporter,
+ expected == helper.fNumBlocksAllocated ||
+ expected+1 == helper.fNumBlocksAllocated);
+ }
+}
+
+static void Test(skiatest::Reporter* reporter, int allocCount) {
+ SkDeque deq(sizeof(int), allocCount);
int i;
// test pushing on the front
@@ -53,18 +108,21 @@
*(int*)deq.push_front() = i;
}
assert_count(reporter, deq, 10);
- assert_f2biter(reporter, deq, 10, 1);
+ assert_iter(reporter, deq, 10, 1);
+ assert_blocks(reporter, deq, allocCount);
for (i = 0; i < 5; i++) {
deq.pop_front();
}
assert_count(reporter, deq, 5);
- assert_f2biter(reporter, deq, 5, 1);
+ assert_iter(reporter, deq, 5, 1);
+ assert_blocks(reporter, deq, allocCount);
for (i = 0; i < 5; i++) {
deq.pop_front();
}
assert_count(reporter, deq, 0);
+ assert_blocks(reporter, deq, allocCount);
// now test pushing on the back
@@ -72,20 +130,23 @@
*(int*)deq.push_back() = i;
}
assert_count(reporter, deq, 10);
- assert_f2biter(reporter, deq, 10, 1);
+ assert_iter(reporter, deq, 10, 1);
+ assert_blocks(reporter, deq, allocCount);
for (i = 0; i < 5; i++) {
deq.pop_back();
}
assert_count(reporter, deq, 5);
- assert_f2biter(reporter, deq, 10, 6);
+ assert_iter(reporter, deq, 10, 6);
+ assert_blocks(reporter, deq, allocCount);
for (i = 0; i < 5; i++) {
deq.pop_back();
}
assert_count(reporter, deq, 0);
+ assert_blocks(reporter, deq, allocCount);
- // now tests pushing/poping on both ends
+ // now test pushing/popping on both ends
*(int*)deq.push_front() = 5;
*(int*)deq.push_back() = 4;
@@ -96,8 +157,15 @@
*(int*)deq.push_front() = 8;
*(int*)deq.push_back() = 1;
assert_count(reporter, deq, 8);
- assert_f2biter(reporter, deq, 8, 1);
+ assert_iter(reporter, deq, 8, 1);
+ assert_blocks(reporter, deq, allocCount);
}
+static void TestDeque(skiatest::Reporter* reporter) {
+ // test it once with the default allocation count
+ Test(reporter, 1);
+ // test it again with a generous allocation count
+ Test(reporter, 10);
+}
#include "TestClassDef.h"
DEFINE_TESTCLASS("Deque", TestDequeClass, TestDeque)