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