X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=unittests%2FADT%2FHashingTest.cpp;h=1b3d0617a5e3de55a1a524ed390ee6d59699e4cb;hb=6bf104b165cec9c14dacf10bf3380eeb32c278d7;hp=19a036cdf53c1d1176dd4efea7de20c4eab40628;hpb=4d628e200f7133e353c38806b57a229ef6ad2ab4;p=oota-llvm.git diff --git a/unittests/ADT/HashingTest.cpp b/unittests/ADT/HashingTest.cpp index 19a036cdf53..1b3d0617a5e 100644 --- a/unittests/ADT/HashingTest.cpp +++ b/unittests/ADT/HashingTest.cpp @@ -30,6 +30,15 @@ void PrintTo(const hash_code &code, std::ostream *os) { // objects. struct LargeTestInteger { uint64_t arr[8]; }; +struct NonPOD { + uint64_t x, y; + NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {} + ~NonPOD() {} + friend hash_code hash_value(const NonPOD &obj) { + return hash_combine(obj.x, obj.y); + } +}; + namespace hashing { namespace detail { template <> struct is_hashable_data : true_type {}; @@ -42,6 +51,11 @@ using namespace llvm; namespace { +enum TestEnumeration { + TE_Foo = 42, + TE_Bar = 43 +}; + TEST(HashingTest, HashValueBasicTest) { int x = 42, y = 43, c = 'x'; void *p = 0; @@ -51,7 +65,9 @@ TEST(HashingTest, HashValueBasicTest) { const volatile int cvi = 71; uintptr_t addr = reinterpret_cast(&y); EXPECT_EQ(hash_value(42), hash_value(x)); + EXPECT_EQ(hash_value(42), hash_value(TE_Foo)); EXPECT_NE(hash_value(42), hash_value(y)); + EXPECT_NE(hash_value(42), hash_value(TE_Bar)); EXPECT_NE(hash_value(42), hash_value(p)); EXPECT_EQ(hash_value(71), hash_value(i)); EXPECT_EQ(hash_value(71), hash_value(ci)); @@ -60,7 +76,9 @@ TEST(HashingTest, HashValueBasicTest) { EXPECT_EQ(hash_value(c), hash_value('x')); EXPECT_EQ(hash_value('4'), hash_value('0' + 4)); EXPECT_EQ(hash_value(addr), hash_value(&y)); +} +TEST(HashingTest, HashValueStdPair) { EXPECT_EQ(hash_combine(42, 43), hash_value(std::make_pair(42, 43))); EXPECT_NE(hash_combine(43, 42), hash_value(std::make_pair(42, 43))); EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43ull))); @@ -73,6 +91,33 @@ TEST(HashingTest, HashValueBasicTest) { hash_value(std::make_pair(42, std::make_pair(43, 44)))); EXPECT_EQ(hash_value(std::make_pair(42, std::make_pair(43, 44))), hash_value(std::make_pair(std::make_pair(42, 43), 44))); + + // Ensure that pairs which have padding bytes *inside* them don't get treated + // this way. + EXPECT_EQ(hash_combine('0', hash_combine(1ull, '2')), + hash_value(std::make_pair('0', std::make_pair(1ull, '2')))); + + // Ensure that non-POD pairs don't explode the traits used. + NonPOD obj1(1, 2), obj2(3, 4), obj3(5, 6); + EXPECT_EQ(hash_combine(obj1, hash_combine(obj2, obj3)), + hash_value(std::make_pair(obj1, std::make_pair(obj2, obj3)))); +} + +TEST(HashingTest, HashValueStdString) { + std::string s = "Hello World!"; + EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size()), hash_value(s)); + EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size() - 1), + hash_value(s.substr(0, s.size() - 1))); + EXPECT_EQ(hash_combine_range(s.c_str() + 1, s.c_str() + s.size() - 1), + hash_value(s.substr(1, s.size() - 2))); + + std::wstring ws = L"Hello Wide World!"; + EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size()), + hash_value(ws)); + EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size() - 1), + hash_value(ws.substr(0, ws.size() - 1))); + EXPECT_EQ(hash_combine_range(ws.c_str() + 1, ws.c_str() + ws.size() - 1), + hash_value(ws.substr(1, ws.size() - 2))); } template T *begin(T (&arr)[N]) { return arr; } @@ -211,64 +256,65 @@ TEST(HashingTest, HashCombineRangeGoldenTest) { { "abababab", 0xee14a29ddf0ce54cULL }, { "ababababababa", 0x38b3ddaada2d52b4ULL }, { "ababababababababababa", 0xd3665364219f2b85ULL }, + { "abababababababababababababababab", 0xa75cd6afbf1bc972ULL }, { "abababababababababababababababab" "abababababababababababababababab" "abababababababababababababababab" "abababababababababababababababab" "abababababababababababababababab", 0x840192d129f7a22bULL } #elif SIZE_MAX == UINT32_MAX - { "a", 0x000000004605f745ULL }, - { "ab", 0x00000000d5f06301ULL }, - { "abc", 0x00000000559fe1eeULL }, - { "abcde", 0x00000000424028d7ULL }, - { "abcdefgh", 0x000000007bb119f8ULL }, - { "abcdefghijklm", 0x00000000edbca513ULL }, - { "abcdefghijklmnopqrstu", 0x000000007c15712eULL }, - { "abcdefghijklmnopqrstuvwxyzabcdef", 0x000000000b3aad66ULL }, - { "abcdefghijklmnopqrstuvwxyzabcdef" - "abcdefghijklmnopqrstuvwxyzghijkl" - "abcdefghijklmnopqrstuvwxyzmnopqr" - "abcdefghijklmnopqrstuvwxyzstuvwx" - "abcdefghijklmnopqrstuvwxyzyzabcd", 0x000000008c758c8bULL }, - { "a", 0x000000004605f745ULL }, - { "aa", 0x00000000dc0a52daULL }, - { "aaa", 0x00000000b309274fULL }, - { "aaaaa", 0x00000000203b5ef6ULL }, - { "aaaaaaaa", 0x00000000a429e18fULL }, - { "aaaaaaaaaaaaa", 0x000000008662070bULL }, - { "aaaaaaaaaaaaaaaaaaaaa", 0x000000003f11151cULL }, - { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0x000000008600fe20ULL }, - { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0x000000004e0e0804ULL }, - { "z", 0x00000000c5e405e9ULL }, - { "zz", 0x00000000a8d8a2c6ULL }, - { "zzz", 0x00000000fc2af672ULL }, - { "zzzzz", 0x0000000047d9efe6ULL }, - { "zzzzzzzz", 0x0000000080d77794ULL }, - { "zzzzzzzzzzzzz", 0x00000000405f93adULL }, - { "zzzzzzzzzzzzzzzzzzzzz", 0x00000000fc72838dULL }, - { "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0x000000007ce160f1ULL }, - { "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" - "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" - "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" - "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" - "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0x00000000aed9ed1bULL }, - { "a", 0x000000004605f745ULL }, - { "ab", 0x00000000d5f06301ULL }, - { "aba", 0x00000000a85cd91bULL }, - { "ababa", 0x000000009e3bb52eULL }, - { "abababab", 0x000000002709b3b9ULL }, - { "ababababababa", 0x000000003a234174ULL }, - { "ababababababababababa", 0x000000005c63e5ceULL }, - { "abababababababababababababababab", 0x0000000013f74334ULL }, - { "abababababababababababababababab" - "abababababababababababababababab" - "abababababababababababababababab" - "abababababababababababababababab" - "abababababababababababababababab", 0x00000000c1a6f135ULL }, + { "a", 0x000000004605f745ULL }, + { "ab", 0x00000000d5f06301ULL }, + { "abc", 0x00000000559fe1eeULL }, + { "abcde", 0x00000000424028d7ULL }, + { "abcdefgh", 0x000000007bb119f8ULL }, + { "abcdefghijklm", 0x00000000edbca513ULL }, + { "abcdefghijklmnopqrstu", 0x000000007c15712eULL }, + { "abcdefghijklmnopqrstuvwxyzabcdef", 0x000000000b3aad66ULL }, + { "abcdefghijklmnopqrstuvwxyzabcdef" + "abcdefghijklmnopqrstuvwxyzghijkl" + "abcdefghijklmnopqrstuvwxyzmnopqr" + "abcdefghijklmnopqrstuvwxyzstuvwx" + "abcdefghijklmnopqrstuvwxyzyzabcd", 0x000000008c758c8bULL }, + { "a", 0x000000004605f745ULL }, + { "aa", 0x00000000dc0a52daULL }, + { "aaa", 0x00000000b309274fULL }, + { "aaaaa", 0x00000000203b5ef6ULL }, + { "aaaaaaaa", 0x00000000a429e18fULL }, + { "aaaaaaaaaaaaa", 0x000000008662070bULL }, + { "aaaaaaaaaaaaaaaaaaaaa", 0x000000003f11151cULL }, + { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0x000000008600fe20ULL }, + { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0x000000004e0e0804ULL }, + { "z", 0x00000000c5e405e9ULL }, + { "zz", 0x00000000a8d8a2c6ULL }, + { "zzz", 0x00000000fc2af672ULL }, + { "zzzzz", 0x0000000047d9efe6ULL }, + { "zzzzzzzz", 0x0000000080d77794ULL }, + { "zzzzzzzzzzzzz", 0x00000000405f93adULL }, + { "zzzzzzzzzzzzzzzzzzzzz", 0x00000000fc72838dULL }, + { "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0x000000007ce160f1ULL }, + { "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" + "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" + "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" + "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" + "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0x00000000aed9ed1bULL }, + { "a", 0x000000004605f745ULL }, + { "ab", 0x00000000d5f06301ULL }, + { "aba", 0x00000000a85cd91bULL }, + { "ababa", 0x000000009e3bb52eULL }, + { "abababab", 0x000000002709b3b9ULL }, + { "ababababababa", 0x000000003a234174ULL }, + { "ababababababababababa", 0x000000005c63e5ceULL }, + { "abababababababababababababababab", 0x0000000013f74334ULL }, + { "abababababababababababababababab" + "abababababababababababababababab" + "abababababababababababababababab" + "abababababababababababababababab" + "abababababababababababababababab", 0x00000000c1a6f135ULL }, #else #error This test only supports 64-bit and 32-bit systems. #endif @@ -299,7 +345,7 @@ TEST(HashingTest, HashCombineBasicTest) { EXPECT_EQ(hash_combine_range(arr1, arr1 + 6), hash_combine(i1, i2, i3, i4, i5, i6)); - // Hashing a sequence of heterogenous types which *happen* to all produce the + // Hashing a sequence of heterogeneous types which *happen* to all produce the // same data for hashing produces the same as a range-based hash of the // fundamental values. const size_t s1 = 1024, s2 = 8888, s3 = 9000000;