123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146 |
- // Copyright 2019 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "base/containers/intrusive_heap.h"
- #include "base/callback_helpers.h"
- #include "base/check_op.h"
- #include "base/memory/ptr_util.h"
- #include "base/notreached.h"
- #include "base/rand_util.h"
- #include "base/test/bind.h"
- #include "testing/gmock/include/gmock/gmock.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace base {
- namespace {
- using IntrusiveHeapInt = IntrusiveHeap<WithHeapHandle<int>>;
- // Validates whether or not the given heap satisfies the heap invariant.
- template <class H>
- void ExpectHeap(const H& heap) {
- const auto& less = heap.value_comp();
- const auto& handle_access = heap.heap_handle_access();
- for (size_t i = 0; i < heap.size(); ++i) {
- size_t left = intrusive_heap::LeftIndex(i);
- size_t right = left + 1;
- if (left < heap.size())
- EXPECT_FALSE(less(heap[i], heap[left]));
- if (right < heap.size())
- EXPECT_FALSE(less(heap[i], heap[right]));
- intrusive_heap::CheckInvalidOrEqualTo(handle_access.GetHeapHandle(&heap[i]),
- i);
- }
- }
- // A small set of canonical elements, and the a function for validating the
- // heap that should be created by those elements. This is used in various
- // constructor/insertion tests.
- #define CANONICAL_ELEMENTS 3, 1, 2, 4, 5, 6, 7, 0
- void ExpectCanonical(const IntrusiveHeapInt& heap) {
- ExpectHeap(heap);
- // Manual implementation of a max-heap inserting the elements defined by
- // CANONICAL_ELEMENTS:
- // 3
- // 3 1
- // 3 1 2
- // 3 1 2 4 -> 3 4 2 1 -> 4 3 2 1
- // 4 3 2 1 5 -> 4 5 2 1 3 -> 5 4 2 1 3
- // 5 4 2 1 3 6 -> 5 4 6 1 3 2 -> 6 4 5 1 3 2
- // 6 4 5 1 3 2 7 -> 6 4 7 1 3 2 5 -> 7 4 6 1 3 2 5
- // 7 4 6 1 3 2 5 0
- std::vector<int> expected{7, 4, 6, 1, 3, 2, 5, 0};
- std::vector<int> actual;
- for (const auto& element : heap)
- actual.push_back(element.value());
- ASSERT_THAT(actual, testing::ContainerEq(expected));
- }
- // Initializes the given heap to be the "canonical" heap from the point of view
- // of these tests.
- void MakeCanonical(IntrusiveHeapInt* heap) {
- static constexpr int kInts[] = {CANONICAL_ELEMENTS};
- heap->clear();
- heap->insert(kInts, kInts + std::size(kInts));
- ExpectCanonical(*heap);
- }
- // A handful of helper functions and classes related to building an exhaustive
- // stress test for IntrusiveHeap, with all combinations of default-constructible
- // supports-move-operations and supports-copy-operations value types.
- // IntrusiveHeap supports 3 types of operations: those that cause the heap to
- // get smaller (deletions), those that keep the heap the same size (updates,
- // replaces, etc), and those that cause the heap to get bigger (insertions).
- enum OperationTypes : int {
- kGrowing,
- kShrinking,
- kSameSize,
- kOperationTypesCount
- };
- // The operations that cause a heap to get bigger.
- enum GrowingOperations : int { kInsert, kEmplace, kGrowingOperationsCount };
- // The operations that cause a heap to get smaller. Some of these are only
- // supported by move-only value types.
- enum ShrinkingOperations : int {
- kTake,
- kTakeTop,
- kErase,
- kPop,
- kShrinkingOperationsCount
- };
- // The operations that keep a heap the same size.
- enum SameSizeOperations : int {
- kReplace,
- kReplaceTop,
- kUpdate,
- kSameSizeOperationsCount
- };
- // Randomly selects an operation for the GrowingOperations enum, applies it to
- // the given heap, and validates that the operation completed as expected.
- template <typename T>
- void DoGrowingOperation(IntrusiveHeap<T>* heap) {
- GrowingOperations op = static_cast<GrowingOperations>(
- base::RandInt(0, kGrowingOperationsCount - 1));
- int value = base::RandInt(0, 1000);
- size_t old_size = heap->size();
- typename IntrusiveHeap<T>::const_iterator it;
- switch (op) {
- case kInsert: {
- it = heap->insert(T(value));
- break;
- }
- case kEmplace: {
- it = heap->emplace(value);
- break;
- }
- case kGrowingOperationsCount:
- NOTREACHED();
- }
- EXPECT_EQ(old_size + 1, heap->size());
- EXPECT_EQ(value, it->value());
- EXPECT_EQ(it->GetHeapHandle().index(), heap->ToIndex(it));
- }
- // Helper struct for determining with the given value type T is movable or not.
- // Used to determine whether or not the "take" operations can be used.
- template <typename T>
- struct NotMovable {
- static constexpr bool value = !std::is_nothrow_move_constructible<T>::value &&
- std::is_copy_constructible<T>::value;
- };
- // Invokes "take" if the type is movable, otherwise invokes erase.
- template <typename T, bool kNotMovable = NotMovable<T>::value>
- struct Take;
- template <typename T>
- struct Take<T, true> {
- static void Do(IntrusiveHeap<T>* heap, size_t index) { heap->erase(index); }
- };
- template <typename T>
- struct Take<T, false> {
- static void Do(IntrusiveHeap<T>* heap, size_t index) {
- int value = heap->at(index).value();
- T t = heap->take(index);
- EXPECT_EQ(value, t.value());
- EXPECT_FALSE(t.GetHeapHandle().IsValid());
- }
- };
- // Invokes "take_top" if the type is movable, otherwise invokes pop.
- template <typename T, bool kNotMovable = NotMovable<T>::value>
- struct TakeTop;
- template <typename T>
- struct TakeTop<T, true> {
- static void Do(IntrusiveHeap<T>* heap) { heap->pop(); }
- };
- template <typename T>
- struct TakeTop<T, false> {
- static void Do(IntrusiveHeap<T>* heap) {
- int value = heap->at(0).value();
- T t = heap->take_top();
- EXPECT_EQ(value, t.value());
- EXPECT_FALSE(t.GetHeapHandle().IsValid());
- }
- };
- // Randomly selects a shrinking operations, applies it to the given |heap| and
- // validates that the operation completed as expected and resulted in a valid
- // heap. The "take" operations will only be invoked for a value type T that
- // supports move operations, otherwise they will be mapped to erase/pop.
- template <typename T>
- void DoShrinkingOperation(IntrusiveHeap<T>* heap) {
- ShrinkingOperations op = static_cast<ShrinkingOperations>(
- base::RandInt(0, kShrinkingOperationsCount - 1));
- size_t old_size = heap->size();
- size_t index = static_cast<size_t>(base::RandInt(0, old_size - 1));
- switch (op) {
- case kTake: {
- Take<T>::Do(heap, index);
- break;
- }
- case kTakeTop: {
- TakeTop<T>::Do(heap);
- break;
- }
- case kErase: {
- heap->erase(index);
- break;
- }
- case kPop: {
- heap->pop();
- break;
- }
- case kShrinkingOperationsCount:
- NOTREACHED();
- }
- EXPECT_EQ(old_size - 1, heap->size());
- }
- // Randomly selects a same size operation, applies it to the given |heap| and
- // validates that the operation completed as expected and resulted in a valid
- // heap.
- template <typename T>
- void DoSameSizeOperation(IntrusiveHeap<T>* heap) {
- SameSizeOperations op = static_cast<SameSizeOperations>(
- base::RandInt(0, kSameSizeOperationsCount - 1));
- size_t old_size = heap->size();
- size_t index = static_cast<size_t>(base::RandInt(0, old_size - 1));
- if (op == kReplaceTop)
- index = 0;
- int new_value = base::RandInt(0, 1000);
- typename IntrusiveHeap<T>::const_iterator it;
- switch (op) {
- case kReplace: {
- it = heap->Replace(index, T(new_value));
- break;
- }
- case kReplaceTop: {
- it = heap->ReplaceTop(T(new_value));
- break;
- }
- case kUpdate: {
- it = heap->Modify(
- index, [&new_value](T& element) { element.set_value(new_value); });
- break;
- }
- case kSameSizeOperationsCount:
- NOTREACHED();
- }
- EXPECT_EQ(old_size, heap->size());
- EXPECT_EQ(new_value, it->value());
- EXPECT_EQ(it->GetHeapHandle().index(), heap->ToIndex(it));
- }
- // Randomly selects an operation, applies it to the given |heap| and validates
- // that the operation completed as expected and resulted in a valid heap.
- template <typename T>
- void DoRandomHeapOperation(IntrusiveHeap<T>* heap) {
- static constexpr int kMinHeapSize = 10u;
- static constexpr int kMaxHeapSize = 100u;
- OperationTypes operation_type =
- static_cast<OperationTypes>(base::RandInt(0, kOperationTypesCount - 1));
- // Keep the heap size bounded by forcing growing and shrinking operations when
- // it exceeds the bounds.
- if (heap->size() < kMinHeapSize) {
- operation_type = kGrowing;
- } else if (heap->size() > kMaxHeapSize) {
- operation_type = kShrinking;
- }
- switch (operation_type) {
- case kGrowing:
- DoGrowingOperation(heap);
- break;
- case kShrinking:
- DoShrinkingOperation(heap);
- break;
- case kSameSize:
- DoSameSizeOperation(heap);
- break;
- case kOperationTypesCount:
- NOTREACHED();
- }
- }
- // A stress test that is only applicable to value types T that support move
- // operations.
- template <typename T>
- void MoveStressTest() {
- IntrusiveHeap<T> heap({2, 4, 6, 8});
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(heap.empty());
- ExpectHeap(heap);
- IntrusiveHeap<T> heap2(std::move(heap));
- EXPECT_EQ(4u, heap2.size());
- EXPECT_FALSE(heap2.empty());
- ExpectHeap(heap2);
- EXPECT_EQ(0u, heap.size());
- EXPECT_TRUE(heap.empty());
- ExpectHeap(heap);
- heap = std::move(heap2);
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(heap.empty());
- ExpectHeap(heap);
- EXPECT_EQ(0u, heap2.size());
- EXPECT_TRUE(heap2.empty());
- ExpectHeap(heap2);
- }
- // A stress that that is only applicable to value types T that support copy
- // operations.
- template <typename T>
- void CopyStressTest() {
- IntrusiveHeap<T> heap({2, 4, 6, 8});
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(heap.empty());
- ExpectHeap(heap);
- IntrusiveHeap<T> heap2(heap);
- EXPECT_EQ(4u, heap2.size());
- EXPECT_FALSE(heap2.empty());
- ExpectHeap(heap2);
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(heap.empty());
- ExpectHeap(heap);
- IntrusiveHeap<T> heap3({1, 3, 5});
- heap3.clear();
- heap3 = heap;
- EXPECT_EQ(4u, heap3.size());
- EXPECT_FALSE(heap3.empty());
- ExpectHeap(heap);
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(heap.empty());
- ExpectHeap(heap);
- EXPECT_TRUE(heap == heap2);
- EXPECT_FALSE(heap != heap2);
- }
- // A stress test that is applicable to all value types, whether or not they
- // support copy and/or move operations.
- template <typename T>
- void GeneralStressTest() {
- std::vector<int> vector{2, 4, 6, 8};
- IntrusiveHeap<T> heap(vector.begin(), vector.end());
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(heap.empty());
- ExpectHeap(heap);
- heap.clear();
- EXPECT_EQ(0u, heap.size());
- EXPECT_TRUE(heap.empty());
- ExpectHeap(heap);
- // Create an element and get a handle to it.
- auto it = heap.insert(T(34));
- EXPECT_EQ(1u, heap.size());
- HeapHandle* handle = it->handle();
- EXPECT_EQ(0u, handle->index());
- ExpectHeap(heap);
- // Add some other elements.
- heap.insert(T(12));
- heap.emplace(14);
- EXPECT_EQ(3u, heap.size());
- ExpectHeap(heap);
- // The handle should have tracked the element it is associated with.
- EXPECT_EQ(34, heap[*handle].value());
- // Replace with a value that shouldn't need moving in the heap.
- size_t index = handle->index();
- handle = heap.Replace(*handle, T(40))->handle();
- EXPECT_EQ(3u, heap.size());
- ExpectHeap(heap);
- EXPECT_EQ(index, handle->index());
- // Replace with a value that should cause the entry to move.
- handle = heap.Replace(handle->index(), T(1))->handle();
- EXPECT_EQ(3u, heap.size());
- ExpectHeap(heap);
- EXPECT_NE(index, handle->index());
- // Replace the top element.
- heap.ReplaceTop(T(65));
- EXPECT_EQ(3u, heap.size());
- ExpectHeap(heap);
- // Insert several more elements.
- std::vector<int> elements({13, 17, 19, 23, 29, 31, 37, 41});
- heap.insert(elements.begin(), elements.end());
- EXPECT_EQ(11u, heap.size());
- ExpectHeap(heap);
- // Invasively change an element that is already inside the heap, and then
- // repair the heap.
- T* element = const_cast<T*>(&heap[7]);
- element->set_value(97);
- heap.Update(7u);
- ExpectHeap(heap);
- // Safely modify an element that is already inside the heap.
- heap.Modify(7u, [](T& element) { element.set_value(128); });
- ExpectHeap(heap);
- // Do some more updates that are no-ops, just to explore all the flavours of
- // ToIndex.
- handle = heap[5].handle();
- heap.Update(*handle);
- heap.Update(heap.begin() + 6);
- heap.Update(heap.rbegin() + 8);
- ExpectHeap(heap);
- handle = heap[5].handle();
- EXPECT_TRUE(handle);
- EXPECT_EQ(5u, handle->index());
- EXPECT_EQ(5u, heap.ToIndex(*handle));
- EXPECT_EQ(5u, heap.ToIndex(heap.begin() + 5));
- EXPECT_EQ(5u, heap.ToIndex(heap.cbegin() + 5));
- EXPECT_EQ(5u, heap.ToIndex(heap.rbegin() + 5));
- EXPECT_EQ(5u, heap.ToIndex(heap.crbegin() + 5));
- EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.end()));
- EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.cend()));
- EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.rend()));
- EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.crend()));
- EXPECT_EQ(&heap[0], &heap.at(0));
- EXPECT_EQ(&heap[0], &heap.front());
- EXPECT_EQ(&heap[0], &heap.top());
- EXPECT_EQ(&heap[heap.size() - 1], &heap.back());
- EXPECT_EQ(&heap[0], heap.data());
- // Do a bunch of random operations on a heap as a stress test.
- for (size_t i = 0; i < 1000; ++i) {
- DoRandomHeapOperation(&heap);
- ExpectHeap(heap);
- }
- }
- // A basic value type that wraps an integer. This is default constructible, and
- // supports both move and copy operations.
- class Value : public InternalHeapHandleStorage {
- public:
- explicit Value(int value) : value_(value) {}
- Value() : value_(-1) {}
- Value(Value&& other) noexcept
- : InternalHeapHandleStorage(std::move(other)),
- value_(std::exchange(other.value_, -1)) {}
- Value(const Value& other) : value_(other.value_) {
- HeapHandle h = other.GetHeapHandle();
- if (h.IsValid())
- SetHeapHandle(h);
- }
- ~Value() override {}
- Value& operator=(Value&& other) noexcept {
- InternalHeapHandleStorage::operator=(std::move(other));
- value_ = std::exchange(other.value_, -1);
- return *this;
- }
- Value& operator=(const Value& other) {
- value_ = other.value_;
- return *this;
- }
- int value() const { return value_; }
- void set_value(int value) { value_ = value; }
- bool operator==(const Value& rhs) const { return value_ == rhs.value_; }
- bool operator!=(const Value& rhs) const { return value_ != rhs.value_; }
- bool operator<=(const Value& rhs) const { return value_ <= rhs.value_; }
- bool operator>=(const Value& rhs) const { return value_ >= rhs.value_; }
- bool operator<(const Value& rhs) const { return value_ < rhs.value_; }
- bool operator>(const Value& rhs) const { return value_ > rhs.value_; }
- private:
- int value_;
- };
- // Macro for creating versions of Value that selectively enable/disable
- // default-constructors, move-operations and copy-operations.
- #define DEFINE_VALUE_TYPE(name, default_construct, move, copy) \
- class name : public Value { \
- public: \
- explicit name(int value) : Value(value) {} \
- name() = default_construct; \
- name(name&&) noexcept = move; \
- name(const name&) = copy; \
- name& operator=(name&&) noexcept = move; \
- name& operator=(const name&) = copy; \
- };
- DEFINE_VALUE_TYPE(Value_DMC, default, default, default)
- DEFINE_VALUE_TYPE(Value_DmC, default, delete, default)
- DEFINE_VALUE_TYPE(Value_DMc, default, default, delete)
- DEFINE_VALUE_TYPE(Value_dMC, delete, default, default)
- DEFINE_VALUE_TYPE(Value_dmC, delete, delete, default)
- DEFINE_VALUE_TYPE(Value_dMc, delete, default, delete)
- // Used to validate that the generated value types work as expected wrt
- // default-constructors, move-operations and copy-operations.
- template <typename ValueType, bool D, bool M, bool C>
- void ValidateValueType() {
- static_assert(std::is_default_constructible<ValueType>::value == D, "oops");
- static_assert(std::is_move_constructible<ValueType>::value == M, "oops");
- static_assert(std::is_move_assignable<ValueType>::value == M, "oops");
- static_assert(std::is_copy_constructible<ValueType>::value == C, "oops");
- static_assert(std::is_copy_assignable<ValueType>::value == C, "oops");
- }
- // A small test element that provides its own HeapHandle storage and implements
- // the contract expected of the DefaultHeapHandleAccessor.
- struct TestElement {
- int key;
- HeapHandle* handle;
- // Make this a min-heap by return > instead of <.
- bool operator<(const TestElement& other) const { return key > other.key; }
- void SetHeapHandle(HeapHandle h) {
- if (handle)
- *handle = h;
- }
- void ClearHeapHandle() {
- if (handle)
- handle->reset();
- }
- HeapHandle GetHeapHandle() const {
- if (handle)
- return *handle;
- return HeapHandle::Invalid();
- }
- };
- } // namespace
- ////////////////////////////////////////////////////////////////////////////////
- // TEST SUITE 1
- //
- // Explicit tests of a simple heap using WithHeapHandle<>.
- TEST(IntrusiveHeapTest, Constructors) {
- {
- // Default constructor.
- IntrusiveHeapInt heap;
- EXPECT_TRUE(heap.empty());
- }
- {
- // Constructor with iterators.
- std::vector<int> ints{CANONICAL_ELEMENTS};
- IntrusiveHeapInt heap(ints.begin(), ints.end());
- ExpectCanonical(heap);
- // Move constructor.
- IntrusiveHeapInt heap2(std::move(heap));
- EXPECT_TRUE(heap.empty());
- ExpectCanonical(heap2);
- }
- {
- // Constructor with initializer list.
- IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
- ExpectCanonical(heap);
- }
- }
- TEST(IntrusiveHeapTest, Assignment) {
- IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
- // Move assignment.
- IntrusiveHeapInt heap2;
- heap2 = std::move(heap);
- EXPECT_TRUE(heap.empty());
- ExpectCanonical(heap2);
- }
- TEST(IntrusiveHeapTest, Swap) {
- IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
- IntrusiveHeapInt heap2;
- swap(heap, heap2);
- EXPECT_TRUE(heap.empty());
- ExpectCanonical(heap2);
- heap.swap(heap2);
- EXPECT_TRUE(heap2.empty());
- ExpectCanonical(heap);
- }
- TEST(IntrusiveHeapTest, ElementAccess) {
- IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
- EXPECT_EQ(heap.front(), heap[0]);
- EXPECT_EQ(heap.back(), heap[7]);
- EXPECT_EQ(heap.top(), heap[0]);
- for (size_t i = 0; i < heap.size(); ++i) {
- EXPECT_EQ(heap[i], heap.at(i));
- EXPECT_EQ(heap[i], heap.data()[i]);
- }
- }
- TEST(IntrusiveHeapTest, SizeManagement) {
- IntrusiveHeapInt heap;
- EXPECT_TRUE(heap.empty());
- EXPECT_LE(heap.size(), heap.capacity());
- MakeCanonical(&heap);
- EXPECT_FALSE(heap.empty());
- EXPECT_LE(heap.size(), heap.capacity());
- }
- TEST(IntrusiveHeapTest, Iterators) {
- IntrusiveHeapInt heap;
- MakeCanonical(&heap);
- size_t i = 0;
- for (auto it = heap.begin(); it != heap.end(); ++it) {
- EXPECT_EQ(i, heap.ToIndex(it));
- EXPECT_EQ(&(*it), heap.data() + i);
- ++i;
- }
- i = heap.size() - 1;
- for (auto rit = heap.rbegin(); rit != heap.rend(); ++rit) {
- EXPECT_EQ(i, heap.ToIndex(rit));
- EXPECT_EQ(&(*rit), heap.data() + i);
- --i;
- }
- }
- ////////////////////////////////////////////////////////////////////////////////
- // TEST SUITE 2
- //
- // Exhaustive stress tests with different value types, exploring all
- // possibilities of default-constrible, movable and copyable value types.
- TEST(IntrusiveHeapTest, MoveOnlyNoDefaultConstructorTest) {
- using ValueType = Value_dMc;
- ValidateValueType<ValueType, false, true, false>();
- MoveStressTest<ValueType>();
- GeneralStressTest<ValueType>();
- }
- TEST(IntrusiveHeapTest, CopyOnlyNoDefaultConstructorTest) {
- using ValueType = Value_dmC;
- ValidateValueType<ValueType, false, false, true>();
- // We cannot perform CopyStressTest nor GeneralStressTest here, because
- // Value_dmC has deleted move constructor and assignment operator. See
- // crbug.com/1022576.
- }
- TEST(IntrusiveHeapTest, CopyAndMoveNoDefaultConstructorTest) {
- using ValueType = Value_dMC;
- ValidateValueType<ValueType, false, true, true>();
- CopyStressTest<ValueType>();
- MoveStressTest<ValueType>();
- GeneralStressTest<ValueType>();
- }
- TEST(IntrusiveHeapTest, MoveOnlyWithDefaultConstructorTest) {
- using ValueType = Value_DMc;
- ValidateValueType<ValueType, true, true, false>();
- MoveStressTest<ValueType>();
- GeneralStressTest<ValueType>();
- }
- TEST(IntrusiveHeapTest, CopyOnlyWithDefaultConstructorTest) {
- using ValueType = Value_DmC;
- ValidateValueType<ValueType, true, false, true>();
- // We cannot perform CopyStressTest nor GeneralStressTest here, because
- // Value_DmC has deleted move constructor and assignment operator. See
- // crbug.com/1022576.
- }
- TEST(IntrusiveHeapTest, CopyAndMoveWithDefaultConstructorTest) {
- using ValueType = Value_DMC;
- ValidateValueType<ValueType, true, true, true>();
- CopyStressTest<ValueType>();
- MoveStressTest<ValueType>();
- GeneralStressTest<ValueType>();
- }
- ////////////////////////////////////////////////////////////////////////////////
- // TEST SUITE 3
- //
- // Tests individual functions on a custom type that provides heap handle storage
- // externally through raw pointers.
- TEST(IntrusiveHeapTest, Basic) {
- IntrusiveHeap<TestElement> heap;
- EXPECT_TRUE(heap.empty());
- EXPECT_EQ(0u, heap.size());
- }
- TEST(IntrusiveHeapTest, Clear) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index1;
- heap.insert({11, &index1});
- EXPECT_EQ(1u, heap.size());
- EXPECT_TRUE(index1.IsValid());
- heap.clear();
- EXPECT_EQ(0u, heap.size());
- EXPECT_FALSE(index1.IsValid());
- }
- TEST(IntrusiveHeapTest, Destructor) {
- HeapHandle index1;
- {
- IntrusiveHeap<TestElement> heap;
- heap.insert({11, &index1});
- EXPECT_EQ(1u, heap.size());
- EXPECT_TRUE(index1.IsValid());
- }
- EXPECT_FALSE(index1.IsValid());
- }
- TEST(IntrusiveHeapTest, Min) {
- IntrusiveHeap<TestElement> heap;
- heap.insert({9, nullptr});
- heap.insert({10, nullptr});
- heap.insert({8, nullptr});
- heap.insert({2, nullptr});
- heap.insert({7, nullptr});
- heap.insert({15, nullptr});
- heap.insert({22, nullptr});
- heap.insert({3, nullptr});
- EXPECT_FALSE(heap.empty());
- EXPECT_EQ(8u, heap.size());
- EXPECT_EQ(2, heap.top().key);
- }
- TEST(IntrusiveHeapTest, MinDuplicates) {
- IntrusiveHeap<TestElement> heap;
- heap.insert({2, nullptr});
- heap.insert({2, nullptr});
- heap.insert({3, nullptr});
- EXPECT_FALSE(heap.empty());
- EXPECT_EQ(3u, heap.size());
- EXPECT_EQ(2, heap.top().key);
- }
- TEST(IntrusiveHeapTest, InsertAscending) {
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 50; i++)
- heap.insert({i, nullptr});
- EXPECT_EQ(0, heap.top().key);
- EXPECT_EQ(50u, heap.size());
- }
- TEST(IntrusiveHeapTest, InsertDescending) {
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 50; i++)
- heap.insert({50 - i, nullptr});
- EXPECT_EQ(1, heap.top().key);
- EXPECT_EQ(50u, heap.size());
- }
- TEST(IntrusiveHeapTest, HeapIndex) {
- HeapHandle index5;
- HeapHandle index4;
- HeapHandle index3;
- HeapHandle index2;
- HeapHandle index1;
- IntrusiveHeap<TestElement> heap;
- EXPECT_FALSE(index1.IsValid());
- EXPECT_FALSE(index2.IsValid());
- EXPECT_FALSE(index3.IsValid());
- EXPECT_FALSE(index4.IsValid());
- EXPECT_FALSE(index5.IsValid());
- heap.insert({15, &index5});
- heap.insert({14, &index4});
- heap.insert({13, &index3});
- heap.insert({12, &index2});
- heap.insert({11, &index1});
- EXPECT_TRUE(index1.IsValid());
- EXPECT_TRUE(index2.IsValid());
- EXPECT_TRUE(index3.IsValid());
- EXPECT_TRUE(index4.IsValid());
- EXPECT_TRUE(index5.IsValid());
- EXPECT_FALSE(heap.empty());
- }
- TEST(IntrusiveHeapTest, HeapIndexDuplicates) {
- HeapHandle index2;
- HeapHandle index1;
- IntrusiveHeap<TestElement> heap;
- EXPECT_FALSE(index1.IsValid());
- EXPECT_FALSE(index2.IsValid());
- heap.insert({2, &index2});
- heap.insert({2, &index1});
- EXPECT_TRUE(index1.IsValid());
- EXPECT_TRUE(index2.IsValid());
- EXPECT_EQ(2U, heap.size());
- }
- TEST(IntrusiveHeapTest, Pop) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index1;
- HeapHandle index2;
- heap.insert({11, &index1});
- heap.insert({12, &index2});
- EXPECT_EQ(2u, heap.size());
- EXPECT_TRUE(index1.IsValid());
- EXPECT_TRUE(index2.IsValid());
- heap.pop();
- EXPECT_EQ(1u, heap.size());
- EXPECT_FALSE(index1.IsValid());
- EXPECT_TRUE(index2.IsValid());
- heap.pop();
- EXPECT_EQ(0u, heap.size());
- EXPECT_FALSE(index1.IsValid());
- EXPECT_FALSE(index2.IsValid());
- }
- TEST(IntrusiveHeapTest, PopMany) {
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 500; i++)
- heap.insert({i, nullptr});
- EXPECT_FALSE(heap.empty());
- EXPECT_EQ(500u, heap.size());
- for (int i = 0; i < 500; i++) {
- EXPECT_EQ(i, heap.top().key);
- heap.pop();
- }
- EXPECT_TRUE(heap.empty());
- }
- TEST(IntrusiveHeapTest, Erase) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index12;
- heap.insert({15, nullptr});
- heap.insert({14, nullptr});
- heap.insert({13, nullptr});
- heap.insert({12, &index12});
- heap.insert({11, nullptr});
- EXPECT_EQ(5u, heap.size());
- EXPECT_TRUE(index12.IsValid());
- heap.erase(index12);
- EXPECT_EQ(4u, heap.size());
- EXPECT_FALSE(index12.IsValid());
- EXPECT_EQ(11, heap.top().key);
- heap.pop();
- EXPECT_EQ(13, heap.top().key);
- heap.pop();
- EXPECT_EQ(14, heap.top().key);
- heap.pop();
- EXPECT_EQ(15, heap.top().key);
- heap.pop();
- EXPECT_TRUE(heap.empty());
- }
- TEST(IntrusiveHeapTest, ReplaceTop) {
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 500; i++)
- heap.insert({500 - i, nullptr});
- EXPECT_EQ(1, heap.top().key);
- for (int i = 0; i < 500; i++)
- heap.ReplaceTop({1000 + i, nullptr});
- EXPECT_EQ(1000, heap.top().key);
- }
- TEST(IntrusiveHeapTest, ReplaceTopWithNonLeafNode) {
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 50; i++) {
- heap.insert({i, nullptr});
- heap.insert({200 + i, nullptr});
- }
- EXPECT_EQ(0, heap.top().key);
- for (int i = 0; i < 50; i++)
- heap.ReplaceTop({100 + i, nullptr});
- for (int i = 0; i < 50; i++) {
- EXPECT_EQ((100 + i), heap.top().key);
- heap.pop();
- }
- for (int i = 0; i < 50; i++) {
- EXPECT_EQ((200 + i), heap.top().key);
- heap.pop();
- }
- EXPECT_TRUE(heap.empty());
- }
- TEST(IntrusiveHeapTest, ReplaceTopCheckAllFinalPositions) {
- HeapHandle index[100];
- HeapHandle top_index;
- for (int j = -1; j <= 201; j += 2) {
- IntrusiveHeap<TestElement> heap;
- for (size_t i = 0; i < 100; i++) {
- heap.insert({static_cast<int>(i) * 2, &index[i]});
- }
- heap.ReplaceTop({j, &top_index});
- int prev = -2;
- while (!heap.empty()) {
- DCHECK_GT(heap.top().key, prev);
- DCHECK(heap.top().key == j || (heap.top().key % 2) == 0);
- DCHECK_NE(heap.top().key, 0);
- prev = heap.top().key;
- heap.pop();
- }
- }
- }
- TEST(IntrusiveHeapTest, ReplaceUp) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index[10];
- for (size_t i = 0; i < 10; i++) {
- heap.insert({static_cast<int>(i) * 2, &index[i]});
- }
- heap.Replace(index[5], {17, &index[5]});
- std::vector<int> results;
- while (!heap.empty()) {
- results.push_back(heap.top().key);
- heap.pop();
- }
- EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 12, 14, 16, 17, 18));
- }
- TEST(IntrusiveHeapTest, ReplaceUpButDoesntMove) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index[10];
- for (size_t i = 0; i < 10; i++) {
- heap.insert({static_cast<int>(i) * 2, &index[i]});
- }
- heap.Replace(index[5], {11, &index[5]});
- std::vector<int> results;
- while (!heap.empty()) {
- results.push_back(heap.top().key);
- heap.pop();
- }
- EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 11, 12, 14, 16, 18));
- }
- TEST(IntrusiveHeapTest, ReplaceDown) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index[10];
- for (size_t i = 0; i < 10; i++) {
- heap.insert({static_cast<int>(i) * 2, &index[i]});
- }
- heap.Replace(index[5], {1, &index[5]});
- std::vector<int> results;
- while (!heap.empty()) {
- results.push_back(heap.top().key);
- heap.pop();
- }
- EXPECT_THAT(results, testing::ElementsAre(0, 1, 2, 4, 6, 8, 12, 14, 16, 18));
- }
- TEST(IntrusiveHeapTest, ReplaceDownButDoesntMove) {
- IntrusiveHeap<TestElement> heap;
- HeapHandle index[10];
- for (size_t i = 0; i < 10; i++) {
- heap.insert({static_cast<int>(i) * 2, &index[i]});
- }
- heap.Replace(index[5], {9, &index[5]});
- std::vector<int> results;
- while (!heap.empty()) {
- results.push_back(heap.top().key);
- heap.pop();
- }
- EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 9, 12, 14, 16, 18));
- }
- TEST(IntrusiveHeapTest, ReplaceCheckAllFinalPositions) {
- HeapHandle index[100];
- for (int j = -1; j <= 201; j += 2) {
- IntrusiveHeap<TestElement> heap;
- for (size_t i = 0; i < 100; i++) {
- heap.insert({static_cast<int>(i) * 2, &index[i]});
- }
- heap.Replace(index[40], {j, &index[40]});
- int prev = -2;
- while (!heap.empty()) {
- DCHECK_GT(heap.top().key, prev);
- DCHECK(heap.top().key == j || (heap.top().key % 2) == 0);
- DCHECK_NE(heap.top().key, 80);
- prev = heap.top().key;
- heap.pop();
- }
- }
- }
- TEST(IntrusiveHeapTest, At) {
- HeapHandle index[10];
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 10; i++)
- heap.insert({static_cast<int>(i ^ (i + 1)), &index[i]});
- for (int i = 0; i < 10; i++) {
- EXPECT_EQ(heap.at(index[i]).key, i ^ (i + 1));
- EXPECT_EQ(heap.at(index[i]).handle, &index[i]);
- }
- }
- bool IsEven(int i) {
- return i % 2 == 0;
- }
- TEST(IntrusiveHeapTest, EraseIf) {
- HeapHandle index[10];
- IntrusiveHeap<TestElement> heap;
- for (int i = 0; i < 10; i++)
- heap.insert({i, &index[i]});
- ASSERT_EQ(heap.size(), 10u);
- // Remove all even elements.
- heap.EraseIf([](const TestElement& element) { return IsEven(element.key); });
- ASSERT_EQ(heap.size(), 5u);
- // Handles were correctly updated.
- for (int i = 0; i < 10; i++)
- EXPECT_EQ(IsEven(i), !index[i].IsValid());
- // Now iterate over all elements of the heap and check their handles.
- for (size_t i = 0; i < heap.size(); i++) {
- auto it = heap.begin();
- std::advance(it, i);
- // Retrieve the value of the element at this position.
- int value = it->key;
- // Its handle should have the correct index.
- EXPECT_EQ(index[value].index(), i);
- }
- std::vector<int> results;
- while (!heap.empty()) {
- results.push_back(heap.top().key);
- heap.pop();
- }
- EXPECT_THAT(results, testing::ElementsAre(1, 3, 5, 7, 9));
- }
- // A comparator class whose sole purpose is to allow the insertion of a
- // ScopedClosureRunner inside the heap. The ordering does not matter.
- class Comparator {
- public:
- bool operator()(const WithHeapHandle<ScopedClosureRunner>& lhs,
- const WithHeapHandle<ScopedClosureRunner>& rhs) {
- // Treat all closures as equal.
- return true;
- }
- };
- // Tests that inserting another element from the destructor of an object removed
- // during EraseIf() doesn't crash.
- TEST(IntrusiveHeapTest, EraseIf_Reentrancy) {
- IntrusiveHeap<WithHeapHandle<ScopedClosureRunner>, Comparator> heap;
- // The task that will post a new element inside the heap upon destruction of
- // the first.
- OnceClosure insert_task = BindLambdaForTesting([&]() {
- // Insert a null callback so it can be differentiated.
- heap.insert(OnceClosure());
- });
- heap.insert(ScopedClosureRunner(std::move(insert_task)));
- // The heap contains the non-null closure.
- EXPECT_EQ(heap.size(), 1u);
- EXPECT_TRUE(heap.top().value());
- // Erase the only element using EraseIf().
- heap.EraseIf([](const auto& element) { return true; });
- // Now the heap contains the null closure.
- EXPECT_EQ(heap.size(), 1u);
- EXPECT_FALSE(heap.top().value());
- }
- } // namespace base
|