X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FHashing.h;h=cda31a261df29248b01d6f65f8ab22acc7954b33;hb=fbaf206f470b5a6a54811547641ee41368a2cccd;hp=7bb540e8331aa109b77eb96cc53a90b1c5344526;hpb=a2a9b9e7752f1eeb8c158112fc940ff67b04d7a1;p=oota-llvm.git diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h index 7bb540e8331..cda31a261df 100644 --- a/include/llvm/ADT/Hashing.h +++ b/include/llvm/ADT/Hashing.h @@ -76,10 +76,6 @@ namespace llvm { /// using llvm::hash_value; /// llvm::hash_code code = hash_value(x); /// \endcode -/// -/// Also note that there are two numerical values which are reserved, and the -/// implementation ensures will never be produced for real hash_codes. These -/// can be used as sentinels within hashing data structures. class hash_code { size_t value; @@ -113,7 +109,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. /// @@ -124,6 +120,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. /// @@ -334,7 +334,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; } @@ -345,14 +345,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 @@ -408,15 +409,12 @@ bool store_and_advance(char *&buffer_ptr, char *buffer_end, const T& value, /// combining them, this (as an optimization) directly combines the integers. template hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) { - typedef typename std::iterator_traits::value_type ValueT; const size_t seed = get_execution_seed(); char buffer[64], *buffer_ptr = buffer; char *const buffer_end = buffer_ptr + array_lengthof(buffer); 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); @@ -454,7 +452,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); @@ -502,13 +500,10 @@ namespace detail { /// recursive combining of arguments used in hash_combine. It is particularly /// useful at minimizing the code in the recursive calls to ease the pain /// caused by a lack of variadic functions. -class hash_combine_recursive_helper { - const size_t seed; +struct hash_combine_recursive_helper { char buffer[64]; - char *const buffer_end; - char *buffer_ptr; - size_t length; hash_state state; + const size_t seed; public: /// \brief Construct a recursive hash combining helper. @@ -516,10 +511,7 @@ public: /// This sets up the state for a recursive hash combine, including getting /// the seed and buffer setup. hash_combine_recursive_helper() - : seed(get_execution_seed()), - buffer_end(buffer + array_lengthof(buffer)), - buffer_ptr(buffer), - length(0) {} + : seed(get_execution_seed()) {} /// \brief Combine one chunk of data into the current in-flight hash. /// @@ -527,7 +519,8 @@ public: /// the data. If the buffer is full, it hashes the buffer into its /// hash_state, empties it, and then merges the new chunk in. This also /// handles cases where the data straddles the end of the buffer. - template void combine_data(T data) { + template + char *combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data) { if (!store_and_advance(buffer_ptr, buffer_end, data)) { // Check for skew which prevents the buffer from being packed, and do // a partial store into the buffer to fill it. This is only a concern @@ -558,6 +551,7 @@ public: partial_store_size)) abort(); } + return buffer_ptr; } #if defined(__has_feature) && __has_feature(__cxx_variadic_templates__) @@ -567,11 +561,12 @@ public: /// This function recurses through each argument, combining that argument /// into a single hash. template - hash_code combine(const T &arg, const Ts &...args) { - combine_data( get_hashable_data(arg)); + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T &arg, const Ts &...args) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg)); // Recurse to the next argument. - return combine(args...); + return combine(length, buffer_ptr, buffer_end, args...); } #else @@ -580,37 +575,43 @@ public: template - hash_code combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3, const T4 &arg4, const T5 &arg5, const T6 &arg6) { - combine_data(get_hashable_data(arg1)); - return combine(arg2, arg3, arg4, arg5, arg6); + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5, arg6); } template - hash_code combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3, const T4 &arg4, const T5 &arg5) { - combine_data(get_hashable_data(arg1)); - return combine(arg2, arg3, arg4, arg5); + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5); } template - hash_code combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3, const T4 &arg4) { - combine_data(get_hashable_data(arg1)); - return combine(arg2, arg3, arg4); + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4); } template - hash_code combine(const T1 &arg1, const T2 &arg2, const T3 &arg3) { - combine_data(get_hashable_data(arg1)); - return combine(arg2, arg3); + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3); } template - hash_code combine(const T1 &arg1, const T2 &arg2) { - combine_data(get_hashable_data(arg1)); - return combine(arg2); + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2); } template - hash_code combine(const T1 &arg1) { - combine_data(get_hashable_data(arg1)); - return combine(); + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end); } #endif @@ -620,7 +621,7 @@ public: /// The base case when combining arguments recursively is reached when all /// arguments have been handled. It flushes the remaining buffer and /// constructs a hash_code. - hash_code combine() { + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end) { // Check whether the entire set of values fit in the buffer. If so, we'll // use the optimized short hashing routine and skip state entirely. if (length == 0) @@ -660,7 +661,7 @@ public: template hash_code hash_combine(const Ts &...args) { // Recursively hash each argument using a helper class. ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(args...); + return helper.combine(0, helper.buffer, helper.buffer + 64, args...); } #else @@ -671,42 +672,45 @@ template hash_code hash_combine(const Ts &...args) { template hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4, const T5 &arg5, const T6 &arg6) { + const T4 &arg4, const T5 &arg5, const T6 &arg6) { ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(arg1, arg2, arg3, arg4, arg5, arg6); + return helper.combine(0, helper.buffer, helper.buffer + 64, + arg1, arg2, arg3, arg4, arg5, arg6); } template hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4, const T5 &arg5) { + const T4 &arg4, const T5 &arg5) { ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(arg1, arg2, arg3, arg4, arg5); + return helper.combine(0, helper.buffer, helper.buffer + 64, + arg1, arg2, arg3, arg4, arg5); } template hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4) { + const T4 &arg4) { ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(arg1, arg2, arg3, arg4); + return helper.combine(0, helper.buffer, helper.buffer + 64, + arg1, arg2, arg3, arg4); } template hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3) { ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(arg1, arg2, arg3); + return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2, arg3); } template hash_code hash_combine(const T1 &arg1, const T2 &arg2) { ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(arg1, arg2); + return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2); } template hash_code hash_combine(const T1 &arg1) { ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(arg1); + return helper.combine(0, helper.buffer, helper.buffer + 64, arg1); } #endif -// Implementation details for implementatinos of hash_value overloads provided +// Implementation details for implementations of hash_value overloads provided // here. namespace hashing { namespace detail { @@ -730,7 +734,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); } @@ -748,6 +753,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