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 <unittest/unittest.h> 6#include <fbl/intrusive_single_list.h> 7#include <fbl/intrusive_hash_table.h> 8#include <fbl/tests/intrusive_containers/associative_container_test_environment.h> 9#include <fbl/tests/intrusive_containers/intrusive_hash_table_checker.h> 10#include <fbl/tests/intrusive_containers/test_thunks.h> 11 12namespace fbl { 13namespace tests { 14namespace intrusive_containers { 15 16using OtherKeyType = uint16_t; 17using OtherHashType = uint32_t; 18static constexpr OtherHashType kOtherNumBuckets = 23; 19 20template <typename PtrType> 21struct OtherHashTraits { 22 using ObjType = typename ::fbl::internal::ContainerPtrTraits<PtrType>::ValueType; 23 using BucketStateType = SinglyLinkedListNodeState<PtrType>; 24 25 // Linked List Traits 26 static BucketStateType& node_state(ObjType& obj) { 27 return obj.other_container_state_.bucket_state_; 28 } 29 30 // Keyed Object Traits 31 static OtherKeyType GetKey(const ObjType& obj) { 32 return obj.other_container_state_.key_; 33 } 34 35 static bool LessThan(const OtherKeyType& key1, const OtherKeyType& key2) { 36 return key1 < key2; 37 } 38 39 static bool EqualTo(const OtherKeyType& key1, const OtherKeyType& key2) { 40 return key1 == key2; 41 } 42 43 // Hash Traits 44 static OtherHashType GetHash(const OtherKeyType& key) { 45 return static_cast<OtherHashType>((key * 0xaee58187) % kOtherNumBuckets); 46 } 47 48 // Set key is a trait which is only used by the tests, not by the containers 49 // themselves. 50 static void SetKey(ObjType& obj, OtherKeyType key) { 51 obj.other_container_state_.key_ = key; 52 } 53}; 54 55template <typename PtrType> 56struct OtherHashState { 57private: 58 friend struct OtherHashTraits<PtrType>; 59 OtherKeyType key_; 60 typename OtherHashTraits<PtrType>::BucketStateType bucket_state_; 61}; 62 63template <typename PtrType> 64class HTSLLTraits { 65public: 66 using ObjType = typename ::fbl::internal::ContainerPtrTraits<PtrType>::ValueType; 67 68 using ContainerType = HashTable<size_t, PtrType>; 69 using ContainableBaseClass = SinglyLinkedListable<PtrType>; 70 using ContainerStateType = SinglyLinkedListNodeState<PtrType>; 71 using KeyType = typename ContainerType::KeyType; 72 using HashType = typename ContainerType::HashType; 73 74 using OtherContainerTraits = OtherHashTraits<PtrType>; 75 using OtherContainerStateType = OtherHashState<PtrType>; 76 using OtherBucketType = SinglyLinkedList<PtrType, OtherContainerTraits>; 77 using OtherContainerType = HashTable<OtherKeyType, 78 PtrType, 79 OtherBucketType, 80 OtherHashType, 81 kOtherNumBuckets, 82 OtherContainerTraits, 83 OtherContainerTraits>; 84 85 using TestObjBaseType = HashedTestObjBase<typename ContainerType::KeyType, 86 typename ContainerType::HashType, 87 ContainerType::kNumBuckets>; 88}; 89 90DEFINE_TEST_OBJECTS(HTSLL); 91using UMTE = DEFINE_TEST_THUNK(Associative, HTSLL, Unmanaged); 92using UPTE = DEFINE_TEST_THUNK(Associative, HTSLL, UniquePtr); 93using RPTE = DEFINE_TEST_THUNK(Associative, HTSLL, RefPtr); 94 95BEGIN_TEST_CASE(hashtable_sll_tests) 96////////////////////////////////////////// 97// General container specific tests. 98////////////////////////////////////////// 99RUN_NAMED_TEST("Clear (unmanaged)", UMTE::ClearTest) 100RUN_NAMED_TEST("Clear (unique)", UPTE::ClearTest) 101RUN_NAMED_TEST("Clear (RefPtr)", RPTE::ClearTest) 102 103RUN_NAMED_TEST("ClearUnsafe (unmanaged)", UMTE::ClearUnsafeTest) 104#if TEST_WILL_NOT_COMPILE || 0 105RUN_NAMED_TEST("ClearUnsafe (unique)", UPTE::ClearUnsafeTest) 106RUN_NAMED_TEST("ClearUnsafe (RefPtr)", RPTE::ClearUnsafeTest) 107#endif 108 109RUN_NAMED_TEST("IsEmpty (unmanaged)", UMTE::IsEmptyTest) 110RUN_NAMED_TEST("IsEmpty (unique)", UPTE::IsEmptyTest) 111RUN_NAMED_TEST("IsEmpty (RefPtr)", RPTE::IsEmptyTest) 112 113RUN_NAMED_TEST("Iterate (unmanaged)", UMTE::IterateTest) 114RUN_NAMED_TEST("Iterate (unique)", UPTE::IterateTest) 115RUN_NAMED_TEST("Iterate (RefPtr)", RPTE::IterateTest) 116 117// Hashtables with singly linked list bucket can perform direct 118// iterator/reference erase operations, but the operations will be O(n) 119RUN_NAMED_TEST("IterErase (unmanaged)", UMTE::IterEraseTest) 120RUN_NAMED_TEST("IterErase (unique)", UPTE::IterEraseTest) 121RUN_NAMED_TEST("IterErase (RefPtr)", RPTE::IterEraseTest) 122 123RUN_NAMED_TEST("DirectErase (unmanaged)", UMTE::DirectEraseTest) 124#if TEST_WILL_NOT_COMPILE || 0 125RUN_NAMED_TEST("DirectErase (unique)", UPTE::DirectEraseTest) 126#endif 127RUN_NAMED_TEST("DirectErase (RefPtr)", RPTE::DirectEraseTest) 128 129RUN_NAMED_TEST("MakeIterator (unmanaged)", UMTE::MakeIteratorTest) 130#if TEST_WILL_NOT_COMPILE || 0 131RUN_NAMED_TEST("MakeIterator (unique)", UPTE::MakeIteratorTest) 132#endif 133RUN_NAMED_TEST("MakeIterator (RefPtr)", RPTE::MakeIteratorTest) 134 135// HashTables with SinglyLinkedList buckets cannot iterate backwards (because 136// their buckets cannot iterate backwards) 137#if TEST_WILL_NOT_COMPILE || 0 138RUN_NAMED_TEST("ReverseIterErase (unmanaged)", UMTE::ReverseIterEraseTest) 139RUN_NAMED_TEST("ReverseIterErase (unique)", UPTE::ReverseIterEraseTest) 140RUN_NAMED_TEST("ReverseIterErase (RefPtr)", RPTE::ReverseIterEraseTest) 141 142RUN_NAMED_TEST("ReverseIterate (unmanaged)", UMTE::ReverseIterateTest) 143RUN_NAMED_TEST("ReverseIterate (unique)", UPTE::ReverseIterateTest) 144RUN_NAMED_TEST("ReverseIterate (RefPtr)", RPTE::ReverseIterateTest) 145#endif 146 147// Hash tables do not support swapping or Rvalue operations (Assignment or 148// construction) as doing so would be an O(n) operation (With 'n' == to the 149// number of buckets in the hashtable) 150#if TEST_WILL_NOT_COMPILE || 0 151RUN_NAMED_TEST("Swap (unmanaged)", UMTE::SwapTest) 152RUN_NAMED_TEST("Swap (unique)", UPTE::SwapTest) 153RUN_NAMED_TEST("Swap (RefPtr)", RPTE::SwapTest) 154 155RUN_NAMED_TEST("Rvalue Ops (unmanaged)", UMTE::RvalueOpsTest) 156RUN_NAMED_TEST("Rvalue Ops (unique)", UPTE::RvalueOpsTest) 157RUN_NAMED_TEST("Rvalue Ops (RefPtr)", RPTE::RvalueOpsTest) 158#endif 159 160RUN_NAMED_TEST("Scope (unique)", UPTE::ScopeTest) 161RUN_NAMED_TEST("Scope (RefPtr)", RPTE::ScopeTest) 162 163RUN_NAMED_TEST("TwoContainer (unmanaged)", UMTE::TwoContainerTest) 164#if TEST_WILL_NOT_COMPILE || 0 165RUN_NAMED_TEST("TwoContainer (unique)", UPTE::TwoContainerTest) 166#endif 167RUN_NAMED_TEST("TwoContainer (RefPtr)", RPTE::TwoContainerTest) 168 169RUN_NAMED_TEST("IterCopyPointer (unmanaged)", UMTE::IterCopyPointerTest) 170#if TEST_WILL_NOT_COMPILE || 0 171RUN_NAMED_TEST("IterCopyPointer (unique)", UPTE::IterCopyPointerTest) 172#endif 173RUN_NAMED_TEST("IterCopyPointer (RefPtr)", RPTE::IterCopyPointerTest) 174 175RUN_NAMED_TEST("EraseIf (unmanaged)", UMTE::EraseIfTest) 176RUN_NAMED_TEST("EraseIf (unique)", UPTE::EraseIfTest) 177RUN_NAMED_TEST("EraseIf (RefPtr)", RPTE::EraseIfTest) 178 179RUN_NAMED_TEST("FindIf (unmanaged)", UMTE::FindIfTest) 180RUN_NAMED_TEST("FindIf (unique)", UPTE::FindIfTest) 181RUN_NAMED_TEST("FindIf (RefPtr)", RPTE::FindIfTest) 182 183////////////////////////////////////////// 184// Associative container specific tests. 185////////////////////////////////////////// 186RUN_NAMED_TEST("InsertByKey (unmanaged)", UMTE::InsertByKeyTest) 187RUN_NAMED_TEST("InsertByKey (unique)", UPTE::InsertByKeyTest) 188RUN_NAMED_TEST("InsertByKey (RefPtr)", RPTE::InsertByKeyTest) 189 190RUN_NAMED_TEST("FindByKey (unmanaged)", UMTE::FindByKeyTest) 191RUN_NAMED_TEST("FindByKey (unique)", UPTE::FindByKeyTest) 192RUN_NAMED_TEST("FindByKey (RefPtr)", RPTE::FindByKeyTest) 193 194RUN_NAMED_TEST("EraseByKey (unmanaged)", UMTE::EraseByKeyTest) 195RUN_NAMED_TEST("EraseByKey (unique)", UPTE::EraseByKeyTest) 196RUN_NAMED_TEST("EraseByKey (RefPtr)", RPTE::EraseByKeyTest) 197 198RUN_NAMED_TEST("InsertOrFind (unmanaged)", UMTE::InsertOrFindTest) 199RUN_NAMED_TEST("InsertOrFind (unique)", UPTE::InsertOrFindTest) 200RUN_NAMED_TEST("InsertOrFind (RefPtr)", RPTE::InsertOrFindTest) 201 202RUN_NAMED_TEST("InsertOrReplace (unmanaged)", UMTE::InsertOrReplaceTest) 203RUN_NAMED_TEST("InsertOrReplace (unique)", UPTE::InsertOrReplaceTest) 204RUN_NAMED_TEST("InsertOrReplace (RefPtr)", RPTE::InsertOrReplaceTest) 205END_TEST_CASE(hashtable_sll_tests); 206 207} // namespace intrusive_containers 208} // namespace tests 209} // namespace fbl 210