123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169 |
- /*
- * Copyright 2011 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "include/core/SkDeque.h"
- #include "tests/Test.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, nullptr == deq.front());
- REPORTER_ASSERT(reporter, nullptr == deq.back());
- } else {
- REPORTER_ASSERT(reporter, !deq.empty());
- REPORTER_ASSERT(reporter, count == deq.count());
- REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
- REPORTER_ASSERT(reporter, deq.front());
- REPORTER_ASSERT(reporter, deq.back());
- if (1 == count) {
- REPORTER_ASSERT(reporter, deq.back() == deq.front());
- } else {
- REPORTER_ASSERT(reporter, deq.back() != deq.front());
- }
- }
- }
- static void assert_iter(skiatest::Reporter* reporter, const SkDeque& deq,
- int max, int min) {
- // test forward iteration
- SkDeque::Iter iter(deq, SkDeque::Iter::kFront_IterStart);
- void* ptr;
- int value = max;
- while ((ptr = iter.next())) {
- REPORTER_ASSERT(reporter, value == *(int*)ptr);
- value -= 1;
- }
- REPORTER_ASSERT(reporter, value+1 == min);
- // test reverse iteration
- iter.reset(deq, SkDeque::Iter::kBack_IterStart);
- value = min;
- while ((ptr = iter.prev())) {
- REPORTER_ASSERT(reporter, value == *(int*)ptr);
- value += 1;
- }
- REPORTER_ASSERT(reporter, value-1 == max);
- // test mixed iteration
- iter.reset(deq, SkDeque::Iter::kFront_IterStart);
- value = max;
- // forward iteration half-way
- for (int i = 0; i < deq.count()/2 && (ptr = iter.next()); i++) {
- REPORTER_ASSERT(reporter, value == *(int*)ptr);
- value -= 1;
- }
- // then back down w/ reverse iteration
- while ((ptr = iter.prev())) {
- REPORTER_ASSERT(reporter, value == *(int*)ptr);
- value += 1;
- }
- REPORTER_ASSERT(reporter, value-1 == max);
- }
- // This helper is intended to only give the unit test access to SkDeque's
- // private numBlocksAllocated method
- class DequeUnitTestHelper {
- public:
- int fNumBlocksAllocated;
- DequeUnitTestHelper(const SkDeque& deq) {
- fNumBlocksAllocated = deq.numBlocksAllocated();
- }
- };
- static void assert_blocks(skiatest::Reporter* reporter,
- const SkDeque& deq,
- int allocCount) {
- DequeUnitTestHelper helper(deq);
- if (0 == deq.count()) {
- REPORTER_ASSERT(reporter, 1 == helper.fNumBlocksAllocated);
- } else {
- int expected = (deq.count() + allocCount - 1) / allocCount;
- // A block isn't freed in the deque when it first becomes empty so
- // sometimes an extra block lingers around
- REPORTER_ASSERT(reporter,
- expected == helper.fNumBlocksAllocated ||
- expected+1 == helper.fNumBlocksAllocated);
- }
- }
- static void TestSub(skiatest::Reporter* reporter, int allocCount) {
- SkDeque deq(sizeof(int), allocCount);
- int i;
- // test pushing on the front
- assert_count(reporter, deq, 0);
- for (i = 1; i <= 10; i++) {
- *(int*)deq.push_front() = i;
- }
- assert_count(reporter, deq, 10);
- assert_iter(reporter, deq, 10, 1);
- assert_blocks(reporter, deq, allocCount);
- for (i = 0; i < 5; i++) {
- deq.pop_front();
- }
- assert_count(reporter, deq, 5);
- assert_iter(reporter, deq, 5, 1);
- assert_blocks(reporter, deq, allocCount);
- for (i = 0; i < 5; i++) {
- deq.pop_front();
- }
- assert_count(reporter, deq, 0);
- assert_blocks(reporter, deq, allocCount);
- // now test pushing on the back
- for (i = 10; i >= 1; --i) {
- *(int*)deq.push_back() = i;
- }
- assert_count(reporter, deq, 10);
- assert_iter(reporter, deq, 10, 1);
- assert_blocks(reporter, deq, allocCount);
- for (i = 0; i < 5; i++) {
- deq.pop_back();
- }
- assert_count(reporter, deq, 5);
- assert_iter(reporter, deq, 10, 6);
- assert_blocks(reporter, deq, allocCount);
- for (i = 0; i < 5; i++) {
- deq.pop_back();
- }
- assert_count(reporter, deq, 0);
- assert_blocks(reporter, deq, allocCount);
- // now test pushing/popping on both ends
- *(int*)deq.push_front() = 5;
- *(int*)deq.push_back() = 4;
- *(int*)deq.push_front() = 6;
- *(int*)deq.push_back() = 3;
- *(int*)deq.push_front() = 7;
- *(int*)deq.push_back() = 2;
- *(int*)deq.push_front() = 8;
- *(int*)deq.push_back() = 1;
- assert_count(reporter, deq, 8);
- assert_iter(reporter, deq, 8, 1);
- assert_blocks(reporter, deq, allocCount);
- }
- DEF_TEST(Deque, reporter) {
- // test it once with the default allocation count
- TestSub(reporter, 1);
- // test it again with a generous allocation count
- TestSub(reporter, 10);
- }
|