rename SkDeque::Iter to SkDeque::F2BIter, since it runs front-to-back (in preparation

for another iter that runs back-to-front (B2FIter).

add unittest for Deque



git-svn-id: http://skia.googlecode.com/svn/trunk@821 2bbb7eff-a529-9590-31e7-b0007b416f81

6 files changed, 96 insertions, 33 deletions

diff --git a/include/core/SkDeque.h b/include/core/SkDeque.h
index cbed930088..99c8dd46ab 100644
--- a/include/core/SkDeque.h
+++ b/include/core/SkDeque.h
@@ -42,7 +42,7 @@ public:
 
     void* push_front();
     void* push_back();
-    
+
     void pop_front();
     void pop_back();
 
@@ -50,9 +50,9 @@ private:
     struct Head;
 
 public:
-    class Iter {
+    class F2BIter {
     public:
-        Iter(const SkDeque& d);
+        F2BIter(const SkDeque& d);
         void* next();
 
     private:
@@ -67,7 +67,7 @@ private:
     size_t  fElemSize;
     void*   fInitialStorage;
     int     fCount;
-    
+
     friend class Iter;
 };
 
diff --git a/src/core/SkCanvas.cpp b/src/core/SkCanvas.cpp
index b05d424cf9..046c69298a 100644
--- a/src/core/SkCanvas.cpp
+++ b/src/core/SkCanvas.cpp
@@ -477,16 +477,16 @@ SkDrawFilter* SkCanvas::setDrawFilter(SkDrawFilter* filter) {
 
 SkDevice* SkCanvas::getDevice() const {
     // return root device
-    SkDeque::Iter   iter(fMCStack);
-    MCRec*          rec = (MCRec*)iter.next();
+    SkDeque::F2BIter iter(fMCStack);
+    MCRec*           rec = (MCRec*)iter.next();
     SkASSERT(rec && rec->fLayer);
     return rec->fLayer->fDevice;
 }
 
 SkDevice* SkCanvas::setDevice(SkDevice* device) {
     // return root device
-    SkDeque::Iter   iter(fMCStack);
-    MCRec*          rec = (MCRec*)iter.next();
+    SkDeque::F2BIter iter(fMCStack);
+    MCRec*           rec = (MCRec*)iter.next();
     SkASSERT(rec && rec->fLayer);
     SkDevice*       rootDevice = rec->fLayer->fDevice;
 
diff --git a/src/core/SkDeque.cpp b/src/core/SkDeque.cpp
index 4f15051012..2c6ce64fae 100644
--- a/src/core/SkDeque.cpp
+++ b/src/core/SkDeque.cpp
@@ -2,16 +2,16 @@
 **
 ** Copyright 2006, The Android Open Source Project
 **
-** Licensed under the Apache License, Version 2.0 (the "License"); 
-** you may not use this file except in compliance with the License. 
-** You may obtain a copy of the License at 
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
 **
-**     http://www.apache.org/licenses/LICENSE-2.0 
+**     http://www.apache.org/licenses/LICENSE-2.0
 **
-** Unless required by applicable law or agreed to in writing, software 
-** distributed under the License is distributed on an "AS IS" BASIS, 
-** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
-** See the License for the specific language governing permissions and 
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
 ** limitations under the License.
 */
 
@@ -25,10 +25,10 @@ struct SkDeque::Head {
     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
-    
+
     char*       start() { return (char*)(this + 1); }
     const char* start() const { return (const char*)(this + 1); }
-    
+
     void init(size_t size) {
         fNext   = fPrev = NULL;
         fBegin  = fEnd = NULL;
@@ -44,7 +44,7 @@ SkDeque::SkDeque(size_t elemSize)
 SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize)
         : fElemSize(elemSize), fInitialStorage(storage), fCount(0) {
     SkASSERT(storageSize == 0 || storage != NULL);
-    
+
     if (storageSize >= sizeof(Head) + elemSize) {
         fFront = (Head*)storage;
         fFront->init(storageSize);
@@ -69,7 +69,7 @@ SkDeque::~SkDeque() {
 
 const void* SkDeque::front() const {
     Head* front = fFront;
-    
+
     if (NULL == front) {
         return NULL;
     }
@@ -108,7 +108,7 @@ void* SkDeque::push_front() {
         fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
         fBack = fFront;     // update our linklist
     }
-    
+
     Head*   first = fFront;
     char*   begin;
 
@@ -144,7 +144,7 @@ void* SkDeque::push_back() {
         fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
         fFront = fBack; // update our linklist
     }
-    
+
     Head*   last = fBack;
     char*   end;
 
@@ -178,7 +178,7 @@ void SkDeque::pop_front() {
     Head*   first = fFront;
 
     SkASSERT(first != NULL);
-    
+
     if (first->fBegin == NULL) {  // we were marked empty from before
         first = first->fNext;
         first->fPrev = NULL;
@@ -202,9 +202,9 @@ void SkDeque::pop_back() {
     fCount -= 1;
 
     Head* last = fBack;
-    
+
     SkASSERT(last != NULL);
-    
+
     if (last->fEnd == NULL) {  // we were marked empty from before
         last = last->fPrev;
         last->fNext = NULL;
@@ -212,7 +212,7 @@ void SkDeque::pop_back() {
         fBack = last;
         SkASSERT(last != NULL);  // else we popped too far
     }
-    
+
     char* end = last->fEnd - fElemSize;
     SkASSERT(end >= last->fBegin);
 
@@ -225,7 +225,7 @@ void SkDeque::pop_back() {
 
 ///////////////////////////////////////////////////////////////////////////////
 
-SkDeque::Iter::Iter(const SkDeque& d) : fElemSize(d.fElemSize) {
+SkDeque::F2BIter::F2BIter(const SkDeque& d) : fElemSize(d.fElemSize) {
     fHead = d.fFront;
     while (fHead != NULL && fHead->fBegin == NULL) {
         fHead = fHead->fNext;
@@ -233,9 +233,9 @@ SkDeque::Iter::Iter(const SkDeque& d) : fElemSize(d.fElemSize) {
     fPos = fHead ? fHead->fBegin : NULL;
 }
 
-void* SkDeque::Iter::next() {
+void* SkDeque::F2BIter::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);
diff --git a/src/effects/SkLayerRasterizer.cpp b/src/effects/SkLayerRasterizer.cpp
index 168fbe91ea..851f418d26 100644
--- a/src/effects/SkLayerRasterizer.cpp
+++ b/src/effects/SkLayerRasterizer.cpp
@@ -37,7 +37,7 @@ SkLayerRasterizer::SkLayerRasterizer() : fLayers(sizeof(SkLayerRasterizer_Rec))
 
 SkLayerRasterizer::~SkLayerRasterizer()
 {
-    SkDeque::Iter           iter(fLayers);
+    SkDeque::F2BIter        iter(fLayers);
     SkLayerRasterizer_Rec*  rec;
 
     while ((rec = (SkLayerRasterizer_Rec*)iter.next()) != NULL)
@@ -55,7 +55,7 @@ void SkLayerRasterizer::addLayer(const SkPaint& paint, SkScalar dx, SkScalar dy)
 static bool compute_bounds(const SkDeque& layers, const SkPath& path, const SkMatrix& matrix,
                            const SkIRect* clipBounds, SkIRect* bounds)
 {
-    SkDeque::Iter           iter(layers);
+    SkDeque::F2BIter        iter(layers);
     SkLayerRasterizer_Rec*  rec;
 
     bounds->set(SK_MaxS32, SK_MaxS32, SK_MinS32, SK_MinS32);
@@ -139,7 +139,7 @@ bool SkLayerRasterizer::onRasterize(const SkPath& path, const SkMatrix& matrix,
         // we set the matrixproc in the loop, as the matrix changes each time (potentially)
         draw.fBounder   = NULL;
 
-        SkDeque::Iter           iter(fLayers);
+        SkDeque::F2BIter        iter(fLayers);
         SkLayerRasterizer_Rec*  rec;
 
         while ((rec = (SkLayerRasterizer_Rec*)iter.next()) != NULL) {
@@ -219,7 +219,7 @@ void SkLayerRasterizer::flatten(SkFlattenableWriteBuffer& buffer)
 
     buffer.write32(fLayers.count());
 
-    SkDeque::Iter                   iter(fLayers);
+    SkDeque::F2BIter                iter(fLayers);
     const SkLayerRasterizer_Rec*    rec;
 
     while ((rec = (const SkLayerRasterizer_Rec*)iter.next()) != NULL)
diff --git a/tests/DequeTest.cpp b/tests/DequeTest.cpp
new file mode 100644
index 0000000000..3b8991adda
--- /dev/null
+++ b/tests/DequeTest.cpp
@@ -0,0 +1,62 @@
+#include "Test.h"
+#include "SkDeque.h"
+
+static void assert_count(skiatest::Reporter* reporter, const SkDeque& deq, int count) {
+    if (0 == count) {
+        REPORTER_ASSERT(reporter, deq.empty());
+        REPORTER_ASSERT(reporter, 0 == deq.count());
+        REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
+        REPORTER_ASSERT(reporter, NULL == deq.front());
+        REPORTER_ASSERT(reporter, NULL == deq.back());
+    } else {
+        REPORTER_ASSERT(reporter, !deq.empty());
+        REPORTER_ASSERT(reporter, count == deq.count());
+        REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
+        REPORTER_ASSERT(reporter, NULL != deq.front());
+        REPORTER_ASSERT(reporter, NULL != deq.back());
+        if (1 == count) {
+            REPORTER_ASSERT(reporter, deq.back() == deq.front());
+        } else {
+            REPORTER_ASSERT(reporter, deq.back() != deq.front());
+        }
+    }
+}
+
+static void assert_f2biter(skiatest::Reporter* reporter, const SkDeque& deq,
+                           int max, int min) {
+    SkDeque::F2BIter iter(deq);
+    void* ptr;
+
+    int value = max;
+    while ((ptr = iter.next()) != NULL) {
+        REPORTER_ASSERT(reporter, value == *(int*)ptr);
+        value -= 1;
+    }
+    REPORTER_ASSERT(reporter, value+1 == min);
+}
+
+static void TestDeque(skiatest::Reporter* reporter) {
+    SkDeque deq(sizeof(int));
+    int i;
+
+    assert_count(reporter, deq, 0);
+    for (i = 1; i <= 10; i++) {
+        *(int*)deq.push_front() = i;
+    }
+    assert_count(reporter, deq, 10);
+    assert_f2biter(reporter, deq, 10, 1);
+
+    for (i = 0; i < 5; i++) {
+        deq.pop_front();
+    }
+    assert_count(reporter, deq, 5);
+    assert_f2biter(reporter, deq, 5, 1);
+
+    for (i = 0; i < 5; i++) {
+        deq.pop_front();
+    }
+    assert_count(reporter, deq, 0);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("Deque", TestDequeClass, TestDeque)
diff --git a/tests/tests_files.mk b/tests/tests_files.mk
index 1c6a0efd5a..40e88807a3 100644
--- a/tests/tests_files.mk
+++ b/tests/tests_files.mk
@@ -3,6 +3,7 @@ SOURCE := \
     BlitRowTest.cpp \
     ClipCubicTest.cpp \
     ClipperTest.cpp \
+    DequeTest.cpp \
     FillPathTest.cpp \
     FlateTest.cpp \
     GeometryTest.cpp \