From: Yedidya Feldblum Date: Tue, 24 Oct 2017 21:12:03 +0000 (-0700) Subject: Move folly/Hash.h to folly/hash/, leaving a shim X-Git-Tag: v2017.10.30.00~20 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=commitdiff_plain;h=37335efb4659f1389db145a485f8d663d343261f Move folly/Hash.h to folly/hash/, leaving a shim Summary: [Folly] Move `folly/Hash.h` to `folly/hash/`, leaving a shim. Reviewed By: Orvid Differential Revision: D6132955 fbshipit-source-id: dc789e9c6daa28116be6a5d83c3cfbb40e247114 --- diff --git a/folly/Hash.h b/folly/Hash.h index 5253975a..916dfba8 100644 --- a/folly/Hash.h +++ b/folly/Hash.h @@ -16,504 +16,5 @@ #pragma once -#include -#include -#include -#include -#include -#include -#include - -#include -#include -#include -#include - -/* - * Various hashing functions. - */ - -namespace folly { namespace hash { - -// This is a general-purpose way to create a single hash from multiple -// hashable objects. hash_combine_generic takes a class Hasher implementing -// hash; hash_combine uses a default hasher StdHasher that uses std::hash. -// hash_combine_generic hashes each argument and combines those hashes in -// an order-dependent way to yield a new hash. - - -// This is the Hash128to64 function from Google's cityhash (available -// under the MIT License). We use it to reduce multiple 64 bit hashes -// into a single hash. -inline uint64_t hash_128_to_64(const uint64_t upper, const uint64_t lower) { - // Murmur-inspired hashing. - const uint64_t kMul = 0x9ddfea08eb382d69ULL; - uint64_t a = (lower ^ upper) * kMul; - a ^= (a >> 47); - uint64_t b = (upper ^ a) * kMul; - b ^= (b >> 47); - b *= kMul; - return b; -} - -// Never used, but gcc demands it. -template -inline size_t hash_combine_generic() { - return 0; -} - -template < - class Iter, - class Hash = std::hash::value_type>> -uint64_t hash_range(Iter begin, - Iter end, - uint64_t hash = 0, - Hash hasher = Hash()) { - for (; begin != end; ++begin) { - hash = hash_128_to_64(hash, hasher(*begin)); - } - return hash; -} - -inline uint32_t twang_32from64(uint64_t key); - -template -size_t hash_combine_generic(const T& t, const Ts&... ts) { - size_t seed = Hasher::hash(t); - if (sizeof...(ts) == 0) { - return seed; - } - size_t remainder = hash_combine_generic(ts...); - /* static */ if (sizeof(size_t) == sizeof(uint32_t)) { - return twang_32from64((uint64_t(seed) << 32) | remainder); - } else { - return static_cast(hash_128_to_64(seed, remainder)); - } -} - -// Simply uses std::hash to hash. Note that std::hash is not guaranteed -// to be a very good hash function; provided std::hash doesn't collide on -// the individual inputs, you are fine, but that won't be true for, say, -// strings or pairs -class StdHasher { - public: - template - static size_t hash(const T& t) { - return std::hash()(t); - } -}; - -template -size_t hash_combine(const T& t, const Ts&... ts) { - return hash_combine_generic(t, ts...); -} - -////////////////////////////////////////////////////////////////////// - -/* - * Thomas Wang 64 bit mix hash function - */ - -inline uint64_t twang_mix64(uint64_t key) { - key = (~key) + (key << 21); // key *= (1 << 21) - 1; key -= 1; - key = key ^ (key >> 24); - key = key + (key << 3) + (key << 8); // key *= 1 + (1 << 3) + (1 << 8) - key = key ^ (key >> 14); - key = key + (key << 2) + (key << 4); // key *= 1 + (1 << 2) + (1 << 4) - key = key ^ (key >> 28); - key = key + (key << 31); // key *= 1 + (1 << 31) - return key; -} - -/* - * Inverse of twang_mix64 - * - * Note that twang_unmix64 is significantly slower than twang_mix64. - */ - -inline uint64_t twang_unmix64(uint64_t key) { - // See the comments in jenkins_rev_unmix32 for an explanation as to how this - // was generated - key *= 4611686016279904257U; - key ^= (key >> 28) ^ (key >> 56); - key *= 14933078535860113213U; - key ^= (key >> 14) ^ (key >> 28) ^ (key >> 42) ^ (key >> 56); - key *= 15244667743933553977U; - key ^= (key >> 24) ^ (key >> 48); - key = (key + 1) * 9223367638806167551U; - return key; -} - -/* - * Thomas Wang downscaling hash function - */ - -inline uint32_t twang_32from64(uint64_t key) { - key = (~key) + (key << 18); - key = key ^ (key >> 31); - key = key * 21; - key = key ^ (key >> 11); - key = key + (key << 6); - key = key ^ (key >> 22); - return (uint32_t) key; -} - -/* - * Robert Jenkins' reversible 32 bit mix hash function - */ - -inline uint32_t jenkins_rev_mix32(uint32_t key) { - key += (key << 12); // key *= (1 + (1 << 12)) - key ^= (key >> 22); - key += (key << 4); // key *= (1 + (1 << 4)) - key ^= (key >> 9); - key += (key << 10); // key *= (1 + (1 << 10)) - key ^= (key >> 2); - // key *= (1 + (1 << 7)) * (1 + (1 << 12)) - key += (key << 7); - key += (key << 12); - return key; -} - -/* - * Inverse of jenkins_rev_mix32 - * - * Note that jenkinks_rev_unmix32 is significantly slower than - * jenkins_rev_mix32. - */ - -inline uint32_t jenkins_rev_unmix32(uint32_t key) { - // These are the modular multiplicative inverses (in Z_2^32) of the - // multiplication factors in jenkins_rev_mix32, in reverse order. They were - // computed using the Extended Euclidean algorithm, see - // http://en.wikipedia.org/wiki/Modular_multiplicative_inverse - key *= 2364026753U; - - // The inverse of a ^= (a >> n) is - // b = a - // for (int i = n; i < 32; i += n) { - // b ^= (a >> i); - // } - key ^= - (key >> 2) ^ (key >> 4) ^ (key >> 6) ^ (key >> 8) ^ - (key >> 10) ^ (key >> 12) ^ (key >> 14) ^ (key >> 16) ^ - (key >> 18) ^ (key >> 20) ^ (key >> 22) ^ (key >> 24) ^ - (key >> 26) ^ (key >> 28) ^ (key >> 30); - key *= 3222273025U; - key ^= (key >> 9) ^ (key >> 18) ^ (key >> 27); - key *= 4042322161U; - key ^= (key >> 22); - key *= 16773121U; - return key; -} - -/* - * Fowler / Noll / Vo (FNV) Hash - * http://www.isthe.com/chongo/tech/comp/fnv/ - */ - -const uint32_t FNV_32_HASH_START = 2166136261UL; -const uint64_t FNV_64_HASH_START = 14695981039346656037ULL; -const uint64_t FNVA_64_HASH_START = 14695981039346656037ULL; - -inline uint32_t fnv32(const char* buf, uint32_t hash = FNV_32_HASH_START) { - // forcing signed char, since other platforms can use unsigned - const signed char* s = reinterpret_cast(buf); - - for (; *s; ++s) { - hash += (hash << 1) + (hash << 4) + (hash << 7) + - (hash << 8) + (hash << 24); - hash ^= *s; - } - return hash; -} - -inline uint32_t fnv32_buf(const void* buf, - size_t n, - uint32_t hash = FNV_32_HASH_START) { - // forcing signed char, since other platforms can use unsigned - const signed char* char_buf = reinterpret_cast(buf); - - for (size_t i = 0; i < n; ++i) { - hash += (hash << 1) + (hash << 4) + (hash << 7) + - (hash << 8) + (hash << 24); - hash ^= char_buf[i]; - } - - return hash; -} - -inline uint32_t fnv32(const std::string& str, - uint32_t hash = FNV_32_HASH_START) { - return fnv32_buf(str.data(), str.size(), hash); -} - -inline uint64_t fnv64(const char* buf, uint64_t hash = FNV_64_HASH_START) { - // forcing signed char, since other platforms can use unsigned - const signed char* s = reinterpret_cast(buf); - - for (; *s; ++s) { - hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + - (hash << 8) + (hash << 40); - hash ^= *s; - } - return hash; -} - -inline uint64_t fnv64_buf(const void* buf, - size_t n, - uint64_t hash = FNV_64_HASH_START) { - // forcing signed char, since other platforms can use unsigned - const signed char* char_buf = reinterpret_cast(buf); - - for (size_t i = 0; i < n; ++i) { - hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + - (hash << 8) + (hash << 40); - hash ^= char_buf[i]; - } - return hash; -} - -inline uint64_t fnv64(const std::string& str, - uint64_t hash = FNV_64_HASH_START) { - return fnv64_buf(str.data(), str.size(), hash); -} - -inline uint64_t fnva64_buf(const void* buf, - size_t n, - uint64_t hash = FNVA_64_HASH_START) { - const uint8_t* char_buf = reinterpret_cast(buf); - - for (size_t i = 0; i < n; ++i) { - hash ^= char_buf[i]; - hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + - (hash << 8) + (hash << 40); - } - return hash; -} - -inline uint64_t fnva64(const std::string& str, - uint64_t hash = FNVA_64_HASH_START) { - return fnva64_buf(str.data(), str.size(), hash); -} - -/* - * Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html - */ - -#define get16bits(d) folly::loadUnaligned(d) - -inline uint32_t hsieh_hash32_buf(const void* buf, size_t len) { - // forcing signed char, since other platforms can use unsigned - const unsigned char* s = reinterpret_cast(buf); - uint32_t hash = static_cast(len); - uint32_t tmp; - size_t rem; - - if (len <= 0 || buf == nullptr) { - return 0; - } - - rem = len & 3; - len >>= 2; - - /* Main loop */ - for (;len > 0; len--) { - hash += get16bits (s); - tmp = (get16bits (s+2) << 11) ^ hash; - hash = (hash << 16) ^ tmp; - s += 2*sizeof (uint16_t); - hash += hash >> 11; - } - - /* Handle end cases */ - switch (rem) { - case 3: - hash += get16bits(s); - hash ^= hash << 16; - hash ^= s[sizeof (uint16_t)] << 18; - hash += hash >> 11; - break; - case 2: - hash += get16bits(s); - hash ^= hash << 11; - hash += hash >> 17; - break; - case 1: - hash += *s; - hash ^= hash << 10; - hash += hash >> 1; - } - - /* Force "avalanching" of final 127 bits */ - hash ^= hash << 3; - hash += hash >> 5; - hash ^= hash << 4; - hash += hash >> 17; - hash ^= hash << 25; - hash += hash >> 6; - - return hash; -}; - -#undef get16bits - -inline uint32_t hsieh_hash32(const char* s) { - return hsieh_hash32_buf(s, std::strlen(s)); -} - -inline uint32_t hsieh_hash32_str(const std::string& str) { - return hsieh_hash32_buf(str.data(), str.size()); -} - -////////////////////////////////////////////////////////////////////// - -} // namespace hash - -namespace detail { -struct integral_hasher { - template - size_t operator()(I const& i) const { - static_assert(sizeof(I) <= 8, "input type is too wide"); - if (sizeof(I) <= 4) { // the branch taken is known at compile time - auto const i32 = static_cast(i); // impl accident: sign-extends - auto const u32 = static_cast(i32); - return static_cast(hash::jenkins_rev_mix32(u32)); - } else { - auto const u64 = static_cast(i); - return static_cast(hash::twang_mix64(u64)); - } - } -}; -} // namespace detail - -template -struct hasher; - -struct Hash { - template - size_t operator()(const T& v) const { - return hasher()(v); - } - - template - size_t operator()(const T& t, const Ts&... ts) const { - return hash::hash_128_to_64((*this)(t), (*this)(ts...)); - } -}; - -template <> -struct hasher { - size_t operator()(bool key) const { - // Make sure that all the output bits depend on the input. - return key ? std::numeric_limits::max() : 0; - } -}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> -struct hasher : detail::integral_hasher {}; - -template <> // char is a different type from both signed char and unsigned char -struct hasher : detail::integral_hasher {}; - -template <> struct hasher { - size_t operator()(const std::string& key) const { - return static_cast( - hash::SpookyHashV2::Hash64(key.data(), key.size(), 0)); - } -}; - -template -struct hasher::value, void>::type> { - size_t operator()(T key) const { - return Hash()(static_cast::type>(key)); - } -}; - -template -struct hasher> { - size_t operator()(const std::pair& key) const { - return Hash()(key.first, key.second); - } -}; - -template -struct hasher> { - size_t operator() (const std::tuple& key) const { - return applyTuple(Hash(), key); - } -}; - -// recursion -template -struct TupleHasher { - size_t operator()(std::tuple const& key) const { - return hash::hash_combine( - TupleHasher()(key), - std::get(key)); - } -}; - -// base -template -struct TupleHasher<0, Ts...> { - size_t operator()(std::tuple const& key) const { - // we could do std::hash here directly, but hash_combine hides all the - // ugly templating implicitly - return hash::hash_combine(std::get<0>(key)); - } -}; - -} // namespace folly - -// Custom hash functions. -namespace std { - // Hash function for pairs. Requires default hash functions for both - // items in the pair. - template - struct hash > { - public: - size_t operator()(const std::pair& x) const { - return folly::hash::hash_combine(x.first, x.second); - } - }; - - // Hash function for tuples. Requires default hash functions for all types. - template - struct hash> { - size_t operator()(std::tuple const& key) const { - folly::TupleHasher< - std::tuple_size>::value - 1, // start index - Ts...> hasher; - - return hasher(key); - } - }; -} // namespace std +// shims: +#include diff --git a/folly/Makefile.am b/folly/Makefile.am index 7d28d8c0..bb515379 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -228,6 +228,7 @@ nobase_follyinclude_HEADERS = \ futures/test/TestExecutor.h \ hash/Checksum.h \ hash/detail/ChecksumDetail.h \ + hash/Hash.h \ hash/SpookyHashV1.h \ hash/SpookyHashV2.h \ gen/Base.h \ diff --git a/folly/compression/test/CompressionTest.cpp b/folly/compression/test/CompressionTest.cpp index 4bbf5027..b0a2b22b 100644 --- a/folly/compression/test/CompressionTest.cpp +++ b/folly/compression/test/CompressionTest.cpp @@ -27,10 +27,10 @@ #include #include -#include #include #include #include +#include #include #include diff --git a/folly/concurrency/test/ConcurrentHashMapTest.cpp b/folly/concurrency/test/ConcurrentHashMapTest.cpp index cf283c41..32b3d8ae 100644 --- a/folly/concurrency/test/ConcurrentHashMapTest.cpp +++ b/folly/concurrency/test/ConcurrentHashMapTest.cpp @@ -17,8 +17,8 @@ #include #include -#include #include +#include #include #include diff --git a/folly/experimental/test/StringKeyedTest.cpp b/folly/experimental/test/StringKeyedTest.cpp index b6744459..072500b5 100644 --- a/folly/experimental/test/StringKeyedTest.cpp +++ b/folly/experimental/test/StringKeyedTest.cpp @@ -25,8 +25,8 @@ #include -#include #include +#include #include #include diff --git a/folly/hash/Hash.h b/folly/hash/Hash.h new file mode 100644 index 00000000..5253975a --- /dev/null +++ b/folly/hash/Hash.h @@ -0,0 +1,519 @@ +/* + * 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. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/* + * Various hashing functions. + */ + +namespace folly { namespace hash { + +// This is a general-purpose way to create a single hash from multiple +// hashable objects. hash_combine_generic takes a class Hasher implementing +// hash; hash_combine uses a default hasher StdHasher that uses std::hash. +// hash_combine_generic hashes each argument and combines those hashes in +// an order-dependent way to yield a new hash. + + +// This is the Hash128to64 function from Google's cityhash (available +// under the MIT License). We use it to reduce multiple 64 bit hashes +// into a single hash. +inline uint64_t hash_128_to_64(const uint64_t upper, const uint64_t lower) { + // Murmur-inspired hashing. + const uint64_t kMul = 0x9ddfea08eb382d69ULL; + uint64_t a = (lower ^ upper) * kMul; + a ^= (a >> 47); + uint64_t b = (upper ^ a) * kMul; + b ^= (b >> 47); + b *= kMul; + return b; +} + +// Never used, but gcc demands it. +template +inline size_t hash_combine_generic() { + return 0; +} + +template < + class Iter, + class Hash = std::hash::value_type>> +uint64_t hash_range(Iter begin, + Iter end, + uint64_t hash = 0, + Hash hasher = Hash()) { + for (; begin != end; ++begin) { + hash = hash_128_to_64(hash, hasher(*begin)); + } + return hash; +} + +inline uint32_t twang_32from64(uint64_t key); + +template +size_t hash_combine_generic(const T& t, const Ts&... ts) { + size_t seed = Hasher::hash(t); + if (sizeof...(ts) == 0) { + return seed; + } + size_t remainder = hash_combine_generic(ts...); + /* static */ if (sizeof(size_t) == sizeof(uint32_t)) { + return twang_32from64((uint64_t(seed) << 32) | remainder); + } else { + return static_cast(hash_128_to_64(seed, remainder)); + } +} + +// Simply uses std::hash to hash. Note that std::hash is not guaranteed +// to be a very good hash function; provided std::hash doesn't collide on +// the individual inputs, you are fine, but that won't be true for, say, +// strings or pairs +class StdHasher { + public: + template + static size_t hash(const T& t) { + return std::hash()(t); + } +}; + +template +size_t hash_combine(const T& t, const Ts&... ts) { + return hash_combine_generic(t, ts...); +} + +////////////////////////////////////////////////////////////////////// + +/* + * Thomas Wang 64 bit mix hash function + */ + +inline uint64_t twang_mix64(uint64_t key) { + key = (~key) + (key << 21); // key *= (1 << 21) - 1; key -= 1; + key = key ^ (key >> 24); + key = key + (key << 3) + (key << 8); // key *= 1 + (1 << 3) + (1 << 8) + key = key ^ (key >> 14); + key = key + (key << 2) + (key << 4); // key *= 1 + (1 << 2) + (1 << 4) + key = key ^ (key >> 28); + key = key + (key << 31); // key *= 1 + (1 << 31) + return key; +} + +/* + * Inverse of twang_mix64 + * + * Note that twang_unmix64 is significantly slower than twang_mix64. + */ + +inline uint64_t twang_unmix64(uint64_t key) { + // See the comments in jenkins_rev_unmix32 for an explanation as to how this + // was generated + key *= 4611686016279904257U; + key ^= (key >> 28) ^ (key >> 56); + key *= 14933078535860113213U; + key ^= (key >> 14) ^ (key >> 28) ^ (key >> 42) ^ (key >> 56); + key *= 15244667743933553977U; + key ^= (key >> 24) ^ (key >> 48); + key = (key + 1) * 9223367638806167551U; + return key; +} + +/* + * Thomas Wang downscaling hash function + */ + +inline uint32_t twang_32from64(uint64_t key) { + key = (~key) + (key << 18); + key = key ^ (key >> 31); + key = key * 21; + key = key ^ (key >> 11); + key = key + (key << 6); + key = key ^ (key >> 22); + return (uint32_t) key; +} + +/* + * Robert Jenkins' reversible 32 bit mix hash function + */ + +inline uint32_t jenkins_rev_mix32(uint32_t key) { + key += (key << 12); // key *= (1 + (1 << 12)) + key ^= (key >> 22); + key += (key << 4); // key *= (1 + (1 << 4)) + key ^= (key >> 9); + key += (key << 10); // key *= (1 + (1 << 10)) + key ^= (key >> 2); + // key *= (1 + (1 << 7)) * (1 + (1 << 12)) + key += (key << 7); + key += (key << 12); + return key; +} + +/* + * Inverse of jenkins_rev_mix32 + * + * Note that jenkinks_rev_unmix32 is significantly slower than + * jenkins_rev_mix32. + */ + +inline uint32_t jenkins_rev_unmix32(uint32_t key) { + // These are the modular multiplicative inverses (in Z_2^32) of the + // multiplication factors in jenkins_rev_mix32, in reverse order. They were + // computed using the Extended Euclidean algorithm, see + // http://en.wikipedia.org/wiki/Modular_multiplicative_inverse + key *= 2364026753U; + + // The inverse of a ^= (a >> n) is + // b = a + // for (int i = n; i < 32; i += n) { + // b ^= (a >> i); + // } + key ^= + (key >> 2) ^ (key >> 4) ^ (key >> 6) ^ (key >> 8) ^ + (key >> 10) ^ (key >> 12) ^ (key >> 14) ^ (key >> 16) ^ + (key >> 18) ^ (key >> 20) ^ (key >> 22) ^ (key >> 24) ^ + (key >> 26) ^ (key >> 28) ^ (key >> 30); + key *= 3222273025U; + key ^= (key >> 9) ^ (key >> 18) ^ (key >> 27); + key *= 4042322161U; + key ^= (key >> 22); + key *= 16773121U; + return key; +} + +/* + * Fowler / Noll / Vo (FNV) Hash + * http://www.isthe.com/chongo/tech/comp/fnv/ + */ + +const uint32_t FNV_32_HASH_START = 2166136261UL; +const uint64_t FNV_64_HASH_START = 14695981039346656037ULL; +const uint64_t FNVA_64_HASH_START = 14695981039346656037ULL; + +inline uint32_t fnv32(const char* buf, uint32_t hash = FNV_32_HASH_START) { + // forcing signed char, since other platforms can use unsigned + const signed char* s = reinterpret_cast(buf); + + for (; *s; ++s) { + hash += (hash << 1) + (hash << 4) + (hash << 7) + + (hash << 8) + (hash << 24); + hash ^= *s; + } + return hash; +} + +inline uint32_t fnv32_buf(const void* buf, + size_t n, + uint32_t hash = FNV_32_HASH_START) { + // forcing signed char, since other platforms can use unsigned + const signed char* char_buf = reinterpret_cast(buf); + + for (size_t i = 0; i < n; ++i) { + hash += (hash << 1) + (hash << 4) + (hash << 7) + + (hash << 8) + (hash << 24); + hash ^= char_buf[i]; + } + + return hash; +} + +inline uint32_t fnv32(const std::string& str, + uint32_t hash = FNV_32_HASH_START) { + return fnv32_buf(str.data(), str.size(), hash); +} + +inline uint64_t fnv64(const char* buf, uint64_t hash = FNV_64_HASH_START) { + // forcing signed char, since other platforms can use unsigned + const signed char* s = reinterpret_cast(buf); + + for (; *s; ++s) { + hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + + (hash << 8) + (hash << 40); + hash ^= *s; + } + return hash; +} + +inline uint64_t fnv64_buf(const void* buf, + size_t n, + uint64_t hash = FNV_64_HASH_START) { + // forcing signed char, since other platforms can use unsigned + const signed char* char_buf = reinterpret_cast(buf); + + for (size_t i = 0; i < n; ++i) { + hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + + (hash << 8) + (hash << 40); + hash ^= char_buf[i]; + } + return hash; +} + +inline uint64_t fnv64(const std::string& str, + uint64_t hash = FNV_64_HASH_START) { + return fnv64_buf(str.data(), str.size(), hash); +} + +inline uint64_t fnva64_buf(const void* buf, + size_t n, + uint64_t hash = FNVA_64_HASH_START) { + const uint8_t* char_buf = reinterpret_cast(buf); + + for (size_t i = 0; i < n; ++i) { + hash ^= char_buf[i]; + hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + + (hash << 8) + (hash << 40); + } + return hash; +} + +inline uint64_t fnva64(const std::string& str, + uint64_t hash = FNVA_64_HASH_START) { + return fnva64_buf(str.data(), str.size(), hash); +} + +/* + * Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html + */ + +#define get16bits(d) folly::loadUnaligned(d) + +inline uint32_t hsieh_hash32_buf(const void* buf, size_t len) { + // forcing signed char, since other platforms can use unsigned + const unsigned char* s = reinterpret_cast(buf); + uint32_t hash = static_cast(len); + uint32_t tmp; + size_t rem; + + if (len <= 0 || buf == nullptr) { + return 0; + } + + rem = len & 3; + len >>= 2; + + /* Main loop */ + for (;len > 0; len--) { + hash += get16bits (s); + tmp = (get16bits (s+2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + s += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: + hash += get16bits(s); + hash ^= hash << 16; + hash ^= s[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: + hash += get16bits(s); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: + hash += *s; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +}; + +#undef get16bits + +inline uint32_t hsieh_hash32(const char* s) { + return hsieh_hash32_buf(s, std::strlen(s)); +} + +inline uint32_t hsieh_hash32_str(const std::string& str) { + return hsieh_hash32_buf(str.data(), str.size()); +} + +////////////////////////////////////////////////////////////////////// + +} // namespace hash + +namespace detail { +struct integral_hasher { + template + size_t operator()(I const& i) const { + static_assert(sizeof(I) <= 8, "input type is too wide"); + if (sizeof(I) <= 4) { // the branch taken is known at compile time + auto const i32 = static_cast(i); // impl accident: sign-extends + auto const u32 = static_cast(i32); + return static_cast(hash::jenkins_rev_mix32(u32)); + } else { + auto const u64 = static_cast(i); + return static_cast(hash::twang_mix64(u64)); + } + } +}; +} // namespace detail + +template +struct hasher; + +struct Hash { + template + size_t operator()(const T& v) const { + return hasher()(v); + } + + template + size_t operator()(const T& t, const Ts&... ts) const { + return hash::hash_128_to_64((*this)(t), (*this)(ts...)); + } +}; + +template <> +struct hasher { + size_t operator()(bool key) const { + // Make sure that all the output bits depend on the input. + return key ? std::numeric_limits::max() : 0; + } +}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> +struct hasher : detail::integral_hasher {}; + +template <> // char is a different type from both signed char and unsigned char +struct hasher : detail::integral_hasher {}; + +template <> struct hasher { + size_t operator()(const std::string& key) const { + return static_cast( + hash::SpookyHashV2::Hash64(key.data(), key.size(), 0)); + } +}; + +template +struct hasher::value, void>::type> { + size_t operator()(T key) const { + return Hash()(static_cast::type>(key)); + } +}; + +template +struct hasher> { + size_t operator()(const std::pair& key) const { + return Hash()(key.first, key.second); + } +}; + +template +struct hasher> { + size_t operator() (const std::tuple& key) const { + return applyTuple(Hash(), key); + } +}; + +// recursion +template +struct TupleHasher { + size_t operator()(std::tuple const& key) const { + return hash::hash_combine( + TupleHasher()(key), + std::get(key)); + } +}; + +// base +template +struct TupleHasher<0, Ts...> { + size_t operator()(std::tuple const& key) const { + // we could do std::hash here directly, but hash_combine hides all the + // ugly templating implicitly + return hash::hash_combine(std::get<0>(key)); + } +}; + +} // namespace folly + +// Custom hash functions. +namespace std { + // Hash function for pairs. Requires default hash functions for both + // items in the pair. + template + struct hash > { + public: + size_t operator()(const std::pair& x) const { + return folly::hash::hash_combine(x.first, x.second); + } + }; + + // Hash function for tuples. Requires default hash functions for all types. + template + struct hash> { + size_t operator()(std::tuple const& key) const { + folly::TupleHasher< + std::tuple_size>::value - 1, // start index + Ts...> hasher; + + return hasher(key); + } + }; +} // namespace std diff --git a/folly/hash/test/ChecksumTest.cpp b/folly/hash/test/ChecksumTest.cpp index e5e613c6..05ac6e59 100644 --- a/folly/hash/test/ChecksumTest.cpp +++ b/folly/hash/test/ChecksumTest.cpp @@ -19,7 +19,7 @@ #include #include -#include +#include #include #include #include diff --git a/folly/hash/test/HashBenchmark.cpp b/folly/hash/test/HashBenchmark.cpp new file mode 100644 index 00000000..bb49a52b --- /dev/null +++ b/folly/hash/test/HashBenchmark.cpp @@ -0,0 +1,146 @@ +/* + * 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. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include +#include +#include +#include +#include + +#include + +#include +#include +#include +#include + +namespace detail { + +std::vector randomBytes(size_t n) { + std::vector ret(n); + std::default_random_engine rng(1729); // Deterministic seed. + std::uniform_int_distribution dist(0, 255); + std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); }); + return ret; +} + +std::vector benchData = randomBytes(1 << 20); // 1MiB, fits in cache. + +template +void bmHasher(Hasher hasher, size_t k, size_t iters) { + CHECK_LE(k, benchData.size()); + for (size_t i = 0, pos = 0; i < iters; ++i, ++pos) { + if (pos == benchData.size() - k + 1) { pos = 0; } + folly::doNotOptimizeAway(hasher(benchData.data() + pos, k)); + } +} + +template +void addHashBenchmark(const std::string& name) { + static std::deque names; + + for (size_t i = 0; i < 16; ++i) { + auto k = size_t(1) << i; + names.emplace_back(folly::sformat("{}: k=2^{}",name, i)); + folly::addBenchmark(__FILE__, names.back().c_str(), + [=] (unsigned iters) { + Hasher hasher; + bmHasher(hasher, k, iters); + return iters; + }); + } + + /* Draw line. */ + folly::addBenchmark(__FILE__, "-", [] () { return 0; }); +} + +struct SpookyHashV2 { + uint64_t operator()(const uint8_t* data, size_t size) const { + return folly::hash::SpookyHashV2::Hash64(data, size, 0); + } +}; + +struct FNV64 { + uint64_t operator()(const uint8_t* data, size_t size) const { + return folly::hash::fnv64_buf(data, size); + } +}; + +} // namespace detail + +int main(int argc, char** argv) { + gflags::ParseCommandLineFlags(&argc, &argv, true); + google::InitGoogleLogging(argv[0]); + + std::deque names; // Backing for benchmark names. + +#define BENCHMARK_HASH(HASHER) \ + detail::addHashBenchmark(FB_STRINGIZE(HASHER)); + + BENCHMARK_HASH(SpookyHashV2); + BENCHMARK_HASH(FNV64); + +#undef BENCHMARK_HASH + + folly::runBenchmarks(); + + return 0; +} + +#if 0 +Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz +$ hash_benchmark --bm_min_usec=100000 +============================================================================ +folly/test/HashBenchmark.cpp relative time/iter iters/s +============================================================================ +SpookyHashV2: k=2^0 11.67ns 85.66M +SpookyHashV2: k=2^1 12.49ns 80.07M +SpookyHashV2: k=2^2 11.87ns 84.22M +SpookyHashV2: k=2^3 12.36ns 80.89M +SpookyHashV2: k=2^4 21.47ns 46.58M +SpookyHashV2: k=2^5 22.21ns 45.02M +SpookyHashV2: k=2^6 31.47ns 31.78M +SpookyHashV2: k=2^7 49.86ns 20.05M +SpookyHashV2: k=2^8 69.56ns 14.38M +SpookyHashV2: k=2^9 102.99ns 9.71M +SpookyHashV2: k=2^10 153.72ns 6.51M +SpookyHashV2: k=2^11 271.43ns 3.68M +SpookyHashV2: k=2^12 498.85ns 2.00M +SpookyHashV2: k=2^13 961.55ns 1.04M +SpookyHashV2: k=2^14 1.88us 532.57K +SpookyHashV2: k=2^15 3.73us 268.42K +-------------------------------------------------------------------------- +FNV64: k=2^0 2.67ns 374.83M +FNV64: k=2^1 4.67ns 214.24M +FNV64: k=2^2 10.30ns 97.07M +FNV64: k=2^3 23.16ns 43.17M +FNV64: k=2^4 48.77ns 20.51M +FNV64: k=2^5 100.45ns 9.96M +FNV64: k=2^6 201.74ns 4.96M +FNV64: k=2^7 399.42ns 2.50M +FNV64: k=2^8 801.64ns 1.25M +FNV64: k=2^9 1.59us 627.32K +FNV64: k=2^10 3.19us 313.51K +FNV64: k=2^11 6.38us 156.80K +FNV64: k=2^12 12.75us 78.45K +FNV64: k=2^13 25.49us 39.23K +FNV64: k=2^14 50.98us 19.62K +FNV64: k=2^15 101.93us 9.81K +---------------------------------------------------------------------------- +============================================================================ +#endif diff --git a/folly/hash/test/HashTest.cpp b/folly/hash/test/HashTest.cpp new file mode 100644 index 00000000..68627002 --- /dev/null +++ b/folly/hash/test/HashTest.cpp @@ -0,0 +1,452 @@ +/* + * 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. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include +#include +#include +#include +#include + +using namespace folly::hash; + +TEST(Hash, Fnv32) { + const char* s1 = "hello, world!"; + 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 = 1270448334UL; + EXPECT_EQ(fnv32(s2), s2_res); + EXPECT_EQ(fnv32(s2), fnv32_buf(s2, strlen(s2))); + + const char* s3 = ""; + 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) { + const char* s1 = "hello, world!"; + const uint64_t s1_res = 13991426986746681734ULL; + EXPECT_EQ(fnv64(s1), s1_res); + EXPECT_EQ(fnv64(s1), fnv64_buf(s1, strlen(s1))); + + const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~"; + const uint64_t s2_res = 6091394665637302478ULL; + EXPECT_EQ(fnv64(s2), s2_res); + EXPECT_EQ(fnv64(s2), fnv64_buf(s2, strlen(s2))); + + const char* s3 = ""; + const uint64_t s3_res = 14695981039346656037ULL; + 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"; + int64_t t4_b = 0xF1E2D3C4B5A69788; + int32_t t4_c = 0xAB12CD34; + const char* t4_d = "Unum"; + uint64_t t4_res = 15571330457339273965ULL; + uint64_t t4_hash1 = fnv64_buf(t4_a, + strlen(t4_a)); + uint64_t t4_hash2 = fnv64_buf(reinterpret_cast(&t4_b), + sizeof(int64_t), + t4_hash1); + uint64_t t4_hash3 = fnv64_buf(reinterpret_cast(&t4_c), + sizeof(int32_t), + t4_hash2); + uint64_t t4_hash4 = fnv64_buf(t4_d, + strlen(t4_d), + t4_hash3); + EXPECT_EQ(t4_hash4, t4_res); + // note: These are probabalistic, not determinate, but c'mon. + // These hash values should be different, or something's not + // working. + EXPECT_NE(t4_hash1, t4_hash4); + EXPECT_NE(t4_hash2, t4_hash4); + EXPECT_NE(t4_hash3, t4_hash4); +} + +TEST(Hash, Hsieh32) { + const char* s1 = "hello, world!"; + const uint32_t s1_res = 2918802987ul; + EXPECT_EQ(hsieh_hash32(s1), s1_res); + EXPECT_EQ(hsieh_hash32(s1), hsieh_hash32_buf(s1, strlen(s1))); + + const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~"; + const uint32_t s2_res = 47373213ul; + EXPECT_EQ(hsieh_hash32(s2), s2_res); + EXPECT_EQ(hsieh_hash32(s2), hsieh_hash32_buf(s2, strlen(s2))); + + const char* s3 = ""; + const uint32_t s3_res = 0; + EXPECT_EQ(hsieh_hash32(s3), s3_res); + EXPECT_EQ(hsieh_hash32(s3), hsieh_hash32_buf(s3, strlen(s3))); +} + +TEST(Hash, TWang_Mix64) { + uint64_t i1 = 0x78a87873e2d31dafULL; + uint64_t i1_res = 3389151152926383528ULL; + EXPECT_EQ(i1_res, twang_mix64(i1)); + EXPECT_EQ(i1, twang_unmix64(i1_res)); + + uint64_t i2 = 0x0123456789abcdefULL; + uint64_t i2_res = 3061460455458984563ull; + EXPECT_EQ(i2_res, twang_mix64(i2)); + EXPECT_EQ(i2, twang_unmix64(i2_res)); +} + +namespace { +void checkTWang(uint64_t r) { + uint64_t result = twang_mix64(r); + EXPECT_EQ(r, twang_unmix64(result)); +} +} // namespace + +TEST(Hash, TWang_Unmix64) { + // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1 + for (int i = 1; i < 64; i++) { + checkTWang((uint64_t(1) << i) - 1); + checkTWang(uint64_t(1) << i); + checkTWang((uint64_t(1) << i) + 1); + } +} + +TEST(Hash, TWang_32From64) { + uint64_t i1 = 0x78a87873e2d31dafULL; + uint32_t i1_res = 1525586863ul; + EXPECT_EQ(twang_32from64(i1), i1_res); + + uint64_t i2 = 0x0123456789abcdefULL; + uint32_t i2_res = 2918899159ul; + EXPECT_EQ(twang_32from64(i2), i2_res); +} + +TEST(Hash, Jenkins_Rev_Mix32) { + uint32_t i1 = 3805486511ul; + uint32_t i1_res = 381808021ul; + EXPECT_EQ(i1_res, jenkins_rev_mix32(i1)); + EXPECT_EQ(i1, jenkins_rev_unmix32(i1_res)); + + uint32_t i2 = 2309737967ul; + uint32_t i2_res = 1834777923ul; + EXPECT_EQ(i2_res, jenkins_rev_mix32(i2)); + EXPECT_EQ(i2, jenkins_rev_unmix32(i2_res)); +} + +namespace { +void checkJenkins(uint32_t r) { + uint32_t result = jenkins_rev_mix32(r); + EXPECT_EQ(r, jenkins_rev_unmix32(result)); +} +} // namespace + +TEST(Hash, Jenkins_Rev_Unmix32) { + // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1 + for (int i = 1; i < 32; i++) { + checkJenkins((1U << i) - 1); + checkJenkins(1U << i); + checkJenkins((1U << i) + 1); + } +} + +TEST(Hash, hasher) { + // Basically just confirms that things compile ok. + std::unordered_map> m; + m.insert(std::make_pair(4, 5)); + EXPECT_EQ(get_default(m, 4), 5); +} + +TEST(Hash, integral_types) { + // Basically just confirms that things compile ok. + std::unordered_set hashes; + folly::Hash hasher; + hashes.insert(hasher((char)1)); + hashes.insert(hasher((signed char)2)); + hashes.insert(hasher((unsigned char)3)); + hashes.insert(hasher((short)4)); + hashes.insert(hasher((signed short)5)); + hashes.insert(hasher((unsigned short)6)); + hashes.insert(hasher((int)7)); + hashes.insert(hasher((signed int)8)); + hashes.insert(hasher((unsigned int)9)); + hashes.insert(hasher((long)10)); + hashes.insert(hasher((signed long)11)); + hashes.insert(hasher((unsigned long)12)); + hashes.insert(hasher((long long)13)); + hashes.insert(hasher((signed long long)14)); + hashes.insert(hasher((unsigned long long)15)); + hashes.insert(hasher((int8_t)16)); + hashes.insert(hasher((uint8_t)17)); + hashes.insert(hasher((int16_t)18)); + hashes.insert(hasher((uint16_t)19)); + hashes.insert(hasher((int32_t)20)); + hashes.insert(hasher((uint32_t)21)); + hashes.insert(hasher((int64_t)22)); + hashes.insert(hasher((uint64_t)23)); + hashes.insert(hasher((size_t)24)); + EXPECT_EQ(24, hashes.size()); +} + +// Not a full hasher since only handles one type +class TestHasher { + public: + static size_t hash(const std::pair& p) { + return p.first + p.second; + } +}; + +template +size_t hash_combine_test(const T& t, const Ts&... ts) { + return hash_combine_generic(t, ts...); +} + +TEST(Hash, pair) { + auto a = std::make_pair(1, 2); + auto b = std::make_pair(3, 4); + auto c = std::make_pair(1, 2); + auto d = std::make_pair(2, 1); + EXPECT_EQ(hash_combine(a), + hash_combine(c)); + EXPECT_NE(hash_combine(b), + hash_combine(c)); + EXPECT_NE(hash_combine(d), + hash_combine(c)); + + // With composition + EXPECT_EQ(hash_combine(a, b), + hash_combine(c, b)); + // Test order dependence + EXPECT_NE(hash_combine(a, b), + hash_combine(b, a)); + + // Test with custom hasher + EXPECT_EQ(hash_combine_test(a), + hash_combine_test(c)); + // 3 + 4 != 1 + 2 + EXPECT_NE(hash_combine_test(b), + hash_combine_test(c)); + // This time, thanks to a terrible hash function, these are equal + EXPECT_EQ(hash_combine_test(d), + hash_combine_test(c)); + // With composition + EXPECT_EQ(hash_combine_test(a, b), + hash_combine_test(c, b)); + // Test order dependence + EXPECT_NE(hash_combine_test(a, b), + hash_combine_test(b, a)); + // Again, 1 + 2 == 2 + 1 + EXPECT_EQ(hash_combine_test(a, b), + hash_combine_test(d, b)); +} + +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); + + std::unordered_map m; + m[t] = "bar"; + 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()); +} +} // namespace + +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); + tuple3 t2(9, "bar", 3); + tuple3 t3(42, "foo", 3); + + EXPECT_NE(std::hash()(t1), + std::hash()(t2)); + 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())); +} + +struct FNVTestParam { + std::string in; + uint64_t out; +}; + +class FNVTest : public ::testing::TestWithParam {}; + +TEST_P(FNVTest, Fnva64Buf) { + EXPECT_EQ(GetParam().out, + fnva64_buf(GetParam().in.data(), GetParam().in.size())); +} + +TEST_P(FNVTest, Fnva64) { + EXPECT_EQ(GetParam().out, fnva64(GetParam().in)); +} + +TEST_P(FNVTest, Fnva64Partial) { + size_t partialLen = GetParam().in.size() / 2; + auto data = GetParam().in.data(); + auto partial = fnva64_buf(data, partialLen); + EXPECT_EQ(GetParam().out, + fnva64_buf( + data + partialLen, GetParam().in.size() - partialLen, partial)); +} + +// Taken from http://www.isthe.com/chongo/src/fnv/test_fnv.c +INSTANTIATE_TEST_CASE_P( + FNVTesting, + FNVTest, + ::testing::Values( + (FNVTestParam){"foobar", // 11 + 0x85944171f73967e8}, + (FNVTestParam){"chongo was here!\n", // 39 + 0x46810940eff5f915}, + (FNVTestParam){"127.0.0.3", // 106, + 0xaabafc7104d91158}, + (FNVTestParam){ + "http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash", // 126 + 0xd9b957fb7fe794c5}, + (FNVTestParam){"http://norvig.com/21-days.html", // 136 + 0x07aaa640476e0b9a})); diff --git a/folly/test/AtomicHashArrayTest.cpp b/folly/test/AtomicHashArrayTest.cpp index 86d8ae5a..2ffb701b 100644 --- a/folly/test/AtomicHashArrayTest.cpp +++ b/folly/test/AtomicHashArrayTest.cpp @@ -21,8 +21,8 @@ #include #include -#include #include +#include #include #include diff --git a/folly/test/ConcurrentSkipListBenchmark.cpp b/folly/test/ConcurrentSkipListBenchmark.cpp index 51f9a9f7..89de974b 100644 --- a/folly/test/ConcurrentSkipListBenchmark.cpp +++ b/folly/test/ConcurrentSkipListBenchmark.cpp @@ -24,8 +24,8 @@ #include #include -#include #include +#include #include #include diff --git a/folly/test/HashBenchmark.cpp b/folly/test/HashBenchmark.cpp deleted file mode 100644 index 8c586aa9..00000000 --- a/folly/test/HashBenchmark.cpp +++ /dev/null @@ -1,146 +0,0 @@ -/* - * 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. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include - -#include -#include -#include -#include -#include - -#include - -#include -#include -#include -#include - -namespace detail { - -std::vector randomBytes(size_t n) { - std::vector ret(n); - std::default_random_engine rng(1729); // Deterministic seed. - std::uniform_int_distribution dist(0, 255); - std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); }); - return ret; -} - -std::vector benchData = randomBytes(1 << 20); // 1MiB, fits in cache. - -template -void bmHasher(Hasher hasher, size_t k, size_t iters) { - CHECK_LE(k, benchData.size()); - for (size_t i = 0, pos = 0; i < iters; ++i, ++pos) { - if (pos == benchData.size() - k + 1) { pos = 0; } - folly::doNotOptimizeAway(hasher(benchData.data() + pos, k)); - } -} - -template -void addHashBenchmark(const std::string& name) { - static std::deque names; - - for (size_t i = 0; i < 16; ++i) { - auto k = size_t(1) << i; - names.emplace_back(folly::sformat("{}: k=2^{}",name, i)); - folly::addBenchmark(__FILE__, names.back().c_str(), - [=] (unsigned iters) { - Hasher hasher; - bmHasher(hasher, k, iters); - return iters; - }); - } - - /* Draw line. */ - folly::addBenchmark(__FILE__, "-", [] () { return 0; }); -} - -struct SpookyHashV2 { - uint64_t operator()(const uint8_t* data, size_t size) const { - return folly::hash::SpookyHashV2::Hash64(data, size, 0); - } -}; - -struct FNV64 { - uint64_t operator()(const uint8_t* data, size_t size) const { - return folly::hash::fnv64_buf(data, size); - } -}; - -} // namespace detail - -int main(int argc, char** argv) { - gflags::ParseCommandLineFlags(&argc, &argv, true); - google::InitGoogleLogging(argv[0]); - - std::deque names; // Backing for benchmark names. - -#define BENCHMARK_HASH(HASHER) \ - detail::addHashBenchmark(FB_STRINGIZE(HASHER)); - - BENCHMARK_HASH(SpookyHashV2); - BENCHMARK_HASH(FNV64); - -#undef BENCHMARK_HASH - - folly::runBenchmarks(); - - return 0; -} - -#if 0 -Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz -$ hash_benchmark --bm_min_usec=100000 -============================================================================ -folly/test/HashBenchmark.cpp relative time/iter iters/s -============================================================================ -SpookyHashV2: k=2^0 11.67ns 85.66M -SpookyHashV2: k=2^1 12.49ns 80.07M -SpookyHashV2: k=2^2 11.87ns 84.22M -SpookyHashV2: k=2^3 12.36ns 80.89M -SpookyHashV2: k=2^4 21.47ns 46.58M -SpookyHashV2: k=2^5 22.21ns 45.02M -SpookyHashV2: k=2^6 31.47ns 31.78M -SpookyHashV2: k=2^7 49.86ns 20.05M -SpookyHashV2: k=2^8 69.56ns 14.38M -SpookyHashV2: k=2^9 102.99ns 9.71M -SpookyHashV2: k=2^10 153.72ns 6.51M -SpookyHashV2: k=2^11 271.43ns 3.68M -SpookyHashV2: k=2^12 498.85ns 2.00M -SpookyHashV2: k=2^13 961.55ns 1.04M -SpookyHashV2: k=2^14 1.88us 532.57K -SpookyHashV2: k=2^15 3.73us 268.42K --------------------------------------------------------------------------- -FNV64: k=2^0 2.67ns 374.83M -FNV64: k=2^1 4.67ns 214.24M -FNV64: k=2^2 10.30ns 97.07M -FNV64: k=2^3 23.16ns 43.17M -FNV64: k=2^4 48.77ns 20.51M -FNV64: k=2^5 100.45ns 9.96M -FNV64: k=2^6 201.74ns 4.96M -FNV64: k=2^7 399.42ns 2.50M -FNV64: k=2^8 801.64ns 1.25M -FNV64: k=2^9 1.59us 627.32K -FNV64: k=2^10 3.19us 313.51K -FNV64: k=2^11 6.38us 156.80K -FNV64: k=2^12 12.75us 78.45K -FNV64: k=2^13 25.49us 39.23K -FNV64: k=2^14 50.98us 19.62K -FNV64: k=2^15 101.93us 9.81K ----------------------------------------------------------------------------- -============================================================================ -#endif diff --git a/folly/test/HashTest.cpp b/folly/test/HashTest.cpp deleted file mode 100644 index 9521aee7..00000000 --- a/folly/test/HashTest.cpp +++ /dev/null @@ -1,452 +0,0 @@ -/* - * 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. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include -#include -#include -#include -#include -#include -#include - -using namespace folly::hash; - -TEST(Hash, Fnv32) { - const char* s1 = "hello, world!"; - 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 = 1270448334UL; - EXPECT_EQ(fnv32(s2), s2_res); - EXPECT_EQ(fnv32(s2), fnv32_buf(s2, strlen(s2))); - - const char* s3 = ""; - 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) { - const char* s1 = "hello, world!"; - const uint64_t s1_res = 13991426986746681734ULL; - EXPECT_EQ(fnv64(s1), s1_res); - EXPECT_EQ(fnv64(s1), fnv64_buf(s1, strlen(s1))); - - const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~"; - const uint64_t s2_res = 6091394665637302478ULL; - EXPECT_EQ(fnv64(s2), s2_res); - EXPECT_EQ(fnv64(s2), fnv64_buf(s2, strlen(s2))); - - const char* s3 = ""; - const uint64_t s3_res = 14695981039346656037ULL; - 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"; - int64_t t4_b = 0xF1E2D3C4B5A69788; - int32_t t4_c = 0xAB12CD34; - const char* t4_d = "Unum"; - uint64_t t4_res = 15571330457339273965ULL; - uint64_t t4_hash1 = fnv64_buf(t4_a, - strlen(t4_a)); - uint64_t t4_hash2 = fnv64_buf(reinterpret_cast(&t4_b), - sizeof(int64_t), - t4_hash1); - uint64_t t4_hash3 = fnv64_buf(reinterpret_cast(&t4_c), - sizeof(int32_t), - t4_hash2); - uint64_t t4_hash4 = fnv64_buf(t4_d, - strlen(t4_d), - t4_hash3); - EXPECT_EQ(t4_hash4, t4_res); - // note: These are probabalistic, not determinate, but c'mon. - // These hash values should be different, or something's not - // working. - EXPECT_NE(t4_hash1, t4_hash4); - EXPECT_NE(t4_hash2, t4_hash4); - EXPECT_NE(t4_hash3, t4_hash4); -} - -TEST(Hash, Hsieh32) { - const char* s1 = "hello, world!"; - const uint32_t s1_res = 2918802987ul; - EXPECT_EQ(hsieh_hash32(s1), s1_res); - EXPECT_EQ(hsieh_hash32(s1), hsieh_hash32_buf(s1, strlen(s1))); - - const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~"; - const uint32_t s2_res = 47373213ul; - EXPECT_EQ(hsieh_hash32(s2), s2_res); - EXPECT_EQ(hsieh_hash32(s2), hsieh_hash32_buf(s2, strlen(s2))); - - const char* s3 = ""; - const uint32_t s3_res = 0; - EXPECT_EQ(hsieh_hash32(s3), s3_res); - EXPECT_EQ(hsieh_hash32(s3), hsieh_hash32_buf(s3, strlen(s3))); -} - -TEST(Hash, TWang_Mix64) { - uint64_t i1 = 0x78a87873e2d31dafULL; - uint64_t i1_res = 3389151152926383528ULL; - EXPECT_EQ(i1_res, twang_mix64(i1)); - EXPECT_EQ(i1, twang_unmix64(i1_res)); - - uint64_t i2 = 0x0123456789abcdefULL; - uint64_t i2_res = 3061460455458984563ull; - EXPECT_EQ(i2_res, twang_mix64(i2)); - EXPECT_EQ(i2, twang_unmix64(i2_res)); -} - -namespace { -void checkTWang(uint64_t r) { - uint64_t result = twang_mix64(r); - EXPECT_EQ(r, twang_unmix64(result)); -} -} // namespace - -TEST(Hash, TWang_Unmix64) { - // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1 - for (int i = 1; i < 64; i++) { - checkTWang((uint64_t(1) << i) - 1); - checkTWang(uint64_t(1) << i); - checkTWang((uint64_t(1) << i) + 1); - } -} - -TEST(Hash, TWang_32From64) { - uint64_t i1 = 0x78a87873e2d31dafULL; - uint32_t i1_res = 1525586863ul; - EXPECT_EQ(twang_32from64(i1), i1_res); - - uint64_t i2 = 0x0123456789abcdefULL; - uint32_t i2_res = 2918899159ul; - EXPECT_EQ(twang_32from64(i2), i2_res); -} - -TEST(Hash, Jenkins_Rev_Mix32) { - uint32_t i1 = 3805486511ul; - uint32_t i1_res = 381808021ul; - EXPECT_EQ(i1_res, jenkins_rev_mix32(i1)); - EXPECT_EQ(i1, jenkins_rev_unmix32(i1_res)); - - uint32_t i2 = 2309737967ul; - uint32_t i2_res = 1834777923ul; - EXPECT_EQ(i2_res, jenkins_rev_mix32(i2)); - EXPECT_EQ(i2, jenkins_rev_unmix32(i2_res)); -} - -namespace { -void checkJenkins(uint32_t r) { - uint32_t result = jenkins_rev_mix32(r); - EXPECT_EQ(r, jenkins_rev_unmix32(result)); -} -} // namespace - -TEST(Hash, Jenkins_Rev_Unmix32) { - // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1 - for (int i = 1; i < 32; i++) { - checkJenkins((1U << i) - 1); - checkJenkins(1U << i); - checkJenkins((1U << i) + 1); - } -} - -TEST(Hash, hasher) { - // Basically just confirms that things compile ok. - std::unordered_map> m; - m.insert(std::make_pair(4, 5)); - EXPECT_EQ(get_default(m, 4), 5); -} - -TEST(Hash, integral_types) { - // Basically just confirms that things compile ok. - std::unordered_set hashes; - folly::Hash hasher; - hashes.insert(hasher((char)1)); - hashes.insert(hasher((signed char)2)); - hashes.insert(hasher((unsigned char)3)); - hashes.insert(hasher((short)4)); - hashes.insert(hasher((signed short)5)); - hashes.insert(hasher((unsigned short)6)); - hashes.insert(hasher((int)7)); - hashes.insert(hasher((signed int)8)); - hashes.insert(hasher((unsigned int)9)); - hashes.insert(hasher((long)10)); - hashes.insert(hasher((signed long)11)); - hashes.insert(hasher((unsigned long)12)); - hashes.insert(hasher((long long)13)); - hashes.insert(hasher((signed long long)14)); - hashes.insert(hasher((unsigned long long)15)); - hashes.insert(hasher((int8_t)16)); - hashes.insert(hasher((uint8_t)17)); - hashes.insert(hasher((int16_t)18)); - hashes.insert(hasher((uint16_t)19)); - hashes.insert(hasher((int32_t)20)); - hashes.insert(hasher((uint32_t)21)); - hashes.insert(hasher((int64_t)22)); - hashes.insert(hasher((uint64_t)23)); - hashes.insert(hasher((size_t)24)); - EXPECT_EQ(24, hashes.size()); -} - -// Not a full hasher since only handles one type -class TestHasher { - public: - static size_t hash(const std::pair& p) { - return p.first + p.second; - } -}; - -template -size_t hash_combine_test(const T& t, const Ts&... ts) { - return hash_combine_generic(t, ts...); -} - -TEST(Hash, pair) { - auto a = std::make_pair(1, 2); - auto b = std::make_pair(3, 4); - auto c = std::make_pair(1, 2); - auto d = std::make_pair(2, 1); - EXPECT_EQ(hash_combine(a), - hash_combine(c)); - EXPECT_NE(hash_combine(b), - hash_combine(c)); - EXPECT_NE(hash_combine(d), - hash_combine(c)); - - // With composition - EXPECT_EQ(hash_combine(a, b), - hash_combine(c, b)); - // Test order dependence - EXPECT_NE(hash_combine(a, b), - hash_combine(b, a)); - - // Test with custom hasher - EXPECT_EQ(hash_combine_test(a), - hash_combine_test(c)); - // 3 + 4 != 1 + 2 - EXPECT_NE(hash_combine_test(b), - hash_combine_test(c)); - // This time, thanks to a terrible hash function, these are equal - EXPECT_EQ(hash_combine_test(d), - hash_combine_test(c)); - // With composition - EXPECT_EQ(hash_combine_test(a, b), - hash_combine_test(c, b)); - // Test order dependence - EXPECT_NE(hash_combine_test(a, b), - hash_combine_test(b, a)); - // Again, 1 + 2 == 2 + 1 - EXPECT_EQ(hash_combine_test(a, b), - hash_combine_test(d, b)); -} - -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); - - std::unordered_map m; - m[t] = "bar"; - 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()); -} -} // namespace - -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); - tuple3 t2(9, "bar", 3); - tuple3 t3(42, "foo", 3); - - EXPECT_NE(std::hash()(t1), - std::hash()(t2)); - 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())); -} - -struct FNVTestParam { - std::string in; - uint64_t out; -}; - -class FNVTest : public ::testing::TestWithParam {}; - -TEST_P(FNVTest, Fnva64Buf) { - EXPECT_EQ(GetParam().out, - fnva64_buf(GetParam().in.data(), GetParam().in.size())); -} - -TEST_P(FNVTest, Fnva64) { - EXPECT_EQ(GetParam().out, fnva64(GetParam().in)); -} - -TEST_P(FNVTest, Fnva64Partial) { - size_t partialLen = GetParam().in.size() / 2; - auto data = GetParam().in.data(); - auto partial = fnva64_buf(data, partialLen); - EXPECT_EQ(GetParam().out, - fnva64_buf( - data + partialLen, GetParam().in.size() - partialLen, partial)); -} - -// Taken from http://www.isthe.com/chongo/src/fnv/test_fnv.c -INSTANTIATE_TEST_CASE_P( - FNVTesting, - FNVTest, - ::testing::Values( - (FNVTestParam){"foobar", // 11 - 0x85944171f73967e8}, - (FNVTestParam){"chongo was here!\n", // 39 - 0x46810940eff5f915}, - (FNVTestParam){"127.0.0.3", // 106, - 0xaabafc7104d91158}, - (FNVTestParam){ - "http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash", // 126 - 0xd9b957fb7fe794c5}, - (FNVTestParam){"http://norvig.com/21-days.html", // 136 - 0x07aaa640476e0b9a})); diff --git a/folly/test/ThreadCachedIntTest.cpp b/folly/test/ThreadCachedIntTest.cpp index f4a77d3f..8709abf6 100644 --- a/folly/test/ThreadCachedIntTest.cpp +++ b/folly/test/ThreadCachedIntTest.cpp @@ -24,7 +24,7 @@ #include #include -#include +#include #include #include #include