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