1 // Copyright 2014 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_BASE_FUNCTIONAL_H_ 6 #define V8_BASE_FUNCTIONAL_H_ 7 8 #include <stddef.h> 9 #include <stdint.h> 10 11 #include <cstddef> 12 #include <cstring> 13 #include <functional> 14 #include <utility> 15 16 #include "src/base/base-export.h" 17 #include "src/base/macros.h" 18 19 namespace v8 { 20 namespace base { 21 22 // base::hash is an implementation of the hash function object specified by 23 // C++11. It was designed to be compatible with std::hash (in C++11) and 24 // boost:hash (which in turn is based on the hash function object specified by 25 // the Draft Technical Report on C++ Library Extensions (TR1)). 26 // 27 // base::hash is implemented by calling the hash_value function. The namespace 28 // isn't specified so that it can detect overloads via argument dependant 29 // lookup. So if there is a free function hash_value in the same namespace as a 30 // custom type, it will get called. 31 // 32 // If users are asked to implement a hash function for their own types with no 33 // guidance, they generally write bad hash functions. Instead, we provide a 34 // simple function base::hash_combine to pass hash-relevant member variables 35 // into, in order to define a decent hash function. base::hash_combine is 36 // declared as: 37 // 38 // template<typename T, typename... Ts> 39 // size_t hash_combine(const T& v, const Ts& ...vs); 40 // 41 // Consider the following example: 42 // 43 // namespace v8 { 44 // namespace bar { 45 // struct Point { int x; int y; }; 46 // size_t hash_value(Point const& p) { 47 // return base::hash_combine(p.x, p.y); 48 // } 49 // } 50 // 51 // namespace foo { 52 // void DoSomeWork(bar::Point const& p) { 53 // base::hash<bar::Point> h; 54 // ... 55 // size_t hash_code = h(p); // calls bar::hash_value(Point const&) 56 // ... 57 // } 58 // } 59 // } 60 // 61 // Based on the "Hashing User-Defined Types in C++1y" proposal from Jeffrey 62 // Yasskin and Chandler Carruth, see 63 // http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html. 64 65 template <typename> 66 struct hash; 67 68 69 V8_INLINE size_t hash_combine() { return 0u; } 70 V8_INLINE size_t hash_combine(size_t seed) { return seed; } 71 V8_BASE_EXPORT size_t hash_combine(size_t seed, size_t value); 72 template <typename T, typename... Ts> 73 V8_INLINE size_t hash_combine(T const& v, Ts const&... vs) { 74 return hash_combine(hash_combine(vs...), hash<T>()(v)); 75 } 76 77 78 template <typename Iterator> 79 V8_INLINE size_t hash_range(Iterator first, Iterator last) { 80 size_t seed = 0; 81 for (; first != last; ++first) { 82 seed = hash_combine(seed, *first); 83 } 84 return seed; 85 } 86 87 88 #define V8_BASE_HASH_VALUE_TRIVIAL(type) \ 89 V8_INLINE size_t hash_value(type v) { return static_cast<size_t>(v); } 90 V8_BASE_HASH_VALUE_TRIVIAL(bool) 91 V8_BASE_HASH_VALUE_TRIVIAL(unsigned char) 92 V8_BASE_HASH_VALUE_TRIVIAL(unsigned short) // NOLINT(runtime/int) 93 #undef V8_BASE_HASH_VALUE_TRIVIAL 94 95 V8_BASE_EXPORT size_t hash_value(unsigned int); 96 V8_BASE_EXPORT size_t hash_value(unsigned long); // NOLINT(runtime/int) 97 V8_BASE_EXPORT size_t hash_value(unsigned long long); // NOLINT(runtime/int) 98 99 #define V8_BASE_HASH_VALUE_SIGNED(type) \ 100 V8_INLINE size_t hash_value(signed type v) { \ 101 return hash_value(bit_cast<unsigned type>(v)); \ 102 } 103 V8_BASE_HASH_VALUE_SIGNED(char) 104 V8_BASE_HASH_VALUE_SIGNED(short) // NOLINT(runtime/int) 105 V8_BASE_HASH_VALUE_SIGNED(int) // NOLINT(runtime/int) 106 V8_BASE_HASH_VALUE_SIGNED(long) // NOLINT(runtime/int) 107 V8_BASE_HASH_VALUE_SIGNED(long long) // NOLINT(runtime/int) 108 #undef V8_BASE_HASH_VALUE_SIGNED 109 110 V8_INLINE size_t hash_value(float v) { 111 // 0 and -0 both hash to zero. 112 return v != 0.0f ? hash_value(bit_cast<uint32_t>(v)) : 0; 113 } 114 115 V8_INLINE size_t hash_value(double v) { 116 // 0 and -0 both hash to zero. 117 return v != 0.0 ? hash_value(bit_cast<uint64_t>(v)) : 0; 118 } 119 120 template <typename T, size_t N> 121 V8_INLINE size_t hash_value(const T (&v)[N]) { 122 return hash_range(v, v + N); 123 } 124 125 template <typename T, size_t N> 126 V8_INLINE size_t hash_value(T (&v)[N]) { 127 return hash_range(v, v + N); 128 } 129 130 template <typename T> 131 V8_INLINE size_t hash_value(T* const& v) { 132 return hash_value(bit_cast<uintptr_t>(v)); 133 } 134 135 template <typename T1, typename T2> 136 V8_INLINE size_t hash_value(std::pair<T1, T2> const& v) { 137 return hash_combine(v.first, v.second); 138 } 139 140 141 template <typename T> 142 struct hash : public std::unary_function<T, size_t> { 143 V8_INLINE size_t operator()(T const& v) const { return hash_value(v); } 144 }; 145 146 #define V8_BASE_HASH_SPECIALIZE(type) \ 147 template <> \ 148 struct hash<type> : public std::unary_function<type, size_t> { \ 149 V8_INLINE size_t operator()(type const v) const { \ 150 return ::v8::base::hash_value(v); \ 151 } \ 152 }; 153 V8_BASE_HASH_SPECIALIZE(bool) 154 V8_BASE_HASH_SPECIALIZE(signed char) 155 V8_BASE_HASH_SPECIALIZE(unsigned char) 156 V8_BASE_HASH_SPECIALIZE(short) // NOLINT(runtime/int) 157 V8_BASE_HASH_SPECIALIZE(unsigned short) // NOLINT(runtime/int) 158 V8_BASE_HASH_SPECIALIZE(int) 159 V8_BASE_HASH_SPECIALIZE(unsigned int) 160 V8_BASE_HASH_SPECIALIZE(long) // NOLINT(runtime/int) 161 V8_BASE_HASH_SPECIALIZE(unsigned long) // NOLINT(runtime/int) 162 V8_BASE_HASH_SPECIALIZE(long long) // NOLINT(runtime/int) 163 V8_BASE_HASH_SPECIALIZE(unsigned long long) // NOLINT(runtime/int) 164 V8_BASE_HASH_SPECIALIZE(float) 165 V8_BASE_HASH_SPECIALIZE(double) 166 #undef V8_BASE_HASH_SPECIALIZE 167 168 template <typename T> 169 struct hash<T*> : public std::unary_function<T*, size_t> { 170 V8_INLINE size_t operator()(T* const v) const { 171 return ::v8::base::hash_value(v); 172 } 173 }; 174 175 176 // base::bit_equal_to is a function object class for bitwise equality 177 // comparison, similar to std::equal_to, except that the comparison is performed 178 // on the bit representation of the operands. 179 // 180 // base::bit_hash is a function object class for bitwise hashing, similar to 181 // base::hash. It can be used together with base::bit_equal_to to implement a 182 // hash data structure based on the bitwise representation of types. 183 184 template <typename T> 185 struct bit_equal_to : public std::binary_function<T, T, bool> {}; 186 187 template <typename T> 188 struct bit_hash : public std::unary_function<T, size_t> {}; 189 190 #define V8_BASE_BIT_SPECIALIZE_TRIVIAL(type) \ 191 template <> \ 192 struct bit_equal_to<type> : public std::equal_to<type> {}; \ 193 template <> \ 194 struct bit_hash<type> : public hash<type> {}; 195 V8_BASE_BIT_SPECIALIZE_TRIVIAL(signed char) 196 V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned char) 197 V8_BASE_BIT_SPECIALIZE_TRIVIAL(short) // NOLINT(runtime/int) 198 V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned short) // NOLINT(runtime/int) 199 V8_BASE_BIT_SPECIALIZE_TRIVIAL(int) 200 V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned int) 201 V8_BASE_BIT_SPECIALIZE_TRIVIAL(long) // NOLINT(runtime/int) 202 V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned long) // NOLINT(runtime/int) 203 V8_BASE_BIT_SPECIALIZE_TRIVIAL(long long) // NOLINT(runtime/int) 204 V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned long long) // NOLINT(runtime/int) 205 #undef V8_BASE_BIT_SPECIALIZE_TRIVIAL 206 207 #define V8_BASE_BIT_SPECIALIZE_BIT_CAST(type, btype) \ 208 template <> \ 209 struct bit_equal_to<type> : public std::binary_function<type, type, bool> { \ 210 V8_INLINE bool operator()(type lhs, type rhs) const { \ 211 return bit_cast<btype>(lhs) == bit_cast<btype>(rhs); \ 212 } \ 213 }; \ 214 template <> \ 215 struct bit_hash<type> : public std::unary_function<type, size_t> { \ 216 V8_INLINE size_t operator()(type v) const { \ 217 hash<btype> h; \ 218 return h(bit_cast<btype>(v)); \ 219 } \ 220 }; 221 V8_BASE_BIT_SPECIALIZE_BIT_CAST(float, uint32_t) 222 V8_BASE_BIT_SPECIALIZE_BIT_CAST(double, uint64_t) 223 #undef V8_BASE_BIT_SPECIALIZE_BIT_CAST 224 225 } // namespace base 226 } // namespace v8 227 228 #endif // V8_BASE_FUNCTIONAL_H_ 229
