src/google/protobuf/stubs/hash.h - platform/external/protobuf - Git at Google

 // Protocol Buffers - Google's data interchange format
 // Copyright 2008 Google Inc.  All rights reserved.
 // https://developers.google.com/protocol-buffers/
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 // copyright notice, this list of conditions and the following disclaimer
 // in the documentation and/or other materials provided with the
 // distribution.
 //     * Neither the name of Google Inc. nor the names of its
 // contributors may be used to endorse or promote products derived from
 // this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 // Author: [email protected] (Kenton Varda)
 //
 // Deals with the fact that hash_map is not defined everywhere.

 #ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__
 #define GOOGLE_PROTOBUF_STUBS_HASH_H__

 #include <string.h>
 #include <google/protobuf/stubs/common.h>

 #define GOOGLE_PROTOBUF_HAVE_HASH_MAP 1
 #define GOOGLE_PROTOBUF_HAVE_HASH_SET 1

 // Use C++11 unordered_{map|set} if available.
 #if ((defined(_LIBCPP_STD_VER) && _LIBCPP_STD_VER >= 11) || \
     (((__cplusplus >= 201103L) || defined(__GXX_EXPERIMENTAL_CXX0X)) && \
     (__GLIBCXX__ > 20090421)))
 # define GOOGLE_PROTOBUF_HAS_CXX11_HASH

 // For XCode >= 4.6:  the compiler is clang with libc++.
 // For earlier XCode version: the compiler is gcc-4.2.1 with libstdc++.
 // libc++ provides <unordered_map> and friends even in non C++11 mode,
 // and it does not provide the tr1 library. Therefore the following macro
 // checks against this special case.
 // Note that we should not test the __APPLE_CC__ version number or the
 // __clang__ macro, since the new compiler can still use -stdlib=libstdc++, in
 // which case <unordered_map> is not compilable without -std=c++11
 #elif defined(__APPLE_CC__)
 # if __GNUC__ >= 4
 #  define GOOGLE_PROTOBUF_HAS_TR1
 # else
 // Not tested for gcc < 4... These setting can compile under 4.2.1 though.
 #  define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx
 #  include <ext/hash_map>
 #  define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
 #  include <ext/hash_set>
 #  define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
 # endif

 // Version checks for gcc.
 #elif defined(__GNUC__)
 // For GCC 4.x+, use tr1::unordered_map/set; otherwise, follow the
 // instructions from:
 // https://gcc.gnu.org/onlinedocs/libstdc++/manual/backwards.html
 # if __GNUC__ >= 4
 #  define GOOGLE_PROTOBUF_HAS_TR1
 # elif __GNUC__ >= 3
 #  include <backward/hash_map>
 #  define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
 #  include <backward/hash_set>
 #  define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
 #  if __GNUC__ == 3 && __GNUC_MINOR__ == 0
 #   define GOOGLE_PROTOBUF_HASH_NAMESPACE std       // GCC 3.0
 #  else
 #   define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx // GCC 3.1 and later
 #  endif
 # else
 #  define GOOGLE_PROTOBUF_HASH_NAMESPACE
 #  include <hash_map>
 #  define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
 #  include <hash_set>
 #  define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
 # endif

 // GCC <= 4.1 does not define std::tr1::hash for `long long int` or `long long unsigned int`
 # if __GNUC__ == 4 && __GNUC__MINOR__ <= 1
 #  define GOOGLE_PROTOBUF_MISSING_HASH
 #  include <map>
 #  include <set>
 # endif

 // Version checks for MSC.
 // Apparently Microsoft decided to move hash_map *back* to the std namespace in
 // MSVC 2010:
 // http://blogs.msdn.com/vcblog/archive/2009/05/25/stl-breaking-changes-in-visual-studio-2010-beta-1.aspx
 // And.. they are moved back to stdext in MSVC 2013 (haven't checked 2012). That
 // said, use unordered_map for MSVC 2010 and beyond is our safest bet.
 #elif defined(_MSC_VER)
 # if _MSC_VER >= 1600  // Since Visual Studio 2010
 #  define GOOGLE_PROTOBUF_HAS_CXX11_HASH
 #  define GOOGLE_PROTOBUF_HASH_COMPARE std::hash_compare
 # elif _MSC_VER >= 1500  // Since Visual Studio 2008
 #  define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext
 #  include <hash_map>
 #  define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
 #  include <hash_set>
 #  define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
 #  define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
 #  define GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE
 # elif _MSC_VER >= 1310
 #  define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext
 #  include <hash_map>
 #  define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
 #  include <hash_set>
 #  define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
 #  define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
 # else
 #  define GOOGLE_PROTOBUF_HASH_NAMESPACE std
 #  include <hash_map>
 #  define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
 #  include <hash_set>
 #  define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
 #  define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
 # endif

 // **ADD NEW COMPILERS SUPPORT HERE.**
 // For other compilers, undefine the macro and fallback to use std::map, in
 // google/protobuf/stubs/hash.h
 #else
 # undef GOOGLE_PROTOBUF_HAVE_HASH_MAP
 # undef GOOGLE_PROTOBUF_HAVE_HASH_SET
 #endif

 #if defined(GOOGLE_PROTOBUF_HAS_CXX11_HASH)
 # define GOOGLE_PROTOBUF_HASH_NAMESPACE std
 # include <unordered_map>
 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map
 # include <unordered_set>
 # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set
 #elif defined(GOOGLE_PROTOBUF_HAS_TR1)
 # define GOOGLE_PROTOBUF_HASH_NAMESPACE std::tr1
 # include <tr1/unordered_map>
 # define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map
 # include <tr1/unordered_set>
 # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set
 #endif

 # define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \
   namespace google {                                      \
   namespace protobuf {
 # define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END }}

 #undef GOOGLE_PROTOBUF_HAS_CXX11_HASH
 #undef GOOGLE_PROTOBUF_HAS_TR1

 #if defined(GOOGLE_PROTOBUF_HAVE_HASH_MAP) && \
     defined(GOOGLE_PROTOBUF_HAVE_HASH_SET)
 #else
 #define GOOGLE_PROTOBUF_MISSING_HASH
 #include <map>
 #include <set>
 #endif

 namespace google {
 namespace protobuf {

 #ifdef GOOGLE_PROTOBUF_MISSING_HASH
 #undef GOOGLE_PROTOBUF_MISSING_HASH

 // This system doesn't have hash_map or hash_set.  Emulate them using map and
 // set.

 // Make hash<T> be the same as less<T>.  Note that everywhere where custom
 // hash functions are defined in the protobuf code, they are also defined such
 // that they can be used as "less" functions, which is required by MSVC anyway.
 template <typename Key>
 struct hash {
   // Dummy, just to make derivative hash functions compile.
   int operator()(const Key& key) {
     GOOGLE_LOG(FATAL) << "Should never be called.";
     return 0;
   }

   inline bool operator()(const Key& a, const Key& b) const {
     return a < b;
   }
 };

 // Make sure char* is compared by value.
 template <>
 struct hash<const char*> {
   // Dummy, just to make derivative hash functions compile.
   int operator()(const char* key) {
     GOOGLE_LOG(FATAL) << "Should never be called.";
     return 0;
   }

   inline bool operator()(const char* a, const char* b) const {
     return strcmp(a, b) < 0;
   }
 };

 template <typename Key, typename Data,
           typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key>,
           typename Alloc = std::allocator< std::pair<const Key, Data> > >
 class hash_map : public std::map<Key, Data, HashFcn, Alloc> {
   typedef std::map<Key, Data, HashFcn, Alloc> BaseClass;

  public:
   hash_map(int a = 0, const HashFcn& b = HashFcn(),
            const EqualKey& c = EqualKey(),
            const Alloc& d = Alloc()) : BaseClass(b, d) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 template <typename Key,
           typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key> >
 class hash_set : public std::set<Key, HashFcn> {
  public:
   hash_set(int = 0) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)

 template <typename Key>
 struct hash : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> {
 };

 // MSVC's hash_compare<const char*> hashes based on the string contents but
 // compares based on the string pointer.  WTF?
 class CstringLess {
  public:
   inline bool operator()(const char* a, const char* b) const {
     return strcmp(a, b) < 0;
   }
 };

 template <>
 struct hash<const char*>
     : public GOOGLE_PROTOBUF_HASH_COMPARE<const char*, CstringLess> {};

 #ifdef GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE

 template <typename Key, typename HashFcn, typename EqualKey>
 struct InternalHashCompare : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> {
   InternalHashCompare() {}
   InternalHashCompare(HashFcn hashfcn, EqualKey equalkey)
       : hashfcn_(hashfcn), equalkey_(equalkey) {}
   size_t operator()(const Key& key) const { return hashfcn_(key); }
   bool operator()(const Key& key1, const Key& key2) const {
     return !equalkey_(key1, key2);
   }
   HashFcn hashfcn_;
   EqualKey equalkey_;
 };

 template <typename Key, typename Data,
           typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key>,
           typename Alloc = std::allocator< std::pair<const Key, Data> > >
 class hash_map
     : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
           Key, Data, InternalHashCompare<Key, HashFcn, EqualKey>, Alloc> {
   typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
       Key, Data, InternalHashCompare<Key, HashFcn, EqualKey>, Alloc> BaseClass;

  public:
   hash_map(int a = 0, const HashFcn& b = HashFcn(),
            const EqualKey& c = EqualKey(), const Alloc& d = Alloc())
       : BaseClass(InternalHashCompare<Key, HashFcn, EqualKey>(b, c), d) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 template <typename Key, typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key> >
 class hash_set
     : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
           Key, InternalHashCompare<Key, HashFcn, EqualKey> > {
  public:
   hash_set(int = 0) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 #else  // GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE

 template <typename Key, typename Data,
           typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key>,
           typename Alloc = std::allocator< std::pair<const Key, Data> > >
 class hash_map
     : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
           Key, Data, HashFcn, EqualKey, Alloc> {
   typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
       Key, Data, HashFcn, EqualKey, Alloc> BaseClass;

  public:
   hash_map(int a = 0, const HashFcn& b = HashFcn(),
            const EqualKey& c = EqualKey(),
            const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 template <typename Key, typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key> >
 class hash_set
     : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
           Key, HashFcn, EqualKey> {
  public:
   hash_set(int = 0) {}

   HashFcn hash_function() const { return HashFcn(); }
 };
 #endif  // GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE

 #else  // defined(_MSC_VER) && !defined(_STLPORT_VERSION)

 template <typename Key>
 struct hash : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash<Key> {
 };

 template <typename Key>
 struct hash<const Key*> {
   inline size_t operator()(const Key* key) const {
     return reinterpret_cast<size_t>(key);
   }
 };

 // Unlike the old SGI version, the TR1 "hash" does not special-case char*.  So,
 // we go ahead and provide our own implementation.
 template <>
 struct hash<const char*> {
   inline size_t operator()(const char* str) const {
     size_t result = 0;
     for (; *str != '\0'; str++) {
       result = 5 * result + static_cast<size_t>(*str);
     }
     return result;
   }
 };

 template<>
 struct hash<bool> {
   size_t operator()(bool x) const {
     return static_cast<size_t>(x);
   }
 };

 template <typename Key, typename Data,
           typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key>,
           typename Alloc = std::allocator< std::pair<const Key, Data> > >
 class hash_map
     : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
           Key, Data, HashFcn, EqualKey, Alloc> {
   typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
       Key, Data, HashFcn, EqualKey, Alloc> BaseClass;

  public:
   hash_map(int a = 0, const HashFcn& b = HashFcn(),
            const EqualKey& c = EqualKey(),
            const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 template <typename Key, typename HashFcn = hash<Key>,
           typename EqualKey = std::equal_to<Key> >
 class hash_set
     : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
           Key, HashFcn, EqualKey> {
  public:
   hash_set(int = 0) {}

   HashFcn hash_function() const { return HashFcn(); }
 };

 #endif  // !GOOGLE_PROTOBUF_MISSING_HASH

 template <>
 struct hash<string> {
   inline size_t operator()(const string& key) const {
     return hash<const char*>()(key.c_str());
   }

   static const size_t bucket_size = 4;
   static const size_t min_buckets = 8;
   inline bool operator()(const string& a, const string& b) const {
     return a < b;
   }
 };

 template <typename First, typename Second>
 struct hash<pair<First, Second> > {
   inline size_t operator()(const pair<First, Second>& key) const {
     size_t first_hash = hash<First>()(key.first);
     size_t second_hash = hash<Second>()(key.second);

     // FIXME(kenton):  What is the best way to compute this hash?  I have
     // no idea!  This seems a bit better than an XOR.
     return first_hash * ((1 << 16) - 1) + second_hash;
   }

   static const size_t bucket_size = 4;
   static const size_t min_buckets = 8;
   inline bool operator()(const pair<First, Second>& a,
                            const pair<First, Second>& b) const {
     return a < b;
   }
 };

 // Used by GCC/SGI STL only.  (Why isn't this provided by the standard
 // library?  :( )
 struct streq {
   inline bool operator()(const char* a, const char* b) const {
     return strcmp(a, b) == 0;
   }
 };

 }  // namespace protobuf
 }  // namespace google

 #endif  // GOOGLE_PROTOBUF_STUBS_HASH_H__
	// Protocol Buffers - Google's data interchange format
	// Copyright 2008 Google Inc. All rights reserved.
	// https://developers.google.com/protocol-buffers/
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are
	// met:
	//
	// * Redistributions of source code must retain the above copyright
	// notice, this list of conditions and the following disclaimer.
	// * Redistributions in binary form must reproduce the above
	// copyright notice, this list of conditions and the following disclaimer
	// in the documentation and/or other materials provided with the
	// distribution.
	// * Neither the name of Google Inc. nor the names of its
	// contributors may be used to endorse or promote products derived from
	// this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	// Author: [email protected] (Kenton Varda)
	//
	// Deals with the fact that hash_map is not defined everywhere.

	#ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__
	#define GOOGLE_PROTOBUF_STUBS_HASH_H__

	#include <string.h>
	#include <google/protobuf/stubs/common.h>

	#define GOOGLE_PROTOBUF_HAVE_HASH_MAP 1
	#define GOOGLE_PROTOBUF_HAVE_HASH_SET 1

	// Use C++11 unordered_{map\|set} if available.
	#if ((defined(_LIBCPP_STD_VER) && _LIBCPP_STD_VER >= 11) \|\| \
	(((__cplusplus >= 201103L) \|\| defined(__GXX_EXPERIMENTAL_CXX0X)) && \
	(__GLIBCXX__ > 20090421)))
	# define GOOGLE_PROTOBUF_HAS_CXX11_HASH

	// For XCode >= 4.6: the compiler is clang with libc++.
	// For earlier XCode version: the compiler is gcc-4.2.1 with libstdc++.
	// libc++ provides <unordered_map> and friends even in non C++11 mode,
	// and it does not provide the tr1 library. Therefore the following macro
	// checks against this special case.
	// Note that we should not test the __APPLE_CC__ version number or the
	// __clang__ macro, since the new compiler can still use -stdlib=libstdc++, in
	// which case <unordered_map> is not compilable without -std=c++11
	#elif defined(__APPLE_CC__)
	# if __GNUC__ >= 4
	# define GOOGLE_PROTOBUF_HAS_TR1
	# else
	// Not tested for gcc < 4... These setting can compile under 4.2.1 though.
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx
	# include <ext/hash_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
	# include <ext/hash_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
	# endif

	// Version checks for gcc.
	#elif defined(__GNUC__)
	// For GCC 4.x+, use tr1::unordered_map/set; otherwise, follow the
	// instructions from:
	// https://gcc.gnu.org/onlinedocs/libstdc++/manual/backwards.html
	# if __GNUC__ >= 4
	# define GOOGLE_PROTOBUF_HAS_TR1
	# elif __GNUC__ >= 3
	# include <backward/hash_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
	# include <backward/hash_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
	# if __GNUC__ == 3 && __GNUC_MINOR__ == 0
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE std // GCC 3.0
	# else
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx // GCC 3.1 and later
	# endif
	# else
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE
	# include <hash_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
	# include <hash_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
	# endif

	// GCC <= 4.1 does not define std::tr1::hash for `long long int` or `long long unsigned int`
	# if __GNUC__ == 4 && __GNUC__MINOR__ <= 1
	# define GOOGLE_PROTOBUF_MISSING_HASH
	# include <map>
	# include <set>
	# endif

	// Version checks for MSC.
	// Apparently Microsoft decided to move hash_map back to the std namespace in
	// MSVC 2010:
	// http://blogs.msdn.com/vcblog/archive/2009/05/25/stl-breaking-changes-in-visual-studio-2010-beta-1.aspx
	// And.. they are moved back to stdext in MSVC 2013 (haven't checked 2012). That
	// said, use unordered_map for MSVC 2010 and beyond is our safest bet.
	#elif defined(_MSC_VER)
	# if _MSC_VER >= 1600 // Since Visual Studio 2010
	# define GOOGLE_PROTOBUF_HAS_CXX11_HASH
	# define GOOGLE_PROTOBUF_HASH_COMPARE std::hash_compare
	# elif _MSC_VER >= 1500 // Since Visual Studio 2008
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext
	# include <hash_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
	# include <hash_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
	# define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
	# define GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE
	# elif _MSC_VER >= 1310
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext
	# include <hash_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
	# include <hash_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
	# define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
	# else
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE std
	# include <hash_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
	# include <hash_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
	# define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
	# endif

	// ADD NEW COMPILERS SUPPORT HERE.
	// For other compilers, undefine the macro and fallback to use std::map, in
	// google/protobuf/stubs/hash.h
	#else
	# undef GOOGLE_PROTOBUF_HAVE_HASH_MAP
	# undef GOOGLE_PROTOBUF_HAVE_HASH_SET
	#endif

	#if defined(GOOGLE_PROTOBUF_HAS_CXX11_HASH)
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE std
	# include <unordered_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map
	# include <unordered_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set
	#elif defined(GOOGLE_PROTOBUF_HAS_TR1)
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE std::tr1
	# include <tr1/unordered_map>
	# define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map
	# include <tr1/unordered_set>
	# define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set
	#endif

	# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \
	namespace google { \
	namespace protobuf {
	# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END }}

	#undef GOOGLE_PROTOBUF_HAS_CXX11_HASH
	#undef GOOGLE_PROTOBUF_HAS_TR1

	#if defined(GOOGLE_PROTOBUF_HAVE_HASH_MAP) && \
	defined(GOOGLE_PROTOBUF_HAVE_HASH_SET)
	#else
	#define GOOGLE_PROTOBUF_MISSING_HASH
	#include <map>
	#include <set>
	#endif

	namespace google {
	namespace protobuf {

	#ifdef GOOGLE_PROTOBUF_MISSING_HASH
	#undef GOOGLE_PROTOBUF_MISSING_HASH

	// This system doesn't have hash_map or hash_set. Emulate them using map and
	// set.

	// Make hash<T> be the same as less<T>. Note that everywhere where custom
	// hash functions are defined in the protobuf code, they are also defined such
	// that they can be used as "less" functions, which is required by MSVC anyway.
	template <typename Key>
	struct hash {
	// Dummy, just to make derivative hash functions compile.
	int operator()(const Key& key) {
	GOOGLE_LOG(FATAL) << "Should never be called.";
	return 0;
	}

	inline bool operator()(const Key& a, const Key& b) const {
	return a < b;
	}
	};

	// Make sure char* is compared by value.
	template <>
	struct hash<const char*> {
	// Dummy, just to make derivative hash functions compile.
	int operator()(const char* key) {
	GOOGLE_LOG(FATAL) << "Should never be called.";
	return 0;
	}

	inline bool operator()(const char* a, const char* b) const {
	return strcmp(a, b) < 0;
	}
	};

	template <typename Key, typename Data,
	typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key>,
	typename Alloc = std::allocator< std::pair<const Key, Data> > >
	class hash_map : public std::map<Key, Data, HashFcn, Alloc> {
	typedef std::map<Key, Data, HashFcn, Alloc> BaseClass;

	public:
	hash_map(int a = 0, const HashFcn& b = HashFcn(),
	const EqualKey& c = EqualKey(),
	const Alloc& d = Alloc()) : BaseClass(b, d) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	template <typename Key,
	typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key> >
	class hash_set : public std::set<Key, HashFcn> {
	public:
	hash_set(int = 0) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	#elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)

	template <typename Key>
	struct hash : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> {
	};

	// MSVC's hash_compare<const char*> hashes based on the string contents but
	// compares based on the string pointer. WTF?
	class CstringLess {
	public:
	inline bool operator()(const char* a, const char* b) const {
	return strcmp(a, b) < 0;
	}
	};

	template <>
	struct hash<const char*>
	: public GOOGLE_PROTOBUF_HASH_COMPARE<const char*, CstringLess> {};

	#ifdef GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE

	template <typename Key, typename HashFcn, typename EqualKey>
	struct InternalHashCompare : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> {
	InternalHashCompare() {}
	InternalHashCompare(HashFcn hashfcn, EqualKey equalkey)
	: hashfcn_(hashfcn), equalkey_(equalkey) {}
	size_t operator()(const Key& key) const { return hashfcn_(key); }
	bool operator()(const Key& key1, const Key& key2) const {
	return !equalkey_(key1, key2);
	}
	HashFcn hashfcn_;
	EqualKey equalkey_;
	};

	template <typename Key, typename Data,
	typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key>,
	typename Alloc = std::allocator< std::pair<const Key, Data> > >
	class hash_map
	: public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
	Key, Data, InternalHashCompare<Key, HashFcn, EqualKey>, Alloc> {
	typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
	Key, Data, InternalHashCompare<Key, HashFcn, EqualKey>, Alloc> BaseClass;

	public:
	hash_map(int a = 0, const HashFcn& b = HashFcn(),
	const EqualKey& c = EqualKey(), const Alloc& d = Alloc())
	: BaseClass(InternalHashCompare<Key, HashFcn, EqualKey>(b, c), d) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	template <typename Key, typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key> >
	class hash_set
	: public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
	Key, InternalHashCompare<Key, HashFcn, EqualKey> > {
	public:
	hash_set(int = 0) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	#else // GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE

	template <typename Key, typename Data,
	typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key>,
	typename Alloc = std::allocator< std::pair<const Key, Data> > >
	class hash_map
	: public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
	Key, Data, HashFcn, EqualKey, Alloc> {
	typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
	Key, Data, HashFcn, EqualKey, Alloc> BaseClass;

	public:
	hash_map(int a = 0, const HashFcn& b = HashFcn(),
	const EqualKey& c = EqualKey(),
	const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	template <typename Key, typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key> >
	class hash_set
	: public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
	Key, HashFcn, EqualKey> {
	public:
	hash_set(int = 0) {}

	HashFcn hash_function() const { return HashFcn(); }
	};
	#endif // GOOGLE_PROTOBUF_CONTAINERS_NEED_HASH_COMPARE

	#else // defined(_MSC_VER) && !defined(_STLPORT_VERSION)

	template <typename Key>
	struct hash : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash<Key> {
	};

	template <typename Key>
	struct hash<const Key*> {
	inline size_t operator()(const Key* key) const {
	return reinterpret_cast<size_t>(key);
	}
	};

	// Unlike the old SGI version, the TR1 "hash" does not special-case char*. So,
	// we go ahead and provide our own implementation.
	template <>
	struct hash<const char*> {
	inline size_t operator()(const char* str) const {
	size_t result = 0;
	for (; *str != '\0'; str++) {
	result = 5 * result + static_cast<size_t>(*str);
	}
	return result;
	}
	};

	template<>
	struct hash<bool> {
	size_t operator()(bool x) const {
	return static_cast<size_t>(x);
	}
	};

	template <typename Key, typename Data,
	typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key>,
	typename Alloc = std::allocator< std::pair<const Key, Data> > >
	class hash_map
	: public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
	Key, Data, HashFcn, EqualKey, Alloc> {
	typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
	Key, Data, HashFcn, EqualKey, Alloc> BaseClass;

	public:
	hash_map(int a = 0, const HashFcn& b = HashFcn(),
	const EqualKey& c = EqualKey(),
	const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	template <typename Key, typename HashFcn = hash<Key>,
	typename EqualKey = std::equal_to<Key> >
	class hash_set
	: public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
	Key, HashFcn, EqualKey> {
	public:
	hash_set(int = 0) {}

	HashFcn hash_function() const { return HashFcn(); }
	};

	#endif // !GOOGLE_PROTOBUF_MISSING_HASH

	template <>
	struct hash<string> {
	inline size_t operator()(const string& key) const {
	return hash<const char*>()(key.c_str());
	}

	static const size_t bucket_size = 4;
	static const size_t min_buckets = 8;
	inline bool operator()(const string& a, const string& b) const {
	return a < b;
	}
	};

	template <typename First, typename Second>
	struct hash<pair<First, Second> > {
	inline size_t operator()(const pair<First, Second>& key) const {
	size_t first_hash = hash<First>()(key.first);
	size_t second_hash = hash<Second>()(key.second);

	// FIXME(kenton): What is the best way to compute this hash? I have
	// no idea! This seems a bit better than an XOR.
	return first_hash * ((1 << 16) - 1) + second_hash;
	}

	static const size_t bucket_size = 4;
	static const size_t min_buckets = 8;
	inline bool operator()(const pair<First, Second>& a,
	const pair<First, Second>& b) const {
	return a < b;
	}
	};

	// Used by GCC/SGI STL only. (Why isn't this provided by the standard
	// library? :( )
	struct streq {
	inline bool operator()(const char* a, const char* b) const {
	return strcmp(a, b) == 0;
	}
	};

	} // namespace protobuf
	} // namespace google

	#endif // GOOGLE_PROTOBUF_STUBS_HASH_H__