Line data Source code
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 34075078 : V8_INLINE size_t hash_combine(T const& v, Ts const&... vs) {
74 404338399 : 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 18259476 : 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 11015 : V8_BASE_HASH_VALUE_TRIVIAL(bool)
91 0 : V8_BASE_HASH_VALUE_TRIVIAL(unsigned char)
92 87338026 : 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 165821362 : V8_BASE_HASH_VALUE_SIGNED(int) // NOLINT(runtime/int)
106 27660339 : 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 0 : 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 26621667 : 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 85799702 : 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 179329123 : V8_BASE_HASH_SPECIALIZE(unsigned int)
160 : V8_BASE_HASH_SPECIALIZE(long) // NOLINT(runtime/int)
161 347779668 : 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 702 : V8_BASE_BIT_SPECIALIZE_BIT_CAST(float, uint32_t)
222 7582989 : 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_
|
