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 "MoveOnly.h"
29#include <wtf/HashMap.h>
30#include <wtf/HashSet.h>
31#include <wtf/ListHashSet.h>
32#include <wtf/Vector.h>
33#include <wtf/text/StringHash.h>
34#include <wtf/text/WTFString.h>
35
36namespace TestWebKitAPI {
37
38TEST(WTF_Vector, Basic)
39{
40 Vector<int> intVector;
41 EXPECT_TRUE(intVector.isEmpty());
42 EXPECT_EQ(0U, intVector.size());
43 EXPECT_EQ(0U, intVector.capacity());
44}
45
46TEST(WTF_Vector, Iterator)
47{
48 Vector<int> intVector;
49 intVector.append(10);
50 intVector.append(11);
51 intVector.append(12);
52 intVector.append(13);
53
54 Vector<int>::iterator it = intVector.begin();
55 Vector<int>::iterator end = intVector.end();
56 EXPECT_TRUE(end != it);
57
58 EXPECT_EQ(10, *it);
59 ++it;
60 EXPECT_EQ(11, *it);
61 ++it;
62 EXPECT_EQ(12, *it);
63 ++it;
64 EXPECT_EQ(13, *it);
65 ++it;
66
67 EXPECT_TRUE(end == it);
68}
69
70TEST(WTF_Vector, OverloadedOperatorAmpersand)
71{
72 struct Test {
73 private:
74 Test* operator&() = delete;
75 };
76
77 Vector<Test> vector;
78 vector.append(Test());
79}
80
81TEST(WTF_Vector, AppendLast)
82{
83 Vector<unsigned> vector;
84 vector.append(0);
85
86 // FIXME: This test needs to be run with GuardMalloc to show the bug.
87 for (size_t i = 0; i < 100; ++i)
88 vector.append(const_cast<const unsigned&>(vector.last()));
89}
90
91TEST(WTF_Vector, InitializerList)
92{
93 Vector<int> vector = { 1, 2, 3, 4 };
94 EXPECT_EQ(4U, vector.size());
95
96 EXPECT_EQ(1, vector[0]);
97 EXPECT_EQ(2, vector[1]);
98 EXPECT_EQ(3, vector[2]);
99 EXPECT_EQ(4, vector[3]);
100}
101
102TEST(WTF_Vector, ConstructWithFrom)
103{
104 auto vector = Vector<int>::from(1, 2, 3, 4, 5);
105 EXPECT_EQ(5U, vector.size());
106 EXPECT_EQ(5U, vector.capacity());
107
108 EXPECT_EQ(1, vector[0]);
109 EXPECT_EQ(2, vector[1]);
110 EXPECT_EQ(3, vector[2]);
111 EXPECT_EQ(4, vector[3]);
112 EXPECT_EQ(5, vector[4]);
113}
114
115TEST(WTF_Vector, ConstructWithFromString)
116{
117 String s1 = "s1";
118 String s2 = "s2";
119 String s3 = s1;
120 auto vector = Vector<String>::from(s1, s2, WTFMove(s3));
121 EXPECT_EQ(3U, vector.size());
122 EXPECT_EQ(3U, vector.capacity());
123
124 EXPECT_TRUE(s1 == vector[0]);
125 EXPECT_TRUE(s2 == vector[1]);
126 EXPECT_TRUE(s1 == vector[2]);
127 EXPECT_TRUE(s3.isNull());
128}
129
130TEST(WTF_Vector, ConstructWithFromMoveOnly)
131{
132 auto vector1 = Vector<MoveOnly>::from(MoveOnly(1));
133 auto vector3 = Vector<MoveOnly>::from(MoveOnly(1), MoveOnly(2), MoveOnly(3));
134
135 EXPECT_EQ(1U, vector1.size());
136 EXPECT_EQ(1U, vector1.capacity());
137
138 EXPECT_EQ(3U, vector3.size());
139 EXPECT_EQ(3U, vector3.capacity());
140
141 EXPECT_EQ(1U, vector1[0].value());
142 EXPECT_EQ(1U, vector3[0].value());
143 EXPECT_EQ(2U, vector3[1].value());
144 EXPECT_EQ(3U, vector3[2].value());
145}
146
147TEST(WTF_Vector, InitializeFromOtherInitialCapacity)
148{
149 Vector<int, 3> vector = { 1, 3, 2, 4 };
150 Vector<int, 5> vectorCopy(vector);
151 EXPECT_EQ(4U, vector.size());
152 EXPECT_EQ(4U, vectorCopy.size());
153 EXPECT_EQ(5U, vectorCopy.capacity());
154
155 EXPECT_EQ(1, vectorCopy[0]);
156 EXPECT_EQ(3, vectorCopy[1]);
157 EXPECT_EQ(2, vectorCopy[2]);
158 EXPECT_EQ(4, vectorCopy[3]);
159}
160
161TEST(WTF_Vector, CopyFromOtherInitialCapacity)
162{
163 Vector<int, 3> vector = { 1, 3, 2, 4 };
164 Vector<int, 5> vectorCopy { 0 };
165 EXPECT_EQ(4U, vector.size());
166 EXPECT_EQ(1U, vectorCopy.size());
167
168 vectorCopy = vector;
169
170 EXPECT_EQ(4U, vector.size());
171 EXPECT_EQ(4U, vectorCopy.size());
172 EXPECT_EQ(5U, vectorCopy.capacity());
173
174 EXPECT_EQ(1, vectorCopy[0]);
175 EXPECT_EQ(3, vectorCopy[1]);
176 EXPECT_EQ(2, vectorCopy[2]);
177 EXPECT_EQ(4, vectorCopy[3]);
178}
179
180TEST(WTF_Vector, InitializeFromOtherOverflowBehavior)
181{
182 Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
183 Vector<int, 7, UnsafeVectorOverflow> vectorCopy(vector);
184 EXPECT_EQ(4U, vector.size());
185 EXPECT_EQ(4U, vectorCopy.size());
186
187 EXPECT_EQ(4, vectorCopy[0]);
188 EXPECT_EQ(3, vectorCopy[1]);
189 EXPECT_EQ(2, vectorCopy[2]);
190 EXPECT_EQ(1, vectorCopy[3]);
191}
192
193TEST(WTF_Vector, CopyFromOtherOverflowBehavior)
194{
195 Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
196 Vector<int, 7, UnsafeVectorOverflow> vectorCopy = { 0, 0, 0 };
197
198 EXPECT_EQ(4U, vector.size());
199 EXPECT_EQ(3U, vectorCopy.size());
200
201 vectorCopy = vector;
202
203 EXPECT_EQ(4U, vector.size());
204 EXPECT_EQ(4U, vectorCopy.size());
205
206 EXPECT_EQ(4, vectorCopy[0]);
207 EXPECT_EQ(3, vectorCopy[1]);
208 EXPECT_EQ(2, vectorCopy[2]);
209 EXPECT_EQ(1, vectorCopy[3]);
210}
211
212TEST(WTF_Vector, InitializeFromOtherMinCapacity)
213{
214 Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
215 Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy(vector);
216 EXPECT_EQ(4U, vector.size());
217 EXPECT_EQ(4U, vectorCopy.size());
218
219 EXPECT_EQ(3, vectorCopy[0]);
220 EXPECT_EQ(4, vectorCopy[1]);
221 EXPECT_EQ(2, vectorCopy[2]);
222 EXPECT_EQ(1, vectorCopy[3]);
223}
224
225TEST(WTF_Vector, CopyFromOtherMinCapacity)
226{
227 Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
228 Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy;
229
230 EXPECT_EQ(4U, vector.size());
231 EXPECT_EQ(0U, vectorCopy.size());
232
233 vectorCopy = vector;
234
235 EXPECT_EQ(4U, vector.size());
236 EXPECT_EQ(4U, vectorCopy.size());
237
238 EXPECT_EQ(3, vectorCopy[0]);
239 EXPECT_EQ(4, vectorCopy[1]);
240 EXPECT_EQ(2, vectorCopy[2]);
241 EXPECT_EQ(1, vectorCopy[3]);
242}
243
244TEST(WTF_Vector, Reverse)
245{
246 Vector<int> intVector;
247 intVector.append(10);
248 intVector.append(11);
249 intVector.append(12);
250 intVector.append(13);
251 intVector.reverse();
252
253 EXPECT_EQ(13, intVector[0]);
254 EXPECT_EQ(12, intVector[1]);
255 EXPECT_EQ(11, intVector[2]);
256 EXPECT_EQ(10, intVector[3]);
257
258 intVector.append(9);
259 intVector.reverse();
260
261 EXPECT_EQ(9, intVector[0]);
262 EXPECT_EQ(10, intVector[1]);
263 EXPECT_EQ(11, intVector[2]);
264 EXPECT_EQ(12, intVector[3]);
265 EXPECT_EQ(13, intVector[4]);
266}
267
268TEST(WTF_Vector, ReverseIterator)
269{
270 Vector<int> intVector;
271 intVector.append(10);
272 intVector.append(11);
273 intVector.append(12);
274 intVector.append(13);
275
276 Vector<int>::reverse_iterator it = intVector.rbegin();
277 Vector<int>::reverse_iterator end = intVector.rend();
278 EXPECT_TRUE(end != it);
279
280 EXPECT_EQ(13, *it);
281 ++it;
282 EXPECT_EQ(12, *it);
283 ++it;
284 EXPECT_EQ(11, *it);
285 ++it;
286 EXPECT_EQ(10, *it);
287 ++it;
288
289 EXPECT_TRUE(end == it);
290}
291
292TEST(WTF_Vector, MoveOnly_UncheckedAppend)
293{
294 Vector<MoveOnly> vector;
295
296 vector.reserveInitialCapacity(100);
297 for (size_t i = 0; i < 100; ++i) {
298 MoveOnly moveOnly(i);
299 vector.uncheckedAppend(WTFMove(moveOnly));
300 EXPECT_EQ(0U, moveOnly.value());
301 }
302
303 for (size_t i = 0; i < 100; ++i)
304 EXPECT_EQ(i, vector[i].value());
305}
306
307TEST(WTF_Vector, MoveOnly_Append)
308{
309 Vector<MoveOnly> vector;
310
311 for (size_t i = 0; i < 100; ++i) {
312 MoveOnly moveOnly(i);
313 vector.append(WTFMove(moveOnly));
314 EXPECT_EQ(0U, moveOnly.value());
315 }
316
317 for (size_t i = 0; i < 100; ++i)
318 EXPECT_EQ(i, vector[i].value());
319
320 for (size_t i = 0; i < 16; ++i) {
321 Vector<MoveOnly> vector;
322
323 vector.append(i);
324
325 for (size_t j = 0; j < i; ++j)
326 vector.append(j);
327 vector.append(WTFMove(vector[0]));
328
329 EXPECT_EQ(0U, vector[0].value());
330
331 for (size_t j = 0; j < i; ++j)
332 EXPECT_EQ(j, vector[j + 1].value());
333 EXPECT_EQ(i, vector.last().value());
334 }
335}
336
337TEST(WTF_Vector, MoveOnly_Insert)
338{
339 Vector<MoveOnly> vector;
340
341 for (size_t i = 0; i < 100; ++i) {
342 MoveOnly moveOnly(i);
343 vector.insert(0, WTFMove(moveOnly));
344 EXPECT_EQ(0U, moveOnly.value());
345 }
346
347 EXPECT_EQ(vector.size(), 100U);
348 for (size_t i = 0; i < 100; ++i)
349 EXPECT_EQ(99 - i, vector[i].value());
350
351 for (size_t i = 0; i < 200; i += 2) {
352 MoveOnly moveOnly(1000 + i);
353 vector.insert(i, WTFMove(moveOnly));
354 EXPECT_EQ(0U, moveOnly.value());
355 }
356
357 EXPECT_EQ(200U, vector.size());
358 for (size_t i = 0; i < 200; ++i) {
359 if (i % 2)
360 EXPECT_EQ(99 - i / 2, vector[i].value());
361 else
362 EXPECT_EQ(1000 + i, vector[i].value());
363 }
364}
365
366TEST(WTF_Vector, MoveOnly_TakeLast)
367{
368 Vector<MoveOnly> vector;
369
370 for (size_t i = 0; i < 100; ++i) {
371 MoveOnly moveOnly(i);
372 vector.append(WTFMove(moveOnly));
373 EXPECT_EQ(0U, moveOnly.value());
374 }
375
376 EXPECT_EQ(100U, vector.size());
377 for (size_t i = 0; i < 100; ++i)
378 EXPECT_EQ(99 - i, vector.takeLast().value());
379
380 EXPECT_EQ(0U, vector.size());
381}
382
383TEST(WTF_Vector, VectorOfVectorsOfVectorsInlineCapacitySwap)
384{
385 Vector<Vector<Vector<int, 1>, 1>, 1> a;
386 Vector<Vector<Vector<int, 1>, 1>, 1> b;
387 Vector<Vector<Vector<int, 1>, 1>, 1> c;
388
389 EXPECT_EQ(0U, a.size());
390 EXPECT_EQ(0U, b.size());
391 EXPECT_EQ(0U, c.size());
392
393 Vector<int, 1> x;
394 x.append(42);
395
396 EXPECT_EQ(1U, x.size());
397 EXPECT_EQ(42, x[0]);
398
399 Vector<Vector<int, 1>, 1> y;
400 y.append(x);
401
402 EXPECT_EQ(1U, x.size());
403 EXPECT_EQ(42, x[0]);
404 EXPECT_EQ(1U, y.size());
405 EXPECT_EQ(1U, y[0].size());
406 EXPECT_EQ(42, y[0][0]);
407
408 a.append(y);
409
410 EXPECT_EQ(1U, x.size());
411 EXPECT_EQ(42, x[0]);
412 EXPECT_EQ(1U, y.size());
413 EXPECT_EQ(1U, y[0].size());
414 EXPECT_EQ(42, y[0][0]);
415 EXPECT_EQ(1U, a.size());
416 EXPECT_EQ(1U, a[0].size());
417 EXPECT_EQ(1U, a[0][0].size());
418 EXPECT_EQ(42, a[0][0][0]);
419
420 a.swap(b);
421
422 EXPECT_EQ(0U, a.size());
423 EXPECT_EQ(1U, x.size());
424 EXPECT_EQ(42, x[0]);
425 EXPECT_EQ(1U, y.size());
426 EXPECT_EQ(1U, y[0].size());
427 EXPECT_EQ(42, y[0][0]);
428 EXPECT_EQ(1U, b.size());
429 EXPECT_EQ(1U, b[0].size());
430 EXPECT_EQ(1U, b[0][0].size());
431 EXPECT_EQ(42, b[0][0][0]);
432
433 b.swap(c);
434
435 EXPECT_EQ(0U, a.size());
436 EXPECT_EQ(0U, b.size());
437 EXPECT_EQ(1U, x.size());
438 EXPECT_EQ(42, x[0]);
439 EXPECT_EQ(1U, y.size());
440 EXPECT_EQ(1U, y[0].size());
441 EXPECT_EQ(42, y[0][0]);
442 EXPECT_EQ(1U, c.size());
443 EXPECT_EQ(1U, c[0].size());
444 EXPECT_EQ(1U, c[0][0].size());
445 EXPECT_EQ(42, c[0][0][0]);
446
447 y[0][0] = 24;
448
449 EXPECT_EQ(1U, x.size());
450 EXPECT_EQ(42, x[0]);
451 EXPECT_EQ(1U, y.size());
452 EXPECT_EQ(1U, y[0].size());
453 EXPECT_EQ(24, y[0][0]);
454
455 a.append(y);
456
457 EXPECT_EQ(1U, x.size());
458 EXPECT_EQ(42, x[0]);
459 EXPECT_EQ(1U, y.size());
460 EXPECT_EQ(1U, y[0].size());
461 EXPECT_EQ(24, y[0][0]);
462 EXPECT_EQ(1U, a.size());
463 EXPECT_EQ(1U, a[0].size());
464 EXPECT_EQ(1U, a[0][0].size());
465 EXPECT_EQ(24, a[0][0][0]);
466 EXPECT_EQ(1U, c.size());
467 EXPECT_EQ(1U, c[0].size());
468 EXPECT_EQ(1U, c[0][0].size());
469 EXPECT_EQ(42, c[0][0][0]);
470 EXPECT_EQ(0U, b.size());
471}
472
473TEST(WTF_Vector, RemoveFirst)
474{
475 Vector<int> v;
476 EXPECT_TRUE(v.isEmpty());
477 EXPECT_FALSE(v.removeFirst(1));
478 EXPECT_FALSE(v.removeFirst(-1));
479 EXPECT_TRUE(v.isEmpty());
480
481 v.fill(2, 10);
482 EXPECT_EQ(10U, v.size());
483 EXPECT_FALSE(v.removeFirst(1));
484 EXPECT_EQ(10U, v.size());
485 v.clear();
486
487 v.fill(1, 10);
488 EXPECT_EQ(10U, v.size());
489 EXPECT_TRUE(v.removeFirst(1));
490 EXPECT_TRUE(v == Vector<int>({1, 1, 1, 1, 1, 1, 1, 1, 1}));
491 EXPECT_EQ(9U, v.size());
492 EXPECT_FALSE(v.removeFirst(2));
493 EXPECT_EQ(9U, v.size());
494 EXPECT_TRUE(v == Vector<int>({1, 1, 1, 1, 1, 1, 1, 1, 1}));
495
496 unsigned removed = 0;
497 while (v.removeFirst(1))
498 ++removed;
499 EXPECT_EQ(9U, removed);
500 EXPECT_TRUE(v.isEmpty());
501
502 v.resize(1);
503 EXPECT_EQ(1U, v.size());
504 EXPECT_TRUE(v.removeFirst(1));
505 EXPECT_EQ(0U, v.size());
506 EXPECT_TRUE(v.isEmpty());
507}
508
509TEST(WTF_Vector, RemoveAll)
510{
511 // Using a memcpy-able type.
512 static_assert(VectorTraits<int>::canMoveWithMemcpy, "Should use a memcpy-able type");
513 Vector<int> v;
514 EXPECT_TRUE(v.isEmpty());
515 EXPECT_FALSE(v.removeAll(1));
516 EXPECT_FALSE(v.removeAll(-1));
517 EXPECT_TRUE(v.isEmpty());
518
519 v.fill(1, 10);
520 EXPECT_EQ(10U, v.size());
521 EXPECT_EQ(10U, v.removeAll(1));
522 EXPECT_TRUE(v.isEmpty());
523
524 v.fill(2, 10);
525 EXPECT_EQ(10U, v.size());
526 EXPECT_EQ(0U, v.removeAll(1));
527 EXPECT_EQ(10U, v.size());
528
529 v = {1, 2, 1, 2, 1, 2, 2, 1, 1, 1};
530 EXPECT_EQ(10U, v.size());
531 EXPECT_EQ(6U, v.removeAll(1));
532 EXPECT_EQ(4U, v.size());
533 EXPECT_TRUE(v == Vector<int>({2, 2, 2, 2}));
534 EXPECT_TRUE(v.find(1) == notFound);
535 EXPECT_EQ(4U, v.removeAll(2));
536 EXPECT_TRUE(v.isEmpty());
537
538 v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
539 EXPECT_EQ(12U, v.size());
540 EXPECT_EQ(6U, v.removeAll(1));
541 EXPECT_EQ(6U, v.size());
542 EXPECT_TRUE(v.find(1) == notFound);
543 EXPECT_TRUE(v == Vector<int>({3, 2, 2, 2, 2, 3}));
544
545 EXPECT_EQ(4U, v.removeAll(2));
546 EXPECT_EQ(2U, v.size());
547 EXPECT_TRUE(v.find(2) == notFound);
548 EXPECT_TRUE(v == Vector<int>({3, 3}));
549
550 EXPECT_EQ(2U, v.removeAll(3));
551 EXPECT_TRUE(v.isEmpty());
552
553 v = {1, 1, 1, 3, 2, 4, 2, 2, 2, 4, 4, 3};
554 EXPECT_EQ(12U, v.size());
555 EXPECT_EQ(3U, v.removeAll(1));
556 EXPECT_EQ(9U, v.size());
557 EXPECT_TRUE(v.find(1) == notFound);
558 EXPECT_TRUE(v == Vector<int>({3, 2, 4, 2, 2, 2, 4, 4, 3}));
559
560 // Using a non memcpy-able type.
561 static_assert(!VectorTraits<CString>::canMoveWithMemcpy, "Should use a non memcpy-able type");
562 Vector<CString> vExpected;
563 Vector<CString> v2;
564 EXPECT_TRUE(v2.isEmpty());
565 EXPECT_FALSE(v2.removeAll("1"));
566 EXPECT_TRUE(v2.isEmpty());
567
568 v2.fill("1", 10);
569 EXPECT_EQ(10U, v2.size());
570 EXPECT_EQ(10U, v2.removeAll("1"));
571 EXPECT_TRUE(v2.isEmpty());
572
573 v2.fill("2", 10);
574 EXPECT_EQ(10U, v2.size());
575 EXPECT_EQ(0U, v2.removeAll("1"));
576 EXPECT_EQ(10U, v2.size());
577
578 v2 = {"1", "2", "1", "2", "1", "2", "2", "1", "1", "1"};
579 EXPECT_EQ(10U, v2.size());
580 EXPECT_EQ(6U, v2.removeAll("1"));
581 EXPECT_EQ(4U, v2.size());
582 EXPECT_TRUE(v2.find("1") == notFound);
583 EXPECT_EQ(4U, v2.removeAll("2"));
584 EXPECT_TRUE(v2.isEmpty());
585
586 v2 = {"3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3"};
587 EXPECT_EQ(12U, v2.size());
588 EXPECT_EQ(6U, v2.removeAll("1"));
589 EXPECT_EQ(6U, v2.size());
590 EXPECT_TRUE(v2.find("1") == notFound);
591 vExpected = {"3", "2", "2", "2", "2", "3"};
592 EXPECT_TRUE(v2 == vExpected);
593
594 EXPECT_EQ(4U, v2.removeAll("2"));
595 EXPECT_EQ(2U, v2.size());
596 EXPECT_TRUE(v2.find("2") == notFound);
597 vExpected = {"3", "3"};
598 EXPECT_TRUE(v2 == vExpected);
599
600 EXPECT_EQ(2U, v2.removeAll("3"));
601 EXPECT_TRUE(v2.isEmpty());
602
603 v2 = {"1", "1", "1", "3", "2", "4", "2", "2", "2", "4", "4", "3"};
604 EXPECT_EQ(12U, v2.size());
605 EXPECT_EQ(3U, v2.removeAll("1"));
606 EXPECT_EQ(9U, v2.size());
607 EXPECT_TRUE(v2.find("1") == notFound);
608 vExpected = {"3", "2", "4", "2", "2", "2", "4", "4", "3"};
609 EXPECT_TRUE(v2 == vExpected);
610}
611
612TEST(WTF_Vector, FindMatching)
613{
614 Vector<int> v;
615 EXPECT_TRUE(v.findMatching([](int) { return false; }) == notFound);
616 EXPECT_TRUE(v.findMatching([](int) { return true; }) == notFound);
617
618 v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
619 EXPECT_TRUE(v.findMatching([](int value) { return value > 3; }) == notFound);
620 EXPECT_TRUE(v.findMatching([](int) { return false; }) == notFound);
621 EXPECT_EQ(0U, v.findMatching([](int) { return true; }));
622 EXPECT_EQ(0U, v.findMatching([](int value) { return value <= 3; }));
623 EXPECT_EQ(1U, v.findMatching([](int value) { return value < 3; }));
624 EXPECT_EQ(2U, v.findMatching([](int value) { return value == 2; }));
625}
626
627TEST(WTF_Vector, RemoveFirstMatching)
628{
629 Vector<int> v;
630 EXPECT_TRUE(v.isEmpty());
631 EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value > 0; }));
632 EXPECT_FALSE(v.removeFirstMatching([] (int) { return true; }));
633 EXPECT_FALSE(v.removeFirstMatching([] (int) { return false; }));
634
635 v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
636 EXPECT_EQ(12U, v.size());
637 EXPECT_FALSE(v.removeFirstMatching([] (int) { return false; }));
638 EXPECT_EQ(12U, v.size());
639 EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value < 0; }));
640 EXPECT_EQ(12U, v.size());
641 EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value < 3; }));
642 EXPECT_EQ(11U, v.size());
643 EXPECT_TRUE(v == Vector<int>({3, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3}));
644 EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value > 2; }));
645 EXPECT_EQ(10U, v.size());
646 EXPECT_TRUE(v == Vector<int>({2, 1, 2, 1, 2, 2, 1, 1, 1, 3}));
647 EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value > 2; }));
648 EXPECT_EQ(9U, v.size());
649 EXPECT_TRUE(v == Vector<int>({2, 1, 2, 1, 2, 2, 1, 1, 1}));
650 EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value == 1; }, 1));
651 EXPECT_EQ(8U, v.size());
652 EXPECT_TRUE(v == Vector<int>({2, 2, 1, 2, 2, 1, 1, 1}));
653 EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value == 1; }, 3));
654 EXPECT_EQ(7U, v.size());
655 EXPECT_TRUE(v == Vector<int>({2, 2, 1, 2, 2, 1, 1}));
656 EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value == 1; }, 7));
657 EXPECT_EQ(7U, v.size());
658 EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value == 1; }, 10));
659 EXPECT_EQ(7U, v.size());
660}
661
662TEST(WTF_Vector, RemoveAllMatching)
663{
664 Vector<int> v;
665 EXPECT_TRUE(v.isEmpty());
666 EXPECT_FALSE(v.removeAllMatching([] (int value) { return value > 0; }));
667 EXPECT_FALSE(v.removeAllMatching([] (int) { return true; }));
668 EXPECT_FALSE(v.removeAllMatching([] (int) { return false; }));
669
670 v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
671 EXPECT_EQ(12U, v.size());
672 EXPECT_EQ(0U, v.removeAllMatching([] (int) { return false; }));
673 EXPECT_EQ(12U, v.size());
674 EXPECT_EQ(0U, v.removeAllMatching([] (int value) { return value < 0; }));
675 EXPECT_EQ(12U, v.size());
676 EXPECT_EQ(12U, v.removeAllMatching([] (int value) { return value > 0; }));
677 EXPECT_TRUE(v.isEmpty());
678
679 v = {3, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 1, 3};
680 EXPECT_EQ(13U, v.size());
681 EXPECT_EQ(3U, v.removeAllMatching([] (int value) { return value > 2; }));
682 EXPECT_EQ(10U, v.size());
683 EXPECT_TRUE(v == Vector<int>({1, 2, 1, 2, 1, 2, 2, 1, 1, 1}));
684 EXPECT_EQ(6U, v.removeAllMatching([] (int value) { return value != 2; }));
685 EXPECT_EQ(4U, v.size());
686 EXPECT_TRUE(v == Vector<int>({2, 2, 2, 2}));
687 EXPECT_EQ(4U, v.removeAllMatching([] (int value) { return value == 2; }));
688 EXPECT_TRUE(v.isEmpty());
689
690 v = {3, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 1, 3};
691 EXPECT_EQ(13U, v.size());
692 EXPECT_EQ(0U, v.removeAllMatching([] (int value) { return value > 0; }, 13));
693 EXPECT_EQ(13U, v.size());
694 EXPECT_EQ(0U, v.removeAllMatching([] (int value) { return value > 0; }, 20));
695 EXPECT_EQ(13U, v.size());
696 EXPECT_EQ(5U, v.removeAllMatching([] (int value) { return value > 1; }, 3));
697 EXPECT_EQ(8U, v.size());
698 EXPECT_TRUE(v == Vector<int>({3, 1, 2, 1, 1, 1, 1, 1}));
699 EXPECT_EQ(8U, v.removeAllMatching([] (int value) { return value > 0; }, 0));
700 EXPECT_EQ(0U, v.size());
701}
702
703static int multiplyByTwo(int value)
704{
705 return 2 * value;
706}
707
708TEST(WTF_Vector, MapStaticFunction)
709{
710 Vector<int> vector { 2, 3, 4 };
711
712 auto mapped = WTF::map(vector, multiplyByTwo);
713
714 EXPECT_EQ(3U, mapped.size());
715 EXPECT_EQ(4, mapped[0]);
716 EXPECT_EQ(6, mapped[1]);
717 EXPECT_EQ(8, mapped[2]);
718}
719
720static MoveOnly multiplyByTwoMoveOnly(const MoveOnly& value)
721{
722 return MoveOnly(2 * value.value());
723}
724
725TEST(WTF_Vector, MapStaticFunctionMoveOnly)
726{
727 Vector<MoveOnly> vector;
728
729 vector.reserveInitialCapacity(3);
730 for (unsigned i = 0; i < 3; ++i)
731 vector.uncheckedAppend(MoveOnly { i });
732
733 auto mapped = WTF::map(vector, multiplyByTwoMoveOnly);
734
735 EXPECT_EQ(3U, mapped.size());
736 EXPECT_EQ(0U, mapped[0].value());
737 EXPECT_EQ(2U, mapped[1].value());
738 EXPECT_EQ(4U, mapped[2].value());
739}
740
741TEST(WTF_Vector, MapLambda)
742{
743 Vector<int> vector { 2, 3, 4 };
744
745 int counter = 0;
746 auto mapped = WTF::map(vector, [&] (int item) {
747 counter += 2;
748 return counter <= item;
749 });
750
751 EXPECT_EQ(3U, mapped.size());
752 EXPECT_TRUE(mapped[0]);
753 EXPECT_FALSE(mapped[1]);
754 EXPECT_FALSE(mapped[2]);
755}
756
757TEST(WTF_Vector, MapLambdaMove)
758{
759 Vector<MoveOnly> vector;
760
761 vector.reserveInitialCapacity(3);
762 for (unsigned i = 0; i < 3; ++i)
763 vector.uncheckedAppend(MoveOnly { i });
764
765
766 unsigned counter = 0;
767 auto mapped = WTF::map(WTFMove(vector), [&] (MoveOnly&& item) {
768 item = item.value() + ++counter;
769 return WTFMove(item);
770 });
771
772 EXPECT_EQ(3U, mapped.size());
773 EXPECT_EQ(1U, mapped[0].value());
774 EXPECT_EQ(3U, mapped[1].value());
775 EXPECT_EQ(5U, mapped[2].value());
776}
777
778TEST(WTF_Vector, MapFromHashMap)
779{
780 HashMap<String, String> map;
781 map.set(String { "k1" }, String { "v1" });
782 map.set(String { "k2" }, String { "v2" });
783 map.set(String { "k3" }, String { "v3" });
784
785 auto mapped = WTF::map(map, [&] (KeyValuePair<String, String>& pair) -> String {
786 return pair.value;
787 });
788 std::sort(mapped.begin(), mapped.end(), WTF::codePointCompareLessThan);
789
790 EXPECT_EQ(3U, mapped.size());
791 EXPECT_TRUE(mapped[0] == "v1");
792 EXPECT_TRUE(mapped[1] == "v2");
793 EXPECT_TRUE(mapped[2] == "v3");
794
795 mapped = WTF::map(map, [&] (const auto& pair) -> String {
796 return pair.key;
797 });
798 std::sort(mapped.begin(), mapped.end(), WTF::codePointCompareLessThan);
799
800 EXPECT_EQ(3U, mapped.size());
801 EXPECT_TRUE(mapped[0] == "k1");
802 EXPECT_TRUE(mapped[1] == "k2");
803 EXPECT_TRUE(mapped[2] == "k3");
804
805 mapped = WTF::map(WTFMove(map), [&] (KeyValuePair<String, String>&& pair) -> String {
806 return WTFMove(pair.value);
807 });
808 std::sort(mapped.begin(), mapped.end(), WTF::codePointCompareLessThan);
809
810 EXPECT_EQ(3U, mapped.size());
811 EXPECT_TRUE(mapped[0] == "v1");
812 EXPECT_TRUE(mapped[1] == "v2");
813 EXPECT_TRUE(mapped[2] == "v3");
814
815 EXPECT_TRUE(map.contains("k1"));
816 EXPECT_TRUE(map.contains("k2"));
817 EXPECT_TRUE(map.contains("k3"));
818
819 EXPECT_TRUE(map.get("k1").isNull());
820 EXPECT_TRUE(map.get("k2").isNull());
821 EXPECT_TRUE(map.get("k3").isNull());
822
823}
824
825TEST(WTF_Vector, CopyToVector)
826{
827 HashSet<int> intSet { 1, 2, 3 };
828
829 auto vector = copyToVector(intSet);
830 EXPECT_EQ(3U, vector.size());
831
832 std::sort(vector.begin(), vector.end());
833 EXPECT_EQ(1, vector[0]);
834 EXPECT_EQ(2, vector[1]);
835 EXPECT_EQ(3, vector[2]);
836}
837
838TEST(WTF_Vector, CopyToVectorOrderPreserving)
839{
840 ListHashSet<int> orderedIntSet;
841 orderedIntSet.add(1);
842 orderedIntSet.add(2);
843 orderedIntSet.add(3);
844
845 auto vector = copyToVector(orderedIntSet);
846 EXPECT_EQ(3U, vector.size());
847
848 EXPECT_EQ(1, vector[0]);
849 EXPECT_EQ(2, vector[1]);
850 EXPECT_EQ(3, vector[2]);
851}
852
853TEST(WTF_Vector, CopyToVectorOf)
854{
855 HashSet<int> intSet { 1, 2, 3 };
856
857 Vector<float> vector = copyToVectorOf<float>(intSet);
858 EXPECT_EQ(3U, vector.size());
859
860 std::sort(vector.begin(), vector.end());
861 EXPECT_FLOAT_EQ(1, vector[0]);
862 EXPECT_FLOAT_EQ(2, vector[1]);
863 EXPECT_FLOAT_EQ(3, vector[2]);
864}
865
866TEST(WTF_Vector, CopyToVectorSizeRangeIterator)
867{
868 HashMap<int, float> map {
869 { 1, 9 },
870 { 2, 8 },
871 { 3, 7 }
872 };
873
874 auto keysVector = copyToVector(map.keys());
875 EXPECT_EQ(3U, keysVector.size());
876
877 std::sort(keysVector.begin(), keysVector.end());
878 EXPECT_EQ(1, keysVector[0]);
879 EXPECT_EQ(2, keysVector[1]);
880 EXPECT_EQ(3, keysVector[2]);
881
882 auto valuesVector = copyToVector(map.values());
883 EXPECT_EQ(3U, valuesVector.size());
884
885 std::sort(valuesVector.begin(), valuesVector.end());
886 EXPECT_FLOAT_EQ(7, valuesVector[0]);
887 EXPECT_FLOAT_EQ(8, valuesVector[1]);
888 EXPECT_FLOAT_EQ(9, valuesVector[2]);
889}
890
891TEST(WTF_Vector, StringComparison)
892{
893 Vector<String> a = {{ "a" }};
894 Vector<String> b = {{ "a" }};
895 EXPECT_TRUE(a == b);
896}
897
898} // namespace TestWebKitAPI
899