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
22namespace llvm {
23
24// Helper for test code to print hash codes.
25void 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.
31struct LargeTestInteger { uint64_t arr[8]; };
32
33struct 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
41namespace hashing {
42namespace detail {
43template <> struct is_hashable_data<LargeTestInteger> : std::true_type {};
44} // namespace detail
45} // namespace hashing
46
47} // namespace llvm
48
49using namespace llvm;
50
51namespace {
52
53enum TestEnumeration {
54  TE_Foo = 42,
55  TE_Bar = 43
56};
57
58TEST(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
80TEST(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
105TEST(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
122template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }
123template <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.
127struct HashableDummy { size_t value; };
128hash_code hash_value(HashableDummy dummy) { return dummy.value; }
129
130TEST(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
172TEST(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
209TEST(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
334TEST(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
423TEST(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