Torne (Richard Coles) | 868fa2f | 2013-06-11 10:57:03 +0100 | [diff] [blame] | 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 |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. |
| 20 | |
| 21 | #ifndef BASE_CONTAINERS_HASH_TABLES_H_ |
| 22 | #define BASE_CONTAINERS_HASH_TABLES_H_ |
| 23 | |
Ben Murdoch | eb525c5 | 2013-07-10 11:40:50 +0100 | [diff] [blame] | 24 | #include <utility> |
| 25 | |
| 26 | #include "base/basictypes.h" |
Torne (Richard Coles) | 5e3f23d | 2013-06-11 16:24:11 +0100 | [diff] [blame] | 27 | #include "base/strings/string16.h" |
Torne (Richard Coles) | 868fa2f | 2013-06-11 10:57:03 +0100 | [diff] [blame] | 28 | #include "build/build_config.h" |
| 29 | |
| 30 | #if defined(COMPILER_MSVC) |
| 31 | #include <hash_map> |
| 32 | #include <hash_set> |
| 33 | |
| 34 | #define BASE_HASH_NAMESPACE stdext |
| 35 | |
| 36 | #elif defined(COMPILER_GCC) |
| 37 | #if defined(OS_ANDROID) |
| 38 | #define BASE_HASH_NAMESPACE std |
| 39 | #else |
| 40 | #define BASE_HASH_NAMESPACE __gnu_cxx |
| 41 | #endif |
| 42 | |
| 43 | // 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 |
| 45 | // can use <tr1/unordered_map> and <tr1/unordered_set>. |
| 46 | #ifdef __DEPRECATED |
| 47 | #define CHROME_OLD__DEPRECATED __DEPRECATED |
| 48 | #undef __DEPRECATED |
| 49 | #endif |
| 50 | |
| 51 | #if defined(OS_ANDROID) |
| 52 | #include <hash_map> |
| 53 | #include <hash_set> |
| 54 | #else |
| 55 | #include <ext/hash_map> |
| 56 | #include <ext/hash_set> |
| 57 | #endif |
| 58 | |
| 59 | #include <string> |
| 60 | |
| 61 | #ifdef CHROME_OLD__DEPRECATED |
| 62 | #define __DEPRECATED CHROME_OLD__DEPRECATED |
| 63 | #undef CHROME_OLD__DEPRECATED |
| 64 | #endif |
| 65 | |
| 66 | namespace BASE_HASH_NAMESPACE { |
| 67 | |
| 68 | #if !defined(OS_ANDROID) |
| 69 | // 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 |
| 71 | // narrower than |long long|. This is probably good enough for what we will |
| 72 | // use it for. |
| 73 | |
| 74 | #define DEFINE_TRIVIAL_HASH(integral_type) \ |
| 75 | template<> \ |
| 76 | struct hash<integral_type> { \ |
| 77 | std::size_t operator()(integral_type value) const { \ |
| 78 | return static_cast<std::size_t>(value); \ |
| 79 | } \ |
| 80 | } |
| 81 | |
| 82 | DEFINE_TRIVIAL_HASH(long long); |
| 83 | DEFINE_TRIVIAL_HASH(unsigned long long); |
| 84 | |
| 85 | #undef DEFINE_TRIVIAL_HASH |
| 86 | #endif // !defined(OS_ANDROID) |
| 87 | |
| 88 | // Implement string hash functions so that strings of various flavors can |
| 89 | // be used as keys in STL maps and sets. The hash algorithm comes from the |
| 90 | // GNU C++ library, in <tr1/functional>. It is duplicated here because GCC |
| 91 | // versions prior to 4.3.2 are unable to compile <tr1/functional> when RTTI |
| 92 | // is disabled, as it is in our build. |
| 93 | |
| 94 | #define DEFINE_STRING_HASH(string_type) \ |
| 95 | template<> \ |
| 96 | struct hash<string_type> { \ |
| 97 | std::size_t operator()(const string_type& s) const { \ |
| 98 | std::size_t result = 0; \ |
| 99 | for (string_type::const_iterator i = s.begin(); i != s.end(); ++i) \ |
| 100 | result = (result * 131) + *i; \ |
| 101 | return result; \ |
| 102 | } \ |
| 103 | } |
| 104 | |
| 105 | DEFINE_STRING_HASH(std::string); |
| 106 | DEFINE_STRING_HASH(string16); |
| 107 | |
| 108 | #undef DEFINE_STRING_HASH |
| 109 | |
| 110 | } // namespace BASE_HASH_NAMESPACE |
| 111 | |
| 112 | #else // COMPILER |
| 113 | #error define BASE_HASH_NAMESPACE for your compiler |
| 114 | #endif // COMPILER |
| 115 | |
| 116 | namespace base { |
| 117 | using BASE_HASH_NAMESPACE::hash_map; |
| 118 | using BASE_HASH_NAMESPACE::hash_multimap; |
| 119 | using BASE_HASH_NAMESPACE::hash_multiset; |
| 120 | using BASE_HASH_NAMESPACE::hash_set; |
Ben Murdoch | eb525c5 | 2013-07-10 11:40:50 +0100 | [diff] [blame] | 121 | |
| 122 | // 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 |
| 124 | // multiply-add hashing. This algorithm, as described in |
| 125 | // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in |
| 126 | // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: |
| 127 | // |
| 128 | // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 |
| 129 | // |
| 130 | // Contact danakj@chromium.org for any questions. |
Ben Murdoch | bb1529c | 2013-08-08 10:24:53 +0100 | [diff] [blame^] | 131 | inline std::size_t HashInts32(uint32 value1, uint32 value2) { |
| 132 | uint64 value1_64 = value1; |
| 133 | uint64 hash64 = (value1_64 << 32) | value2; |
| 134 | |
| 135 | if (sizeof(std::size_t) >= sizeof(uint64)) |
| 136 | return static_cast<std::size_t>(hash64); |
| 137 | |
| 138 | uint64 odd_random = 481046412LL << 32 | 1025306955LL; |
| 139 | uint32 shift_random = 10121U << 16; |
| 140 | |
| 141 | hash64 = hash64 * odd_random + shift_random; |
| 142 | std::size_t high_bits = static_cast<std::size_t>( |
| 143 | hash64 >> (sizeof(uint64) - sizeof(std::size_t))); |
| 144 | return high_bits; |
| 145 | } |
| 146 | |
| 147 | // Implement hashing for pairs of up-to 64-bit integer values. |
| 148 | // We use the compound integer hash method to produce a 64-bit hash code, by |
| 149 | // breaking the two 64-bit inputs into 4 32-bit values: |
| 150 | // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000 |
| 151 | // Then we reduce our result to 32 bits if required, similar to above. |
| 152 | inline std::size_t HashInts64(uint64 value1, uint64 value2) { |
| 153 | uint32 short_random1 = 842304669U; |
| 154 | uint32 short_random2 = 619063811U; |
| 155 | uint32 short_random3 = 937041849U; |
| 156 | uint32 short_random4 = 3309708029U; |
| 157 | |
| 158 | uint32 value1a = static_cast<uint32>(value1 & 0xffffffff); |
| 159 | uint32 value1b = static_cast<uint32>((value1 >> 32) & 0xffffffff); |
| 160 | uint32 value2a = static_cast<uint32>(value2 & 0xffffffff); |
| 161 | uint32 value2b = static_cast<uint32>((value2 >> 32) & 0xffffffff); |
| 162 | |
| 163 | uint64 product1 = static_cast<uint64>(value1a) * short_random1; |
| 164 | uint64 product2 = static_cast<uint64>(value1b) * short_random2; |
| 165 | uint64 product3 = static_cast<uint64>(value2a) * short_random3; |
| 166 | uint64 product4 = static_cast<uint64>(value2b) * short_random4; |
| 167 | |
| 168 | uint64 hash64 = product1 + product2 + product3 + product4; |
| 169 | |
| 170 | if (sizeof(std::size_t) >= sizeof(uint64)) |
| 171 | return static_cast<std::size_t>(hash64); |
| 172 | |
| 173 | uint64 odd_random = 1578233944LL << 32 | 194370989LL; |
| 174 | uint32 shift_random = 20591U << 16; |
| 175 | |
| 176 | hash64 = hash64 * odd_random + shift_random; |
| 177 | std::size_t high_bits = static_cast<std::size_t>( |
| 178 | hash64 >> (sizeof(uint64) - sizeof(std::size_t))); |
| 179 | return high_bits; |
| 180 | } |
| 181 | |
| 182 | #define DEFINE_32BIT_PAIR_HASH(Type1, Type2) \ |
| 183 | inline std::size_t HashPair(Type1 value1, Type2 value2) { \ |
| 184 | return HashInts32(value1, value2); \ |
| 185 | } |
Ben Murdoch | eb525c5 | 2013-07-10 11:40:50 +0100 | [diff] [blame] | 186 | |
| 187 | DEFINE_32BIT_PAIR_HASH(int16, int16); |
| 188 | DEFINE_32BIT_PAIR_HASH(int16, uint16); |
| 189 | DEFINE_32BIT_PAIR_HASH(int16, int32); |
| 190 | DEFINE_32BIT_PAIR_HASH(int16, uint32); |
| 191 | DEFINE_32BIT_PAIR_HASH(uint16, int16); |
| 192 | DEFINE_32BIT_PAIR_HASH(uint16, uint16); |
| 193 | DEFINE_32BIT_PAIR_HASH(uint16, int32); |
| 194 | DEFINE_32BIT_PAIR_HASH(uint16, uint32); |
| 195 | DEFINE_32BIT_PAIR_HASH(int32, int16); |
| 196 | DEFINE_32BIT_PAIR_HASH(int32, uint16); |
| 197 | DEFINE_32BIT_PAIR_HASH(int32, int32); |
| 198 | DEFINE_32BIT_PAIR_HASH(int32, uint32); |
| 199 | DEFINE_32BIT_PAIR_HASH(uint32, int16); |
| 200 | DEFINE_32BIT_PAIR_HASH(uint32, uint16); |
| 201 | DEFINE_32BIT_PAIR_HASH(uint32, int32); |
| 202 | DEFINE_32BIT_PAIR_HASH(uint32, uint32); |
| 203 | |
| 204 | #undef DEFINE_32BIT_PAIR_HASH |
| 205 | |
Ben Murdoch | bb1529c | 2013-08-08 10:24:53 +0100 | [diff] [blame^] | 206 | #define DEFINE_64BIT_PAIR_HASH(Type1, Type2) \ |
| 207 | inline std::size_t HashPair(Type1 value1, Type2 value2) { \ |
| 208 | return HashInts64(value1, value2); \ |
| 209 | } |
Ben Murdoch | eb525c5 | 2013-07-10 11:40:50 +0100 | [diff] [blame] | 210 | |
| 211 | DEFINE_64BIT_PAIR_HASH(int16, int64); |
| 212 | DEFINE_64BIT_PAIR_HASH(int16, uint64); |
| 213 | DEFINE_64BIT_PAIR_HASH(uint16, int64); |
| 214 | DEFINE_64BIT_PAIR_HASH(uint16, uint64); |
| 215 | DEFINE_64BIT_PAIR_HASH(int32, int64); |
| 216 | DEFINE_64BIT_PAIR_HASH(int32, uint64); |
| 217 | DEFINE_64BIT_PAIR_HASH(uint32, int64); |
| 218 | DEFINE_64BIT_PAIR_HASH(uint32, uint64); |
| 219 | DEFINE_64BIT_PAIR_HASH(int64, int16); |
| 220 | DEFINE_64BIT_PAIR_HASH(int64, uint16); |
| 221 | DEFINE_64BIT_PAIR_HASH(int64, int32); |
| 222 | DEFINE_64BIT_PAIR_HASH(int64, uint32); |
| 223 | DEFINE_64BIT_PAIR_HASH(int64, int64); |
| 224 | DEFINE_64BIT_PAIR_HASH(int64, uint64); |
| 225 | DEFINE_64BIT_PAIR_HASH(uint64, int16); |
| 226 | DEFINE_64BIT_PAIR_HASH(uint64, uint16); |
| 227 | DEFINE_64BIT_PAIR_HASH(uint64, int32); |
| 228 | DEFINE_64BIT_PAIR_HASH(uint64, uint32); |
| 229 | DEFINE_64BIT_PAIR_HASH(uint64, int64); |
| 230 | DEFINE_64BIT_PAIR_HASH(uint64, uint64); |
| 231 | |
| 232 | #undef DEFINE_64BIT_PAIR_HASH |
Ben Murdoch | bb1529c | 2013-08-08 10:24:53 +0100 | [diff] [blame^] | 233 | } // namespace base |
| 234 | |
| 235 | namespace BASE_HASH_NAMESPACE { |
| 236 | |
| 237 | // Implement methods for hashing a pair of integers, so they can be used as |
| 238 | // keys in STL containers. |
| 239 | |
| 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> |
| 249 | struct hash<std::pair<Type1, Type2> > { |
| 250 | std::size_t operator()(std::pair<Type1, Type2> value) const { |
| 251 | return base::HashPair(value.first, value.second); |
| 252 | } |
| 253 | }; |
| 254 | |
| 255 | #else |
| 256 | #error define hash<std::pair<Type1, Type2> > for your compiler |
| 257 | #endif // COMPILER |
| 258 | |
Ben Murdoch | eb525c5 | 2013-07-10 11:40:50 +0100 | [diff] [blame] | 259 | } |
| 260 | |
| 261 | #undef DEFINE_PAIR_HASH_FUNCTION_START |
| 262 | #undef DEFINE_PAIR_HASH_FUNCTION_END |
| 263 | |
Torne (Richard Coles) | 868fa2f | 2013-06-11 10:57:03 +0100 | [diff] [blame] | 264 | #endif // BASE_CONTAINERS_HASH_TABLES_H_ |