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
