src/google/protobuf/stubs/hash.h

   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@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 #include "config.h"
  41
  42 #if defined(HAVE_HASH_MAP) && defined(HAVE_HASH_SET)
  43 #include HASH_MAP_H
  44 #include HASH_SET_H
  45 #else
  46 #define MISSING_HASH
  47 #include <map>
  48 #include <set>
  49 #endif
  50
  51 namespace google {
  52 namespace protobuf {
  53
  54 #ifdef MISSING_HASH
  55
  56 // This system doesn't have hash_map or hash_set.  Emulate them using map and
  57 // set.
  58
  59 // Make hash<T> be the same as less<T>.  Note that everywhere where custom
  60 // hash functions are defined in the protobuf code, they are also defined such
  61 // that they can be used as "less" functions, which is required by MSVC anyway.
  62 template <typename Key>
  63 struct hash {
  64   // Dummy, just to make derivative hash functions compile.
  65   int operator()(const Key& key) {
  66     GOOGLE_LOG(FATAL) << "Should never be called.";
  67     return 0;
  68   }
  69
  70   inline bool operator()(const Key& a, const Key& b) const {
  71     return a < b;
  72   }
  73 };
  74
  75 // Make sure char* is compared by value.
  76 template <>
  77 struct hash<const char*> {
  78   // Dummy, just to make derivative hash functions compile.
  79   int operator()(const char* key) {
  80     GOOGLE_LOG(FATAL) << "Should never be called.";
  81     return 0;
  82   }
  83
  84   inline bool operator()(const char* a, const char* b) const {
  85     return strcmp(a, b) < 0;
  86   }
  87 };
  88
  89 template <typename Key, typename Data,
  90           typename HashFcn = hash<Key>,
  91           typename EqualKey = int >
  92 class hash_map : public std::map<Key, Data, HashFcn> {
  93  public:
  94   hash_map(int = 0) {}
  95 };
  96
  97 template <typename Key,
  98           typename HashFcn = hash<Key>,
  99           typename EqualKey = int >
 100 class hash_set : public std::set<Key, HashFcn> {
 101  public:
 102   hash_set(int = 0) {}
 103 };
 104
 105 #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)
 106
 107 template <typename Key>
 108 struct hash : public HASH_NAMESPACE::hash_compare<Key> {
 109 };
 110
 111 // MSVC's hash_compare<const char*> hashes based on the string contents but
 112 // compares based on the string pointer.  WTF?
 113 class CstringLess {
 114  public:
 115   inline bool operator()(const char* a, const char* b) const {
 116     return strcmp(a, b) < 0;
 117   }
 118 };
 119
 120 template <>
 121 struct hash<const char*>
 122   : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> {
 123 };
 124
 125 template <typename Key, typename Data,
 126           typename HashFcn = hash<Key>,
 127           typename EqualKey = int >
 128 class hash_map : public HASH_NAMESPACE::hash_map<
 129     Key, Data, HashFcn> {
 130  public:
 131   hash_map(int = 0) {}
 132 };
 133
 134 template <typename Key,
 135           typename HashFcn = hash<Key>,
 136           typename EqualKey = int >
 137 class hash_set : public HASH_NAMESPACE::hash_set<
 138     Key, HashFcn> {
 139  public:
 140   hash_set(int = 0) {}
 141 };
 142
 143 #else
 144
 145 template <typename Key>
 146 struct hash : public HASH_NAMESPACE::hash<Key> {
 147 };
 148
 149 template <typename Key>
 150 struct hash<const Key*> {
 151   inline size_t operator()(const Key* key) const {
 152     return reinterpret_cast<size_t>(key);
 153   }
 154 };
 155
 156 // Unlike the old SGI version, the TR1 "hash" does not special-case char*.  So,
 157 // we go ahead and provide our own implementation.
 158 template <>
 159 struct hash<const char*> {
 160   inline size_t operator()(const char* str) const {
 161     size_t result = 0;
 162     for (; *str != '\0'; str++) {
 163       result = 5 * result + *str;
 164     }
 165     return result;
 166   }
 167 };
 168
 169 template <typename Key, typename Data,
 170           typename HashFcn = hash<Key>,
 171           typename EqualKey = std::equal_to<Key> >
 172 class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
 173     Key, Data, HashFcn, EqualKey> {
 174  public:
 175   hash_map(int = 0) {}
 176 };
 177
 178 template <typename Key,
 179           typename HashFcn = hash<Key>,
 180           typename EqualKey = std::equal_to<Key> >
 181 class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
 182     Key, HashFcn, EqualKey> {
 183  public:
 184   hash_set(int = 0) {}
 185 };
 186
 187 #endif
 188
 189 template <>
 190 struct hash<string> {
 191   inline size_t operator()(const string& key) const {
 192     return hash<const char*>()(key.c_str());
 193   }
 194
 195   static const size_t bucket_size = 4;
 196   static const size_t min_buckets = 8;
 197   inline size_t operator()(const string& a, const string& b) const {
 198     return a < b;
 199   }
 200 };
 201
 202 template <typename First, typename Second>
 203 struct hash<pair<First, Second> > {
 204   inline size_t operator()(const pair<First, Second>& key) const {
 205     size_t first_hash = hash<First>()(key.first);
 206     size_t second_hash = hash<Second>()(key.second);
 207
 208     // FIXME(kenton):  What is the best way to compute this hash?  I have
 209     // no idea!  This seems a bit better than an XOR.
 210     return first_hash * ((1 << 16) - 1) + second_hash;
 211   }
 212
 213   static const size_t bucket_size = 4;
 214   static const size_t min_buckets = 8;
 215   inline size_t operator()(const pair<First, Second>& a,
 216                            const pair<First, Second>& b) const {
 217     return a < b;
 218   }
 219 };
 220
 221 // Used by GCC/SGI STL only.  (Why isn't this provided by the standard
 222 // library?  :( )
 223 struct streq {
 224   inline bool operator()(const char* a, const char* b) const {
 225     return strcmp(a, b) == 0;
 226   }
 227 };
 228
 229 }  // namespace protobuf
 230 }  // namespace google
 231
 232 #endif  // GOOGLE_PROTOBUF_STUBS_HASH_H__