OLD | NEW |
| (Empty) |
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 <wtf/RefPtr.h> | |
25 #include <stdint.h> | |
26 | |
27 namespace WTF { | |
28 | |
29 template<size_t size> struct IntTypes; | |
30 template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t U
nsignedType; }; | |
31 template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t
UnsignedType; }; | |
32 template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t
UnsignedType; }; | |
33 template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t
UnsignedType; }; | |
34 | |
35 // integer hash function | |
36 | |
37 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | |
38 inline unsigned intHash(uint8_t key8) | |
39 { | |
40 unsigned key = key8; | |
41 key += ~(key << 15); | |
42 key ^= (key >> 10); | |
43 key += (key << 3); | |
44 key ^= (key >> 6); | |
45 key += ~(key << 11); | |
46 key ^= (key >> 16); | |
47 return key; | |
48 } | |
49 | |
50 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | |
51 inline unsigned intHash(uint16_t key16) | |
52 { | |
53 unsigned key = key16; | |
54 key += ~(key << 15); | |
55 key ^= (key >> 10); | |
56 key += (key << 3); | |
57 key ^= (key >> 6); | |
58 key += ~(key << 11); | |
59 key ^= (key >> 16); | |
60 return key; | |
61 } | |
62 | |
63 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | |
64 inline unsigned intHash(uint32_t key) | |
65 { | |
66 key += ~(key << 15); | |
67 key ^= (key >> 10); | |
68 key += (key << 3); | |
69 key ^= (key >> 6); | |
70 key += ~(key << 11); | |
71 key ^= (key >> 16); | |
72 return key; | |
73 } | |
74 | |
75 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | |
76 inline unsigned intHash(uint64_t key) | |
77 { | |
78 key += ~(key << 32); | |
79 key ^= (key >> 22); | |
80 key += ~(key << 13); | |
81 key ^= (key >> 8); | |
82 key += (key << 3); | |
83 key ^= (key >> 15); | |
84 key += ~(key << 27); | |
85 key ^= (key >> 31); | |
86 return static_cast<unsigned>(key); | |
87 } | |
88 | |
89 // Compound integer hash method: http://opendatastructures.org/versions/edit
ion-0.1d/ods-java/node33.html#SECTION00832000000000000000 | |
90 inline unsigned pairIntHash(unsigned key1, unsigned key2) | |
91 { | |
92 unsigned shortRandom1 = 277951225; // A random 32-bit value. | |
93 unsigned shortRandom2 = 95187966; // A random 32-bit value. | |
94 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. | |
95 | |
96 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * ke
y2); | |
97 unsigned highBits = static_cast<unsigned>(product >> (sizeof(uint64_t) -
sizeof(unsigned))); | |
98 return highBits; | |
99 } | |
100 | |
101 template<typename T> struct IntHash { | |
102 static unsigned hash(T key) { return intHash(static_cast<typename IntTyp
es<sizeof(T)>::UnsignedType>(key)); } | |
103 static bool equal(T a, T b) { return a == b; } | |
104 static const bool safeToCompareToEmptyOrDeleted = true; | |
105 }; | |
106 | |
107 template<typename T> struct FloatHash { | |
108 typedef typename IntTypes<sizeof(T)>::UnsignedType Bits; | |
109 static unsigned hash(T key) | |
110 { | |
111 return intHash(bitwise_cast<Bits>(key)); | |
112 } | |
113 static bool equal(T a, T b) | |
114 { | |
115 return bitwise_cast<Bits>(a) == bitwise_cast<Bits>(b); | |
116 } | |
117 static const bool safeToCompareToEmptyOrDeleted = true; | |
118 }; | |
119 | |
120 // pointer identity hash function | |
121 | |
122 template<typename T> struct PtrHash { | |
123 static unsigned hash(T key) | |
124 { | |
125 #if COMPILER(MSVC) | |
126 #pragma warning(push) | |
127 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's c
onversion warnings | |
128 #endif | |
129 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); | |
130 #if COMPILER(MSVC) | |
131 #pragma warning(pop) | |
132 #endif | |
133 } | |
134 static bool equal(T a, T b) { return a == b; } | |
135 static const bool safeToCompareToEmptyOrDeleted = true; | |
136 }; | |
137 template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P*> { | |
138 using PtrHash<P*>::hash; | |
139 static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); } | |
140 using PtrHash<P*>::equal; | |
141 static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a ==
b; } | |
142 static bool equal(P* a, const RefPtr<P>& b) { return a == b; } | |
143 static bool equal(const RefPtr<P>& a, P* b) { return a == b; } | |
144 }; | |
145 | |
146 // default hash function for each type | |
147 | |
148 template<typename T> struct DefaultHash; | |
149 | |
150 template<typename T, typename U> struct PairHash { | |
151 static unsigned hash(const std::pair<T, U>& p) | |
152 { | |
153 return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<
U>::Hash::hash(p.second)); | |
154 } | |
155 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) | |
156 { | |
157 return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<
U>::Hash::equal(a.second, b.second); | |
158 } | |
159 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::
safeToCompareToEmptyOrDeleted | |
160 && DefaultHash<U>::H
ash::safeToCompareToEmptyOrDeleted; | |
161 }; | |
162 | |
163 template<typename T, typename U> struct IntPairHash { | |
164 static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.fi
rst, p.second); } | |
165 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) {
return PairHash<T, T>::equal(a, b); } | |
166 static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeTo
CompareToEmptyOrDeleted; | |
167 }; | |
168 | |
169 // make IntHash the default hash function for many integer types | |
170 | |
171 template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; }; | |
172 template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Ha
sh; }; | |
173 template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; }; | |
174 template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; }; | |
175 template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; }
; | |
176 template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long
> Hash; }; | |
177 template<> struct DefaultHash<long long> { typedef IntHash<unsigned long lon
g> Hash; }; | |
178 template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned
long long> Hash; }; | |
179 | |
180 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) | |
181 template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; }; | |
182 #endif | |
183 | |
184 template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; }; | |
185 template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; }; | |
186 | |
187 // make PtrHash the default hash function for pointer types that don't speci
alize | |
188 | |
189 template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; }; | |
190 template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr
<P> > Hash; }; | |
191 | |
192 // make IntPairHash the default hash function for pairs of (at most) 32-bit
integers. | |
193 | |
194 template<> struct DefaultHash<std::pair<short, short> > { typedef IntPairHas
h<short, short> Hash; }; | |
195 template<> struct DefaultHash<std::pair<short, unsigned short> > { typedef I
ntPairHash<short, unsigned short> Hash; }; | |
196 template<> struct DefaultHash<std::pair<short, int> > { typedef IntPairHash<
short, int> Hash; }; | |
197 template<> struct DefaultHash<std::pair<short, unsigned> > { typedef IntPair
Hash<short, unsigned> Hash; }; | |
198 template<> struct DefaultHash<std::pair<unsigned short, short> > { typedef I
ntPairHash<unsigned short, short> Hash; }; | |
199 template<> struct DefaultHash<std::pair<unsigned short, unsigned short> > {
typedef IntPairHash<unsigned short, unsigned short> Hash; }; | |
200 template<> struct DefaultHash<std::pair<unsigned short, int> > { typedef Int
PairHash<unsigned short, int> Hash; }; | |
201 template<> struct DefaultHash<std::pair<unsigned short, unsigned> > { typede
f IntPairHash<unsigned short, unsigned> Hash; }; | |
202 template<> struct DefaultHash<std::pair<int, short> > { typedef IntPairHash<
int, short> Hash; }; | |
203 template<> struct DefaultHash<std::pair<int, unsigned short> > { typedef Int
PairHash<int, unsigned short> Hash; }; | |
204 template<> struct DefaultHash<std::pair<int, int> > { typedef IntPairHash<in
t, int> Hash; }; | |
205 template<> struct DefaultHash<std::pair<int, unsigned> > { typedef IntPairHa
sh<unsigned, unsigned> Hash; }; | |
206 template<> struct DefaultHash<std::pair<unsigned, short> > { typedef IntPair
Hash<unsigned, short> Hash; }; | |
207 template<> struct DefaultHash<std::pair<unsigned, unsigned short> > { typede
f IntPairHash<unsigned, unsigned short> Hash; }; | |
208 template<> struct DefaultHash<std::pair<unsigned, int> > { typedef IntPairHa
sh<unsigned, int> Hash; }; | |
209 template<> struct DefaultHash<std::pair<unsigned, unsigned> > { typedef IntP
airHash<unsigned, unsigned> Hash; }; | |
210 | |
211 // make PairHash the default hash function for pairs of arbitrary values. | |
212 | |
213 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { type
def PairHash<T, U> Hash; }; | |
214 | |
215 } // namespace WTF | |
216 | |
217 using WTF::DefaultHash; | |
218 using WTF::IntHash; | |
219 using WTF::PtrHash; | |
220 | |
221 #endif // WTF_HashFunctions_h | |
OLD | NEW |