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
hash_combine()68 V8_INLINE size_t hash_combine() { return 0u; }
hash_combine(size_t seed)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>
hash_combine(T const & v,Ts const &...vs)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>
hash_range(Iterator first,Iterator last)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)
V8_BASE_HASH_VALUE_SIGNED(short)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
hash_value(double v)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>
hash_value(const T (& v)[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>
hash_value(T (& v)[N])125 V8_INLINE size_t hash_value(T (&v)[N]) {
126 return hash_range(v, v + N);
127 }
128
129 template <typename T>
hash_value(T * const & v)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>
hash_value(std::pair<T1,T2> const & v)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> {
operatorhash142 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