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 <utility> |
| 25 |
| 26 #include "base/basictypes.h" |
24 #include "base/strings/string16.h" | 27 #include "base/strings/string16.h" |
25 #include "build/build_config.h" | 28 #include "build/build_config.h" |
26 | 29 |
27 #if defined(COMPILER_MSVC) | 30 #if defined(COMPILER_MSVC) |
28 #include <hash_map> | 31 #include <hash_map> |
29 #include <hash_set> | 32 #include <hash_set> |
30 | 33 |
31 #define BASE_HASH_NAMESPACE stdext | 34 #define BASE_HASH_NAMESPACE stdext |
32 | 35 |
33 #elif defined(COMPILER_GCC) | 36 #elif defined(COMPILER_GCC) |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
110 #error define BASE_HASH_NAMESPACE for your compiler | 113 #error define BASE_HASH_NAMESPACE for your compiler |
111 #endif // COMPILER | 114 #endif // COMPILER |
112 | 115 |
113 namespace base { | 116 namespace base { |
114 using BASE_HASH_NAMESPACE::hash_map; | 117 using BASE_HASH_NAMESPACE::hash_map; |
115 using BASE_HASH_NAMESPACE::hash_multimap; | 118 using BASE_HASH_NAMESPACE::hash_multimap; |
116 using BASE_HASH_NAMESPACE::hash_multiset; | 119 using BASE_HASH_NAMESPACE::hash_multiset; |
117 using BASE_HASH_NAMESPACE::hash_set; | 120 using BASE_HASH_NAMESPACE::hash_set; |
118 } | 121 } |
119 | 122 |
| 123 |
| 124 // Implement methods for hashing a pair of integers, so they can be used as |
| 125 // keys in STL containers. |
| 126 |
| 127 #if defined(COMPILER_MSVC) |
| 128 |
| 129 #define DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) \ |
| 130 template<> \ |
| 131 inline std::size_t hash_value<std::pair<type1, type2> >( \ |
| 132 const std::pair<type1, type2>& value) |
| 133 |
| 134 #define DEFINE_PAIR_HASH_FUNCTION_END() |
| 135 |
| 136 #elif defined(COMPILER_GCC) |
| 137 |
| 138 #define DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) \ |
| 139 template<> \ |
| 140 struct hash<std::pair<type1, type2> > { \ |
| 141 std::size_t operator()(std::pair<type1, type2> value) const |
| 142 |
| 143 #define DEFINE_PAIR_HASH_FUNCTION_END() \ |
| 144 }; |
| 145 |
| 146 #else |
| 147 #error define DEFINE_PAIR_HASH_FUNCTION_START for your compiler |
| 148 #endif // COMPILER |
| 149 |
| 150 namespace BASE_HASH_NAMESPACE { |
| 151 |
| 152 // Implement hashing for pairs of at-most 32 bit integer values. |
| 153 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using |
| 154 // multiply-add hashing. This algorithm, as described in |
| 155 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in |
| 156 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: |
| 157 // |
| 158 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 |
| 159 // |
| 160 // Contact danakj@chromium.org for any questions. |
| 161 #define DEFINE_32BIT_PAIR_HASH(type1, type2) \ |
| 162 DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \ |
| 163 uint64 first = value.first; \ |
| 164 uint32 second = value.second; \ |
| 165 uint64 hash64 = (first << 32) | second; \ |
| 166 \ |
| 167 if (sizeof(std::size_t) >= sizeof(uint64)) \ |
| 168 return static_cast<std::size_t>(hash64); \ |
| 169 \ |
| 170 uint64 odd_random = 481046412LL << 32 | 1025306954LL; \ |
| 171 uint32 shift_random = 10121U << 16; \ |
| 172 \ |
| 173 hash64 = hash64 * odd_random + shift_random; \ |
| 174 std::size_t high_bits = static_cast<std::size_t>( \ |
| 175 hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \ |
| 176 return high_bits; \ |
| 177 } \ |
| 178 DEFINE_PAIR_HASH_FUNCTION_END(); |
| 179 |
| 180 DEFINE_32BIT_PAIR_HASH(int16, int16); |
| 181 DEFINE_32BIT_PAIR_HASH(int16, uint16); |
| 182 DEFINE_32BIT_PAIR_HASH(int16, int32); |
| 183 DEFINE_32BIT_PAIR_HASH(int16, uint32); |
| 184 DEFINE_32BIT_PAIR_HASH(uint16, int16); |
| 185 DEFINE_32BIT_PAIR_HASH(uint16, uint16); |
| 186 DEFINE_32BIT_PAIR_HASH(uint16, int32); |
| 187 DEFINE_32BIT_PAIR_HASH(uint16, uint32); |
| 188 DEFINE_32BIT_PAIR_HASH(int32, int16); |
| 189 DEFINE_32BIT_PAIR_HASH(int32, uint16); |
| 190 DEFINE_32BIT_PAIR_HASH(int32, int32); |
| 191 DEFINE_32BIT_PAIR_HASH(int32, uint32); |
| 192 DEFINE_32BIT_PAIR_HASH(uint32, int16); |
| 193 DEFINE_32BIT_PAIR_HASH(uint32, uint16); |
| 194 DEFINE_32BIT_PAIR_HASH(uint32, int32); |
| 195 DEFINE_32BIT_PAIR_HASH(uint32, uint32); |
| 196 |
| 197 #undef DEFINE_32BIT_PAIR_HASH |
| 198 |
| 199 // Implement hashing for pairs of up-to 64-bit integer values. |
| 200 // We use the compound integer hash method to produce a 64-bit hash code, by |
| 201 // breaking the two 64-bit inputs into 4 32-bit values: |
| 202 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 |
| 203 // Then we reduce our result to 32 bits if required, similar to above. |
| 204 #define DEFINE_64BIT_PAIR_HASH(type1, type2) \ |
| 205 DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \ |
| 206 uint32 short_random1 = 842304669U; \ |
| 207 uint32 short_random2 = 619063811U; \ |
| 208 uint32 short_random3 = 937041849U; \ |
| 209 uint32 short_random4 = 3309708029U; \ |
| 210 \ |
| 211 uint64 value1 = value.first; \ |
| 212 uint64 value2 = value.second; \ |
| 213 uint32 value1a = static_cast<uint32>(value1 & 0xffffffff); \ |
| 214 uint32 value1b = static_cast<uint32>((value1 >> 32) & 0xffffffff); \ |
| 215 uint32 value2a = static_cast<uint32>(value2 & 0xffffffff); \ |
| 216 uint32 value2b = static_cast<uint32>((value2 >> 32) & 0xffffffff); \ |
| 217 \ |
| 218 uint64 product1 = static_cast<uint64>(value1a) * short_random1; \ |
| 219 uint64 product2 = static_cast<uint64>(value1b) * short_random2; \ |
| 220 uint64 product3 = static_cast<uint64>(value2a) * short_random3; \ |
| 221 uint64 product4 = static_cast<uint64>(value2b) * short_random4; \ |
| 222 \ |
| 223 uint64 hash64 = product1 + product2 + product3 + product4; \ |
| 224 \ |
| 225 if (sizeof(std::size_t) >= sizeof(uint64)) \ |
| 226 return static_cast<std::size_t>(hash64); \ |
| 227 \ |
| 228 uint64 odd_random = 1578233944LL << 32 | 194370989LL; \ |
| 229 uint32 shift_random = 20591U << 16; \ |
| 230 \ |
| 231 hash64 = hash64 * odd_random + shift_random; \ |
| 232 std::size_t high_bits = static_cast<std::size_t>( \ |
| 233 hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \ |
| 234 return high_bits; \ |
| 235 } \ |
| 236 DEFINE_PAIR_HASH_FUNCTION_END(); |
| 237 |
| 238 DEFINE_64BIT_PAIR_HASH(int16, int64); |
| 239 DEFINE_64BIT_PAIR_HASH(int16, uint64); |
| 240 DEFINE_64BIT_PAIR_HASH(uint16, int64); |
| 241 DEFINE_64BIT_PAIR_HASH(uint16, uint64); |
| 242 DEFINE_64BIT_PAIR_HASH(int32, int64); |
| 243 DEFINE_64BIT_PAIR_HASH(int32, uint64); |
| 244 DEFINE_64BIT_PAIR_HASH(uint32, int64); |
| 245 DEFINE_64BIT_PAIR_HASH(uint32, uint64); |
| 246 DEFINE_64BIT_PAIR_HASH(int64, int16); |
| 247 DEFINE_64BIT_PAIR_HASH(int64, uint16); |
| 248 DEFINE_64BIT_PAIR_HASH(int64, int32); |
| 249 DEFINE_64BIT_PAIR_HASH(int64, uint32); |
| 250 DEFINE_64BIT_PAIR_HASH(int64, int64); |
| 251 DEFINE_64BIT_PAIR_HASH(int64, uint64); |
| 252 DEFINE_64BIT_PAIR_HASH(uint64, int16); |
| 253 DEFINE_64BIT_PAIR_HASH(uint64, uint16); |
| 254 DEFINE_64BIT_PAIR_HASH(uint64, int32); |
| 255 DEFINE_64BIT_PAIR_HASH(uint64, uint32); |
| 256 DEFINE_64BIT_PAIR_HASH(uint64, int64); |
| 257 DEFINE_64BIT_PAIR_HASH(uint64, uint64); |
| 258 |
| 259 #undef DEFINE_64BIT_PAIR_HASH |
| 260 } |
| 261 |
| 262 #undef DEFINE_PAIR_HASH_FUNCTION_START |
| 263 #undef DEFINE_PAIR_HASH_FUNCTION_END |
| 264 |
120 #endif // BASE_CONTAINERS_HASH_TABLES_H_ | 265 #endif // BASE_CONTAINERS_HASH_TABLES_H_ |
OLD | NEW |