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
11static 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
32static 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
74class DequeUnitTestHelper {
75public:
76    int fNumBlocksAllocated;
77
78    DequeUnitTestHelper(const SkDeque& deq) {
79        fNumBlocksAllocated = deq.numBlocksAllocated();
80    }
81};
82
83static 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
100static 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
164DEF_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}
170