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