1234285Sdim//===-- llvm/ADT/Hashing.h - Utilities for hashing --------------*- C++ -*-===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file implements the newly proposed standard C++ interfaces for hashing 11234285Sdim// arbitrary data and building hash functions for user-defined types. This 12234285Sdim// interface was originally proposed in N3333[1] and is currently under review 13234285Sdim// for inclusion in a future TR and/or standard. 14234285Sdim// 15234285Sdim// The primary interfaces provide are comprised of one type and three functions: 16234285Sdim// 17234285Sdim// -- 'hash_code' class is an opaque type representing the hash code for some 18234285Sdim// data. It is the intended product of hashing, and can be used to implement 19234285Sdim// hash tables, checksumming, and other common uses of hashes. It is not an 20234285Sdim// integer type (although it can be converted to one) because it is risky 21234285Sdim// to assume much about the internals of a hash_code. In particular, each 22234285Sdim// execution of the program has a high probability of producing a different 23234285Sdim// hash_code for a given input. Thus their values are not stable to save or 24234285Sdim// persist, and should only be used during the execution for the 25234285Sdim// construction of hashing datastructures. 26234285Sdim// 27234285Sdim// -- 'hash_value' is a function designed to be overloaded for each 28234285Sdim// user-defined type which wishes to be used within a hashing context. It 29234285Sdim// should be overloaded within the user-defined type's namespace and found 30234285Sdim// via ADL. Overloads for primitive types are provided by this library. 31234285Sdim// 32234285Sdim// -- 'hash_combine' and 'hash_combine_range' are functions designed to aid 33234285Sdim// programmers in easily and intuitively combining a set of data into 34234285Sdim// a single hash_code for their object. They should only logically be used 35234285Sdim// within the implementation of a 'hash_value' routine or similar context. 36234285Sdim// 37234285Sdim// Note that 'hash_combine_range' contains very special logic for hashing 38234285Sdim// a contiguous array of integers or pointers. This logic is *extremely* fast, 39234285Sdim// on a modern Intel "Gainestown" Xeon (Nehalem uarch) @2.2 GHz, these were 40234285Sdim// benchmarked at over 6.5 GiB/s for large keys, and <20 cycles/hash for keys 41234285Sdim// under 32-bytes. 42234285Sdim// 43234285Sdim//===----------------------------------------------------------------------===// 44234285Sdim 45234285Sdim#ifndef LLVM_ADT_HASHING_H 46234285Sdim#define LLVM_ADT_HASHING_H 47234285Sdim 48234285Sdim#include "llvm/ADT/STLExtras.h" 49234285Sdim#include "llvm/Support/DataTypes.h" 50234285Sdim#include "llvm/Support/Host.h" 51234285Sdim#include "llvm/Support/SwapByteOrder.h" 52234285Sdim#include "llvm/Support/type_traits.h" 53234285Sdim#include <algorithm> 54234285Sdim#include <cassert> 55234285Sdim#include <cstring> 56234285Sdim#include <iterator> 57234285Sdim#include <utility> 58234285Sdim 59234285Sdim// Allow detecting C++11 feature availability when building with Clang without 60234285Sdim// breaking other compilers. 61234285Sdim#ifndef __has_feature 62234285Sdim# define __has_feature(x) 0 63234285Sdim#endif 64234285Sdim 65234285Sdimnamespace llvm { 66234285Sdim 67234285Sdim/// \brief An opaque object representing a hash code. 68234285Sdim/// 69234285Sdim/// This object represents the result of hashing some entity. It is intended to 70234285Sdim/// be used to implement hashtables or other hashing-based data structures. 71234285Sdim/// While it wraps and exposes a numeric value, this value should not be 72234285Sdim/// trusted to be stable or predictable across processes or executions. 73234285Sdim/// 74234285Sdim/// In order to obtain the hash_code for an object 'x': 75234285Sdim/// \code 76234285Sdim/// using llvm::hash_value; 77234285Sdim/// llvm::hash_code code = hash_value(x); 78234285Sdim/// \endcode 79234285Sdimclass hash_code { 80234285Sdim size_t value; 81234285Sdim 82234285Sdimpublic: 83234285Sdim /// \brief Default construct a hash_code. 84234285Sdim /// Note that this leaves the value uninitialized. 85234285Sdim hash_code() {} 86234285Sdim 87234285Sdim /// \brief Form a hash code directly from a numerical value. 88234285Sdim hash_code(size_t value) : value(value) {} 89234285Sdim 90234285Sdim /// \brief Convert the hash code to its numerical value for use. 91234285Sdim /*explicit*/ operator size_t() const { return value; } 92234285Sdim 93234285Sdim friend bool operator==(const hash_code &lhs, const hash_code &rhs) { 94234285Sdim return lhs.value == rhs.value; 95234285Sdim } 96234285Sdim friend bool operator!=(const hash_code &lhs, const hash_code &rhs) { 97234285Sdim return lhs.value != rhs.value; 98234285Sdim } 99234285Sdim 100234285Sdim /// \brief Allow a hash_code to be directly run through hash_value. 101234285Sdim friend size_t hash_value(const hash_code &code) { return code.value; } 102234285Sdim}; 103234285Sdim 104234285Sdim/// \brief Compute a hash_code for any integer value. 105234285Sdim/// 106234285Sdim/// Note that this function is intended to compute the same hash_code for 107234285Sdim/// a particular value without regard to the pre-promotion type. This is in 108234285Sdim/// contrast to hash_combine which may produce different hash_codes for 109234285Sdim/// differing argument types even if they would implicit promote to a common 110234285Sdim/// type without changing the value. 111234285Sdimtemplate <typename T> 112234285Sdimtypename enable_if<is_integral_or_enum<T>, hash_code>::type hash_value(T value); 113234285Sdim 114234285Sdim/// \brief Compute a hash_code for a pointer's address. 115234285Sdim/// 116234285Sdim/// N.B.: This hashes the *address*. Not the value and not the type. 117234285Sdimtemplate <typename T> hash_code hash_value(const T *ptr); 118234285Sdim 119234285Sdim/// \brief Compute a hash_code for a pair of objects. 120234285Sdimtemplate <typename T, typename U> 121234285Sdimhash_code hash_value(const std::pair<T, U> &arg); 122234285Sdim 123234285Sdim/// \brief Compute a hash_code for a standard string. 124234285Sdimtemplate <typename T> 125234285Sdimhash_code hash_value(const std::basic_string<T> &arg); 126234285Sdim 127234285Sdim 128234285Sdim/// \brief Override the execution seed with a fixed value. 129234285Sdim/// 130234285Sdim/// This hashing library uses a per-execution seed designed to change on each 131234285Sdim/// run with high probability in order to ensure that the hash codes are not 132234285Sdim/// attackable and to ensure that output which is intended to be stable does 133234285Sdim/// not rely on the particulars of the hash codes produced. 134234285Sdim/// 135234285Sdim/// That said, there are use cases where it is important to be able to 136234285Sdim/// reproduce *exactly* a specific behavior. To that end, we provide a function 137234285Sdim/// which will forcibly set the seed to a fixed value. This must be done at the 138234285Sdim/// start of the program, before any hashes are computed. Also, it cannot be 139234285Sdim/// undone. This makes it thread-hostile and very hard to use outside of 140234285Sdim/// immediately on start of a simple program designed for reproducible 141234285Sdim/// behavior. 142234285Sdimvoid set_fixed_execution_hash_seed(size_t fixed_value); 143234285Sdim 144234285Sdim 145234285Sdim// All of the implementation details of actually computing the various hash 146234285Sdim// code values are held within this namespace. These routines are included in 147234285Sdim// the header file mainly to allow inlining and constant propagation. 148234285Sdimnamespace hashing { 149234285Sdimnamespace detail { 150234285Sdim 151234285Sdiminline uint64_t fetch64(const char *p) { 152234285Sdim uint64_t result; 153234285Sdim memcpy(&result, p, sizeof(result)); 154251662Sdim if (sys::IsBigEndianHost) 155234285Sdim return sys::SwapByteOrder(result); 156234285Sdim return result; 157234285Sdim} 158234285Sdim 159234285Sdiminline uint32_t fetch32(const char *p) { 160234285Sdim uint32_t result; 161234285Sdim memcpy(&result, p, sizeof(result)); 162251662Sdim if (sys::IsBigEndianHost) 163234285Sdim return sys::SwapByteOrder(result); 164234285Sdim return result; 165234285Sdim} 166234285Sdim 167234285Sdim/// Some primes between 2^63 and 2^64 for various uses. 168234285Sdimstatic const uint64_t k0 = 0xc3a5c85c97cb3127ULL; 169234285Sdimstatic const uint64_t k1 = 0xb492b66fbe98f273ULL; 170234285Sdimstatic const uint64_t k2 = 0x9ae16a3b2f90404fULL; 171234285Sdimstatic const uint64_t k3 = 0xc949d7c7509e6557ULL; 172234285Sdim 173234285Sdim/// \brief Bitwise right rotate. 174234285Sdim/// Normally this will compile to a single instruction, especially if the 175234285Sdim/// shift is a manifest constant. 176234285Sdiminline uint64_t rotate(uint64_t val, size_t shift) { 177234285Sdim // Avoid shifting by 64: doing so yields an undefined result. 178234285Sdim return shift == 0 ? val : ((val >> shift) | (val << (64 - shift))); 179234285Sdim} 180234285Sdim 181234285Sdiminline uint64_t shift_mix(uint64_t val) { 182234285Sdim return val ^ (val >> 47); 183234285Sdim} 184234285Sdim 185234285Sdiminline uint64_t hash_16_bytes(uint64_t low, uint64_t high) { 186234285Sdim // Murmur-inspired hashing. 187234285Sdim const uint64_t kMul = 0x9ddfea08eb382d69ULL; 188234285Sdim uint64_t a = (low ^ high) * kMul; 189234285Sdim a ^= (a >> 47); 190234285Sdim uint64_t b = (high ^ a) * kMul; 191234285Sdim b ^= (b >> 47); 192234285Sdim b *= kMul; 193234285Sdim return b; 194234285Sdim} 195234285Sdim 196234285Sdiminline uint64_t hash_1to3_bytes(const char *s, size_t len, uint64_t seed) { 197234285Sdim uint8_t a = s[0]; 198234285Sdim uint8_t b = s[len >> 1]; 199234285Sdim uint8_t c = s[len - 1]; 200234285Sdim uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8); 201234285Sdim uint32_t z = len + (static_cast<uint32_t>(c) << 2); 202234285Sdim return shift_mix(y * k2 ^ z * k3 ^ seed) * k2; 203234285Sdim} 204234285Sdim 205234285Sdiminline uint64_t hash_4to8_bytes(const char *s, size_t len, uint64_t seed) { 206234285Sdim uint64_t a = fetch32(s); 207234285Sdim return hash_16_bytes(len + (a << 3), seed ^ fetch32(s + len - 4)); 208234285Sdim} 209234285Sdim 210234285Sdiminline uint64_t hash_9to16_bytes(const char *s, size_t len, uint64_t seed) { 211234285Sdim uint64_t a = fetch64(s); 212234285Sdim uint64_t b = fetch64(s + len - 8); 213234285Sdim return hash_16_bytes(seed ^ a, rotate(b + len, len)) ^ b; 214234285Sdim} 215234285Sdim 216234285Sdiminline uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed) { 217234285Sdim uint64_t a = fetch64(s) * k1; 218234285Sdim uint64_t b = fetch64(s + 8); 219234285Sdim uint64_t c = fetch64(s + len - 8) * k2; 220234285Sdim uint64_t d = fetch64(s + len - 16) * k0; 221234285Sdim return hash_16_bytes(rotate(a - b, 43) + rotate(c ^ seed, 30) + d, 222234285Sdim a + rotate(b ^ k3, 20) - c + len + seed); 223234285Sdim} 224234285Sdim 225234285Sdiminline uint64_t hash_33to64_bytes(const char *s, size_t len, uint64_t seed) { 226234285Sdim uint64_t z = fetch64(s + 24); 227234285Sdim uint64_t a = fetch64(s) + (len + fetch64(s + len - 16)) * k0; 228234285Sdim uint64_t b = rotate(a + z, 52); 229234285Sdim uint64_t c = rotate(a, 37); 230234285Sdim a += fetch64(s + 8); 231234285Sdim c += rotate(a, 7); 232234285Sdim a += fetch64(s + 16); 233234285Sdim uint64_t vf = a + z; 234234285Sdim uint64_t vs = b + rotate(a, 31) + c; 235234285Sdim a = fetch64(s + 16) + fetch64(s + len - 32); 236234285Sdim z = fetch64(s + len - 8); 237234285Sdim b = rotate(a + z, 52); 238234285Sdim c = rotate(a, 37); 239234285Sdim a += fetch64(s + len - 24); 240234285Sdim c += rotate(a, 7); 241234285Sdim a += fetch64(s + len - 16); 242234285Sdim uint64_t wf = a + z; 243234285Sdim uint64_t ws = b + rotate(a, 31) + c; 244234285Sdim uint64_t r = shift_mix((vf + ws) * k2 + (wf + vs) * k0); 245234285Sdim return shift_mix((seed ^ (r * k0)) + vs) * k2; 246234285Sdim} 247234285Sdim 248234285Sdiminline uint64_t hash_short(const char *s, size_t length, uint64_t seed) { 249234285Sdim if (length >= 4 && length <= 8) 250234285Sdim return hash_4to8_bytes(s, length, seed); 251234285Sdim if (length > 8 && length <= 16) 252234285Sdim return hash_9to16_bytes(s, length, seed); 253234285Sdim if (length > 16 && length <= 32) 254234285Sdim return hash_17to32_bytes(s, length, seed); 255234285Sdim if (length > 32) 256234285Sdim return hash_33to64_bytes(s, length, seed); 257234285Sdim if (length != 0) 258234285Sdim return hash_1to3_bytes(s, length, seed); 259234285Sdim 260234285Sdim return k2 ^ seed; 261234285Sdim} 262234285Sdim 263234285Sdim/// \brief The intermediate state used during hashing. 264234285Sdim/// Currently, the algorithm for computing hash codes is based on CityHash and 265234285Sdim/// keeps 56 bytes of arbitrary state. 266234285Sdimstruct hash_state { 267234285Sdim uint64_t h0, h1, h2, h3, h4, h5, h6; 268234285Sdim uint64_t seed; 269234285Sdim 270234285Sdim /// \brief Create a new hash_state structure and initialize it based on the 271234285Sdim /// seed and the first 64-byte chunk. 272234285Sdim /// This effectively performs the initial mix. 273234285Sdim static hash_state create(const char *s, uint64_t seed) { 274234285Sdim hash_state state = { 275234285Sdim 0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49), 276234285Sdim seed * k1, shift_mix(seed), 0, seed }; 277234285Sdim state.h6 = hash_16_bytes(state.h4, state.h5); 278234285Sdim state.mix(s); 279234285Sdim return state; 280234285Sdim } 281234285Sdim 282234285Sdim /// \brief Mix 32-bytes from the input sequence into the 16-bytes of 'a' 283234285Sdim /// and 'b', including whatever is already in 'a' and 'b'. 284234285Sdim static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b) { 285234285Sdim a += fetch64(s); 286234285Sdim uint64_t c = fetch64(s + 24); 287234285Sdim b = rotate(b + a + c, 21); 288234285Sdim uint64_t d = a; 289234285Sdim a += fetch64(s + 8) + fetch64(s + 16); 290234285Sdim b += rotate(a, 44) + d; 291234285Sdim a += c; 292234285Sdim } 293234285Sdim 294234285Sdim /// \brief Mix in a 64-byte buffer of data. 295234285Sdim /// We mix all 64 bytes even when the chunk length is smaller, but we 296234285Sdim /// record the actual length. 297234285Sdim void mix(const char *s) { 298234285Sdim h0 = rotate(h0 + h1 + h3 + fetch64(s + 8), 37) * k1; 299234285Sdim h1 = rotate(h1 + h4 + fetch64(s + 48), 42) * k1; 300234285Sdim h0 ^= h6; 301234285Sdim h1 += h3 + fetch64(s + 40); 302234285Sdim h2 = rotate(h2 + h5, 33) * k1; 303234285Sdim h3 = h4 * k1; 304234285Sdim h4 = h0 + h5; 305234285Sdim mix_32_bytes(s, h3, h4); 306234285Sdim h5 = h2 + h6; 307234285Sdim h6 = h1 + fetch64(s + 16); 308234285Sdim mix_32_bytes(s + 32, h5, h6); 309234285Sdim std::swap(h2, h0); 310234285Sdim } 311234285Sdim 312234285Sdim /// \brief Compute the final 64-bit hash code value based on the current 313234285Sdim /// state and the length of bytes hashed. 314234285Sdim uint64_t finalize(size_t length) { 315234285Sdim return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2, 316234285Sdim hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0); 317234285Sdim } 318234285Sdim}; 319234285Sdim 320234285Sdim 321234285Sdim/// \brief A global, fixed seed-override variable. 322234285Sdim/// 323234285Sdim/// This variable can be set using the \see llvm::set_fixed_execution_seed 324234285Sdim/// function. See that function for details. Do not, under any circumstances, 325234285Sdim/// set or read this variable. 326234285Sdimextern size_t fixed_seed_override; 327234285Sdim 328234285Sdiminline size_t get_execution_seed() { 329234285Sdim // FIXME: This needs to be a per-execution seed. This is just a placeholder 330234285Sdim // implementation. Switching to a per-execution seed is likely to flush out 331234285Sdim // instability bugs and so will happen as its own commit. 332234285Sdim // 333234285Sdim // However, if there is a fixed seed override set the first time this is 334234285Sdim // called, return that instead of the per-execution seed. 335234285Sdim const uint64_t seed_prime = 0xff51afd7ed558ccdULL; 336234285Sdim static size_t seed = fixed_seed_override ? fixed_seed_override 337234285Sdim : (size_t)seed_prime; 338234285Sdim return seed; 339234285Sdim} 340234285Sdim 341234285Sdim 342234285Sdim/// \brief Trait to indicate whether a type's bits can be hashed directly. 343234285Sdim/// 344234285Sdim/// A type trait which is true if we want to combine values for hashing by 345234285Sdim/// reading the underlying data. It is false if values of this type must 346234285Sdim/// first be passed to hash_value, and the resulting hash_codes combined. 347234285Sdim// 348234285Sdim// FIXME: We want to replace is_integral_or_enum and is_pointer here with 349234285Sdim// a predicate which asserts that comparing the underlying storage of two 350234285Sdim// values of the type for equality is equivalent to comparing the two values 351234285Sdim// for equality. For all the platforms we care about, this holds for integers 352234285Sdim// and pointers, but there are platforms where it doesn't and we would like to 353234285Sdim// support user-defined types which happen to satisfy this property. 354234285Sdimtemplate <typename T> struct is_hashable_data 355234285Sdim : integral_constant<bool, ((is_integral_or_enum<T>::value || 356234285Sdim is_pointer<T>::value) && 357234285Sdim 64 % sizeof(T) == 0)> {}; 358234285Sdim 359234285Sdim// Special case std::pair to detect when both types are viable and when there 360234285Sdim// is no alignment-derived padding in the pair. This is a bit of a lie because 361234285Sdim// std::pair isn't truly POD, but it's close enough in all reasonable 362234285Sdim// implementations for our use case of hashing the underlying data. 363234285Sdimtemplate <typename T, typename U> struct is_hashable_data<std::pair<T, U> > 364234285Sdim : integral_constant<bool, (is_hashable_data<T>::value && 365234285Sdim is_hashable_data<U>::value && 366234285Sdim (sizeof(T) + sizeof(U)) == 367234285Sdim sizeof(std::pair<T, U>))> {}; 368234285Sdim 369234285Sdim/// \brief Helper to get the hashable data representation for a type. 370234285Sdim/// This variant is enabled when the type itself can be used. 371234285Sdimtemplate <typename T> 372234285Sdimtypename enable_if<is_hashable_data<T>, T>::type 373234285Sdimget_hashable_data(const T &value) { 374234285Sdim return value; 375234285Sdim} 376234285Sdim/// \brief Helper to get the hashable data representation for a type. 377234285Sdim/// This variant is enabled when we must first call hash_value and use the 378234285Sdim/// result as our data. 379234285Sdimtemplate <typename T> 380234285Sdimtypename enable_if_c<!is_hashable_data<T>::value, size_t>::type 381234285Sdimget_hashable_data(const T &value) { 382234285Sdim using ::llvm::hash_value; 383234285Sdim return hash_value(value); 384234285Sdim} 385234285Sdim 386234285Sdim/// \brief Helper to store data from a value into a buffer and advance the 387234285Sdim/// pointer into that buffer. 388234285Sdim/// 389234285Sdim/// This routine first checks whether there is enough space in the provided 390234285Sdim/// buffer, and if not immediately returns false. If there is space, it 391234285Sdim/// copies the underlying bytes of value into the buffer, advances the 392234285Sdim/// buffer_ptr past the copied bytes, and returns true. 393234285Sdimtemplate <typename T> 394234285Sdimbool store_and_advance(char *&buffer_ptr, char *buffer_end, const T& value, 395234285Sdim size_t offset = 0) { 396234285Sdim size_t store_size = sizeof(value) - offset; 397234285Sdim if (buffer_ptr + store_size > buffer_end) 398234285Sdim return false; 399234285Sdim const char *value_data = reinterpret_cast<const char *>(&value); 400234285Sdim memcpy(buffer_ptr, value_data + offset, store_size); 401234285Sdim buffer_ptr += store_size; 402234285Sdim return true; 403234285Sdim} 404234285Sdim 405234285Sdim/// \brief Implement the combining of integral values into a hash_code. 406234285Sdim/// 407234285Sdim/// This overload is selected when the value type of the iterator is 408234285Sdim/// integral. Rather than computing a hash_code for each object and then 409234285Sdim/// combining them, this (as an optimization) directly combines the integers. 410234285Sdimtemplate <typename InputIteratorT> 411234285Sdimhash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) { 412234285Sdim const size_t seed = get_execution_seed(); 413234285Sdim char buffer[64], *buffer_ptr = buffer; 414234285Sdim char *const buffer_end = buffer_ptr + array_lengthof(buffer); 415234285Sdim while (first != last && store_and_advance(buffer_ptr, buffer_end, 416234285Sdim get_hashable_data(*first))) 417234285Sdim ++first; 418234285Sdim if (first == last) 419234285Sdim return hash_short(buffer, buffer_ptr - buffer, seed); 420234285Sdim assert(buffer_ptr == buffer_end); 421234285Sdim 422234285Sdim hash_state state = state.create(buffer, seed); 423234285Sdim size_t length = 64; 424234285Sdim while (first != last) { 425234285Sdim // Fill up the buffer. We don't clear it, which re-mixes the last round 426234285Sdim // when only a partial 64-byte chunk is left. 427234285Sdim buffer_ptr = buffer; 428234285Sdim while (first != last && store_and_advance(buffer_ptr, buffer_end, 429234285Sdim get_hashable_data(*first))) 430234285Sdim ++first; 431234285Sdim 432234285Sdim // Rotate the buffer if we did a partial fill in order to simulate doing 433234285Sdim // a mix of the last 64-bytes. That is how the algorithm works when we 434234285Sdim // have a contiguous byte sequence, and we want to emulate that here. 435234285Sdim std::rotate(buffer, buffer_ptr, buffer_end); 436234285Sdim 437234285Sdim // Mix this chunk into the current state. 438234285Sdim state.mix(buffer); 439234285Sdim length += buffer_ptr - buffer; 440234285Sdim }; 441234285Sdim 442234285Sdim return state.finalize(length); 443234285Sdim} 444234285Sdim 445234285Sdim/// \brief Implement the combining of integral values into a hash_code. 446234285Sdim/// 447234285Sdim/// This overload is selected when the value type of the iterator is integral 448234285Sdim/// and when the input iterator is actually a pointer. Rather than computing 449234285Sdim/// a hash_code for each object and then combining them, this (as an 450234285Sdim/// optimization) directly combines the integers. Also, because the integers 451234285Sdim/// are stored in contiguous memory, this routine avoids copying each value 452234285Sdim/// and directly reads from the underlying memory. 453234285Sdimtemplate <typename ValueT> 454234285Sdimtypename enable_if<is_hashable_data<ValueT>, hash_code>::type 455234285Sdimhash_combine_range_impl(ValueT *first, ValueT *last) { 456234285Sdim const size_t seed = get_execution_seed(); 457234285Sdim const char *s_begin = reinterpret_cast<const char *>(first); 458234285Sdim const char *s_end = reinterpret_cast<const char *>(last); 459234285Sdim const size_t length = std::distance(s_begin, s_end); 460234285Sdim if (length <= 64) 461234285Sdim return hash_short(s_begin, length, seed); 462234285Sdim 463234285Sdim const char *s_aligned_end = s_begin + (length & ~63); 464234285Sdim hash_state state = state.create(s_begin, seed); 465234285Sdim s_begin += 64; 466234285Sdim while (s_begin != s_aligned_end) { 467234285Sdim state.mix(s_begin); 468234285Sdim s_begin += 64; 469234285Sdim } 470234285Sdim if (length & 63) 471234285Sdim state.mix(s_end - 64); 472234285Sdim 473234285Sdim return state.finalize(length); 474234285Sdim} 475234285Sdim 476234285Sdim} // namespace detail 477234285Sdim} // namespace hashing 478234285Sdim 479234285Sdim 480234285Sdim/// \brief Compute a hash_code for a sequence of values. 481234285Sdim/// 482234285Sdim/// This hashes a sequence of values. It produces the same hash_code as 483234285Sdim/// 'hash_combine(a, b, c, ...)', but can run over arbitrary sized sequences 484234285Sdim/// and is significantly faster given pointers and types which can be hashed as 485234285Sdim/// a sequence of bytes. 486234285Sdimtemplate <typename InputIteratorT> 487234285Sdimhash_code hash_combine_range(InputIteratorT first, InputIteratorT last) { 488234285Sdim return ::llvm::hashing::detail::hash_combine_range_impl(first, last); 489234285Sdim} 490234285Sdim 491234285Sdim 492234285Sdim// Implementation details for hash_combine. 493234285Sdimnamespace hashing { 494234285Sdimnamespace detail { 495234285Sdim 496234285Sdim/// \brief Helper class to manage the recursive combining of hash_combine 497234285Sdim/// arguments. 498234285Sdim/// 499234285Sdim/// This class exists to manage the state and various calls involved in the 500234285Sdim/// recursive combining of arguments used in hash_combine. It is particularly 501234285Sdim/// useful at minimizing the code in the recursive calls to ease the pain 502234285Sdim/// caused by a lack of variadic functions. 503234285Sdimstruct hash_combine_recursive_helper { 504234285Sdim char buffer[64]; 505234285Sdim hash_state state; 506234285Sdim const size_t seed; 507234285Sdim 508234285Sdimpublic: 509234285Sdim /// \brief Construct a recursive hash combining helper. 510234285Sdim /// 511234285Sdim /// This sets up the state for a recursive hash combine, including getting 512234285Sdim /// the seed and buffer setup. 513234285Sdim hash_combine_recursive_helper() 514234285Sdim : seed(get_execution_seed()) {} 515234285Sdim 516234285Sdim /// \brief Combine one chunk of data into the current in-flight hash. 517234285Sdim /// 518234285Sdim /// This merges one chunk of data into the hash. First it tries to buffer 519234285Sdim /// the data. If the buffer is full, it hashes the buffer into its 520234285Sdim /// hash_state, empties it, and then merges the new chunk in. This also 521234285Sdim /// handles cases where the data straddles the end of the buffer. 522234285Sdim template <typename T> 523234285Sdim char *combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data) { 524234285Sdim if (!store_and_advance(buffer_ptr, buffer_end, data)) { 525234285Sdim // Check for skew which prevents the buffer from being packed, and do 526234285Sdim // a partial store into the buffer to fill it. This is only a concern 527234285Sdim // with the variadic combine because that formation can have varying 528234285Sdim // argument types. 529234285Sdim size_t partial_store_size = buffer_end - buffer_ptr; 530234285Sdim memcpy(buffer_ptr, &data, partial_store_size); 531234285Sdim 532234285Sdim // If the store fails, our buffer is full and ready to hash. We have to 533234285Sdim // either initialize the hash state (on the first full buffer) or mix 534234285Sdim // this buffer into the existing hash state. Length tracks the *hashed* 535234285Sdim // length, not the buffered length. 536234285Sdim if (length == 0) { 537234285Sdim state = state.create(buffer, seed); 538234285Sdim length = 64; 539234285Sdim } else { 540234285Sdim // Mix this chunk into the current state and bump length up by 64. 541234285Sdim state.mix(buffer); 542234285Sdim length += 64; 543234285Sdim } 544234285Sdim // Reset the buffer_ptr to the head of the buffer for the next chunk of 545234285Sdim // data. 546234285Sdim buffer_ptr = buffer; 547234285Sdim 548234285Sdim // Try again to store into the buffer -- this cannot fail as we only 549234285Sdim // store types smaller than the buffer. 550234285Sdim if (!store_and_advance(buffer_ptr, buffer_end, data, 551234285Sdim partial_store_size)) 552234285Sdim abort(); 553234285Sdim } 554234285Sdim return buffer_ptr; 555234285Sdim } 556234285Sdim 557234285Sdim#if defined(__has_feature) && __has_feature(__cxx_variadic_templates__) 558234285Sdim 559234285Sdim /// \brief Recursive, variadic combining method. 560234285Sdim /// 561234285Sdim /// This function recurses through each argument, combining that argument 562234285Sdim /// into a single hash. 563234285Sdim template <typename T, typename ...Ts> 564234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 565234285Sdim const T &arg, const Ts &...args) { 566234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg)); 567234285Sdim 568234285Sdim // Recurse to the next argument. 569234285Sdim return combine(length, buffer_ptr, buffer_end, args...); 570234285Sdim } 571234285Sdim 572234285Sdim#else 573234285Sdim // Manually expanded recursive combining methods. See variadic above for 574234285Sdim // documentation. 575234285Sdim 576234285Sdim template <typename T1, typename T2, typename T3, typename T4, typename T5, 577234285Sdim typename T6> 578234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 579234285Sdim const T1 &arg1, const T2 &arg2, const T3 &arg3, 580234285Sdim const T4 &arg4, const T5 &arg5, const T6 &arg6) { 581234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); 582234285Sdim return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5, arg6); 583234285Sdim } 584234285Sdim template <typename T1, typename T2, typename T3, typename T4, typename T5> 585234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 586234285Sdim const T1 &arg1, const T2 &arg2, const T3 &arg3, 587234285Sdim const T4 &arg4, const T5 &arg5) { 588234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); 589234285Sdim return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5); 590234285Sdim } 591234285Sdim template <typename T1, typename T2, typename T3, typename T4> 592234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 593234285Sdim const T1 &arg1, const T2 &arg2, const T3 &arg3, 594234285Sdim const T4 &arg4) { 595234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); 596234285Sdim return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4); 597234285Sdim } 598234285Sdim template <typename T1, typename T2, typename T3> 599234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 600234285Sdim const T1 &arg1, const T2 &arg2, const T3 &arg3) { 601234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); 602234285Sdim return combine(length, buffer_ptr, buffer_end, arg2, arg3); 603234285Sdim } 604234285Sdim template <typename T1, typename T2> 605234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 606234285Sdim const T1 &arg1, const T2 &arg2) { 607234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); 608234285Sdim return combine(length, buffer_ptr, buffer_end, arg2); 609234285Sdim } 610234285Sdim template <typename T1> 611234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, 612234285Sdim const T1 &arg1) { 613234285Sdim buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); 614234285Sdim return combine(length, buffer_ptr, buffer_end); 615234285Sdim } 616234285Sdim 617234285Sdim#endif 618234285Sdim 619234285Sdim /// \brief Base case for recursive, variadic combining. 620234285Sdim /// 621234285Sdim /// The base case when combining arguments recursively is reached when all 622234285Sdim /// arguments have been handled. It flushes the remaining buffer and 623234285Sdim /// constructs a hash_code. 624234285Sdim hash_code combine(size_t length, char *buffer_ptr, char *buffer_end) { 625234285Sdim // Check whether the entire set of values fit in the buffer. If so, we'll 626234285Sdim // use the optimized short hashing routine and skip state entirely. 627234285Sdim if (length == 0) 628234285Sdim return hash_short(buffer, buffer_ptr - buffer, seed); 629234285Sdim 630234285Sdim // Mix the final buffer, rotating it if we did a partial fill in order to 631234285Sdim // simulate doing a mix of the last 64-bytes. That is how the algorithm 632234285Sdim // works when we have a contiguous byte sequence, and we want to emulate 633234285Sdim // that here. 634234285Sdim std::rotate(buffer, buffer_ptr, buffer_end); 635234285Sdim 636234285Sdim // Mix this chunk into the current state. 637234285Sdim state.mix(buffer); 638234285Sdim length += buffer_ptr - buffer; 639234285Sdim 640234285Sdim return state.finalize(length); 641234285Sdim } 642234285Sdim}; 643234285Sdim 644234285Sdim} // namespace detail 645234285Sdim} // namespace hashing 646234285Sdim 647234285Sdim 648234285Sdim#if __has_feature(__cxx_variadic_templates__) 649234285Sdim 650234285Sdim/// \brief Combine values into a single hash_code. 651234285Sdim/// 652234285Sdim/// This routine accepts a varying number of arguments of any type. It will 653234285Sdim/// attempt to combine them into a single hash_code. For user-defined types it 654234285Sdim/// attempts to call a \see hash_value overload (via ADL) for the type. For 655234285Sdim/// integer and pointer types it directly combines their data into the 656234285Sdim/// resulting hash_code. 657234285Sdim/// 658234285Sdim/// The result is suitable for returning from a user's hash_value 659234285Sdim/// *implementation* for their user-defined type. Consumers of a type should 660234285Sdim/// *not* call this routine, they should instead call 'hash_value'. 661234285Sdimtemplate <typename ...Ts> hash_code hash_combine(const Ts &...args) { 662234285Sdim // Recursively hash each argument using a helper class. 663234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 664234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, args...); 665234285Sdim} 666234285Sdim 667234285Sdim#else 668234285Sdim 669234285Sdim// What follows are manually exploded overloads for each argument width. See 670234285Sdim// the above variadic definition for documentation and specification. 671234285Sdim 672234285Sdimtemplate <typename T1, typename T2, typename T3, typename T4, typename T5, 673234285Sdim typename T6> 674234285Sdimhash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, 675234285Sdim const T4 &arg4, const T5 &arg5, const T6 &arg6) { 676234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 677234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, 678234285Sdim arg1, arg2, arg3, arg4, arg5, arg6); 679234285Sdim} 680234285Sdimtemplate <typename T1, typename T2, typename T3, typename T4, typename T5> 681234285Sdimhash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, 682234285Sdim const T4 &arg4, const T5 &arg5) { 683234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 684234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, 685234285Sdim arg1, arg2, arg3, arg4, arg5); 686234285Sdim} 687234285Sdimtemplate <typename T1, typename T2, typename T3, typename T4> 688234285Sdimhash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, 689234285Sdim const T4 &arg4) { 690234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 691234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, 692234285Sdim arg1, arg2, arg3, arg4); 693234285Sdim} 694234285Sdimtemplate <typename T1, typename T2, typename T3> 695234285Sdimhash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3) { 696234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 697234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2, arg3); 698234285Sdim} 699234285Sdimtemplate <typename T1, typename T2> 700234285Sdimhash_code hash_combine(const T1 &arg1, const T2 &arg2) { 701234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 702234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2); 703234285Sdim} 704234285Sdimtemplate <typename T1> 705234285Sdimhash_code hash_combine(const T1 &arg1) { 706234285Sdim ::llvm::hashing::detail::hash_combine_recursive_helper helper; 707234285Sdim return helper.combine(0, helper.buffer, helper.buffer + 64, arg1); 708234285Sdim} 709234285Sdim 710234285Sdim#endif 711234285Sdim 712234285Sdim 713243830Sdim// Implementation details for implementations of hash_value overloads provided 714234285Sdim// here. 715234285Sdimnamespace hashing { 716234285Sdimnamespace detail { 717234285Sdim 718234285Sdim/// \brief Helper to hash the value of a single integer. 719234285Sdim/// 720234285Sdim/// Overloads for smaller integer types are not provided to ensure consistent 721234285Sdim/// behavior in the presence of integral promotions. Essentially, 722234285Sdim/// "hash_value('4')" and "hash_value('0' + 4)" should be the same. 723234285Sdiminline hash_code hash_integer_value(uint64_t value) { 724234285Sdim // Similar to hash_4to8_bytes but using a seed instead of length. 725234285Sdim const uint64_t seed = get_execution_seed(); 726234285Sdim const char *s = reinterpret_cast<const char *>(&value); 727234285Sdim const uint64_t a = fetch32(s); 728234285Sdim return hash_16_bytes(seed + (a << 3), fetch32(s + 4)); 729234285Sdim} 730234285Sdim 731234285Sdim} // namespace detail 732234285Sdim} // namespace hashing 733234285Sdim 734234285Sdim// Declared and documented above, but defined here so that any of the hashing 735234285Sdim// infrastructure is available. 736234285Sdimtemplate <typename T> 737234285Sdimtypename enable_if<is_integral_or_enum<T>, hash_code>::type 738234285Sdimhash_value(T value) { 739234285Sdim return ::llvm::hashing::detail::hash_integer_value(value); 740234285Sdim} 741234285Sdim 742234285Sdim// Declared and documented above, but defined here so that any of the hashing 743234285Sdim// infrastructure is available. 744234285Sdimtemplate <typename T> hash_code hash_value(const T *ptr) { 745234285Sdim return ::llvm::hashing::detail::hash_integer_value( 746234285Sdim reinterpret_cast<uintptr_t>(ptr)); 747234285Sdim} 748234285Sdim 749234285Sdim// Declared and documented above, but defined here so that any of the hashing 750234285Sdim// infrastructure is available. 751234285Sdimtemplate <typename T, typename U> 752234285Sdimhash_code hash_value(const std::pair<T, U> &arg) { 753234285Sdim return hash_combine(arg.first, arg.second); 754234285Sdim} 755234285Sdim 756234285Sdim// Declared and documented above, but defined here so that any of the hashing 757234285Sdim// infrastructure is available. 758234285Sdimtemplate <typename T> 759234285Sdimhash_code hash_value(const std::basic_string<T> &arg) { 760234285Sdim return hash_combine_range(arg.begin(), arg.end()); 761234285Sdim} 762234285Sdim 763234285Sdim} // namespace llvm 764234285Sdim 765234285Sdim#endif 766