Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(90)

Side by Side Diff: base/containers/hash_tables.h

Issue 612323010: Align base::hash_map with C++11. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Try a different tack for C++ insanity Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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_
OLDNEW
« no previous file with comments | « no previous file | base/containers/hash_tables_unittest.cc » ('j') | base/containers/small_map_unittest.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698