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 24 #include <stddef.h> 25 #include <stdint.h> 26 27 #include <utility> 28 29 #include "base/strings/string16.h" 30 #include "build/build_config.h" 31 32 #if defined(COMPILER_MSVC) 33 #include <unordered_map> 34 #include <unordered_set> 35 36 #define BASE_HASH_NAMESPACE std 37 38 #elif defined(COMPILER_GCC) 39 40 #define BASE_HASH_NAMESPACE base_hash 41 42 // This is a hack to disable the gcc 4.4 warning about hash_map and hash_set 43 // being deprecated. We can get rid of this when we upgrade to VS2008 and we 44 // can use <tr1/unordered_map> and <tr1/unordered_set>. 45 #ifdef __DEPRECATED 46 #define CHROME_OLD__DEPRECATED __DEPRECATED 47 #undef __DEPRECATED 48 #endif 49 50 #include <ext/hash_map> 51 #include <ext/hash_set> 52 #define BASE_HASH_IMPL_NAMESPACE __gnu_cxx 53 54 #include <string> 55 56 #ifdef CHROME_OLD__DEPRECATED 57 #define __DEPRECATED CHROME_OLD__DEPRECATED 58 #undef CHROME_OLD__DEPRECATED 59 #endif 60 61 namespace BASE_HASH_NAMESPACE { 62 63 // The pre-standard hash behaves like C++11's std::hash, except around pointers. 64 // const char* is specialized to hash the C string and hash functions for 65 // general T* are missing. Define a BASE_HASH_NAMESPACE::hash which aligns with 66 // the C++11 behavior. 67 68 template<typename T> 69 struct hash { operatorhash70 std::size_t operator()(const T& value) const { 71 return BASE_HASH_IMPL_NAMESPACE::hash<T>()(value); 72 } 73 }; 74 75 template<typename T> 76 struct hash<T*> { 77 std::size_t operator()(T* value) const { 78 return BASE_HASH_IMPL_NAMESPACE::hash<uintptr_t>()( 79 reinterpret_cast<uintptr_t>(value)); 80 } 81 }; 82 83 // The GNU C++ library provides identity hash functions for many integral types, 84 // but not for |long long|. This hash function will truncate if |size_t| is 85 // narrower than |long long|. This is probably good enough for what we will 86 // use it for. 87 88 #define DEFINE_TRIVIAL_HASH(integral_type) \ 89 template<> \ 90 struct hash<integral_type> { \ 91 std::size_t operator()(integral_type value) const { \ 92 return static_cast<std::size_t>(value); \ 93 } \ 94 } 95 96 DEFINE_TRIVIAL_HASH(long long); 97 DEFINE_TRIVIAL_HASH(unsigned long long); 98 99 #undef DEFINE_TRIVIAL_HASH 100 101 // Implement string hash functions so that strings of various flavors can 102 // be used as keys in STL maps and sets. The hash algorithm comes from the 103 // GNU C++ library, in <tr1/functional>. It is duplicated here because GCC 104 // versions prior to 4.3.2 are unable to compile <tr1/functional> when RTTI 105 // is disabled, as it is in our build. 106 107 #define DEFINE_STRING_HASH(string_type) \ 108 template<> \ 109 struct hash<string_type> { \ 110 std::size_t operator()(const string_type& s) const { \ 111 std::size_t result = 0; \ 112 for (string_type::const_iterator i = s.begin(); i != s.end(); ++i) \ 113 result = (result * 131) + *i; \ 114 return result; \ 115 } \ 116 } 117 118 DEFINE_STRING_HASH(std::string); 119 DEFINE_STRING_HASH(base::string16); 120 121 #undef DEFINE_STRING_HASH 122 123 } // namespace BASE_HASH_NAMESPACE 124 125 #else // COMPILER 126 #error define BASE_HASH_NAMESPACE for your compiler 127 #endif // COMPILER 128 129 namespace base { 130 131 // On MSVC, use the C++11 containers. 132 #if defined(COMPILER_MSVC) 133 134 template<class Key, class T, 135 class Hash = std::hash<Key>, 136 class Pred = std::equal_to<Key>, 137 class Alloc = std::allocator<std::pair<const Key, T>>> 138 using hash_map = std::unordered_map<Key, T, Hash, Pred, Alloc>; 139 140 template<class Key, class T, 141 class Hash = std::hash<Key>, 142 class Pred = std::equal_to<Key>, 143 class Alloc = std::allocator<std::pair<const Key, T>>> 144 using hash_multimap = std::unordered_multimap<Key, T, Hash, Pred, Alloc>; 145 146 template<class Key, 147 class Hash = std::hash<Key>, 148 class Pred = std::equal_to<Key>, 149 class Alloc = std::allocator<Key>> 150 using hash_multiset = std::unordered_multiset<Key, Hash, Pred, Alloc>; 151 152 template<class Key, 153 class Hash = std::hash<Key>, 154 class Pred = std::equal_to<Key>, 155 class Alloc = std::allocator<Key>> 156 using hash_set = std::unordered_set<Key, Hash, Pred, Alloc>; 157 158 #else // !COMPILER_MSVC 159 160 // Otherwise, use the pre-standard ones, but override the default hash to match 161 // C++11. 162 template<class Key, class T, 163 class Hash = BASE_HASH_NAMESPACE::hash<Key>, 164 class Pred = std::equal_to<Key>, 165 class Alloc = std::allocator<std::pair<const Key, T>>> 166 using hash_map = BASE_HASH_IMPL_NAMESPACE::hash_map<Key, T, Hash, Pred, Alloc>; 167 168 template<class Key, class T, 169 class Hash = BASE_HASH_NAMESPACE::hash<Key>, 170 class Pred = std::equal_to<Key>, 171 class Alloc = std::allocator<std::pair<const Key, T>>> 172 using hash_multimap = 173 BASE_HASH_IMPL_NAMESPACE::hash_multimap<Key, T, Hash, Pred, Alloc>; 174 175 template<class Key, 176 class Hash = BASE_HASH_NAMESPACE::hash<Key>, 177 class Pred = std::equal_to<Key>, 178 class Alloc = std::allocator<Key>> 179 using hash_multiset = 180 BASE_HASH_IMPL_NAMESPACE::hash_multiset<Key, 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_set = BASE_HASH_IMPL_NAMESPACE::hash_set<Key, Hash, Pred, Alloc>; 187 188 #undef BASE_HASH_IMPL_NAMESPACE 189 190 #endif // COMPILER_MSVC 191 192 // Implement hashing for pairs of at-most 32 bit integer values. 193 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using 194 // multiply-add hashing. This algorithm, as described in 195 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in 196 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: 197 // 198 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 199 // 200 // Contact danakj@chromium.org for any questions. 201 inline std::size_t HashInts32(uint32_t value1, uint32_t value2) { 202 uint64_t value1_64 = value1; 203 uint64_t hash64 = (value1_64 << 32) | value2; 204 205 if (sizeof(std::size_t) >= sizeof(uint64_t)) 206 return static_cast<std::size_t>(hash64); 207 208 uint64_t odd_random = 481046412LL << 32 | 1025306955LL; 209 uint32_t shift_random = 10121U << 16; 210 211 hash64 = hash64 * odd_random + shift_random; 212 std::size_t high_bits = static_cast<std::size_t>( 213 hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); 214 return high_bits; 215 } 216 217 // Implement hashing for pairs of up-to 64-bit integer values. 218 // We use the compound integer hash method to produce a 64-bit hash code, by 219 // breaking the two 64-bit inputs into 4 32-bit values: 220 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000 221 // Then we reduce our result to 32 bits if required, similar to above. 222 inline std::size_t HashInts64(uint64_t value1, uint64_t value2) { 223 uint32_t short_random1 = 842304669U; 224 uint32_t short_random2 = 619063811U; 225 uint32_t short_random3 = 937041849U; 226 uint32_t short_random4 = 3309708029U; 227 228 uint32_t value1a = static_cast<uint32_t>(value1 & 0xffffffff); 229 uint32_t value1b = static_cast<uint32_t>((value1 >> 32) & 0xffffffff); 230 uint32_t value2a = static_cast<uint32_t>(value2 & 0xffffffff); 231 uint32_t value2b = static_cast<uint32_t>((value2 >> 32) & 0xffffffff); 232 233 uint64_t product1 = static_cast<uint64_t>(value1a) * short_random1; 234 uint64_t product2 = static_cast<uint64_t>(value1b) * short_random2; 235 uint64_t product3 = static_cast<uint64_t>(value2a) * short_random3; 236 uint64_t product4 = static_cast<uint64_t>(value2b) * short_random4; 237 238 uint64_t hash64 = product1 + product2 + product3 + product4; 239 240 if (sizeof(std::size_t) >= sizeof(uint64_t)) 241 return static_cast<std::size_t>(hash64); 242 243 uint64_t odd_random = 1578233944LL << 32 | 194370989LL; 244 uint32_t shift_random = 20591U << 16; 245 246 hash64 = hash64 * odd_random + shift_random; 247 std::size_t high_bits = static_cast<std::size_t>( 248 hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t)))); 249 return high_bits; 250 } 251 252 template<typename T1, typename T2> 253 inline std::size_t HashPair(T1 value1, T2 value2) { 254 // This condition is expected to be compile-time evaluated and optimised away 255 // in release builds. 256 if (sizeof(T1) > sizeof(uint32_t) || (sizeof(T2) > sizeof(uint32_t))) 257 return HashInts64(value1, value2); 258 259 return HashInts32(value1, value2); 260 } 261 262 } // namespace base 263 264 namespace BASE_HASH_NAMESPACE { 265 266 // Implement methods for hashing a pair of integers, so they can be used as 267 // keys in STL containers. 268 269 template<typename Type1, typename Type2> 270 struct hash<std::pair<Type1, Type2> > { 271 std::size_t operator()(std::pair<Type1, Type2> value) const { 272 return base::HashPair(value.first, value.second); 273 } 274 }; 275 276 } // namespace BASE_HASH_NAMESPACE 277 278 #undef DEFINE_PAIR_HASH_FUNCTION_START 279 #undef DEFINE_PAIR_HASH_FUNCTION_END 280 281 #endif // BASE_CONTAINERS_HASH_TABLES_H_ 282