1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // https://developers.google.com/protocol-buffers/ 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following disclaimer 13 // in the documentation and/or other materials provided with the 14 // distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived from 17 // this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 // Author: kenton (at) google.com (Kenton Varda) 32 // 33 // Deals with the fact that hash_map is not defined everywhere. 34 35 #ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__ 36 #define GOOGLE_PROTOBUF_STUBS_HASH_H__ 37 38 #include <string.h> 39 #include <google/protobuf/stubs/common.h> 40 41 #define GOOGLE_PROTOBUF_HAVE_HASH_MAP 1 42 #define GOOGLE_PROTOBUF_HAVE_HASH_SET 1 43 44 // Android 45 #if defined(__ANDROID__) 46 # undef GOOGLE_PROTOBUF_HAVE_HASH_MAP 47 # undef GOOGLE_PROTOBUF_HAVE_HASH_MAP 48 49 // Use C++11 unordered_{map|set} if available. 50 #elif ((_LIBCPP_STD_VER >= 11) || \ 51 (((__cplusplus >= 201103L) || defined(__GXX_EXPERIMENTAL_CXX0X)) && \ 52 (__GLIBCXX__ > 20090421))) 53 # define GOOGLE_PROTOBUF_HAS_CXX11_HASH 54 55 // For XCode >= 4.6: the compiler is clang with libc++. 56 // For earlier XCode version: the compiler is gcc-4.2.1 with libstdc++. 57 // libc++ provides <unordered_map> and friends even in non C++11 mode, 58 // and it does not provide the tr1 library. Therefore the following macro 59 // checks against this special case. 60 // Note that we should not test the __APPLE_CC__ version number or the 61 // __clang__ macro, since the new compiler can still use -stdlib=libstdc++, in 62 // which case <unordered_map> is not compilable without -std=c++11 63 #elif defined(__APPLE_CC__) 64 # if __GNUC__ >= 4 65 # define GOOGLE_PROTOBUF_HAS_TR1 66 # else 67 // Not tested for gcc < 4... These setting can compile under 4.2.1 though. 68 # define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx 69 # include <ext/hash_map> 70 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map 71 # include <ext/hash_set> 72 # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set 73 # endif 74 75 // Version checks for gcc. 76 #elif defined(__GNUC__) 77 // For GCC 4.x+, use tr1::unordered_map/set; otherwise, follow the 78 // instructions from: 79 // https://gcc.gnu.org/onlinedocs/libstdc++/manual/backwards.html 80 # if __GNUC__ >= 4 81 # define GOOGLE_PROTOBUF_HAS_TR1 82 # elif __GNUC__ >= 3 83 # include <backward/hash_map> 84 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map 85 # include <backward/hash_set> 86 # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set 87 # if __GNUC__ == 3 && __GNUC_MINOR__ == 0 88 # define GOOGLE_PROTOBUF_HASH_NAMESPACE std // GCC 3.0 89 # else 90 # define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx // GCC 3.1 and later 91 # endif 92 # else 93 # define GOOGLE_PROTOBUF_HASH_NAMESPACE 94 # include <hash_map> 95 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map 96 # include <hash_set> 97 # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set 98 # endif 99 100 // Version checks for MSC. 101 // Apparently Microsoft decided to move hash_map *back* to the std namespace in 102 // MSVC 2010: 103 // http://blogs.msdn.com/vcblog/archive/2009/05/25/stl-breaking-changes-in-visual-studio-2010-beta-1.aspx 104 // And.. they are moved back to stdext in MSVC 2013 (haven't checked 2012). That 105 // said, use unordered_map for MSVC 2010 and beyond is our safest bet. 106 #elif defined(_MSC_VER) 107 # if _MSC_VER >= 1600 // Since Visual Studio 2010 108 # define GOOGLE_PROTOBUF_HAS_CXX11_HASH 109 # define GOOGLE_PROTOBUF_HASH_COMPARE std::hash_compare 110 # elif _MSC_VER >= 1500 // Since Visual Studio 2008 111 # define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext 112 # include <hash_map> 113 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map 114 # include <hash_set> 115 # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set 116 # define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare 117 # define GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE 118 # elif _MSC_VER >= 1310 119 # define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext 120 # include <hash_map> 121 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map 122 # include <hash_set> 123 # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set 124 # define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare 125 # else 126 # define GOOGLE_PROTOBUF_HASH_NAMESPACE std 127 # include <hash_map> 128 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map 129 # include <hash_set> 130 # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set 131 # define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare 132 # endif 133 134 // **ADD NEW COMPILERS SUPPORT HERE.** 135 // For other compilers, undefine the macro and fallback to use std::map, in 136 // google/protobuf/stubs/hash.h 137 #else 138 # undef GOOGLE_PROTOBUF_HAVE_HASH_MAP 139 # undef GOOGLE_PROTOBUF_HAVE_HASH_SET 140 #endif 141 142 #if defined(GOOGLE_PROTOBUF_HAS_CXX11_HASH) 143 # define GOOGLE_PROTOBUF_HASH_NAMESPACE std 144 # include <unordered_map> 145 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map 146 # include <unordered_set> 147 # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set 148 #elif defined(GOOGLE_PROTOBUF_HAS_TR1) 149 # define GOOGLE_PROTOBUF_HASH_NAMESPACE std::tr1 150 # include <tr1/unordered_map> 151 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map 152 # include <tr1/unordered_set> 153 # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set 154 #endif 155 156 # define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \ 157 namespace google { \ 158 namespace protobuf { 159 # define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END }} 160 161 #undef GOOGLE_PROTOBUF_HAS_CXX11_HASH 162 #undef GOOGLE_PROTOBUF_HAS_TR1 163 164 #if defined(GOOGLE_PROTOBUF_HAVE_HASH_MAP) && \ 165 defined(GOOGLE_PROTOBUF_HAVE_HASH_SET) 166 #else 167 #define GOOGLE_PROTOBUF_MISSING_HASH 168 #include <map> 169 #include <set> 170 #endif 171 172 namespace google { 173 namespace protobuf { 174 175 #ifdef GOOGLE_PROTOBUF_MISSING_HASH 176 #undef GOOGLE_PROTOBUF_MISSING_HASH 177 178 // This system doesn't have hash_map or hash_set. Emulate them using map and 179 // set. 180 181 // Make hash<T> be the same as less<T>. Note that everywhere where custom 182 // hash functions are defined in the protobuf code, they are also defined such 183 // that they can be used as "less" functions, which is required by MSVC anyway. 184 template <typename Key> 185 struct hash { 186 // Dummy, just to make derivative hash functions compile. 187 int operator()(const Key& key) { 188 GOOGLE_LOG(FATAL) << "Should never be called."; 189 return 0; 190 } 191 192 inline bool operator()(const Key& a, const Key& b) const { 193 return a < b; 194 } 195 }; 196 197 // Make sure char* is compared by value. 198 template <> 199 struct hash<const char*> { 200 // Dummy, just to make derivative hash functions compile. 201 int operator()(const char* key) { 202 GOOGLE_LOG(FATAL) << "Should never be called."; 203 return 0; 204 } 205 206 inline bool operator()(const char* a, const char* b) const { 207 return strcmp(a, b) < 0; 208 } 209 }; 210 211 template <typename Key, typename Data, 212 typename HashFcn = hash<Key>, 213 typename EqualKey = std::equal_to<Key>, 214 typename Alloc = std::allocator< std::pair<const Key, Data> > > 215 class hash_map : public std::map<Key, Data, HashFcn, Alloc> { 216 typedef std::map<Key, Data, HashFcn, Alloc> BaseClass; 217 218 public: 219 hash_map(int a = 0, const HashFcn& b = HashFcn(), 220 const EqualKey& c = EqualKey(), 221 const Alloc& d = Alloc()) : BaseClass(b, d) {} 222 223 HashFcn hash_function() const { return HashFcn(); } 224 }; 225 226 template <typename Key, 227 typename HashFcn = hash<Key>, 228 typename EqualKey = std::equal_to<Key> > 229 class hash_set : public std::set<Key, HashFcn> { 230 public: 231 hash_set(int = 0) {} 232 233 HashFcn hash_function() const { return HashFcn(); } 234 }; 235 236 #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION) 237 238 template <typename Key> 239 struct hash : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> { 240 }; 241 242 // MSVC's hash_compare<const char*> hashes based on the string contents but 243 // compares based on the string pointer. WTF? 244 class CstringLess { 245 public: 246 inline bool operator()(const char* a, const char* b) const { 247 return strcmp(a, b) < 0; 248 } 249 }; 250 251 template <> 252 struct hash<const char*> 253 : public GOOGLE_PROTOBUF_HASH_COMPARE<const char*, CstringLess> {}; 254 255 #ifdef GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE 256 257 template <typename Key, typename HashFcn, typename EqualKey> 258 struct InternalHashCompare : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> { 259 InternalHashCompare() {} 260 InternalHashCompare(HashFcn hashfcn, EqualKey equalkey) 261 : hashfcn_(hashfcn), equalkey_(equalkey) {} 262 size_t operator()(const Key& key) const { return hashfcn_(key); } 263 bool operator()(const Key& key1, const Key& key2) const { 264 return !equalkey_(key1, key2); 265 } 266 HashFcn hashfcn_; 267 EqualKey equalkey_; 268 }; 269 270 template <typename Key, typename Data, 271 typename HashFcn = hash<Key>, 272 typename EqualKey = std::equal_to<Key>, 273 typename Alloc = std::allocator< std::pair<const Key, Data> > > 274 class hash_map 275 : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< 276 Key, Data, InternalHashCompare<Key, HashFcn, EqualKey>, Alloc> { 277 typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< 278 Key, Data, InternalHashCompare<Key, HashFcn, EqualKey>, Alloc> BaseClass; 279 280 public: 281 hash_map(int a = 0, const HashFcn& b = HashFcn(), 282 const EqualKey& c = EqualKey(), const Alloc& d = Alloc()) 283 : BaseClass(InternalHashCompare<Key, HashFcn, EqualKey>(b, c), d) {} 284 285 HashFcn hash_function() const { return HashFcn(); } 286 }; 287 288 template <typename Key, typename HashFcn = hash<Key>, 289 typename EqualKey = std::equal_to<Key> > 290 class hash_set 291 : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS< 292 Key, InternalHashCompare<Key, HashFcn, EqualKey> > { 293 public: 294 hash_set(int = 0) {} 295 296 HashFcn hash_function() const { return HashFcn(); } 297 }; 298 299 #else // GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE 300 301 template <typename Key, typename Data, 302 typename HashFcn = hash<Key>, 303 typename EqualKey = std::equal_to<Key>, 304 typename Alloc = std::allocator< std::pair<const Key, Data> > > 305 class hash_map 306 : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< 307 Key, Data, HashFcn, EqualKey, Alloc> { 308 typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< 309 Key, Data, HashFcn, EqualKey, Alloc> BaseClass; 310 311 public: 312 hash_map(int a = 0, const HashFcn& b = HashFcn(), 313 const EqualKey& c = EqualKey(), 314 const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {} 315 316 HashFcn hash_function() const { return HashFcn(); } 317 }; 318 319 template <typename Key, typename HashFcn = hash<Key>, 320 typename EqualKey = std::equal_to<Key> > 321 class hash_set 322 : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS< 323 Key, HashFcn, EqualKey> { 324 public: 325 hash_set(int = 0) {} 326 327 HashFcn hash_function() const { return HashFcn(); } 328 }; 329 #endif // GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE 330 331 #else // defined(_MSC_VER) && !defined(_STLPORT_VERSION) 332 333 template <typename Key> 334 struct hash : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash<Key> { 335 }; 336 337 template <typename Key> 338 struct hash<const Key*> { 339 inline size_t operator()(const Key* key) const { 340 return reinterpret_cast<size_t>(key); 341 } 342 }; 343 344 // Unlike the old SGI version, the TR1 "hash" does not special-case char*. So, 345 // we go ahead and provide our own implementation. 346 template <> 347 struct hash<const char*> { 348 inline size_t operator()(const char* str) const { 349 size_t result = 0; 350 for (; *str != '\0'; str++) { 351 result = 5 * result + *str; 352 } 353 return result; 354 } 355 }; 356 357 template<> 358 struct hash<bool> { 359 size_t operator()(bool x) const { 360 return static_cast<size_t>(x); 361 } 362 }; 363 364 template <typename Key, typename Data, 365 typename HashFcn = hash<Key>, 366 typename EqualKey = std::equal_to<Key>, 367 typename Alloc = std::allocator< std::pair<const Key, Data> > > 368 class hash_map 369 : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< 370 Key, Data, HashFcn, EqualKey, Alloc> { 371 typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< 372 Key, Data, HashFcn, EqualKey, Alloc> BaseClass; 373 374 public: 375 hash_map(int a = 0, const HashFcn& b = HashFcn(), 376 const EqualKey& c = EqualKey(), 377 const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {} 378 379 HashFcn hash_function() const { return HashFcn(); } 380 }; 381 382 template <typename Key, typename HashFcn = hash<Key>, 383 typename EqualKey = std::equal_to<Key> > 384 class hash_set 385 : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS< 386 Key, HashFcn, EqualKey> { 387 public: 388 hash_set(int = 0) {} 389 390 HashFcn hash_function() const { return HashFcn(); } 391 }; 392 393 #endif // !GOOGLE_PROTOBUF_MISSING_HASH 394 395 template <> 396 struct hash<string> { 397 inline size_t operator()(const string& key) const { 398 return hash<const char*>()(key.c_str()); 399 } 400 401 static const size_t bucket_size = 4; 402 static const size_t min_buckets = 8; 403 inline bool operator()(const string& a, const string& b) const { 404 return a < b; 405 } 406 }; 407 408 template <typename First, typename Second> 409 struct hash<pair<First, Second> > { 410 inline size_t operator()(const pair<First, Second>& key) const { 411 size_t first_hash = hash<First>()(key.first); 412 size_t second_hash = hash<Second>()(key.second); 413 414 // FIXME(kenton): What is the best way to compute this hash? I have 415 // no idea! This seems a bit better than an XOR. 416 return first_hash * ((1 << 16) - 1) + second_hash; 417 } 418 419 static const size_t bucket_size = 4; 420 static const size_t min_buckets = 8; 421 inline bool operator()(const pair<First, Second>& a, 422 const pair<First, Second>& b) const { 423 return a < b; 424 } 425 }; 426 427 // Used by GCC/SGI STL only. (Why isn't this provided by the standard 428 // library? :( ) 429 struct streq { 430 inline bool operator()(const char* a, const char* b) const { 431 return strcmp(a, b) == 0; 432 } 433 }; 434 435 } // namespace protobuf 436 } // namespace google 437 438 #endif // GOOGLE_PROTOBUF_STUBS_HASH_H__ 439
