1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/container/internal/hash_function_defaults.h"
16
17 #include <functional>
18 #include <type_traits>
19 #include <utility>
20
21 #include "gtest/gtest.h"
22 #include "absl/strings/string_view.h"
23
24 namespace absl {
25 ABSL_NAMESPACE_BEGIN
26 namespace container_internal {
27 namespace {
28
29 using ::testing::Types;
30
TEST(Eq,Int32)31 TEST(Eq, Int32) {
32 hash_default_eq<int32_t> eq;
33 EXPECT_TRUE(eq(1, 1u));
34 EXPECT_TRUE(eq(1, char{1}));
35 EXPECT_TRUE(eq(1, true));
36 EXPECT_TRUE(eq(1, double{1.1}));
37 EXPECT_FALSE(eq(1, char{2}));
38 EXPECT_FALSE(eq(1, 2u));
39 EXPECT_FALSE(eq(1, false));
40 EXPECT_FALSE(eq(1, 2.));
41 }
42
TEST(Hash,Int32)43 TEST(Hash, Int32) {
44 hash_default_hash<int32_t> hash;
45 auto h = hash(1);
46 EXPECT_EQ(h, hash(1u));
47 EXPECT_EQ(h, hash(char{1}));
48 EXPECT_EQ(h, hash(true));
49 EXPECT_EQ(h, hash(double{1.1}));
50 EXPECT_NE(h, hash(2u));
51 EXPECT_NE(h, hash(char{2}));
52 EXPECT_NE(h, hash(false));
53 EXPECT_NE(h, hash(2.));
54 }
55
56 enum class MyEnum { A, B, C, D };
57
TEST(Eq,Enum)58 TEST(Eq, Enum) {
59 hash_default_eq<MyEnum> eq;
60 EXPECT_TRUE(eq(MyEnum::A, MyEnum::A));
61 EXPECT_FALSE(eq(MyEnum::A, MyEnum::B));
62 }
63
TEST(Hash,Enum)64 TEST(Hash, Enum) {
65 hash_default_hash<MyEnum> hash;
66
67 for (MyEnum e : {MyEnum::A, MyEnum::B, MyEnum::C}) {
68 auto h = hash(e);
69 EXPECT_EQ(h, hash_default_hash<int>{}(static_cast<int>(e)));
70 EXPECT_NE(h, hash(MyEnum::D));
71 }
72 }
73
74 using StringTypes = ::testing::Types<std::string, absl::string_view>;
75
76 template <class T>
77 struct EqString : ::testing::Test {
78 hash_default_eq<T> key_eq;
79 };
80
81 TYPED_TEST_SUITE(EqString, StringTypes);
82
83 template <class T>
84 struct HashString : ::testing::Test {
85 hash_default_hash<T> hasher;
86 };
87
88 TYPED_TEST_SUITE(HashString, StringTypes);
89
TYPED_TEST(EqString,Works)90 TYPED_TEST(EqString, Works) {
91 auto eq = this->key_eq;
92 EXPECT_TRUE(eq("a", "a"));
93 EXPECT_TRUE(eq("a", absl::string_view("a")));
94 EXPECT_TRUE(eq("a", std::string("a")));
95 EXPECT_FALSE(eq("a", "b"));
96 EXPECT_FALSE(eq("a", absl::string_view("b")));
97 EXPECT_FALSE(eq("a", std::string("b")));
98 }
99
TYPED_TEST(HashString,Works)100 TYPED_TEST(HashString, Works) {
101 auto hash = this->hasher;
102 auto h = hash("a");
103 EXPECT_EQ(h, hash(absl::string_view("a")));
104 EXPECT_EQ(h, hash(std::string("a")));
105 EXPECT_NE(h, hash(absl::string_view("b")));
106 EXPECT_NE(h, hash(std::string("b")));
107 }
108
109 struct NoDeleter {
110 template <class T>
operator ()absl::container_internal::__anonf3323b4a0111::NoDeleter111 void operator()(const T* ptr) const {}
112 };
113
114 using PointerTypes =
115 ::testing::Types<const int*, int*, std::unique_ptr<const int>,
116 std::unique_ptr<const int, NoDeleter>,
117 std::unique_ptr<int>, std::unique_ptr<int, NoDeleter>,
118 std::shared_ptr<const int>, std::shared_ptr<int>>;
119
120 template <class T>
121 struct EqPointer : ::testing::Test {
122 hash_default_eq<T> key_eq;
123 };
124
125 TYPED_TEST_SUITE(EqPointer, PointerTypes);
126
127 template <class T>
128 struct HashPointer : ::testing::Test {
129 hash_default_hash<T> hasher;
130 };
131
132 TYPED_TEST_SUITE(HashPointer, PointerTypes);
133
TYPED_TEST(EqPointer,Works)134 TYPED_TEST(EqPointer, Works) {
135 int dummy;
136 auto eq = this->key_eq;
137 auto sptr = std::make_shared<int>();
138 std::shared_ptr<const int> csptr = sptr;
139 int* ptr = sptr.get();
140 const int* cptr = ptr;
141 std::unique_ptr<int, NoDeleter> uptr(ptr);
142 std::unique_ptr<const int, NoDeleter> cuptr(ptr);
143
144 EXPECT_TRUE(eq(ptr, cptr));
145 EXPECT_TRUE(eq(ptr, sptr));
146 EXPECT_TRUE(eq(ptr, uptr));
147 EXPECT_TRUE(eq(ptr, csptr));
148 EXPECT_TRUE(eq(ptr, cuptr));
149 EXPECT_FALSE(eq(&dummy, cptr));
150 EXPECT_FALSE(eq(&dummy, sptr));
151 EXPECT_FALSE(eq(&dummy, uptr));
152 EXPECT_FALSE(eq(&dummy, csptr));
153 EXPECT_FALSE(eq(&dummy, cuptr));
154 }
155
TEST(Hash,DerivedAndBase)156 TEST(Hash, DerivedAndBase) {
157 struct Base {};
158 struct Derived : Base {};
159
160 hash_default_hash<Base*> hasher;
161
162 Base base;
163 Derived derived;
164 EXPECT_NE(hasher(&base), hasher(&derived));
165 EXPECT_EQ(hasher(static_cast<Base*>(&derived)), hasher(&derived));
166
167 auto dp = std::make_shared<Derived>();
168 EXPECT_EQ(hasher(static_cast<Base*>(dp.get())), hasher(dp));
169 }
170
TEST(Hash,FunctionPointer)171 TEST(Hash, FunctionPointer) {
172 using Func = int (*)();
173 hash_default_hash<Func> hasher;
174 hash_default_eq<Func> eq;
175
176 Func p1 = [] { return 1; }, p2 = [] { return 2; };
177 EXPECT_EQ(hasher(p1), hasher(p1));
178 EXPECT_TRUE(eq(p1, p1));
179
180 EXPECT_NE(hasher(p1), hasher(p2));
181 EXPECT_FALSE(eq(p1, p2));
182 }
183
TYPED_TEST(HashPointer,Works)184 TYPED_TEST(HashPointer, Works) {
185 int dummy;
186 auto hash = this->hasher;
187 auto sptr = std::make_shared<int>();
188 std::shared_ptr<const int> csptr = sptr;
189 int* ptr = sptr.get();
190 const int* cptr = ptr;
191 std::unique_ptr<int, NoDeleter> uptr(ptr);
192 std::unique_ptr<const int, NoDeleter> cuptr(ptr);
193
194 EXPECT_EQ(hash(ptr), hash(cptr));
195 EXPECT_EQ(hash(ptr), hash(sptr));
196 EXPECT_EQ(hash(ptr), hash(uptr));
197 EXPECT_EQ(hash(ptr), hash(csptr));
198 EXPECT_EQ(hash(ptr), hash(cuptr));
199 EXPECT_NE(hash(&dummy), hash(cptr));
200 EXPECT_NE(hash(&dummy), hash(sptr));
201 EXPECT_NE(hash(&dummy), hash(uptr));
202 EXPECT_NE(hash(&dummy), hash(csptr));
203 EXPECT_NE(hash(&dummy), hash(cuptr));
204 }
205
206 // Cartesian product of (std::string, absl::string_view)
207 // with (std::string, absl::string_view, const char*).
208 using StringTypesCartesianProduct = Types<
209 // clang-format off
210
211 std::pair<absl::string_view, std::string>,
212 std::pair<absl::string_view, absl::string_view>,
213 std::pair<absl::string_view, const char*>>;
214 // clang-format on
215
216 constexpr char kFirstString[] = "abc123";
217 constexpr char kSecondString[] = "ijk456";
218
219 template <typename T>
220 struct StringLikeTest : public ::testing::Test {
221 typename T::first_type a1{kFirstString};
222 typename T::second_type b1{kFirstString};
223 typename T::first_type a2{kSecondString};
224 typename T::second_type b2{kSecondString};
225 hash_default_eq<typename T::first_type> eq;
226 hash_default_hash<typename T::first_type> hash;
227 };
228
229 TYPED_TEST_CASE_P(StringLikeTest);
230
TYPED_TEST_P(StringLikeTest,Eq)231 TYPED_TEST_P(StringLikeTest, Eq) {
232 EXPECT_TRUE(this->eq(this->a1, this->b1));
233 EXPECT_TRUE(this->eq(this->b1, this->a1));
234 }
235
TYPED_TEST_P(StringLikeTest,NotEq)236 TYPED_TEST_P(StringLikeTest, NotEq) {
237 EXPECT_FALSE(this->eq(this->a1, this->b2));
238 EXPECT_FALSE(this->eq(this->b2, this->a1));
239 }
240
TYPED_TEST_P(StringLikeTest,HashEq)241 TYPED_TEST_P(StringLikeTest, HashEq) {
242 EXPECT_EQ(this->hash(this->a1), this->hash(this->b1));
243 EXPECT_EQ(this->hash(this->a2), this->hash(this->b2));
244 // It would be a poor hash function which collides on these strings.
245 EXPECT_NE(this->hash(this->a1), this->hash(this->b2));
246 }
247
248 TYPED_TEST_SUITE(StringLikeTest, StringTypesCartesianProduct);
249
250 } // namespace
251 } // namespace container_internal
252 ABSL_NAMESPACE_END
253 } // namespace absl
254
255 enum Hash : size_t {
256 kStd = 0x2, // std::hash
257 #ifdef _MSC_VER
258 kExtension = kStd, // In MSVC, std::hash == ::hash
259 #else // _MSC_VER
260 kExtension = 0x4, // ::hash (GCC extension)
261 #endif // _MSC_VER
262 };
263
264 // H is a bitmask of Hash enumerations.
265 // Hashable<H> is hashable via all means specified in H.
266 template <int H>
267 struct Hashable {
HashableByHashable268 static constexpr bool HashableBy(Hash h) { return h & H; }
269 };
270
271 namespace std {
272 template <int H>
273 struct hash<Hashable<H>> {
274 template <class E = Hashable<H>,
275 class = typename std::enable_if<E::HashableBy(kStd)>::type>
operator ()std::hash276 size_t operator()(E) const {
277 return kStd;
278 }
279 };
280 } // namespace std
281
282 namespace absl {
283 ABSL_NAMESPACE_BEGIN
284 namespace container_internal {
285 namespace {
286
287 template <class T>
Hash(const T & v)288 size_t Hash(const T& v) {
289 return hash_default_hash<T>()(v);
290 }
291
TEST(Delegate,HashDispatch)292 TEST(Delegate, HashDispatch) {
293 EXPECT_EQ(Hash(kStd), Hash(Hashable<kStd>()));
294 }
295
296 } // namespace
297 } // namespace container_internal
298 ABSL_NAMESPACE_END
299 } // namespace absl
300