• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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