| // 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 <algorithm> |
| #include <iterator> |
| |
| #include <fbl/intrusive_pointer_traits.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 <zxtest/zxtest.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, NodeOptions kNodeOptions = NodeOptions::None> |
| class WAVLTraits { |
| public: |
| // clang-format off |
| using KeyType = size_t; |
| using TestObjBaseType = KeyedTestObjBase<KeyType>; |
| |
| using ContainerType = WAVLTree<KeyType, PtrType>; |
| using ContainableBaseClass = WAVLTreeContainable<PtrType, kNodeOptions>; |
| using ContainerStateType = WAVLTreeNodeState<PtrType, kNodeOptions>; |
| |
| using OtherContainerStateType = OtherTreeNodeState<KeyType, PtrType>; |
| using OtherContainerTraits = OtherTreeTraits<OtherContainerStateType>; |
| using OtherContainerType = WAVLTree<KeyType, |
| PtrType, |
| OtherContainerTraits, |
| DefaultObjectTag, |
| OtherContainerTraits>; |
| |
| struct Tag1 {}; |
| struct Tag2 {}; |
| struct Tag3 {}; |
| |
| using TaggedContainableBaseClasses = |
| fbl::ContainableBaseClasses<TaggedWAVLTreeContainable<PtrType, Tag1>, |
| TaggedWAVLTreeContainable<PtrType, Tag2>, |
| TaggedWAVLTreeContainable<PtrType, Tag3>>; |
| |
| using TaggedType1 = TaggedWAVLTree<KeyType, PtrType, Tag1>; |
| using TaggedType2 = TaggedWAVLTree<KeyType, PtrType, Tag2>; |
| using TaggedType3 = TaggedWAVLTree<KeyType, PtrType, Tag3>; |
| // clang-format on |
| }; |
| |
| // 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. |
| // clang-format off |
| DEFINE_TEST_OBJECTS(WAVL); |
| using UMTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, Unmanaged); |
| using UPDDTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, UniquePtrDefaultDeleter); |
| using UPCDTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, UniquePtrCustomDeleter); |
| using RPTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, RefPtr); |
| VERIFY_CONTAINER_SIZES(WAVL, sizeof(void*) * 4); |
| |
| // Versions of the test objects which support clear_unsafe. |
| template <typename PtrType> |
| using CU_WAVLTraits = WAVLTraits<PtrType, fbl::NodeOptions::AllowClearUnsafe>; |
| DEFINE_TEST_OBJECTS(CU_WAVL); |
| using CU_UMTE = DEFINE_TEST_THUNK(OrderedAssociative, CU_WAVL, Unmanaged); |
| using CU_UPDDTE = DEFINE_TEST_THUNK(OrderedAssociative, CU_WAVL, UniquePtrDefaultDeleter); |
| // clang-format on |
| |
| // 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() = default; |
| |
| void reset() { *this = OpCounts{}; } |
| |
| 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.insert_collisions_ += insert_collisions_; |
| target.insert_replacements_ += insert_replacements_; |
| target.insert_traversals_ += insert_traversals_; |
| target.inspected_rotations_ += inspected_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_{0}; |
| size_t insert_promotes_{0}; |
| size_t insert_rotations_{0}; |
| size_t insert_double_rotations_{0}; |
| size_t insert_collisions_{0}; |
| size_t insert_replacements_{0}; |
| size_t insert_traversals_{0}; |
| |
| size_t inspected_rotations_{0}; |
| |
| size_t erase_ops_{0}; |
| size_t erase_demotes_{0}; |
| size_t erase_rotations_{0}; |
| size_t erase_double_rotations_{0}; |
| }; |
| |
| static void ResetObserverOpCounts() { op_counts_.reset(); } |
| static void AccumulateObserverOpCounts(OpCounts& target) { op_counts_.accumulate(target); } |
| |
| template <typename Iter> |
| static void RecordInsert(Iter node) { |
| ++op_counts_.insert_ops_; |
| |
| // Set the subtree min/max values to the node's key, as it is a leaf when |
| // first inserted, before rebalancing. |
| node->min_subtree_key_ = node->max_subtree_key_ = node->key_; |
| } |
| template <typename T, typename Iter> |
| static void RecordInsertCollision(T* node, Iter collision) { |
| ++op_counts_.insert_collisions_; |
| |
| // A collision doesn't affect the subtree min/max values of any ancestor |
| // during traversal. |
| } |
| template <typename Iter, typename T> |
| static void RecordInsertReplace(Iter node, T* replacement) { |
| ++op_counts_.insert_replacements_; |
| |
| // Copy the subtree min/max values to the replacement node. |
| replacement->min_subtree_key_ = node->min_subtree_key_; |
| replacement->max_subtree_key_ = node->max_subtree_key_; |
| } |
| template <typename T, typename Iter> |
| static void RecordInsertTraverse(T* node, Iter ancestor) { |
| ++op_counts_.insert_traversals_; |
| |
| // Update each ancestor's subtree min/max values as the insertion traverses |
| // them to find the insertion point of the new node. |
| ancestor->min_subtree_key_ = std::min(ancestor->min_subtree_key_, node->key_); |
| ancestor->max_subtree_key_ = std::max(ancestor->max_subtree_key_, node->key_); |
| } |
| static void RecordInsertPromote() { ++op_counts_.insert_promotes_; } |
| static void RecordInsertRotation() { ++op_counts_.insert_rotations_; } |
| static void RecordInsertDoubleRotation() { ++op_counts_.insert_double_rotations_; } |
| template <typename Iter> |
| static void RecordRotation(Iter pivot, Iter lr_child, Iter rl_child, Iter parent, Iter sibling) { |
| ++op_counts_.inspected_rotations_; |
| |
| // Update the subtree min/max values given the nodes that are about to be |
| // rotated. |
| |
| // The overall subtree maintains the same max/min. The pivot replaces the |
| // parent at the head of the subtree. |
| pivot->min_subtree_key_ = parent->min_subtree_key_; |
| pivot->max_subtree_key_ = parent->max_subtree_key_; |
| |
| // Compute the new subtree min/max of the original parent, which may now |
| // include a node adopted from the pivot. |
| parent->min_subtree_key_ = parent->key_; |
| parent->max_subtree_key_ = parent->key_; |
| if (sibling) { |
| parent->min_subtree_key_ = std::min(parent->min_subtree_key_, sibling->min_subtree_key_); |
| parent->max_subtree_key_ = std::max(parent->max_subtree_key_, sibling->max_subtree_key_); |
| } |
| if (lr_child) { |
| parent->min_subtree_key_ = std::min(parent->min_subtree_key_, lr_child->min_subtree_key_); |
| parent->max_subtree_key_ = std::max(parent->max_subtree_key_, lr_child->max_subtree_key_); |
| } |
| } |
| template <typename T, typename Iter> |
| static void RecordErase(T* node, Iter invalidated) { |
| ++op_counts_.erase_ops_; |
| |
| // Erasing a node may invalidate each ancestor's subtree min/max along the |
| // path to the root: re-compute the min/max values for each ancestor. |
| // Note that this process could be terminated early when updating an |
| // ancestor has no effect, but this optimization is not necessary to |
| // demonstrate correctness. |
| Iter current = invalidated; |
| while (current) { |
| current->min_subtree_key_ = current->key_; |
| current->max_subtree_key_ = current->key_; |
| if (Iter left = current.left(); left) { |
| current->min_subtree_key_ = std::min(current->min_subtree_key_, left->min_subtree_key_); |
| current->max_subtree_key_ = std::max(current->max_subtree_key_, left->max_subtree_key_); |
| } |
| if (Iter right = current.right(); right) { |
| current->min_subtree_key_ = std::min(current->min_subtree_key_, right->min_subtree_key_); |
| current->max_subtree_key_ = std::max(current->max_subtree_key_, right->max_subtree_key_); |
| } |
| current = current.parent(); |
| } |
| } |
| 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 void VerifyRankRule(const TreeType& tree, typename TreeType::RawPtrType node) { |
| 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]"); |
| } |
| } |
| } |
| |
| template <typename TreeType> |
| static void VerifyBalance(const TreeType& tree, uint64_t depth) { |
| // 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; |
| } |
| |
| const 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"); |
| |
| const 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"); |
| |
| const size_t total_inspected_rotations = |
| op_counts_.insert_rotations_ + op_counts_.erase_rotations_ + |
| 2 * op_counts_.insert_double_rotations_ + 2 * op_counts_.erase_double_rotations_; |
| EXPECT_EQ(total_inspected_rotations, op_counts_.inspected_rotations_, |
| "#inspected rotations must be == #rotations"); |
| |
| EXPECT_GE(max_depth, depth); |
| } |
| |
| 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 = std::unique_ptr<BalanceTestObj>; |
| using BalanceTestTree = |
| WAVLTree<BalanceTestKeyType, BalanceTestObjPtr, |
| DefaultKeyedObjectTraits<BalanceTestKeyType, BalanceTestObj>, DefaultObjectTag, |
| DefaultWAVLTreeTraits<BalanceTestObjPtr, DefaultObjectTag>, WAVLBalanceTestObserver>; |
| |
| class BalanceTestObj { |
| public: |
| void Init(BalanceTestKeyType val) { |
| key_ = val; |
| erase_deck_ptr_ = this; |
| } |
| |
| BalanceTestKeyType GetKey() const { return key_; } |
| BalanceTestKeyType GetMinSubtreeKey() const { return min_subtree_key_; } |
| BalanceTestKeyType GetMaxSubtreeKey() const { return max_subtree_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, DefaultObjectTag>; |
| friend WAVLBalanceTestObserver; |
| |
| static void operator delete(void* ptr) { |
| // Deliberate no-op |
| } |
| friend class std::default_delete<BalanceTestObj>; |
| |
| BalanceTestKeyType key_; |
| BalanceTestKeyType min_subtree_key_; |
| BalanceTestKeyType max_subtree_key_; |
| BalanceTestObj* erase_deck_ptr_; |
| WAVLTreeNodeState<BalanceTestObjPtr, NodeOptions::None, int32_t> wavl_node_state_; |
| }; |
| |
| // Only enable heavy weight testing when asked to do so. |
| #if FBL_TEST_ENABLE_WAVL_TREE_BALANCE_TEST |
| static constexpr size_t kBalanceTestSize = 2048; |
| #else |
| static constexpr size_t kBalanceTestSize = 32; |
| #endif |
| |
| static void DoBalanceTestInsert(BalanceTestTree& tree, BalanceTestObj* ptr) { |
| // The selected object should not be in the tree. |
| ASSERT_NOT_NULL(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_NO_FAILURES(WAVLTreeChecker::SanityCheck(tree)); |
| } |
| |
| static void DoBalanceTestCollide(BalanceTestTree& tree, BalanceTestObj* ptr) { |
| // The selected object should not be in the tree. |
| ASSERT_NOT_NULL(ptr); |
| ASSERT_FALSE(ptr->InContainer()); |
| |
| // Put the object into the tree. Assert that it fails, then |
| // sanity check the tree. |
| ASSERT_FALSE(tree.insert_or_find(BalanceTestObjPtr(ptr))); |
| ASSERT_NO_FAILURES(WAVLTreeChecker::SanityCheck(tree)); |
| } |
| |
| static void DoBalanceTestReplace(BalanceTestTree& tree, BalanceTestObj* ptr) { |
| // The selected object should not be in the tree. |
| ASSERT_NOT_NULL(ptr); |
| ASSERT_FALSE(ptr->InContainer()); |
| |
| // Put the object into the tree. Assert that it fails, then |
| // sanity check the tree. |
| ASSERT_NOT_NULL(tree.insert_or_replace(BalanceTestObjPtr(ptr))); |
| ASSERT_NO_FAILURES(WAVLTreeChecker::SanityCheck(tree)); |
| } |
| |
| static void DoBalanceTestErase(BalanceTestTree& tree, BalanceTestObj* ptr) { |
| // The selected object should still be in the tree. |
| ASSERT_NOT_NULL(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_NO_FAILURES(WAVLTreeChecker::SanityCheck(tree)); |
| } |
| |
| static void ShuffleEraseDeck(const std::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]); |
| } |
| } |
| |
| // Performs an efficient check that the augmented binary tree invariants hold. |
| // The augmented binary tree maintains the min/max keys of every subtree. The |
| // min/max values in the root node should always match the keys of the leftmost/ |
| // rightmost nodes, respectively. |
| static void CheckAugmentedInvariants(const BalanceTestTree& tree) { |
| if (const auto root = tree.croot(); root) { |
| EXPECT_EQ(root->GetMinSubtreeKey(), tree.front().GetKey()); |
| EXPECT_EQ(root->GetMaxSubtreeKey(), tree.back().GetKey()); |
| } |
| } |
| |
| // Checks that left, right, and parent iterator operations reach the expected |
| // nodes. |
| static void CheckIterators(const BalanceTestTree& tree) { |
| // Descend the left and right paths from the root. These should reach the |
| // leftmost and rightmost nodes in no more iterations than there are nodes, |
| // in the worst case. |
| const auto left_most = tree.cbegin(); |
| const auto right_most = --tree.cend(); |
| const auto root = tree.croot(); |
| const auto size = tree.size(); |
| |
| auto left_cursor = root; |
| auto right_cursor = root; |
| size_t i; |
| for (i = 0; (left_cursor != left_most || right_cursor != right_most) && i < size; ++i) { |
| ASSERT_TRUE(left_cursor); |
| if (left_cursor == left_most) { |
| EXPECT_FALSE(left_cursor.left()); |
| } else { |
| left_cursor = left_cursor.left(); |
| } |
| |
| ASSERT_TRUE(right_cursor); |
| if (right_cursor == right_most) { |
| EXPECT_FALSE(right_cursor.right()); |
| } else { |
| right_cursor = right_cursor.right(); |
| } |
| } |
| |
| EXPECT_EQ(left_cursor, left_most); |
| EXPECT_EQ(right_cursor, right_most); |
| |
| // Ascend the left and right paths to the root. These should reach the root |
| // node in no more iterations than the descent above. |
| const size_t limit = i; |
| left_cursor = left_most; |
| right_cursor = right_most; |
| for (i = 0; (left_cursor != root || right_cursor != root) && i < limit; ++i) { |
| ASSERT_TRUE(left_cursor); |
| if (left_cursor == root) { |
| EXPECT_FALSE(left_cursor.parent()); |
| } else { |
| left_cursor = left_cursor.parent(); |
| } |
| |
| ASSERT_TRUE(right_cursor); |
| if (right_cursor == root) { |
| EXPECT_FALSE(right_cursor.parent()); |
| } else { |
| right_cursor = right_cursor.parent(); |
| } |
| } |
| |
| EXPECT_EQ(left_cursor, root); |
| EXPECT_EQ(right_cursor, root); |
| } |
| |
| // clang-format off |
| ////////////////////////////////////////// |
| // General container specific tests. |
| ////////////////////////////////////////// |
| RUN_ZXTEST(WavlTreeTest, UMTE, Clear) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, Clear) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, Clear) |
| RUN_ZXTEST(WavlTreeTest, RPTE, Clear) |
| |
| #if TEST_WILL_NOT_COMPILE || 0 |
| // Won't compile because node lacks AllowClearUnsafe option. |
| RUN_ZXTEST(WavlTreeTest, UMTE, ClearUnsafe) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, ClearUnsafe) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, ClearUnsafe) |
| RUN_ZXTEST(WavlTreeTest, RPTE, ClearUnsafe) |
| #endif |
| |
| #if TEST_WILL_NOT_COMPILE || 0 |
| // Won't compile because pointer type is managed. |
| RUN_ZXTEST(WavlTreeTest, CU_UPDDTE, ClearUnsafe) |
| #endif |
| |
| RUN_ZXTEST(WavlTreeTest, CU_UMTE, ClearUnsafe) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, IsEmpty) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, IsEmpty) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, IsEmpty) |
| RUN_ZXTEST(WavlTreeTest, RPTE, IsEmpty) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, Iterate) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, Iterate) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, Iterate) |
| RUN_ZXTEST(WavlTreeTest, RPTE, Iterate) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, IterErase) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, IterErase) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, IterErase) |
| RUN_ZXTEST(WavlTreeTest, RPTE, IterErase) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, DirectErase) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, DirectErase) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, DirectErase) |
| RUN_ZXTEST(WavlTreeTest, RPTE, DirectErase) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, MakeIterator) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, MakeIterator) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, MakeIterator) |
| RUN_ZXTEST(WavlTreeTest, RPTE, MakeIterator) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, ReverseIterErase) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, ReverseIterErase) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, ReverseIterErase) |
| RUN_ZXTEST(WavlTreeTest, RPTE, ReverseIterErase) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, ReverseIterate) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, ReverseIterate) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, ReverseIterate) |
| RUN_ZXTEST(WavlTreeTest, RPTE, ReverseIterate) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, Swap) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, Swap) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, Swap) |
| RUN_ZXTEST(WavlTreeTest, RPTE, Swap) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, RvalueOps) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, RvalueOps) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, RvalueOps) |
| RUN_ZXTEST(WavlTreeTest, RPTE, RvalueOps) |
| |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, Scope) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, Scope) |
| RUN_ZXTEST(WavlTreeTest, RPTE, Scope) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, TwoContainer) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, TwoContainer) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, TwoContainer) |
| #endif |
| RUN_ZXTEST(WavlTreeTest, RPTE, TwoContainer) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, ThreeContainerHelper) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, ThreeContainerHelper) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, ThreeContainerHelper) |
| #endif |
| RUN_ZXTEST(WavlTreeTest, RPTE, ThreeContainerHelper) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, IterCopyPointer) |
| #if TEST_WILL_NOT_COMPILE || 0 |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, IterCopyPointer) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, IterCopyPointer) |
| #endif |
| RUN_ZXTEST(WavlTreeTest, RPTE, IterCopyPointer) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, EraseIf) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, EraseIf) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, EraseIf) |
| RUN_ZXTEST(WavlTreeTest, RPTE, EraseIf) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, FindIf) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, FindIf) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, FindIf) |
| RUN_ZXTEST(WavlTreeTest, RPTE, FindIf) |
| |
| ////////////////////////////////////////// |
| // Associative container specific tests. |
| ////////////////////////////////////////// |
| RUN_ZXTEST(WavlTreeTest, UMTE, InsertByKey) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, InsertByKey) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, InsertByKey) |
| RUN_ZXTEST(WavlTreeTest, RPTE, InsertByKey) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, FindByKey) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, FindByKey) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, FindByKey) |
| RUN_ZXTEST(WavlTreeTest, RPTE, FindByKey) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, EraseByKey) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, EraseByKey) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, EraseByKey) |
| RUN_ZXTEST(WavlTreeTest, RPTE, EraseByKey) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, InsertOrFind) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, InsertOrFind) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, InsertOrFind) |
| RUN_ZXTEST(WavlTreeTest, RPTE, InsertOrFind) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, InsertOrReplace) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, InsertOrReplace) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, InsertOrReplace) |
| RUN_ZXTEST(WavlTreeTest, RPTE, InsertOrReplace) |
| |
| //////////////////////////////////////////////// |
| // OrderedAssociative container specific tests. |
| //////////////////////////////////////////////// |
| RUN_ZXTEST(WavlTreeTest, UMTE, OrderedIter) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, OrderedIter) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, OrderedIter) |
| RUN_ZXTEST(WavlTreeTest, RPTE, OrderedIter) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, OrderedReverseIter) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, OrderedReverseIter) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, OrderedReverseIter) |
| RUN_ZXTEST(WavlTreeTest, RPTE, OrderedReverseIter) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, UpperBound) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, UpperBound) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, UpperBound) |
| RUN_ZXTEST(WavlTreeTest, RPTE, UpperBound) |
| |
| RUN_ZXTEST(WavlTreeTest, UMTE, LowerBound) |
| RUN_ZXTEST(WavlTreeTest, UPDDTE, LowerBound) |
| RUN_ZXTEST(WavlTreeTest, UPCDTE, LowerBound) |
| RUN_ZXTEST(WavlTreeTest, RPTE, LowerBound) |
| |
| |
| // Negative compilation test which make sure that we don't accidentally |
| // mismatch pointer types between the node and the container. |
| TEST(WavlTreeTest, MismatchedPointerType) { |
| struct Obj { |
| fbl::WAVLTreeNodeState<Obj*> wavl_node_state_; |
| uintptr_t GetKey() const { return reinterpret_cast<uintptr_t>(this); } |
| }; |
| #if TEST_WILL_NOT_COMPILE || 0 |
| [[maybe_unused]] fbl::WAVLTree<uintptr_t, std::unique_ptr<Obj>> tree; |
| #endif |
| } |
| |
| // Negative compilation test which make sure that we cannot try to use a node |
| // flagged with AllowRemoveFromContainer with a WAVLTree. Note: While it would |
| // be a rather complicated refactor, we _could_ allow this, but only if we first |
| // introduce a version of the WAVLTree which does not track the size of the |
| // container. |
| TEST(WavlTreeTest, NoRemoveFromContainer) { |
| struct Obj : public WAVLTreeContainable<Obj*, NodeOptions::AllowRemoveFromContainer> { |
| uintptr_t GetKey() const { return reinterpret_cast<uintptr_t>(this); } |
| }; |
| #if TEST_WILL_NOT_COMPILE || 0 |
| [[maybe_unused]] fbl::WAVLTree<uintptr_t, Obj*> tree; |
| #endif |
| } |
| |
| TEST(WavlTreeTest, BalanceAndInvariants) { |
| 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. |
| std::unique_ptr<BalanceTestObj[]> objects; |
| std::unique_ptr<BalanceTestObj[]> replacements; |
| 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}; |
| |
| // The replacements set is a fraction of the size of the object set. |
| const size_t kReplacementCount = kBalanceTestSize / 8; |
| static_assert(kReplacementCount != 0); |
| |
| // 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!"); |
| |
| replacements.reset(new (&ac) BalanceTestObj[kReplacementCount]); |
| ASSERT_TRUE(ac.check(), "Failed to allocate replacement objects!"); |
| } |
| |
| for (size_t seed_ndx = 0; seed_ndx < std::size(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); |
| if (i < kReplacementCount) { |
| replacements[i].Init(i); |
| } |
| } |
| break; |
| |
| case 1u: |
| for (size_t i = 0; i < kBalanceTestSize; ++i) { |
| objects[i].Init(kBalanceTestSize - i); |
| if (i < kReplacementCount) { |
| replacements[i].Init(kBalanceTestSize - i); |
| } |
| } |
| break; |
| |
| default: |
| for (size_t i = 0; i < kBalanceTestSize; ++i) { |
| objects[i].Init(rng.GetNext()); |
| if (i < kReplacementCount) { |
| replacements[i].Init(objects[i].GetKey()); |
| } |
| } |
| 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_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestInsert(tree, &objects[i])); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| ASSERT_NO_FAILURES(CheckIterators(tree)); |
| |
| // Collide the replacement set with the tree. |
| for (size_t i = 0; i < kReplacementCount; ++i) { |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestCollide(tree, &replacements[i])); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| // Replace nodes in the tree with the replacement set. |
| for (size_t i = 0; i < kReplacementCount; ++i) { |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestReplace(tree, &replacements[i])); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| ASSERT_NO_FAILURES(CheckIterators(tree)); |
| |
| // Replace the original nodes in the tree. |
| for (size_t i = 0; i < kReplacementCount; ++i) { |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestReplace(tree, &objects[i])); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| ASSERT_NO_FAILURES(CheckIterators(tree)); |
| |
| // 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_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestErase(tree, objects[i].EraseDeckPtr())); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| ASSERT_NO_FAILURES(CheckIterators(tree)); |
| |
| // 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_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestInsert(tree, objects[i].EraseDeckPtr())); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| ASSERT_NO_FAILURES(CheckIterators(tree)); |
| |
| // Shuffle the erase deck again. |
| ShuffleEraseDeck(objects, rng); |
| |
| // Now erase every element from the tree. |
| for (size_t i = 0; i < kBalanceTestSize; ++i) { |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| ASSERT_NO_FAILURES(DoBalanceTestErase(tree, objects[i].EraseDeckPtr())); |
| ASSERT_NO_FAILURES(CheckAugmentedInvariants(tree)); |
| } |
| |
| ASSERT_NO_FAILURES(CheckIterators(tree)); |
| |
| 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.insert_collisions_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.insert_replacements_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.insert_traversals_, "Insufficient test coverage!"); |
| EXPECT_LT(0u, op_counts.inspected_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!"); |
| } |
| |
| } // namespace intrusive_containers |
| } // namespace tests |
| } // namespace fbl |