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