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_double_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 12 namespace fbl { 13 namespace tests { 14 namespace intrusive_containers { 15 16 using OtherKeyType = uint16_t; 17 using OtherHashType = uint32_t; 18 static constexpr OtherHashType kOtherNumBuckets = 23; 19 20 template <typename PtrType> 21 struct OtherHashTraits { 22 using ObjType = typename ::fbl::internal::ContainerPtrTraits<PtrType>::ValueType; 23 using BucketStateType = DoublyLinkedListNodeState<PtrType>; 24 25 // Linked List Traits node_statefbl::tests::intrusive_containers::OtherHashTraits26 static BucketStateType& node_state(ObjType& obj) { 27 return obj.other_container_state_.bucket_state_; 28 } 29 30 // Keyed Object Traits GetKeyfbl::tests::intrusive_containers::OtherHashTraits31 static OtherKeyType GetKey(const ObjType& obj) { 32 return obj.other_container_state_.key_; 33 } 34 LessThanfbl::tests::intrusive_containers::OtherHashTraits35 static bool LessThan(const OtherKeyType& key1, const OtherKeyType& key2) { 36 return key1 < key2; 37 } 38 EqualTofbl::tests::intrusive_containers::OtherHashTraits39 static bool EqualTo(const OtherKeyType& key1, const OtherKeyType& key2) { 40 return key1 == key2; 41 } 42 43 // Hash Traits GetHashfbl::tests::intrusive_containers::OtherHashTraits44 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. SetKeyfbl::tests::intrusive_containers::OtherHashTraits50 static void SetKey(ObjType& obj, OtherKeyType key) { 51 obj.other_container_state_.key_ = key; 52 } 53 }; 54 55 template <typename PtrType> 56 struct OtherHashState { 57 private: 58 friend struct OtherHashTraits<PtrType>; 59 OtherKeyType key_; 60 typename OtherHashTraits<PtrType>::BucketStateType bucket_state_; 61 }; 62 63 template <typename PtrType> 64 class HTDLLTraits { 65 public: 66 using ObjType = typename ::fbl::internal::ContainerPtrTraits<PtrType>::ValueType; 67 68 using ContainerType = HashTable<size_t, PtrType, DoublyLinkedList<PtrType>>; 69 using ContainableBaseClass = DoublyLinkedListable<PtrType>; 70 using ContainerStateType = DoublyLinkedListNodeState<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 = DoublyLinkedList<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 90 DEFINE_TEST_OBJECTS(HTDLL); 91 using UMTE = DEFINE_TEST_THUNK(Associative, HTDLL, Unmanaged); 92 using UPTE = DEFINE_TEST_THUNK(Associative, HTDLL, UniquePtr); 93 using SUPDDTE = DEFINE_TEST_THUNK(Associative, HTDLL, StdUniquePtrDefaultDeleter); 94 using SUPCDTE = DEFINE_TEST_THUNK(Associative, HTDLL, StdUniquePtrCustomDeleter); 95 using RPTE = DEFINE_TEST_THUNK(Associative, HTDLL, RefPtr); 96 97 BEGIN_TEST_CASE(hashtable_dll_tests) 98 ////////////////////////////////////////// 99 // General container specific tests. 100 ////////////////////////////////////////// 101 RUN_NAMED_TEST("Clear (unmanaged)", UMTE::ClearTest) 102 RUN_NAMED_TEST("Clear (unique)", UPTE::ClearTest) 103 RUN_NAMED_TEST("Clear (std::uptr)", SUPDDTE::ClearTest) 104 RUN_NAMED_TEST("Clear (std::uptr<Del>)", SUPCDTE::ClearTest) 105 RUN_NAMED_TEST("Clear (RefPtr)", RPTE::ClearTest) 106 107 RUN_NAMED_TEST("ClearUnsafe (unmanaged)", UMTE::ClearUnsafeTest) 108 #if TEST_WILL_NOT_COMPILE || 0 109 RUN_NAMED_TEST("ClearUnsafe (unique)", UPTE::ClearUnsafeTest) 110 RUN_NAMED_TEST("ClearUnsafe (std::uptr)", SUPDDTE::ClearUnsafeTest) 111 RUN_NAMED_TEST("ClearUnsafe (std::uptr<Del>)", SUPCDTE::ClearUnsafeTest) 112 RUN_NAMED_TEST("ClearUnsafe (RefPtr)", RPTE::ClearUnsafeTest) 113 #endif 114 115 RUN_NAMED_TEST("IsEmpty (unmanaged)", UMTE::IsEmptyTest) 116 RUN_NAMED_TEST("IsEmpty (unique)", UPTE::IsEmptyTest) 117 RUN_NAMED_TEST("IsEmpty (std::uptr)", SUPDDTE::IsEmptyTest) 118 RUN_NAMED_TEST("IsEmpty (std::uptr<Del>)", SUPCDTE::IsEmptyTest) 119 RUN_NAMED_TEST("IsEmpty (RefPtr)", RPTE::IsEmptyTest) 120 121 RUN_NAMED_TEST("Iterate (unmanaged)", UMTE::IterateTest) 122 RUN_NAMED_TEST("Iterate (unique)", UPTE::IterateTest) 123 RUN_NAMED_TEST("Iterate (std::uptr)", SUPDDTE::IterateTest) 124 RUN_NAMED_TEST("Iterate (std::uptr<Del>)", SUPCDTE::IterateTest) 125 RUN_NAMED_TEST("Iterate (RefPtr)", RPTE::IterateTest) 126 127 RUN_NAMED_TEST("IterErase (unmanaged)", UMTE::IterEraseTest) 128 RUN_NAMED_TEST("IterErase (unique)", UPTE::IterEraseTest) 129 RUN_NAMED_TEST("IterErase (std::uptr)", SUPDDTE::IterEraseTest) 130 RUN_NAMED_TEST("IterErase (std::uptr<Del>)", SUPCDTE::IterEraseTest) 131 RUN_NAMED_TEST("IterErase (RefPtr)", RPTE::IterEraseTest) 132 133 RUN_NAMED_TEST("DirectErase (unmanaged)", UMTE::DirectEraseTest) 134 #if TEST_WILL_NOT_COMPILE || 0 135 RUN_NAMED_TEST("DirectErase (unique)", UPTE::DirectEraseTest) 136 RUN_NAMED_TEST("DirectErase (std::uptr)", SUPDDTE::DirectEraseTest) 137 RUN_NAMED_TEST("DirectErase (std::uptr<Del>)", SUPCDTE::DirectEraseTest) 138 #endif 139 RUN_NAMED_TEST("DirectErase (RefPtr)", RPTE::DirectEraseTest) 140 141 RUN_NAMED_TEST("MakeIterator (unmanaged)", UMTE::MakeIteratorTest) 142 #if TEST_WILL_NOT_COMPILE || 0 143 RUN_NAMED_TEST("MakeIterator (unique)", UPTE::MakeIteratorTest) 144 RUN_NAMED_TEST("MakeIterator (std::uptr)", SUPDDTE::MakeIteratorTest) 145 RUN_NAMED_TEST("MakeIterator (std::uptr<Del>)", SUPCDTE::MakeIteratorTest) 146 #endif 147 RUN_NAMED_TEST("MakeIterator (RefPtr)", RPTE::MakeIteratorTest) 148 149 RUN_NAMED_TEST("ReverseIterErase (unmanaged)", UMTE::ReverseIterEraseTest) 150 RUN_NAMED_TEST("ReverseIterErase (unique)", UPTE::ReverseIterEraseTest) 151 RUN_NAMED_TEST("ReverseIterErase (std::uptr)", SUPDDTE::ReverseIterEraseTest) 152 RUN_NAMED_TEST("ReverseIterErase (std::uptr<Del>)", SUPCDTE::ReverseIterEraseTest) 153 RUN_NAMED_TEST("ReverseIterErase (RefPtr)", RPTE::ReverseIterEraseTest) 154 155 RUN_NAMED_TEST("ReverseIterate (unmanaged)", UMTE::ReverseIterateTest) 156 RUN_NAMED_TEST("ReverseIterate (unique)", UPTE::ReverseIterateTest) 157 RUN_NAMED_TEST("ReverseIterate (std::uptr)", SUPDDTE::ReverseIterateTest) 158 RUN_NAMED_TEST("ReverseIterate (std::uptr<Del>)", SUPCDTE::ReverseIterateTest) 159 RUN_NAMED_TEST("ReverseIterate (RefPtr)", RPTE::ReverseIterateTest) 160 161 // Hash tables do not support swapping or Rvalue operations (Assignment or 162 // construction) as doing so would be an O(n) operation (With 'n' == to the 163 // number of buckets in the hashtable) 164 #if TEST_WILL_NOT_COMPILE || 0 165 RUN_NAMED_TEST("Swap (unmanaged)", UMTE::SwapTest) 166 RUN_NAMED_TEST("Swap (unique)", UPTE::SwapTest) 167 RUN_NAMED_TEST("Swap (std::uptr)", SUPDDTE::SwapTest) 168 RUN_NAMED_TEST("Swap (std::uptr<Del>)", SUPCDTE::SwapTest) 169 RUN_NAMED_TEST("Swap (RefPtr)", RPTE::SwapTest) 170 171 RUN_NAMED_TEST("Rvalue Ops (unmanaged)", UMTE::RvalueOpsTest) 172 RUN_NAMED_TEST("Rvalue Ops (unique)", UPTE::RvalueOpsTest) 173 RUN_NAMED_TEST("Rvalue Ops (std::uptr)", SUPDDTE::RvalueOpsTest) 174 RUN_NAMED_TEST("Rvalue Ops (std::uptr<Del>)", SUPCDTE::RvalueOpsTest) 175 RUN_NAMED_TEST("Rvalue Ops (RefPtr)", RPTE::RvalueOpsTest) 176 #endif 177 178 RUN_NAMED_TEST("Scope (unique)", UPTE::ScopeTest) 179 RUN_NAMED_TEST("Scope (std::uptr)", SUPDDTE::ScopeTest) 180 RUN_NAMED_TEST("Scope (std::uptr<Del>)", SUPCDTE::ScopeTest) 181 RUN_NAMED_TEST("Scope (RefPtr)", RPTE::ScopeTest) 182 183 RUN_NAMED_TEST("TwoContainer (unmanaged)", UMTE::TwoContainerTest) 184 #if TEST_WILL_NOT_COMPILE || 0 185 RUN_NAMED_TEST("TwoContainer (unique)", UPTE::TwoContainerTest) 186 RUN_NAMED_TEST("TwoContainer (std::uptr)", SUPDDTE::TwoContainerTest) 187 RUN_NAMED_TEST("TwoContainer (std::uptr<Del>)", SUPCDTE::TwoContainerTest) 188 #endif 189 RUN_NAMED_TEST("TwoContainer (RefPtr)", RPTE::TwoContainerTest) 190 191 RUN_NAMED_TEST("IterCopyPointer (unmanaged)", UMTE::IterCopyPointerTest) 192 #if TEST_WILL_NOT_COMPILE || 0 193 RUN_NAMED_TEST("IterCopyPointer (unique)", UPTE::IterCopyPointerTest) 194 RUN_NAMED_TEST("IterCopyPointer (std::uptr)", SUPDDTE::IterCopyPointerTest) 195 RUN_NAMED_TEST("IterCopyPointer (std::uptr<Del>)", SUPCDTE::IterCopyPointerTest) 196 #endif 197 RUN_NAMED_TEST("IterCopyPointer (RefPtr)", RPTE::IterCopyPointerTest) 198 199 RUN_NAMED_TEST("EraseIf (unmanaged)", UMTE::EraseIfTest) 200 RUN_NAMED_TEST("EraseIf (unique)", UPTE::EraseIfTest) 201 RUN_NAMED_TEST("EraseIf (std::uptr)", SUPDDTE::EraseIfTest) 202 RUN_NAMED_TEST("EraseIf (std::uptr<Del>)", SUPCDTE::EraseIfTest) 203 RUN_NAMED_TEST("EraseIf (RefPtr)", RPTE::EraseIfTest) 204 205 RUN_NAMED_TEST("FindIf (unmanaged)", UMTE::FindIfTest) 206 RUN_NAMED_TEST("FindIf (unique)", UPTE::FindIfTest) 207 RUN_NAMED_TEST("FindIf (std::uptr)", SUPDDTE::FindIfTest) 208 RUN_NAMED_TEST("FindIf (std::uptr<Del>)", SUPCDTE::FindIfTest) 209 RUN_NAMED_TEST("FindIf (RefPtr)", RPTE::FindIfTest) 210 211 ////////////////////////////////////////// 212 // Associative container specific tests. 213 ////////////////////////////////////////// 214 RUN_NAMED_TEST("InsertByKey (unmanaged)", UMTE::InsertByKeyTest) 215 RUN_NAMED_TEST("InsertByKey (unique)", UPTE::InsertByKeyTest) 216 RUN_NAMED_TEST("InsertByKey (std::uptr)", SUPDDTE::InsertByKeyTest) 217 RUN_NAMED_TEST("InsertByKey (std::uptr<Del>)", SUPCDTE::InsertByKeyTest) 218 RUN_NAMED_TEST("InsertByKey (RefPtr)", RPTE::InsertByKeyTest) 219 220 RUN_NAMED_TEST("FindByKey (unmanaged)", UMTE::FindByKeyTest) 221 RUN_NAMED_TEST("FindByKey (unique)", UPTE::FindByKeyTest) 222 RUN_NAMED_TEST("FindByKey (std::uptr)", SUPDDTE::FindByKeyTest) 223 RUN_NAMED_TEST("FindByKey (std::uptr<Del>)", SUPCDTE::FindByKeyTest) 224 RUN_NAMED_TEST("FindByKey (RefPtr)", RPTE::FindByKeyTest) 225 226 RUN_NAMED_TEST("EraseByKey (unmanaged)", UMTE::EraseByKeyTest) 227 RUN_NAMED_TEST("EraseByKey (unique)", UPTE::EraseByKeyTest) 228 RUN_NAMED_TEST("EraseByKey (std::uptr)", SUPDDTE::EraseByKeyTest) 229 RUN_NAMED_TEST("EraseByKey (std::uptr<Del>)", SUPCDTE::EraseByKeyTest) 230 RUN_NAMED_TEST("EraseByKey (RefPtr)", RPTE::EraseByKeyTest) 231 232 RUN_NAMED_TEST("InsertOrFind (unmanaged)", UMTE::InsertOrFindTest) 233 RUN_NAMED_TEST("InsertOrFind (unique)", UPTE::InsertOrFindTest) 234 RUN_NAMED_TEST("InsertOrFind (std::uptr)", SUPDDTE::InsertOrFindTest) 235 RUN_NAMED_TEST("InsertOrFind (std::uptr<Del>)", SUPCDTE::InsertOrFindTest) 236 RUN_NAMED_TEST("InsertOrFind (RefPtr)", RPTE::InsertOrFindTest) 237 238 RUN_NAMED_TEST("InsertOrReplace (unmanaged)", UMTE::InsertOrReplaceTest) 239 RUN_NAMED_TEST("InsertOrReplace (unique)", UPTE::InsertOrReplaceTest) 240 RUN_NAMED_TEST("InsertOrReplace (std::uptr)", SUPDDTE::InsertOrReplaceTest) 241 RUN_NAMED_TEST("InsertOrReplace (std::uptr<Del>)", SUPCDTE::InsertOrReplaceTest) 242 RUN_NAMED_TEST("InsertOrReplace (RefPtr)", RPTE::InsertOrReplaceTest) 243 END_TEST_CASE(hashtable_dll_tests); 244 245 } // namespace intrusive_containers 246 } // namespace tests 247 } // namespace fbl 248