1 | //===- llvm/unittest/ADT/HashingTest.cpp ----------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // Hashing.h unit tests. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "llvm/ADT/Hashing.h" |
14 | #include "llvm/Support/DataTypes.h" |
15 | #include "llvm/Support/HashBuilder.h" |
16 | #include "gtest/gtest.h" |
17 | #include <deque> |
18 | #include <list> |
19 | #include <map> |
20 | #include <optional> |
21 | #include <vector> |
22 | |
23 | namespace llvm { |
24 | |
25 | // Helper for test code to print hash codes. |
26 | void PrintTo(const hash_code &code, std::ostream *os) { |
27 | *os << static_cast<size_t>(code); |
28 | } |
29 | |
30 | // Fake an object that is recognized as hashable data to test super large |
31 | // objects. |
32 | struct LargeTestInteger { uint64_t arr[8]; }; |
33 | |
34 | struct NonPOD { |
35 | uint64_t x, y; |
36 | NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {} |
37 | friend hash_code hash_value(const NonPOD &obj) { |
38 | return hash_combine(args: obj.x, args: obj.y); |
39 | } |
40 | }; |
41 | |
42 | namespace hashing { |
43 | namespace detail { |
44 | template <> struct is_hashable_data<LargeTestInteger> : std::true_type {}; |
45 | } // namespace detail |
46 | } // namespace hashing |
47 | |
48 | } // namespace llvm |
49 | |
50 | using namespace llvm; |
51 | |
52 | namespace { |
53 | |
54 | enum TestEnumeration { |
55 | TE_Foo = 42, |
56 | TE_Bar = 43 |
57 | }; |
58 | |
59 | TEST(HashingTest, HashValueBasicTest) { |
60 | int x = 42, y = 43, c = 'x'; |
61 | void *p = nullptr; |
62 | uint64_t i = 71; |
63 | const unsigned ci = 71; |
64 | volatile int vi = 71; |
65 | const volatile int cvi = 71; |
66 | uintptr_t addr = reinterpret_cast<uintptr_t>(&y); |
67 | EXPECT_EQ(hash_value(42), hash_value(x)); |
68 | EXPECT_EQ(hash_value(42), hash_value(TE_Foo)); |
69 | EXPECT_NE(hash_value(42), hash_value(y)); |
70 | EXPECT_NE(hash_value(42), hash_value(TE_Bar)); |
71 | EXPECT_NE(hash_value(42), hash_value(p)); |
72 | EXPECT_EQ(hash_value(71), hash_value(i)); |
73 | EXPECT_EQ(hash_value(71), hash_value(ci)); |
74 | EXPECT_EQ(hash_value(71), hash_value(vi)); |
75 | EXPECT_EQ(hash_value(71), hash_value(cvi)); |
76 | EXPECT_EQ(hash_value(c), hash_value('x')); |
77 | EXPECT_EQ(hash_value('4'), hash_value('0' + 4)); |
78 | EXPECT_EQ(hash_value(addr), hash_value(&y)); |
79 | } |
80 | |
81 | TEST(HashingTest, HashValueStdPair) { |
82 | EXPECT_EQ(hash_combine(42, 43), hash_value(std::make_pair(42, 43))); |
83 | EXPECT_NE(hash_combine(43, 42), hash_value(std::make_pair(42, 43))); |
84 | EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43ull))); |
85 | EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42, 43ull))); |
86 | EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43))); |
87 | |
88 | // Note that pairs are implicitly flattened to a direct sequence of data and |
89 | // hashed efficiently as a consequence. |
90 | EXPECT_EQ(hash_combine(42, 43, 44), |
91 | hash_value(std::make_pair(42, std::make_pair(43, 44)))); |
92 | EXPECT_EQ(hash_value(std::make_pair(42, std::make_pair(43, 44))), |
93 | hash_value(std::make_pair(std::make_pair(42, 43), 44))); |
94 | |
95 | // Ensure that pairs which have padding bytes *inside* them don't get treated |
96 | // this way. |
97 | EXPECT_EQ(hash_combine('0', hash_combine(1ull, '2')), |
98 | hash_value(std::make_pair('0', std::make_pair(1ull, '2')))); |
99 | |
100 | // Ensure that non-POD pairs don't explode the traits used. |
101 | NonPOD obj1(1, 2), obj2(3, 4), obj3(5, 6); |
102 | EXPECT_EQ(hash_combine(obj1, hash_combine(obj2, obj3)), |
103 | hash_value(std::make_pair(obj1, std::make_pair(obj2, obj3)))); |
104 | } |
105 | |
106 | TEST(HashingTest, HashValueStdTuple) { |
107 | EXPECT_EQ(hash_combine(), hash_value(std::make_tuple())); |
108 | EXPECT_EQ(hash_combine(42), hash_value(std::make_tuple(42))); |
109 | EXPECT_EQ(hash_combine(42, 'c'), hash_value(std::make_tuple(42, 'c'))); |
110 | |
111 | EXPECT_NE(hash_combine(43, 42), hash_value(std::make_tuple(42, 43))); |
112 | EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42ull, 43ull))); |
113 | EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42, 43ull))); |
114 | EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42ull, 43))); |
115 | } |
116 | |
117 | TEST(HashingTest, HashValueStdString) { |
118 | std::string s = "Hello World!" ; |
119 | EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size()), hash_value(s)); |
120 | EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size() - 1), |
121 | hash_value(s.substr(0, s.size() - 1))); |
122 | EXPECT_EQ(hash_combine_range(s.c_str() + 1, s.c_str() + s.size() - 1), |
123 | hash_value(s.substr(1, s.size() - 2))); |
124 | |
125 | std::wstring ws = L"Hello Wide World!" ; |
126 | EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size()), |
127 | hash_value(ws)); |
128 | EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size() - 1), |
129 | hash_value(ws.substr(0, ws.size() - 1))); |
130 | EXPECT_EQ(hash_combine_range(ws.c_str() + 1, ws.c_str() + ws.size() - 1), |
131 | hash_value(ws.substr(1, ws.size() - 2))); |
132 | } |
133 | |
134 | TEST(HashingTest, HashValueStdOptional) { |
135 | // Check that std::nullopt, false, and true all hash differently. |
136 | std::optional<bool> B, B0 = false, B1 = true; |
137 | EXPECT_NE(hash_value(B0), hash_value(B)); |
138 | EXPECT_NE(hash_value(B1), hash_value(B)); |
139 | EXPECT_NE(hash_value(B1), hash_value(B0)); |
140 | |
141 | // Check that std::nullopt, 0, and 1 all hash differently. |
142 | std::optional<int> I, I0 = 0, I1 = 1; |
143 | EXPECT_NE(hash_value(I0), hash_value(I)); |
144 | EXPECT_NE(hash_value(I1), hash_value(I)); |
145 | EXPECT_NE(hash_value(I1), hash_value(I0)); |
146 | |
147 | // Check std::nullopt hash the same way regardless of type. |
148 | EXPECT_EQ(hash_value(B), hash_value(I)); |
149 | } |
150 | |
151 | template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; } |
152 | template <typename T, size_t N> T *end(T (&arr)[N]) { return arr + N; } |
153 | |
154 | // Provide a dummy, hashable type designed for easy verification: its hash is |
155 | // the same as its value. |
156 | struct HashableDummy { size_t value; }; |
157 | hash_code hash_value(HashableDummy dummy) { return dummy.value; } |
158 | |
159 | TEST(HashingTest, HashCombineRangeBasicTest) { |
160 | // Leave this uninitialized in the hope that valgrind will catch bad reads. |
161 | int dummy; |
162 | hash_code dummy_hash = hash_combine_range(first: &dummy, last: &dummy); |
163 | EXPECT_NE(hash_code(0), dummy_hash); |
164 | |
165 | const int arr1[] = { 1, 2, 3 }; |
166 | hash_code arr1_hash = hash_combine_range(first: begin(arr: arr1), last: end(arr: arr1)); |
167 | EXPECT_NE(dummy_hash, arr1_hash); |
168 | EXPECT_EQ(arr1_hash, hash_combine_range(begin(arr1), end(arr1))); |
169 | |
170 | const std::vector<int> vec(begin(arr: arr1), end(arr: arr1)); |
171 | EXPECT_EQ(arr1_hash, hash_combine_range(vec.begin(), vec.end())); |
172 | |
173 | const std::list<int> list(begin(arr: arr1), end(arr: arr1)); |
174 | EXPECT_EQ(arr1_hash, hash_combine_range(list.begin(), list.end())); |
175 | |
176 | const std::deque<int> deque(begin(arr: arr1), end(arr: arr1)); |
177 | EXPECT_EQ(arr1_hash, hash_combine_range(deque.begin(), deque.end())); |
178 | |
179 | const int arr2[] = { 3, 2, 1 }; |
180 | hash_code arr2_hash = hash_combine_range(first: begin(arr: arr2), last: end(arr: arr2)); |
181 | EXPECT_NE(dummy_hash, arr2_hash); |
182 | EXPECT_NE(arr1_hash, arr2_hash); |
183 | |
184 | const int arr3[] = { 1, 1, 2, 3 }; |
185 | hash_code arr3_hash = hash_combine_range(first: begin(arr: arr3), last: end(arr: arr3)); |
186 | EXPECT_NE(dummy_hash, arr3_hash); |
187 | EXPECT_NE(arr1_hash, arr3_hash); |
188 | |
189 | const int arr4[] = { 1, 2, 3, 3 }; |
190 | hash_code arr4_hash = hash_combine_range(first: begin(arr: arr4), last: end(arr: arr4)); |
191 | EXPECT_NE(dummy_hash, arr4_hash); |
192 | EXPECT_NE(arr1_hash, arr4_hash); |
193 | |
194 | const size_t arr5[] = { 1, 2, 3 }; |
195 | const HashableDummy d_arr5[] = { {.value: 1}, {.value: 2}, {.value: 3} }; |
196 | hash_code arr5_hash = hash_combine_range(first: begin(arr: arr5), last: end(arr: arr5)); |
197 | hash_code d_arr5_hash = hash_combine_range(first: begin(arr: d_arr5), last: end(arr: d_arr5)); |
198 | EXPECT_EQ(arr5_hash, d_arr5_hash); |
199 | } |
200 | |
201 | TEST(HashingTest, HashCombineRangeLengthDiff) { |
202 | // Test that as only the length varies, we compute different hash codes for |
203 | // sequences. |
204 | std::map<size_t, size_t> code_to_size; |
205 | std::vector<char> all_one_c(256, '\xff'); |
206 | for (unsigned Idx = 1, Size = all_one_c.size(); Idx < Size; ++Idx) { |
207 | hash_code code = hash_combine_range(first: &all_one_c[0], last: &all_one_c[0] + Idx); |
208 | std::map<size_t, size_t>::iterator |
209 | I = code_to_size.insert(x: std::make_pair(x&: code, y&: Idx)).first; |
210 | EXPECT_EQ(Idx, I->second); |
211 | } |
212 | code_to_size.clear(); |
213 | std::vector<char> all_zero_c(256, '\0'); |
214 | for (unsigned Idx = 1, Size = all_zero_c.size(); Idx < Size; ++Idx) { |
215 | hash_code code = hash_combine_range(first: &all_zero_c[0], last: &all_zero_c[0] + Idx); |
216 | std::map<size_t, size_t>::iterator |
217 | I = code_to_size.insert(x: std::make_pair(x&: code, y&: Idx)).first; |
218 | EXPECT_EQ(Idx, I->second); |
219 | } |
220 | code_to_size.clear(); |
221 | std::vector<unsigned> all_one_int(512, -1); |
222 | for (unsigned Idx = 1, Size = all_one_int.size(); Idx < Size; ++Idx) { |
223 | hash_code code = hash_combine_range(first: &all_one_int[0], last: &all_one_int[0] + Idx); |
224 | std::map<size_t, size_t>::iterator |
225 | I = code_to_size.insert(x: std::make_pair(x&: code, y&: Idx)).first; |
226 | EXPECT_EQ(Idx, I->second); |
227 | } |
228 | code_to_size.clear(); |
229 | std::vector<unsigned> all_zero_int(512, 0); |
230 | for (unsigned Idx = 1, Size = all_zero_int.size(); Idx < Size; ++Idx) { |
231 | hash_code code = hash_combine_range(first: &all_zero_int[0], last: &all_zero_int[0] + Idx); |
232 | std::map<size_t, size_t>::iterator |
233 | I = code_to_size.insert(x: std::make_pair(x&: code, y&: Idx)).first; |
234 | EXPECT_EQ(Idx, I->second); |
235 | } |
236 | } |
237 | |
238 | TEST(HashingTest, HashCombineRangeGoldenTest) { |
239 | struct { const char *s; uint64_t hash; } golden_data[] = { |
240 | #if SIZE_MAX == UINT64_MAX || SIZE_MAX == UINT32_MAX |
241 | { .s: "a" , .hash: 0xaeb6f9d5517c61f8ULL }, |
242 | { .s: "ab" , .hash: 0x7ab1edb96be496b4ULL }, |
243 | { .s: "abc" , .hash: 0xe38e60bf19c71a3fULL }, |
244 | { .s: "abcde" , .hash: 0xd24461a66de97f6eULL }, |
245 | { .s: "abcdefgh" , .hash: 0x4ef872ec411dec9dULL }, |
246 | { .s: "abcdefghijklm" , .hash: 0xe8a865539f4eadfeULL }, |
247 | { .s: "abcdefghijklmnopqrstu" , .hash: 0x261cdf85faaf4e79ULL }, |
248 | { .s: "abcdefghijklmnopqrstuvwxyzabcdef" , .hash: 0x43ba70e4198e3b2aULL }, |
249 | { .s: "abcdefghijklmnopqrstuvwxyzabcdef" |
250 | "abcdefghijklmnopqrstuvwxyzghijkl" |
251 | "abcdefghijklmnopqrstuvwxyzmnopqr" |
252 | "abcdefghijklmnopqrstuvwxyzstuvwx" |
253 | "abcdefghijklmnopqrstuvwxyzyzabcd" , .hash: 0xdcd57fb2afdf72beULL }, |
254 | { .s: "a" , .hash: 0xaeb6f9d5517c61f8ULL }, |
255 | { .s: "aa" , .hash: 0xf2b3b69a9736a1ebULL }, |
256 | { .s: "aaa" , .hash: 0xf752eb6f07b1cafeULL }, |
257 | { .s: "aaaaa" , .hash: 0x812bd21e1236954cULL }, |
258 | { .s: "aaaaaaaa" , .hash: 0xff07a2cff08ac587ULL }, |
259 | { .s: "aaaaaaaaaaaaa" , .hash: 0x84ac949d54d704ecULL }, |
260 | { .s: "aaaaaaaaaaaaaaaaaaaaa" , .hash: 0xcb2c8fb6be8f5648ULL }, |
261 | { .s: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" , .hash: 0xcc40ab7f164091b6ULL }, |
262 | { .s: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
263 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
264 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
265 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
266 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" , .hash: 0xc58e174c1e78ffe9ULL }, |
267 | { .s: "z" , .hash: 0x1ba160d7e8f8785cULL }, |
268 | { .s: "zz" , .hash: 0x2c5c03172f1285d7ULL }, |
269 | { .s: "zzz" , .hash: 0x9d2c4f4b507a2ac3ULL }, |
270 | { .s: "zzzzz" , .hash: 0x0f03b9031735693aULL }, |
271 | { .s: "zzzzzzzz" , .hash: 0xe674147c8582c08eULL }, |
272 | { .s: "zzzzzzzzzzzzz" , .hash: 0x3162d9fa6938db83ULL }, |
273 | { .s: "zzzzzzzzzzzzzzzzzzzzz" , .hash: 0x37b9a549e013620cULL }, |
274 | { .s: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" , .hash: 0x8921470aff885016ULL }, |
275 | { .s: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
276 | "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
277 | "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
278 | "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
279 | "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" , .hash: 0xf60fdcd9beb08441ULL }, |
280 | { .s: "a" , .hash: 0xaeb6f9d5517c61f8ULL }, |
281 | { .s: "ab" , .hash: 0x7ab1edb96be496b4ULL }, |
282 | { .s: "aba" , .hash: 0x3edb049950884d0aULL }, |
283 | { .s: "ababa" , .hash: 0x8f2de9e73a97714bULL }, |
284 | { .s: "abababab" , .hash: 0xee14a29ddf0ce54cULL }, |
285 | { .s: "ababababababa" , .hash: 0x38b3ddaada2d52b4ULL }, |
286 | { .s: "ababababababababababa" , .hash: 0xd3665364219f2b85ULL }, |
287 | { .s: "abababababababababababababababab" , .hash: 0xa75cd6afbf1bc972ULL }, |
288 | { .s: "abababababababababababababababab" |
289 | "abababababababababababababababab" |
290 | "abababababababababababababababab" |
291 | "abababababababababababababababab" |
292 | "abababababababababababababababab" , .hash: 0x840192d129f7a22bULL } |
293 | #else |
294 | #error This test only supports 64-bit and 32-bit systems. |
295 | #endif |
296 | }; |
297 | for (unsigned i = 0; i < sizeof(golden_data)/sizeof(*golden_data); ++i) { |
298 | StringRef str = golden_data[i].s; |
299 | hash_code hash = hash_combine_range(first: str.begin(), last: str.end()); |
300 | #if 0 // Enable this to generate paste-able text for the above structure. |
301 | std::string member_str = "\"" + str.str() + "\"," ; |
302 | fprintf(stderr, " { %-35s 0x%016llxULL },\n" , |
303 | member_str.c_str(), static_cast<uint64_t>(hash)); |
304 | #endif |
305 | EXPECT_EQ(static_cast<size_t>(golden_data[i].hash), |
306 | static_cast<size_t>(hash)); |
307 | } |
308 | } |
309 | |
310 | TEST(HashingTest, HashCombineBasicTest) { |
311 | // Hashing a sequence of homogenous types matches range hashing. |
312 | const int i1 = 42, i2 = 43, i3 = 123, i4 = 999, i5 = 0, i6 = 79; |
313 | const int arr1[] = { i1, i2, i3, i4, i5, i6 }; |
314 | EXPECT_EQ(hash_combine_range(arr1, arr1 + 1), hash_combine(i1)); |
315 | EXPECT_EQ(hash_combine_range(arr1, arr1 + 2), hash_combine(i1, i2)); |
316 | EXPECT_EQ(hash_combine_range(arr1, arr1 + 3), hash_combine(i1, i2, i3)); |
317 | EXPECT_EQ(hash_combine_range(arr1, arr1 + 4), hash_combine(i1, i2, i3, i4)); |
318 | EXPECT_EQ(hash_combine_range(arr1, arr1 + 5), |
319 | hash_combine(i1, i2, i3, i4, i5)); |
320 | EXPECT_EQ(hash_combine_range(arr1, arr1 + 6), |
321 | hash_combine(i1, i2, i3, i4, i5, i6)); |
322 | |
323 | // Hashing a sequence of heterogeneous types which *happen* to all produce the |
324 | // same data for hashing produces the same as a range-based hash of the |
325 | // fundamental values. |
326 | const size_t s1 = 1024, s2 = 8888, s3 = 9000000; |
327 | const HashableDummy d1 = { .value: 1024 }, d2 = { .value: 8888 }, d3 = { .value: 9000000 }; |
328 | const size_t arr2[] = { s1, s2, s3 }; |
329 | EXPECT_EQ(hash_combine_range(begin(arr2), end(arr2)), |
330 | hash_combine(s1, s2, s3)); |
331 | EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, s2, d3)); |
332 | EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, d2, s3)); |
333 | EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, s2, s3)); |
334 | EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, s3)); |
335 | EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, d3)); |
336 | |
337 | // Permuting values causes hashes to change. |
338 | EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i1, i2)); |
339 | EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i2, i1)); |
340 | EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i1, i1)); |
341 | EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i1)); |
342 | EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i2)); |
343 | EXPECT_NE(hash_combine(i2, i1, i1), hash_combine(i1, i1, i2)); |
344 | EXPECT_NE(hash_combine(i1, i1, i2), hash_combine(i1, i2, i1)); |
345 | EXPECT_NE(hash_combine(i1, i2, i1), hash_combine(i2, i1, i1)); |
346 | |
347 | // Changing type w/o changing value causes hashes to change. |
348 | EXPECT_NE(hash_combine(i1, i2, i3), hash_combine((char)i1, i2, i3)); |
349 | EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, (char)i2, i3)); |
350 | EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, i2, (char)i3)); |
351 | |
352 | // This is array of uint64, but it should have the exact same byte pattern as |
353 | // an array of LargeTestIntegers. |
354 | const uint64_t bigarr[] = { |
355 | 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, |
356 | 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL, |
357 | 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL, |
358 | 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, |
359 | 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL, |
360 | 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL, |
361 | 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, |
362 | 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL, |
363 | 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL |
364 | }; |
365 | // Hash a preposterously large integer, both aligned with the buffer and |
366 | // misaligned. |
367 | const LargeTestInteger li = { .arr: { |
368 | 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, |
369 | 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL, |
370 | 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL |
371 | } }; |
372 | // Rotate the storage from 'li'. |
373 | const LargeTestInteger l2 = { .arr: { |
374 | 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, |
375 | 0xfefefefededededeULL, 0xafafafafededededULL, 0xffffeeeeddddccccULL, |
376 | 0xaaaacbcbffffababULL, 0xaaaaaaaaababababULL |
377 | } }; |
378 | const LargeTestInteger l3 = { .arr: { |
379 | 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, |
380 | 0xafafafafededededULL, 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL, |
381 | 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL |
382 | } }; |
383 | EXPECT_EQ(hash_combine_range(begin(bigarr), end(bigarr)), |
384 | hash_combine(li, li, li)); |
385 | EXPECT_EQ(hash_combine_range(bigarr, bigarr + 9), |
386 | hash_combine(bigarr[0], l2)); |
387 | EXPECT_EQ(hash_combine_range(bigarr, bigarr + 10), |
388 | hash_combine(bigarr[0], bigarr[1], l3)); |
389 | EXPECT_EQ(hash_combine_range(bigarr, bigarr + 17), |
390 | hash_combine(li, bigarr[0], l2)); |
391 | EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18), |
392 | hash_combine(li, bigarr[0], bigarr[1], l3)); |
393 | EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18), |
394 | hash_combine(bigarr[0], l2, bigarr[9], l3)); |
395 | EXPECT_EQ(hash_combine_range(bigarr, bigarr + 20), |
396 | hash_combine(bigarr[0], l2, bigarr[9], l3, bigarr[18], bigarr[19])); |
397 | } |
398 | |
399 | TEST(HashingTest, HashCombineArgs18) { |
400 | // This tests that we can pass in up to 18 args. |
401 | #define CHECK_SAME(...) \ |
402 | EXPECT_EQ(hash_combine(__VA_ARGS__), hash_combine(__VA_ARGS__)) |
403 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18); |
404 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17); |
405 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16); |
406 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15); |
407 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14); |
408 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13); |
409 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12); |
410 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11); |
411 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); |
412 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9); |
413 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8); |
414 | CHECK_SAME(1, 2, 3, 4, 5, 6, 7); |
415 | CHECK_SAME(1, 2, 3, 4, 5, 6); |
416 | CHECK_SAME(1, 2, 3, 4, 5); |
417 | CHECK_SAME(1, 2, 3, 4); |
418 | CHECK_SAME(1, 2, 3); |
419 | CHECK_SAME(1, 2); |
420 | CHECK_SAME(1); |
421 | #undef CHECK_SAME |
422 | } |
423 | |
424 | struct StructWithHashBuilderSupport { |
425 | char C; |
426 | int I; |
427 | template <typename HasherT, llvm::endianness Endianness> |
428 | friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder, |
429 | const StructWithHashBuilderSupport &Value) { |
430 | HBuilder.add(Value.C, Value.I); |
431 | } |
432 | }; |
433 | |
434 | TEST(HashingTest, HashWithHashBuilder) { |
435 | StructWithHashBuilderSupport S{.C: 'c', .I: 1}; |
436 | EXPECT_NE(static_cast<size_t>(llvm::hash_value(S)), static_cast<size_t>(0)); |
437 | } |
438 | |
439 | struct StructWithHashBuilderAndHashValueSupport { |
440 | char C; |
441 | int I; |
442 | template <typename HasherT, llvm::endianness Endianness> |
443 | friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder, |
444 | const StructWithHashBuilderAndHashValueSupport &Value) {} |
445 | friend hash_code |
446 | hash_value(const StructWithHashBuilderAndHashValueSupport &Value) { |
447 | return 0xbeef; |
448 | } |
449 | }; |
450 | |
451 | TEST(HashingTest, HashBuilderAndHashValue) { |
452 | StructWithHashBuilderAndHashValueSupport S{.C: 'c', .I: 1}; |
453 | EXPECT_EQ(static_cast<size_t>(hash_value(S)), static_cast<size_t>(0xbeef)); |
454 | } |
455 | |
456 | } // namespace |
457 | |