base/containers/hash_tables.h

   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 <utility>
  25
  26 #include "base/basictypes.h"
  27 #include "base/strings/string16.h"
  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(base::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;
 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.
 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 >> (8 * (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 >> (8 * (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 }
 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
 206 #define DEFINE_64BIT_PAIR_HASH(Type1, Type2) \
 207 inline std::size_t HashPair(Type1 value1, Type2 value2) { \
 208   return HashInts64(value1, value2); \
 209 }
 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
 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
 259 }
 260
 261 #undef DEFINE_PAIR_HASH_FUNCTION_START
 262 #undef DEFINE_PAIR_HASH_FUNCTION_END
 263
 264 #endif  // BASE_CONTAINERS_HASH_TABLES_H_