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 "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 UnsignedType; }; |
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/inthash.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/inthash.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/inthash.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/inthash.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 | template<typename T> struct IntHash { |
90 | static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); } |
91 | static bool equal(T a, T b) { return a == b; } |
92 | static const bool safeToCompareToEmptyOrDeleted = true; |
93 | }; |
94 | |
95 | template<typename T> struct FloatHash { |
96 | static unsigned hash(T key) |
97 | { |
98 | union { |
99 | T key; |
100 | typename IntTypes<sizeof(T)>::UnsignedType bits; |
101 | } u; |
102 | u.key = key; |
103 | return intHash(u.bits); |
104 | } |
105 | static bool equal(T a, T b) { return a == b; } |
106 | static const bool safeToCompareToEmptyOrDeleted = true; |
107 | }; |
108 | |
109 | // pointer identity hash function |
110 | |
111 | template<typename T> struct PtrHash { |
112 | static unsigned hash(T key) |
113 | { |
114 | #if COMPILER(MSVC) |
115 | #pragma warning(push) |
116 | #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings |
117 | #endif |
118 | return IntHash<uintptr_t>::hash(key: reinterpret_cast<uintptr_t>(key)); |
119 | #if COMPILER(MSVC) |
120 | #pragma warning(pop) |
121 | #endif |
122 | } |
123 | static bool equal(T a, T b) { return a == b; } |
124 | static const bool safeToCompareToEmptyOrDeleted = true; |
125 | }; |
126 | template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P*> { |
127 | using PtrHash<P*>::hash; |
128 | static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); } |
129 | using PtrHash<P*>::equal; |
130 | static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; } |
131 | static bool equal(P* a, const RefPtr<P>& b) { return a == b; } |
132 | static bool equal(const RefPtr<P>& a, P* b) { return a == b; } |
133 | }; |
134 | |
135 | // default hash function for each type |
136 | |
137 | template<typename T> struct DefaultHash; |
138 | |
139 | template<typename T, typename U> struct PairHash { |
140 | static unsigned hash(const std::pair<T, U>& p) |
141 | { |
142 | return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second))); |
143 | } |
144 | static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) |
145 | { |
146 | return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second); |
147 | } |
148 | static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted |
149 | && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted; |
150 | }; |
151 | |
152 | // make IntHash the default hash function for many integer types |
153 | |
154 | template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; }; |
155 | template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Hash; }; |
156 | template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; }; |
157 | template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; }; |
158 | template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; }; |
159 | template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; }; |
160 | template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; }; |
161 | template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; }; |
162 | |
163 | #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) |
164 | template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; }; |
165 | #endif |
166 | |
167 | template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; }; |
168 | template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; }; |
169 | |
170 | // make PtrHash the default hash function for pointer types that don't specialize |
171 | |
172 | template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; }; |
173 | template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; }; |
174 | |
175 | template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; }; |
176 | |
177 | } // namespace WTF |
178 | |
179 | using WTF::DefaultHash; |
180 | using WTF::IntHash; |
181 | using WTF::PtrHash; |
182 | |
183 | #endif // WTF_HashFunctions_h |
184 | |