| 1 |
//===- llvm/unittest/ADT/HashingTest.cpp ----------------------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// Hashing.h unit tests. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "llvm/ADT/Hashing.h" |
| 14 |
#include "llvm/Support/DataTypes.h" |
| 15 |
#include "llvm/Support/HashBuilder.h" |
| 16 |
#include "gtest/gtest.h" |
| 17 |
#include <deque> |
| 18 |
#include <list> |
| 19 |
#include <map> |
| 20 |
#include <optional> |
| 21 |
#include <vector> |
| 22 |
|
| 23 |
namespace llvm { |
| 24 |
|
| 25 |
// Helper for test code to print hash codes. |
| 26 |
void PrintTo(const hash_code &code, std::ostream *os) { |
| 27 |
*os << static_cast<size_t>(code); |
| 28 |
} |
| 29 |
|
| 30 |
// Fake an object that is recognized as hashable data to test super large |
| 31 |
// objects. |
| 32 |
struct LargeTestInteger { uint64_t arr[8]; }; |
| 33 |
|
| 34 |
struct NonPOD { |
| 35 |
uint64_t x, y; |
| 36 |
NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {} |
| 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> : std::true_type {}; |
| 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'; |
| 61 |
void *p = nullptr; |
| 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, HashValueStdTuple) { |
| 107 |
EXPECT_EQ(hash_combine(), hash_value(std::make_tuple())); |
| 108 |
EXPECT_EQ(hash_combine(42), hash_value(std::make_tuple(42))); |
| 109 |
EXPECT_EQ(hash_combine(42, 'c'), hash_value(std::make_tuple(42, 'c'))); |
| 110 |
|
| 111 |
EXPECT_NE(hash_combine(43, 42), hash_value(std::make_tuple(42, 43))); |
| 112 |
EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42ull, 43ull))); |
| 113 |
EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42, 43ull))); |
| 114 |
EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42ull, 43))); |
| 115 |
} |
| 116 |
|
| 117 |
TEST(HashingTest, HashValueStdString) { |
| 118 |
std::string s = "Hello World!"; |
| 119 |
EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size()), hash_value(s)); |
| 120 |
EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size() - 1), |
| 121 |
hash_value(s.substr(0, s.size() - 1))); |
| 122 |
EXPECT_EQ(hash_combine_range(s.c_str() + 1, s.c_str() + s.size() - 1), |
| 123 |
hash_value(s.substr(1, s.size() - 2))); |
| 124 |
|
| 125 |
std::wstring ws = L"Hello Wide World!"; |
| 126 |
EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size()), |
| 127 |
hash_value(ws)); |
| 128 |
EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size() - 1), |
| 129 |
hash_value(ws.substr(0, ws.size() - 1))); |
| 130 |
EXPECT_EQ(hash_combine_range(ws.c_str() + 1, ws.c_str() + ws.size() - 1), |
| 131 |
hash_value(ws.substr(1, ws.size() - 2))); |
| 132 |
} |
| 133 |
|
| 134 |
TEST(HashingTest, HashValueStdOptional) { |
| 135 |
// Check that std::nullopt, false, and true all hash differently. |
| 136 |
std::optional<bool> B, B0 = false, B1 = true; |
| 137 |
EXPECT_NE(hash_value(B0), hash_value(B)); |
| 138 |
EXPECT_NE(hash_value(B1), hash_value(B)); |
| 139 |
EXPECT_NE(hash_value(B1), hash_value(B0)); |
| 140 |
|
| 141 |
// Check that std::nullopt, 0, and 1 all hash differently. |
| 142 |
std::optional<int> I, I0 = 0, I1 = 1; |
| 143 |
EXPECT_NE(hash_value(I0), hash_value(I)); |
| 144 |
EXPECT_NE(hash_value(I1), hash_value(I)); |
| 145 |
EXPECT_NE(hash_value(I1), hash_value(I0)); |
| 146 |
|
| 147 |
// Check std::nullopt hash the same way regardless of type. |
| 148 |
EXPECT_EQ(hash_value(B), hash_value(I)); |
| 149 |
} |
| 150 |
|
| 151 |
template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; } |
| 152 |
template <typename T, size_t N> T *end(T (&arr)[N]) { return arr + N; } |
| 153 |
|
| 154 |
// Provide a dummy, hashable type designed for easy verification: its hash is |
| 155 |
// the same as its value. |
| 156 |
struct HashableDummy { size_t value; }; |
| 157 |
hash_code hash_value(HashableDummy dummy) { return dummy.value; } |
| 158 |
|
| 159 |
TEST(HashingTest, HashCombineRangeBasicTest) { |
| 160 |
// Leave this uninitialized in the hope that valgrind will catch bad reads. |
| 161 |
int dummy; |
| 162 |
hash_code dummy_hash = hash_combine_range(&dummy, &dummy); |
| 163 |
EXPECT_NE(hash_code(0), dummy_hash); |
| 164 |
|
| 165 |
const int arr1[] = { 1, 2, 3 }; |
| 166 |
hash_code arr1_hash = hash_combine_range(begin(arr1), end(arr1)); |
| 167 |
EXPECT_NE(dummy_hash, arr1_hash); |
| 168 |
EXPECT_EQ(arr1_hash, hash_combine_range(begin(arr1), end(arr1))); |
| 169 |
|
| 170 |
const std::vector<int> vec(begin(arr1), end(arr1)); |
| 171 |
EXPECT_EQ(arr1_hash, hash_combine_range(vec.begin(), vec.end())); |
| 172 |
|
| 173 |
const std::list<int> list(begin(arr1), end(arr1)); |
| 174 |
EXPECT_EQ(arr1_hash, hash_combine_range(list.begin(), list.end())); |
| 175 |
|
| 176 |
const std::deque<int> deque(begin(arr1), end(arr1)); |
| 177 |
EXPECT_EQ(arr1_hash, hash_combine_range(deque.begin(), deque.end())); |
| 178 |
|
| 179 |
const int arr2[] = { 3, 2, 1 }; |
| 180 |
hash_code arr2_hash = hash_combine_range(begin(arr2), end(arr2)); |
| 181 |
EXPECT_NE(dummy_hash, arr2_hash); |
| 182 |
EXPECT_NE(arr1_hash, arr2_hash); |
| 183 |
|
| 184 |
const int arr3[] = { 1, 1, 2, 3 }; |
| 185 |
hash_code arr3_hash = hash_combine_range(begin(arr3), end(arr3)); |
| 186 |
EXPECT_NE(dummy_hash, arr3_hash); |
| 187 |
EXPECT_NE(arr1_hash, arr3_hash); |
| 188 |
|
| 189 |
const int arr4[] = { 1, 2, 3, 3 }; |
| 190 |
hash_code arr4_hash = hash_combine_range(begin(arr4), end(arr4)); |
| 191 |
EXPECT_NE(dummy_hash, arr4_hash); |
| 192 |
EXPECT_NE(arr1_hash, arr4_hash); |
| 193 |
|
| 194 |
const size_t arr5[] = { 1, 2, 3 }; |
| 195 |
const HashableDummy d_arr5[] = { {1}, {2}, {3} }; |
| 196 |
hash_code arr5_hash = hash_combine_range(begin(arr5), end(arr5)); |
| 197 |
hash_code d_arr5_hash = hash_combine_range(begin(d_arr5), end(d_arr5)); |
| 198 |
EXPECT_EQ(arr5_hash, d_arr5_hash); |
| 199 |
} |
| 200 |
|
| 201 |
TEST(HashingTest, HashCombineRangeLengthDiff) { |
| 202 |
// Test that as only the length varies, we compute different hash codes for |
| 203 |
// sequences. |
| 204 |
std::map<size_t, size_t> code_to_size; |
| 205 |
std::vector<char> all_one_c(256, '\xff'); |
| 206 |
for (unsigned Idx = 1, Size = all_one_c.size(); Idx < Size; ++Idx) { |
| 207 |
hash_code code = hash_combine_range(&all_one_c[0], &all_one_c[0] + Idx); |
| 208 |
std::map<size_t, size_t>::iterator |
| 209 |
I = code_to_size.insert(std::make_pair(code, Idx)).first; |
| 210 |
EXPECT_EQ(Idx, I->second); |
| 211 |
} |
| 212 |
code_to_size.clear(); |
| 213 |
std::vector<char> all_zero_c(256, '\0'); |
| 214 |
for (unsigned Idx = 1, Size = all_zero_c.size(); Idx < Size; ++Idx) { |
| 215 |
hash_code code = hash_combine_range(&all_zero_c[0], &all_zero_c[0] + Idx); |
| 216 |
std::map<size_t, size_t>::iterator |
| 217 |
I = code_to_size.insert(std::make_pair(code, Idx)).first; |
| 218 |
EXPECT_EQ(Idx, I->second); |
| 219 |
} |
| 220 |
code_to_size.clear(); |
| 221 |
std::vector<unsigned> all_one_int(512, -1); |
| 222 |
for (unsigned Idx = 1, Size = all_one_int.size(); Idx < Size; ++Idx) { |
| 223 |
hash_code code = hash_combine_range(&all_one_int[0], &all_one_int[0] + Idx); |
| 224 |
std::map<size_t, size_t>::iterator |
| 225 |
I = code_to_size.insert(std::make_pair(code, Idx)).first; |
| 226 |
EXPECT_EQ(Idx, I->second); |
| 227 |
} |
| 228 |
code_to_size.clear(); |
| 229 |
std::vector<unsigned> all_zero_int(512, 0); |
| 230 |
for (unsigned Idx = 1, Size = all_zero_int.size(); Idx < Size; ++Idx) { |
| 231 |
hash_code code = hash_combine_range(&all_zero_int[0], &all_zero_int[0] + Idx); |
| 232 |
std::map<size_t, size_t>::iterator |
| 233 |
I = code_to_size.insert(std::make_pair(code, Idx)).first; |
| 234 |
EXPECT_EQ(Idx, I->second); |
| 235 |
} |
| 236 |
} |
| 237 |
|
| 238 |
TEST(HashingTest, HashCombineRangeGoldenTest) { |
| 239 |
struct { const char *s; uint64_t hash; } golden_data[] = { |
| 240 |
#if SIZE_MAX == UINT64_MAX || SIZE_MAX == UINT32_MAX |
| 241 |
{ "a", 0xaeb6f9d5517c61f8ULL }, |
| 242 |
{ "ab", 0x7ab1edb96be496b4ULL }, |
| 243 |
{ "abc", 0xe38e60bf19c71a3fULL }, |
| 244 |
{ "abcde", 0xd24461a66de97f6eULL }, |
| 245 |
{ "abcdefgh", 0x4ef872ec411dec9dULL }, |
| 246 |
{ "abcdefghijklm", 0xe8a865539f4eadfeULL }, |
| 247 |
{ "abcdefghijklmnopqrstu", 0x261cdf85faaf4e79ULL }, |
| 248 |
{ "abcdefghijklmnopqrstuvwxyzabcdef", 0x43ba70e4198e3b2aULL }, |
| 249 |
{ "abcdefghijklmnopqrstuvwxyzabcdef" |
| 250 |
"abcdefghijklmnopqrstuvwxyzghijkl" |
| 251 |
"abcdefghijklmnopqrstuvwxyzmnopqr" |
| 252 |
"abcdefghijklmnopqrstuvwxyzstuvwx" |
| 253 |
"abcdefghijklmnopqrstuvwxyzyzabcd", 0xdcd57fb2afdf72beULL }, |
| 254 |
{ "a", 0xaeb6f9d5517c61f8ULL }, |
| 255 |
{ "aa", 0xf2b3b69a9736a1ebULL }, |
| 256 |
{ "aaa", 0xf752eb6f07b1cafeULL }, |
| 257 |
{ "aaaaa", 0x812bd21e1236954cULL }, |
| 258 |
{ "aaaaaaaa", 0xff07a2cff08ac587ULL }, |
| 259 |
{ "aaaaaaaaaaaaa", 0x84ac949d54d704ecULL }, |
| 260 |
{ "aaaaaaaaaaaaaaaaaaaaa", 0xcb2c8fb6be8f5648ULL }, |
| 261 |
{ "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0xcc40ab7f164091b6ULL }, |
| 262 |
{ "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
| 263 |
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
| 264 |
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
| 265 |
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
| 266 |
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0xc58e174c1e78ffe9ULL }, |
| 267 |
{ "z", 0x1ba160d7e8f8785cULL }, |
| 268 |
{ "zz", 0x2c5c03172f1285d7ULL }, |
| 269 |
{ "zzz", 0x9d2c4f4b507a2ac3ULL }, |
| 270 |
{ "zzzzz", 0x0f03b9031735693aULL }, |
| 271 |
{ "zzzzzzzz", 0xe674147c8582c08eULL }, |
| 272 |
{ "zzzzzzzzzzzzz", 0x3162d9fa6938db83ULL }, |
| 273 |
{ "zzzzzzzzzzzzzzzzzzzzz", 0x37b9a549e013620cULL }, |
| 274 |
{ "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0x8921470aff885016ULL }, |
| 275 |
{ "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
| 276 |
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
| 277 |
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
| 278 |
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" |
| 279 |
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0xf60fdcd9beb08441ULL }, |
| 280 |
{ "a", 0xaeb6f9d5517c61f8ULL }, |
| 281 |
{ "ab", 0x7ab1edb96be496b4ULL }, |
| 282 |
{ "aba", 0x3edb049950884d0aULL }, |
| 283 |
{ "ababa", 0x8f2de9e73a97714bULL }, |
| 284 |
{ "abababab", 0xee14a29ddf0ce54cULL }, |
| 285 |
{ "ababababababa", 0x38b3ddaada2d52b4ULL }, |
| 286 |
{ "ababababababababababa", 0xd3665364219f2b85ULL }, |
| 287 |
{ "abababababababababababababababab", 0xa75cd6afbf1bc972ULL }, |
| 288 |
{ "abababababababababababababababab" |
| 289 |
"abababababababababababababababab" |
| 290 |
"abababababababababababababababab" |
| 291 |
"abababababababababababababababab" |
| 292 |
"abababababababababababababababab", 0x840192d129f7a22bULL } |
| 293 |
#else |
| 294 |
#error This test only supports 64-bit and 32-bit systems. |
| 295 |
#endif |
| 296 |
}; |
| 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)); |
| 304 |
#endif |
| 305 |
EXPECT_EQ(static_cast<size_t>(golden_data[i].hash), |
| 306 |
static_cast<size_t>(hash)); |
| 307 |
} |
| 308 |
} |
| 309 |
|
| 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)); |
| 322 |
|
| 323 |
// Hashing a sequence of heterogeneous 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)); |
| 336 |
|
| 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)); |
| 346 |
|
| 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)); |
| 351 |
|
| 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 |
| 364 |
}; |
| 365 |
// Hash a preposterously large integer, both aligned with the buffer and |
| 366 |
// misaligned. |
| 367 |
const LargeTestInteger li = { { |
| 368 |
0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, |
| 369 |
0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL, |
| 370 |
0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL |
| 371 |
} }; |
| 372 |
// Rotate the storage from 'li'. |
| 373 |
const LargeTestInteger l2 = { { |
| 374 |
0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, |
| 375 |
0xfefefefededededeULL, 0xafafafafededededULL, 0xffffeeeeddddccccULL, |
| 376 |
0xaaaacbcbffffababULL, 0xaaaaaaaaababababULL |
| 377 |
} }; |
| 378 |
const LargeTestInteger l3 = { { |
| 379 |
0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, |
| 380 |
0xafafafafededededULL, 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL, |
| 381 |
0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL |
| 382 |
} }; |
| 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])); |
| 397 |
} |
| 398 |
|
| 399 |
TEST(HashingTest, HashCombineArgs18) { |
| 400 |
// This tests that we can pass in up to 18 args. |
| 401 |
#define CHECK_SAME(...) \ |
| 402 |
EXPECT_EQ(hash_combine(__VA_ARGS__), hash_combine(__VA_ARGS__)) |
| 403 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18); |
| 404 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17); |
| 405 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16); |
| 406 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15); |
| 407 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14); |
| 408 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13); |
| 409 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12); |
| 410 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11); |
| 411 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); |
| 412 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9); |
| 413 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8); |
| 414 |
CHECK_SAME(1, 2, 3, 4, 5, 6, 7); |
| 415 |
CHECK_SAME(1, 2, 3, 4, 5, 6); |
| 416 |
CHECK_SAME(1, 2, 3, 4, 5); |
| 417 |
CHECK_SAME(1, 2, 3, 4); |
| 418 |
CHECK_SAME(1, 2, 3); |
| 419 |
CHECK_SAME(1, 2); |
| 420 |
CHECK_SAME(1); |
| 421 |
#undef CHECK_SAME |
| 422 |
} |
| 423 |
|
| 424 |
struct StructWithHashBuilderSupport { |
| 425 |
char C; |
| 426 |
int I; |
| 427 |
template <typename HasherT, llvm::support::endianness Endianness> |
| 428 |
friend void addHash(llvm::HashBuilderImpl<HasherT, Endianness> &HBuilder, |
| 429 |
const StructWithHashBuilderSupport &Value) { |
| 430 |
HBuilder.add(Value.C, Value.I); |
| 431 |
} |
| 432 |
}; |
| 433 |
|
| 434 |
TEST(HashingTest, HashWithHashBuilder) { |
| 435 |
StructWithHashBuilderSupport S{'c', 1}; |
| 436 |
EXPECT_NE(static_cast<size_t>(llvm::hash_value(S)), static_cast<size_t>(0)); |
| 437 |
} |
| 438 |
|
| 439 |
struct StructWithHashBuilderAndHashValueSupport { |
| 440 |
char C; |
| 441 |
int I; |
| 442 |
template <typename HasherT, llvm::support::endianness Endianness> |
| 443 |
friend void addHash(llvm::HashBuilderImpl<HasherT, Endianness> &HBuilder, |
| 444 |
const StructWithHashBuilderAndHashValueSupport &Value) {} |
| 445 |
friend hash_code |
| 446 |
hash_value(const StructWithHashBuilderAndHashValueSupport &Value) { |
| 447 |
return 0xbeef; |
| 448 |
} |
| 449 |
}; |
| 450 |
|
| 451 |
TEST(HashingTest, HashBuilderAndHashValue) { |
| 452 |
StructWithHashBuilderAndHashValueSupport S{'c', 1}; |
| 453 |
EXPECT_EQ(static_cast<size_t>(hash_value(S)), static_cast<size_t>(0xbeef)); |
| 454 |
} |
| 455 |
|
| 456 |
} // namespace |