Home | History | Annotate | Download | only in tests
      1 
      2 /*
      3  * Copyright 2011 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 #include "Test.h"
      9 #include "SkDeque.h"
     10 
     11 static void assert_count(skiatest::Reporter* reporter, const SkDeque& deq, int count) {
     12     if (0 == count) {
     13         REPORTER_ASSERT(reporter, deq.empty());
     14         REPORTER_ASSERT(reporter, 0 == deq.count());
     15         REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
     16         REPORTER_ASSERT(reporter, NULL == deq.front());
     17         REPORTER_ASSERT(reporter, NULL == deq.back());
     18     } else {
     19         REPORTER_ASSERT(reporter, !deq.empty());
     20         REPORTER_ASSERT(reporter, count == deq.count());
     21         REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
     22         REPORTER_ASSERT(reporter, NULL != deq.front());
     23         REPORTER_ASSERT(reporter, NULL != deq.back());
     24         if (1 == count) {
     25             REPORTER_ASSERT(reporter, deq.back() == deq.front());
     26         } else {
     27             REPORTER_ASSERT(reporter, deq.back() != deq.front());
     28         }
     29     }
     30 }
     31 
     32 static void assert_iter(skiatest::Reporter* reporter, const SkDeque& deq,
     33                         int max, int min) {
     34     // test forward iteration
     35     SkDeque::Iter iter(deq, SkDeque::Iter::kFront_IterStart);
     36     void* ptr;
     37 
     38     int value = max;
     39     while (NULL != (ptr = iter.next())) {
     40         REPORTER_ASSERT(reporter, value == *(int*)ptr);
     41         value -= 1;
     42     }
     43     REPORTER_ASSERT(reporter, value+1 == min);
     44 
     45     // test reverse iteration
     46     iter.reset(deq, SkDeque::Iter::kBack_IterStart);
     47 
     48     value = min;
     49     while (NULL != (ptr = iter.prev())) {
     50         REPORTER_ASSERT(reporter, value == *(int*)ptr);
     51         value += 1;
     52     }
     53     REPORTER_ASSERT(reporter, value-1 == max);
     54 
     55     // test mixed iteration
     56     iter.reset(deq, SkDeque::Iter::kFront_IterStart);
     57 
     58     value = max;
     59     // forward iteration half-way
     60     for (int i = 0; i < deq.count()/2 && NULL != (ptr = iter.next()); i++) {
     61         REPORTER_ASSERT(reporter, value == *(int*)ptr);
     62         value -= 1;
     63     }
     64     // then back down w/ reverse iteration
     65     while (NULL != (ptr = iter.prev())) {
     66         REPORTER_ASSERT(reporter, value == *(int*)ptr);
     67         value += 1;
     68     }
     69     REPORTER_ASSERT(reporter, value-1 == max);
     70 }
     71 
     72 // This helper is intended to only give the unit test access to SkDeque's
     73 // private numBlocksAllocated method
     74 class DequeUnitTestHelper {
     75 public:
     76     int fNumBlocksAllocated;
     77 
     78     DequeUnitTestHelper(const SkDeque& deq) {
     79         fNumBlocksAllocated = deq.numBlocksAllocated();
     80     }
     81 };
     82 
     83 static void assert_blocks(skiatest::Reporter* reporter,
     84                           const SkDeque& deq,
     85                           int allocCount) {
     86     DequeUnitTestHelper helper(deq);
     87 
     88     if (0 == deq.count()) {
     89         REPORTER_ASSERT(reporter, 1 == helper.fNumBlocksAllocated);
     90     } else {
     91         int expected = (deq.count() + allocCount - 1) / allocCount;
     92         // A block isn't freed in the deque when it first becomes empty so
     93         // sometimes an extra block lingers around
     94         REPORTER_ASSERT(reporter,
     95             expected == helper.fNumBlocksAllocated ||
     96             expected+1 == helper.fNumBlocksAllocated);
     97     }
     98 }
     99 
    100 static void TestSub(skiatest::Reporter* reporter, int allocCount) {
    101     SkDeque deq(sizeof(int), allocCount);
    102     int i;
    103 
    104     // test pushing on the front
    105 
    106     assert_count(reporter, deq, 0);
    107     for (i = 1; i <= 10; i++) {
    108         *(int*)deq.push_front() = i;
    109     }
    110     assert_count(reporter, deq, 10);
    111     assert_iter(reporter, deq, 10, 1);
    112     assert_blocks(reporter, deq, allocCount);
    113 
    114     for (i = 0; i < 5; i++) {
    115         deq.pop_front();
    116     }
    117     assert_count(reporter, deq, 5);
    118     assert_iter(reporter, deq, 5, 1);
    119     assert_blocks(reporter, deq, allocCount);
    120 
    121     for (i = 0; i < 5; i++) {
    122         deq.pop_front();
    123     }
    124     assert_count(reporter, deq, 0);
    125     assert_blocks(reporter, deq, allocCount);
    126 
    127     // now test pushing on the back
    128 
    129     for (i = 10; i >= 1; --i) {
    130         *(int*)deq.push_back() = i;
    131     }
    132     assert_count(reporter, deq, 10);
    133     assert_iter(reporter, deq, 10, 1);
    134     assert_blocks(reporter, deq, allocCount);
    135 
    136     for (i = 0; i < 5; i++) {
    137         deq.pop_back();
    138     }
    139     assert_count(reporter, deq, 5);
    140     assert_iter(reporter, deq, 10, 6);
    141     assert_blocks(reporter, deq, allocCount);
    142 
    143     for (i = 0; i < 5; i++) {
    144         deq.pop_back();
    145     }
    146     assert_count(reporter, deq, 0);
    147     assert_blocks(reporter, deq, allocCount);
    148 
    149     // now test pushing/popping on both ends
    150 
    151     *(int*)deq.push_front() = 5;
    152     *(int*)deq.push_back() = 4;
    153     *(int*)deq.push_front() = 6;
    154     *(int*)deq.push_back() = 3;
    155     *(int*)deq.push_front() = 7;
    156     *(int*)deq.push_back() = 2;
    157     *(int*)deq.push_front() = 8;
    158     *(int*)deq.push_back() = 1;
    159     assert_count(reporter, deq, 8);
    160     assert_iter(reporter, deq, 8, 1);
    161     assert_blocks(reporter, deq, allocCount);
    162 }
    163 
    164 static void TestDeque(skiatest::Reporter* reporter) {
    165     // test it once with the default allocation count
    166     TestSub(reporter, 1);
    167     // test it again with a generous allocation count
    168     TestSub(reporter, 10);
    169 }
    170 #include "TestClassDef.h"
    171 DEFINE_TESTCLASS("Deque", TestDequeClass, TestDeque)
    172