// Copyright 2014 the V8 project 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 V8_BASE_FUNCTIONAL_H_ #define V8_BASE_FUNCTIONAL_H_ #include <stddef.h> #include <stdint.h> #include <cstddef> #include <cstring> #include <functional> #include <utility> #include "src/base/base-export.h" #include "src/base/macros.h" namespace v8 { namespace base { // base::hash is an implementation of the hash function object specified by // C++11. It was designed to be compatible with std::hash (in C++11) and // boost:hash (which in turn is based on the hash function object specified by // the Draft Technical Report on C++ Library Extensions (TR1)). // // base::hash is implemented by calling the hash_value function. The namespace // isn't specified so that it can detect overloads via argument dependent // lookup. So if there is a free function hash_value in the same namespace as a // custom type, it will get called. // // If users are asked to implement a hash function for their own types with no // guidance, they generally write bad hash functions. Instead, we provide a // simple function base::hash_combine to pass hash-relevant member variables // into, in order to define a decent hash function. base::hash_combine is // declared as: // // template<typename T, typename... Ts> // size_t hash_combine(const T& v, const Ts& ...vs); // // Consider the following example: // // namespace v8 { // namespace bar { // struct Point { int x; int y; }; // size_t hash_value(Point const& p) { // return base::hash_combine(p.x, p.y); // } // } // // namespace foo { // void DoSomeWork(bar::Point const& p) { // base::hash<bar::Point> h; // ... // size_t hash_code = h(p); // calls bar::hash_value(Point const&) // ... // } // } // } // // Based on the "Hashing User-Defined Types in C++1y" proposal from Jeffrey // Yasskin and Chandler Carruth, see // http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html. template <typename> struct hash; V8_INLINE size_t hash_combine() { return 0u; } V8_INLINE size_t hash_combine(size_t seed) { return seed; } V8_BASE_EXPORT size_t hash_combine(size_t seed, size_t value); template <typename T, typename... Ts> V8_INLINE size_t hash_combine(T const& v, Ts const&... vs) { return hash_combine(hash_combine(vs...), hash<T>()(v)); } template <typename Iterator> V8_INLINE size_t hash_range(Iterator first, Iterator last) { size_t seed = 0; for (; first != last; ++first) { seed = hash_combine(seed, *first); } return seed; } #define V8_BASE_HASH_VALUE_TRIVIAL(type) \ V8_INLINE size_t hash_value(type v) { return static_cast<size_t>(v); } V8_BASE_HASH_VALUE_TRIVIAL(bool) V8_BASE_HASH_VALUE_TRIVIAL(unsigned char) V8_BASE_HASH_VALUE_TRIVIAL(unsigned short) // NOLINT(runtime/int) #undef V8_BASE_HASH_VALUE_TRIVIAL V8_BASE_EXPORT size_t hash_value(unsigned int); V8_BASE_EXPORT size_t hash_value(unsigned long); // NOLINT(runtime/int) V8_BASE_EXPORT size_t hash_value(unsigned long long); // NOLINT(runtime/int) #define V8_BASE_HASH_VALUE_SIGNED(type) \ V8_INLINE size_t hash_value(signed type v) { \ return hash_value(bit_cast<unsigned type>(v)); \ } V8_BASE_HASH_VALUE_SIGNED(char) V8_BASE_HASH_VALUE_SIGNED(short) // NOLINT(runtime/int) V8_BASE_HASH_VALUE_SIGNED(int) // NOLINT(runtime/int) V8_BASE_HASH_VALUE_SIGNED(long) // NOLINT(runtime/int) V8_BASE_HASH_VALUE_SIGNED(long long) // NOLINT(runtime/int) #undef V8_BASE_HASH_VALUE_SIGNED V8_INLINE size_t hash_value(float v) { // 0 and -0 both hash to zero. return v != 0.0f ? hash_value(bit_cast<uint32_t>(v)) : 0; } V8_INLINE size_t hash_value(double v) { // 0 and -0 both hash to zero. return v != 0.0 ? hash_value(bit_cast<uint64_t>(v)) : 0; } template <typename T, size_t N> V8_INLINE size_t hash_value(const T (&v)[N]) { return hash_range(v, v + N); } template <typename T, size_t N> V8_INLINE size_t hash_value(T (&v)[N]) { return hash_range(v, v + N); } template <typename T> V8_INLINE size_t hash_value(T* const& v) { return hash_value(bit_cast<uintptr_t>(v)); } template <typename T1, typename T2> V8_INLINE size_t hash_value(std::pair<T1, T2> const& v) { return hash_combine(v.first, v.second); } template <typename T> struct hash { V8_INLINE size_t operator()(T const& v) const { return hash_value(v); } }; #define V8_BASE_HASH_SPECIALIZE(type) \ template <> \ struct hash<type> { \ V8_INLINE size_t operator()(type const v) const { \ return ::v8::base::hash_value(v); \ } \ }; V8_BASE_HASH_SPECIALIZE(bool) V8_BASE_HASH_SPECIALIZE(signed char) V8_BASE_HASH_SPECIALIZE(unsigned char) V8_BASE_HASH_SPECIALIZE(short) // NOLINT(runtime/int) V8_BASE_HASH_SPECIALIZE(unsigned short) // NOLINT(runtime/int) V8_BASE_HASH_SPECIALIZE(int) V8_BASE_HASH_SPECIALIZE(unsigned int) V8_BASE_HASH_SPECIALIZE(long) // NOLINT(runtime/int) V8_BASE_HASH_SPECIALIZE(unsigned long) // NOLINT(runtime/int) V8_BASE_HASH_SPECIALIZE(long long) // NOLINT(runtime/int) V8_BASE_HASH_SPECIALIZE(unsigned long long) // NOLINT(runtime/int) V8_BASE_HASH_SPECIALIZE(float) V8_BASE_HASH_SPECIALIZE(double) #undef V8_BASE_HASH_SPECIALIZE template <typename T> struct hash<T*> { V8_INLINE size_t operator()(T* const v) const { return ::v8::base::hash_value(v); } }; // base::bit_equal_to is a function object class for bitwise equality // comparison, similar to std::equal_to, except that the comparison is performed // on the bit representation of the operands. // // base::bit_hash is a function object class for bitwise hashing, similar to // base::hash. It can be used together with base::bit_equal_to to implement a // hash data structure based on the bitwise representation of types. template <typename T> struct bit_equal_to {}; template <typename T> struct bit_hash {}; #define V8_BASE_BIT_SPECIALIZE_TRIVIAL(type) \ template <> \ struct bit_equal_to<type> : public std::equal_to<type> {}; \ template <> \ struct bit_hash<type> : public hash<type> {}; V8_BASE_BIT_SPECIALIZE_TRIVIAL(signed char) V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned char) V8_BASE_BIT_SPECIALIZE_TRIVIAL(short) // NOLINT(runtime/int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned short) // NOLINT(runtime/int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(long) // NOLINT(runtime/int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned long) // NOLINT(runtime/int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(long long) // NOLINT(runtime/int) V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned long long) // NOLINT(runtime/int) #undef V8_BASE_BIT_SPECIALIZE_TRIVIAL #define V8_BASE_BIT_SPECIALIZE_BIT_CAST(type, btype) \ template <> \ struct bit_equal_to<type> { \ V8_INLINE bool operator()(type lhs, type rhs) const { \ return bit_cast<btype>(lhs) == bit_cast<btype>(rhs); \ } \ }; \ template <> \ struct bit_hash<type> { \ V8_INLINE size_t operator()(type v) const { \ hash<btype> h; \ return h(bit_cast<btype>(v)); \ } \ }; V8_BASE_BIT_SPECIALIZE_BIT_CAST(float, uint32_t) V8_BASE_BIT_SPECIALIZE_BIT_CAST(double, uint64_t) #undef V8_BASE_BIT_SPECIALIZE_BIT_CAST } // namespace base } // namespace v8 #endif // V8_BASE_FUNCTIONAL_H_