src/third_party/skia/tests/DequeTest.cpp

   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 "SkDeque.h"
   9 #include "Test.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, deq.front());
  23         REPORTER_ASSERT(reporter, 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 ((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 ((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 && (ptr = iter.next()); i++) {
  61         REPORTER_ASSERT(reporter, value == *(int*)ptr);
  62         value -= 1;
  63     }
  64     // then back down w/ reverse iteration
  65     while ((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 DEF_TEST(Deque, 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 }