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
35 namespace {
36
TEST(VectorTest,Basic)37 TEST(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
TEST(VectorTest,Reverse)45 TEST(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
TEST(VectorTest,Iterator)69 TEST(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
TEST(VectorTest,ReverseIterator)93 TEST(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
117 class DestructCounter {
118 public:
DestructCounter(int i,int * destructNumber)119 explicit DestructCounter(int i, int* destructNumber)
120 : m_i(i)
121 , m_destructNumber(destructNumber)
122 { }
123
~DestructCounter()124 ~DestructCounter() { ++(*m_destructNumber); }
get() const125 int get() const { return m_i; }
126
127 private:
128 int m_i;
129 int* m_destructNumber;
130 };
131
132 typedef WTF::Vector<OwnPtr<DestructCounter> > OwnPtrVector;
133
TEST(VectorTest,OwnPtr)134 TEST(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.
200 static HashSet<void*> constructedWrappedInts;
201 class WrappedInt {
202 public:
WrappedInt(int i=0)203 WrappedInt(int i = 0)
204 : m_originalThisPtr(this)
205 , m_i(i)
206 {
207 constructedWrappedInts.add(this);
208 }
209
WrappedInt(const WrappedInt & other)210 WrappedInt(const WrappedInt& other)
211 : m_originalThisPtr(this)
212 , m_i(other.m_i)
213 {
214 constructedWrappedInts.add(this);
215 }
216
operator =(const WrappedInt & other)217 WrappedInt& operator=(const WrappedInt& other)
218 {
219 m_i = other.m_i;
220 return *this;
221 }
222
~WrappedInt()223 ~WrappedInt()
224 {
225 EXPECT_EQ(m_originalThisPtr, this);
226 EXPECT_TRUE(constructedWrappedInts.contains(this));
227 constructedWrappedInts.remove(this);
228 }
229
get() const230 int get() const { return m_i; }
231
232 private:
233 void* m_originalThisPtr;
234 int m_i;
235 };
236
TEST(VectorTest,SwapWithInlineCapacity)237 TEST(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
287 class Comparable {
288 };
operator ==(const Comparable & a,const Comparable & b)289 bool operator==(const Comparable& a, const Comparable& b) { return true; }
290
compare()291 template<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
TEST(VectorTest,Compare)299 TEST(VectorTest, Compare)
300 {
301 compare<int>();
302 compare<Comparable>();
303 compare<WTF::String>();
304 }
305 } // namespace
306