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 // |
| 5 |
| 6 // |
| 7 // Deal with the differences between Microsoft and GNU implemenations |
| 8 // of hash_map. Allows all platforms to use |base::hash_map| and |
| 9 // |base::hash_set|. |
| 10 // eg: |
| 11 // base::hash_map<int> my_map; |
| 12 // base::hash_set<int> my_set; |
| 13 // |
| 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, |
| 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 |
| 18 // because identity hashes are not desirable for all types that might show up |
| 19 // in containers as pointers. |
4 | 20 |
5 #ifndef BASE_CONTAINERS_HASH_TABLES_H_ | 21 #ifndef BASE_CONTAINERS_HASH_TABLES_H_ |
6 #define BASE_CONTAINERS_HASH_TABLES_H_ | 22 #define BASE_CONTAINERS_HASH_TABLES_H_ |
7 | 23 |
8 #include <cstddef> | 24 #include <stddef.h> |
| 25 #include <stdint.h> |
| 26 |
| 27 #include <utility> |
| 28 |
| 29 #include "base/strings/string16.h" |
| 30 #include "build/build_config.h" |
| 31 |
| 32 #if defined(COMPILER_MSVC) |
9 #include <unordered_map> | 33 #include <unordered_map> |
10 #include <unordered_set> | 34 #include <unordered_set> |
11 #include <utility> | 35 |
12 | 36 #define BASE_HASH_NAMESPACE std |
13 #include "base/hash.h" | 37 |
14 | 38 #elif defined(COMPILER_GCC) |
15 // This header file is deprecated. Use the corresponding C++11 type | 39 |
16 // instead. https://crbug.com/576864 | |
17 | |
18 // Use a custom hasher instead. | |
19 #define BASE_HASH_NAMESPACE base_hash | 40 #define BASE_HASH_NAMESPACE base_hash |
20 | 41 |
| 42 // This is a hack to disable the gcc 4.4 warning about hash_map and hash_set |
| 43 // being deprecated. We can get rid of this when we upgrade to VS2008 and we |
| 44 // can use <tr1/unordered_map> and <tr1/unordered_set>. |
| 45 #ifdef __DEPRECATED |
| 46 #define CHROME_OLD__DEPRECATED __DEPRECATED |
| 47 #undef __DEPRECATED |
| 48 #endif |
| 49 |
| 50 #include <ext/hash_map> |
| 51 #include <ext/hash_set> |
| 52 #define BASE_HASH_IMPL_NAMESPACE __gnu_cxx |
| 53 |
| 54 #include <string> |
| 55 |
| 56 #ifdef CHROME_OLD__DEPRECATED |
| 57 #define __DEPRECATED CHROME_OLD__DEPRECATED |
| 58 #undef CHROME_OLD__DEPRECATED |
| 59 #endif |
| 60 |
21 namespace BASE_HASH_NAMESPACE { | 61 namespace BASE_HASH_NAMESPACE { |
22 | 62 |
23 // A separate hasher which, by default, forwards to std::hash. This is so legacy | 63 // The pre-standard hash behaves like C++11's std::hash, except around pointers. |
24 // uses of BASE_HASH_NAMESPACE with base::hash_map do not interfere with | 64 // const char* is specialized to hash the C string and hash functions for |
25 // std::hash mid-transition. | 65 // general T* are missing. Define a BASE_HASH_NAMESPACE::hash which aligns with |
| 66 // the C++11 behavior. |
| 67 |
26 template<typename T> | 68 template<typename T> |
27 struct hash { | 69 struct hash { |
28 std::size_t operator()(const T& value) const { | 70 std::size_t operator()(const T& value) const { |
29 return std::hash<T>()(value); | 71 return BASE_HASH_IMPL_NAMESPACE::hash<T>()(value); |
30 } | 72 } |
31 }; | 73 }; |
32 | 74 |
33 // Use base::IntPairHash from base/hash.h as a custom hasher instead. | 75 template<typename T> |
| 76 struct hash<T*> { |
| 77 std::size_t operator()(T* value) const { |
| 78 return BASE_HASH_IMPL_NAMESPACE::hash<uintptr_t>()( |
| 79 reinterpret_cast<uintptr_t>(value)); |
| 80 } |
| 81 }; |
| 82 |
| 83 // The GNU C++ library provides identity hash functions for many integral types, |
| 84 // but not for |long long|. This hash function will truncate if |size_t| is |
| 85 // narrower than |long long|. This is probably good enough for what we will |
| 86 // use it for. |
| 87 |
| 88 #define DEFINE_TRIVIAL_HASH(integral_type) \ |
| 89 template<> \ |
| 90 struct hash<integral_type> { \ |
| 91 std::size_t operator()(integral_type value) const { \ |
| 92 return static_cast<std::size_t>(value); \ |
| 93 } \ |
| 94 } |
| 95 |
| 96 DEFINE_TRIVIAL_HASH(long long); |
| 97 DEFINE_TRIVIAL_HASH(unsigned long long); |
| 98 |
| 99 #undef DEFINE_TRIVIAL_HASH |
| 100 |
| 101 // Implement string hash functions so that strings of various flavors can |
| 102 // be used as keys in STL maps and sets. The hash algorithm comes from the |
| 103 // GNU C++ library, in <tr1/functional>. It is duplicated here because GCC |
| 104 // versions prior to 4.3.2 are unable to compile <tr1/functional> when RTTI |
| 105 // is disabled, as it is in our build. |
| 106 |
| 107 #define DEFINE_STRING_HASH(string_type) \ |
| 108 template<> \ |
| 109 struct hash<string_type> { \ |
| 110 std::size_t operator()(const string_type& s) const { \ |
| 111 std::size_t result = 0; \ |
| 112 for (string_type::const_iterator i = s.begin(); i != s.end(); ++i) \ |
| 113 result = (result * 131) + *i; \ |
| 114 return result; \ |
| 115 } \ |
| 116 } |
| 117 |
| 118 DEFINE_STRING_HASH(std::string); |
| 119 DEFINE_STRING_HASH(base::string16); |
| 120 |
| 121 #undef DEFINE_STRING_HASH |
| 122 |
| 123 } // namespace BASE_HASH_NAMESPACE |
| 124 |
| 125 #else // COMPILER |
| 126 #error define BASE_HASH_NAMESPACE for your compiler |
| 127 #endif // COMPILER |
| 128 |
| 129 namespace base { |
| 130 |
| 131 // On MSVC, use the C++11 containers. |
| 132 #if defined(COMPILER_MSVC) |
| 133 |
| 134 template<class Key, class T, |
| 135 class Hash = std::hash<Key>, |
| 136 class Pred = std::equal_to<Key>, |
| 137 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 138 using hash_map = std::unordered_map<Key, T, Hash, Pred, Alloc>; |
| 139 |
| 140 template<class Key, class T, |
| 141 class Hash = std::hash<Key>, |
| 142 class Pred = std::equal_to<Key>, |
| 143 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 144 using hash_multimap = std::unordered_multimap<Key, T, Hash, Pred, Alloc>; |
| 145 |
| 146 template<class Key, |
| 147 class Hash = std::hash<Key>, |
| 148 class Pred = std::equal_to<Key>, |
| 149 class Alloc = std::allocator<Key>> |
| 150 using hash_multiset = std::unordered_multiset<Key, Hash, Pred, Alloc>; |
| 151 |
| 152 template<class Key, |
| 153 class Hash = std::hash<Key>, |
| 154 class Pred = std::equal_to<Key>, |
| 155 class Alloc = std::allocator<Key>> |
| 156 using hash_set = std::unordered_set<Key, Hash, Pred, Alloc>; |
| 157 |
| 158 #else // !COMPILER_MSVC |
| 159 |
| 160 // Otherwise, use the pre-standard ones, but override the default hash to match |
| 161 // C++11. |
| 162 template<class Key, class T, |
| 163 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 164 class Pred = std::equal_to<Key>, |
| 165 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 166 using hash_map = BASE_HASH_IMPL_NAMESPACE::hash_map<Key, T, Hash, Pred, Alloc>; |
| 167 |
| 168 template<class Key, class T, |
| 169 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 170 class Pred = std::equal_to<Key>, |
| 171 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 172 using hash_multimap = |
| 173 BASE_HASH_IMPL_NAMESPACE::hash_multimap<Key, T, Hash, Pred, Alloc>; |
| 174 |
| 175 template<class Key, |
| 176 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 177 class Pred = std::equal_to<Key>, |
| 178 class Alloc = std::allocator<Key>> |
| 179 using hash_multiset = |
| 180 BASE_HASH_IMPL_NAMESPACE::hash_multiset<Key, Hash, Pred, Alloc>; |
| 181 |
| 182 template<class Key, |
| 183 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 184 class Pred = std::equal_to<Key>, |
| 185 class Alloc = std::allocator<Key>> |
| 186 using hash_set = BASE_HASH_IMPL_NAMESPACE::hash_set<Key, Hash, Pred, Alloc>; |
| 187 |
| 188 #undef BASE_HASH_IMPL_NAMESPACE |
| 189 |
| 190 #endif // COMPILER_MSVC |
| 191 |
| 192 // Implement hashing for pairs of at-most 32 bit integer values. |
| 193 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using |
| 194 // multiply-add hashing. This algorithm, as described in |
| 195 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in |
| 196 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: |
| 197 // |
| 198 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 |
| 199 // |
| 200 // Contact danakj@chromium.org for any questions. |
| 201 inline std::size_t HashInts32(uint32_t value1, uint32_t value2) { |
| 202 uint64_t value1_64 = value1; |
| 203 uint64_t hash64 = (value1_64 << 32) | value2; |
| 204 |
| 205 if (sizeof(std::size_t) >= sizeof(uint64_t)) |
| 206 return static_cast<std::size_t>(hash64); |
| 207 |
| 208 uint64_t odd_random = 481046412LL << 32 | 1025306955LL; |
| 209 uint32_t shift_random = 10121U << 16; |
| 210 |
| 211 hash64 = hash64 * odd_random + shift_random; |
| 212 std::size_t high_bits = static_cast<std::size_t>( |
| 213 hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); |
| 214 return high_bits; |
| 215 } |
| 216 |
| 217 // Implement hashing for pairs of up-to 64-bit integer values. |
| 218 // We use the compound integer hash method to produce a 64-bit hash code, by |
| 219 // breaking the two 64-bit inputs into 4 32-bit values: |
| 220 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 |
| 221 // Then we reduce our result to 32 bits if required, similar to above. |
| 222 inline std::size_t HashInts64(uint64_t value1, uint64_t value2) { |
| 223 uint32_t short_random1 = 842304669U; |
| 224 uint32_t short_random2 = 619063811U; |
| 225 uint32_t short_random3 = 937041849U; |
| 226 uint32_t short_random4 = 3309708029U; |
| 227 |
| 228 uint32_t value1a = static_cast<uint32_t>(value1 & 0xffffffff); |
| 229 uint32_t value1b = static_cast<uint32_t>((value1 >> 32) & 0xffffffff); |
| 230 uint32_t value2a = static_cast<uint32_t>(value2 & 0xffffffff); |
| 231 uint32_t value2b = static_cast<uint32_t>((value2 >> 32) & 0xffffffff); |
| 232 |
| 233 uint64_t product1 = static_cast<uint64_t>(value1a) * short_random1; |
| 234 uint64_t product2 = static_cast<uint64_t>(value1b) * short_random2; |
| 235 uint64_t product3 = static_cast<uint64_t>(value2a) * short_random3; |
| 236 uint64_t product4 = static_cast<uint64_t>(value2b) * short_random4; |
| 237 |
| 238 uint64_t hash64 = product1 + product2 + product3 + product4; |
| 239 |
| 240 if (sizeof(std::size_t) >= sizeof(uint64_t)) |
| 241 return static_cast<std::size_t>(hash64); |
| 242 |
| 243 uint64_t odd_random = 1578233944LL << 32 | 194370989LL; |
| 244 uint32_t shift_random = 20591U << 16; |
| 245 |
| 246 hash64 = hash64 * odd_random + shift_random; |
| 247 std::size_t high_bits = static_cast<std::size_t>( |
| 248 hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); |
| 249 return high_bits; |
| 250 } |
| 251 |
| 252 template<typename T1, typename T2> |
| 253 inline std::size_t HashPair(T1 value1, T2 value2) { |
| 254 // This condition is expected to be compile-time evaluated and optimised away |
| 255 // in release builds. |
| 256 if (sizeof(T1) > sizeof(uint32_t) || (sizeof(T2) > sizeof(uint32_t))) |
| 257 return HashInts64(value1, value2); |
| 258 |
| 259 return HashInts32(value1, value2); |
| 260 } |
| 261 |
| 262 } // namespace base |
| 263 |
| 264 namespace BASE_HASH_NAMESPACE { |
| 265 |
| 266 // Implement methods for hashing a pair of integers, so they can be used as |
| 267 // keys in STL containers. |
| 268 |
34 template<typename Type1, typename Type2> | 269 template<typename Type1, typename Type2> |
35 struct hash<std::pair<Type1, Type2> > { | 270 struct hash<std::pair<Type1, Type2> > { |
36 std::size_t operator()(std::pair<Type1, Type2> value) const { | 271 std::size_t operator()(std::pair<Type1, Type2> value) const { |
37 return base::HashInts(value.first, value.second); | 272 return base::HashPair(value.first, value.second); |
38 } | 273 } |
39 }; | 274 }; |
40 | 275 |
41 } // namespace BASE_HASH_NAMESPACE | 276 } // namespace BASE_HASH_NAMESPACE |
42 | 277 |
43 namespace base { | 278 #undef DEFINE_PAIR_HASH_FUNCTION_START |
44 | 279 #undef DEFINE_PAIR_HASH_FUNCTION_END |
45 // Use std::unordered_map instead. | |
46 template<class Key, class T, | |
47 class Hash = BASE_HASH_NAMESPACE::hash<Key>, | |
48 class Pred = std::equal_to<Key>, | |
49 class Alloc = std::allocator<std::pair<const Key, T>>> | |
50 using hash_map = std::unordered_map<Key, T, Hash, Pred, Alloc>; | |
51 | |
52 // Use std::unordered_multimap instead. | |
53 template<class Key, class T, | |
54 class Hash = BASE_HASH_NAMESPACE::hash<Key>, | |
55 class Pred = std::equal_to<Key>, | |
56 class Alloc = std::allocator<std::pair<const Key, T>>> | |
57 using hash_multimap = std::unordered_multimap<Key, T, Hash, Pred, Alloc>; | |
58 | |
59 // Use std::unordered_multiset instead. | |
60 template<class Key, | |
61 class Hash = BASE_HASH_NAMESPACE::hash<Key>, | |
62 class Pred = std::equal_to<Key>, | |
63 class Alloc = std::allocator<Key>> | |
64 using hash_multiset = std::unordered_multiset<Key, Hash, Pred, Alloc>; | |
65 | |
66 // Use std::unordered_set instead. | |
67 template<class Key, | |
68 class Hash = BASE_HASH_NAMESPACE::hash<Key>, | |
69 class Pred = std::equal_to<Key>, | |
70 class Alloc = std::allocator<Key>> | |
71 using hash_set = std::unordered_set<Key, Hash, Pred, Alloc>; | |
72 | |
73 } // namespace base | |
74 | 280 |
75 #endif // BASE_CONTAINERS_HASH_TABLES_H_ | 281 #endif // BASE_CONTAINERS_HASH_TABLES_H_ |
OLD | NEW |