1/*
2 * Copyright (C) 2012 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 "Counters.h"
29#include "MoveOnly.h"
30#include <wtf/ListHashSet.h>
31
32namespace TestWebKitAPI {
33
34TEST(WTF_ListHashSet, RemoveFirst)
35{
36 ListHashSet<int> list;
37 list.add(1);
38 list.add(2);
39 list.add(3);
40
41 ASSERT_EQ(1, list.first());
42
43 list.removeFirst();
44 ASSERT_EQ(2, list.first());
45
46 list.removeFirst();
47 ASSERT_EQ(3, list.first());
48
49 list.removeFirst();
50 ASSERT_TRUE(list.isEmpty());
51}
52
53TEST(WTF_ListHashSet, RemoveLast)
54{
55 ListHashSet<int> list;
56 list.add(1);
57 list.add(2);
58 list.add(3);
59
60 ASSERT_EQ(3, list.last());
61
62 list.removeLast();
63 ASSERT_EQ(2, list.last());
64
65 list.removeLast();
66 ASSERT_EQ(1, list.last());
67
68 list.removeLast();
69 ASSERT_TRUE(list.isEmpty());
70}
71
72TEST(WTF_ListHashSet, AppendOrMoveToLastNewItems)
73{
74 ListHashSet<int> list;
75 ListHashSet<int>::AddResult result = list.appendOrMoveToLast(1);
76 ASSERT_TRUE(result.isNewEntry);
77 result = list.add(2);
78 ASSERT_TRUE(result.isNewEntry);
79 result = list.appendOrMoveToLast(3);
80 ASSERT_TRUE(result.isNewEntry);
81
82 ASSERT_EQ(list.size(), 3u);
83
84 // The list should be in order 1, 2, 3.
85 ListHashSet<int>::iterator iterator = list.begin();
86 ASSERT_EQ(1, *iterator);
87 ++iterator;
88 ASSERT_EQ(2, *iterator);
89 ++iterator;
90 ASSERT_EQ(3, *iterator);
91 ++iterator;
92}
93
94TEST(WTF_ListHashSet, AppendOrMoveToLastWithDuplicates)
95{
96 ListHashSet<int> list;
97
98 // Add a single element twice.
99 ListHashSet<int>::AddResult result = list.add(1);
100 ASSERT_TRUE(result.isNewEntry);
101 result = list.appendOrMoveToLast(1);
102 ASSERT_FALSE(result.isNewEntry);
103 ASSERT_EQ(1u, list.size());
104
105 list.add(2);
106 list.add(3);
107 ASSERT_EQ(3u, list.size());
108
109 // Appending 2 move it to the end.
110 ASSERT_EQ(3, list.last());
111 result = list.appendOrMoveToLast(2);
112 ASSERT_FALSE(result.isNewEntry);
113 ASSERT_EQ(2, list.last());
114
115 // Inverse the list by moving each element to end end.
116 result = list.appendOrMoveToLast(3);
117 ASSERT_FALSE(result.isNewEntry);
118 result = list.appendOrMoveToLast(2);
119 ASSERT_FALSE(result.isNewEntry);
120 result = list.appendOrMoveToLast(1);
121 ASSERT_FALSE(result.isNewEntry);
122 ASSERT_EQ(3u, list.size());
123
124 ListHashSet<int>::iterator iterator = list.begin();
125 ASSERT_EQ(3, *iterator);
126 ++iterator;
127 ASSERT_EQ(2, *iterator);
128 ++iterator;
129 ASSERT_EQ(1, *iterator);
130 ++iterator;
131}
132
133TEST(WTF_ListHashSet, PrependOrMoveToLastNewItems)
134{
135 ListHashSet<int> list;
136 ListHashSet<int>::AddResult result = list.prependOrMoveToFirst(1);
137 ASSERT_TRUE(result.isNewEntry);
138 result = list.add(2);
139 ASSERT_TRUE(result.isNewEntry);
140 result = list.prependOrMoveToFirst(3);
141 ASSERT_TRUE(result.isNewEntry);
142
143 ASSERT_EQ(list.size(), 3u);
144
145 // The list should be in order 3, 1, 2.
146 ListHashSet<int>::iterator iterator = list.begin();
147 ASSERT_EQ(3, *iterator);
148 ++iterator;
149 ASSERT_EQ(1, *iterator);
150 ++iterator;
151 ASSERT_EQ(2, *iterator);
152 ++iterator;
153}
154
155TEST(WTF_ListHashSet, PrependOrMoveToLastWithDuplicates)
156{
157 ListHashSet<int> list;
158
159 // Add a single element twice.
160 ListHashSet<int>::AddResult result = list.add(1);
161 ASSERT_TRUE(result.isNewEntry);
162 result = list.prependOrMoveToFirst(1);
163 ASSERT_FALSE(result.isNewEntry);
164 ASSERT_EQ(1u, list.size());
165
166 list.add(2);
167 list.add(3);
168 ASSERT_EQ(3u, list.size());
169
170 // Prepending 2 move it to the beginning.
171 ASSERT_EQ(1, list.first());
172 result = list.prependOrMoveToFirst(2);
173 ASSERT_FALSE(result.isNewEntry);
174 ASSERT_EQ(2, list.first());
175
176 // Inverse the list by moving each element to the first position.
177 result = list.prependOrMoveToFirst(1);
178 ASSERT_FALSE(result.isNewEntry);
179 result = list.prependOrMoveToFirst(2);
180 ASSERT_FALSE(result.isNewEntry);
181 result = list.prependOrMoveToFirst(3);
182 ASSERT_FALSE(result.isNewEntry);
183 ASSERT_EQ(3u, list.size());
184
185 ListHashSet<int>::iterator iterator = list.begin();
186 ASSERT_EQ(3, *iterator);
187 ++iterator;
188 ASSERT_EQ(2, *iterator);
189 ++iterator;
190 ASSERT_EQ(1, *iterator);
191 ++iterator;
192}
193
194TEST(WTF_ListHashSet, ReverseIterator)
195{
196 ListHashSet<int> list;
197
198 list.add(1);
199 list.add(2);
200 list.add(3);
201
202 auto it = list.rbegin();
203 ASSERT_EQ(3, *it);
204 ++it;
205 ASSERT_EQ(2, *it);
206 ++it;
207 ASSERT_EQ(1, *it);
208 ++it;
209 ASSERT_TRUE(it == list.rend());
210
211 const auto& listHashSet = list;
212
213 auto constIt = listHashSet.rbegin();
214 ASSERT_EQ(3, *constIt);
215 ++constIt;
216 ASSERT_EQ(2, *constIt);
217 ++constIt;
218 ASSERT_EQ(1, *constIt);
219 ++constIt;
220 ASSERT_TRUE(constIt == listHashSet.rend());
221}
222
223TEST(WTF_ListHashSet, MoveOnly)
224{
225 ListHashSet<MoveOnly> list;
226 list.add(MoveOnly(2));
227 list.add(MoveOnly(4));
228
229 // { 2, 4 }
230 ASSERT_EQ(2U, list.first().value());
231 ASSERT_EQ(4U, list.last().value());
232
233 list.appendOrMoveToLast(MoveOnly(3));
234
235 // { 2, 4, 3 }
236 ASSERT_EQ(3U, list.last().value());
237
238 // { 4, 3, 2 }
239 list.appendOrMoveToLast(MoveOnly(2));
240 ASSERT_EQ(4U, list.first().value());
241 ASSERT_EQ(2U, list.last().value());
242
243 list.prependOrMoveToFirst(MoveOnly(5));
244
245 // { 5, 2, 4, 3 }
246 ASSERT_EQ(5U, list.first().value());
247
248 list.prependOrMoveToFirst(MoveOnly(3));
249
250 // { 3, 5, 4, 2 }
251 ASSERT_EQ(3U, list.first().value());
252 ASSERT_EQ(2U, list.last().value());
253
254 list.insertBefore(MoveOnly(4), MoveOnly(1));
255 list.insertBefore(list.end(), MoveOnly(6));
256
257 // { 3, 5, 1, 4, 2, 6 }
258 ASSERT_EQ(3U, list.takeFirst().value());
259 ASSERT_EQ(5U, list.takeFirst().value());
260 ASSERT_EQ(1U, list.takeFirst().value());
261
262 // { 4, 2, 6 }
263 ASSERT_EQ(6U, list.takeLast().value());
264 ASSERT_EQ(2U, list.takeLast().value());
265 ASSERT_EQ(4U, list.takeLast().value());
266
267 ASSERT_TRUE(list.isEmpty());
268}
269
270TEST(WTF_ListHashSet, MoveConstructor)
271{
272 ListHashSet<int> list;
273 list.add(1);
274 list.add(2);
275 list.add(3);
276
277 ASSERT_EQ(3U, list.size());
278 auto iterator = list.begin();
279 ASSERT_EQ(1, *iterator);
280 ++iterator;
281 ASSERT_EQ(2, *iterator);
282 ++iterator;
283 ASSERT_EQ(3, *iterator);
284 ++iterator;
285
286 ListHashSet<int> list2(WTFMove(list));
287 ASSERT_EQ(3U, list2.size());
288 auto iterator2 = list2.begin();
289 ASSERT_EQ(1, *iterator2);
290 ++iterator2;
291 ASSERT_EQ(2, *iterator2);
292 ++iterator2;
293 ASSERT_EQ(3, *iterator2);
294 ++iterator2;
295
296 ASSERT_EQ(0U, list.size());
297 ASSERT_TRUE(list.begin() == list.end());
298 list.add(4);
299 list.add(5);
300 list.add(6);
301 iterator = list.begin();
302 ASSERT_EQ(4, *iterator);
303 ++iterator;
304 ASSERT_EQ(5, *iterator);
305 ++iterator;
306 ASSERT_EQ(6, *iterator);
307 ++iterator;
308}
309
310TEST(WTF_ListHashSet, MoveAssignment)
311{
312 ListHashSet<int> list;
313 list.add(1);
314 list.add(2);
315 list.add(3);
316
317 ASSERT_EQ(3U, list.size());
318 auto iterator = list.begin();
319 ASSERT_EQ(1, *iterator);
320 ++iterator;
321 ASSERT_EQ(2, *iterator);
322 ++iterator;
323 ASSERT_EQ(3, *iterator);
324 ++iterator;
325
326 ListHashSet<int> list2;
327 list2.add(10);
328 list2 = (WTFMove(list));
329 ASSERT_EQ(3U, list2.size());
330 auto iterator2 = list2.begin();
331 ASSERT_EQ(1, *iterator2);
332 ++iterator2;
333 ASSERT_EQ(2, *iterator2);
334 ++iterator2;
335 ASSERT_EQ(3, *iterator2);
336 ++iterator2;
337
338 ASSERT_EQ(0U, list.size());
339 ASSERT_TRUE(list.begin() == list.end());
340 list.add(4);
341 list.add(5);
342 list.add(6);
343 iterator = list.begin();
344 ASSERT_EQ(4, *iterator);
345 ++iterator;
346 ASSERT_EQ(5, *iterator);
347 ++iterator;
348 ASSERT_EQ(6, *iterator);
349 ++iterator;
350}
351
352TEST(WTF_ListHashSet, InitializerListConstuctor)
353{
354 ListHashSet<int> set { 1, 2, 3 };
355 ASSERT_EQ(3U, set.size());
356 auto iterator = set.begin();
357 ASSERT_EQ(1, *iterator);
358 ++iterator;
359 ASSERT_EQ(2, *iterator);
360 ++iterator;
361 ASSERT_EQ(3, *iterator);
362 ++iterator;
363
364 set = { 4, 5, 6, 7 };
365 ASSERT_EQ(4U, set.size());
366 iterator = set.begin();
367 ASSERT_EQ(4, *iterator);
368 ++iterator;
369 ASSERT_EQ(5, *iterator);
370 ++iterator;
371 ASSERT_EQ(6, *iterator);
372 ++iterator;
373 ASSERT_EQ(7, *iterator);
374 ++iterator;
375}
376
377TEST(WTF_ListHashSet, UniquePtrKey)
378{
379 ConstructorDestructorCounter::TestingScope scope;
380
381 ListHashSet<std::unique_ptr<ConstructorDestructorCounter>> list;
382
383 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
384 list.add(WTFMove(uniquePtr));
385
386 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
387 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
388
389 list.clear();
390
391 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
392 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
393}
394
395TEST(WTF_ListHashSet, UniquePtrKey_FindUsingRawPointer)
396{
397 ListHashSet<std::unique_ptr<int>> list;
398
399 auto uniquePtr = std::make_unique<int>(5);
400 auto ptr = uniquePtr.get();
401 list.add(WTFMove(uniquePtr));
402
403 auto it = list.find(ptr);
404 ASSERT_TRUE(it != list.end());
405 EXPECT_EQ(ptr, it->get());
406 EXPECT_EQ(5, *it->get());
407}
408
409TEST(WTF_ListHashSet, UniquePtrKey_ContainsUsingRawPointer)
410{
411 ListHashSet<std::unique_ptr<int>> list;
412
413 auto uniquePtr = std::make_unique<int>(5);
414 auto ptr = uniquePtr.get();
415 list.add(WTFMove(uniquePtr));
416
417 EXPECT_EQ(true, list.contains(ptr));
418}
419
420TEST(WTF_ListHashSet, UniquePtrKey_InsertBeforeUsingRawPointer)
421{
422 ListHashSet<std::unique_ptr<int>> list;
423
424 auto uniquePtrWith2 = std::make_unique<int>(2);
425 auto ptrWith2 = uniquePtrWith2.get();
426 auto uniquePtrWith4 = std::make_unique<int>(4);
427 auto ptrWith4 = uniquePtrWith4.get();
428
429 list.add(WTFMove(uniquePtrWith2));
430 list.add(WTFMove(uniquePtrWith4));
431
432 // { 2, 4 }
433 ASSERT_EQ(ptrWith2, list.first().get());
434 ASSERT_EQ(2, *list.first().get());
435 ASSERT_EQ(ptrWith4, list.last().get());
436 ASSERT_EQ(4, *list.last().get());
437
438 auto uniquePtrWith3 = std::make_unique<int>(3);
439 auto ptrWith3 = uniquePtrWith3.get();
440
441 list.insertBefore(ptrWith4, WTFMove(uniquePtrWith3));
442
443 // { 2, 3, 4 }
444 auto firstWith2 = list.takeFirst();
445 ASSERT_EQ(ptrWith2, firstWith2.get());
446 ASSERT_EQ(2, *firstWith2);
447
448 auto firstWith3 = list.takeFirst();
449 ASSERT_EQ(ptrWith3, firstWith3.get());
450 ASSERT_EQ(3, *firstWith3);
451
452 auto firstWith4 = list.takeFirst();
453 ASSERT_EQ(ptrWith4, firstWith4.get());
454 ASSERT_EQ(4, *firstWith4);
455
456 ASSERT_TRUE(list.isEmpty());
457}
458
459TEST(WTF_ListHashSet, UniquePtrKey_RemoveUsingRawPointer)
460{
461 ConstructorDestructorCounter::TestingScope scope;
462
463 ListHashSet<std::unique_ptr<ConstructorDestructorCounter>> list;
464
465 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
466 auto* ptr = uniquePtr.get();
467 list.add(WTFMove(uniquePtr));
468
469 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
470 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
471
472 bool result = list.remove(ptr);
473 EXPECT_EQ(true, result);
474
475 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
476 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
477}
478
479} // namespace TestWebKitAPI
480