X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Ftest%2FHashTest.cpp;h=01cbf2e39e96f917731706f80b1b212bf5a8b1ea;hb=a60bf0bb374f4b57c0f00cd862e2861e1f381ed0;hp=5b8840f5f24b6d3bc18725a37af7406b3635d0e2;hpb=8035fc11627f1739125066bee3951627adfce61e;p=folly.git diff --git a/folly/test/HashTest.cpp b/folly/test/HashTest.cpp index 5b8840f5..01cbf2e3 100644 --- a/folly/test/HashTest.cpp +++ b/folly/test/HashTest.cpp @@ -1,5 +1,5 @@ /* - * Copyright 2013 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -14,9 +14,9 @@ * limitations under the License. */ -#include "folly/Hash.h" -#include "folly/MapUtil.h" -#include +#include +#include +#include #include #include #include @@ -25,19 +25,25 @@ using namespace folly::hash; TEST(Hash, Fnv32) { const char* s1 = "hello, world!"; - const uint32_t s1_res = 3180823791ul; + const uint32_t s1_res = 3605494790UL; EXPECT_EQ(fnv32(s1), s1_res); EXPECT_EQ(fnv32(s1), fnv32_buf(s1, strlen(s1))); const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~"; - const uint32_t s2_res = 194407565ul; + const uint32_t s2_res = 1270448334UL; EXPECT_EQ(fnv32(s2), s2_res); EXPECT_EQ(fnv32(s2), fnv32_buf(s2, strlen(s2))); const char* s3 = ""; - const uint32_t s3_res = 216613626ul; + const uint32_t s3_res = 2166136261UL; EXPECT_EQ(fnv32(s3), s3_res); EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3))); + + const uint8_t s4_data[] = {0xFF, 0xFF, 0xFF, 0x00}; + const char* s4 = reinterpret_cast(s4_data); + const uint32_t s4_res = 2420936562UL; + EXPECT_EQ(fnv32(s4), s4_res); + EXPECT_EQ(fnv32(s4), fnv32_buf(s4, strlen(s4))); } TEST(Hash, Fnv64) { @@ -56,6 +62,12 @@ TEST(Hash, Fnv64) { EXPECT_EQ(fnv64(s3), s3_res); EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3))); + const uint8_t s4_data[] = {0xFF, 0xFF, 0xFF, 0x00}; + const char* s4 = reinterpret_cast(s4_data); + const uint64_t s4_res = 2787597222566293202ULL; + EXPECT_EQ(fnv64(s4), s4_res); + EXPECT_EQ(fnv64(s4), fnv64_buf(s4, strlen(s4))); + // note: Use fnv64_buf to make a single hash value from multiple // fields/datatypes. const char* t4_a = "E Pluribus"; @@ -122,9 +134,9 @@ void checkTWang(uint64_t r) { TEST(Hash, TWang_Unmix64) { // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1 for (int i = 1; i < 64; i++) { - checkTWang((1U << i) - 1); - checkTWang(1U << i); - checkTWang((1U << i) + 1); + checkTWang((uint64_t(1) << i) - 1); + checkTWang(uint64_t(1) << i); + checkTWang((uint64_t(1) << i) + 1); } } @@ -229,6 +241,39 @@ TEST(Hash, hash_combine) { EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1)); } +TEST(Hash, hash_bool) { + const auto hash = folly::Hash(); + EXPECT_NE(hash(true), hash(false)); +} + +TEST(Hash, hash_bool10) { + const auto hash = folly::Hash(); + std::set values; + for (bool b1 : {false, true}) { + for (bool b2 : {false, true}) { + for (bool b3 : {false, true}) { + for (bool b4 : {false, true}) { + for (bool b5 : {false, true}) { + for (bool b6 : {false, true}) { + for (bool b7 : {false, true}) { + for (bool b8 : {false, true}) { + for (bool b9 : {false, true}) { + for (bool b10 : {false, true}) { + values.insert( + hash(b1, b2, b3, b4, b5, b6, b7, b8, b9, b10)); + } + } + } + } + } + } + } + } + } + } + EXPECT_EQ(values.size(), 1 << 10); +} + TEST(Hash, std_tuple) { typedef std::tuple tuple3; tuple3 t(42, "foo", 1); @@ -238,6 +283,59 @@ TEST(Hash, std_tuple) { EXPECT_EQ("bar", m[t]); } +TEST(Hash, enum_type) { + const auto hash = folly::Hash(); + + enum class Enum32 : int32_t { Foo, Bar }; + EXPECT_EQ(hash(static_cast(Enum32::Foo)), hash(Enum32::Foo)); + EXPECT_EQ(hash(static_cast(Enum32::Bar)), hash(Enum32::Bar)); + EXPECT_NE(hash(Enum32::Foo), hash(Enum32::Bar)); + + std::unordered_map m32; + m32[Enum32::Foo] = "foo"; + EXPECT_EQ("foo", m32[Enum32::Foo]); + + enum class Enum64 : int64_t { Foo, Bar }; + EXPECT_EQ(hash(static_cast(Enum64::Foo)), hash(Enum64::Foo)); + EXPECT_EQ(hash(static_cast(Enum64::Bar)), hash(Enum64::Bar)); + EXPECT_NE(hash(Enum64::Foo), hash(Enum64::Bar)); + + std::unordered_map m64; + m64[Enum64::Foo] = "foo"; + EXPECT_EQ("foo", m64[Enum64::Foo]); +} + +TEST(Hash, pair_folly_hash) { + typedef std::pair pair2; + pair2 p(42, 1); + + std::unordered_map m; + m[p] = "bar"; + EXPECT_EQ("bar", m[p]); +} + +TEST(Hash, tuple_folly_hash) { + typedef std::tuple tuple3; + tuple3 t(42, 1, 1); + + std::unordered_map m; + m[t] = "bar"; + EXPECT_EQ("bar", m[t]); +} + +namespace { +template +size_t hash_vector(const std::vector& v) { + return hash_range(v.begin(), v.end()); +} +} + +TEST(Hash, hash_range) { + EXPECT_EQ(hash_vector({1, 2}), hash_vector({1, 2})); + EXPECT_NE(hash_vector({2, 1}), hash_vector({1, 2})); + EXPECT_EQ(hash_vector({}), hash_vector({})); +} + TEST(Hash, std_tuple_different_hash) { typedef std::tuple tuple3; tuple3 t1(42, "foo", 1); @@ -249,3 +347,32 @@ TEST(Hash, std_tuple_different_hash) { EXPECT_NE(std::hash()(t1), std::hash()(t3)); } + +TEST(Hash, Strings) { + using namespace folly; + + StringPiece a1 = "10050517", b1 = "51107032", + a2 = "10050518", b2 = "51107033", + a3 = "10050519", b3 = "51107034", + a4 = "10050525", b4 = "51107040"; + Range w1 = range(L"10050517"), w2 = range(L"51107032"), + w3 = range(L"10050518"), w4 = range(L"51107033"); + Hash h2; + EXPECT_NE(h2(a1), h2(b1)); + EXPECT_NE(h2(a1), h2(b1)); + EXPECT_NE(h2(a2), h2(b2)); + EXPECT_NE(h2(a3), h2(b3)); + EXPECT_NE(h2(ByteRange(a1)), h2(ByteRange(b1))); + EXPECT_NE(h2(ByteRange(a2)), h2(ByteRange(b2))); + EXPECT_NE(h2(ByteRange(a3)), h2(ByteRange(b3))); + EXPECT_NE(h2(ByteRange(a4)), h2(ByteRange(b4))); + EXPECT_NE(h2(w1), h2(w2)); + EXPECT_NE(h2(w1), h2(w3)); + EXPECT_NE(h2(w2), h2(w4)); + + // Check compatibility with std::string. + EXPECT_EQ(h2(a1), h2(a1.str())); + EXPECT_EQ(h2(a2), h2(a2.str())); + EXPECT_EQ(h2(a3), h2(a3.str())); + EXPECT_EQ(h2(a4), h2(a4.str())); +}