unittests/ADT/HashingTest.cpp

   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 namespace hashing {
  34 namespace detail {
  35 template <> struct is_hashable_data<LargeTestInteger> : true_type {};
  36 } // namespace detail
  37 } // namespace hashing
  38
  39 } // namespace llvm
  40
  41 using namespace llvm;
  42
  43 namespace {
  44
  45 TEST(HashingTest, HashValueBasicTest) {
  46   int x = 42, y = 43, c = 'x';
  47   void *p = 0;
  48   uint64_t i = 71;
  49   const unsigned ci = 71;
  50   volatile int vi = 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));
  63
  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)));
  69
  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)));
  76 }
  77
  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; }
  80
  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; }
  85
  86 TEST(HashingTest, HashCombineRangeBasicTest) {
  87   // Leave this uninitialized in the hope that valgrind will catch bad reads.
  88   int dummy;
  89   hash_code dummy_hash = hash_combine_range(&dummy, &dummy);
  90   EXPECT_NE(hash_code(0), dummy_hash);
  91
  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)));
  96
  97   const std::vector<int> vec(begin(arr1), end(arr1));
  98   EXPECT_EQ(arr1_hash, hash_combine_range(vec.begin(), vec.end()));
  99
 100   const std::list<int> list(begin(arr1), end(arr1));
 101   EXPECT_EQ(arr1_hash, hash_combine_range(list.begin(), list.end()));
 102
 103   const std::deque<int> deque(begin(arr1), end(arr1));
 104   EXPECT_EQ(arr1_hash, hash_combine_range(deque.begin(), deque.end()));
 105
 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);
 110
 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);
 115
 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);
 120
 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);
 126 }
 127
 128 TEST(HashingTest, HashCombineRangeLengthDiff) {
 129   // Test that as only the length varies, we compute different hash codes for
 130   // sequences.
 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);
 138   }
 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);
 146   }
 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);
 154   }
 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);
 162   }
 163 }
 164
 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 },
 272 #else
 273 #error This test only supports 64-bit and 32-bit systems.
 274 #endif
 275   };
 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));
 283 #endif
 284     EXPECT_EQ(static_cast<size_t>(golden_data[i].hash),
 285               static_cast<size_t>(hash));
 286   }
 287 }
 288
 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));
 301
 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));
 315
 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));
 325
 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));
 330
 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
 343   };
 344   // Hash a preposterously large integer, both aligned with the buffer and
 345   // misaligned.
 346   const LargeTestInteger li = { {
 347     0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
 348     0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
 349     0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL
 350   } };
 351   // Rotate the storage from 'li'.
 352   const LargeTestInteger l2 = { {
 353     0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL,
 354     0xfefefefededededeULL, 0xafafafafededededULL, 0xffffeeeeddddccccULL,
 355     0xaaaacbcbffffababULL, 0xaaaaaaaaababababULL
 356   } };
 357   const LargeTestInteger l3 = { {
 358     0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL,
 359     0xafafafafededededULL, 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
 360     0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL
 361   } };
 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]));
 376 }
 377
 378 }