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