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