OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
47 typedef uint32_t UnsignedType; | 47 typedef uint32_t UnsignedType; |
48 }; | 48 }; |
49 template <> | 49 template <> |
50 struct IntTypes<8> { | 50 struct IntTypes<8> { |
51 typedef int64_t SignedType; | 51 typedef int64_t SignedType; |
52 typedef uint64_t UnsignedType; | 52 typedef uint64_t UnsignedType; |
53 }; | 53 }; |
54 | 54 |
55 // integer hash function | 55 // integer hash function |
56 | 56 |
57 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 57 // Thomas Wang's 32 Bit Mix Function: |
| 58 // http://www.cris.com/~Ttwang/tech/inthash.htm |
58 inline unsigned hashInt(uint8_t key8) { | 59 inline unsigned hashInt(uint8_t key8) { |
59 unsigned key = key8; | 60 unsigned key = key8; |
60 key += ~(key << 15); | 61 key += ~(key << 15); |
61 key ^= (key >> 10); | 62 key ^= (key >> 10); |
62 key += (key << 3); | 63 key += (key << 3); |
63 key ^= (key >> 6); | 64 key ^= (key >> 6); |
64 key += ~(key << 11); | 65 key += ~(key << 11); |
65 key ^= (key >> 16); | 66 key ^= (key >> 16); |
66 return key; | 67 return key; |
67 } | 68 } |
68 | 69 |
69 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 70 // Thomas Wang's 32 Bit Mix Function: |
| 71 // http://www.cris.com/~Ttwang/tech/inthash.htm |
70 inline unsigned hashInt(uint16_t key16) { | 72 inline unsigned hashInt(uint16_t key16) { |
71 unsigned key = key16; | 73 unsigned key = key16; |
72 key += ~(key << 15); | 74 key += ~(key << 15); |
73 key ^= (key >> 10); | 75 key ^= (key >> 10); |
74 key += (key << 3); | 76 key += (key << 3); |
75 key ^= (key >> 6); | 77 key ^= (key >> 6); |
76 key += ~(key << 11); | 78 key += ~(key << 11); |
77 key ^= (key >> 16); | 79 key ^= (key >> 16); |
78 return key; | 80 return key; |
79 } | 81 } |
80 | 82 |
81 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 83 // Thomas Wang's 32 Bit Mix Function: |
| 84 // http://www.cris.com/~Ttwang/tech/inthash.htm |
82 inline unsigned hashInt(uint32_t key) { | 85 inline unsigned hashInt(uint32_t key) { |
83 key += ~(key << 15); | 86 key += ~(key << 15); |
84 key ^= (key >> 10); | 87 key ^= (key >> 10); |
85 key += (key << 3); | 88 key += (key << 3); |
86 key ^= (key >> 6); | 89 key ^= (key >> 6); |
87 key += ~(key << 11); | 90 key += ~(key << 11); |
88 key ^= (key >> 16); | 91 key ^= (key >> 16); |
89 return key; | 92 return key; |
90 } | 93 } |
91 | 94 |
92 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 95 // Thomas Wang's 64 bit Mix Function: |
| 96 // http://www.cris.com/~Ttwang/tech/inthash.htm |
93 inline unsigned hashInt(uint64_t key) { | 97 inline unsigned hashInt(uint64_t key) { |
94 key += ~(key << 32); | 98 key += ~(key << 32); |
95 key ^= (key >> 22); | 99 key ^= (key >> 22); |
96 key += ~(key << 13); | 100 key += ~(key << 13); |
97 key ^= (key >> 8); | 101 key ^= (key >> 8); |
98 key += (key << 3); | 102 key += (key << 3); |
99 key ^= (key >> 15); | 103 key ^= (key >> 15); |
100 key += ~(key << 27); | 104 key += ~(key << 27); |
101 key ^= (key >> 31); | 105 key ^= (key >> 31); |
102 return static_cast<unsigned>(key); | 106 return static_cast<unsigned>(key); |
103 } | 107 } |
104 | 108 |
105 // Compound integer hash method: http://opendatastructures.org/versions/edition-
0.1d/ods-java/node33.html#SECTION00832000000000000000 | 109 // Compound integer hash method: |
| 110 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 |
106 inline unsigned hashInts(unsigned key1, unsigned key2) { | 111 inline unsigned hashInts(unsigned key1, unsigned key2) { |
107 unsigned shortRandom1 = 277951225; // A random 32-bit value. | 112 unsigned shortRandom1 = 277951225; // A random 32-bit value. |
108 unsigned shortRandom2 = 95187966; // A random 32-bit value. | 113 unsigned shortRandom2 = 95187966; // A random 32-bit value. |
109 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. | 114 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. |
110 | 115 |
111 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2); | 116 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2); |
112 unsigned highBits = | 117 unsigned highBits = |
113 static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned))); | 118 static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned))); |
114 return highBits; | 119 return highBits; |
115 } | 120 } |
(...skipping 18 matching lines...) Expand all Loading... |
134 static const bool safeToCompareToEmptyOrDeleted = true; | 139 static const bool safeToCompareToEmptyOrDeleted = true; |
135 }; | 140 }; |
136 | 141 |
137 // pointer identity hash function | 142 // pointer identity hash function |
138 | 143 |
139 template <typename T> | 144 template <typename T> |
140 struct PtrHash { | 145 struct PtrHash { |
141 static unsigned hash(T* key) { | 146 static unsigned hash(T* key) { |
142 #if COMPILER(MSVC) | 147 #if COMPILER(MSVC) |
143 #pragma warning(push) | 148 #pragma warning(push) |
144 #pragma warning( \ | 149 // work around what seems to be a bug in MSVC's conversion warnings |
145 disable : 4244) // work around what seems to be a bug in MSVC's conversion
warnings | 150 #pragma warning(disable : 4244) |
146 #endif | 151 #endif |
147 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); | 152 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); |
148 #if COMPILER(MSVC) | 153 #if COMPILER(MSVC) |
149 #pragma warning(pop) | 154 #pragma warning(pop) |
150 #endif | 155 #endif |
151 } | 156 } |
152 static bool equal(T* a, T* b) { return a == b; } | 157 static bool equal(T* a, T* b) { return a == b; } |
153 static bool equal(std::nullptr_t, T* b) { return !b; } | 158 static bool equal(std::nullptr_t, T* b) { return !b; } |
154 static bool equal(T* a, std::nullptr_t) { return !a; } | 159 static bool equal(T* a, std::nullptr_t) { return !a; } |
155 static const bool safeToCompareToEmptyOrDeleted = true; | 160 static const bool safeToCompareToEmptyOrDeleted = true; |
(...skipping 29 matching lines...) Expand all Loading... |
185 return a == b.get(); | 190 return a == b.get(); |
186 } | 191 } |
187 }; | 192 }; |
188 | 193 |
189 // Default hash function for each type. | 194 // Default hash function for each type. |
190 template <typename T> | 195 template <typename T> |
191 struct DefaultHash; | 196 struct DefaultHash; |
192 | 197 |
193 // Actual implementation of DefaultHash. | 198 // Actual implementation of DefaultHash. |
194 // | 199 // |
195 // The case of |isIntegral| == false is not implemented. If you see a compile er
ror saying DefaultHashImpl<T, false> | 200 // The case of |isIntegral| == false is not implemented. If you see a compile |
196 // is not defined, that's because the default hash functions for T are not defin
ed. You need to implement them yourself. | 201 // error saying DefaultHashImpl<T, false> is not defined, that's because the |
| 202 // default hash functions for T are not defined. You need to implement them |
| 203 // yourself. |
197 template <typename T, bool isIntegral> | 204 template <typename T, bool isIntegral> |
198 struct DefaultHashImpl; | 205 struct DefaultHashImpl; |
199 | 206 |
200 template <typename T> | 207 template <typename T> |
201 struct DefaultHashImpl<T, true> { | 208 struct DefaultHashImpl<T, true> { |
202 using Hash = IntHash<typename std::make_unsigned<T>::type>; | 209 using Hash = IntHash<typename std::make_unsigned<T>::type>; |
203 }; | 210 }; |
204 | 211 |
205 // Canonical implementation of DefaultHash. | 212 // Canonical implementation of DefaultHash. |
206 template <typename T> | 213 template <typename T> |
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
274 using Hash = PairHash<T, U>; | 281 using Hash = PairHash<T, U>; |
275 }; | 282 }; |
276 | 283 |
277 } // namespace WTF | 284 } // namespace WTF |
278 | 285 |
279 using WTF::DefaultHash; | 286 using WTF::DefaultHash; |
280 using WTF::IntHash; | 287 using WTF::IntHash; |
281 using WTF::PtrHash; | 288 using WTF::PtrHash; |
282 | 289 |
283 #endif // WTF_HashFunctions_h | 290 #endif // WTF_HashFunctions_h |
OLD | NEW |