1// Copyright 2016 The Fuchsia Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include <math.h> 6#include <fbl/intrusive_wavl_tree.h> 7#include <fbl/tests/intrusive_containers/intrusive_wavl_tree_checker.h> 8#include <fbl/tests/intrusive_containers/ordered_associative_container_test_environment.h> 9#include <fbl/tests/intrusive_containers/test_thunks.h> 10#include <fbl/intrusive_pointer_traits.h> 11#include <unittest/unittest.h> 12 13namespace fbl { 14namespace tests { 15namespace intrusive_containers { 16 17template <typename ContainerStateType> 18struct OtherTreeTraits { 19 using KeyType = typename ContainerStateType::KeyType; 20 using PtrType = typename ContainerStateType::PtrType; 21 using PtrTraits = ::fbl::internal::ContainerPtrTraits<PtrType>; 22 23 // Node Traits 24 static WAVLTreeNodeState<PtrType>& node_state(typename PtrTraits::RefType obj) { 25 return obj.other_container_state_.node_state_; 26 } 27 28 // Key Traits 29 static KeyType GetKey(typename PtrTraits::ConstRefType obj) { 30 return obj.other_container_state_.key_; 31 } 32 static bool LessThan(const KeyType& key1, const KeyType& key2) { return key1 < key2; } 33 static bool EqualTo (const KeyType& key1, const KeyType& key2) { return key1 == key2; } 34 35 // Set key is a trait which is only used by the tests, not by the containers 36 // themselves. 37 static void SetKey(typename PtrTraits::RefType obj, KeyType key) { 38 obj.other_container_state_.key_ = key; 39 } 40}; 41 42template <typename _KeyType, typename _PtrType> 43class OtherTreeNodeState { 44public: 45 using KeyType = _KeyType; 46 using PtrType = _PtrType; 47 48private: 49 friend struct OtherTreeTraits<OtherTreeNodeState<KeyType, PtrType>>; 50 WAVLTreeNodeState<PtrType> node_state_; 51 KeyType key_ = 0; 52}; 53 54template <typename PtrType> 55class WAVLTraits { 56public: 57 using KeyType = size_t; 58 using TestObjBaseType = KeyedTestObjBase<KeyType>; 59 60 using ContainerType = WAVLTree<KeyType, PtrType>; 61 using ContainableBaseClass = WAVLTreeContainable<PtrType>; 62 using ContainerStateType = WAVLTreeNodeState<PtrType>; 63 64 using OtherContainerStateType = OtherTreeNodeState<KeyType, PtrType>; 65 using OtherContainerTraits = OtherTreeTraits<OtherContainerStateType>; 66 using OtherContainerType = WAVLTree<KeyType, 67 PtrType, 68 OtherContainerTraits, 69 OtherContainerTraits>; 70}; 71 72// Generate all of the standard tests. 73DEFINE_TEST_OBJECTS(WAVL); 74using UMTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, Unmanaged); 75using UPTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, UniquePtr); 76using RPTE = DEFINE_TEST_THUNK(OrderedAssociative, WAVL, RefPtr); 77 78// WAVLBalanceTestObserver 79// 80// An implementation of a WAVLTree Observer which collects stats on the number 81// of balance operations (inserts, erases, rank promotions, rank demotions and 82// rotatations) which have taken place. It is used by the BalanceTest to verify 83// that... 84// 85// 1) The computation costs of rebalancing after insert and erase are amortized 86// constant and obey their specific worst-case constant bounds. 87// 2) The maximum depth bounds for trees with just insert operations, and with 88// both insert and erase operations, are obeyed. 89// 3) Sufficient code coverage has been achieved during testing (eg. all of the 90// rebalancing edge cases have been run over the length of the test). 91class WAVLBalanceTestObserver { 92public: 93 struct OpCounts { 94 OpCounts() { reset(); } 95 96 void reset() { 97 insert_ops_ = 0; 98 insert_promotes_ = 0; 99 insert_rotations_ = 0; 100 insert_double_rotations_ = 0; 101 erase_ops_ = 0; 102 erase_demotes_ = 0; 103 erase_rotations_ = 0; 104 erase_double_rotations_ = 0; 105 } 106 107 void accumulate(OpCounts& target) { 108 target.insert_ops_ += insert_ops_; 109 target.insert_promotes_ += insert_promotes_; 110 target.insert_rotations_ += insert_rotations_; 111 target.insert_double_rotations_ += insert_double_rotations_; 112 target.erase_ops_ += erase_ops_; 113 target.erase_demotes_ += erase_demotes_; 114 target.erase_rotations_ += erase_rotations_; 115 target.erase_double_rotations_ += erase_double_rotations_; 116 } 117 118 size_t insert_ops_; 119 size_t insert_promotes_; 120 size_t insert_rotations_; 121 size_t insert_double_rotations_; 122 123 size_t erase_ops_; 124 size_t erase_demotes_; 125 size_t erase_rotations_; 126 size_t erase_double_rotations_; 127 }; 128 129 static void ResetObserverOpCounts() { op_counts_.reset(); } 130 static void AccumulateObserverOpCounts(OpCounts& target) { op_counts_.accumulate(target); } 131 132 static void RecordInsert() { ++op_counts_.insert_ops_; } 133 static void RecordInsertPromote() { ++op_counts_.insert_promotes_; } 134 static void RecordInsertRotation() { ++op_counts_.insert_rotations_; } 135 static void RecordInsertDoubleRotation() { ++op_counts_.insert_double_rotations_; } 136 static void RecordErase() { ++op_counts_.erase_ops_; } 137 static void RecordEraseDemote() { ++op_counts_.erase_demotes_; } 138 static void RecordEraseRotation() { ++op_counts_.erase_rotations_; } 139 static void RecordEraseDoubleRotation() { ++op_counts_.erase_double_rotations_; } 140 141 template <typename TreeType> 142 static bool VerifyRankRule(const TreeType& tree, typename TreeType::RawPtrType node) { 143 BEGIN_TEST; 144 using NodeTraits = typename TreeType::NodeTraits; 145 using PtrTraits = typename TreeType::PtrTraits; 146 147 ASSERT_TRUE(PtrTraits::IsValid(node)); 148 149 // Check the rank rule. The rules for a WAVL tree are... 150 // 1) All rank differences are either 1 or 2 151 // 2) All leaf nodes have rank 0 (by implication, all rank 152 // differences are non-negative) 153 const auto& ns = NodeTraits::node_state(*node); 154 ASSERT_LE(0, ns.rank_, "All ranks must be non-negative."); 155 156 if (!PtrTraits::IsValid(ns.left_) && !PtrTraits::IsValid(ns.right_)) { 157 ASSERT_EQ(0, ns.rank_, "Leaf nodes must have rank 0!"); 158 } else { 159 if (PtrTraits::IsValid(ns.left_)) { 160 auto& left_ns = NodeTraits::node_state(*ns.left_); 161 auto delta = ns.rank_ - left_ns.rank_; 162 ASSERT_LE(1, delta, "Left hand rank difference not on range [1, 2]"); 163 ASSERT_GE(2, delta, "Left hand rank difference not on range [1, 2]"); 164 } 165 166 if (PtrTraits::IsValid(ns.right_)) { 167 auto& right_ns = NodeTraits::node_state(*ns.right_); 168 auto delta = ns.rank_ - right_ns.rank_; 169 ASSERT_LE(1, delta, "Right hand rank difference not on range [1, 2]"); 170 ASSERT_GE(2, delta, "Right hand rank difference not on range [1, 2]"); 171 } 172 } 173 174 END_TEST; 175 } 176 177 template <typename TreeType> 178 static bool VerifyBalance(const TreeType& tree, uint64_t depth) { 179 BEGIN_TEST; 180 181 // Compute the maximum expected depth. 182 uint64_t max_depth = 0; 183 if (tree.size()) { 184 // If we have performed erase operations, the max depth should be 185 // rounddown(2 * log_2(N)) + 1. 186 // 187 // If we have not performed any erases, then the max depth should be 188 // rounddown(log_phi(N)) + 1. We know that... 189 // 190 // phi = (1 + sqrt(5)) / 2 191 // log_phi(N) = log_2(N) / log_2(phi) 192 // 193 // Start by computing log_2(N), then scale by either 2.0, or 194 // (1/log_2(phi)). 195 constexpr double one_over_log2_phi = 196 1.4404200904125563642566021371749229729175567626953125; 197 double log2N = log2(static_cast<double>(tree.size())); 198 double scale = op_counts_.erase_ops_ ? 2.0 : one_over_log2_phi; 199 200 max_depth = static_cast<uint64_t>(log2N * scale) + 1; 201 } 202 203 size_t total_insert_rotations = op_counts_.insert_rotations_ 204 + op_counts_.insert_double_rotations_; 205 EXPECT_LE(op_counts_.insert_promotes_, 206 (3 * op_counts_.insert_ops_) + (2 * op_counts_.erase_ops_), 207 "#insert promotes must be <= (3 * #inserts) + (2 * #erases)"); 208 EXPECT_LE(total_insert_rotations, op_counts_.insert_ops_, 209 "#insert_rotations must be <= #inserts"); 210 211 size_t total_erase_rotations = op_counts_.erase_rotations_ 212 + op_counts_.erase_double_rotations_; 213 EXPECT_LE(op_counts_.erase_demotes_, op_counts_.erase_ops_, 214 "#erase demotes must be <= #erases"); 215 EXPECT_LE(total_erase_rotations, op_counts_.erase_ops_, 216 "#erase_rotations must be <= #erases"); 217 218 EXPECT_GE(max_depth, depth); 219 220 END_TEST; 221 } 222 223private: 224 static OpCounts op_counts_; 225}; 226 227// Static storage for the observer. 228WAVLBalanceTestObserver::OpCounts WAVLBalanceTestObserver::op_counts_; 229 230// Test objects during the balance test will be allocated as a block all at once 231// and cleaned up at the end of the test. Our test containers, however, are 232// containers of unique pointers to objects with a no-op delete. This allows 233// the containers to go out of scope with elements still in them (in case of a 234// REQUIRE failure) without triggering the container assert for destroying a 235// container of unmanaged pointer with elements still in it. 236class BalanceTestObj; 237 238using BalanceTestKeyType = uint64_t; 239using BalanceTestObjPtr = unique_ptr<BalanceTestObj>; 240using BalanceTestTree = WAVLTree<BalanceTestKeyType, 241 BalanceTestObjPtr, 242 DefaultKeyedObjectTraits<BalanceTestKeyType, BalanceTestObj>, 243 DefaultWAVLTreeTraits<BalanceTestObjPtr, int32_t>, 244 WAVLBalanceTestObserver>; 245 246class BalanceTestObj { 247public: 248 void Init(BalanceTestKeyType val) { 249 key_ = val; 250 erase_deck_ptr_ = this; 251 } 252 253 BalanceTestKeyType GetKey() const { return key_; } 254 BalanceTestObj* EraseDeckPtr() const { return erase_deck_ptr_; }; 255 256 void SwapEraseDeckPtr(BalanceTestObj& other) { 257 BalanceTestObj* tmp = erase_deck_ptr_; 258 erase_deck_ptr_ = other.erase_deck_ptr_; 259 other.erase_deck_ptr_ = tmp; 260 } 261 262 bool InContainer() const { return wavl_node_state_.InContainer(); } 263 264private: 265 friend DefaultWAVLTreeTraits<BalanceTestObjPtr, int32_t>; 266 267 static void operator delete(void* ptr) { 268 // Deliberate no-op 269 } 270 friend class fbl::unique_ptr<BalanceTestObj[]>; 271 friend class fbl::unique_ptr<BalanceTestObj>; 272 273 BalanceTestKeyType key_; 274 BalanceTestObj* erase_deck_ptr_; 275 WAVLTreeNodeState<BalanceTestObjPtr, int32_t> wavl_node_state_; 276}; 277 278static constexpr size_t kBalanceTestSize = 2048; 279 280static bool DoBalanceTestInsert(BalanceTestTree& tree, BalanceTestObj* ptr) { 281 BEGIN_TEST; 282 283 // The selected object should not be in the tree. 284 ASSERT_NONNULL(ptr); 285 ASSERT_FALSE(ptr->InContainer()); 286 287 // Put the object into the tree. Assert that it succeeds, then 288 // sanity check the tree. 289 ASSERT_TRUE(tree.insert_or_find(BalanceTestObjPtr(ptr))); 290 ASSERT_TRUE(WAVLTreeChecker::SanityCheck(tree)); 291 292 END_TEST; 293} 294 295static bool DoBalanceTestErase(BalanceTestTree& tree, BalanceTestObj* ptr) { 296 BEGIN_TEST; 297 298 // The selected object should still be in the tree. 299 ASSERT_NONNULL(ptr); 300 ASSERT_TRUE(ptr->InContainer()); 301 302 // Erase should find the object and transfer its pointer back to us. 303 // The object should no longer be in the tree. 304 BalanceTestObjPtr erased = tree.erase(ptr->GetKey()); 305 ASSERT_EQ(ptr, erased.get()); 306 ASSERT_FALSE(ptr->InContainer()); 307 308 // Run a full sanity check on the tree. Its depth should be 309 // consistent with a tree which has seen both inserts and erases. 310 ASSERT_TRUE(WAVLTreeChecker::SanityCheck(tree)); 311 312 END_TEST; 313} 314 315static void ShuffleEraseDeck(const unique_ptr<BalanceTestObj[]>& objects, 316 Lfsr<BalanceTestKeyType>& rng) { 317 // Note: shuffle algorithm is a Fisher-Yates (aka Knuth) shuffle. 318 static_assert(kBalanceTestSize > 0, "Test size must be positive!"); 319 for (size_t i = kBalanceTestSize - 1; i > 1; --i) { 320 size_t ndx = static_cast<size_t>(rng.GetNext()) % i; 321 if (ndx != i) 322 objects[i].SwapEraseDeckPtr(objects[ndx]); 323 } 324} 325 326static bool WAVLBalanceTest() { 327 BEGIN_TEST; 328 329 WAVLBalanceTestObserver::OpCounts op_counts; 330 331 // Declare these in a specific order (object pointer first) so that the tree 332 // has a chance to clean up before the memory backing the objects gets 333 // cleaned up. 334 unique_ptr<BalanceTestObj[]> objects; 335 BalanceTestTree tree; 336 337 // We will run this test 3 times with 3 different (constant) seeds. During 338 // the first run, we will insert all of the elements with ascending key 339 // order. During the second run, we will insert all of the keys with 340 // descending key order. During the final run, we will insert all of the 341 // keys in a random order. 342 Lfsr<BalanceTestKeyType> rng; 343 static const BalanceTestKeyType seeds[] = { 0xe87e1062fc1f4f80u, 344 0x03d6bffb124b4918u, 345 0x8f7d83e8d10b4765u }; 346 347 // Allocate the objects we will use for the test. 348 { 349 AllocChecker ac; 350 objects.reset(new (&ac) BalanceTestObj[kBalanceTestSize]); 351 ASSERT_TRUE(ac.check(), "Failed to allocate test objects!"); 352 } 353 354 for (size_t seed_ndx = 0; seed_ndx < fbl::count_of(seeds); ++seed_ndx) { 355 auto seed = seeds[seed_ndx]; 356 357 // Seed the RNG and reset the observer stats. 358 rng.SetCore(seed); 359 WAVLBalanceTestObserver::ResetObserverOpCounts(); 360 361 // Initialize each object with the proper key for this run. This places 362 // the object in the erase deck sequence at the same time. 363 switch (seed_ndx) { 364 case 0u: 365 for (size_t i = 0; i < kBalanceTestSize; ++i) 366 objects[i].Init(i); 367 break; 368 369 case 1u: 370 for (size_t i = 0; i < kBalanceTestSize; ++i) 371 objects[i].Init(kBalanceTestSize - i); 372 break; 373 374 default: 375 for (size_t i = 0; i < kBalanceTestSize; ++i) 376 objects[i].Init(rng.GetNext()); 377 break; 378 } 379 380 // Place each object into the tree, then perform a full sanity check on 381 // the tree. If anything goes wrong, just abort the test. If we keep 382 // going, we are just going to get an unmanageable amt of errors. 383 for (size_t i = 0; i < kBalanceTestSize; ++i) 384 ASSERT_TRUE(DoBalanceTestInsert(tree, &objects[i])); 385 386 // Shuffle the erase deck. 387 ShuffleEraseDeck(objects, rng); 388 389 // Erase half of the elements in the tree. 390 for (size_t i = 0; i < (kBalanceTestSize >> 1); ++i) 391 ASSERT_TRUE(DoBalanceTestErase(tree, objects[i].EraseDeckPtr())); 392 393 // Put the elements back so that we have inserted some elements into a 394 // non-empty tree which has seen erase operations. 395 for (size_t i = 0; i < (kBalanceTestSize >> 1); ++i) 396 ASSERT_TRUE(DoBalanceTestInsert(tree, objects[i].EraseDeckPtr())); 397 398 // Shuffle the erase deck again. 399 ShuffleEraseDeck(objects, rng); 400 401 // Now erase every element from the tree. 402 for (size_t i = 0; i < kBalanceTestSize; ++i) 403 ASSERT_TRUE(DoBalanceTestErase(tree, objects[i].EraseDeckPtr())); 404 405 ASSERT_EQ(0u, tree.size()); 406 407 WAVLBalanceTestObserver::AccumulateObserverOpCounts(op_counts); 408 } 409 410 // Finally, make sure that we have exercised all of the different re-balance 411 // cases. 412 EXPECT_LT(0u, op_counts.insert_ops_, "Insufficient test coverage!"); 413 EXPECT_LT(0u, op_counts.insert_promotes_, "Insufficient test coverage!"); 414 EXPECT_LT(0u, op_counts.insert_rotations_, "Insufficient test coverage!"); 415 EXPECT_LT(0u, op_counts.insert_double_rotations_, "Insufficient test coverage!"); 416 EXPECT_LT(0u, op_counts.erase_ops_, "Insufficient test coverage!"); 417 EXPECT_LT(0u, op_counts.erase_demotes_, "Insufficient test coverage!"); 418 EXPECT_LT(0u, op_counts.erase_rotations_, "Insufficient test coverage!"); 419 EXPECT_LT(0u, op_counts.erase_double_rotations_, "Insufficient test coverage!"); 420 421 END_TEST; 422} 423 424BEGIN_TEST_CASE(wavl_tree_tests) 425////////////////////////////////////////// 426// General container specific tests. 427////////////////////////////////////////// 428RUN_NAMED_TEST("Clear (unmanaged)", UMTE::ClearTest) 429RUN_NAMED_TEST("Clear (unique)", UPTE::ClearTest) 430RUN_NAMED_TEST("Clear (RefPtr)", RPTE::ClearTest) 431 432RUN_NAMED_TEST("ClearUnsafe (unmanaged)", UMTE::ClearUnsafeTest) 433#if TEST_WILL_NOT_COMPILE || 0 434RUN_NAMED_TEST("ClearUnsafe (unique)", UPTE::ClearUnsafeTest) 435RUN_NAMED_TEST("ClearUnsafe (RefPtr)", RPTE::ClearUnsafeTest) 436#endif 437 438RUN_NAMED_TEST("IsEmpty (unmanaged)", UMTE::IsEmptyTest) 439RUN_NAMED_TEST("IsEmpty (unique)", UPTE::IsEmptyTest) 440RUN_NAMED_TEST("IsEmpty (RefPtr)", RPTE::IsEmptyTest) 441 442RUN_NAMED_TEST("Iterate (unmanaged)", UMTE::IterateTest) 443RUN_NAMED_TEST("Iterate (unique)", UPTE::IterateTest) 444RUN_NAMED_TEST("Iterate (RefPtr)", RPTE::IterateTest) 445 446RUN_NAMED_TEST("IterErase (unmanaged)", UMTE::IterEraseTest) 447RUN_NAMED_TEST("IterErase (unique)", UPTE::IterEraseTest) 448RUN_NAMED_TEST("IterErase (RefPtr)", RPTE::IterEraseTest) 449 450RUN_NAMED_TEST("DirectErase (unmanaged)", UMTE::DirectEraseTest) 451#if TEST_WILL_NOT_COMPILE || 0 452RUN_NAMED_TEST("DirectErase (unique)", UPTE::DirectEraseTest) 453#endif 454RUN_NAMED_TEST("DirectErase (RefPtr)", RPTE::DirectEraseTest) 455 456RUN_NAMED_TEST("MakeIterator (unmanaged)", UMTE::MakeIteratorTest) 457#if TEST_WILL_NOT_COMPILE || 0 458RUN_NAMED_TEST("MakeIterator (unique)", UPTE::MakeIteratorTest) 459#endif 460RUN_NAMED_TEST("MakeIterator (RefPtr)", RPTE::MakeIteratorTest) 461 462RUN_NAMED_TEST("ReverseIterErase (unmanaged)", UMTE::ReverseIterEraseTest) 463RUN_NAMED_TEST("ReverseIterErase (unique)", UPTE::ReverseIterEraseTest) 464RUN_NAMED_TEST("ReverseIterErase (RefPtr)", RPTE::ReverseIterEraseTest) 465 466RUN_NAMED_TEST("ReverseIterate (unmanaged)", UMTE::ReverseIterateTest) 467RUN_NAMED_TEST("ReverseIterate (unique)", UPTE::ReverseIterateTest) 468RUN_NAMED_TEST("ReverseIterate (RefPtr)", RPTE::ReverseIterateTest) 469 470RUN_NAMED_TEST("Swap (unmanaged)", UMTE::SwapTest) 471RUN_NAMED_TEST("Swap (unique)", UPTE::SwapTest) 472RUN_NAMED_TEST("Swap (RefPtr)", RPTE::SwapTest) 473 474RUN_NAMED_TEST("Rvalue Ops (unmanaged)", UMTE::RvalueOpsTest) 475RUN_NAMED_TEST("Rvalue Ops (unique)", UPTE::RvalueOpsTest) 476RUN_NAMED_TEST("Rvalue Ops (RefPtr)", RPTE::RvalueOpsTest) 477 478RUN_NAMED_TEST("Scope (unique)", UPTE::ScopeTest) 479RUN_NAMED_TEST("Scope (RefPtr)", RPTE::ScopeTest) 480 481RUN_NAMED_TEST("TwoContainer (unmanaged)", UMTE::TwoContainerTest) 482#if TEST_WILL_NOT_COMPILE || 0 483RUN_NAMED_TEST("TwoContainer (unique)", UPTE::TwoContainerTest) 484#endif 485RUN_NAMED_TEST("TwoContainer (RefPtr)", RPTE::TwoContainerTest) 486 487RUN_NAMED_TEST("IterCopyPointer (unmanaged)", UMTE::IterCopyPointerTest) 488#if TEST_WILL_NOT_COMPILE || 0 489RUN_NAMED_TEST("IterCopyPointer (unique)", UPTE::IterCopyPointerTest) 490#endif 491RUN_NAMED_TEST("IterCopyPointer (RefPtr)", RPTE::IterCopyPointerTest) 492 493RUN_NAMED_TEST("EraseIf (unmanaged)", UMTE::EraseIfTest) 494RUN_NAMED_TEST("EraseIf (unique)", UPTE::EraseIfTest) 495RUN_NAMED_TEST("EraseIf (RefPtr)", RPTE::EraseIfTest) 496 497RUN_NAMED_TEST("FindIf (unmanaged)", UMTE::FindIfTest) 498RUN_NAMED_TEST("FindIf (unique)", UPTE::FindIfTest) 499RUN_NAMED_TEST("FindIf (RefPtr)", RPTE::FindIfTest) 500 501////////////////////////////////////////// 502// Associative container specific tests. 503////////////////////////////////////////// 504RUN_NAMED_TEST("InsertByKey (unmanaged)", UMTE::InsertByKeyTest) 505RUN_NAMED_TEST("InsertByKey (unique)", UPTE::InsertByKeyTest) 506RUN_NAMED_TEST("InsertByKey (RefPtr)", RPTE::InsertByKeyTest) 507 508RUN_NAMED_TEST("FindByKey (unmanaged)", UMTE::FindByKeyTest) 509RUN_NAMED_TEST("FindByKey (unique)", UPTE::FindByKeyTest) 510RUN_NAMED_TEST("FindByKey (RefPtr)", RPTE::FindByKeyTest) 511 512RUN_NAMED_TEST("EraseByKey (unmanaged)", UMTE::EraseByKeyTest) 513RUN_NAMED_TEST("EraseByKey (unique)", UPTE::EraseByKeyTest) 514RUN_NAMED_TEST("EraseByKey (RefPtr)", RPTE::EraseByKeyTest) 515 516RUN_NAMED_TEST("InsertOrFind (unmanaged)", UMTE::InsertOrFindTest) 517RUN_NAMED_TEST("InsertOrFind (unique)", UPTE::InsertOrFindTest) 518RUN_NAMED_TEST("InsertOrFind (RefPtr)", RPTE::InsertOrFindTest) 519 520RUN_NAMED_TEST("InsertOrReplace (unmanaged)", UMTE::InsertOrReplaceTest) 521RUN_NAMED_TEST("InsertOrReplace (unique)", UPTE::InsertOrReplaceTest) 522RUN_NAMED_TEST("InsertOrReplace (RefPtr)", RPTE::InsertOrReplaceTest) 523 524//////////////////////////////////////////////// 525// OrderedAssociative container specific tests. 526//////////////////////////////////////////////// 527RUN_NAMED_TEST("OrderedIter (unmanaged)", UMTE::OrderedIterTest) 528RUN_NAMED_TEST("OrderedIter (unique)", UPTE::OrderedIterTest) 529RUN_NAMED_TEST("OrderedIter (RefPtr)", RPTE::OrderedIterTest) 530 531RUN_NAMED_TEST("OrderedReverseIter (unmanaged)", UMTE::OrderedReverseIterTest) 532RUN_NAMED_TEST("OrderedReverseIter (unique)", UPTE::OrderedReverseIterTest) 533RUN_NAMED_TEST("OrderedReverseIter (RefPtr)", RPTE::OrderedReverseIterTest) 534 535RUN_NAMED_TEST("UpperBound (unmanaged)", UMTE::UpperBoundTest) 536RUN_NAMED_TEST("UpperBound (unique)", UPTE::UpperBoundTest) 537RUN_NAMED_TEST("UpperBound (RefPtr)", RPTE::UpperBoundTest) 538 539RUN_NAMED_TEST("LowerBound (unmanaged)", UMTE::LowerBoundTest) 540RUN_NAMED_TEST("LowerBound (unique)", UPTE::LowerBoundTest) 541RUN_NAMED_TEST("LowerBound (RefPtr)", RPTE::LowerBoundTest) 542 543//////////////////////////// 544// WAVLTree specific tests. 545//////////////////////////// 546// ZX-2230: This can take more than 20 seconds in CI, so mark it medium. 547RUN_NAMED_TEST_MEDIUM("BalanceTest", WAVLBalanceTest) 548 549END_TEST_CASE(wavl_tree_tests); 550 551} // namespace intrusive_containers 552} // namespace tests 553} // namespace fbl 554