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/HashSet.h"
29#include "wtf/OwnPtr.h"
30#include "wtf/PassOwnPtr.h"
31#include "wtf/text/WTFString.h"
32#include "wtf/Vector.h"
33#include <gtest/gtest.h>
34
35namespace {
36
37TEST(VectorTest, Basic)
38{
39    Vector<int> intVector;
40    EXPECT_TRUE(intVector.isEmpty());
41    EXPECT_EQ(0ul, intVector.size());
42    EXPECT_EQ(0ul, intVector.capacity());
43}
44
45TEST(VectorTest, Reverse)
46{
47    Vector<int> intVector;
48    intVector.append(10);
49    intVector.append(11);
50    intVector.append(12);
51    intVector.append(13);
52    intVector.reverse();
53
54    EXPECT_EQ(13, intVector[0]);
55    EXPECT_EQ(12, intVector[1]);
56    EXPECT_EQ(11, intVector[2]);
57    EXPECT_EQ(10, intVector[3]);
58
59    intVector.append(9);
60    intVector.reverse();
61
62    EXPECT_EQ(9, intVector[0]);
63    EXPECT_EQ(10, intVector[1]);
64    EXPECT_EQ(11, intVector[2]);
65    EXPECT_EQ(12, intVector[3]);
66    EXPECT_EQ(13, intVector[4]);
67}
68
69TEST(VectorTest, Iterator)
70{
71    Vector<int> intVector;
72    intVector.append(10);
73    intVector.append(11);
74    intVector.append(12);
75    intVector.append(13);
76
77    Vector<int>::iterator it = intVector.begin();
78    Vector<int>::iterator end = intVector.end();
79    EXPECT_TRUE(end != it);
80
81    EXPECT_EQ(10, *it);
82    ++it;
83    EXPECT_EQ(11, *it);
84    ++it;
85    EXPECT_EQ(12, *it);
86    ++it;
87    EXPECT_EQ(13, *it);
88    ++it;
89
90    EXPECT_TRUE(end == it);
91}
92
93TEST(VectorTest, ReverseIterator)
94{
95    Vector<int> intVector;
96    intVector.append(10);
97    intVector.append(11);
98    intVector.append(12);
99    intVector.append(13);
100
101    Vector<int>::reverse_iterator it = intVector.rbegin();
102    Vector<int>::reverse_iterator end = intVector.rend();
103    EXPECT_TRUE(end != it);
104
105    EXPECT_EQ(13, *it);
106    ++it;
107    EXPECT_EQ(12, *it);
108    ++it;
109    EXPECT_EQ(11, *it);
110    ++it;
111    EXPECT_EQ(10, *it);
112    ++it;
113
114    EXPECT_TRUE(end == it);
115}
116
117class DestructCounter {
118public:
119    explicit DestructCounter(int i, int* destructNumber)
120        : m_i(i)
121        , m_destructNumber(destructNumber)
122    { }
123
124    ~DestructCounter() { ++(*m_destructNumber); }
125    int get() const { return m_i; }
126
127private:
128    int m_i;
129    int* m_destructNumber;
130};
131
132typedef WTF::Vector<OwnPtr<DestructCounter> > OwnPtrVector;
133
134TEST(VectorTest, OwnPtr)
135{
136    int destructNumber = 0;
137    OwnPtrVector vector;
138    vector.append(adoptPtr(new DestructCounter(0, &destructNumber)));
139    vector.append(adoptPtr(new DestructCounter(1, &destructNumber)));
140    EXPECT_EQ(2u, vector.size());
141
142    OwnPtr<DestructCounter>& counter0 = vector.first();
143    ASSERT_EQ(0, counter0->get());
144    int counter1 = vector.last()->get();
145    ASSERT_EQ(1, counter1);
146    ASSERT_EQ(0, destructNumber);
147
148    size_t index = 0;
149    for (OwnPtrVector::iterator iter = vector.begin(); iter != vector.end(); ++iter) {
150        OwnPtr<DestructCounter>* refCounter = iter;
151        EXPECT_EQ(index, static_cast<size_t>(refCounter->get()->get()));
152        EXPECT_EQ(index, static_cast<size_t>((*refCounter)->get()));
153        index++;
154    }
155    EXPECT_EQ(0, destructNumber);
156
157    for (index = 0; index < vector.size(); index++) {
158        OwnPtr<DestructCounter>& refCounter = vector[index];
159        EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
160        index++;
161    }
162    EXPECT_EQ(0, destructNumber);
163
164    EXPECT_EQ(0, vector[0]->get());
165    EXPECT_EQ(1, vector[1]->get());
166    vector.remove(0);
167    EXPECT_EQ(1, vector[0]->get());
168    EXPECT_EQ(1u, vector.size());
169    EXPECT_EQ(1, destructNumber);
170
171    OwnPtr<DestructCounter> ownCounter1 = vector[0].release();
172    vector.remove(0);
173    ASSERT_EQ(counter1, ownCounter1->get());
174    ASSERT_EQ(0u, vector.size());
175    ASSERT_EQ(1, destructNumber);
176
177    ownCounter1.clear();
178    EXPECT_EQ(2, destructNumber);
179
180    size_t count = 1025;
181    destructNumber = 0;
182    for (size_t i = 0; i < count; i++)
183        vector.prepend(adoptPtr(new DestructCounter(i, &destructNumber)));
184
185    // Vector relocation must not destruct OwnPtr element.
186    EXPECT_EQ(0, destructNumber);
187    EXPECT_EQ(count, vector.size());
188
189    OwnPtrVector copyVector;
190    vector.swap(copyVector);
191    EXPECT_EQ(0, destructNumber);
192    EXPECT_EQ(count, copyVector.size());
193    EXPECT_EQ(0u, vector.size());
194
195    copyVector.clear();
196    EXPECT_EQ(count, static_cast<size_t>(destructNumber));
197}
198
199// WrappedInt class will fail if it was memmoved or memcpyed.
200static HashSet<void*> constructedWrappedInts;
201class WrappedInt {
202public:
203    WrappedInt(int i = 0)
204        : m_originalThisPtr(this)
205        , m_i(i)
206    {
207        constructedWrappedInts.add(this);
208    }
209
210    WrappedInt(const WrappedInt& other)
211        : m_originalThisPtr(this)
212        , m_i(other.m_i)
213    {
214        constructedWrappedInts.add(this);
215    }
216
217    WrappedInt& operator=(const WrappedInt& other)
218    {
219        m_i = other.m_i;
220        return *this;
221    }
222
223    ~WrappedInt()
224    {
225        EXPECT_EQ(m_originalThisPtr, this);
226        EXPECT_TRUE(constructedWrappedInts.contains(this));
227        constructedWrappedInts.remove(this);
228    }
229
230    int get() const { return m_i; }
231
232private:
233    void* m_originalThisPtr;
234    int m_i;
235};
236
237TEST(VectorTest, SwapWithInlineCapacity)
238{
239    const size_t inlineCapacity = 2;
240    Vector<WrappedInt, inlineCapacity> vectorA;
241    vectorA.append(WrappedInt(1));
242    Vector<WrappedInt, inlineCapacity> vectorB;
243    vectorB.append(WrappedInt(2));
244
245    EXPECT_EQ(vectorA.size(), vectorB.size());
246    vectorA.swap(vectorB);
247
248    EXPECT_EQ(1u, vectorA.size());
249    EXPECT_EQ(2, vectorA.at(0).get());
250    EXPECT_EQ(1u, vectorB.size());
251    EXPECT_EQ(1, vectorB.at(0).get());
252
253    vectorA.append(WrappedInt(3));
254
255    EXPECT_GT(vectorA.size(), vectorB.size());
256    vectorA.swap(vectorB);
257
258    EXPECT_EQ(1u, vectorA.size());
259    EXPECT_EQ(1, vectorA.at(0).get());
260    EXPECT_EQ(2u, vectorB.size());
261    EXPECT_EQ(2, vectorB.at(0).get());
262    EXPECT_EQ(3, vectorB.at(1).get());
263
264    EXPECT_LT(vectorA.size(), vectorB.size());
265    vectorA.swap(vectorB);
266
267    EXPECT_EQ(2u, vectorA.size());
268    EXPECT_EQ(2, vectorA.at(0).get());
269    EXPECT_EQ(3, vectorA.at(1).get());
270    EXPECT_EQ(1u, vectorB.size());
271    EXPECT_EQ(1, vectorB.at(0).get());
272
273    vectorA.append(WrappedInt(4));
274    EXPECT_GT(vectorA.size(), inlineCapacity);
275    vectorA.swap(vectorB);
276
277    EXPECT_EQ(1u, vectorA.size());
278    EXPECT_EQ(1, vectorA.at(0).get());
279    EXPECT_EQ(3u, vectorB.size());
280    EXPECT_EQ(2, vectorB.at(0).get());
281    EXPECT_EQ(3, vectorB.at(1).get());
282    EXPECT_EQ(4, vectorB.at(2).get());
283
284    vectorB.swap(vectorA);
285}
286
287class Comparable {
288};
289bool operator==(const Comparable& a, const Comparable& b) { return true; }
290
291template<typename T> void compare()
292{
293    EXPECT_TRUE(Vector<T>() == Vector<T>());
294    EXPECT_FALSE(Vector<T>(1) == Vector<T>(0));
295    EXPECT_FALSE(Vector<T>() == Vector<T>(1));
296    EXPECT_TRUE(Vector<T>(1) == Vector<T>(1));
297}
298
299TEST(VectorTest, Compare)
300{
301    compare<int>();
302    compare<Comparable>();
303    compare<WTF::String>();
304}
305} // namespace
306