Allow std::unordered_*.

base/hash.h

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef BASE_HASH_H_
 #define BASE_HASH_H_
 
 #include <stddef.h>
 #include <stdint.h>
 
 #include <limits>
 #include <string>
+#include <utility>
 
 #include "base/base_export.h"
 #include "base/logging.h"
 
 namespace base {
 
 // WARNING: This hash function should not be used for any cryptographic purpose.
 BASE_EXPORT uint32_t SuperFastHash(const char* data, int len);
 
 // Computes a hash of a memory buffer |data| of a given |length|.
 // WARNING: This hash function should not be used for any cryptographic purpose.
 inline uint32_t Hash(const char* data, size_t length) {
   if (length > static_cast<size_t>(std::numeric_limits<int>::max())) {
     NOTREACHED();
     return 0;
   }
   return SuperFastHash(data, static_cast<int>(length));
 }
 
 // Computes a hash of a string |str|.
 // WARNING: This hash function should not be used for any cryptographic purpose.
 inline uint32_t Hash(const std::string& str) {
   return Hash(str.data(), str.size());
 }
 
+// Implement hashing for pairs of at-most 32 bit integer values.
+// When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using
+// multiply-add hashing. This algorithm, as described in
+// Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in
+// eingeschränkten Branchingprogrammmodellen" by Woelfel, is:
+//
+//   h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32
+//
+// Contact danakj@chromium.org for any questions.
+inline size_t HashInts32(uint32_t value1, uint32_t value2) {

[davidben, 2016/01/16 00:22:23]

I switched std::size_t to size_t to avoid having to include both cstddef and
stddef.h in the same header as that seemed kinda silly. I'm assuming these are
always going to be the same.

[danakj, 2016/01/19 21:21:55]

Ya they will, cool.

+  uint64_t value1_64 = value1;
+  uint64_t hash64 = (value1_64 << 32) | value2;
+
+  if (sizeof(size_t) >= sizeof(uint64_t))
+    return static_cast<size_t>(hash64);
+
+  uint64_t odd_random = 481046412LL << 32 | 1025306955LL;
+  uint32_t shift_random = 10121U << 16;
+
+  hash64 = hash64 * odd_random + shift_random;
+  size_t high_bits = static_cast<size_t>(
+      hash64 >> (8 * (sizeof(uint64_t) - sizeof(size_t))));
+  return high_bits;
+}
+
+// Implement hashing for pairs of up-to 64-bit integer values.
+// We use the compound integer hash method to produce a 64-bit hash code, by
+// breaking the two 64-bit inputs into 4 32-bit values:
+// http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
+// Then we reduce our result to 32 bits if required, similar to above.
+inline size_t HashInts64(uint64_t value1, uint64_t value2) {
+  uint32_t short_random1 = 842304669U;
+  uint32_t short_random2 = 619063811U;
+  uint32_t short_random3 = 937041849U;
+  uint32_t short_random4 = 3309708029U;
+
+  uint32_t value1a = static_cast<uint32_t>(value1 & 0xffffffff);
+  uint32_t value1b = static_cast<uint32_t>((value1 >> 32) & 0xffffffff);
+  uint32_t value2a = static_cast<uint32_t>(value2 & 0xffffffff);
+  uint32_t value2b = static_cast<uint32_t>((value2 >> 32) & 0xffffffff);
+
+  uint64_t product1 = static_cast<uint64_t>(value1a) * short_random1;
+  uint64_t product2 = static_cast<uint64_t>(value1b) * short_random2;
+  uint64_t product3 = static_cast<uint64_t>(value2a) * short_random3;
+  uint64_t product4 = static_cast<uint64_t>(value2b) * short_random4;
+
+  uint64_t hash64 = product1 + product2 + product3 + product4;
+
+  if (sizeof(size_t) >= sizeof(uint64_t))
+    return static_cast<size_t>(hash64);
+
+  uint64_t odd_random = 1578233944LL << 32 | 194370989LL;
+  uint32_t shift_random = 20591U << 16;
+
+  hash64 = hash64 * odd_random + shift_random;
+  size_t high_bits = static_cast<size_t>(
+      hash64 >> (8 * (sizeof(uint64_t) - sizeof(size_t))));
+  return high_bits;
+}
+
+template<typename T1, typename T2>
+inline size_t HashInts(T1 value1, T2 value2) {
+  // This condition is expected to be compile-time evaluated and optimised away
+  // in release builds.
+  if (sizeof(T1) > sizeof(uint32_t) || (sizeof(T2) > sizeof(uint32_t)))
+    return HashInts64(value1, value2);
+
+  return HashInts32(value1, value2);
+}
+
+// A templated hasher for pairs of integer types.
+template<typename T> struct IntPairHash;
+
+template<typename Type1, typename Type2>
+struct IntPairHash<std::pair<Type1, Type2>> {

[davidben, 2016/01/16 00:22:23]

Is there a better way to do this? / Should I be doing this?

I switched it from a two-argument IntPairHash because most of the consumers I
found do something like...

using MyCoolId = std::pair<int, SomeEnumThatIsAlsoAnInt>;
using MyCoolHash = base::hash_set<MyCoolId>;

So it seems better to switch to

using MyCoolHash = base::hash_set<MyCoolId, IntPairHash<MyCoolId>>;

rather than

using MyCoolHash = base::hash_set<MyCoolId, IntPairHash<int,
SomeEnumThatIsAlsoAnInt>>;

But I can switch it back if the old one was better. This is also not actually
used right now, so we can leave it out and expect code to be converted to a call
to HashInts on a call-by-call basis. I don't have strong opinions.

[danakj, 2016/01/19 21:21:54]

I'm uh.. staring at this pretending I know C++ but I just don't see what you've
changed from before.

The old code was:
template<typename Type1, typename Type2>
struct hash<std::pair<Type1, Type2> > {
  std::size_t operator()(std::pair<Type1, Type2> value) const {const {
    return base::HashPair(value.first, value.second);	  36     return
base::HashInts(value.first, value.second);
  }
};


The new code looks the same wrt the templates. That said passing the pair as the
type argument instead of the 2 values does seem ok, and would work for anything
with a .first and .second.. so what am I missing here..?

[davidben, 2016/01/19 22:30:28]

Oh, sorry, that was ambiguous. By "the old one", I meant "a previous patch set's
version of the new code".

https://codereview.chromium.org/1502373009/diff/220001/base/hash.h#pair-109

The difference being whether IntPairHash takes a single template argument that
must be std::pair<T1, T2> or if it takes two template arguments, T1 and T2.

Originally I did the latter, but I think taking the single argument is a bit
better because it's friendlier to typedefs.

+  size_t operator()(std::pair<Type1, Type2> value) const {
+    return HashInts(value.first, value.second);
+  }
+};
+
 }  // namespace base
 
 #endif  // BASE_HASH_H_