/* * 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); }