#include <boost/iterator/iterator_facade.hpp>
#include <boost/noncopyable.hpp>
+#include <folly/Hash.h>
#include <folly/ThreadCachedInt.h>
#include <folly/Utility.h>
-#include <folly/hash/Hash.h>
namespace folly {
#include <folly/AtomicHashArray.h>
#include <folly/Foreach.h>
+#include <folly/Hash.h>
#include <folly/Likely.h>
#include <folly/ThreadCachedInt.h>
-#include <folly/hash/Hash.h>
namespace folly {
#include <string>
#include <utility>
+#include <folly/Hash.h>
#include <folly/Malloc.h>
#include <folly/Traits.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/BitsFunctexcept.h>
// When used in folly, assertions are not disabled.
} // 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);
/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
#pragma once
-#include <folly/hash/Hash.h>
+#include <cstdint>
+#include <cstring>
+#include <limits>
+#include <string>
+#include <tuple>
+#include <type_traits>
+#include <utility>
+
+#include <folly/ApplyTuple.h>
+#include <folly/Bits.h>
+#include <folly/hash/SpookyHashV1.h>
+#include <folly/hash/SpookyHashV2.h>
+
+/*
+ * 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<T>; 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 <class Hasher>
+inline size_t hash_combine_generic() {
+ return 0;
+}
+
+template <
+ class Iter,
+ class Hash = std::hash<typename std::iterator_traits<Iter>::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 <class Hasher, typename T, typename... Ts>
+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<Hasher>(ts...);
+ /* static */ if (sizeof(size_t) == sizeof(uint32_t)) {
+ return twang_32from64((uint64_t(seed) << 32) | remainder);
+ } else {
+ return static_cast<size_t>(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 <typename T>
+ static size_t hash(const T& t) {
+ return std::hash<T>()(t);
+ }
+};
+
+template <typename T, typename... Ts>
+size_t hash_combine(const T& t, const Ts&... ts) {
+ return hash_combine_generic<StdHasher>(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<const signed char*>(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<const signed char*>(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<const signed char*>(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<const signed char*>(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<const uint8_t*>(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<uint16_t>(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<const unsigned char*>(buf);
+ uint32_t hash = static_cast<uint32_t>(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 <typename I>
+ 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<int32_t>(i); // impl accident: sign-extends
+ auto const u32 = static_cast<uint32_t>(i32);
+ return static_cast<size_t>(hash::jenkins_rev_mix32(u32));
+ } else {
+ auto const u64 = static_cast<uint64_t>(i);
+ return static_cast<size_t>(hash::twang_mix64(u64));
+ }
+ }
+};
+} // namespace detail
+
+template <class Key, class Enable = void>
+struct hasher;
+
+struct Hash {
+ template <class T>
+ size_t operator()(const T& v) const {
+ return hasher<T>()(v);
+ }
+
+ template <class T, class... Ts>
+ size_t operator()(const T& t, const Ts&... ts) const {
+ return hash::hash_128_to_64((*this)(t), (*this)(ts...));
+ }
+};
+
+template <>
+struct hasher<bool> {
+ size_t operator()(bool key) const {
+ // Make sure that all the output bits depend on the input.
+ return key ? std::numeric_limits<size_t>::max() : 0;
+ }
+};
+
+template <>
+struct hasher<unsigned long long> : detail::integral_hasher {};
+
+template <>
+struct hasher<signed long long> : detail::integral_hasher {};
+
+template <>
+struct hasher<unsigned long> : detail::integral_hasher {};
+
+template <>
+struct hasher<signed long> : detail::integral_hasher {};
+
+template <>
+struct hasher<unsigned int> : detail::integral_hasher {};
+
+template <>
+struct hasher<signed int> : detail::integral_hasher {};
+
+template <>
+struct hasher<unsigned short> : detail::integral_hasher {};
+
+template <>
+struct hasher<signed short> : detail::integral_hasher {};
+
+template <>
+struct hasher<unsigned char> : detail::integral_hasher {};
+
+template <>
+struct hasher<signed char> : detail::integral_hasher {};
+
+template <> // char is a different type from both signed char and unsigned char
+struct hasher<char> : detail::integral_hasher {};
+
+template <> struct hasher<std::string> {
+ size_t operator()(const std::string& key) const {
+ return static_cast<size_t>(
+ hash::SpookyHashV2::Hash64(key.data(), key.size(), 0));
+ }
+};
+
+template <class T>
+struct hasher<T, typename std::enable_if<std::is_enum<T>::value, void>::type> {
+ size_t operator()(T key) const {
+ return Hash()(static_cast<typename std::underlying_type<T>::type>(key));
+ }
+};
+
+template <class T1, class T2>
+struct hasher<std::pair<T1, T2>> {
+ size_t operator()(const std::pair<T1, T2>& key) const {
+ return Hash()(key.first, key.second);
+ }
+};
+
+template <typename... Ts>
+struct hasher<std::tuple<Ts...>> {
+ size_t operator() (const std::tuple<Ts...>& key) const {
+ return applyTuple(Hash(), key);
+ }
+};
+
+// recursion
+template <size_t index, typename... Ts>
+struct TupleHasher {
+ size_t operator()(std::tuple<Ts...> const& key) const {
+ return hash::hash_combine(
+ TupleHasher<index - 1, Ts...>()(key),
+ std::get<index>(key));
+ }
+};
+
+// base
+template <typename... Ts>
+struct TupleHasher<0, Ts...> {
+ size_t operator()(std::tuple<Ts...> 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 <typename T1, typename T2>
+ struct hash<std::pair<T1, T2> > {
+ public:
+ size_t operator()(const std::pair<T1, T2>& x) const {
+ return folly::hash::hash_combine(x.first, x.second);
+ }
+ };
+
+ // Hash function for tuples. Requires default hash functions for all types.
+ template <typename... Ts>
+ struct hash<std::tuple<Ts...>> {
+ size_t operator()(std::tuple<Ts...> const& key) const {
+ folly::TupleHasher<
+ std::tuple_size<std::tuple<Ts...>>::value - 1, // start index
+ Ts...> hasher;
+
+ return hasher(key);
+ }
+ };
+} // namespace std
#include <iosfwd>
#include <folly/FBString.h>
+#include <folly/Hash.h>
#include <folly/Range.h>
#include <folly/detail/IPAddress.h>
-#include <folly/hash/Hash.h>
namespace folly {
#include <stdexcept>
#include <folly/FBString.h>
+#include <folly/Hash.h>
#include <folly/Optional.h>
#include <folly/Range.h>
#include <folly/detail/IPAddress.h>
-#include <folly/hash/Hash.h>
namespace folly {
futures/test/TestExecutor.h \
hash/Checksum.h \
hash/detail/ChecksumDetail.h \
- hash/Hash.h \
hash/SpookyHashV1.h \
hash/SpookyHashV2.h \
gen/Base.h \
gen/String.h \
gen/String-inl.h \
GroupVarint.h \
+ Hash.h \
IPAddress.h \
IPAddressV4.h \
IPAddressV6.h \
#include <folly/Demangle.h>
#include <folly/Exception.h>
#include <folly/Executor.h>
+#include <folly/Hash.h>
#include <folly/Memory.h>
#include <folly/RWSpinLock.h>
#include <folly/Synchronized.h>
#include <folly/detail/StaticSingletonManager.h>
#include <folly/experimental/ReadMostlySharedPtr.h>
-#include <folly/hash/Hash.h>
#include <algorithm>
#include <atomic>
#include <folly/CppAttributes.h>
#include <folly/Exception.h>
#include <folly/Format.h>
-#include <folly/hash/Hash.h>
+#include <folly/Hash.h>
namespace {
#include <tuple>
#include <folly/Conv.h>
-#include <folly/hash/Hash.h>
+#include <folly/Hash.h>
namespace folly {
#include <unordered_map>
#include <vector>
+#include <folly/Hash.h>
#include <folly/Indestructible.h>
#include <folly/Likely.h>
#include <folly/Memory.h>
#include <folly/Portability.h>
#include <folly/ThreadId.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/BitsFunctexcept.h>
#include <folly/portability/Memory.h>
#include <memory>
#include <thread>
+#include <folly/Hash.h>
#include <folly/concurrency/ConcurrentHashMap.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/GTest.h>
#include <folly/test/DeterministicSchedule.h>
#include <folly/detail/Futex.h>
#include <boost/intrusive/list.hpp>
+#include <folly/Hash.h>
#include <folly/ScopeGuard.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/SysSyscall.h>
#include <stdint.h>
#include <string.h>
#include <chrono>
#include <folly/AtomicStruct.h>
+#include <folly/Hash.h>
#include <folly/ThreadId.h>
#include <folly/Traits.h>
#include <folly/detail/Futex.h>
-#include <folly/hash/Hash.h>
namespace folly {
#include <folly/Assume.h>
#include <folly/Format.h>
-#include <folly/hash/Hash.h>
+#include <folly/Hash.h>
#include <folly/portability/BitsFunctexcept.h>
namespace folly {
#include <folly/Function.h>
#include <folly/Range.h>
-#include <folly/hash/Hash.h>
+#include <folly/Hash.h>
#include <chrono>
#include <condition_variable>
#include <mutex>
#include <thread>
-#include <unordered_map>
#include <vector>
+#include <unordered_map>
namespace folly {
#include <unordered_map>
#include <utility>
+#include <folly/Hash.h>
#include <folly/Range.h>
#include <folly/experimental/StringKeyedCommon.h>
-#include <folly/hash/Hash.h>
namespace folly {
#include <unordered_set>
#include <utility>
+#include <folly/Hash.h>
#include <folly/Range.h>
#include <folly/experimental/StringKeyedCommon.h>
-#include <folly/hash/Hash.h>
namespace folly {
#include <boost/operators.hpp>
#include <glog/logging.h>
+#include <folly/Hash.h>
#include <folly/Range.h>
#include <folly/experimental/symbolizer/Elf.h>
-#include <folly/hash/Hash.h>
namespace folly {
namespace symbolizer {
#include <glog/logging.h>
+#include <folly/Hash.h>
#include <folly/Range.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
+++ /dev/null
-/*
- * 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 <cstdint>
-#include <cstring>
-#include <limits>
-#include <string>
-#include <tuple>
-#include <type_traits>
-#include <utility>
-
-#include <folly/ApplyTuple.h>
-#include <folly/Bits.h>
-#include <folly/hash/SpookyHashV1.h>
-#include <folly/hash/SpookyHashV2.h>
-
-/*
- * 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<T>; 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 <class Hasher>
-inline size_t hash_combine_generic() {
- return 0;
-}
-
-template <
- class Iter,
- class Hash = std::hash<typename std::iterator_traits<Iter>::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 <class Hasher, typename T, typename... Ts>
-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<Hasher>(ts...);
- /* static */ if (sizeof(size_t) == sizeof(uint32_t)) {
- return twang_32from64((uint64_t(seed) << 32) | remainder);
- } else {
- return static_cast<size_t>(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 <typename T>
- static size_t hash(const T& t) {
- return std::hash<T>()(t);
- }
-};
-
-template <typename T, typename... Ts>
-size_t hash_combine(const T& t, const Ts&... ts) {
- return hash_combine_generic<StdHasher>(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<const signed char*>(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<const signed char*>(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<const signed char*>(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<const signed char*>(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<const uint8_t*>(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<uint16_t>(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<const unsigned char*>(buf);
- uint32_t hash = static_cast<uint32_t>(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 <typename I>
- 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<int32_t>(i); // impl accident: sign-extends
- auto const u32 = static_cast<uint32_t>(i32);
- return static_cast<size_t>(hash::jenkins_rev_mix32(u32));
- } else {
- auto const u64 = static_cast<uint64_t>(i);
- return static_cast<size_t>(hash::twang_mix64(u64));
- }
- }
-};
-} // namespace detail
-
-template <class Key, class Enable = void>
-struct hasher;
-
-struct Hash {
- template <class T>
- size_t operator()(const T& v) const {
- return hasher<T>()(v);
- }
-
- template <class T, class... Ts>
- size_t operator()(const T& t, const Ts&... ts) const {
- return hash::hash_128_to_64((*this)(t), (*this)(ts...));
- }
-};
-
-template <>
-struct hasher<bool> {
- size_t operator()(bool key) const {
- // Make sure that all the output bits depend on the input.
- return key ? std::numeric_limits<size_t>::max() : 0;
- }
-};
-
-template <>
-struct hasher<unsigned long long> : detail::integral_hasher {};
-
-template <>
-struct hasher<signed long long> : detail::integral_hasher {};
-
-template <>
-struct hasher<unsigned long> : detail::integral_hasher {};
-
-template <>
-struct hasher<signed long> : detail::integral_hasher {};
-
-template <>
-struct hasher<unsigned int> : detail::integral_hasher {};
-
-template <>
-struct hasher<signed int> : detail::integral_hasher {};
-
-template <>
-struct hasher<unsigned short> : detail::integral_hasher {};
-
-template <>
-struct hasher<signed short> : detail::integral_hasher {};
-
-template <>
-struct hasher<unsigned char> : detail::integral_hasher {};
-
-template <>
-struct hasher<signed char> : detail::integral_hasher {};
-
-template <> // char is a different type from both signed char and unsigned char
-struct hasher<char> : detail::integral_hasher {};
-
-template <> struct hasher<std::string> {
- size_t operator()(const std::string& key) const {
- return static_cast<size_t>(
- hash::SpookyHashV2::Hash64(key.data(), key.size(), 0));
- }
-};
-
-template <class T>
-struct hasher<T, typename std::enable_if<std::is_enum<T>::value, void>::type> {
- size_t operator()(T key) const {
- return Hash()(static_cast<typename std::underlying_type<T>::type>(key));
- }
-};
-
-template <class T1, class T2>
-struct hasher<std::pair<T1, T2>> {
- size_t operator()(const std::pair<T1, T2>& key) const {
- return Hash()(key.first, key.second);
- }
-};
-
-template <typename... Ts>
-struct hasher<std::tuple<Ts...>> {
- size_t operator() (const std::tuple<Ts...>& key) const {
- return applyTuple(Hash(), key);
- }
-};
-
-// recursion
-template <size_t index, typename... Ts>
-struct TupleHasher {
- size_t operator()(std::tuple<Ts...> const& key) const {
- return hash::hash_combine(
- TupleHasher<index - 1, Ts...>()(key),
- std::get<index>(key));
- }
-};
-
-// base
-template <typename... Ts>
-struct TupleHasher<0, Ts...> {
- size_t operator()(std::tuple<Ts...> 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 <typename T1, typename T2>
- struct hash<std::pair<T1, T2> > {
- public:
- size_t operator()(const std::pair<T1, T2>& x) const {
- return folly::hash::hash_combine(x.first, x.second);
- }
- };
-
- // Hash function for tuples. Requires default hash functions for all types.
- template <typename... Ts>
- struct hash<std::tuple<Ts...>> {
- size_t operator()(std::tuple<Ts...> const& key) const {
- folly::TupleHasher<
- std::tuple_size<std::tuple<Ts...>>::value - 1, // start index
- Ts...> hasher;
-
- return hasher(key);
- }
- };
-} // namespace std
#include <boost/crc.hpp>
#include <folly/Benchmark.h>
-#include <folly/hash/Hash.h>
+#include <folly/Hash.h>
#include <folly/hash/detail/ChecksumDetail.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
+++ /dev/null
-/*
- * 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 <folly/hash/Hash.h>
-
-#include <stdint.h>
-#include <deque>
-#include <random>
-#include <string>
-#include <vector>
-
-#include <glog/logging.h>
-
-#include <folly/Benchmark.h>
-#include <folly/Format.h>
-#include <folly/Preprocessor.h>
-#include <folly/portability/GFlags.h>
-
-namespace detail {
-
-std::vector<uint8_t> randomBytes(size_t n) {
- std::vector<uint8_t> ret(n);
- std::default_random_engine rng(1729); // Deterministic seed.
- std::uniform_int_distribution<uint16_t> dist(0, 255);
- std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); });
- return ret;
-}
-
-std::vector<uint8_t> benchData = randomBytes(1 << 20); // 1MiB, fits in cache.
-
-template <class Hasher>
-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 <class Hasher>
-void addHashBenchmark(const std::string& name) {
- static std::deque<std::string> 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);
- }
-};
-
-}
-
-int main(int argc, char** argv) {
- gflags::ParseCommandLineFlags(&argc, &argv, true);
- google::InitGoogleLogging(argv[0]);
-
- std::deque<std::string> names; // Backing for benchmark names.
-
-#define BENCHMARK_HASH(HASHER) \
- detail::addHashBenchmark<detail::HASHER>(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
+++ /dev/null
-/*
- * 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 <folly/hash/Hash.h>
-#include <folly/MapUtil.h>
-#include <folly/portability/GTest.h>
-#include <stdint.h>
-#include <unordered_map>
-#include <unordered_set>
-#include <utility>
-
-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<const char*>(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<const char*>(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<void*>(&t4_b),
- sizeof(int64_t),
- t4_hash1);
- uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&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<int32_t,int32_t,folly::hasher<int32_t>> 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<size_t> 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<int, int>& p) {
- return p.first + p.second;
- }
-};
-
-template <typename T, typename... Ts>
-size_t hash_combine_test(const T& t, const Ts&... ts) {
- return hash_combine_generic<TestHasher>(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<size_t> 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<int64_t, std::string, int32_t> tuple3;
- tuple3 t(42, "foo", 1);
-
- std::unordered_map<tuple3, std::string> 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<int32_t>(Enum32::Foo)), hash(Enum32::Foo));
- EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Bar)), hash(Enum32::Bar));
- EXPECT_NE(hash(Enum32::Foo), hash(Enum32::Bar));
-
- std::unordered_map<Enum32, std::string, folly::Hash> m32;
- m32[Enum32::Foo] = "foo";
- EXPECT_EQ("foo", m32[Enum32::Foo]);
-
- enum class Enum64 : int64_t { Foo, Bar };
- EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Foo)), hash(Enum64::Foo));
- EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Bar)), hash(Enum64::Bar));
- EXPECT_NE(hash(Enum64::Foo), hash(Enum64::Bar));
-
- std::unordered_map<Enum64, std::string, folly::Hash> m64;
- m64[Enum64::Foo] = "foo";
- EXPECT_EQ("foo", m64[Enum64::Foo]);
-}
-
-TEST(Hash, pair_folly_hash) {
- typedef std::pair<int64_t, int32_t> pair2;
- pair2 p(42, 1);
-
- std::unordered_map<pair2, std::string, folly::Hash> m;
- m[p] = "bar";
- EXPECT_EQ("bar", m[p]);
-}
-
-TEST(Hash, tuple_folly_hash) {
- typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
- tuple3 t(42, 1, 1);
-
- std::unordered_map<tuple3, std::string, folly::Hash> m;
- m[t] = "bar";
- EXPECT_EQ("bar", m[t]);
-}
-
-namespace {
-template <class T>
-size_t hash_vector(const std::vector<T>& v) {
- return hash_range(v.begin(), v.end());
-}
-}
-
-TEST(Hash, hash_range) {
- EXPECT_EQ(hash_vector<int32_t>({1, 2}), hash_vector<int16_t>({1, 2}));
- EXPECT_NE(hash_vector<int>({2, 1}), hash_vector<int>({1, 2}));
- EXPECT_EQ(hash_vector<int>({}), hash_vector<float>({}));
-}
-
-TEST(Hash, std_tuple_different_hash) {
- typedef std::tuple<int64_t, std::string, int32_t> tuple3;
- tuple3 t1(42, "foo", 1);
- tuple3 t2(9, "bar", 3);
- tuple3 t3(42, "foo", 3);
-
- EXPECT_NE(std::hash<tuple3>()(t1),
- std::hash<tuple3>()(t2));
- EXPECT_NE(std::hash<tuple3>()(t1),
- std::hash<tuple3>()(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<const wchar_t*> 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<FNVTestParam> {};
-
-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}));
#include <glog/logging.h>
#include <folly/Benchmark.h>
+#include <folly/Hash.h>
#include <folly/Memory.h>
#include <folly/Random.h>
#include <folly/Varint.h>
-#include <folly/hash/Hash.h>
#include <folly/io/IOBufQueue.h>
#include <folly/portability/GTest.h>
#include <folly/AtomicHashArray.h>
#include <folly/Conv.h>
+#include <folly/Hash.h>
#include <folly/Memory.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/GTest.h>
#include <folly/portability/SysMman.h>
#include <folly/Benchmark.h>
#include <folly/ConcurrentSkipList.h>
+#include <folly/Hash.h>
#include <folly/RWSpinLock.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/GFlags.h>
#include <glog/logging.h>
--- /dev/null
+/*
+ * 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 <folly/Hash.h>
+
+#include <stdint.h>
+#include <deque>
+#include <random>
+#include <string>
+#include <vector>
+
+#include <glog/logging.h>
+
+#include <folly/Benchmark.h>
+#include <folly/Format.h>
+#include <folly/Preprocessor.h>
+#include <folly/portability/GFlags.h>
+
+namespace detail {
+
+std::vector<uint8_t> randomBytes(size_t n) {
+ std::vector<uint8_t> ret(n);
+ std::default_random_engine rng(1729); // Deterministic seed.
+ std::uniform_int_distribution<uint16_t> dist(0, 255);
+ std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); });
+ return ret;
+}
+
+std::vector<uint8_t> benchData = randomBytes(1 << 20); // 1MiB, fits in cache.
+
+template <class Hasher>
+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 <class Hasher>
+void addHashBenchmark(const std::string& name) {
+ static std::deque<std::string> 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);
+ }
+};
+
+}
+
+int main(int argc, char** argv) {
+ gflags::ParseCommandLineFlags(&argc, &argv, true);
+ google::InitGoogleLogging(argv[0]);
+
+ std::deque<std::string> names; // Backing for benchmark names.
+
+#define BENCHMARK_HASH(HASHER) \
+ detail::addHashBenchmark<detail::HASHER>(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
--- /dev/null
+/*
+ * 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 <folly/Hash.h>
+#include <folly/MapUtil.h>
+#include <folly/portability/GTest.h>
+#include <stdint.h>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+
+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<const char*>(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<const char*>(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<void*>(&t4_b),
+ sizeof(int64_t),
+ t4_hash1);
+ uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&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<int32_t,int32_t,folly::hasher<int32_t>> 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<size_t> 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<int, int>& p) {
+ return p.first + p.second;
+ }
+};
+
+template <typename T, typename... Ts>
+size_t hash_combine_test(const T& t, const Ts&... ts) {
+ return hash_combine_generic<TestHasher>(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<size_t> 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<int64_t, std::string, int32_t> tuple3;
+ tuple3 t(42, "foo", 1);
+
+ std::unordered_map<tuple3, std::string> 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<int32_t>(Enum32::Foo)), hash(Enum32::Foo));
+ EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Bar)), hash(Enum32::Bar));
+ EXPECT_NE(hash(Enum32::Foo), hash(Enum32::Bar));
+
+ std::unordered_map<Enum32, std::string, folly::Hash> m32;
+ m32[Enum32::Foo] = "foo";
+ EXPECT_EQ("foo", m32[Enum32::Foo]);
+
+ enum class Enum64 : int64_t { Foo, Bar };
+ EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Foo)), hash(Enum64::Foo));
+ EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Bar)), hash(Enum64::Bar));
+ EXPECT_NE(hash(Enum64::Foo), hash(Enum64::Bar));
+
+ std::unordered_map<Enum64, std::string, folly::Hash> m64;
+ m64[Enum64::Foo] = "foo";
+ EXPECT_EQ("foo", m64[Enum64::Foo]);
+}
+
+TEST(Hash, pair_folly_hash) {
+ typedef std::pair<int64_t, int32_t> pair2;
+ pair2 p(42, 1);
+
+ std::unordered_map<pair2, std::string, folly::Hash> m;
+ m[p] = "bar";
+ EXPECT_EQ("bar", m[p]);
+}
+
+TEST(Hash, tuple_folly_hash) {
+ typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
+ tuple3 t(42, 1, 1);
+
+ std::unordered_map<tuple3, std::string, folly::Hash> m;
+ m[t] = "bar";
+ EXPECT_EQ("bar", m[t]);
+}
+
+namespace {
+template <class T>
+size_t hash_vector(const std::vector<T>& v) {
+ return hash_range(v.begin(), v.end());
+}
+}
+
+TEST(Hash, hash_range) {
+ EXPECT_EQ(hash_vector<int32_t>({1, 2}), hash_vector<int16_t>({1, 2}));
+ EXPECT_NE(hash_vector<int>({2, 1}), hash_vector<int>({1, 2}));
+ EXPECT_EQ(hash_vector<int>({}), hash_vector<float>({}));
+}
+
+TEST(Hash, std_tuple_different_hash) {
+ typedef std::tuple<int64_t, std::string, int32_t> tuple3;
+ tuple3 t1(42, "foo", 1);
+ tuple3 t2(9, "bar", 3);
+ tuple3 t3(42, "foo", 3);
+
+ EXPECT_NE(std::hash<tuple3>()(t1),
+ std::hash<tuple3>()(t2));
+ EXPECT_NE(std::hash<tuple3>()(t1),
+ std::hash<tuple3>()(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<const wchar_t*> 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<FNVTestParam> {};
+
+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}));
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
#include <glog/logging.h>
#include <folly/Benchmark.h>
+#include <folly/Hash.h>
#include <folly/ThreadId.h>
-#include <folly/hash/Hash.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
projects / folly.git / commitdiff