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