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
67namespace 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
83DEFINE_TRIVIAL_HASH(long long);
84DEFINE_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
106DEFINE_STRING_HASH(std::string);
107DEFINE_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
117namespace butil {
118using BUTIL_HASH_NAMESPACE::hash_map;
119using BUTIL_HASH_NAMESPACE::hash_multimap;
120using BUTIL_HASH_NAMESPACE::hash_multiset;
121using BUTIL_HASH_NAMESPACE::hash_set;
122
123// Implement hashing for pairs of at-most 32 bit integer values.
124inline 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.
135inline 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) \
166inline std::size_t HashPair(Type1 value1, Type2 value2) { \
167 return HashInts32(value1, value2); \
168}
169
170DEFINE_32BIT_PAIR_HASH(int16_t, int16_t);
171DEFINE_32BIT_PAIR_HASH(int16_t, uint16_t);
172DEFINE_32BIT_PAIR_HASH(int16_t, int32_t);
173DEFINE_32BIT_PAIR_HASH(int16_t, uint32_t);
174DEFINE_32BIT_PAIR_HASH(uint16_t, int16_t);
175DEFINE_32BIT_PAIR_HASH(uint16_t, uint16_t);
176DEFINE_32BIT_PAIR_HASH(uint16_t, int32_t);
177DEFINE_32BIT_PAIR_HASH(uint16_t, uint32_t);
178DEFINE_32BIT_PAIR_HASH(int32_t, int16_t);
179DEFINE_32BIT_PAIR_HASH(int32_t, uint16_t);
180DEFINE_32BIT_PAIR_HASH(int32_t, int32_t);
181DEFINE_32BIT_PAIR_HASH(int32_t, uint32_t);
182DEFINE_32BIT_PAIR_HASH(uint32_t, int16_t);
183DEFINE_32BIT_PAIR_HASH(uint32_t, uint16_t);
184DEFINE_32BIT_PAIR_HASH(uint32_t, int32_t);
185DEFINE_32BIT_PAIR_HASH(uint32_t, uint32_t);
186
187#undef DEFINE_32BIT_PAIR_HASH
188
189#define DEFINE_64BIT_PAIR_HASH(Type1, Type2) \
190inline std::size_t HashPair(Type1 value1, Type2 value2) { \
191 return HashInts64(value1, value2); \
192}
193
194DEFINE_64BIT_PAIR_HASH(int16_t, int64_t);
195DEFINE_64BIT_PAIR_HASH(int16_t, uint64_t);
196DEFINE_64BIT_PAIR_HASH(uint16_t, int64_t);
197DEFINE_64BIT_PAIR_HASH(uint16_t, uint64_t);
198DEFINE_64BIT_PAIR_HASH(int32_t, int64_t);
199DEFINE_64BIT_PAIR_HASH(int32_t, uint64_t);
200DEFINE_64BIT_PAIR_HASH(uint32_t, int64_t);
201DEFINE_64BIT_PAIR_HASH(uint32_t, uint64_t);
202DEFINE_64BIT_PAIR_HASH(int64_t, int16_t);
203DEFINE_64BIT_PAIR_HASH(int64_t, uint16_t);
204DEFINE_64BIT_PAIR_HASH(int64_t, int32_t);
205DEFINE_64BIT_PAIR_HASH(int64_t, uint32_t);
206DEFINE_64BIT_PAIR_HASH(int64_t, int64_t);
207DEFINE_64BIT_PAIR_HASH(int64_t, uint64_t);
208DEFINE_64BIT_PAIR_HASH(uint64_t, int16_t);
209DEFINE_64BIT_PAIR_HASH(uint64_t, uint16_t);
210DEFINE_64BIT_PAIR_HASH(uint64_t, int32_t);
211DEFINE_64BIT_PAIR_HASH(uint64_t, uint32_t);
212DEFINE_64BIT_PAIR_HASH(uint64_t, int64_t);
213DEFINE_64BIT_PAIR_HASH(uint64_t, uint64_t);
214
215#undef DEFINE_64BIT_PAIR_HASH
216} // namespace butil
217
218namespace 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
228template<typename Type1, typename Type2>
229inline std::size_t hash_value(const std::pair<Type1, Type2>& value) {
230 return butil::HashPair(value.first, value.second);
231}
232template<typename Type>
233inline std::size_t hash_value(Type* ptr) {
234 return (uintptr_t)ptr;
235}
236
237#elif defined(COMPILER_GCC)
238template<typename Type1, typename Type2>
239struct 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};
244template<typename Type>
245struct 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