Move folly/Hash.h to folly/hash/
authorYedidya Feldblum <yfeldblum@fb.com>
Thu, 19 Oct 2017 07:37:48 +0000 (00:37 -0700)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Thu, 19 Oct 2017 07:51:18 +0000 (00:51 -0700)
Summary: [Folly] Move `folly/Hash.h` to `folly/hash/`.

Reviewed By: jsedgwick

Differential Revision: D6050464

fbshipit-source-id: 64eb65aac8e3e7cd0126e65ca3998bfe167e2d73

32 files changed:
folly/AtomicHashArray.h
folly/AtomicHashMap.h
folly/FBString.h
folly/FixedString.h
folly/Hash.h
folly/IPAddressV4.h
folly/IPAddressV6.h
folly/Makefile.am
folly/Singleton.h
folly/SocketAddress.cpp
folly/Uri-inl.h
folly/concurrency/CacheLocality.h
folly/concurrency/test/ConcurrentHashMapTest.cpp
folly/detail/Futex.cpp
folly/detail/MemoryIdler.h
folly/dynamic.cpp
folly/experimental/FunctionScheduler.h
folly/experimental/StringKeyedUnorderedMap.h
folly/experimental/StringKeyedUnorderedSet.h
folly/experimental/symbolizer/ElfCache.h
folly/experimental/test/StringKeyedTest.cpp
folly/hash/Hash.h [new file with mode: 0644]
folly/hash/test/ChecksumTest.cpp
folly/hash/test/HashBenchmark.cpp [new file with mode: 0644]
folly/hash/test/HashTest.cpp [new file with mode: 0644]
folly/io/test/CompressionTest.cpp
folly/test/AtomicHashArrayTest.cpp
folly/test/ConcurrentSkipListBenchmark.cpp
folly/test/HashBenchmark.cpp [deleted file]
folly/test/HashTest.cpp [deleted file]
folly/test/Makefile.am
folly/test/ThreadCachedIntTest.cpp

index 16b8dad..654077b 100644 (file)
@@ -37,9 +37,9 @@
 #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 {
 
index af8aa63..a3f42c0 100644 (file)
@@ -92,9 +92,9 @@
 
 #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 {
 
index b566d11..4cdafcf 100644 (file)
@@ -54,9 +54,9 @@
 #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.
index 732ae6a..d94468c 100644 (file)
@@ -409,7 +409,7 @@ struct ReverseIterator {
 } // namespace fixedstring
 } // namespace detail
 
-// Defined in folly/Hash.h
+// Defined in folly/hash/Hash.h
 std::uint32_t hsieh_hash32_buf(const void* buf, std::size_t len);
 
 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
index 410d272..22b7f14 100644 (file)
 
 #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 <folly/hash/Hash.h>
index 96de8ad..76534ad 100644 (file)
@@ -23,9 +23,9 @@
 #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 {
 
index f641bdc..78ec4c7 100644 (file)
 #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 {
 
index ce29ac0..439ea6b 100644 (file)
@@ -229,6 +229,7 @@ nobase_follyinclude_HEADERS = \
        futures/test/TestExecutor.h \
        hash/Checksum.h \
        hash/detail/ChecksumDetail.h \
+       hash/Hash.h \
        hash/SpookyHashV1.h \
        hash/SpookyHashV2.h \
        gen/Base.h \
@@ -246,7 +247,6 @@ nobase_follyinclude_HEADERS = \
        gen/String.h \
        gen/String-inl.h \
        GroupVarint.h \
-       Hash.h \
        IPAddress.h \
        IPAddressV4.h \
        IPAddressV6.h \
index 028cf7f..413b51f 100644 (file)
 #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>
index 6cb5a7a..af6cd77 100644 (file)
@@ -32,7 +32,7 @@
 #include <folly/CppAttributes.h>
 #include <folly/Exception.h>
 #include <folly/Format.h>
-#include <folly/Hash.h>
+#include <folly/hash/Hash.h>
 
 namespace {
 
index 6445eef..50d57c2 100644 (file)
@@ -22,7 +22,7 @@
 #include <tuple>
 
 #include <folly/Conv.h>
-#include <folly/Hash.h>
+#include <folly/hash/Hash.h>
 
 namespace folly {
 
index 38f5557..ecbed1e 100644 (file)
 #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>
 
index cf283c4..32b3d8a 100644 (file)
@@ -17,8 +17,8 @@
 #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>
 
index 8604a74..da7a04d 100644 (file)
@@ -16,8 +16,8 @@
 
 #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>
index fcbde00..fc7c8b7 100644 (file)
 #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 {
 
index 08e9747..3ac1173 100644 (file)
@@ -18,7 +18,7 @@
 
 #include <folly/Assume.h>
 #include <folly/Format.h>
-#include <folly/Hash.h>
+#include <folly/hash/Hash.h>
 #include <folly/portability/BitsFunctexcept.h>
 
 namespace folly {
index fbc7399..e8765fa 100644 (file)
 
 #include <folly/Function.h>
 #include <folly/Range.h>
-#include <folly/Hash.h>
+#include <folly/hash/Hash.h>
 #include <chrono>
 #include <condition_variable>
 #include <mutex>
 #include <thread>
-#include <vector>
 #include <unordered_map>
+#include <vector>
 
 namespace folly {
 
index 41180cb..4cf33b4 100644 (file)
@@ -24,9 +24,9 @@
 #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 {
 
index 11317ed..269d2e6 100644 (file)
@@ -24,9 +24,9 @@
 #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 {
 
index b9d7d96..57a36cf 100644 (file)
@@ -29,9 +29,9 @@
 #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 {
index b674445..072500b 100644 (file)
@@ -25,8 +25,8 @@
 
 #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>
 
diff --git a/folly/hash/Hash.h b/folly/hash/Hash.h
new file mode 100644 (file)
index 0000000..410d272
--- /dev/null
@@ -0,0 +1,519 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <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
index e5e613c..05ac6e5 100644 (file)
@@ -19,7 +19,7 @@
 #include <boost/crc.hpp>
 
 #include <folly/Benchmark.h>
-#include <folly/Hash.h>
+#include <folly/hash/Hash.h>
 #include <folly/hash/detail/ChecksumDetail.h>
 #include <folly/portability/GFlags.h>
 #include <folly/portability/GTest.h>
diff --git a/folly/hash/test/HashBenchmark.cpp b/folly/hash/test/HashBenchmark.cpp
new file mode 100644 (file)
index 0000000..f387f5a
--- /dev/null
@@ -0,0 +1,146 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <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
diff --git a/folly/hash/test/HashTest.cpp b/folly/hash/test/HashTest.cpp
new file mode 100644 (file)
index 0000000..fe7a804
--- /dev/null
@@ -0,0 +1,452 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <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}));
index 69a037d..69069c8 100644 (file)
 #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>
 
index 780076a..531732c 100644 (file)
@@ -20,8 +20,8 @@
 
 #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>
 
index cfe9aa9..97c2762 100644 (file)
@@ -23,8 +23,8 @@
 
 #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>
 
diff --git a/folly/test/HashBenchmark.cpp b/folly/test/HashBenchmark.cpp
deleted file mode 100644 (file)
index 4595a6e..0000000
+++ /dev/null
@@ -1,146 +0,0 @@
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <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
diff --git a/folly/test/HashTest.cpp b/folly/test/HashTest.cpp
deleted file mode 100644 (file)
index 759f997..0000000
+++ /dev/null
@@ -1,452 +0,0 @@
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <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}));
index a2f5883..22c1127 100644 (file)
@@ -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 = HashTest.cpp
+hash_test_SOURCES = ../hash/test/HashTest.cpp
 hash_test_LDADD = libfollytestmain.la
 
 invoke_test_SOURCES = ../functional/test/InvokeTest.cpp
index e09c780..588aa52 100644 (file)
@@ -23,8 +23,8 @@
 #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>