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