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