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: |
(...skipping 10 matching lines...) Expand all Loading... |
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> | 24 #include <utility> |
25 | 25 |
26 #include "base/basictypes.h" | 26 #include "base/basictypes.h" |
27 #include "base/strings/string16.h" | 27 #include "base/strings/string16.h" |
28 #include "build/build_config.h" | 28 #include "build/build_config.h" |
29 | 29 |
30 #if defined(COMPILER_MSVC) | 30 #if defined(COMPILER_MSVC) |
31 #include <hash_map> | 31 #include <unordered_map> |
32 #include <hash_set> | 32 #include <unordered_set> |
33 | 33 |
34 #define BASE_HASH_NAMESPACE stdext | 34 #define BASE_HASH_NAMESPACE std |
35 | 35 |
36 #elif defined(COMPILER_GCC) | 36 #elif defined(COMPILER_GCC) |
37 #if defined(OS_ANDROID) | 37 |
38 #define BASE_HASH_NAMESPACE std | 38 #define BASE_HASH_NAMESPACE base_hash |
39 #else | |
40 #define BASE_HASH_NAMESPACE __gnu_cxx | |
41 #endif | |
42 | 39 |
43 // This is a hack to disable the gcc 4.4 warning about hash_map and hash_set | 40 // This is a hack to disable the gcc 4.4 warning about hash_map and hash_set |
44 // being deprecated. We can get rid of this when we upgrade to VS2008 and we | 41 // being deprecated. We can get rid of this when we upgrade to VS2008 and we |
45 // can use <tr1/unordered_map> and <tr1/unordered_set>. | 42 // can use <tr1/unordered_map> and <tr1/unordered_set>. |
46 #ifdef __DEPRECATED | 43 #ifdef __DEPRECATED |
47 #define CHROME_OLD__DEPRECATED __DEPRECATED | 44 #define CHROME_OLD__DEPRECATED __DEPRECATED |
48 #undef __DEPRECATED | 45 #undef __DEPRECATED |
49 #endif | 46 #endif |
50 | 47 |
51 #if defined(OS_ANDROID) | 48 #if defined(OS_ANDROID) |
52 #include <hash_map> | 49 #include <hash_map> |
53 #include <hash_set> | 50 #include <hash_set> |
| 51 #define BASE_HASH_IMPL_NAMESPACE std |
54 #else | 52 #else |
55 #include <ext/hash_map> | 53 #include <ext/hash_map> |
56 #include <ext/hash_set> | 54 #include <ext/hash_set> |
| 55 #define BASE_HASH_IMPL_NAMESPACE __gnu_cxx |
57 #endif | 56 #endif |
58 | 57 |
59 #include <string> | 58 #include <string> |
60 | 59 |
61 #ifdef CHROME_OLD__DEPRECATED | 60 #ifdef CHROME_OLD__DEPRECATED |
62 #define __DEPRECATED CHROME_OLD__DEPRECATED | 61 #define __DEPRECATED CHROME_OLD__DEPRECATED |
63 #undef CHROME_OLD__DEPRECATED | 62 #undef CHROME_OLD__DEPRECATED |
64 #endif | 63 #endif |
65 | 64 |
66 namespace BASE_HASH_NAMESPACE { | 65 namespace BASE_HASH_NAMESPACE { |
67 | 66 |
| 67 // The pre-standard hash behaves like C++11's std::hash, except around pointers. |
| 68 // const char* is specialized to hash the C string and hash functions for |
| 69 // general T* are missing. Define a BASE_HASH_NAMESPACE::hash which aligns with |
| 70 // the C++11 behavior. |
| 71 |
| 72 template<typename T> |
| 73 struct hash { |
| 74 std::size_t operator()(const T& value) const { |
| 75 BASE_HASH_IMPL_NAMESPACE::hash<T> h; |
| 76 return h(value); |
| 77 } |
| 78 }; |
| 79 |
| 80 template<typename T> |
| 81 struct hash<T*> { |
| 82 std::size_t operator()(T* value) const { |
| 83 BASE_HASH_IMPL_NAMESPACE::hash<uintptr_t> h; |
| 84 return h(reinterpret_cast<uintptr_t>(value)); |
| 85 } |
| 86 }; |
| 87 |
68 #if !defined(OS_ANDROID) | 88 #if !defined(OS_ANDROID) |
69 // The GNU C++ library provides identity hash functions for many integral types, | 89 // The GNU C++ library provides identity hash functions for many integral types, |
70 // but not for |long long|. This hash function will truncate if |size_t| is | 90 // but not for |long long|. This hash function will truncate if |size_t| is |
71 // narrower than |long long|. This is probably good enough for what we will | 91 // narrower than |long long|. This is probably good enough for what we will |
72 // use it for. | 92 // use it for. |
73 | 93 |
74 #define DEFINE_TRIVIAL_HASH(integral_type) \ | 94 #define DEFINE_TRIVIAL_HASH(integral_type) \ |
75 template<> \ | 95 template<> \ |
76 struct hash<integral_type> { \ | 96 struct hash<integral_type> { \ |
77 std::size_t operator()(integral_type value) const { \ | 97 std::size_t operator()(integral_type value) const { \ |
(...skipping 29 matching lines...) Expand all Loading... |
107 | 127 |
108 #undef DEFINE_STRING_HASH | 128 #undef DEFINE_STRING_HASH |
109 | 129 |
110 } // namespace BASE_HASH_NAMESPACE | 130 } // namespace BASE_HASH_NAMESPACE |
111 | 131 |
112 #else // COMPILER | 132 #else // COMPILER |
113 #error define BASE_HASH_NAMESPACE for your compiler | 133 #error define BASE_HASH_NAMESPACE for your compiler |
114 #endif // COMPILER | 134 #endif // COMPILER |
115 | 135 |
116 namespace base { | 136 namespace base { |
117 using BASE_HASH_NAMESPACE::hash_map; | 137 |
118 using BASE_HASH_NAMESPACE::hash_multimap; | 138 // On MSVC, use the C++11 containers. |
119 using BASE_HASH_NAMESPACE::hash_multiset; | 139 #if defined(COMPILER_MSVC) |
120 using BASE_HASH_NAMESPACE::hash_set; | 140 |
| 141 template<class Key, class T, |
| 142 class Hash = std::hash<Key>, |
| 143 class Pred = std::equal_to<Key>, |
| 144 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 145 using hash_map = std::unordered_map<Key, T, Hash, Pred, Alloc>; |
| 146 |
| 147 template<class Key, class T, |
| 148 class Hash = std::hash<Key>, |
| 149 class Pred = std::equal_to<Key>, |
| 150 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 151 using hash_multimap = std::unordered_multimap<Key, T, Hash, Pred, Alloc>; |
| 152 |
| 153 template<class Key, |
| 154 class Hash = std::hash<Key>, |
| 155 class Pred = std::equal_to<Key>, |
| 156 class Alloc = std::allocator<Key>> |
| 157 using hash_multiset = std::unordered_multiset<Key, Hash, Pred, Alloc>; |
| 158 |
| 159 template<class Key, |
| 160 class Hash = std::hash<Key>, |
| 161 class Pred = std::equal_to<Key>, |
| 162 class Alloc = std::allocator<Key>> |
| 163 using hash_set = std::unordered_set<Key, Hash, Pred, Alloc>; |
| 164 |
| 165 #else // !COMPILER_MSVC |
| 166 |
| 167 // Otherwise, use the pre-standard ones, but override the default hash to match |
| 168 // C++11. |
| 169 template<class Key, class T, |
| 170 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 171 class Pred = std::equal_to<Key>, |
| 172 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 173 using hash_map = BASE_HASH_IMPL_NAMESPACE::hash_map<Key, T, Hash, Pred, Alloc>; |
| 174 |
| 175 template<class Key, class T, |
| 176 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 177 class Pred = std::equal_to<Key>, |
| 178 class Alloc = std::allocator<std::pair<const Key, T>>> |
| 179 using hash_multimap = |
| 180 BASE_HASH_IMPL_NAMESPACE::hash_multimap<Key, T, 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_multiset = |
| 187 BASE_HASH_IMPL_NAMESPACE::hash_multiset<Key, Hash, Pred, Alloc>; |
| 188 |
| 189 template<class Key, |
| 190 class Hash = BASE_HASH_NAMESPACE::hash<Key>, |
| 191 class Pred = std::equal_to<Key>, |
| 192 class Alloc = std::allocator<Key>> |
| 193 using hash_set = BASE_HASH_IMPL_NAMESPACE::hash_set<Key, Hash, Pred, Alloc>; |
| 194 |
| 195 #undef BASE_HASH_IMPL_NAMESPACE |
| 196 |
| 197 #endif // COMPILER_MSVC |
121 | 198 |
122 // Implement hashing for pairs of at-most 32 bit integer values. | 199 // Implement hashing for pairs of at-most 32 bit integer values. |
123 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using | 200 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using |
124 // multiply-add hashing. This algorithm, as described in | 201 // multiply-add hashing. This algorithm, as described in |
125 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in | 202 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in |
126 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: | 203 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: |
127 // | 204 // |
128 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 | 205 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 |
129 // | 206 // |
130 // Contact danakj@chromium.org for any questions. | 207 // Contact danakj@chromium.org for any questions. |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
230 DEFINE_64BIT_PAIR_HASH(uint64, uint64); | 307 DEFINE_64BIT_PAIR_HASH(uint64, uint64); |
231 | 308 |
232 #undef DEFINE_64BIT_PAIR_HASH | 309 #undef DEFINE_64BIT_PAIR_HASH |
233 } // namespace base | 310 } // namespace base |
234 | 311 |
235 namespace BASE_HASH_NAMESPACE { | 312 namespace BASE_HASH_NAMESPACE { |
236 | 313 |
237 // Implement methods for hashing a pair of integers, so they can be used as | 314 // Implement methods for hashing a pair of integers, so they can be used as |
238 // keys in STL containers. | 315 // keys in STL containers. |
239 | 316 |
240 #if defined(COMPILER_MSVC) | |
241 | |
242 template<typename Type1, typename Type2> | |
243 inline std::size_t hash_value(const std::pair<Type1, Type2>& value) { | |
244 return base::HashPair(value.first, value.second); | |
245 } | |
246 | |
247 #elif defined(COMPILER_GCC) | |
248 template<typename Type1, typename Type2> | 317 template<typename Type1, typename Type2> |
249 struct hash<std::pair<Type1, Type2> > { | 318 struct hash<std::pair<Type1, Type2> > { |
250 std::size_t operator()(std::pair<Type1, Type2> value) const { | 319 std::size_t operator()(std::pair<Type1, Type2> value) const { |
251 return base::HashPair(value.first, value.second); | 320 return base::HashPair(value.first, value.second); |
252 } | 321 } |
253 }; | 322 }; |
254 | 323 |
255 #else | |
256 #error define hash<std::pair<Type1, Type2> > for your compiler | |
257 #endif // COMPILER | |
258 | |
259 } | 324 } |
260 | 325 |
261 #undef DEFINE_PAIR_HASH_FUNCTION_START | 326 #undef DEFINE_PAIR_HASH_FUNCTION_START |
262 #undef DEFINE_PAIR_HASH_FUNCTION_END | 327 #undef DEFINE_PAIR_HASH_FUNCTION_END |
263 | 328 |
264 #endif // BASE_CONTAINERS_HASH_TABLES_H_ | 329 #endif // BASE_CONTAINERS_HASH_TABLES_H_ |
OLD | NEW |