| // Copyright 2016 The Fuchsia 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 <math.h> |
| #include <fbl/intrusive_wavl_tree.h> |
| #include <fbl/tests/intrusive_containers/intrusive_wavl_tree_checker.h> |
| #include <fbl/tests/intrusive_containers/ordered_associative_container_test_environment.h> |
| #include <fbl/tests/intrusive_containers/test_thunks.h> |
| #include <fbl/intrusive_pointer_traits.h> |
| #include <unittest/unittest.h> |
| |
| namespace fbl { |
| namespace tests { |
| namespace intrusive_containers { |
| |
| using ::fbl::internal::valid_sentinel_ptr; |
| |
| template <typename ContainerStateType> |
| struct OtherTreeTraits { |
| using KeyType = typename ContainerStateType::KeyType; |
| using PtrType = typename ContainerStateType::PtrType; |
| using PtrTraits = ::fbl::internal::ContainerPtrTraits<PtrType>; |
| |
| // Node Traits |
| static WAVLTreeNodeState<PtrType>& node_state(typename PtrTraits::RefType obj) { |
| return obj.other_container_state_.node_state_; |
| } |
| |
| // Key Traits |
| static KeyType GetKey(typename PtrTraits::ConstRefType obj) { |
| return obj.other_container_state_.key_; |
| } |
| static bool LessThan(const KeyType& key1, const KeyType& key2) { return key1 < key2; } |
| static bool EqualTo (const KeyType& key1, const KeyType& key2) { return key1 == key2; } |
| |
| // Set key is a trait which is only used by the tests, not by the containers |
| // themselves. |
| static void SetKey(typename PtrTraits::RefType obj, KeyType key) { |
| obj.other_container_state_.key_ = key; |
| } |
| }; |
| |
| template <typename _KeyType, typename _PtrType> |
| class OtherTreeNodeState { |
| public: |
| using KeyType = _KeyType; |
| using PtrType = _PtrType; |
| |
| private: |
| friend struct OtherTreeTraits<OtherTreeNodeState<KeyType, PtrType>>; |
| WAVLTreeNodeState<PtrType> node_state_; |
| KeyType key_ = 0; |
| }; |
| |
| template <typename PtrType> |
| class WAVLTraits { |
| public: |
| using KeyType = size_t; |
| using TestObjBaseType = KeyedTestObjBase<KeyType>; |
| |
| using ContainerType = WAVLTree<KeyType, PtrType>; |
| using ContainableBaseClass = WAVLTreeContainable<PtrType>; |
| using ContainerStateType = WAVLTreeNodeState<PtrType>; |
| |
| using OtherContainerStateType = OtherTreeNodeState<KeyType, PtrType>; |
| using OtherContainerTraits = OtherTreeTraits<OtherContainerStateType>; |
| using OtherContainerType = WAVLTree<KeyType, |
| PtrType, |
| OtherContainerTraits, |
| OtherContainerTraits>; |
| |
| struct Tag1 {}; |
| struct Tag2 {}; |
| struct Tag3 {}; |
| |
| using TaggedContainableBaseClasses = |
| fbl::ContainableBaseClasses<WAVLTreeContainable<PtrType, Tag1>, |
| WAVLTreeContainable<PtrType, Tag2>, |
| WAVLTreeContainable<PtrType, Tag3>>; |
| |
| using TaggedType1 = TaggedWAVLTree<KeyType, PtrType, Tag1>; |
| using TaggedType2 = TaggedWAVLTree<KeyType, PtrType, Tag2>; |
| using TaggedType3 = TaggedWAVLTree<KeyType, PtrType, Tag3>; |
| |
| }; |
| |
| // Just a sanity check so we know our metaprogramming nonsense is |
| // doing what we expect: |
| static_assert(std::is_same_v<typename WAVLTraits<int*>::TaggedContainableBaseClasses::TagTypes, |
| std::tuple<typename WAVLTraits<int*>::Tag1, |
| typename WAVLTraits<int*>::Tag2, |
| typename WAVLTraits<int*>::Tag3>>); |
| |
| // Generate all of the standard tests. |
| DEFINE_TEST_OBJECTS(WAVL); |
| using UMTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, Unmanaged); |
| using UPTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, UniquePtr); |
| using SUPDDTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, StdUniquePtrDefaultDeleter); |
| using SUPCDTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, StdUniquePtrCustomDeleter); |
| using RPTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, RefPtr); |
| |
| // WAVLBalanceTestObserver |
| // |
| // An implementation of a WAVLTree Observer which collects stats on the number |
| // of balance operations (inserts, erases, rank promotions, rank demotions and |
| // rotatations) which have taken place. It is used by the BalanceTest to verify |
| // that... |
| // |
| // 1) The computation costs of rebalancing after insert and erase are amortized |
| // constant and obey their specific worst-case constant bounds. |
| // 2) The maximum depth bounds for trees with just insert operations, and with |
| // both insert and erase operations, are obeyed. |
| // 3) Sufficient code coverage has been achieved during testing (eg. all of the |
| // rebalancing edge cases have been run over the length of the test). |
| class WAVLBalanceTestObserver { |
| public: |
| struct OpCounts { |
| OpCounts() { reset(); } |
| |
| void reset() { |
| insert_ops_ = 0; |
| insert_promotes_ = 0; |
| insert_rotations_ = 0; |
| insert_double_rotations_ = 0; |
| erase_ops_ = 0; |
| erase_demotes_ = 0; |
| erase_rotations_ = 0; |
| erase_double_rotations_ = 0; |
| } |
| |
| void accumulate(OpCounts& target) { |
| target.insert_ops_ += insert_ops_; |
| target.insert_promotes_ += insert_promotes_; |
| target.insert_rotations_ += insert_rotations_; |
| target.insert_double_rotations_ += insert_double_rotations_; |
| target.erase_ops_ += erase_ops_; |
| target.erase_demotes_ += erase_demotes_; |
| target.erase_rotations_ += erase_rotations_; |
| target.erase_double_rotations_ += erase_double_rotations_; |
| } |
| |
| size_t insert_ops_; |
| size_t insert_promotes_; |
| size_t insert_rotations_; |
| size_t insert_double_rotations_; |
| |
| size_t erase_ops_; |
| size_t erase_demotes_; |
| size_t erase_rotations_; |
| size_t erase_double_rotations_; |
| }; |
| |
| static void ResetObserverOpCounts() { op_counts_.reset(); } |
| static void AccumulateObserverOpCounts(OpCounts& target) { op_counts_.accumulate(target); } |
| |
| static void RecordInsert() { ++op_counts_.insert_ops_; } |
| static void RecordInsertPromote() { ++op_counts_.insert_promotes_; } |
| static void RecordInsertRotation() { ++op_counts_.insert_rotations_; } |
| static void RecordInsertDoubleRotation() { ++op_counts_.insert_double_rotations_; } |
| static void RecordErase() { ++op_counts_.erase_ops_; } |
| static void RecordEraseDemote() { ++op_counts_.erase_demotes_; } |
| static void RecordEraseRotation() { ++op_counts_.erase_rotations_; } |
| static void RecordEraseDoubleRotation() { ++op_counts_.erase_double_rotations_; } |
| |
| template <typename TreeType> |
| static bool VerifyRankRule(const TreeType& tree, typename TreeType::RawPtrType node) { |
| BEGIN_TEST; |
| using NodeTraits = typename TreeType::NodeTraits; |
| |
| // Check the rank rule. The rules for a WAVL tree are... |
| // 1) All rank differences are either 1 or 2 |
| // 2) All leaf nodes have rank 0 (by implication, all rank |
| // differences are non-negative) |
| const auto& ns = NodeTraits::node_state(*node); |
| ASSERT_LE(0, ns.rank_, "All ranks must be non-negative."); |
| |
| if (!valid_sentinel_ptr(ns.left_) && !valid_sentinel_ptr(ns.right_)) { |
| ASSERT_EQ(0, ns.rank_, "Leaf nodes must have rank 0!"); |
| } else { |
| if (valid_sentinel_ptr(ns.left_)) { |
| auto& left_ns = NodeTraits::node_state(*ns.left_); |
| auto delta = ns.rank_ - left_ns.rank_; |
| ASSERT_LE(1, delta, "Left hand rank difference not on range [1, 2]"); |
| ASSERT_GE(2, delta, "Left hand rank difference not on range [1, 2]"); |
| } |
| |
| if (valid_sentinel_ptr(ns.right_)) { |
| auto& right_ns = NodeTraits::node_state(*ns.right_); |
| auto delta = ns.rank_ - right_ns.rank_; |
| ASSERT_LE(1, delta, "Right hand rank difference not on range [1, 2]"); |
| ASSERT_GE(2, delta, "Right hand rank difference not on range [1, 2]"); |
| } |
| } |
| |
| END_TEST; |
| } |
| |
| template <typename TreeType> |
| static bool VerifyBalance(const TreeType& tree, uint64_t depth) { |
| BEGIN_TEST; |
| |
| // Compute the maximum expected depth. |
| uint64_t max_depth = 0; |
| if (tree.size()) { |
| // If we have performed erase operations, the max depth should be |
| // rounddown(2 * log_2(N)) + 1. |
| // |
| // If we have not performed any erases, then the max depth should be |
| // rounddown(log_phi(N)) + 1. We know that... |
| // |
| // phi = (1 + sqrt(5)) / 2 |
| // log_phi(N) = log_2(N) / log_2(phi) |
| // |
| // Start by computing log_2(N), then scale by either 2.0, or |
| // (1/log_2(phi)). |
| constexpr double one_over_log2_phi = |
| 1.4404200904125563642566021371749229729175567626953125; |
| double log2N = log2(static_cast<double>(tree.size())); |
| double scale = op_counts_.erase_ops_ ? 2.0 : one_over_log2_phi; |
| |
| max_depth = static_cast<uint64_t>(log2N * scale) + 1; |
| } |
| |
| size_t total_insert_rotations = op_counts_.insert_rotations_ |
| + op_counts_.insert_double_rotations_; |
| EXPECT_LE(op_counts_.insert_promotes_, |
| (3 * op_counts_.insert_ops_) + (2 * op_counts_.erase_ops_), |
| "#insert promotes must be <= (3 * #inserts) + (2 * #erases)"); |
| EXPECT_LE(total_insert_rotations, op_counts_.insert_ops_, |
| "#insert_rotations must be <= #inserts"); |
| |
| size_t total_erase_rotations = op_counts_.erase_rotations_ |
| + op_counts_.erase_double_rotations_; |
| EXPECT_LE(op_counts_.erase_demotes_, op_counts_.erase_ops_, |
| "#erase demotes must be <= #erases"); |
| EXPECT_LE(total_erase_rotations, op_counts_.erase_ops_, |
| "#erase_rotations must be <= #erases"); |
| |
| EXPECT_GE(max_depth, depth); |
| |
| END_TEST; |
| } |
| |
| private: |
| static OpCounts op_counts_; |
| }; |
| |
| // Static storage for the observer. |
| WAVLBalanceTestObserver::OpCounts WAVLBalanceTestObserver::op_counts_; |
| |
| // Test objects during the balance test will be allocated as a block all at once |
| // and cleaned up at the end of the test. Our test containers, however, are |
| // containers of unique pointers to objects with a no-op delete. This allows |
| // the containers to go out of scope with elements still in them (in case of a |
| // REQUIRE failure) without triggering the container assert for destroying a |
| // container of unmanaged pointer with elements still in it. |
| class BalanceTestObj; |
| |
| using BalanceTestKeyType = uint64_t; |
| using BalanceTestObjPtr = unique_ptr<BalanceTestObj>; |
| using BalanceTestTree = WAVLTree<BalanceTestKeyType, |
| BalanceTestObjPtr, |
| DefaultKeyedObjectTraits<BalanceTestKeyType, BalanceTestObj>, |
| DefaultWAVLTreeTraits<BalanceTestObjPtr, int32_t>, |
| DefaultObjectTag, |
| WAVLBalanceTestObserver>; |
| |
| class BalanceTestObj { |
| public: |
| void Init(BalanceTestKeyType val) { |
| key_ = val; |
| erase_deck_ptr_ = this; |
| } |
| |
| BalanceTestKeyType GetKey() const { return key_; } |
| BalanceTestObj* EraseDeckPtr() const { return erase_deck_ptr_; } |
| |
| void SwapEraseDeckPtr(BalanceTestObj& other) { |
| BalanceTestObj* tmp = erase_deck_ptr_; |
| erase_deck_ptr_ = other.erase_deck_ptr_; |
| other.erase_deck_ptr_ = tmp; |
| } |
| |
| bool InContainer() const { return wavl_node_state_.InContainer(); } |
| |
| private: |
| friend DefaultWAVLTreeTraits<BalanceTestObjPtr, int32_t>; |
| |
| static void operator delete(void* ptr) { |
| // Deliberate no-op |
| } |
| friend class std::default_delete<BalanceTestObj>; |
| |
| BalanceTestKeyType key_; |
| BalanceTestObj* erase_deck_ptr_; |
| WAVLTreeNodeState<BalanceTestObjPtr, int32_t> wavl_node_state_; |
| }; |
| |
| static constexpr size_t kBalanceTestSize = 2048; |
| |
| static bool DoBalanceTestInsert(BalanceTestTree& tree, BalanceTestObj* ptr) { |
| BEGIN_TEST; |
| |
| // The selected object should not be in the tree. |
| ASSERT_NONNULL(ptr); |
| ASSERT_FALSE(ptr->InContainer()); |
| |
| // Put the object into the tree. Assert that it succeeds, then |
| // sanity check the tree. |
| ASSERT_TRUE(tree.insert_or_find(BalanceTestObjPtr(ptr))); |
| ASSERT_TRUE(WAVLTreeChecker::SanityCheck(tree)); |
| |
| END_TEST; |
| } |
| |
| static bool DoBalanceTestErase(BalanceTestTree& tree, BalanceTestObj* ptr) { |
| BEGIN_TEST; |
| |
| // The selected object should still be in the tree. |
| ASSERT_NONNULL(ptr); |
| ASSERT_TRUE(ptr->InContainer()); |
| |
| // Erase should find the object and transfer its pointer back to us. |
| // The object should no longer be in the tree. |
| BalanceTestObjPtr erased = tree.erase(ptr->GetKey()); |
| ASSERT_EQ(ptr, erased.get()); |
| ASSERT_FALSE(ptr->InContainer()); |
| |
| // Run a full sanity check on the tree. Its depth should be |
| // consistent with a tree which has seen both inserts and erases. |
| ASSERT_TRUE(WAVLTreeChecker::SanityCheck(tree)); |
| |
| END_TEST; |
| } |
| |
| static void ShuffleEraseDeck(const unique_ptr<BalanceTestObj[]>& objects, |
| Lfsr<BalanceTestKeyType>& rng) { |
| // Note: shuffle algorithm is a Fisher-Yates (aka Knuth) shuffle. |
| static_assert(kBalanceTestSize > 0, "Test size must be positive!"); |
| for (size_t i = kBalanceTestSize - 1; i > 1; --i) { |
| size_t ndx = static_cast<size_t>(rng.GetNext()) % i; |
| if (ndx != i) |
| objects[i].SwapEraseDeckPtr(objects[ndx]); |
| } |
| } |
| |
| static bool WAVLBalanceTest() { |
| BEGIN_TEST; |
| |
| WAVLBalanceTestObserver::OpCounts op_counts; |
| |
| // Declare these in a specific order (object pointer first) so that the tree |
| // has a chance to clean up before the memory backing the objects gets |
| // cleaned up. |
| unique_ptr<BalanceTestObj[]> objects; |
| BalanceTestTree tree; |
| |
| // We will run this test 3 times with 3 different (constant) seeds. During |
| // the first run, we will insert all of the elements with ascending key |
| // order. During the second run, we will insert all of the keys with |
| // descending key order. During the final run, we will insert all of the |
| // keys in a random order. |
| Lfsr<BalanceTestKeyType> rng; |
| static const BalanceTestKeyType seeds[] = { 0xe87e1062fc1f4f80u, |
| 0x03d6bffb124b4918u, |
| 0x8f7d83e8d10b4765u }; |
| |
| // Allocate the objects we will use for the test. |
| { |
| AllocChecker ac; |
| objects.reset(new (&ac) BalanceTestObj[kBalanceTestSize]); |
| ASSERT_TRUE(ac.check(), "Failed to allocate test objects!"); |
| } |
| |
| for (size_t seed_ndx = 0; seed_ndx < fbl::count_of(seeds); ++seed_ndx) { |
| auto seed = seeds[seed_ndx]; |
| |
| // Seed the RNG and reset the observer stats. |
| rng.SetCore(seed); |
| WAVLBalanceTestObserver::ResetObserverOpCounts(); |
| |
| // Initialize each object with the proper key for this run. This places |
| // the object in the erase deck sequence at the same time. |
| switch (seed_ndx) { |
| case 0u: |
| for (size_t i = 0; i < kBalanceTestSize; ++i) |
| objects[i].Init(i); |
| break; |
| |
| case 1u: |
| for (size_t i = 0; i < kBalanceTestSize; ++i) |
| objects[i].Init(kBalanceTestSize - i); |
| break; |
| |
| default: |
| for (size_t i = 0; i < kBalanceTestSize; ++i) |
| objects[i].Init(rng.GetNext()); |
| break; |
| } |
| |
| // Place each object into the tree, then perform a full sanity check on |
| // the tree. If anything goes wrong, just abort the test. If we keep |
| // going, we are just going to get an unmanageable amt of errors. |
| for (size_t i = 0; i < kBalanceTestSize; ++i) |
| ASSERT_TRUE(DoBalanceTestInsert(tree, &objects[i])); |
| |
| // Shuffle the erase deck. |
| ShuffleEraseDeck(objects, rng); |
| |
| // Erase half of the elements in the tree. |
| for (size_t i = 0; i < (kBalanceTestSize >> 1); ++i) |
| ASSERT_TRUE(DoBalanceTestErase(tree, objects[i].EraseDeckPtr())); |
| |
| // Put the elements back so that we have inserted some elements into a |
| // non-empty tree which has seen erase operations. |
| for (size_t i = 0; i < (kBalanceTestSize >> 1); ++i) |
| ASSERT_TRUE(DoBalanceTestInsert(tree, objects[i].EraseDeckPtr())); |
| |
| // Shuffle the erase deck again. |
| ShuffleEraseDeck(objects, rng); |
| |
| // Now erase every element from the tree. |
| for (size_t i = 0; i < kBalanceTestSize; ++i) |
| ASSERT_TRUE(DoBalanceTestErase(tree, objects[i].EraseDeckPtr())); |
| |
| ASSERT_EQ(0u, tree.size()); |
| |
| WAVLBalanceTestObserver::AccumulateObserverOpCounts(op_counts); |
| } |
| |
| // Finally, make sure that we have exercised all of the different re-balance |
| // cases. |
| EXPECT_LT(0u, op_counts.insert_ops_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.insert_promotes_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.insert_rotations_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.insert_double_rotations_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.erase_ops_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.erase_demotes_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.erase_rotations_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.erase_double_rotations_, "Insufficient test coverage!"); |
| |
| END_TEST; |
| } |
| |
| BEGIN_TEST_CASE(wavl_tree_tests) |
| ////////////////////////////////////////// |
| // General container specific tests. |
| ////////////////////////////////////////// |
| RUN_NAMED_TEST("Clear (unmanaged)", UMTE::ClearTest) |
| RUN_NAMED_TEST("Clear (unique)", UPTE::ClearTest) |
| RUN_NAMED_TEST("Clear (std::uptr)", SUPDDTE::ClearTest) |
| RUN_NAMED_TEST("Clear (std::uptr<Del>)", SUPCDTE::ClearTest) |
| RUN_NAMED_TEST("Clear (RefPtr)", RPTE::ClearTest) |
| |
| RUN_NAMED_TEST("ClearUnsafe (unmanaged)", UMTE::ClearUnsafeTest) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_NAMED_TEST("ClearUnsafe (unique)", UPTE::ClearUnsafeTest) |
| RUN_NAMED_TEST("ClearUnsafe (std::uptr)", SUPDDTE::ClearUnsafeTest) |
| RUN_NAMED_TEST("ClearUnsafe (std::uptr<Del>)", SUPCDTE::ClearUnsafeTest) |
| RUN_NAMED_TEST("ClearUnsafe (RefPtr)", RPTE::ClearUnsafeTest) |
| #endif |
| |
| RUN_NAMED_TEST("IsEmpty (unmanaged)", UMTE::IsEmptyTest) |
| RUN_NAMED_TEST("IsEmpty (unique)", UPTE::IsEmptyTest) |
| RUN_NAMED_TEST("IsEmpty (std::uptr)", SUPDDTE::IsEmptyTest) |
| RUN_NAMED_TEST("IsEmpty (std::uptr<Del>)", SUPCDTE::IsEmptyTest) |
| RUN_NAMED_TEST("IsEmpty (RefPtr)", RPTE::IsEmptyTest) |
| |
| RUN_NAMED_TEST("Iterate (unmanaged)", UMTE::IterateTest) |
| RUN_NAMED_TEST("Iterate (unique)", UPTE::IterateTest) |
| RUN_NAMED_TEST("Iterate (std::uptr)", SUPDDTE::IterateTest) |
| RUN_NAMED_TEST("Iterate (std::uptr<Del>)", SUPCDTE::IterateTest) |
| RUN_NAMED_TEST("Iterate (RefPtr)", RPTE::IterateTest) |
| |
| RUN_NAMED_TEST("IterErase (unmanaged)", UMTE::IterEraseTest) |
| RUN_NAMED_TEST("IterErase (unique)", UPTE::IterEraseTest) |
| RUN_NAMED_TEST("IterErase (std::uptr)", SUPDDTE::IterEraseTest) |
| RUN_NAMED_TEST("IterErase (std::uptr<Del>)", SUPCDTE::IterEraseTest) |
| RUN_NAMED_TEST("IterErase (RefPtr)", RPTE::IterEraseTest) |
| |
| RUN_NAMED_TEST("DirectErase (unmanaged)", UMTE::DirectEraseTest) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_NAMED_TEST("DirectErase (unique)", UPTE::DirectEraseTest) |
| RUN_NAMED_TEST("DirectErase (std::uptr)", SUPDDTE::DirectEraseTest) |
| RUN_NAMED_TEST("DirectErase (std::uptr<Del>)", SUPCDTE::DirectEraseTest) |
| #endif |
| RUN_NAMED_TEST("DirectErase (RefPtr)", RPTE::DirectEraseTest) |
| |
| RUN_NAMED_TEST("MakeIterator (unmanaged)", UMTE::MakeIteratorTest) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_NAMED_TEST("MakeIterator (unique)", UPTE::MakeIteratorTest) |
| RUN_NAMED_TEST("MakeIterator (std::uptr)", SUPDDTE::MakeIteratorTest) |
| RUN_NAMED_TEST("MakeIterator (std::uptr<Del>)", SUPCDTE::MakeIteratorTest) |
| #endif |
| RUN_NAMED_TEST("MakeIterator (RefPtr)", RPTE::MakeIteratorTest) |
| |
| RUN_NAMED_TEST("ReverseIterErase (unmanaged)", UMTE::ReverseIterEraseTest) |
| RUN_NAMED_TEST("ReverseIterErase (unique)", UPTE::ReverseIterEraseTest) |
| RUN_NAMED_TEST("ReverseIterErase (std::uptr)", SUPDDTE::ReverseIterEraseTest) |
| RUN_NAMED_TEST("ReverseIterErase (std::uptr<Del>)", SUPCDTE::ReverseIterEraseTest) |
| RUN_NAMED_TEST("ReverseIterErase (RefPtr)", RPTE::ReverseIterEraseTest) |
| |
| RUN_NAMED_TEST("ReverseIterate (unmanaged)", UMTE::ReverseIterateTest) |
| RUN_NAMED_TEST("ReverseIterate (unique)", UPTE::ReverseIterateTest) |
| RUN_NAMED_TEST("ReverseIterate (std::uptr)", SUPDDTE::ReverseIterateTest) |
| RUN_NAMED_TEST("ReverseIterate (std::uptr<Del>)", SUPCDTE::ReverseIterateTest) |
| RUN_NAMED_TEST("ReverseIterate (RefPtr)", RPTE::ReverseIterateTest) |
| |
| RUN_NAMED_TEST("Swap (unmanaged)", UMTE::SwapTest) |
| RUN_NAMED_TEST("Swap (unique)", UPTE::SwapTest) |
| RUN_NAMED_TEST("Swap (std::uptr)", SUPDDTE::SwapTest) |
| RUN_NAMED_TEST("Swap (std::uptr<Del>)", SUPCDTE::SwapTest) |
| RUN_NAMED_TEST("Swap (RefPtr)", RPTE::SwapTest) |
| |
| RUN_NAMED_TEST("Rvalue Ops (unmanaged)", UMTE::RvalueOpsTest) |
| RUN_NAMED_TEST("Rvalue Ops (unique)", UPTE::RvalueOpsTest) |
| RUN_NAMED_TEST("Rvalue Ops (std::uptr)", SUPDDTE::RvalueOpsTest) |
| RUN_NAMED_TEST("Rvalue Ops (std::uptr<Del>)", SUPCDTE::RvalueOpsTest) |
| RUN_NAMED_TEST("Rvalue Ops (RefPtr)", RPTE::RvalueOpsTest) |
| |
| RUN_NAMED_TEST("Scope (unique)", UPTE::ScopeTest) |
| RUN_NAMED_TEST("Scope (std::uptr)", SUPDDTE::ScopeTest) |
| RUN_NAMED_TEST("Scope (std::uptr<Del>)", SUPCDTE::ScopeTest) |
| RUN_NAMED_TEST("Scope (RefPtr)", RPTE::ScopeTest) |
| |
| RUN_NAMED_TEST("TwoContainer (unmanaged)", UMTE::TwoContainerTest) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_NAMED_TEST("TwoContainer (unique)", UPTE::TwoContainerTest) |
| RUN_NAMED_TEST("TwoContainer (std::uptr)", SUPDDTE::TwoContainerTest) |
| RUN_NAMED_TEST("TwoContainer (std::uptr<Del>)", SUPCDTE::TwoContainerTest) |
| #endif |
| RUN_NAMED_TEST("TwoContainer (RefPtr)", RPTE::TwoContainerTest) |
| |
| RUN_NAMED_TEST("ThreeContainerHelper (unmanaged)", UMTE::ThreeContainerHelperTest) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_NAMED_TEST("ThreeContainerHelper (unique)", UPTE::ThreeContainerHelperTest) |
| RUN_NAMED_TEST("ThreeContainerHelper (std::uptr)", SUPDDTE::ThreeContainerHelperTest) |
| RUN_NAMED_TEST("ThreeContainerHelper (std::uptr<Del>)", SUPCDTE::ThreeContainerHelperTest) |
| #endif |
| RUN_NAMED_TEST("ThreeContainerHelper (RefPtr)", RPTE::ThreeContainerHelperTest) |
| |
| RUN_NAMED_TEST("IterCopyPointer (unmanaged)", UMTE::IterCopyPointerTest) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_NAMED_TEST("IterCopyPointer (unique)", UPTE::IterCopyPointerTest) |
| RUN_NAMED_TEST("IterCopyPointer (std::uptr)", SUPDDTE::IterCopyPointerTest) |
| RUN_NAMED_TEST("IterCopyPointer (std::uptr<Del>)", SUPCDTE::IterCopyPointerTest) |
| #endif |
| RUN_NAMED_TEST("IterCopyPointer (RefPtr)", RPTE::IterCopyPointerTest) |
| |
| RUN_NAMED_TEST("EraseIf (unmanaged)", UMTE::EraseIfTest) |
| RUN_NAMED_TEST("EraseIf (unique)", UPTE::EraseIfTest) |
| RUN_NAMED_TEST("EraseIf (std::uptr)", SUPDDTE::EraseIfTest) |
| RUN_NAMED_TEST("EraseIf (std::uptr<Del>)", SUPCDTE::EraseIfTest) |
| RUN_NAMED_TEST("EraseIf (RefPtr)", RPTE::EraseIfTest) |
| |
| RUN_NAMED_TEST("FindIf (unmanaged)", UMTE::FindIfTest) |
| RUN_NAMED_TEST("FindIf (unique)", UPTE::FindIfTest) |
| RUN_NAMED_TEST("FindIf (std::uptr)", SUPDDTE::FindIfTest) |
| RUN_NAMED_TEST("FindIf (std::uptr<Del>)", SUPCDTE::FindIfTest) |
| RUN_NAMED_TEST("FindIf (RefPtr)", RPTE::FindIfTest) |
| |
| ////////////////////////////////////////// |
| // Associative container specific tests. |
| ////////////////////////////////////////// |
| RUN_NAMED_TEST("InsertByKey (unmanaged)", UMTE::InsertByKeyTest) |
| RUN_NAMED_TEST("InsertByKey (unique)", UPTE::InsertByKeyTest) |
| RUN_NAMED_TEST("InsertByKey (std::uptr)", SUPDDTE::InsertByKeyTest) |
| RUN_NAMED_TEST("InsertByKey (std::uptr<Del>)", SUPCDTE::InsertByKeyTest) |
| RUN_NAMED_TEST("InsertByKey (RefPtr)", RPTE::InsertByKeyTest) |
| |
| RUN_NAMED_TEST("FindByKey (unmanaged)", UMTE::FindByKeyTest) |
| RUN_NAMED_TEST("FindByKey (unique)", UPTE::FindByKeyTest) |
| RUN_NAMED_TEST("FindByKey (std::uptr)", SUPDDTE::FindByKeyTest) |
| RUN_NAMED_TEST("FindByKey (std::uptr<Del>)", SUPCDTE::FindByKeyTest) |
| RUN_NAMED_TEST("FindByKey (RefPtr)", RPTE::FindByKeyTest) |
| |
| RUN_NAMED_TEST("EraseByKey (unmanaged)", UMTE::EraseByKeyTest) |
| RUN_NAMED_TEST("EraseByKey (unique)", UPTE::EraseByKeyTest) |
| RUN_NAMED_TEST("EraseByKey (std::uptr)", SUPDDTE::EraseByKeyTest) |
| RUN_NAMED_TEST("EraseByKey (std::uptr<Del>)", SUPCDTE::EraseByKeyTest) |
| RUN_NAMED_TEST("EraseByKey (RefPtr)", RPTE::EraseByKeyTest) |
| |
| RUN_NAMED_TEST("InsertOrFind (unmanaged)", UMTE::InsertOrFindTest) |
| RUN_NAMED_TEST("InsertOrFind (unique)", UPTE::InsertOrFindTest) |
| RUN_NAMED_TEST("InsertOrFind (std::uptr)", SUPDDTE::InsertOrFindTest) |
| RUN_NAMED_TEST("InsertOrFind (std::uptr<Del>)", SUPCDTE::InsertOrFindTest) |
| RUN_NAMED_TEST("InsertOrFind (RefPtr)", RPTE::InsertOrFindTest) |
| |
| RUN_NAMED_TEST("InsertOrReplace (unmanaged)", UMTE::InsertOrReplaceTest) |
| RUN_NAMED_TEST("InsertOrReplace (unique)", UPTE::InsertOrReplaceTest) |
| RUN_NAMED_TEST("InsertOrReplace (std::uptr)", SUPDDTE::InsertOrReplaceTest) |
| RUN_NAMED_TEST("InsertOrReplace (std::uptr<Del>)", SUPCDTE::InsertOrReplaceTest) |
| RUN_NAMED_TEST("InsertOrReplace (RefPtr)", RPTE::InsertOrReplaceTest) |
| |
| //////////////////////////////////////////////// |
| // OrderedAssociative container specific tests. |
| //////////////////////////////////////////////// |
| RUN_NAMED_TEST("OrderedIter (unmanaged)", UMTE::OrderedIterTest) |
| RUN_NAMED_TEST("OrderedIter (unique)", UPTE::OrderedIterTest) |
| RUN_NAMED_TEST("OrderedIter (std::uptr)", SUPDDTE::OrderedIterTest) |
| RUN_NAMED_TEST("OrderedIter (std::uptr<Del>)", SUPCDTE::OrderedIterTest) |
| RUN_NAMED_TEST("OrderedIter (RefPtr)", RPTE::OrderedIterTest) |
| |
| RUN_NAMED_TEST("OrderedReverseIter (unmanaged)", UMTE::OrderedReverseIterTest) |
| RUN_NAMED_TEST("OrderedReverseIter (unique)", UPTE::OrderedReverseIterTest) |
| RUN_NAMED_TEST("OrderedReverseIter (std::uptr)", SUPDDTE::OrderedReverseIterTest) |
| RUN_NAMED_TEST("OrderedReverseIter (std::uptr<Del>)", SUPCDTE::OrderedReverseIterTest) |
| RUN_NAMED_TEST("OrderedReverseIter (RefPtr)", RPTE::OrderedReverseIterTest) |
| |
| RUN_NAMED_TEST("UpperBound (unmanaged)", UMTE::UpperBoundTest) |
| RUN_NAMED_TEST("UpperBound (unique)", UPTE::UpperBoundTest) |
| RUN_NAMED_TEST("UpperBound (std::uptr)", SUPDDTE::UpperBoundTest) |
| RUN_NAMED_TEST("UpperBound (std::uptr<Del>)", SUPCDTE::UpperBoundTest) |
| RUN_NAMED_TEST("UpperBound (RefPtr)", RPTE::UpperBoundTest) |
| |
| RUN_NAMED_TEST("LowerBound (unmanaged)", UMTE::LowerBoundTest) |
| RUN_NAMED_TEST("LowerBound (unique)", UPTE::LowerBoundTest) |
| RUN_NAMED_TEST("LowerBound (std::uptr)", SUPDDTE::LowerBoundTest) |
| RUN_NAMED_TEST("LowerBound (std::uptr<Del>)", SUPCDTE::LowerBoundTest) |
| RUN_NAMED_TEST("LowerBound (RefPtr)", RPTE::LowerBoundTest) |
| |
| //////////////////////////// |
| // WAVLTree specific tests. |
| //////////////////////////// |
| // ZX-2230: This can take more than 20 seconds in CI, so mark it medium. |
| RUN_NAMED_TEST_MEDIUM("BalanceTest", WAVLBalanceTest) |
| |
| END_TEST_CASE(wavl_tree_tests) |
| |
| } // namespace intrusive_containers |
| } // namespace tests |
| } // namespace fbl |
