blob: 47f8c9c73b333eb470836ba87652cfa7ee01a222 [file] [log] [blame]
// 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>;
};
// 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>,
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 fbl::unique_ptr<BalanceTestObj[]>;
friend class fbl::unique_ptr<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("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