OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 // | 4 // |
5 | 5 |
6 // | 6 // |
7 // Deal with the differences between Microsoft and GNU implemenations | 7 // Deal with the differences between Microsoft and GNU implemenations |
8 // of hash_map. Allows all platforms to use |base::hash_map| and | 8 // of hash_map. Allows all platforms to use |base::hash_map| and |
9 // |base::hash_set|. | 9 // |base::hash_set|. |
10 // eg: | 10 // eg: |
11 // base::hash_map<int> my_map; | 11 // base::hash_map<int> my_map; |
12 // base::hash_set<int> my_set; | 12 // base::hash_set<int> my_set; |
13 // | 13 // |
14 // NOTE: It is an explicit non-goal of this class to provide a generic hash | 14 // NOTE: It is an explicit non-goal of this class to provide a generic hash |
15 // function for pointers. If you want to hash a pointers to a particular class, | 15 // function for pointers. If you want to hash a pointers to a particular class, |
16 // please define the template specialization elsewhere (for example, in its | 16 // please define the template specialization elsewhere (for example, in its |
17 // header file) and keep it specific to just pointers to that class. This is | 17 // header file) and keep it specific to just pointers to that class. This is |
18 // because identity hashes are not desirable for all types that might show up | 18 // because identity hashes are not desirable for all types that might show up |
19 // in containers as pointers. | 19 // in containers as pointers. |
20 | 20 |
21 #ifndef BASE_CONTAINERS_HASH_TABLES_H_ | 21 #ifndef BASE_CONTAINERS_HASH_TABLES_H_ |
22 #define BASE_CONTAINERS_HASH_TABLES_H_ | 22 #define BASE_CONTAINERS_HASH_TABLES_H_ |
23 | 23 |
| 24 #include <stddef.h> |
| 25 #include <stdint.h> |
| 26 |
24 #include <utility> | 27 #include <utility> |
25 | 28 |
26 #include "base/basictypes.h" | |
27 #include "base/strings/string16.h" | 29 #include "base/strings/string16.h" |
28 #include "build/build_config.h" | 30 #include "build/build_config.h" |
29 | 31 |
30 #if defined(COMPILER_MSVC) | 32 #if defined(COMPILER_MSVC) |
31 #include <unordered_map> | 33 #include <unordered_map> |
32 #include <unordered_set> | 34 #include <unordered_set> |
33 | 35 |
34 #define BASE_HASH_NAMESPACE std | 36 #define BASE_HASH_NAMESPACE std |
35 | 37 |
36 #elif defined(COMPILER_GCC) | 38 #elif defined(COMPILER_GCC) |
(...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
189 | 191 |
190 // Implement hashing for pairs of at-most 32 bit integer values. | 192 // Implement hashing for pairs of at-most 32 bit integer values. |
191 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using | 193 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using |
192 // multiply-add hashing. This algorithm, as described in | 194 // multiply-add hashing. This algorithm, as described in |
193 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in | 195 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in |
194 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: | 196 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: |
195 // | 197 // |
196 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 | 198 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 |
197 // | 199 // |
198 // Contact danakj@chromium.org for any questions. | 200 // Contact danakj@chromium.org for any questions. |
199 inline std::size_t HashInts32(uint32 value1, uint32 value2) { | 201 inline std::size_t HashInts32(uint32_t value1, uint32_t value2) { |
200 uint64 value1_64 = value1; | 202 uint64_t value1_64 = value1; |
201 uint64 hash64 = (value1_64 << 32) | value2; | 203 uint64_t hash64 = (value1_64 << 32) | value2; |
202 | 204 |
203 if (sizeof(std::size_t) >= sizeof(uint64)) | 205 if (sizeof(std::size_t) >= sizeof(uint64_t)) |
204 return static_cast<std::size_t>(hash64); | 206 return static_cast<std::size_t>(hash64); |
205 | 207 |
206 uint64 odd_random = 481046412LL << 32 | 1025306955LL; | 208 uint64_t odd_random = 481046412LL << 32 | 1025306955LL; |
207 uint32 shift_random = 10121U << 16; | 209 uint32_t shift_random = 10121U << 16; |
208 | 210 |
209 hash64 = hash64 * odd_random + shift_random; | 211 hash64 = hash64 * odd_random + shift_random; |
210 std::size_t high_bits = static_cast<std::size_t>( | 212 std::size_t high_bits = static_cast<std::size_t>( |
211 hash64 >> (8 * (sizeof(uint64) - sizeof(std::size_t)))); | 213 hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); |
212 return high_bits; | 214 return high_bits; |
213 } | 215 } |
214 | 216 |
215 // Implement hashing for pairs of up-to 64-bit integer values. | 217 // Implement hashing for pairs of up-to 64-bit integer values. |
216 // We use the compound integer hash method to produce a 64-bit hash code, by | 218 // We use the compound integer hash method to produce a 64-bit hash code, by |
217 // breaking the two 64-bit inputs into 4 32-bit values: | 219 // breaking the two 64-bit inputs into 4 32-bit values: |
218 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 | 220 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 |
219 // Then we reduce our result to 32 bits if required, similar to above. | 221 // Then we reduce our result to 32 bits if required, similar to above. |
220 inline std::size_t HashInts64(uint64 value1, uint64 value2) { | 222 inline std::size_t HashInts64(uint64_t value1, uint64_t value2) { |
221 uint32 short_random1 = 842304669U; | 223 uint32_t short_random1 = 842304669U; |
222 uint32 short_random2 = 619063811U; | 224 uint32_t short_random2 = 619063811U; |
223 uint32 short_random3 = 937041849U; | 225 uint32_t short_random3 = 937041849U; |
224 uint32 short_random4 = 3309708029U; | 226 uint32_t short_random4 = 3309708029U; |
225 | 227 |
226 uint32 value1a = static_cast<uint32>(value1 & 0xffffffff); | 228 uint32_t value1a = static_cast<uint32_t>(value1 & 0xffffffff); |
227 uint32 value1b = static_cast<uint32>((value1 >> 32) & 0xffffffff); | 229 uint32_t value1b = static_cast<uint32_t>((value1 >> 32) & 0xffffffff); |
228 uint32 value2a = static_cast<uint32>(value2 & 0xffffffff); | 230 uint32_t value2a = static_cast<uint32_t>(value2 & 0xffffffff); |
229 uint32 value2b = static_cast<uint32>((value2 >> 32) & 0xffffffff); | 231 uint32_t value2b = static_cast<uint32_t>((value2 >> 32) & 0xffffffff); |
230 | 232 |
231 uint64 product1 = static_cast<uint64>(value1a) * short_random1; | 233 uint64_t product1 = static_cast<uint64_t>(value1a) * short_random1; |
232 uint64 product2 = static_cast<uint64>(value1b) * short_random2; | 234 uint64_t product2 = static_cast<uint64_t>(value1b) * short_random2; |
233 uint64 product3 = static_cast<uint64>(value2a) * short_random3; | 235 uint64_t product3 = static_cast<uint64_t>(value2a) * short_random3; |
234 uint64 product4 = static_cast<uint64>(value2b) * short_random4; | 236 uint64_t product4 = static_cast<uint64_t>(value2b) * short_random4; |
235 | 237 |
236 uint64 hash64 = product1 + product2 + product3 + product4; | 238 uint64_t hash64 = product1 + product2 + product3 + product4; |
237 | 239 |
238 if (sizeof(std::size_t) >= sizeof(uint64)) | 240 if (sizeof(std::size_t) >= sizeof(uint64_t)) |
239 return static_cast<std::size_t>(hash64); | 241 return static_cast<std::size_t>(hash64); |
240 | 242 |
241 uint64 odd_random = 1578233944LL << 32 | 194370989LL; | 243 uint64_t odd_random = 1578233944LL << 32 | 194370989LL; |
242 uint32 shift_random = 20591U << 16; | 244 uint32_t shift_random = 20591U << 16; |
243 | 245 |
244 hash64 = hash64 * odd_random + shift_random; | 246 hash64 = hash64 * odd_random + shift_random; |
245 std::size_t high_bits = static_cast<std::size_t>( | 247 std::size_t high_bits = static_cast<std::size_t>( |
246 hash64 >> (8 * (sizeof(uint64) - sizeof(std::size_t)))); | 248 hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); |
247 return high_bits; | 249 return high_bits; |
248 } | 250 } |
249 | 251 |
250 template<typename T1, typename T2> | 252 template<typename T1, typename T2> |
251 inline std::size_t HashPair(T1 value1, T2 value2) { | 253 inline std::size_t HashPair(T1 value1, T2 value2) { |
252 // This condition is expected to be compile-time evaluated and optimised away | 254 // This condition is expected to be compile-time evaluated and optimised away |
253 // in release builds. | 255 // in release builds. |
254 if (sizeof(T1) > sizeof(uint32_t) || (sizeof(T2) > sizeof(uint32_t))) | 256 if (sizeof(T1) > sizeof(uint32_t) || (sizeof(T2) > sizeof(uint32_t))) |
255 return HashInts64(value1, value2); | 257 return HashInts64(value1, value2); |
256 | 258 |
(...skipping 13 matching lines...) Expand all Loading... |
270 return base::HashPair(value.first, value.second); | 272 return base::HashPair(value.first, value.second); |
271 } | 273 } |
272 }; | 274 }; |
273 | 275 |
274 } // namespace BASE_HASH_NAMESPACE | 276 } // namespace BASE_HASH_NAMESPACE |
275 | 277 |
276 #undef DEFINE_PAIR_HASH_FUNCTION_START | 278 #undef DEFINE_PAIR_HASH_FUNCTION_START |
277 #undef DEFINE_PAIR_HASH_FUNCTION_END | 279 #undef DEFINE_PAIR_HASH_FUNCTION_END |
278 | 280 |
279 #endif // BASE_CONTAINERS_HASH_TABLES_H_ | 281 #endif // BASE_CONTAINERS_HASH_TABLES_H_ |
OLD | NEW |