Home | History | Annotate | Download | only in ADT
      1 //===-- llvm/ADT/Hashing.h - Utilities for hashing --------------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the newly proposed standard C++ interfaces for hashing
     11 // arbitrary data and building hash functions for user-defined types. This
     12 // interface was originally proposed in N3333[1] and is currently under review
     13 // for inclusion in a future TR and/or standard.
     14 //
     15 // The primary interfaces provide are comprised of one type and three functions:
     16 //
     17 //  -- 'hash_code' class is an opaque type representing the hash code for some
     18 //     data. It is the intended product of hashing, and can be used to implement
     19 //     hash tables, checksumming, and other common uses of hashes. It is not an
     20 //     integer type (although it can be converted to one) because it is risky
     21 //     to assume much about the internals of a hash_code. In particular, each
     22 //     execution of the program has a high probability of producing a different
     23 //     hash_code for a given input. Thus their values are not stable to save or
     24 //     persist, and should only be used during the execution for the
     25 //     construction of hashing datastructures.
     26 //
     27 //  -- 'hash_value' is a function designed to be overloaded for each
     28 //     user-defined type which wishes to be used within a hashing context. It
     29 //     should be overloaded within the user-defined type's namespace and found
     30 //     via ADL. Overloads for primitive types are provided by this library.
     31 //
     32 //  -- 'hash_combine' and 'hash_combine_range' are functions designed to aid
     33 //      programmers in easily and intuitively combining a set of data into
     34 //      a single hash_code for their object. They should only logically be used
     35 //      within the implementation of a 'hash_value' routine or similar context.
     36 //
     37 // Note that 'hash_combine_range' contains very special logic for hashing
     38 // a contiguous array of integers or pointers. This logic is *extremely* fast,
     39 // on a modern Intel "Gainestown" Xeon (Nehalem uarch) @2.2 GHz, these were
     40 // benchmarked at over 6.5 GiB/s for large keys, and <20 cycles/hash for keys
     41 // under 32-bytes.
     42 //
     43 //===----------------------------------------------------------------------===//
     44 
     45 #ifndef LLVM_ADT_HASHING_H
     46 #define LLVM_ADT_HASHING_H
     47 
     48 #include "llvm/Support/DataTypes.h"
     49 #include "llvm/Support/Host.h"
     50 #include "llvm/Support/SwapByteOrder.h"
     51 #include "llvm/Support/type_traits.h"
     52 #include <algorithm>
     53 #include <cassert>
     54 #include <cstring>
     55 #include <iterator>
     56 #include <string>
     57 #include <utility>
     58 
     59 namespace llvm {
     60 
     61 /// \brief An opaque object representing a hash code.
     62 ///
     63 /// This object represents the result of hashing some entity. It is intended to
     64 /// be used to implement hashtables or other hashing-based data structures.
     65 /// While it wraps and exposes a numeric value, this value should not be
     66 /// trusted to be stable or predictable across processes or executions.
     67 ///
     68 /// In order to obtain the hash_code for an object 'x':
     69 /// \code
     70 ///   using llvm::hash_value;
     71 ///   llvm::hash_code code = hash_value(x);
     72 /// \endcode
     73 class hash_code {
     74   size_t value;
     75 
     76 public:
     77   /// \brief Default construct a hash_code.
     78   /// Note that this leaves the value uninitialized.
     79   hash_code() = default;
     80 
     81   /// \brief Form a hash code directly from a numerical value.
     82   hash_code(size_t value) : value(value) {}
     83 
     84   /// \brief Convert the hash code to its numerical value for use.
     85   /*explicit*/ operator size_t() const { return value; }
     86 
     87   friend bool operator==(const hash_code &lhs, const hash_code &rhs) {
     88     return lhs.value == rhs.value;
     89   }
     90   friend bool operator!=(const hash_code &lhs, const hash_code &rhs) {
     91     return lhs.value != rhs.value;
     92   }
     93 
     94   /// \brief Allow a hash_code to be directly run through hash_value.
     95   friend size_t hash_value(const hash_code &code) { return code.value; }
     96 };
     97 
     98 /// \brief Compute a hash_code for any integer value.
     99 ///
    100 /// Note that this function is intended to compute the same hash_code for
    101 /// a particular value without regard to the pre-promotion type. This is in
    102 /// contrast to hash_combine which may produce different hash_codes for
    103 /// differing argument types even if they would implicit promote to a common
    104 /// type without changing the value.
    105 template <typename T>
    106 typename std::enable_if<is_integral_or_enum<T>::value, hash_code>::type
    107 hash_value(T value);
    108 
    109 /// \brief Compute a hash_code for a pointer's address.
    110 ///
    111 /// N.B.: This hashes the *address*. Not the value and not the type.
    112 template <typename T> hash_code hash_value(const T *ptr);
    113 
    114 /// \brief Compute a hash_code for a pair of objects.
    115 template <typename T, typename U>
    116 hash_code hash_value(const std::pair<T, U> &arg);
    117 
    118 /// \brief Compute a hash_code for a standard string.
    119 template <typename T>
    120 hash_code hash_value(const std::basic_string<T> &arg);
    121 
    122 
    123 /// \brief Override the execution seed with a fixed value.
    124 ///
    125 /// This hashing library uses a per-execution seed designed to change on each
    126 /// run with high probability in order to ensure that the hash codes are not
    127 /// attackable and to ensure that output which is intended to be stable does
    128 /// not rely on the particulars of the hash codes produced.
    129 ///
    130 /// That said, there are use cases where it is important to be able to
    131 /// reproduce *exactly* a specific behavior. To that end, we provide a function
    132 /// which will forcibly set the seed to a fixed value. This must be done at the
    133 /// start of the program, before any hashes are computed. Also, it cannot be
    134 /// undone. This makes it thread-hostile and very hard to use outside of
    135 /// immediately on start of a simple program designed for reproducible
    136 /// behavior.
    137 void set_fixed_execution_hash_seed(size_t fixed_value);
    138 
    139 
    140 // All of the implementation details of actually computing the various hash
    141 // code values are held within this namespace. These routines are included in
    142 // the header file mainly to allow inlining and constant propagation.
    143 namespace hashing {
    144 namespace detail {
    145 
    146 inline uint64_t fetch64(const char *p) {
    147   uint64_t result;
    148   memcpy(&result, p, sizeof(result));
    149   if (sys::IsBigEndianHost)
    150     sys::swapByteOrder(result);
    151   return result;
    152 }
    153 
    154 inline uint32_t fetch32(const char *p) {
    155   uint32_t result;
    156   memcpy(&result, p, sizeof(result));
    157   if (sys::IsBigEndianHost)
    158     sys::swapByteOrder(result);
    159   return result;
    160 }
    161 
    162 /// Some primes between 2^63 and 2^64 for various uses.
    163 static const uint64_t k0 = 0xc3a5c85c97cb3127ULL;
    164 static const uint64_t k1 = 0xb492b66fbe98f273ULL;
    165 static const uint64_t k2 = 0x9ae16a3b2f90404fULL;
    166 static const uint64_t k3 = 0xc949d7c7509e6557ULL;
    167 
    168 /// \brief Bitwise right rotate.
    169 /// Normally this will compile to a single instruction, especially if the
    170 /// shift is a manifest constant.
    171 inline uint64_t rotate(uint64_t val, size_t shift) {
    172   // Avoid shifting by 64: doing so yields an undefined result.
    173   return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
    174 }
    175 
    176 inline uint64_t shift_mix(uint64_t val) {
    177   return val ^ (val >> 47);
    178 }
    179 
    180 inline uint64_t hash_16_bytes(uint64_t low, uint64_t high) {
    181   // Murmur-inspired hashing.
    182   const uint64_t kMul = 0x9ddfea08eb382d69ULL;
    183   uint64_t a = (low ^ high) * kMul;
    184   a ^= (a >> 47);
    185   uint64_t b = (high ^ a) * kMul;
    186   b ^= (b >> 47);
    187   b *= kMul;
    188   return b;
    189 }
    190 
    191 inline uint64_t hash_1to3_bytes(const char *s, size_t len, uint64_t seed) {
    192   uint8_t a = s[0];
    193   uint8_t b = s[len >> 1];
    194   uint8_t c = s[len - 1];
    195   uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
    196   uint32_t z = len + (static_cast<uint32_t>(c) << 2);
    197   return shift_mix(y * k2 ^ z * k3 ^ seed) * k2;
    198 }
    199 
    200 inline uint64_t hash_4to8_bytes(const char *s, size_t len, uint64_t seed) {
    201   uint64_t a = fetch32(s);
    202   return hash_16_bytes(len + (a << 3), seed ^ fetch32(s + len - 4));
    203 }
    204 
    205 inline uint64_t hash_9to16_bytes(const char *s, size_t len, uint64_t seed) {
    206   uint64_t a = fetch64(s);
    207   uint64_t b = fetch64(s + len - 8);
    208   return hash_16_bytes(seed ^ a, rotate(b + len, len)) ^ b;
    209 }
    210 
    211 inline uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed) {
    212   uint64_t a = fetch64(s) * k1;
    213   uint64_t b = fetch64(s + 8);
    214   uint64_t c = fetch64(s + len - 8) * k2;
    215   uint64_t d = fetch64(s + len - 16) * k0;
    216   return hash_16_bytes(rotate(a - b, 43) + rotate(c ^ seed, 30) + d,
    217                        a + rotate(b ^ k3, 20) - c + len + seed);
    218 }
    219 
    220 inline uint64_t hash_33to64_bytes(const char *s, size_t len, uint64_t seed) {
    221   uint64_t z = fetch64(s + 24);
    222   uint64_t a = fetch64(s) + (len + fetch64(s + len - 16)) * k0;
    223   uint64_t b = rotate(a + z, 52);
    224   uint64_t c = rotate(a, 37);
    225   a += fetch64(s + 8);
    226   c += rotate(a, 7);
    227   a += fetch64(s + 16);
    228   uint64_t vf = a + z;
    229   uint64_t vs = b + rotate(a, 31) + c;
    230   a = fetch64(s + 16) + fetch64(s + len - 32);
    231   z = fetch64(s + len - 8);
    232   b = rotate(a + z, 52);
    233   c = rotate(a, 37);
    234   a += fetch64(s + len - 24);
    235   c += rotate(a, 7);
    236   a += fetch64(s + len - 16);
    237   uint64_t wf = a + z;
    238   uint64_t ws = b + rotate(a, 31) + c;
    239   uint64_t r = shift_mix((vf + ws) * k2 + (wf + vs) * k0);
    240   return shift_mix((seed ^ (r * k0)) + vs) * k2;
    241 }
    242 
    243 inline uint64_t hash_short(const char *s, size_t length, uint64_t seed) {
    244   if (length >= 4 && length <= 8)
    245     return hash_4to8_bytes(s, length, seed);
    246   if (length > 8 && length <= 16)
    247     return hash_9to16_bytes(s, length, seed);
    248   if (length > 16 && length <= 32)
    249     return hash_17to32_bytes(s, length, seed);
    250   if (length > 32)
    251     return hash_33to64_bytes(s, length, seed);
    252   if (length != 0)
    253     return hash_1to3_bytes(s, length, seed);
    254 
    255   return k2 ^ seed;
    256 }
    257 
    258 /// \brief The intermediate state used during hashing.
    259 /// Currently, the algorithm for computing hash codes is based on CityHash and
    260 /// keeps 56 bytes of arbitrary state.
    261 struct hash_state {
    262   uint64_t h0, h1, h2, h3, h4, h5, h6;
    263 
    264   /// \brief Create a new hash_state structure and initialize it based on the
    265   /// seed and the first 64-byte chunk.
    266   /// This effectively performs the initial mix.
    267   static hash_state create(const char *s, uint64_t seed) {
    268     hash_state state = {
    269       0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49),
    270       seed * k1, shift_mix(seed), 0 };
    271     state.h6 = hash_16_bytes(state.h4, state.h5);
    272     state.mix(s);
    273     return state;
    274   }
    275 
    276   /// \brief Mix 32-bytes from the input sequence into the 16-bytes of 'a'
    277   /// and 'b', including whatever is already in 'a' and 'b'.
    278   static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b) {
    279     a += fetch64(s);
    280     uint64_t c = fetch64(s + 24);
    281     b = rotate(b + a + c, 21);
    282     uint64_t d = a;
    283     a += fetch64(s + 8) + fetch64(s + 16);
    284     b += rotate(a, 44) + d;
    285     a += c;
    286   }
    287 
    288   /// \brief Mix in a 64-byte buffer of data.
    289   /// We mix all 64 bytes even when the chunk length is smaller, but we
    290   /// record the actual length.
    291   void mix(const char *s) {
    292     h0 = rotate(h0 + h1 + h3 + fetch64(s + 8), 37) * k1;
    293     h1 = rotate(h1 + h4 + fetch64(s + 48), 42) * k1;
    294     h0 ^= h6;
    295     h1 += h3 + fetch64(s + 40);
    296     h2 = rotate(h2 + h5, 33) * k1;
    297     h3 = h4 * k1;
    298     h4 = h0 + h5;
    299     mix_32_bytes(s, h3, h4);
    300     h5 = h2 + h6;
    301     h6 = h1 + fetch64(s + 16);
    302     mix_32_bytes(s + 32, h5, h6);
    303     std::swap(h2, h0);
    304   }
    305 
    306   /// \brief Compute the final 64-bit hash code value based on the current
    307   /// state and the length of bytes hashed.
    308   uint64_t finalize(size_t length) {
    309     return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
    310                          hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0);
    311   }
    312 };
    313 
    314 
    315 /// \brief A global, fixed seed-override variable.
    316 ///
    317 /// This variable can be set using the \see llvm::set_fixed_execution_seed
    318 /// function. See that function for details. Do not, under any circumstances,
    319 /// set or read this variable.
    320 extern size_t fixed_seed_override;
    321 
    322 inline size_t get_execution_seed() {
    323   // FIXME: This needs to be a per-execution seed. This is just a placeholder
    324   // implementation. Switching to a per-execution seed is likely to flush out
    325   // instability bugs and so will happen as its own commit.
    326   //
    327   // However, if there is a fixed seed override set the first time this is
    328   // called, return that instead of the per-execution seed.
    329   const uint64_t seed_prime = 0xff51afd7ed558ccdULL;
    330   static size_t seed = fixed_seed_override ? fixed_seed_override
    331                                            : (size_t)seed_prime;
    332   return seed;
    333 }
    334 
    335 
    336 /// \brief Trait to indicate whether a type's bits can be hashed directly.
    337 ///
    338 /// A type trait which is true if we want to combine values for hashing by
    339 /// reading the underlying data. It is false if values of this type must
    340 /// first be passed to hash_value, and the resulting hash_codes combined.
    341 //
    342 // FIXME: We want to replace is_integral_or_enum and is_pointer here with
    343 // a predicate which asserts that comparing the underlying storage of two
    344 // values of the type for equality is equivalent to comparing the two values
    345 // for equality. For all the platforms we care about, this holds for integers
    346 // and pointers, but there are platforms where it doesn't and we would like to
    347 // support user-defined types which happen to satisfy this property.
    348 template <typename T> struct is_hashable_data
    349   : std::integral_constant<bool, ((is_integral_or_enum<T>::value ||
    350                                    std::is_pointer<T>::value) &&
    351                                   64 % sizeof(T) == 0)> {};
    352 
    353 // Special case std::pair to detect when both types are viable and when there
    354 // is no alignment-derived padding in the pair. This is a bit of a lie because
    355 // std::pair isn't truly POD, but it's close enough in all reasonable
    356 // implementations for our use case of hashing the underlying data.
    357 template <typename T, typename U> struct is_hashable_data<std::pair<T, U> >
    358   : std::integral_constant<bool, (is_hashable_data<T>::value &&
    359                                   is_hashable_data<U>::value &&
    360                                   (sizeof(T) + sizeof(U)) ==
    361                                    sizeof(std::pair<T, U>))> {};
    362 
    363 /// \brief Helper to get the hashable data representation for a type.
    364 /// This variant is enabled when the type itself can be used.
    365 template <typename T>
    366 typename std::enable_if<is_hashable_data<T>::value, T>::type
    367 get_hashable_data(const T &value) {
    368   return value;
    369 }
    370 /// \brief Helper to get the hashable data representation for a type.
    371 /// This variant is enabled when we must first call hash_value and use the
    372 /// result as our data.
    373 template <typename T>
    374 typename std::enable_if<!is_hashable_data<T>::value, size_t>::type
    375 get_hashable_data(const T &value) {
    376   using ::llvm::hash_value;
    377   return hash_value(value);
    378 }
    379 
    380 /// \brief Helper to store data from a value into a buffer and advance the
    381 /// pointer into that buffer.
    382 ///
    383 /// This routine first checks whether there is enough space in the provided
    384 /// buffer, and if not immediately returns false. If there is space, it
    385 /// copies the underlying bytes of value into the buffer, advances the
    386 /// buffer_ptr past the copied bytes, and returns true.
    387 template <typename T>
    388 bool store_and_advance(char *&buffer_ptr, char *buffer_end, const T& value,
    389                        size_t offset = 0) {
    390   size_t store_size = sizeof(value) - offset;
    391   if (buffer_ptr + store_size > buffer_end)
    392     return false;
    393   const char *value_data = reinterpret_cast<const char *>(&value);
    394   memcpy(buffer_ptr, value_data + offset, store_size);
    395   buffer_ptr += store_size;
    396   return true;
    397 }
    398 
    399 /// \brief Implement the combining of integral values into a hash_code.
    400 ///
    401 /// This overload is selected when the value type of the iterator is
    402 /// integral. Rather than computing a hash_code for each object and then
    403 /// combining them, this (as an optimization) directly combines the integers.
    404 template <typename InputIteratorT>
    405 hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) {
    406   const size_t seed = get_execution_seed();
    407   char buffer[64], *buffer_ptr = buffer;
    408   char *const buffer_end = std::end(buffer);
    409   while (first != last && store_and_advance(buffer_ptr, buffer_end,
    410                                             get_hashable_data(*first)))
    411     ++first;
    412   if (first == last)
    413     return hash_short(buffer, buffer_ptr - buffer, seed);
    414   assert(buffer_ptr == buffer_end);
    415 
    416   hash_state state = state.create(buffer, seed);
    417   size_t length = 64;
    418   while (first != last) {
    419     // Fill up the buffer. We don't clear it, which re-mixes the last round
    420     // when only a partial 64-byte chunk is left.
    421     buffer_ptr = buffer;
    422     while (first != last && store_and_advance(buffer_ptr, buffer_end,
    423                                               get_hashable_data(*first)))
    424       ++first;
    425 
    426     // Rotate the buffer if we did a partial fill in order to simulate doing
    427     // a mix of the last 64-bytes. That is how the algorithm works when we
    428     // have a contiguous byte sequence, and we want to emulate that here.
    429     std::rotate(buffer, buffer_ptr, buffer_end);
    430 
    431     // Mix this chunk into the current state.
    432     state.mix(buffer);
    433     length += buffer_ptr - buffer;
    434   };
    435 
    436   return state.finalize(length);
    437 }
    438 
    439 /// \brief Implement the combining of integral values into a hash_code.
    440 ///
    441 /// This overload is selected when the value type of the iterator is integral
    442 /// and when the input iterator is actually a pointer. Rather than computing
    443 /// a hash_code for each object and then combining them, this (as an
    444 /// optimization) directly combines the integers. Also, because the integers
    445 /// are stored in contiguous memory, this routine avoids copying each value
    446 /// and directly reads from the underlying memory.
    447 template <typename ValueT>
    448 typename std::enable_if<is_hashable_data<ValueT>::value, hash_code>::type
    449 hash_combine_range_impl(ValueT *first, ValueT *last) {
    450   const size_t seed = get_execution_seed();
    451   const char *s_begin = reinterpret_cast<const char *>(first);
    452   const char *s_end = reinterpret_cast<const char *>(last);
    453   const size_t length = std::distance(s_begin, s_end);
    454   if (length <= 64)
    455     return hash_short(s_begin, length, seed);
    456 
    457   const char *s_aligned_end = s_begin + (length & ~63);
    458   hash_state state = state.create(s_begin, seed);
    459   s_begin += 64;
    460   while (s_begin != s_aligned_end) {
    461     state.mix(s_begin);
    462     s_begin += 64;
    463   }
    464   if (length & 63)
    465     state.mix(s_end - 64);
    466 
    467   return state.finalize(length);
    468 }
    469 
    470 } // namespace detail
    471 } // namespace hashing
    472 
    473 
    474 /// \brief Compute a hash_code for a sequence of values.
    475 ///
    476 /// This hashes a sequence of values. It produces the same hash_code as
    477 /// 'hash_combine(a, b, c, ...)', but can run over arbitrary sized sequences
    478 /// and is significantly faster given pointers and types which can be hashed as
    479 /// a sequence of bytes.
    480 template <typename InputIteratorT>
    481 hash_code hash_combine_range(InputIteratorT first, InputIteratorT last) {
    482   return ::llvm::hashing::detail::hash_combine_range_impl(first, last);
    483 }
    484 
    485 
    486 // Implementation details for hash_combine.
    487 namespace hashing {
    488 namespace detail {
    489 
    490 /// \brief Helper class to manage the recursive combining of hash_combine
    491 /// arguments.
    492 ///
    493 /// This class exists to manage the state and various calls involved in the
    494 /// recursive combining of arguments used in hash_combine. It is particularly
    495 /// useful at minimizing the code in the recursive calls to ease the pain
    496 /// caused by a lack of variadic functions.
    497 struct hash_combine_recursive_helper {
    498   char buffer[64];
    499   hash_state state;
    500   const size_t seed;
    501 
    502 public:
    503   /// \brief Construct a recursive hash combining helper.
    504   ///
    505   /// This sets up the state for a recursive hash combine, including getting
    506   /// the seed and buffer setup.
    507   hash_combine_recursive_helper()
    508     : seed(get_execution_seed()) {}
    509 
    510   /// \brief Combine one chunk of data into the current in-flight hash.
    511   ///
    512   /// This merges one chunk of data into the hash. First it tries to buffer
    513   /// the data. If the buffer is full, it hashes the buffer into its
    514   /// hash_state, empties it, and then merges the new chunk in. This also
    515   /// handles cases where the data straddles the end of the buffer.
    516   template <typename T>
    517   char *combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data) {
    518     if (!store_and_advance(buffer_ptr, buffer_end, data)) {
    519       // Check for skew which prevents the buffer from being packed, and do
    520       // a partial store into the buffer to fill it. This is only a concern
    521       // with the variadic combine because that formation can have varying
    522       // argument types.
    523       size_t partial_store_size = buffer_end - buffer_ptr;
    524       memcpy(buffer_ptr, &data, partial_store_size);
    525 
    526       // If the store fails, our buffer is full and ready to hash. We have to
    527       // either initialize the hash state (on the first full buffer) or mix
    528       // this buffer into the existing hash state. Length tracks the *hashed*
    529       // length, not the buffered length.
    530       if (length == 0) {
    531         state = state.create(buffer, seed);
    532         length = 64;
    533       } else {
    534         // Mix this chunk into the current state and bump length up by 64.
    535         state.mix(buffer);
    536         length += 64;
    537       }
    538       // Reset the buffer_ptr to the head of the buffer for the next chunk of
    539       // data.
    540       buffer_ptr = buffer;
    541 
    542       // Try again to store into the buffer -- this cannot fail as we only
    543       // store types smaller than the buffer.
    544       if (!store_and_advance(buffer_ptr, buffer_end, data,
    545                              partial_store_size))
    546         abort();
    547     }
    548     return buffer_ptr;
    549   }
    550 
    551   /// \brief Recursive, variadic combining method.
    552   ///
    553   /// This function recurses through each argument, combining that argument
    554   /// into a single hash.
    555   template <typename T, typename ...Ts>
    556   hash_code combine(size_t length, char *buffer_ptr, char *buffer_end,
    557                     const T &arg, const Ts &...args) {
    558     buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg));
    559 
    560     // Recurse to the next argument.
    561     return combine(length, buffer_ptr, buffer_end, args...);
    562   }
    563 
    564   /// \brief Base case for recursive, variadic combining.
    565   ///
    566   /// The base case when combining arguments recursively is reached when all
    567   /// arguments have been handled. It flushes the remaining buffer and
    568   /// constructs a hash_code.
    569   hash_code combine(size_t length, char *buffer_ptr, char *buffer_end) {
    570     // Check whether the entire set of values fit in the buffer. If so, we'll
    571     // use the optimized short hashing routine and skip state entirely.
    572     if (length == 0)
    573       return hash_short(buffer, buffer_ptr - buffer, seed);
    574 
    575     // Mix the final buffer, rotating it if we did a partial fill in order to
    576     // simulate doing a mix of the last 64-bytes. That is how the algorithm
    577     // works when we have a contiguous byte sequence, and we want to emulate
    578     // that here.
    579     std::rotate(buffer, buffer_ptr, buffer_end);
    580 
    581     // Mix this chunk into the current state.
    582     state.mix(buffer);
    583     length += buffer_ptr - buffer;
    584 
    585     return state.finalize(length);
    586   }
    587 };
    588 
    589 } // namespace detail
    590 } // namespace hashing
    591 
    592 /// \brief Combine values into a single hash_code.
    593 ///
    594 /// This routine accepts a varying number of arguments of any type. It will
    595 /// attempt to combine them into a single hash_code. For user-defined types it
    596 /// attempts to call a \see hash_value overload (via ADL) for the type. For
    597 /// integer and pointer types it directly combines their data into the
    598 /// resulting hash_code.
    599 ///
    600 /// The result is suitable for returning from a user's hash_value
    601 /// *implementation* for their user-defined type. Consumers of a type should
    602 /// *not* call this routine, they should instead call 'hash_value'.
    603 template <typename ...Ts> hash_code hash_combine(const Ts &...args) {
    604   // Recursively hash each argument using a helper class.
    605   ::llvm::hashing::detail::hash_combine_recursive_helper helper;
    606   return helper.combine(0, helper.buffer, helper.buffer + 64, args...);
    607 }
    608 
    609 // Implementation details for implementations of hash_value overloads provided
    610 // here.
    611 namespace hashing {
    612 namespace detail {
    613 
    614 /// \brief Helper to hash the value of a single integer.
    615 ///
    616 /// Overloads for smaller integer types are not provided to ensure consistent
    617 /// behavior in the presence of integral promotions. Essentially,
    618 /// "hash_value('4')" and "hash_value('0' + 4)" should be the same.
    619 inline hash_code hash_integer_value(uint64_t value) {
    620   // Similar to hash_4to8_bytes but using a seed instead of length.
    621   const uint64_t seed = get_execution_seed();
    622   const char *s = reinterpret_cast<const char *>(&value);
    623   const uint64_t a = fetch32(s);
    624   return hash_16_bytes(seed + (a << 3), fetch32(s + 4));
    625 }
    626 
    627 } // namespace detail
    628 } // namespace hashing
    629 
    630 // Declared and documented above, but defined here so that any of the hashing
    631 // infrastructure is available.
    632 template <typename T>
    633 typename std::enable_if<is_integral_or_enum<T>::value, hash_code>::type
    634 hash_value(T value) {
    635   return ::llvm::hashing::detail::hash_integer_value(value);
    636 }
    637 
    638 // Declared and documented above, but defined here so that any of the hashing
    639 // infrastructure is available.
    640 template <typename T> hash_code hash_value(const T *ptr) {
    641   return ::llvm::hashing::detail::hash_integer_value(
    642     reinterpret_cast<uintptr_t>(ptr));
    643 }
    644 
    645 // Declared and documented above, but defined here so that any of the hashing
    646 // infrastructure is available.
    647 template <typename T, typename U>
    648 hash_code hash_value(const std::pair<T, U> &arg) {
    649   return hash_combine(arg.first, arg.second);
    650 }
    651 
    652 // Declared and documented above, but defined here so that any of the hashing
    653 // infrastructure is available.
    654 template <typename T>
    655 hash_code hash_value(const std::basic_string<T> &arg) {
    656   return hash_combine_range(arg.begin(), arg.end());
    657 }
    658 
    659 } // namespace llvm
    660 
    661 #endif
    662