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