1/*
2 * Copyright (C) 2011 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27
28#include "wtf/Deque.h"
29
30#include "wtf/HashSet.h"
31#include "wtf/OwnPtr.h"
32#include "wtf/PassOwnPtr.h"
33#include <gtest/gtest.h>
34
35namespace {
36
37TEST(DequeTest, Basic)
38{
39    Deque<int> intDeque;
40    EXPECT_TRUE(intDeque.isEmpty());
41    EXPECT_EQ(0ul, intDeque.size());
42}
43
44void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment)
45{
46    Deque<int>::iterator it = increment ? deque.begin() : deque.end();
47    size_t index = increment ? 0 : deque.size();
48    int step = from < to ? 1 : -1;
49    for (int i = from; i != to + step; i += step) {
50        if (!increment) {
51            --it;
52            --index;
53        }
54
55        EXPECT_EQ(i, *it);
56        EXPECT_EQ(i, deque[index]);
57
58        if (increment) {
59            ++it;
60            ++index;
61        }
62    }
63    EXPECT_EQ(increment ? deque.end() : deque.begin(), it);
64    EXPECT_EQ(increment ? deque.size() : 0, index);
65}
66
67void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increment)
68{
69    Deque<int>::reverse_iterator it = increment ? deque.rbegin() : deque.rend();
70    size_t index = increment ? 0 : deque.size();
71    int step = from < to ? 1 : -1;
72    for (int i = from; i != to + step; i += step) {
73        if (!increment) {
74            --it;
75            --index;
76        }
77
78        EXPECT_EQ(i, *it);
79        EXPECT_EQ(i, deque.at(deque.size() - 1 - index));
80
81        if (increment) {
82            ++it;
83            ++index;
84        }
85    }
86    EXPECT_EQ(increment ? deque.rend() : deque.rbegin(), it);
87    EXPECT_EQ(increment ? deque.size() : 0, index);
88}
89
90TEST(DequeTest, Reverse)
91{
92    Deque<int> intDeque;
93    intDeque.append(10);
94    intDeque.append(11);
95    intDeque.append(12);
96    intDeque.append(13);
97
98    checkNumberSequence(intDeque, 10, 13, true);
99    checkNumberSequence(intDeque, 13, 10, false);
100    checkNumberSequenceReverse(intDeque, 13, 10, true);
101    checkNumberSequenceReverse(intDeque, 10, 13, false);
102
103    intDeque.append(14);
104    intDeque.append(15);
105    EXPECT_EQ(10, intDeque.takeFirst());
106    EXPECT_EQ(15, intDeque.takeLast());
107    checkNumberSequence(intDeque, 11, 14, true);
108    checkNumberSequence(intDeque, 14, 11, false);
109    checkNumberSequenceReverse(intDeque, 14, 11, true);
110    checkNumberSequenceReverse(intDeque, 11, 14, false);
111
112    for (int i = 15; i < 200; ++i)
113        intDeque.append(i);
114    checkNumberSequence(intDeque, 11, 199, true);
115    checkNumberSequence(intDeque, 199, 11, false);
116    checkNumberSequenceReverse(intDeque, 199, 11, true);
117    checkNumberSequenceReverse(intDeque, 11, 199, false);
118
119    for (int i = 0; i < 180; ++i) {
120        EXPECT_EQ(i + 11, intDeque[0]);
121        EXPECT_EQ(i + 11, intDeque.takeFirst());
122    }
123    checkNumberSequence(intDeque, 191, 199, true);
124    checkNumberSequence(intDeque, 199, 191, false);
125    checkNumberSequenceReverse(intDeque, 199, 191, true);
126    checkNumberSequenceReverse(intDeque, 191, 199, false);
127
128    Deque<int> intDeque2;
129    swap(intDeque, intDeque2);
130
131    checkNumberSequence(intDeque2, 191, 199, true);
132    checkNumberSequence(intDeque2, 199, 191, false);
133    checkNumberSequenceReverse(intDeque2, 199, 191, true);
134    checkNumberSequenceReverse(intDeque2, 191, 199, false);
135
136    intDeque.swap(intDeque2);
137
138    checkNumberSequence(intDeque, 191, 199, true);
139    checkNumberSequence(intDeque, 199, 191, false);
140    checkNumberSequenceReverse(intDeque, 199, 191, true);
141    checkNumberSequenceReverse(intDeque, 191, 199, false);
142
143    intDeque.swap(intDeque2);
144
145    checkNumberSequence(intDeque2, 191, 199, true);
146    checkNumberSequence(intDeque2, 199, 191, false);
147    checkNumberSequenceReverse(intDeque2, 199, 191, true);
148    checkNumberSequenceReverse(intDeque2, 191, 199, false);
149}
150
151class DestructCounter {
152public:
153    explicit DestructCounter(int i, int* destructNumber)
154        : m_i(i)
155        , m_destructNumber(destructNumber)
156    { }
157
158    ~DestructCounter() { ++(*m_destructNumber); }
159    int get() const { return m_i; }
160
161private:
162    int m_i;
163    int* m_destructNumber;
164};
165
166typedef WTF::Deque<OwnPtr<DestructCounter> > OwnPtrDeque;
167
168TEST(DequeTest, OwnPtr)
169{
170    int destructNumber = 0;
171    OwnPtrDeque deque;
172    deque.append(adoptPtr(new DestructCounter(0, &destructNumber)));
173    deque.append(adoptPtr(new DestructCounter(1, &destructNumber)));
174    EXPECT_EQ(2u, deque.size());
175
176    OwnPtr<DestructCounter>& counter0 = deque.first();
177    EXPECT_EQ(0, counter0->get());
178    int counter1 = deque.last()->get();
179    EXPECT_EQ(1, counter1);
180    EXPECT_EQ(0, destructNumber);
181
182    size_t index = 0;
183    for (OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) {
184        OwnPtr<DestructCounter>& refCounter = *iter;
185        EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
186        EXPECT_EQ(index, static_cast<size_t>((*refCounter).get()));
187        index++;
188    }
189    EXPECT_EQ(0, destructNumber);
190
191    OwnPtrDeque::iterator it = deque.begin();
192    for (index = 0; index < deque.size(); ++index) {
193        OwnPtr<DestructCounter>& refCounter = *it;
194        EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
195        index++;
196        ++it;
197    }
198    EXPECT_EQ(0, destructNumber);
199
200    EXPECT_EQ(0, deque.first()->get());
201    deque.removeFirst();
202    EXPECT_EQ(1, deque.first()->get());
203    EXPECT_EQ(1u, deque.size());
204    EXPECT_EQ(1, destructNumber);
205
206    OwnPtr<DestructCounter> ownCounter1 = deque.first().release();
207    deque.removeFirst();
208    EXPECT_EQ(counter1, ownCounter1->get());
209    EXPECT_EQ(0u, deque.size());
210    EXPECT_EQ(1, destructNumber);
211
212    ownCounter1.clear();
213    EXPECT_EQ(2, destructNumber);
214
215    size_t count = 1025;
216    destructNumber = 0;
217    for (size_t i = 0; i < count; ++i)
218        deque.prepend(adoptPtr(new DestructCounter(i, &destructNumber)));
219
220    // Deque relocation must not destruct OwnPtr element.
221    EXPECT_EQ(0, destructNumber);
222    EXPECT_EQ(count, deque.size());
223
224    OwnPtrDeque copyDeque;
225    deque.swap(copyDeque);
226    EXPECT_EQ(0, destructNumber);
227    EXPECT_EQ(count, copyDeque.size());
228    EXPECT_EQ(0u, deque.size());
229
230    copyDeque.clear();
231    EXPECT_EQ(count, static_cast<size_t>(destructNumber));
232}
233
234// WrappedInt class will fail if it was memmoved or memcpyed.
235static HashSet<void*> constructedWrappedInts;
236class WrappedInt {
237public:
238    WrappedInt(int i = 0)
239        : m_originalThisPtr(this)
240        , m_i(i)
241    {
242        constructedWrappedInts.add(this);
243    }
244
245    WrappedInt(const WrappedInt& other)
246        : m_originalThisPtr(this)
247        , m_i(other.m_i)
248    {
249        constructedWrappedInts.add(this);
250    }
251
252    WrappedInt& operator=(const WrappedInt& other)
253    {
254        m_i = other.m_i;
255        return *this;
256    }
257
258    ~WrappedInt()
259    {
260        EXPECT_EQ(m_originalThisPtr, this);
261        EXPECT_TRUE(constructedWrappedInts.contains(this));
262        constructedWrappedInts.remove(this);
263    }
264
265    int get() const { return m_i; }
266
267private:
268    void* m_originalThisPtr;
269    int m_i;
270};
271
272TEST(DequeTest, SwapWithoutInlineCapacity)
273{
274    Deque<WrappedInt> dequeA;
275    dequeA.append(WrappedInt(1));
276    Deque<WrappedInt> dequeB;
277    dequeB.append(WrappedInt(2));
278
279    ASSERT_EQ(dequeA.size(), dequeB.size());
280    dequeA.swap(dequeB);
281
282    ASSERT_EQ(1u, dequeA.size());
283    EXPECT_EQ(2, dequeA.first().get());
284    ASSERT_EQ(1u, dequeB.size());
285    EXPECT_EQ(1, dequeB.first().get());
286
287    dequeA.append(WrappedInt(3));
288
289    ASSERT_GT(dequeA.size(), dequeB.size());
290    dequeA.swap(dequeB);
291
292    ASSERT_EQ(1u, dequeA.size());
293    EXPECT_EQ(1, dequeA.first().get());
294    ASSERT_EQ(2u, dequeB.size());
295    EXPECT_EQ(2, dequeB.first().get());
296
297    ASSERT_LT(dequeA.size(), dequeB.size());
298    dequeA.swap(dequeB);
299
300    ASSERT_EQ(2u, dequeA.size());
301    EXPECT_EQ(2, dequeA.first().get());
302    ASSERT_EQ(1u, dequeB.size());
303    EXPECT_EQ(1, dequeB.first().get());
304
305    dequeA.append(WrappedInt(4));
306    dequeA.swap(dequeB);
307
308    ASSERT_EQ(1u, dequeA.size());
309    EXPECT_EQ(1, dequeA.first().get());
310    ASSERT_EQ(3u, dequeB.size());
311    EXPECT_EQ(2, dequeB.first().get());
312
313    dequeB.swap(dequeA);
314}
315
316} // namespace
317