unittests/ADT/HashingTest.cpp

   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.
  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;
  35   NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {}
  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
  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
  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
 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
 122 template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }
 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; };
 128 hash_code hash_value(HashableDummy dummy) { return dummy.value; }
 129
 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
 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
 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
 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
 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 }