Make possible HashSet<std::unique_ptr<>>
[WebKit-https.git] / Tools / TestWebKitAPI / Tests / WTF / HashMap.cpp
1 /*
2  * Copyright (C) 2011 Google 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 "Counters.h"
29 #include "MoveOnly.h"
30 #include <string>
31 #include <wtf/HashMap.h>
32 #include <wtf/text/StringHash.h>
33 #include <wtf/OwnPtr.h>
34 #include <wtf/PassOwnPtr.h>
35
36 namespace TestWebKitAPI {
37
38 typedef WTF::HashMap<int, int> IntHashMap;
39
40 TEST(WTF_HashMap, HashTableIteratorComparison)
41 {
42     IntHashMap map;
43     map.add(1, 2);
44     ASSERT_TRUE(map.begin() != map.end());
45     ASSERT_FALSE(map.begin() == map.end());
46
47     IntHashMap::const_iterator begin = map.begin();
48     ASSERT_TRUE(begin == map.begin());
49     ASSERT_TRUE(map.begin() == begin);
50     ASSERT_TRUE(begin != map.end());
51     ASSERT_TRUE(map.end() != begin);
52     ASSERT_FALSE(begin != map.begin());
53     ASSERT_FALSE(map.begin() != begin);
54     ASSERT_FALSE(begin == map.end());
55     ASSERT_FALSE(map.end() == begin);
56 }
57
58 struct TestDoubleHashTraits : HashTraits<double> {
59     static const int minimumTableSize = 8;
60 };
61
62 typedef HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashMap;
63
64 static int bucketForKey(double key)
65 {
66     return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
67 }
68
69 TEST(WTF_HashMap, DoubleHashCollisions)
70 {
71     // The "clobber" key here is one that ends up stealing the bucket that the -0 key
72     // originally wants to be in. This makes the 0 and -0 keys collide and the test then
73     // fails unless the FloatHash::equals() implementation can distinguish them.
74     const double clobberKey = 6;
75     const double zeroKey = 0;
76     const double negativeZeroKey = -zeroKey;
77
78     DoubleHashMap map;
79
80     map.add(clobberKey, 1);
81     map.add(zeroKey, 2);
82     map.add(negativeZeroKey, 3);
83
84     ASSERT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
85     ASSERT_EQ(map.get(clobberKey), 1);
86     ASSERT_EQ(map.get(zeroKey), 2);
87     ASSERT_EQ(map.get(negativeZeroKey), 3);
88 }
89
90 TEST(WTF_HashMap, MoveOnlyValues)
91 {
92     HashMap<unsigned, MoveOnly> moveOnlyValues;
93
94     for (size_t i = 0; i < 100; ++i) {
95         MoveOnly moveOnly(i + 1);
96         moveOnlyValues.set(i + 1, WTF::move(moveOnly));
97     }
98
99     for (size_t i = 0; i < 100; ++i) {
100         auto it = moveOnlyValues.find(i + 1);
101         ASSERT_FALSE(it == moveOnlyValues.end());
102     }
103
104     for (size_t i = 0; i < 50; ++i)
105         ASSERT_EQ(moveOnlyValues.take(i + 1).value(), i + 1);
106
107     for (size_t i = 50; i < 100; ++i)
108         ASSERT_TRUE(moveOnlyValues.remove(i + 1));
109
110     ASSERT_TRUE(moveOnlyValues.isEmpty());
111 }
112
113 TEST(WTF_HashMap, MoveOnlyKeys)
114 {
115     HashMap<MoveOnly, unsigned> moveOnlyKeys;
116
117     for (size_t i = 0; i < 100; ++i) {
118         MoveOnly moveOnly(i + 1);
119         moveOnlyKeys.set(WTF::move(moveOnly), i + 1);
120     }
121
122     for (size_t i = 0; i < 100; ++i) {
123         auto it = moveOnlyKeys.find(MoveOnly(i + 1));
124         ASSERT_FALSE(it == moveOnlyKeys.end());
125     }
126
127     for (size_t i = 0; i < 100; ++i)
128         ASSERT_FALSE(moveOnlyKeys.add(MoveOnly(i + 1), i + 1).isNewEntry);
129
130     for (size_t i = 0; i < 100; ++i)
131         ASSERT_TRUE(moveOnlyKeys.remove(MoveOnly(i + 1)));
132
133     ASSERT_TRUE(moveOnlyKeys.isEmpty());
134 }
135
136 TEST(WTF_HashMap, InitializerList)
137 {
138     HashMap<unsigned, std::string> map = {
139         { 1, "one" },
140         { 2, "two" },
141         { 3, "three" },
142         { 4, "four" },
143     };
144
145     EXPECT_EQ(4, map.size());
146
147     EXPECT_EQ("one", map.get(1));
148     EXPECT_EQ("two", map.get(2));
149     EXPECT_EQ("three", map.get(3));
150     EXPECT_EQ("four", map.get(4));
151     EXPECT_EQ(std::string(), map.get(5));
152 }
153
154 TEST(WTF_HashMap, EfficientGetter)
155 {
156     HashMap<unsigned, CopyMoveCounter> map;
157     map.set(1, CopyMoveCounter());
158
159     {
160         CopyMoveCounter::TestingScope scope;
161         map.get(1);
162         EXPECT_EQ(0U, CopyMoveCounter::constructionCount);
163         EXPECT_EQ(1U, CopyMoveCounter::copyCount);
164         EXPECT_EQ(0U, CopyMoveCounter::moveCount);
165     }
166
167     {
168         CopyMoveCounter::TestingScope scope;
169         map.get(2);
170         EXPECT_EQ(1U, CopyMoveCounter::constructionCount);
171         EXPECT_EQ(0U, CopyMoveCounter::copyCount);
172         EXPECT_EQ(1U, CopyMoveCounter::moveCount);
173     }
174 }
175
176 TEST(WTF_HashMap, OwnPtrKey)
177 {
178     ConstructorDestructorCounter::TestingScope scope;
179
180     HashMap<OwnPtr<ConstructorDestructorCounter>, int> map;
181
182     OwnPtr<ConstructorDestructorCounter> ownPtr = adoptPtr(new ConstructorDestructorCounter);
183     map.add(WTF::move(ownPtr), 2);
184
185     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
186     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
187
188     map.clear();
189     
190     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
191     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
192 }
193
194 TEST(WTF_HashMap, OwnPtrKey_FindUsingRawPointer)
195 {
196     HashMap<OwnPtr<int>, int> map;
197
198     OwnPtr<int> ownPtr = adoptPtr(new int(5));
199     int* ptr = ownPtr.get();
200     map.add(WTF::move(ownPtr), 2);
201
202     auto it = map.find(ptr);
203     ASSERT_TRUE(it != map.end());
204     EXPECT_EQ(ptr, it->key.get());
205     EXPECT_EQ(2, it->value);
206 }
207
208 TEST(WTF_HashMap, OwnPtrKey_ContainsUsingRawPointer)
209 {
210     HashMap<OwnPtr<int>, int> map;
211
212     OwnPtr<int> ownPtr = adoptPtr(new int(5));
213     int* ptr = ownPtr.get();
214     map.add(WTF::move(ownPtr), 2);
215
216     EXPECT_EQ(true, map.contains(ptr));
217 }
218
219 TEST(WTF_HashMap, OwnPtrKey_GetUsingRawPointer)
220 {
221     HashMap<OwnPtr<int>, int> map;
222
223     OwnPtr<int> ownPtr = adoptPtr(new int(5));
224     int* ptr = ownPtr.get();
225     map.add(WTF::move(ownPtr), 2);
226
227     int value = map.get(ptr);
228     EXPECT_EQ(2, value);
229 }
230
231 TEST(WTF_HashMap, OwnPtrKey_RemoveUsingRawPointer)
232 {
233     ConstructorDestructorCounter::TestingScope scope;
234
235     HashMap<OwnPtr<ConstructorDestructorCounter>, int> map;
236
237     OwnPtr<ConstructorDestructorCounter> ownPtr = adoptPtr(new ConstructorDestructorCounter);
238     ConstructorDestructorCounter* ptr = ownPtr.get();
239     map.add(WTF::move(ownPtr), 2);
240
241     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
242     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
243
244     bool result = map.remove(ptr);
245     EXPECT_EQ(true, result);
246
247     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
248     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
249 }
250
251 TEST(WTF_HashMap, OwnPtrKey_TakeUsingRawPointer)
252 {
253     ConstructorDestructorCounter::TestingScope scope;
254
255     HashMap<OwnPtr<ConstructorDestructorCounter>, int> map;
256
257     OwnPtr<ConstructorDestructorCounter> ownPtr = adoptPtr(new ConstructorDestructorCounter);
258     ConstructorDestructorCounter* ptr = ownPtr.get();
259     map.add(WTF::move(ownPtr), 2);
260
261     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
262     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
263
264     int result = map.take(ptr);
265     EXPECT_EQ(2, result);
266
267     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
268     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
269 }
270
271 TEST(WTF_HashMap, UniquePtrKey)
272 {
273     ConstructorDestructorCounter::TestingScope scope;
274
275     HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
276
277     auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
278     map.add(WTF::move(uniquePtr), 2);
279
280     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
281     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
282
283     map.clear();
284     
285     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
286     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
287 }
288
289 TEST(WTF_HashMap, UniquePtrKey_CustomDeleter)
290 {
291     ConstructorDestructorCounter::TestingScope constructorDestructorCounterScope;
292     DeleterCounter<ConstructorDestructorCounter>::TestingScope deleterCounterScope;
293
294     HashMap<std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>>, int> map;
295
296     std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>> uniquePtr(new ConstructorDestructorCounter(), DeleterCounter<ConstructorDestructorCounter>());
297     map.add(WTF::move(uniquePtr), 2);
298
299     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
300     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
301
302     EXPECT_EQ(0u, DeleterCounter<ConstructorDestructorCounter>::deleterCount);
303
304     map.clear();
305     
306     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
307     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
308
309     EXPECT_EQ(1u, DeleterCounter<ConstructorDestructorCounter>::deleterCount);
310 }
311
312 TEST(WTF_HashMap, UniquePtrKey_FindUsingRawPointer)
313 {
314     HashMap<std::unique_ptr<int>, int> map;
315
316     auto uniquePtr = std::make_unique<int>(5);
317     int* ptr = uniquePtr.get();
318     map.add(WTF::move(uniquePtr), 2);
319
320     auto it = map.find(ptr);
321     ASSERT_TRUE(it != map.end());
322     EXPECT_EQ(ptr, it->key.get());
323     EXPECT_EQ(2, it->value);
324 }
325
326 TEST(WTF_HashMap, UniquePtrKey_ContainsUsingRawPointer)
327 {
328     HashMap<std::unique_ptr<int>, int> map;
329
330     auto uniquePtr = std::make_unique<int>(5);
331     int* ptr = uniquePtr.get();
332     map.add(WTF::move(uniquePtr), 2);
333
334     EXPECT_EQ(true, map.contains(ptr));
335 }
336
337 TEST(WTF_HashMap, UniquePtrKey_GetUsingRawPointer)
338 {
339     HashMap<std::unique_ptr<int>, int> map;
340
341     auto uniquePtr = std::make_unique<int>(5);
342     int* ptr = uniquePtr.get();
343     map.add(WTF::move(uniquePtr), 2);
344
345     int value = map.get(ptr);
346     EXPECT_EQ(2, value);
347 }
348
349 TEST(WTF_HashMap, UniquePtrKey_RemoveUsingRawPointer)
350 {
351     ConstructorDestructorCounter::TestingScope scope;
352
353     HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
354
355     auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
356     ConstructorDestructorCounter* ptr = uniquePtr.get();
357     map.add(WTF::move(uniquePtr), 2);
358
359     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
360     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
361
362     bool result = map.remove(ptr);
363     EXPECT_EQ(true, result);
364
365     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
366     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
367 }
368
369 TEST(WTF_HashMap, UniquePtrKey_TakeUsingRawPointer)
370 {
371     ConstructorDestructorCounter::TestingScope scope;
372
373     HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
374
375     auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
376     ConstructorDestructorCounter* ptr = uniquePtr.get();
377     map.add(WTF::move(uniquePtr), 2);
378
379     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
380     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
381
382     int result = map.take(ptr);
383     EXPECT_EQ(2, result);
384
385     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
386     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
387 }
388
389 } // namespace TestWebKitAPI