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
23namespace llvm {
24
25// Helper for test code to print hash codes.
26void 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.
32struct LargeTestInteger { uint64_t arr[8]; };
33
34struct 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
42namespace hashing {
43namespace detail {
44template <> struct is_hashable_data<LargeTestInteger> : std::true_type {};
45} // namespace detail
46} // namespace hashing
47
48} // namespace llvm
49
50using namespace llvm;
51
52namespace {
53
54enum TestEnumeration {
55 TE_Foo = 42,
56 TE_Bar = 43
57};
58
59TEST(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
81TEST(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
106TEST(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
117TEST(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
134TEST(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
151template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }
152template <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.
156struct HashableDummy { size_t value; };
157hash_code hash_value(HashableDummy dummy) { return dummy.value; }
158
159TEST(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
201TEST(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
238TEST(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
310TEST(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
399TEST(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
424struct 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
434TEST(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
439struct 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
451TEST(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

source code of llvm/unittests/ADT/HashingTest.cpp