jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/DeprecatedString.h>
10#include <AK/OwnPtr.h>
11#include <AK/ReverseIterator.h>
12#include <AK/Vector.h>
13
14TEST_CASE(construct)
15{
16 EXPECT(Vector<int>().is_empty());
17 EXPECT(Vector<int>().size() == 0);
18}
19
20TEST_CASE(ints)
21{
22 Vector<int> ints;
23 ints.append(1);
24 ints.append(2);
25 ints.append(3);
26 EXPECT_EQ(ints.size(), 3u);
27 EXPECT_EQ(ints.take_last(), 3);
28 EXPECT_EQ(ints.size(), 2u);
29 EXPECT_EQ(ints.take_last(), 2);
30 EXPECT_EQ(ints.size(), 1u);
31 EXPECT_EQ(ints.take_last(), 1);
32 EXPECT_EQ(ints.size(), 0u);
33
34 ints.clear();
35 EXPECT_EQ(ints.size(), 0u);
36}
37
38TEST_CASE(strings)
39{
40 Vector<DeprecatedString> strings;
41 strings.append("ABC");
42 strings.append("DEF");
43
44 int loop_counter = 0;
45 for (DeprecatedString const& string : strings) {
46 EXPECT(!string.is_null());
47 EXPECT(!string.is_empty());
48 ++loop_counter;
49 }
50
51 loop_counter = 0;
52 for (auto& string : (const_cast<Vector<DeprecatedString> const&>(strings))) {
53 EXPECT(!string.is_null());
54 EXPECT(!string.is_empty());
55 ++loop_counter;
56 }
57 EXPECT_EQ(loop_counter, 2);
58}
59
60TEST_CASE(strings_insert_ordered)
61{
62 Vector<DeprecatedString> strings;
63 strings.append("abc");
64 strings.append("def");
65 strings.append("ghi");
66
67 strings.insert_before_matching("f-g"sv, [](auto& entry) {
68 return "f-g"sv < entry;
69 });
70
71 EXPECT_EQ(strings[0], "abc");
72 EXPECT_EQ(strings[1], "def");
73 EXPECT_EQ(strings[2], "f-g");
74 EXPECT_EQ(strings[3], "ghi");
75}
76
77TEST_CASE(prepend_vector)
78{
79 Vector<int> ints;
80 ints.append(1);
81 ints.append(2);
82 ints.append(3);
83
84 Vector<int> more_ints;
85 more_ints.append(4);
86 more_ints.append(5);
87 more_ints.append(6);
88
89 ints.prepend(move(more_ints));
90
91 EXPECT_EQ(ints.size(), 6u);
92 EXPECT_EQ(more_ints.size(), 0u);
93
94 EXPECT_EQ(ints[0], 4);
95 EXPECT_EQ(ints[1], 5);
96 EXPECT_EQ(ints[2], 6);
97 EXPECT_EQ(ints[3], 1);
98 EXPECT_EQ(ints[4], 2);
99 EXPECT_EQ(ints[5], 3);
100
101 ints.prepend(move(more_ints));
102 EXPECT_EQ(ints.size(), 6u);
103 EXPECT_EQ(more_ints.size(), 0u);
104
105 more_ints.prepend(move(ints));
106 EXPECT_EQ(more_ints.size(), 6u);
107 EXPECT_EQ(ints.size(), 0u);
108}
109
110TEST_CASE(prepend_vector_object)
111{
112 struct SubObject {
113 SubObject(int v)
114 : value(v)
115 {
116 }
117 int value { 0 };
118 };
119 struct Object {
120 Object(NonnullOwnPtr<SubObject>&& a_subobject)
121 : subobject(move(a_subobject))
122 {
123 }
124 OwnPtr<SubObject> subobject;
125 };
126
127 Vector<Object> objects;
128 objects.empend(make<SubObject>(1));
129 objects.empend(make<SubObject>(2));
130 objects.empend(make<SubObject>(3));
131
132 EXPECT_EQ(objects.size(), 3u);
133
134 Vector<Object> more_objects;
135 more_objects.empend(make<SubObject>(4));
136 more_objects.empend(make<SubObject>(5));
137 more_objects.empend(make<SubObject>(6));
138 EXPECT_EQ(more_objects.size(), 3u);
139
140 objects.prepend(move(more_objects));
141 EXPECT_EQ(more_objects.size(), 0u);
142 EXPECT_EQ(objects.size(), 6u);
143
144 EXPECT_EQ(objects[0].subobject->value, 4);
145 EXPECT_EQ(objects[1].subobject->value, 5);
146 EXPECT_EQ(objects[2].subobject->value, 6);
147 EXPECT_EQ(objects[3].subobject->value, 1);
148 EXPECT_EQ(objects[4].subobject->value, 2);
149 EXPECT_EQ(objects[5].subobject->value, 3);
150}
151
152TEST_CASE(vector_compare)
153{
154 Vector<int> ints;
155 Vector<int> same_ints;
156
157 for (int i = 0; i < 1000; ++i) {
158 ints.append(i);
159 same_ints.append(i);
160 }
161
162 EXPECT_EQ(ints.size(), 1000u);
163 EXPECT_EQ(ints, same_ints);
164
165 Vector<DeprecatedString> strings;
166 Vector<DeprecatedString> same_strings;
167
168 for (int i = 0; i < 1000; ++i) {
169 strings.append(DeprecatedString::number(i));
170 same_strings.append(DeprecatedString::number(i));
171 }
172
173 EXPECT_EQ(strings.size(), 1000u);
174 EXPECT_EQ(strings, same_strings);
175}
176
177TEST_CASE(grow_past_inline_capacity)
178{
179 auto make_vector = [] {
180 Vector<DeprecatedString, 16> strings;
181 for (int i = 0; i < 32; ++i) {
182 strings.append(DeprecatedString::number(i));
183 }
184 return strings;
185 };
186
187 auto strings = make_vector();
188
189 EXPECT_EQ(strings.size(), 32u);
190 EXPECT_EQ(strings[31], "31");
191
192 strings.clear();
193 EXPECT_EQ(strings.size(), 0u);
194 EXPECT_EQ(strings.capacity(), 16u);
195
196 strings = make_vector();
197
198 strings.clear_with_capacity();
199 EXPECT_EQ(strings.size(), 0u);
200 EXPECT(strings.capacity() >= 32u);
201}
202
203BENCHMARK_CASE(vector_append_trivial)
204{
205 // This should be super fast thanks to Vector using memmove.
206 Vector<int> ints;
207 for (int i = 0; i < 1000000; ++i) {
208 ints.append(i);
209 }
210 for (int i = 0; i < 100; ++i) {
211 Vector<int> tmp;
212 tmp.extend(ints);
213 EXPECT_EQ(tmp.size(), 1000000u);
214 }
215}
216
217BENCHMARK_CASE(vector_remove_trivial)
218{
219 // This should be super fast thanks to Vector using memmove.
220 Vector<int> ints;
221 for (int i = 0; i < 10000; ++i) {
222 ints.append(i);
223 }
224 while (!ints.is_empty()) {
225 ints.remove(0);
226 }
227 EXPECT_EQ(ints.size(), 0u);
228}
229
230TEST_CASE(vector_remove)
231{
232 Vector<int> ints;
233 ints.append(1);
234 ints.append(2);
235 ints.append(3);
236 ints.append(4);
237 ints.append(5);
238
239 ints.remove(1);
240 EXPECT_EQ(ints.size(), 4u);
241 EXPECT_EQ(ints[0], 1);
242 EXPECT_EQ(ints[1], 3);
243 EXPECT_EQ(ints[2], 4);
244 EXPECT_EQ(ints[3], 5);
245
246 ints.remove(0);
247 EXPECT_EQ(ints.size(), 3u);
248 EXPECT_EQ(ints[0], 3);
249 EXPECT_EQ(ints[1], 4);
250 EXPECT_EQ(ints[2], 5);
251
252 ints.take_last();
253 EXPECT_EQ(ints.size(), 2u);
254 EXPECT_EQ(ints[0], 3);
255 EXPECT_EQ(ints[1], 4);
256
257 ints.take_first();
258 EXPECT_EQ(ints.size(), 1u);
259 EXPECT_EQ(ints[0], 4);
260}
261
262TEST_CASE(remove_all_matching)
263{
264 Vector<int> ints;
265
266 ints.append(1);
267 ints.append(2);
268 ints.append(3);
269 ints.append(4);
270
271 EXPECT_EQ(ints.size(), 4u);
272
273 EXPECT_EQ(ints.remove_all_matching([&](int value) { return value > 2; }), true);
274 EXPECT_EQ(ints.remove_all_matching([&](int) { return false; }), false);
275
276 EXPECT_EQ(ints.size(), 2u);
277
278 EXPECT_EQ(ints.remove_all_matching([&](int) { return true; }), true);
279
280 EXPECT(ints.is_empty());
281
282 EXPECT_EQ(ints.remove_all_matching([&](int) { return true; }), false);
283}
284
285TEST_CASE(nonnullownptrvector)
286{
287 struct Object {
288 DeprecatedString string;
289 };
290 Vector<NonnullOwnPtr<Object>> objects;
291
292 objects.append(make<Object>());
293 EXPECT_EQ(objects.size(), 1u);
294
295 OwnPtr<Object> o = make<Object>();
296 objects.append(o.release_nonnull());
297 EXPECT(o == nullptr);
298 EXPECT_EQ(objects.size(), 2u);
299}
300
301TEST_CASE(insert_trivial)
302{
303 Vector<int> ints;
304 ints.append(0);
305 ints.append(10);
306 ints.append(20);
307 ints.append(30);
308 ints.append(40);
309 ints.insert(2, 15);
310 EXPECT_EQ(ints.size(), 6u);
311 EXPECT_EQ(ints[0], 0);
312 EXPECT_EQ(ints[1], 10);
313 EXPECT_EQ(ints[2], 15);
314 EXPECT_EQ(ints[3], 20);
315 EXPECT_EQ(ints[4], 30);
316 EXPECT_EQ(ints[5], 40);
317}
318
319TEST_CASE(resize_initializes)
320{
321 struct A {
322 A() { initialized = true; }
323 bool initialized { false };
324 };
325
326 Vector<A> ints;
327 ints.resize(32);
328
329 for (size_t idx = 0; idx < 32; ++idx)
330 EXPECT(ints[idx].initialized);
331}
332
333TEST_CASE(should_compare_vectors_of_same_type)
334{
335 Vector<int> a {};
336 Vector<int> b {};
337
338 EXPECT(a == b);
339 EXPECT(!(a != b));
340
341 a.append(1);
342 EXPECT(!(a == b));
343 EXPECT(a != b);
344
345 b.append(1);
346 EXPECT(a == b);
347 EXPECT(!(a != b));
348
349 a.append(42);
350 b.append(17);
351 EXPECT(!(a == b));
352 EXPECT(a != b);
353}
354
355TEST_CASE(should_compare_vectors_of_different_inline_capacity)
356{
357 Vector<int, 1> a {};
358 Vector<int, 64> b {};
359
360 EXPECT(a == b);
361 EXPECT(!(a != b));
362
363 a.append(1);
364 EXPECT(!(a == b));
365 EXPECT(a != b);
366
367 b.append(1);
368 EXPECT(a == b);
369 EXPECT(!(a != b));
370
371 a.append(42);
372 b.append(17);
373 EXPECT(!(a == b));
374 EXPECT(a != b);
375}
376
377TEST_CASE(should_compare_vectors_of_different_sizes)
378{
379 Vector<int, 0> a {};
380 Vector<int, 0> b {};
381
382 EXPECT(a == b);
383 EXPECT(!(a != b));
384
385 // A is longer
386 a.append(1);
387 EXPECT(!(a == b));
388 EXPECT(a != b);
389
390 b.append(1);
391 EXPECT(a == b);
392 EXPECT(!(a != b));
393
394 // B is longer
395 b.append(42);
396 EXPECT(!(a == b));
397 EXPECT(a != b);
398}
399
400TEST_CASE(should_find_value)
401{
402 Vector<int> v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
403
404 auto const expected = v.begin() + 4;
405
406 EXPECT_EQ(expected, v.find(0));
407}
408
409TEST_CASE(should_find_predicate)
410{
411 Vector<int> v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
412
413 auto const expected = v.begin() + 4;
414
415 EXPECT_EQ(expected, v.find_if([](auto const v) { return v == 0; }));
416}
417
418TEST_CASE(should_find_index)
419{
420 Vector<int> v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
421
422 EXPECT_EQ(4u, v.find_first_index(0).value());
423 EXPECT(!v.find_first_index(42).has_value());
424}
425
426TEST_CASE(should_contain_start)
427{
428 // Tests whether value is found if at the start of the range.
429 Vector<int> v { 1, 2, 3, 4, 5 };
430
431 EXPECT(v.contains_in_range(1, 0, 4));
432}
433
434TEST_CASE(should_contain_end)
435{
436 // Tests whether value is found if at the end of the range.
437 Vector<int> v { 1, 2, 3, 4, 5 };
438
439 EXPECT(v.contains_in_range(5, 0, 4));
440}
441
442TEST_CASE(should_contain_range)
443{
444 // Tests whether value is found within a range.
445 Vector<int> v { 1, 2, 3, 4, 5 };
446
447 EXPECT(v.contains_in_range(3, 0, 4));
448}
449
450TEST_CASE(should_not_contain_not_present)
451{
452 // Tests whether a value that is not present is not found, as expected.
453 Vector<int> v { 1, 2, 3, 4, 5 };
454
455 EXPECT(!v.contains_in_range(6, 0, 4));
456}
457
458TEST_CASE(should_not_contain_present_not_in_range)
459{
460 // Tests whether a value that is present, but not in range, is not found.
461 Vector<int> v { 1, 2, 3, 4, 5 };
462
463 EXPECT(!v.contains_in_range(2, 2, 4));
464}
465
466TEST_CASE(can_store_references)
467{
468 int my_integer = 42;
469 Vector<int&> references;
470 references.append(my_integer);
471 references.prepend(my_integer);
472 EXPECT_EQ(&references.first(), &references.last());
473
474 {
475 Vector<int&> other_references;
476 other_references.extend(references);
477 EXPECT_EQ(&other_references.first(), &my_integer);
478 }
479
480 {
481 Vector<int&> other_references;
482 other_references = references;
483 EXPECT_EQ(&other_references.first(), &my_integer);
484 }
485
486 {
487 auto it = references.find(my_integer);
488 EXPECT(!it.is_end());
489 EXPECT_EQ(*it, my_integer);
490 }
491
492 {
493 int other_integer = 42;
494 auto index = references.find_first_index(other_integer);
495 EXPECT(index.has_value());
496 EXPECT_EQ(index.value_or(99999u), 0u);
497 }
498
499 {
500 auto integer = 42;
501 EXPECT(references.contains_slow(integer));
502 }
503
504 {
505 references.remove(0);
506 references.ensure_capacity(10);
507 EXPECT_EQ(&references.take_first(), &my_integer);
508 }
509}
510
511TEST_CASE(reference_deletion_should_not_affect_object)
512{
513 size_t times_deleted = 0;
514 struct DeleteCounter {
515 explicit DeleteCounter(size_t& deleted)
516 : deleted(deleted)
517 {
518 }
519
520 ~DeleteCounter()
521 {
522 ++deleted;
523 }
524
525 size_t& deleted;
526 };
527
528 {
529 DeleteCounter counter { times_deleted };
530 Vector<DeleteCounter&> references;
531 for (size_t i = 0; i < 16; ++i)
532 references.append(counter);
533 }
534 EXPECT_EQ(times_deleted, 1u);
535}
536
537TEST_CASE(rbegin)
538{
539 Vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
540
541 auto const expected = v.begin() + 4;
542 auto const expected_in_reverse = v.rbegin() + 4;
543 EXPECT_EQ(*expected, *expected_in_reverse);
544}
545
546TEST_CASE(rend)
547{
548 Vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
549
550 auto const expected = v.end() - 5;
551 auto const expected_in_reverse = v.rend() - 5;
552 EXPECT_EQ(*expected, *expected_in_reverse);
553}
554
555TEST_CASE(reverse_iterator_for_loop)
556{
557 Vector<int> v { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
558 int index = 9;
559 for (auto rev = v.rbegin(); rev != v.rend(); ++rev)
560 EXPECT_EQ(*rev, index--);
561}
562
563TEST_CASE(reverse_range_for_loop)
564{
565 Vector<int> v { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
566 int index = 9;
567 for (auto item : AK::ReverseWrapper::in_reverse(v))
568 EXPECT_EQ(item, index--);
569
570 index = 9;
571 for (auto item : v.in_reverse())
572 EXPECT_EQ(item, index--);
573}
574
575static bool is_inline_element(auto& el, auto& vector)
576{
577 uintptr_t vector_ptr = (uintptr_t)&vector;
578 uintptr_t element_ptr = (uintptr_t)⪙
579 return (element_ptr >= vector_ptr && element_ptr < (vector_ptr + sizeof(vector)));
580}
581
582TEST_CASE(uses_inline_capacity_when_appended_to)
583{
584 Vector<int, 10> v;
585 v.unchecked_append(1);
586 v.unchecked_append(123);
587 v.unchecked_append(50);
588 v.unchecked_append(43);
589
590 for (auto& el : v)
591 EXPECT(is_inline_element(el, v));
592}
593
594TEST_CASE(uses_inline_capacity_when_constructed_from_initializer_list)
595{
596 Vector<int, 10> v { 10, 9, 3, 1, 3 };
597
598 for (auto& el : v)
599 EXPECT(is_inline_element(el, v));
600}
601
602TEST_CASE(uses_inline_capacity_when_constructed_from_other_vector)
603{
604 Vector other { 4, 3, 2, 1 };
605 Vector<int, 10> v(other);
606
607 for (auto& el : v)
608 EXPECT(is_inline_element(el, v));
609}
610
611TEST_CASE(uses_inline_capacity_when_constructed_from_span)
612{
613 Array array { "f00", "bar", "baz" };
614 Vector<char const*, 10> v(array.span());
615
616 for (auto& el : v)
617 EXPECT(is_inline_element(el, v));
618}