diff options
Diffstat (limited to 'xpcom/tests/gtest/TestTArray.cpp')
| -rw-r--r-- | xpcom/tests/gtest/TestTArray.cpp | 1042 |
1 files changed, 1042 insertions, 0 deletions
diff --git a/xpcom/tests/gtest/TestTArray.cpp b/xpcom/tests/gtest/TestTArray.cpp new file mode 100644 index 0000000000..54aea92dff --- /dev/null +++ b/xpcom/tests/gtest/TestTArray.cpp @@ -0,0 +1,1042 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "nsTArray.h" +#include "gtest/gtest.h" +#include "mozilla/ArrayUtils.h" +#include "mozilla/RefPtr.h" +#include "nsTHashMap.h" + +using namespace mozilla; + +namespace TestTArray { + +struct Copyable { + Copyable() : mDestructionCounter(nullptr) {} + + ~Copyable() { + if (mDestructionCounter) { + (*mDestructionCounter)++; + } + } + + Copyable(const Copyable&) = default; + Copyable& operator=(const Copyable&) = default; + + uint32_t* mDestructionCounter; +}; + +struct Movable { + Movable() : mDestructionCounter(nullptr) {} + + ~Movable() { + if (mDestructionCounter) { + (*mDestructionCounter)++; + } + } + + Movable(Movable&& aOther) : mDestructionCounter(aOther.mDestructionCounter) { + aOther.mDestructionCounter = nullptr; + } + + uint32_t* mDestructionCounter; +}; + +} // namespace TestTArray + +template <> +struct nsTArray_RelocationStrategy<TestTArray::Copyable> { + using Type = nsTArray_RelocateUsingMoveConstructor<TestTArray::Copyable>; +}; + +template <> +struct nsTArray_RelocationStrategy<TestTArray::Movable> { + using Type = nsTArray_RelocateUsingMoveConstructor<TestTArray::Movable>; +}; + +namespace TestTArray { + +constexpr int dummyArrayData[] = {4, 1, 2, 8}; + +static const nsTArray<int>& DummyArray() { + static nsTArray<int> sArray; + if (sArray.IsEmpty()) { + sArray.AppendElements(dummyArrayData, ArrayLength(dummyArrayData)); + } + return sArray; +} + +// This returns an invalid nsTArray with a huge length in order to test that +// fallible operations actually fail. +#ifdef DEBUG +static const nsTArray<int>& FakeHugeArray() { + static nsTArray<int> sArray; + if (sArray.IsEmpty()) { + sArray.AppendElement(); + ((nsTArrayHeader*)sArray.DebugGetHeader())->mLength = UINT32_MAX; + } + return sArray; +} +#endif + +TEST(TArray, int_AppendElements_PlainArray) +{ + nsTArray<int> array; + + int* ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData)); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + + ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData)); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); +} + +TEST(TArray, int_AppendElements_PlainArray_Fallible) +{ + nsTArray<int> array; + + int* ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData), + fallible); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + + ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData), + fallible); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); +} + +TEST(TArray, int_AppendElements_TArray_Copy) +{ + nsTArray<int> array; + + const nsTArray<int> temp(DummyArray().Clone()); + int* ptr = array.AppendElements(temp); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + ASSERT_FALSE(temp.IsEmpty()); + + ptr = array.AppendElements(temp); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); + ASSERT_FALSE(temp.IsEmpty()); +} + +TEST(TArray, int_AppendElements_TArray_Copy_Fallible) +{ + nsTArray<int> array; + + const nsTArray<int> temp(DummyArray().Clone()); + int* ptr = array.AppendElements(temp, fallible); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + ASSERT_FALSE(temp.IsEmpty()); + + ptr = array.AppendElements(temp, fallible); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); + ASSERT_FALSE(temp.IsEmpty()); +} + +TEST(TArray, int_AppendElements_TArray_Rvalue) +{ + nsTArray<int> array; + + nsTArray<int> temp(DummyArray().Clone()); + int* ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + ASSERT_TRUE(temp.IsEmpty()); + + temp = DummyArray().Clone(); + ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); + ASSERT_TRUE(temp.IsEmpty()); +} + +TEST(TArray, int_AppendElements_TArray_Rvalue_Fallible) +{ + nsTArray<int> array; + + nsTArray<int> temp(DummyArray().Clone()); + int* ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + ASSERT_TRUE(temp.IsEmpty()); + + temp = DummyArray().Clone(); + ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); + ASSERT_TRUE(temp.IsEmpty()); +} + +TEST(TArray, int_AppendElements_FallibleArray_Rvalue) +{ + nsTArray<int> array; + + FallibleTArray<int> temp; + ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible)); + int* ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + ASSERT_TRUE(temp.IsEmpty()); + + ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible)); + ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); + ASSERT_TRUE(temp.IsEmpty()); +} + +TEST(TArray, int_AppendElements_FallibleArray_Rvalue_Fallible) +{ + nsTArray<int> array; + + FallibleTArray<int> temp; + ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible)); + int* ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[0], ptr); + ASSERT_EQ(DummyArray(), array); + ASSERT_TRUE(temp.IsEmpty()); + + ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible)); + ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[DummyArray().Length()], ptr); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); + ASSERT_TRUE(temp.IsEmpty()); +} + +TEST(TArray, AppendElementsSpan) +{ + nsTArray<int> array; + + nsTArray<int> temp(DummyArray().Clone()); + Span<int> span = temp; + array.AppendElements(span); + ASSERT_EQ(DummyArray(), array); + + Span<const int> constSpan = temp; + array.AppendElements(constSpan); + nsTArray<int> expected; + expected.AppendElements(DummyArray()); + expected.AppendElements(DummyArray()); + ASSERT_EQ(expected, array); +} + +TEST(TArray, int_AppendElement_NoElementArg) +{ + nsTArray<int> array; + array.AppendElement(); + + ASSERT_EQ(1u, array.Length()); +} + +TEST(TArray, int_AppendElement_NoElementArg_Fallible) +{ + nsTArray<int> array; + ASSERT_NE(nullptr, array.AppendElement(fallible)); + + ASSERT_EQ(1u, array.Length()); +} + +TEST(TArray, int_AppendElement_NoElementArg_Address) +{ + nsTArray<int> array; + *array.AppendElement() = 42; + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(42, array[0]); +} + +TEST(TArray, int_AppendElement_NoElementArg_Fallible_Address) +{ + nsTArray<int> array; + *array.AppendElement(fallible) = 42; + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(42, array[0]); +} + +TEST(TArray, int_AppendElement_ElementArg) +{ + nsTArray<int> array; + array.AppendElement(42); + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(42, array[0]); +} + +TEST(TArray, int_AppendElement_ElementArg_Fallible) +{ + nsTArray<int> array; + ASSERT_NE(nullptr, array.AppendElement(42, fallible)); + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(42, array[0]); +} + +constexpr size_t dummyMovableArrayLength = 4; +uint32_t dummyMovableArrayDestructorCounter; + +static nsTArray<Movable> DummyMovableArray() { + nsTArray<Movable> res; + res.SetLength(dummyMovableArrayLength); + for (size_t i = 0; i < dummyMovableArrayLength; ++i) { + res[i].mDestructionCounter = &dummyMovableArrayDestructorCounter; + } + return res; +} + +TEST(TArray, Movable_AppendElements_TArray_Rvalue) +{ + dummyMovableArrayDestructorCounter = 0; + { + nsTArray<Movable> array; + + nsTArray<Movable> temp(DummyMovableArray()); + Movable* ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[0], ptr); + ASSERT_TRUE(temp.IsEmpty()); + + temp = DummyMovableArray(); + ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[dummyMovableArrayLength], ptr); + ASSERT_TRUE(temp.IsEmpty()); + } + ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElements_TArray_Rvalue_Fallible) +{ + dummyMovableArrayDestructorCounter = 0; + { + nsTArray<Movable> array; + + nsTArray<Movable> temp(DummyMovableArray()); + Movable* ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[0], ptr); + ASSERT_TRUE(temp.IsEmpty()); + + temp = DummyMovableArray(); + ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[dummyMovableArrayLength], ptr); + ASSERT_TRUE(temp.IsEmpty()); + } + ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElements_FallibleArray_Rvalue) +{ + dummyMovableArrayDestructorCounter = 0; + { + nsTArray<Movable> array; + + FallibleTArray<Movable> temp(DummyMovableArray()); + Movable* ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[0], ptr); + ASSERT_TRUE(temp.IsEmpty()); + + temp = DummyMovableArray(); + ptr = array.AppendElements(std::move(temp)); + ASSERT_EQ(&array[dummyMovableArrayLength], ptr); + ASSERT_TRUE(temp.IsEmpty()); + } + ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElements_FallibleArray_Rvalue_Fallible) +{ + dummyMovableArrayDestructorCounter = 0; + { + nsTArray<Movable> array; + + FallibleTArray<Movable> temp(DummyMovableArray()); + Movable* ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[0], ptr); + ASSERT_TRUE(temp.IsEmpty()); + + temp = DummyMovableArray(); + ptr = array.AppendElements(std::move(temp), fallible); + ASSERT_EQ(&array[dummyMovableArrayLength], ptr); + ASSERT_TRUE(temp.IsEmpty()); + } + ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElement_NoElementArg) +{ + nsTArray<Movable> array; + array.AppendElement(); + + ASSERT_EQ(1u, array.Length()); +} + +TEST(TArray, Movable_AppendElement_NoElementArg_Fallible) +{ + nsTArray<Movable> array; + ASSERT_NE(nullptr, array.AppendElement(fallible)); + + ASSERT_EQ(1u, array.Length()); +} + +TEST(TArray, Movable_AppendElement_NoElementArg_Address) +{ + dummyMovableArrayDestructorCounter = 0; + { + nsTArray<Movable> array; + array.AppendElement()->mDestructionCounter = + &dummyMovableArrayDestructorCounter; + + ASSERT_EQ(1u, array.Length()); + } + ASSERT_EQ(1u, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElement_NoElementArg_Fallible_Address) +{ + dummyMovableArrayDestructorCounter = 0; + { + nsTArray<Movable> array; + array.AppendElement(fallible)->mDestructionCounter = + &dummyMovableArrayDestructorCounter; + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(&dummyMovableArrayDestructorCounter, + array[0].mDestructionCounter); + } + ASSERT_EQ(1u, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElement_ElementArg) +{ + dummyMovableArrayDestructorCounter = 0; + Movable movable; + movable.mDestructionCounter = &dummyMovableArrayDestructorCounter; + { + nsTArray<Movable> array; + array.AppendElement(std::move(movable)); + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(&dummyMovableArrayDestructorCounter, + array[0].mDestructionCounter); + } + ASSERT_EQ(1u, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, Movable_AppendElement_ElementArg_Fallible) +{ + dummyMovableArrayDestructorCounter = 0; + Movable movable; + movable.mDestructionCounter = &dummyMovableArrayDestructorCounter; + { + nsTArray<Movable> array; + ASSERT_NE(nullptr, array.AppendElement(std::move(movable), fallible)); + + ASSERT_EQ(1u, array.Length()); + ASSERT_EQ(&dummyMovableArrayDestructorCounter, + array[0].mDestructionCounter); + } + ASSERT_EQ(1u, dummyMovableArrayDestructorCounter); +} + +TEST(TArray, int_Assign) +{ + nsTArray<int> array; + array.Assign(DummyArray()); + ASSERT_EQ(DummyArray(), array); + + ASSERT_TRUE(array.Assign(DummyArray(), fallible)); + ASSERT_EQ(DummyArray(), array); + +#ifdef DEBUG + ASSERT_FALSE(array.Assign(FakeHugeArray(), fallible)); +#endif + + nsTArray<int> array2; + array2.Assign(std::move(array)); + ASSERT_TRUE(array.IsEmpty()); + ASSERT_EQ(DummyArray(), array2); +} + +TEST(TArray, int_Assign_FromEmpty_ToNonEmpty) +{ + nsTArray<int> array; + array.AppendElement(42); + + const nsTArray<int> empty; + array.Assign(empty); + + ASSERT_TRUE(array.IsEmpty()); +} + +TEST(TArray, int_Assign_FromEmpty_ToNonEmpty_Fallible) +{ + nsTArray<int> array; + array.AppendElement(42); + + const nsTArray<int> empty; + ASSERT_TRUE(array.Assign(empty, fallible)); + + ASSERT_TRUE(array.IsEmpty()); +} + +TEST(TArray, int_AssignmentOperatorSelfAssignment) +{ + CopyableTArray<int> array; + array = DummyArray(); + + array = *&array; + ASSERT_EQ(DummyArray(), array); + +#if defined(__clang__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wself-move" +#endif + array = std::move(array); // self-move + ASSERT_EQ(DummyArray(), array); +#if defined(__clang__) +# pragma clang diagnostic pop +#endif +} + +TEST(TArray, Movable_CopyOverlappingForwards) +{ + const size_t rangeLength = 8; + const size_t initialLength = 2 * rangeLength; + uint32_t destructionCounters[initialLength]; + nsTArray<Movable> array; + array.AppendElements(initialLength); + + for (uint32_t i = 0; i < initialLength; ++i) { + destructionCounters[i] = 0; + } + for (uint32_t i = 0; i < initialLength; ++i) { + array[i].mDestructionCounter = &destructionCounters[i]; + } + + const size_t removedLength = rangeLength / 2; + array.RemoveElementsAt(0, removedLength); + + for (uint32_t i = 0; i < removedLength; ++i) { + ASSERT_EQ(destructionCounters[i], 1u); + } + for (uint32_t i = removedLength; i < initialLength; ++i) { + ASSERT_EQ(destructionCounters[i], 0u); + } +} + +// The code to copy overlapping regions had a bug in that it wouldn't correctly +// destroy all over the source elements being copied. +TEST(TArray, Copyable_CopyOverlappingBackwards) +{ + const size_t rangeLength = 8; + const size_t initialLength = 2 * rangeLength; + uint32_t destructionCounters[initialLength]; + nsTArray<Copyable> array; + array.SetCapacity(3 * rangeLength); + array.AppendElements(initialLength); + // To tickle the bug, we need to copy a source region: + // + // ..XXXXX.. + // + // such that it overlaps the destination region: + // + // ....XXXXX + // + // so we are forced to copy back-to-front to ensure correct behavior. + // The easiest way to do that is to call InsertElementsAt, which will force + // the desired kind of shift. + for (uint32_t i = 0; i < initialLength; ++i) { + destructionCounters[i] = 0; + } + for (uint32_t i = 0; i < initialLength; ++i) { + array[i].mDestructionCounter = &destructionCounters[i]; + } + + array.InsertElementsAt(0, rangeLength); + + for (uint32_t i = 0; i < initialLength; ++i) { + ASSERT_EQ(destructionCounters[i], 1u); + } +} + +namespace { + +class E { + public: + E() : mA(-1), mB(-2) { constructCount++; } + E(int a, int b) : mA(a), mB(b) { constructCount++; } + E(E&& aRhs) : mA(aRhs.mA), mB(aRhs.mB) { + aRhs.mA = 0; + aRhs.mB = 0; + moveCount++; + } + + E& operator=(E&& aRhs) { + mA = aRhs.mA; + aRhs.mA = 0; + mB = aRhs.mB; + aRhs.mB = 0; + moveCount++; + return *this; + } + + int a() const { return mA; } + int b() const { return mB; } + + E(const E&) = delete; + E& operator=(const E&) = delete; + + static size_t constructCount; + static size_t moveCount; + + private: + int mA; + int mB; +}; + +size_t E::constructCount = 0; +size_t E::moveCount = 0; + +} // namespace + +TEST(TArray, Emplace) +{ + nsTArray<E> array; + array.SetCapacity(20); + + ASSERT_EQ(array.Length(), 0u); + + for (int i = 0; i < 10; i++) { + E s(i, i * i); + array.AppendElement(std::move(s)); + } + + ASSERT_EQ(array.Length(), 10u); + ASSERT_EQ(E::constructCount, 10u); + ASSERT_EQ(E::moveCount, 10u); + + for (int i = 10; i < 20; i++) { + array.EmplaceBack(i, i * i); + } + + ASSERT_EQ(array.Length(), 20u); + ASSERT_EQ(E::constructCount, 20u); + ASSERT_EQ(E::moveCount, 10u); + + for (int i = 0; i < 20; i++) { + ASSERT_EQ(array[i].a(), i); + ASSERT_EQ(array[i].b(), i * i); + } + + array.EmplaceBack(); + + ASSERT_EQ(array.Length(), 21u); + ASSERT_EQ(E::constructCount, 21u); + ASSERT_EQ(E::moveCount, 10u); + + ASSERT_EQ(array[20].a(), -1); + ASSERT_EQ(array[20].b(), -2); +} + +TEST(TArray, UnorderedRemoveElements) +{ + // When removing an element from the end of the array, it can be removed in + // place, by destroying it and decrementing the length. + // + // [ 1, 2, 3 ] => [ 1, 2 ] + // ^ + { + nsTArray<int> array{1, 2, 3}; + array.UnorderedRemoveElementAt(2); + + nsTArray<int> goal{1, 2}; + ASSERT_EQ(array, goal); + } + + // When removing any other single element, it is removed by swapping it with + // the last element, and then decrementing the length as before. + // + // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 6, 3, 4, 5 ] + // ^ + { + nsTArray<int> array{1, 2, 3, 4, 5, 6}; + array.UnorderedRemoveElementAt(1); + + nsTArray<int> goal{1, 6, 3, 4, 5}; + ASSERT_EQ(array, goal); + } + + // This method also supports efficiently removing a range of elements. If they + // are at the end, then they can all be removed like in the one element case. + // + // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 2 ] + // ^--------^ + { + nsTArray<int> array{1, 2, 3, 4, 5, 6}; + array.UnorderedRemoveElementsAt(2, 4); + + nsTArray<int> goal{1, 2}; + ASSERT_EQ(array, goal); + } + + // If more elements are removed than exist after the removed section, the + // remaining elements will be shifted down like in a normal removal. + // + // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 2, 7, 8 ] + // ^--------^ + { + nsTArray<int> array{1, 2, 3, 4, 5, 6, 7, 8}; + array.UnorderedRemoveElementsAt(2, 4); + + nsTArray<int> goal{1, 2, 7, 8}; + ASSERT_EQ(array, goal); + } + + // And if fewer elements are removed than exist after the removed section, + // elements will be moved from the end of the array to fill the vacated space. + // + // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 7, 8, 4, 5, 6 ] + // ^--^ + { + nsTArray<int> array{1, 2, 3, 4, 5, 6, 7, 8}; + array.UnorderedRemoveElementsAt(1, 2); + + nsTArray<int> goal{1, 7, 8, 4, 5, 6}; + ASSERT_EQ(array, goal); + } + + // We should do the right thing if we drain the entire array. + { + nsTArray<int> array{1, 2, 3, 4, 5}; + array.UnorderedRemoveElementsAt(0, 5); + + nsTArray<int> goal{}; + ASSERT_EQ(array, goal); + } + + { + nsTArray<int> array{1}; + array.UnorderedRemoveElementAt(0); + + nsTArray<int> goal{}; + ASSERT_EQ(array, goal); + } + + // We should do the right thing if we remove the same number of elements that + // we have remaining. + { + nsTArray<int> array{1, 2, 3, 4, 5, 6}; + array.UnorderedRemoveElementsAt(2, 2); + + nsTArray<int> goal{1, 2, 5, 6}; + ASSERT_EQ(array, goal); + } + + { + nsTArray<int> array{1, 2, 3}; + array.UnorderedRemoveElementAt(1); + + nsTArray<int> goal{1, 3}; + ASSERT_EQ(array, goal); + } + + // We should be able to remove elements from the front without issue. + { + nsTArray<int> array{1, 2, 3, 4, 5, 6}; + array.UnorderedRemoveElementsAt(0, 2); + + nsTArray<int> goal{5, 6, 3, 4}; + ASSERT_EQ(array, goal); + } + + { + nsTArray<int> array{1, 2, 3, 4}; + array.UnorderedRemoveElementAt(0); + + nsTArray<int> goal{4, 2, 3}; + ASSERT_EQ(array, goal); + } +} + +TEST(TArray, RemoveFromEnd) +{ + { + nsTArray<int> array{1, 2, 3, 4}; + ASSERT_EQ(array.PopLastElement(), 4); + array.RemoveLastElement(); + ASSERT_EQ(array.PopLastElement(), 2); + array.RemoveLastElement(); + ASSERT_TRUE(array.IsEmpty()); + } +} + +TEST(TArray, ConvertIteratorToConstIterator) +{ + nsTArray<int> array{1, 2, 3, 4}; + + nsTArray<int>::const_iterator it = array.begin(); + ASSERT_EQ(array.cbegin(), it); +} + +TEST(TArray, RemoveElementAt_ByIterator) +{ + nsTArray<int> array{1, 2, 3, 4}; + const auto it = std::find(array.begin(), array.end(), 3); + const auto itAfter = array.RemoveElementAt(it); + + // Based on the implementation of the iterator, we could compare it and + // itAfter, but we should not rely on such implementation details. + + ASSERT_EQ(2, std::distance(array.cbegin(), itAfter)); + const nsTArray<int> expected{1, 2, 4}; + ASSERT_EQ(expected, array); +} + +TEST(TArray, RemoveElementsRange_ByIterator) +{ + nsTArray<int> array{1, 2, 3, 4}; + const auto it = std::find(array.begin(), array.end(), 3); + const auto itAfter = array.RemoveElementsRange(it, array.end()); + + // Based on the implementation of the iterator, we could compare it and + // itAfter, but we should not rely on such implementation details. + + ASSERT_EQ(2, std::distance(array.cbegin(), itAfter)); + const nsTArray<int> expected{1, 2}; + ASSERT_EQ(expected, array); +} + +TEST(TArray, RemoveLastElements_None) +{ + const nsTArray<int> original{1, 2, 3, 4}; + nsTArray<int> array = original.Clone(); + array.RemoveLastElements(0); + + ASSERT_EQ(original, array); +} + +TEST(TArray, RemoveLastElements_Empty_None) +{ + nsTArray<int> array; + array.RemoveLastElements(0); + + ASSERT_EQ(0u, array.Length()); +} + +TEST(TArray, RemoveLastElements_All) +{ + nsTArray<int> array{1, 2, 3, 4}; + array.RemoveLastElements(4); + + ASSERT_EQ(0u, array.Length()); +} + +TEST(TArray, RemoveLastElements_One) +{ + nsTArray<int> array{1, 2, 3, 4}; + array.RemoveLastElements(1); + + ASSERT_EQ((nsTArray<int>{1, 2, 3}), array); +} + +static_assert(std::is_copy_assignable<decltype(MakeBackInserter( + std::declval<nsTArray<int>&>()))>::value, + "output iteraror must be copy-assignable"); +static_assert(std::is_copy_constructible<decltype(MakeBackInserter( + std::declval<nsTArray<int>&>()))>::value, + "output iterator must be copy-constructible"); + +TEST(TArray, MakeBackInserter) +{ + const std::vector<int> src{1, 2, 3, 4}; + nsTArray<int> dst; + + std::copy(src.begin(), src.end(), MakeBackInserter(dst)); + + const nsTArray<int> expected{1, 2, 3, 4}; + ASSERT_EQ(expected, dst); +} + +TEST(TArray, MakeBackInserter_Move) +{ + uint32_t destructionCounter = 0; + + { + std::vector<Movable> src(1); + src[0].mDestructionCounter = &destructionCounter; + + nsTArray<Movable> dst; + + std::copy(std::make_move_iterator(src.begin()), + std::make_move_iterator(src.end()), MakeBackInserter(dst)); + + ASSERT_EQ(1u, dst.Length()); + ASSERT_EQ(0u, destructionCounter); + } + + ASSERT_EQ(1u, destructionCounter); +} + +TEST(TArray, ConvertToSpan) +{ + nsTArray<int> arr = {1, 2, 3, 4, 5}; + + // from const + { + const auto& constArrRef = arr; + + auto span = Span{constArrRef}; + static_assert(std::is_same_v<decltype(span), Span<const int>>); + } + + // from non-const + { + auto span = Span{arr}; + static_assert(std::is_same_v<decltype(span), Span<int>>); + } +} + +// This should compile: +struct RefCounted; + +class Foo { + ~Foo(); // Intentionally out of line + + nsTArray<RefPtr<RefCounted>> mArray; + + const RefCounted* GetFirst() const { return mArray.SafeElementAt(0); } +}; + +TEST(TArray, StableSort) +{ + const nsTArray<std::pair<int, int>> expected = { + std::pair(1, 9), std::pair(1, 8), std::pair(1, 7), std::pair(2, 0), + std::pair(3, 0)}; + nsTArray<std::pair<int, int>> array = {std::pair(1, 9), std::pair(2, 0), + std::pair(1, 8), std::pair(3, 0), + std::pair(1, 7)}; + + array.StableSort([](std::pair<int, int> left, std::pair<int, int> right) { + return left.first - right.first; + }); + + EXPECT_EQ(expected, array); +} + +TEST(TArray, ToArray) +{ + const auto src = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + nsTArray<int> keys = ToArray(src); + keys.Sort(); + + EXPECT_EQ((nsTArray<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys); +} + +// Test this to make sure this properly uses ADL. +TEST(TArray, ToArray_HashMap) +{ + nsTHashMap<uint32_t, uint64_t> src; + + for (uint32_t i = 0; i < 10; ++i) { + src.InsertOrUpdate(i, i); + } + + nsTArray<uint32_t> keys = ToArray(src.Keys()); + keys.Sort(); + + EXPECT_EQ((nsTArray<uint32_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys); +} + +TEST(TArray, ToTArray) +{ + const auto src = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + auto keys = ToTArray<AutoTArray<uint64_t, 10>>(src); + keys.Sort(); + + static_assert(std::is_same_v<decltype(keys), AutoTArray<uint64_t, 10>>); + + EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys); +} + +TEST(TArray, RemoveElementsBy) +{ + // Removing elements returns the correct number of removed elements. + { + nsTArray<int> array{8, 1, 1, 3, 3, 5, 2, 3}; + auto removed = array.RemoveElementsBy([](int i) { return i == 3; }); + EXPECT_EQ(removed, 3u); + + nsTArray<int> goal{8, 1, 1, 5, 2}; + EXPECT_EQ(array, goal); + } + + // The check is called in order. + { + int index = 0; + nsTArray<int> array{0, 1, 2, 3, 4, 5}; + auto removed = array.RemoveElementsBy([&](int i) { + EXPECT_EQ(index, i); + index++; + return i == 3; + }); + EXPECT_EQ(removed, 1u); + + nsTArray<int> goal{0, 1, 2, 4, 5}; + EXPECT_EQ(array, goal); + } + + // Removing nothing works + { + nsTArray<int> array{0, 1, 2, 3, 4}; + auto removed = array.RemoveElementsBy([](int) { return false; }); + EXPECT_EQ(removed, 0u); + + nsTArray<int> goal{0, 1, 2, 3, 4}; + EXPECT_EQ(array, goal); + } + + // Removing everything works + { + nsTArray<int> array{0, 1, 2, 3, 4}; + auto removed = array.RemoveElementsBy([](int) { return true; }); + EXPECT_EQ(removed, 5u); + + nsTArray<int> goal{}; + EXPECT_EQ(array, goal); + } +} + +} // namespace TestTArray |