Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / HashFunctions.h
1 /*
2  * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public License
15  * along with this library; see the file COPYING.LIB.  If not, write to
16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  * Boston, MA 02110-1301, USA.
18  *
19  */
20
21 #ifndef WTF_HashFunctions_h
22 #define WTF_HashFunctions_h
23
24 #include <stdint.h>
25 #include <tuple>
26 #include <wtf/GetPtr.h>
27 #include <wtf/RefPtr.h>
28
29 namespace WTF {
30
31     template<size_t size> struct IntTypes;
32     template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
33     template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
34     template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
35     template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
36
37     // integer hash function
38
39     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
40     inline unsigned intHash(uint8_t key8)
41     {
42         unsigned key = key8;
43         key += ~(key << 15);
44         key ^= (key >> 10);
45         key += (key << 3);
46         key ^= (key >> 6);
47         key += ~(key << 11);
48         key ^= (key >> 16);
49         return key;
50     }
51
52     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
53     inline unsigned intHash(uint16_t key16)
54     {
55         unsigned key = key16;
56         key += ~(key << 15);
57         key ^= (key >> 10);
58         key += (key << 3);
59         key ^= (key >> 6);
60         key += ~(key << 11);
61         key ^= (key >> 16);
62         return key;
63     }
64
65     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
66     inline unsigned intHash(uint32_t key) 
67     {
68         key += ~(key << 15);
69         key ^= (key >> 10);
70         key += (key << 3);
71         key ^= (key >> 6);
72         key += ~(key << 11);
73         key ^= (key >> 16);
74         return key;
75     }
76     
77     // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
78     inline unsigned intHash(uint64_t key)
79     {
80         key += ~(key << 32);
81         key ^= (key >> 22);
82         key += ~(key << 13);
83         key ^= (key >> 8);
84         key += (key << 3);
85         key ^= (key >> 15);
86         key += ~(key << 27);
87         key ^= (key >> 31);
88         return static_cast<unsigned>(key);
89     }
90
91     // Compound integer hash method: http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
92     inline unsigned pairIntHash(unsigned key1, unsigned key2)
93     {
94         unsigned shortRandom1 = 277951225; // A random 32-bit value.
95         unsigned shortRandom2 = 95187966; // A random 32-bit value.
96         uint64_t longRandom = 19248658165952622LL; // A random 64-bit value.
97
98         uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2);
99         unsigned highBits = static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned)));
100         return highBits;
101     }
102
103     template<typename T> struct IntHash {
104         static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
105         static bool equal(T a, T b) { return a == b; }
106         static const bool safeToCompareToEmptyOrDeleted = true;
107     };
108
109     template<typename T> struct FloatHash {
110         typedef typename IntTypes<sizeof(T)>::UnsignedType Bits;
111         static unsigned hash(T key)
112         {
113             return intHash(bitwise_cast<Bits>(key));
114         }
115         static bool equal(T a, T b)
116         {
117             return bitwise_cast<Bits>(a) == bitwise_cast<Bits>(b);
118         }
119         static const bool safeToCompareToEmptyOrDeleted = true;
120     };
121
122     // pointer identity hash function
123
124     template<typename T, bool isSmartPointer> 
125     struct PtrHashBase;
126
127     template <typename T>
128     struct PtrHashBase<T, false /* isSmartPtr */> {
129         typedef T PtrType; 
130
131         static unsigned hash(PtrType key) { return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); }
132         static bool equal(PtrType a, PtrType b) { return a == b; }
133         static const bool safeToCompareToEmptyOrDeleted = true;
134     };
135
136     template <typename T>
137     struct PtrHashBase<T, true /* isSmartPtr */> {
138         typedef typename GetPtrHelper<T>::PtrType PtrType; 
139
140         static unsigned hash(PtrType key) { return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); }
141         static bool equal(PtrType a, PtrType b) { return a == b; }
142         static const bool safeToCompareToEmptyOrDeleted = true;
143
144         static unsigned hash(const T& key) { return hash(getPtr(key)); }
145         static bool equal(const T& a, const T& b) { return getPtr(a) == getPtr(b); }
146         static bool equal(PtrType a, const T& b) { return a == getPtr(b); }
147         static bool equal(const T& a, PtrType b) { return getPtr(a) == b; }
148     };
149
150     template<typename T> struct PtrHash : PtrHashBase<T, IsSmartPtr<T>::value> {
151     };
152
153     template<typename P> struct PtrHash<Ref<P>> : PtrHashBase<Ref<P>, IsSmartPtr<Ref<P>>::value> {
154         static const bool safeToCompareToEmptyOrDeleted = false;
155     };
156
157     // default hash function for each type
158
159     template<typename T> struct DefaultHash;
160
161     template<typename T, typename U> struct PairHash {
162         static unsigned hash(const std::pair<T, U>& p)
163         {
164             return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<U>::Hash::hash(p.second));
165         }
166         static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
167         {
168             return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second);
169         }
170         static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
171     };
172
173     template<typename T, typename U> struct IntPairHash {
174         static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.first, p.second); }
175         static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) { return PairHash<T, T>::equal(a, b); }
176         static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeToCompareToEmptyOrDeleted;
177     };
178
179     template<typename... Types>
180     struct TupleHash {
181         template<size_t I = 0>
182         static typename std::enable_if<I < sizeof...(Types) - 1, unsigned>::type hash(const std::tuple<Types...>& t)
183         {
184             using IthTupleElementType = typename std::tuple_element<I, typename std::tuple<Types...>>::type;
185             return pairIntHash(DefaultHash<IthTupleElementType>::Hash::hash(std::get<I>(t)), hash<I + 1>(t));
186         }
187
188         template<size_t I = 0>
189         static typename std::enable_if<I == sizeof...(Types) - 1, unsigned>::type hash(const std::tuple<Types...>& t)
190         {
191             using IthTupleElementType = typename std::tuple_element<I, typename std::tuple<Types...>>::type;
192             return DefaultHash<IthTupleElementType>::Hash::hash(std::get<I>(t));
193         }
194
195         template<size_t I = 0>
196         static typename std::enable_if<I < sizeof...(Types) - 1, bool>::type equal(const std::tuple<Types...>& a, const std::tuple<Types...>& b)
197         {
198             using IthTupleElementType = typename std::tuple_element<I, typename std::tuple<Types...>>::type;
199             return DefaultHash<IthTupleElementType>::Hash::equal(std::get<I>(a), std::get<I>(b)) && equal<I + 1>(a, b);
200         }
201
202         template<size_t I = 0>
203         static typename std::enable_if<I == sizeof...(Types) - 1, bool>::type equal(const std::tuple<Types...>& a, const std::tuple<Types...>& b)
204         {
205             using IthTupleElementType = typename std::tuple_element<I, typename std::tuple<Types...>>::type;
206             return DefaultHash<IthTupleElementType>::Hash::equal(std::get<I>(a), std::get<I>(b));
207         }
208
209         // We should use safeToCompareToEmptyOrDeleted = DefaultHash<Types>::Hash::safeToCompareToEmptyOrDeleted &&... whenever
210         // we switch to C++17. We can't do anything better here right now because GCC can't do C++.
211         template<typename BoolType>
212         static constexpr bool allTrue(BoolType value) { return value; }
213         template<typename BoolType, typename... BoolTypes>
214         static constexpr bool allTrue(BoolType value, BoolTypes... values) { return value && allTrue(values...); }
215         static const bool safeToCompareToEmptyOrDeleted = allTrue(DefaultHash<Types>::Hash::safeToCompareToEmptyOrDeleted...);
216     };
217
218     // make IntHash the default hash function for many integer types
219
220     template<> struct DefaultHash<bool> { typedef IntHash<uint8_t> Hash; };
221     template<> struct DefaultHash<uint8_t> { typedef IntHash<uint8_t> Hash; };
222     template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
223     template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Hash; };
224     template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
225     template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
226     template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
227     template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
228     template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
229     template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
230
231 #if defined(_NATIVE_WCHAR_T_DEFINED)
232     template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; };
233 #endif
234
235     template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; };
236     template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; };
237
238     // make PtrHash the default hash function for pointer types that don't specialize
239
240     template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
241     template<typename P> struct DefaultHash<RefPtr<P>> { typedef PtrHash<RefPtr<P>> Hash; };
242     template<typename P> struct DefaultHash<Ref<P>> { typedef PtrHash<Ref<P>> Hash; };
243
244     template<typename P, typename Deleter> struct DefaultHash<std::unique_ptr<P, Deleter>> { typedef PtrHash<std::unique_ptr<P, Deleter>> Hash; };
245
246     // make IntPairHash the default hash function for pairs of (at most) 32-bit integers.
247
248     template<> struct DefaultHash<std::pair<short, short>> { typedef IntPairHash<short, short> Hash; };
249     template<> struct DefaultHash<std::pair<short, unsigned short>> { typedef IntPairHash<short, unsigned short> Hash; };
250     template<> struct DefaultHash<std::pair<short, int>> { typedef IntPairHash<short, int> Hash; };
251     template<> struct DefaultHash<std::pair<short, unsigned>> { typedef IntPairHash<short, unsigned> Hash; };
252     template<> struct DefaultHash<std::pair<unsigned short, short>> { typedef IntPairHash<unsigned short, short> Hash; };
253     template<> struct DefaultHash<std::pair<unsigned short, unsigned short>> { typedef IntPairHash<unsigned short, unsigned short> Hash; };
254     template<> struct DefaultHash<std::pair<unsigned short, int>> { typedef IntPairHash<unsigned short, int> Hash; };
255     template<> struct DefaultHash<std::pair<unsigned short, unsigned>> { typedef IntPairHash<unsigned short, unsigned> Hash; };
256     template<> struct DefaultHash<std::pair<int, short>> { typedef IntPairHash<int, short> Hash; };
257     template<> struct DefaultHash<std::pair<int, unsigned short>> { typedef IntPairHash<int, unsigned short> Hash; };
258     template<> struct DefaultHash<std::pair<int, int>> { typedef IntPairHash<int, int> Hash; };
259     template<> struct DefaultHash<std::pair<int, unsigned>> { typedef IntPairHash<unsigned, unsigned> Hash; };
260     template<> struct DefaultHash<std::pair<unsigned, short>> { typedef IntPairHash<unsigned, short> Hash; };
261     template<> struct DefaultHash<std::pair<unsigned, unsigned short>> { typedef IntPairHash<unsigned, unsigned short> Hash; };
262     template<> struct DefaultHash<std::pair<unsigned, int>> { typedef IntPairHash<unsigned, int> Hash; };
263     template<> struct DefaultHash<std::pair<unsigned, unsigned>> { typedef IntPairHash<unsigned, unsigned> Hash; };
264
265     // make PairHash the default hash function for pairs of arbitrary values.
266
267     template<typename T, typename U> struct DefaultHash<std::pair<T, U>> { typedef PairHash<T, U> Hash; };
268     template<typename... Types> struct DefaultHash<std::tuple<Types...>> { typedef TupleHash<Types...> Hash; };
269
270 } // namespace WTF
271
272 using WTF::DefaultHash;
273 using WTF::IntHash;
274 using WTF::PtrHash;
275
276 #endif // WTF_HashFunctions_h