From dce47b8a0cc0e90f93844e66651d68340ed2f940 Mon Sep 17 00:00:00 2001 From: Yedidya Feldblum Date: Thu, 19 Oct 2017 02:30:31 -0700 Subject: [PATCH] Revert D6050464: [Folly] Move folly/Hash.h to folly/hash/ Summary: This reverts commit 64eb65aac8e3e7cd0126e65ca3998bfe167e2d73 bypass-lint Differential Revision: D6050464 fbshipit-source-id: 1ed63f30837dc11ae57b316f1f7cb233a210894a --- folly/AtomicHashArray.h | 2 +- folly/AtomicHashMap.h | 2 +- folly/FBString.h | 2 +- folly/FixedString.h | 2 +- folly/Hash.h | 502 ++++++++++++++++- folly/IPAddressV4.h | 2 +- folly/IPAddressV6.h | 2 +- folly/Makefile.am | 2 +- folly/Singleton.h | 2 +- folly/SocketAddress.cpp | 2 +- folly/Uri-inl.h | 2 +- folly/concurrency/CacheLocality.h | 2 +- .../test/ConcurrentHashMapTest.cpp | 2 +- folly/detail/Futex.cpp | 2 +- folly/detail/MemoryIdler.h | 2 +- folly/dynamic.cpp | 2 +- folly/experimental/FunctionScheduler.h | 4 +- folly/experimental/StringKeyedUnorderedMap.h | 2 +- folly/experimental/StringKeyedUnorderedSet.h | 2 +- folly/experimental/symbolizer/ElfCache.h | 2 +- folly/experimental/test/StringKeyedTest.cpp | 2 +- folly/hash/Hash.h | 519 ------------------ folly/hash/test/ChecksumTest.cpp | 2 +- folly/io/test/CompressionTest.cpp | 2 +- folly/test/AtomicHashArrayTest.cpp | 2 +- folly/test/ConcurrentSkipListBenchmark.cpp | 2 +- folly/{hash => }/test/HashBenchmark.cpp | 2 +- folly/{hash => }/test/HashTest.cpp | 2 +- folly/test/Makefile.am | 2 +- folly/test/ThreadCachedIntTest.cpp | 2 +- 30 files changed, 530 insertions(+), 549 deletions(-) delete mode 100644 folly/hash/Hash.h rename folly/{hash => }/test/HashBenchmark.cpp (99%) rename folly/{hash => }/test/HashTest.cpp (99%) diff --git a/folly/AtomicHashArray.h b/folly/AtomicHashArray.h index 654077b1..16b8dad0 100644 --- a/folly/AtomicHashArray.h +++ b/folly/AtomicHashArray.h @@ -37,9 +37,9 @@ #include #include +#include #include #include -#include namespace folly { diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h index a3f42c0b..af8aa633 100644 --- a/folly/AtomicHashMap.h +++ b/folly/AtomicHashMap.h @@ -92,9 +92,9 @@ #include #include +#include #include #include -#include namespace folly { diff --git a/folly/FBString.h b/folly/FBString.h index 4cdafcfb..b566d119 100644 --- a/folly/FBString.h +++ b/folly/FBString.h @@ -54,9 +54,9 @@ #include #include +#include #include #include -#include #include // When used in folly, assertions are not disabled. diff --git a/folly/FixedString.h b/folly/FixedString.h index d94468c1..732ae6ac 100644 --- a/folly/FixedString.h +++ b/folly/FixedString.h @@ -409,7 +409,7 @@ struct ReverseIterator { } // namespace fixedstring } // namespace detail -// Defined in folly/hash/Hash.h +// Defined in folly/Hash.h std::uint32_t hsieh_hash32_buf(const void* buf, std::size_t len); /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** * diff --git a/folly/Hash.h b/folly/Hash.h index 22b7f14f..410d2720 100644 --- a/folly/Hash.h +++ b/folly/Hash.h @@ -16,4 +16,504 @@ #pragma once -#include +#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/IPAddressV4.h b/folly/IPAddressV4.h index 76534add..96de8add 100644 --- a/folly/IPAddressV4.h +++ b/folly/IPAddressV4.h @@ -23,9 +23,9 @@ #include #include +#include #include #include -#include namespace folly { diff --git a/folly/IPAddressV6.h b/folly/IPAddressV6.h index 78ec4c76..f641bdcd 100644 --- a/folly/IPAddressV6.h +++ b/folly/IPAddressV6.h @@ -25,10 +25,10 @@ #include #include +#include #include #include #include -#include namespace folly { diff --git a/folly/Makefile.am b/folly/Makefile.am index 439ea6b8..ce29ac05 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -229,7 +229,6 @@ 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 \ @@ -247,6 +246,7 @@ nobase_follyinclude_HEADERS = \ gen/String.h \ gen/String-inl.h \ GroupVarint.h \ + Hash.h \ IPAddress.h \ IPAddressV4.h \ IPAddressV6.h \ diff --git a/folly/Singleton.h b/folly/Singleton.h index 413b51f8..028cf7f1 100644 --- a/folly/Singleton.h +++ b/folly/Singleton.h @@ -125,12 +125,12 @@ #include #include #include +#include #include #include #include #include #include -#include #include #include diff --git a/folly/SocketAddress.cpp b/folly/SocketAddress.cpp index af6cd77f..6cb5a7a0 100644 --- a/folly/SocketAddress.cpp +++ b/folly/SocketAddress.cpp @@ -32,7 +32,7 @@ #include #include #include -#include +#include namespace { diff --git a/folly/Uri-inl.h b/folly/Uri-inl.h index 50d57c2e..6445eef3 100644 --- a/folly/Uri-inl.h +++ b/folly/Uri-inl.h @@ -22,7 +22,7 @@ #include #include -#include +#include namespace folly { diff --git a/folly/concurrency/CacheLocality.h b/folly/concurrency/CacheLocality.h index ecbed1ef..38f5557c 100644 --- a/folly/concurrency/CacheLocality.h +++ b/folly/concurrency/CacheLocality.h @@ -28,12 +28,12 @@ #include #include +#include #include #include #include #include #include -#include #include #include diff --git a/folly/concurrency/test/ConcurrentHashMapTest.cpp b/folly/concurrency/test/ConcurrentHashMapTest.cpp index 32b3d8ae..cf283c41 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/detail/Futex.cpp b/folly/detail/Futex.cpp index da7a04dc..8604a745 100644 --- a/folly/detail/Futex.cpp +++ b/folly/detail/Futex.cpp @@ -16,8 +16,8 @@ #include #include +#include #include -#include #include #include #include diff --git a/folly/detail/MemoryIdler.h b/folly/detail/MemoryIdler.h index fc7c8b7e..fcbde002 100644 --- a/folly/detail/MemoryIdler.h +++ b/folly/detail/MemoryIdler.h @@ -20,10 +20,10 @@ #include #include +#include #include #include #include -#include namespace folly { diff --git a/folly/dynamic.cpp b/folly/dynamic.cpp index 3ac1173b..08e97472 100644 --- a/folly/dynamic.cpp +++ b/folly/dynamic.cpp @@ -18,7 +18,7 @@ #include #include -#include +#include #include namespace folly { diff --git a/folly/experimental/FunctionScheduler.h b/folly/experimental/FunctionScheduler.h index e8765fab..fbc73993 100644 --- a/folly/experimental/FunctionScheduler.h +++ b/folly/experimental/FunctionScheduler.h @@ -18,13 +18,13 @@ #include #include -#include +#include #include #include #include #include -#include #include +#include namespace folly { diff --git a/folly/experimental/StringKeyedUnorderedMap.h b/folly/experimental/StringKeyedUnorderedMap.h index 4cf33b43..41180cb7 100644 --- a/folly/experimental/StringKeyedUnorderedMap.h +++ b/folly/experimental/StringKeyedUnorderedMap.h @@ -24,9 +24,9 @@ #include #include +#include #include #include -#include namespace folly { diff --git a/folly/experimental/StringKeyedUnorderedSet.h b/folly/experimental/StringKeyedUnorderedSet.h index 269d2e6d..11317ede 100644 --- a/folly/experimental/StringKeyedUnorderedSet.h +++ b/folly/experimental/StringKeyedUnorderedSet.h @@ -24,9 +24,9 @@ #include #include +#include #include #include -#include namespace folly { diff --git a/folly/experimental/symbolizer/ElfCache.h b/folly/experimental/symbolizer/ElfCache.h index 57a36cf7..b9d7d966 100644 --- a/folly/experimental/symbolizer/ElfCache.h +++ b/folly/experimental/symbolizer/ElfCache.h @@ -29,9 +29,9 @@ #include #include +#include #include #include -#include namespace folly { namespace symbolizer { diff --git a/folly/experimental/test/StringKeyedTest.cpp b/folly/experimental/test/StringKeyedTest.cpp index 072500b5..b6744459 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 deleted file mode 100644 index 410d2720..00000000 --- a/folly/hash/Hash.h +++ /dev/null @@ -1,519 +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. - */ - -#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 05ac6e59..e5e613c6 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/io/test/CompressionTest.cpp b/folly/io/test/CompressionTest.cpp index 69069c82..69a037d8 100644 --- a/folly/io/test/CompressionTest.cpp +++ b/folly/io/test/CompressionTest.cpp @@ -27,10 +27,10 @@ #include #include +#include #include #include #include -#include #include #include diff --git a/folly/test/AtomicHashArrayTest.cpp b/folly/test/AtomicHashArrayTest.cpp index 531732c4..780076a1 100644 --- a/folly/test/AtomicHashArrayTest.cpp +++ b/folly/test/AtomicHashArrayTest.cpp @@ -20,8 +20,8 @@ #include #include +#include #include -#include #include #include diff --git a/folly/test/ConcurrentSkipListBenchmark.cpp b/folly/test/ConcurrentSkipListBenchmark.cpp index 97c27620..cfe9aa98 100644 --- a/folly/test/ConcurrentSkipListBenchmark.cpp +++ b/folly/test/ConcurrentSkipListBenchmark.cpp @@ -23,8 +23,8 @@ #include #include +#include #include -#include #include #include diff --git a/folly/hash/test/HashBenchmark.cpp b/folly/test/HashBenchmark.cpp similarity index 99% rename from folly/hash/test/HashBenchmark.cpp rename to folly/test/HashBenchmark.cpp index f387f5a7..4595a6e6 100644 --- a/folly/hash/test/HashBenchmark.cpp +++ b/folly/test/HashBenchmark.cpp @@ -14,7 +14,7 @@ * limitations under the License. */ -#include +#include #include #include diff --git a/folly/hash/test/HashTest.cpp b/folly/test/HashTest.cpp similarity index 99% rename from folly/hash/test/HashTest.cpp rename to folly/test/HashTest.cpp index fe7a8042..759f9975 100644 --- a/folly/hash/test/HashTest.cpp +++ b/folly/test/HashTest.cpp @@ -14,7 +14,7 @@ * limitations under the License. */ -#include +#include #include #include #include diff --git a/folly/test/Makefile.am b/folly/test/Makefile.am index 22c1127e..a2f58830 100644 --- a/folly/test/Makefile.am +++ b/folly/test/Makefile.am @@ -89,7 +89,7 @@ foreach_benchmark_SOURCES = ForeachBenchmark.cpp foreach_benchmark_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la check_PROGRAMS += foreach_benchmark -hash_test_SOURCES = ../hash/test/HashTest.cpp +hash_test_SOURCES = HashTest.cpp hash_test_LDADD = libfollytestmain.la invoke_test_SOURCES = ../functional/test/InvokeTest.cpp diff --git a/folly/test/ThreadCachedIntTest.cpp b/folly/test/ThreadCachedIntTest.cpp index 588aa52e..e09c780f 100644 --- a/folly/test/ThreadCachedIntTest.cpp +++ b/folly/test/ThreadCachedIntTest.cpp @@ -23,8 +23,8 @@ #include #include +#include #include -#include #include #include -- 2.34.1