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 |
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 |butil::hash_map| and |
9 | // |butil::hash_set|. |
10 | // eg: |
11 | // butil::hash_map<int, std::string> my_map; |
12 | // butil::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. |
20 | |
21 | #ifndef BUTIL_CONTAINERS_HASH_TABLES_H_ |
22 | #define BUTIL_CONTAINERS_HASH_TABLES_H_ |
23 | |
24 | #include <utility> |
25 | |
26 | #include "butil/basictypes.h" |
27 | #include "butil/strings/string16.h" |
28 | #include "butil/build_config.h" |
29 | #include "butil/third_party/murmurhash3/murmurhash3.h" // fmix64 |
30 | |
31 | #if defined(COMPILER_MSVC) |
32 | #include <hash_map> |
33 | #include <hash_set> |
34 | |
35 | #define BUTIL_HASH_NAMESPACE stdext |
36 | |
37 | #elif defined(COMPILER_GCC) |
38 | #if defined(OS_ANDROID) |
39 | #define BUTIL_HASH_NAMESPACE std |
40 | #else |
41 | #define BUTIL_HASH_NAMESPACE __gnu_cxx |
42 | #endif |
43 | |
44 | // This is a hack to disable the gcc 4.4 warning about hash_map and hash_set |
45 | // being deprecated. We can get rid of this when we upgrade to VS2008 and we |
46 | // can use <tr1/unordered_map> and <tr1/unordered_set>. |
47 | #ifdef __DEPRECATED |
48 | #define CHROME_OLD__DEPRECATED __DEPRECATED |
49 | #undef __DEPRECATED |
50 | #endif |
51 | |
52 | #if defined(OS_ANDROID) |
53 | #include <hash_map> |
54 | #include <hash_set> |
55 | #else |
56 | #include <ext/hash_map> |
57 | #include <ext/hash_set> |
58 | #endif |
59 | |
60 | #include <string> |
61 | |
62 | #ifdef CHROME_OLD__DEPRECATED |
63 | #define __DEPRECATED CHROME_OLD__DEPRECATED |
64 | #undef CHROME_OLD__DEPRECATED |
65 | #endif |
66 | |
67 | namespace BUTIL_HASH_NAMESPACE { |
68 | |
69 | #if !defined(OS_ANDROID) |
70 | // The GNU C++ library provides identity hash functions for many integral types, |
71 | // but not for |long long|. This hash function will truncate if |size_t| is |
72 | // narrower than |long long|. This is probably good enough for what we will |
73 | // use it for. |
74 | |
75 | #define DEFINE_TRIVIAL_HASH(integral_type) \ |
76 | template<> \ |
77 | struct hash<integral_type> { \ |
78 | std::size_t operator()(integral_type value) const { \ |
79 | return static_cast<std::size_t>(value); \ |
80 | } \ |
81 | } |
82 | |
83 | DEFINE_TRIVIAL_HASH(long long); |
84 | DEFINE_TRIVIAL_HASH(unsigned long long); |
85 | |
86 | #undef DEFINE_TRIVIAL_HASH |
87 | #endif // !defined(OS_ANDROID) |
88 | |
89 | // Implement string hash functions so that strings of various flavors can |
90 | // be used as keys in STL maps and sets. The hash algorithm comes from the |
91 | // GNU C++ library, in <tr1/functional>. It is duplicated here because GCC |
92 | // versions prior to 4.3.2 are unable to compile <tr1/functional> when RTTI |
93 | // is disabled, as it is in our build. |
94 | |
95 | #define DEFINE_STRING_HASH(string_type) \ |
96 | template<> \ |
97 | struct hash<string_type> { \ |
98 | std::size_t operator()(const string_type& s) const { \ |
99 | std::size_t result = 0; \ |
100 | for (string_type::const_iterator i = s.begin(); i != s.end(); ++i) \ |
101 | result = (result * 131) + *i; \ |
102 | return result; \ |
103 | } \ |
104 | } |
105 | |
106 | DEFINE_STRING_HASH(std::string); |
107 | DEFINE_STRING_HASH(butil::string16); |
108 | |
109 | #undef DEFINE_STRING_HASH |
110 | |
111 | } // namespace BUTIL_HASH_NAMESPACE |
112 | |
113 | #else // COMPILER |
114 | #error define BUTIL_HASH_NAMESPACE for your compiler |
115 | #endif // COMPILER |
116 | |
117 | namespace butil { |
118 | using BUTIL_HASH_NAMESPACE::hash_map; |
119 | using BUTIL_HASH_NAMESPACE::hash_multimap; |
120 | using BUTIL_HASH_NAMESPACE::hash_multiset; |
121 | using BUTIL_HASH_NAMESPACE::hash_set; |
122 | |
123 | // Implement hashing for pairs of at-most 32 bit integer values. |
124 | inline std::size_t HashInts32(uint32_t value1, uint32_t value2) { |
125 | uint64_t value1_64 = value1; |
126 | uint64_t hash64 = (value1_64 << 32) | value2; |
127 | return static_cast<size_t>(fmix64(hash64)); |
128 | } |
129 | |
130 | // Implement hashing for pairs of up-to 64-bit integer values. |
131 | // We use the compound integer hash method to produce a 64-bit hash code, by |
132 | // breaking the two 64-bit inputs into 4 32-bit values: |
133 | // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000 |
134 | // Then we reduce our result to 32 bits if required, similar to above. |
135 | inline std::size_t HashInts64(uint64_t value1, uint64_t value2) { |
136 | uint32_t short_random1 = 842304669U; |
137 | uint32_t short_random2 = 619063811U; |
138 | uint32_t short_random3 = 937041849U; |
139 | uint32_t short_random4 = 3309708029U; |
140 | |
141 | uint32_t value1a = static_cast<uint32_t>(value1 & 0xffffffff); |
142 | uint32_t value1b = static_cast<uint32_t>((value1 >> 32) & 0xffffffff); |
143 | uint32_t value2a = static_cast<uint32_t>(value2 & 0xffffffff); |
144 | uint32_t value2b = static_cast<uint32_t>((value2 >> 32) & 0xffffffff); |
145 | |
146 | uint64_t product1 = static_cast<uint64_t>(value1a) * short_random1; |
147 | uint64_t product2 = static_cast<uint64_t>(value1b) * short_random2; |
148 | uint64_t product3 = static_cast<uint64_t>(value2a) * short_random3; |
149 | uint64_t product4 = static_cast<uint64_t>(value2b) * short_random4; |
150 | |
151 | uint64_t hash64 = product1 + product2 + product3 + product4; |
152 | |
153 | if (sizeof(std::size_t) >= sizeof(uint64_t)) |
154 | return static_cast<std::size_t>(hash64); |
155 | |
156 | uint64_t odd_random = 1578233944LL << 32 | 194370989LL; |
157 | uint32_t shift_random = 20591U << 16; |
158 | |
159 | hash64 = hash64 * odd_random + shift_random; |
160 | std::size_t high_bits = static_cast<std::size_t>( |
161 | hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); |
162 | return high_bits; |
163 | } |
164 | |
165 | #define DEFINE_32BIT_PAIR_HASH(Type1, Type2) \ |
166 | inline std::size_t HashPair(Type1 value1, Type2 value2) { \ |
167 | return HashInts32(value1, value2); \ |
168 | } |
169 | |
170 | DEFINE_32BIT_PAIR_HASH(int16_t, int16_t); |
171 | DEFINE_32BIT_PAIR_HASH(int16_t, uint16_t); |
172 | DEFINE_32BIT_PAIR_HASH(int16_t, int32_t); |
173 | DEFINE_32BIT_PAIR_HASH(int16_t, uint32_t); |
174 | DEFINE_32BIT_PAIR_HASH(uint16_t, int16_t); |
175 | DEFINE_32BIT_PAIR_HASH(uint16_t, uint16_t); |
176 | DEFINE_32BIT_PAIR_HASH(uint16_t, int32_t); |
177 | DEFINE_32BIT_PAIR_HASH(uint16_t, uint32_t); |
178 | DEFINE_32BIT_PAIR_HASH(int32_t, int16_t); |
179 | DEFINE_32BIT_PAIR_HASH(int32_t, uint16_t); |
180 | DEFINE_32BIT_PAIR_HASH(int32_t, int32_t); |
181 | DEFINE_32BIT_PAIR_HASH(int32_t, uint32_t); |
182 | DEFINE_32BIT_PAIR_HASH(uint32_t, int16_t); |
183 | DEFINE_32BIT_PAIR_HASH(uint32_t, uint16_t); |
184 | DEFINE_32BIT_PAIR_HASH(uint32_t, int32_t); |
185 | DEFINE_32BIT_PAIR_HASH(uint32_t, uint32_t); |
186 | |
187 | #undef DEFINE_32BIT_PAIR_HASH |
188 | |
189 | #define DEFINE_64BIT_PAIR_HASH(Type1, Type2) \ |
190 | inline std::size_t HashPair(Type1 value1, Type2 value2) { \ |
191 | return HashInts64(value1, value2); \ |
192 | } |
193 | |
194 | DEFINE_64BIT_PAIR_HASH(int16_t, int64_t); |
195 | DEFINE_64BIT_PAIR_HASH(int16_t, uint64_t); |
196 | DEFINE_64BIT_PAIR_HASH(uint16_t, int64_t); |
197 | DEFINE_64BIT_PAIR_HASH(uint16_t, uint64_t); |
198 | DEFINE_64BIT_PAIR_HASH(int32_t, int64_t); |
199 | DEFINE_64BIT_PAIR_HASH(int32_t, uint64_t); |
200 | DEFINE_64BIT_PAIR_HASH(uint32_t, int64_t); |
201 | DEFINE_64BIT_PAIR_HASH(uint32_t, uint64_t); |
202 | DEFINE_64BIT_PAIR_HASH(int64_t, int16_t); |
203 | DEFINE_64BIT_PAIR_HASH(int64_t, uint16_t); |
204 | DEFINE_64BIT_PAIR_HASH(int64_t, int32_t); |
205 | DEFINE_64BIT_PAIR_HASH(int64_t, uint32_t); |
206 | DEFINE_64BIT_PAIR_HASH(int64_t, int64_t); |
207 | DEFINE_64BIT_PAIR_HASH(int64_t, uint64_t); |
208 | DEFINE_64BIT_PAIR_HASH(uint64_t, int16_t); |
209 | DEFINE_64BIT_PAIR_HASH(uint64_t, uint16_t); |
210 | DEFINE_64BIT_PAIR_HASH(uint64_t, int32_t); |
211 | DEFINE_64BIT_PAIR_HASH(uint64_t, uint32_t); |
212 | DEFINE_64BIT_PAIR_HASH(uint64_t, int64_t); |
213 | DEFINE_64BIT_PAIR_HASH(uint64_t, uint64_t); |
214 | |
215 | #undef DEFINE_64BIT_PAIR_HASH |
216 | } // namespace butil |
217 | |
218 | namespace BUTIL_HASH_NAMESPACE { |
219 | |
220 | // Implement methods for hashing a pair of integers, so they can be used as |
221 | // keys in STL containers. |
222 | |
223 | // NOTE(gejun): Specialize ptr as well which is supposed to work with |
224 | // containers by default |
225 | |
226 | #if defined(COMPILER_MSVC) |
227 | |
228 | template<typename Type1, typename Type2> |
229 | inline std::size_t hash_value(const std::pair<Type1, Type2>& value) { |
230 | return butil::HashPair(value.first, value.second); |
231 | } |
232 | template<typename Type> |
233 | inline std::size_t hash_value(Type* ptr) { |
234 | return (uintptr_t)ptr; |
235 | } |
236 | |
237 | #elif defined(COMPILER_GCC) |
238 | template<typename Type1, typename Type2> |
239 | struct hash<std::pair<Type1, Type2> > { |
240 | std::size_t operator()(std::pair<Type1, Type2> value) const { |
241 | return butil::HashPair(value.first, value.second); |
242 | } |
243 | }; |
244 | template<typename Type> |
245 | struct hash<Type*> { |
246 | std::size_t operator()(Type* ptr) const { |
247 | return (uintptr_t)ptr; |
248 | } |
249 | }; |
250 | |
251 | #else |
252 | #error define hash<std::pair<Type1, Type2> > for your compiler |
253 | #endif // COMPILER |
254 | |
255 | } |
256 | |
257 | #undef DEFINE_PAIR_HASH_FUNCTION_START |
258 | #undef DEFINE_PAIR_HASH_FUNCTION_END |
259 | |
260 | #endif // BUTIL_CONTAINERS_HASH_TABLES_H_ |
261 | |