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

3 files changed, 242 insertions, 75 deletions

diff --git a/include/core/SkDeque.h b/include/core/SkDeque.h
index b4f420daef..3bf0bdd89d 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 @@ public:
     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
+
+    Block*  allocateBlock(int allocCount);
+    void    freeBlock(Block* block);
 
-    friend class Iter;
+    /**
+     * 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 385b48de0b..52c3c2e091 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 @@ struct SkDeque::Head {
     }
 };
 
-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(size_t elemSize, void* storage, size_t storageSize)
 }
 
 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::front() const {
 }
 
 const void* SkDeque::back() const {
-    Head* back = fBack;
+    Block* back = fBack;
 
     if (NULL == back) {
         return NULL;
@@ -95,13 +101,11 @@ void* SkDeque::push_front() {
     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 @@ void* SkDeque::push_front() {
         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 @@ void* SkDeque::push_back() {
     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 @@ void* SkDeque::push_back() {
         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 @@ void SkDeque::pop_front() {
     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 @@ void SkDeque::pop_back() {
     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 @@ void SkDeque::pop_back() {
     }
 }
 
+int SkDeque::numBlocksAllocated() const { 
+    int numBlocks = 0;
+
+    for (const Block* temp = fFront; temp; temp = temp->fNext) {
+        ++numBlocks;
+    }
+
+    return numBlocks; 
+}
+
+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::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {}
+SkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {}
 
-SkDeque::F2BIter::F2BIter(const SkDeque& d) {
-    this->reset(d);
+SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
+    this->reset(d, startLoc);
 }
 
-void* SkDeque::F2BIter::next() {
+// 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) {
+// 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;
+    }
+    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;
-    fHead = d.fFront;
-    while (fHead != NULL && fHead->fBegin == NULL) {
-        fHead = fHead->fNext;
+
+    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;
     }
-    fPos = fHead ? fHead->fBegin : NULL;
 }
diff --git a/tests/DequeTest.cpp b/tests/DequeTest.cpp
index 4e1c1b75d0..40fcb5a725 100644
--- a/tests/DequeTest.cpp
+++ b/tests/DequeTest.cpp
@@ -29,21 +29,76 @@ static void assert_count(skiatest::Reporter* reporter, const SkDeque& deq, int c
     }
 }
 
-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 @@ static void TestDeque(skiatest::Reporter* reporter) {
         *(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 @@ static void TestDeque(skiatest::Reporter* reporter) {
         *(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 @@ static void TestDeque(skiatest::Reporter* reporter) {
     *(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)