X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FHashing.h;h=81a511786a63aac1d743ca6eb1fe4ebae4255b36;hb=005874056e536324cba9fa253d7e14a6f9dcf4fa;hp=7fbe5bb0ca275c901aaee8f059d7028e871f3929;hpb=1c1448984d43f1f02c0235d35ebe8460c9b57afd;p=oota-llvm.git diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h index 7fbe5bb0ca2..81a511786a6 100644 --- a/include/llvm/ADT/Hashing.h +++ b/include/llvm/ADT/Hashing.h @@ -47,6 +47,8 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/Host.h" +#include "llvm/Support/SwapByteOrder.h" #include "llvm/Support/type_traits.h" #include #include @@ -111,7 +113,7 @@ public: /// differing argument types even if they would implicit promote to a common /// type without changing the value. template -typename enable_if, hash_code>::type hash_value(T value); +typename enable_if, hash_code>::type hash_value(T value); /// \brief Compute a hash_code for a pointer's address. /// @@ -122,6 +124,10 @@ template hash_code hash_value(const T *ptr); template hash_code hash_value(const std::pair &arg); +/// \brief Compute a hash_code for a standard string. +template +hash_code hash_value(const std::basic_string &arg); + /// \brief Override the execution seed with a fixed value. /// @@ -149,12 +155,16 @@ namespace detail { inline uint64_t fetch64(const char *p) { uint64_t result; memcpy(&result, p, sizeof(result)); + if (sys::isBigEndianHost()) + return sys::SwapByteOrder(result); return result; } inline uint32_t fetch32(const char *p) { uint32_t result; memcpy(&result, p, sizeof(result)); + if (sys::isBigEndianHost()) + return sys::SwapByteOrder(result); return result; } @@ -167,7 +177,7 @@ static const uint64_t k3 = 0xc949d7c7509e6557ULL; /// \brief Bitwise right rotate. /// Normally this will compile to a single instruction, especially if the /// shift is a manifest constant. -inline uint64_t rotate(uint64_t val, unsigned shift) { +inline uint64_t rotate(uint64_t val, size_t shift) { // Avoid shifting by 64: doing so yields an undefined result. return shift == 0 ? val : ((val >> shift) | (val << (64 - shift))); } @@ -202,9 +212,9 @@ inline uint64_t hash_4to8_bytes(const char *s, size_t len, uint64_t seed) { } inline uint64_t hash_9to16_bytes(const char *s, size_t len, uint64_t seed) { - uint64_t a = fetch64(s); - uint64_t b = fetch64(s + len - 8); - return hash_16_bytes(seed ^ a, rotate(b + len, len)) ^ b; + uint64_t a = fetch64(s); + uint64_t b = fetch64(s + len - 8); + return hash_16_bytes(seed ^ a, rotate(b + len, len)) ^ b; } inline uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed) { @@ -267,9 +277,8 @@ struct hash_state { static hash_state create(const char *s, uint64_t seed) { hash_state state = { 0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49), - seed * k1, shift_mix(seed), hash_16_bytes(state.h4, state.h5), - seed - }; + seed * k1, shift_mix(seed), 0, seed }; + state.h6 = hash_16_bytes(state.h4, state.h5); state.mix(s); return state; } @@ -329,7 +338,7 @@ inline size_t get_execution_seed() { // called, return that instead of the per-execution seed. const uint64_t seed_prime = 0xff51afd7ed558ccdULL; static size_t seed = fixed_seed_override ? fixed_seed_override - : static_cast(seed_prime); + : (size_t)seed_prime; return seed; } @@ -340,14 +349,15 @@ inline size_t get_execution_seed() { /// reading the underlying data. It is false if values of this type must /// first be passed to hash_value, and the resulting hash_codes combined. // -// FIXME: We want to replace is_integral and is_pointer here with a predicate -// which asserts that comparing the underlying storage of two values of the -// type for equality is equivalent to comparing the two values for equality. -// For all the platforms we care about, this holds for integers and pointers, -// but there are platforms where it doesn't and we would like to support -// user-defined types which happen to satisfy this property. +// FIXME: We want to replace is_integral_or_enum and is_pointer here with +// a predicate which asserts that comparing the underlying storage of two +// values of the type for equality is equivalent to comparing the two values +// for equality. For all the platforms we care about, this holds for integers +// and pointers, but there are platforms where it doesn't and we would like to +// support user-defined types which happen to satisfy this property. template struct is_hashable_data - : integral_constant::value || is_pointer::value) && + : integral_constant::value || + is_pointer::value) && 64 % sizeof(T) == 0)> {}; // Special case std::pair to detect when both types are viable and when there @@ -410,8 +420,6 @@ hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) { while (first != last && store_and_advance(buffer_ptr, buffer_end, get_hashable_data(*first))) ++first; -/// \brief Metafunction that determines whether the given type is an integral -/// type. if (first == last) return hash_short(buffer, buffer_ptr - buffer, seed); assert(buffer_ptr == buffer_end); @@ -449,7 +457,7 @@ hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) { /// and directly reads from the underlying memory. template typename enable_if, hash_code>::type -hash_combine_range_impl(const ValueT *first, const ValueT *last) { +hash_combine_range_impl(ValueT *first, ValueT *last) { const size_t seed = get_execution_seed(); const char *s_begin = reinterpret_cast(first); const char *s_end = reinterpret_cast(last); @@ -725,7 +733,8 @@ inline hash_code hash_integer_value(uint64_t value) { // Declared and documented above, but defined here so that any of the hashing // infrastructure is available. template -typename enable_if, hash_code>::type hash_value(T value) { +typename enable_if, hash_code>::type +hash_value(T value) { return ::llvm::hashing::detail::hash_integer_value(value); } @@ -743,6 +752,13 @@ hash_code hash_value(const std::pair &arg) { return hash_combine(arg.first, arg.second); } +// Declared and documented above, but defined here so that any of the hashing +// infrastructure is available. +template +hash_code hash_value(const std::basic_string &arg) { + return hash_combine_range(arg.begin(), arg.end()); +} + } // namespace llvm #endif