/* * Copyright (c) 2018-2020, Andreas Kling * * SPDX-License-Identifier: BSD-2-Clause */ #include #include #include #include #include #include static bool is_inline_element(auto& el, auto& vector) { uintptr_t vector_ptr = (uintptr_t)&vector; uintptr_t element_ptr = (uintptr_t)⪙ return (element_ptr >= vector_ptr && element_ptr < (vector_ptr + sizeof(vector))); } #define DECLARE_TESTS_FOR_VEC(Vector) \ TEST_CASE(Vector##_construct) \ { \ EXPECT(Vector().is_empty()); \ EXPECT(Vector().size() == 0); \ } \ \ TEST_CASE(Vector##_ints) \ { \ Vector ints; \ ints.append(1); \ ints.append(2); \ ints.append(3); \ EXPECT_EQ(ints.size(), 3u); \ EXPECT_EQ(ints.take_last(), 3); \ EXPECT_EQ(ints.size(), 2u); \ EXPECT_EQ(ints.take_last(), 2); \ EXPECT_EQ(ints.size(), 1u); \ EXPECT_EQ(ints.take_last(), 1); \ EXPECT_EQ(ints.size(), 0u); \ \ ints.clear(); \ EXPECT_EQ(ints.size(), 0u); \ } \ \ TEST_CASE(Vector##_strings) \ { \ Vector strings; \ strings.append("ABC"); \ strings.append("DEF"); \ \ int loop_counter = 0; \ for (ByteString const& string : strings) { \ EXPECT(!string.is_empty()); \ ++loop_counter; \ } \ \ loop_counter = 0; \ for (auto& string : (const_cast const&>(strings))) { \ EXPECT(!string.is_empty()); \ ++loop_counter; \ } \ EXPECT_EQ(loop_counter, 2); \ } \ \ TEST_CASE(Vector##_conforms_to_iterator_protocol) \ { \ static_assert(std::random_access_iterator::Iterator>); \ static_assert(std::random_access_iterator::ConstIterator>); \ static_assert(std::random_access_iterator::Iterator>); \ static_assert(std::random_access_iterator::ConstIterator>); \ \ static_assert(std::random_access_iterator::Iterator>); \ static_assert(std::random_access_iterator::ConstIterator>); \ static_assert(std::random_access_iterator::Iterator>); \ static_assert(std::random_access_iterator::ConstIterator>); \ } \ \ TEST_CASE(Vector##_strings_insert_ordered) \ { \ Vector strings; \ strings.append("abc"); \ strings.append("def"); \ strings.append("ghi"); \ \ strings.insert_before_matching("f-g"sv, [](auto& entry) { \ return "f-g"sv < entry; \ }); \ \ EXPECT_EQ(strings[0], "abc"); \ EXPECT_EQ(strings[1], "def"); \ EXPECT_EQ(strings[2], "f-g"); \ EXPECT_EQ(strings[3], "ghi"); \ } \ \ TEST_CASE(Vector##_prepend_vector) \ { \ Vector ints; \ ints.append(1); \ ints.append(2); \ ints.append(3); \ \ Vector more_ints; \ more_ints.append(4); \ more_ints.append(5); \ more_ints.append(6); \ \ ints.prepend(move(more_ints)); \ \ EXPECT_EQ(ints.size(), 6u); \ EXPECT_EQ(more_ints.size(), 0u); \ \ EXPECT_EQ(ints[0], 4); \ EXPECT_EQ(ints[1], 5); \ EXPECT_EQ(ints[2], 6); \ EXPECT_EQ(ints[3], 1); \ EXPECT_EQ(ints[4], 2); \ EXPECT_EQ(ints[5], 3); \ \ ints.prepend(move(more_ints)); \ EXPECT_EQ(ints.size(), 6u); \ EXPECT_EQ(more_ints.size(), 0u); \ \ more_ints.prepend(move(ints)); \ EXPECT_EQ(more_ints.size(), 6u); \ EXPECT_EQ(ints.size(), 0u); \ } \ \ TEST_CASE(Vector##_prepend_vector_object) \ { \ struct SubObject { \ SubObject(int v) \ : value(v) \ { \ } \ int value { 0 }; \ }; \ struct Object { \ Object(NonnullOwnPtr&& a_subobject) \ : subobject(move(a_subobject)) \ { \ } \ OwnPtr subobject; \ }; \ \ Vector objects; \ objects.empend(make(1)); \ objects.empend(make(2)); \ objects.empend(make(3)); \ \ EXPECT_EQ(objects.size(), 3u); \ \ Vector more_objects; \ more_objects.empend(make(4)); \ more_objects.empend(make(5)); \ more_objects.empend(make(6)); \ EXPECT_EQ(more_objects.size(), 3u); \ \ objects.prepend(move(more_objects)); \ EXPECT_EQ(more_objects.size(), 0u); \ EXPECT_EQ(objects.size(), 6u); \ \ EXPECT_EQ(objects[0].subobject->value, 4); \ EXPECT_EQ(objects[1].subobject->value, 5); \ EXPECT_EQ(objects[2].subobject->value, 6); \ EXPECT_EQ(objects[3].subobject->value, 1); \ EXPECT_EQ(objects[4].subobject->value, 2); \ EXPECT_EQ(objects[5].subobject->value, 3); \ } \ \ TEST_CASE(Vector##_vector_compare) \ { \ Vector ints; \ Vector same_ints; \ \ for (int i = 0; i < 1000; ++i) { \ ints.append(i); \ same_ints.append(i); \ } \ \ EXPECT_EQ(ints.size(), 1000u); \ EXPECT_EQ(ints, same_ints); \ \ Vector strings; \ Vector same_strings; \ \ for (int i = 0; i < 1000; ++i) { \ strings.append(ByteString::number(i)); \ same_strings.append(ByteString::number(i)); \ } \ \ EXPECT_EQ(strings.size(), 1000u); \ EXPECT_EQ(strings, same_strings); \ } \ \ TEST_CASE(Vector##_grow_past_inline_capacity) \ { \ auto make_vector = [] { \ Vector strings; \ for (int i = 0; i < 32; ++i) { \ strings.append(ByteString::number(i)); \ } \ return strings; \ }; \ \ auto strings = make_vector(); \ \ EXPECT_EQ(strings.size(), 32u); \ EXPECT_EQ(strings[31], "31"); \ \ strings.clear(); \ EXPECT_EQ(strings.size(), 0u); \ EXPECT_EQ(strings.capacity(), 16u); \ \ strings = make_vector(); \ \ strings.clear_with_capacity(); \ EXPECT_EQ(strings.size(), 0u); \ EXPECT(strings.capacity() >= 32u); \ } \ \ BENCHMARK_CASE(Vector##_append_trivial) \ { \ /* This should be super fast thanks to Vector using memmove. */ \ Vector ints; \ for (int i = 0; i < 1000000; ++i) { \ ints.append(i); \ } \ for (int i = 0; i < 100; ++i) { \ Vector tmp; \ tmp.extend(ints); \ EXPECT_EQ(tmp.size(), 1000000u); \ } \ } \ \ BENCHMARK_CASE(Vector##_remove_trivial) \ { \ /* This should be super fast thanks to Vector using memmove. */ \ Vector ints; \ for (int i = 0; i < 10000; ++i) { \ ints.append(i); \ } \ while (!ints.is_empty()) { \ ints.remove(0); \ } \ EXPECT_EQ(ints.size(), 0u); \ } \ \ BENCHMARK_CASE(Vector##_remove_all_matching_trivial) \ { \ Vector ints; \ for (int i = 0; i < 10000; ++i) { \ ints.append(i); \ } \ ints.remove_all_matching([](int value) { return value % 2 == 0; }); \ EXPECT_EQ(ints.size(), 5000u); \ } \ \ TEST_CASE(Vector##_vector_remove) \ { \ Vector ints; \ ints.append(1); \ ints.append(2); \ ints.append(3); \ ints.append(4); \ ints.append(5); \ \ ints.remove(1); \ EXPECT_EQ(ints.size(), 4u); \ EXPECT_EQ(ints[0], 1); \ EXPECT_EQ(ints[1], 3); \ EXPECT_EQ(ints[2], 4); \ EXPECT_EQ(ints[3], 5); \ \ ints.remove(0); \ EXPECT_EQ(ints.size(), 3u); \ EXPECT_EQ(ints[0], 3); \ EXPECT_EQ(ints[1], 4); \ EXPECT_EQ(ints[2], 5); \ \ ints.take_last(); \ EXPECT_EQ(ints.size(), 2u); \ EXPECT_EQ(ints[0], 3); \ EXPECT_EQ(ints[1], 4); \ \ ints.take_first(); \ EXPECT_EQ(ints.size(), 1u); \ EXPECT_EQ(ints[0], 4); \ } \ \ TEST_CASE(Vector##_remove_all_matching) \ { \ Vector ints; \ \ ints.append(1); \ ints.append(2); \ ints.append(3); \ ints.append(4); \ \ EXPECT_EQ(ints.size(), 4u); \ \ EXPECT_EQ(ints.remove_all_matching([&](int value) { return value > 2; }), true); \ EXPECT_EQ(ints.remove_all_matching([&](int) { return false; }), false); \ \ EXPECT_EQ(ints.size(), 2u); \ \ EXPECT_EQ(ints.remove_all_matching([&](int) { return true; }), true); \ \ EXPECT(ints.is_empty()); \ \ EXPECT_EQ(ints.remove_all_matching([&](int) { return true; }), false); \ } \ \ TEST_CASE(Vector##_nonnullownptrvector) \ { \ struct Object { \ ByteString string; \ }; \ Vector> objects; \ \ objects.append(make()); \ EXPECT_EQ(objects.size(), 1u); \ \ OwnPtr o = make(); \ objects.append(o.release_nonnull()); \ EXPECT(o == nullptr); \ EXPECT_EQ(objects.size(), 2u); \ } \ \ TEST_CASE(Vector##_insert_trivial) \ { \ Vector ints; \ ints.append(0); \ ints.append(10); \ ints.append(20); \ ints.append(30); \ ints.append(40); \ ints.insert(2, 15); \ EXPECT_EQ(ints.size(), 6u); \ EXPECT_EQ(ints[0], 0); \ EXPECT_EQ(ints[1], 10); \ EXPECT_EQ(ints[2], 15); \ EXPECT_EQ(ints[3], 20); \ EXPECT_EQ(ints[4], 30); \ EXPECT_EQ(ints[5], 40); \ } \ \ TEST_CASE(Vector##_resize_initializes) \ { \ struct A { \ A() { initialized = true; } \ bool initialized { false }; \ }; \ \ Vector ints; \ ints.resize(32); \ \ for (size_t idx = 0; idx < 32; ++idx) \ EXPECT(ints[idx].initialized); \ } \ \ TEST_CASE(Vector##_should_compare_vectors_of_same_type) \ { \ Vector a {}; \ Vector b {}; \ \ EXPECT(a == b); \ EXPECT(!(a != b)); \ \ a.append(1); \ EXPECT(!(a == b)); \ EXPECT(a != b); \ \ b.append(1); \ EXPECT(a == b); \ EXPECT(!(a != b)); \ \ a.append(42); \ b.append(17); \ EXPECT(!(a == b)); \ EXPECT(a != b); \ } \ \ TEST_CASE(Vector##_should_compare_vectors_of_different_inline_capacity) \ { \ Vector a {}; \ Vector b {}; \ \ EXPECT(a == b); \ EXPECT(!(a != b)); \ \ a.append(1); \ EXPECT(!(a == b)); \ EXPECT(a != b); \ \ b.append(1); \ EXPECT(a == b); \ EXPECT(!(a != b)); \ \ a.append(42); \ b.append(17); \ EXPECT(!(a == b)); \ EXPECT(a != b); \ } \ \ TEST_CASE(Vector##_should_compare_vectors_of_different_sizes) \ { \ Vector a {}; \ Vector b {}; \ \ EXPECT(a == b); \ EXPECT(!(a != b)); \ \ /* A is longer */ \ a.append(1); \ EXPECT(!(a == b)); \ EXPECT(a != b); \ \ b.append(1); \ EXPECT(a == b); \ EXPECT(!(a != b)); \ \ /* B is longer */ \ b.append(42); \ EXPECT(!(a == b)); \ EXPECT(a != b); \ } \ \ TEST_CASE(Vector##_should_find_value) \ { \ Vector v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 }; \ \ auto const expected = v.begin() + 4; \ \ EXPECT_EQ(expected, v.find(0)); \ } \ \ TEST_CASE(Vector##_should_find_predicate) \ { \ Vector v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 }; \ \ auto const expected = v.begin() + 4; \ \ EXPECT_EQ(expected, v.find_if([](auto const v) { return v == 0; })); \ } \ \ TEST_CASE(Vector##_should_find_index) \ { \ Vector v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 }; \ \ EXPECT_EQ(4u, v.find_first_index(0).value()); \ EXPECT(!v.find_first_index(42).has_value()); \ } \ \ TEST_CASE(Vector##_should_find_predicate_index) \ { \ Vector v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 }; \ \ EXPECT_EQ(4u, v.find_first_index_if([](auto const v) { return v == 0; }).value()); \ EXPECT(!v.find_first_index_if([](auto const v) { return v == 123; }).has_value()); \ } \ \ TEST_CASE(Vector##_should_find_using_a_hashcompatible_value) \ { \ /* Tests whether a hash-compatible value can be used to compare (Strings cannot be implicitly constructed from a StringView.) */ \ Vector v { "hello!"_string }; \ EXPECT(v.contains_slow("hello!"sv)); \ } \ \ TEST_CASE(Vector##_should_contain_start) \ { \ /* Tests whether value is found if at the start of the range. */ \ Vector v { 1, 2, 3, 4, 5 }; \ \ EXPECT(v.contains_in_range(1, 0, 4)); \ } \ \ TEST_CASE(Vector##_should_contain_end) \ { \ /* Tests whether value is found if at the end of the range. */ \ Vector v { 1, 2, 3, 4, 5 }; \ \ EXPECT(v.contains_in_range(5, 0, 4)); \ } \ \ TEST_CASE(Vector##_should_contain_range) \ { \ /* Tests whether value is found within a range. */ \ Vector v { 1, 2, 3, 4, 5 }; \ \ EXPECT(v.contains_in_range(3, 0, 4)); \ } \ \ TEST_CASE(Vector##_should_not_contain_not_present) \ { \ /* Tests whether a value that is not present is not found, as expected.*/ \ Vector v { 1, 2, 3, 4, 5 }; \ \ EXPECT(!v.contains_in_range(6, 0, 4)); \ } \ \ TEST_CASE(Vector##_should_not_contain_present_not_in_range) \ { \ /* Tests whether a value that is present, but not in range, is not found.*/ \ Vector v { 1, 2, 3, 4, 5 }; \ \ EXPECT(!v.contains_in_range(2, 2, 4)); \ } \ \ TEST_CASE(Vector##_can_store_references) \ { \ int my_integer = 42; \ Vector references; \ references.append(my_integer); \ references.prepend(my_integer); \ EXPECT_EQ(&references.first(), &references.last()); \ \ { \ Vector other_references; \ other_references.extend(references); \ EXPECT_EQ(&other_references.first(), &my_integer); \ } \ \ { \ Vector other_references; \ other_references = references; \ EXPECT_EQ(&other_references.first(), &my_integer); \ } \ \ { \ auto it = references.find(my_integer); \ EXPECT(!it.is_end()); \ EXPECT_EQ(*it, my_integer); \ } \ \ { \ int other_integer = 42; \ auto index = references.find_first_index(other_integer); \ EXPECT(index.has_value()); \ EXPECT_EQ(index.value_or(99999u), 0u); \ } \ \ { \ auto integer = 42; \ EXPECT(references.contains_slow(integer)); \ } \ \ { \ references.remove(0); \ references.ensure_capacity(10); \ EXPECT_EQ(&references.take_first(), &my_integer); \ } \ } \ \ TEST_CASE(Vector##_reference_deletion_should_not_affect_object) \ { \ size_t times_deleted = 0; \ struct DeleteCounter { \ explicit DeleteCounter(size_t& deleted) \ : deleted(deleted) \ { \ } \ \ ~DeleteCounter() \ { \ ++deleted; \ } \ \ size_t& deleted; \ }; \ \ { \ DeleteCounter counter { times_deleted }; \ Vector references; \ for (size_t i = 0; i < 16; ++i) \ references.append(counter); \ } \ EXPECT_EQ(times_deleted, 1u); \ } \ \ TEST_CASE(Vector##_rbegin) \ { \ Vector v { 1, 2, 3, 4, 5, 6, 7, 8, 0 }; \ \ auto const expected = v.begin() + 4; \ auto const expected_in_reverse = v.rbegin() + 4; \ EXPECT_EQ(*expected, *expected_in_reverse); \ } \ \ TEST_CASE(Vector##_rend) \ { \ Vector v { 1, 2, 3, 4, 5, 6, 7, 8, 0 }; \ \ auto const expected = v.end() - 5; \ auto const expected_in_reverse = v.rend() - 5; \ EXPECT_EQ(*expected, *expected_in_reverse); \ } \ \ TEST_CASE(Vector##_reverse_iterator_for_loop) \ { \ Vector v { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; \ int index = 9; \ for (auto rev = v.rbegin(); rev != v.rend(); ++rev) \ EXPECT_EQ(*rev, index--); \ } \ \ TEST_CASE(Vector##_reverse_range_for_loop) \ { \ Vector v { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; \ int index = 9; \ for (auto item : AK::ReverseWrapper::in_reverse(v)) \ EXPECT_EQ(item, index--); \ \ index = 9; \ for (auto item : v.in_reverse()) \ EXPECT_EQ(item, index--); \ } \ \ TEST_CASE(Vector##_uses_inline_capacity_when_appended_to) \ { \ Vector v; \ v.unchecked_append(1); \ v.unchecked_append(123); \ v.unchecked_append(50); \ v.unchecked_append(43); \ \ for (auto& el : v) \ EXPECT(is_inline_element(el, v)); \ } \ \ TEST_CASE(Vector##_uses_inline_capacity_when_constructed_from_initializer_list) \ { \ Vector v { 10, 9, 3, 1, 3 }; \ \ for (auto& el : v) \ EXPECT(is_inline_element(el, v)); \ } \ \ TEST_CASE(Vector##_uses_inline_capacity_when_constructed_from_other_vector) \ { \ Vector other { 4, 3, 2, 1 }; \ Vector v(other); \ \ for (auto& el : v) \ EXPECT(is_inline_element(el, v)); \ } \ \ TEST_CASE(Vector##_uses_inline_capacity_when_constructed_from_span) \ { \ Array array { "f00", "bar", "baz" }; \ Vector v(array.span()); \ \ for (auto& el : v) \ EXPECT(is_inline_element(el, v)); \ } \ TEST_CASE(Vector##_remove_all) \ { \ { \ Vector v0 { 1, 2, 3, 2, 4, 2, 5 }; \ Array indices { 1, 4, 6 }; \ v0.remove_all(indices); \ EXPECT_EQ(v0.size(), 4u); \ EXPECT_EQ(v0[0], 1); \ EXPECT_EQ(v0[1], 3); \ EXPECT_EQ(v0[2], 2); \ EXPECT_EQ(v0[3], 2); \ } \ { \ Vector v1 { 1, 2, 3, 4, 5 }; \ Array indices { 0, 1, 2, 3, 4 }; \ v1.remove_all(indices); \ EXPECT_EQ(v1.size(), 0u); \ } \ { \ Vector v2 { 1, 2, 3, 4, 5 }; \ Array indices; \ v2.remove_all(indices); \ EXPECT_EQ(v2.size(), 5u); \ EXPECT_EQ(v2[0], 1); \ EXPECT_EQ(v2[1], 2); \ EXPECT_EQ(v2[2], 3); \ EXPECT_EQ(v2[3], 4); \ EXPECT_EQ(v2[4], 5); \ } \ { \ Vector v3; \ Array indices; \ v3.remove_all(indices); \ EXPECT_EQ(v3.size(), 0u); \ } \ /* One more test with a nonstandard iterator deref function */ \ { \ Vector v4 { 1, 2, 3, 2, 4, 2, 5 }; \ struct IndexWrapper { \ size_t index; \ size_t const& operator*() const { return index; } \ }; \ Array indices { IndexWrapper { 1 }, IndexWrapper { 4 }, IndexWrapper { 6 } }; \ v4.remove_all(indices, [](auto const& it) -> size_t { return **it; }); \ EXPECT_EQ(v4.size(), 4u); \ EXPECT_EQ(v4[0], 1); \ EXPECT_EQ(v4[1], 3); \ EXPECT_EQ(v4[2], 2); \ EXPECT_EQ(v4[3], 2); \ } \ } DECLARE_TESTS_FOR_VEC(Vector) template using VectorWithFastLastAccess = Vector; DECLARE_TESTS_FOR_VEC(VectorWithFastLastAccess) TEST_CASE(VectorWithFastLastAccess_unsafe) { VectorWithFastLastAccess v; v.append(1); v.append(2); EXPECT_EQ(v.unsafe_last(), 2); EXPECT_EQ(v.unsafe_take_last(), 2); EXPECT_EQ(v.unsafe_last(), 1); }