1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // http://code.google.com/p/protobuf/ 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 #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 }; 94 95 template <typename Key, 96 typename HashFcn = hash<Key>, 97 typename EqualKey = int > 98 class hash_set : public std::set<Key, HashFcn> { 99 }; 100 101 #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION) 102 103 template <typename Key> 104 struct hash : public HASH_NAMESPACE::hash_compare<Key> { 105 }; 106 107 // MSVC's hash_compare<const char*> hashes based on the string contents but 108 // compares based on the string pointer. WTF? 109 class CstringLess { 110 public: 111 inline bool operator()(const char* a, const char* b) const { 112 return strcmp(a, b) < 0; 113 } 114 }; 115 116 template <> 117 struct hash<const char*> 118 : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> { 119 }; 120 121 template <typename Key, typename Data, 122 typename HashFcn = hash<Key>, 123 typename EqualKey = int > 124 class hash_map : public HASH_NAMESPACE::hash_map< 125 Key, Data, HashFcn> { 126 }; 127 128 template <typename Key, 129 typename HashFcn = hash<Key>, 130 typename EqualKey = int > 131 class hash_set : public HASH_NAMESPACE::hash_set< 132 Key, HashFcn> { 133 }; 134 135 #else 136 137 template <typename Key> 138 struct hash : public HASH_NAMESPACE::hash<Key> { 139 }; 140 141 template <typename Key> 142 struct hash<const Key*> { 143 inline size_t operator()(const Key* key) const { 144 return reinterpret_cast<size_t>(key); 145 } 146 }; 147 148 // Unlike the old SGI version, the TR1 "hash" does not special-case char*. So, 149 // we go ahead and provide our own implementation. 150 template <> 151 struct hash<const char*> { 152 inline size_t operator()(const char* str) const { 153 size_t result = 0; 154 for (; *str != '\0'; str++) { 155 result = 5 * result + *str; 156 } 157 return result; 158 } 159 }; 160 161 template <typename Key, typename Data, 162 typename HashFcn = hash<Key>, 163 typename EqualKey = std::equal_to<Key> > 164 class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS< 165 Key, Data, HashFcn, EqualKey> { 166 }; 167 168 template <typename Key, 169 typename HashFcn = hash<Key>, 170 typename EqualKey = std::equal_to<Key> > 171 class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS< 172 Key, HashFcn, EqualKey> { 173 }; 174 175 #endif 176 177 template <> 178 struct hash<string> { 179 inline size_t operator()(const string& key) const { 180 return hash<const char*>()(key.c_str()); 181 } 182 183 static const size_t bucket_size = 4; 184 static const size_t min_buckets = 8; 185 inline size_t operator()(const string& a, const string& b) const { 186 return a < b; 187 } 188 }; 189 190 template <typename First, typename Second> 191 struct hash<pair<First, Second> > { 192 inline size_t operator()(const pair<First, Second>& key) const { 193 size_t first_hash = hash<First>()(key.first); 194 size_t second_hash = hash<Second>()(key.second); 195 196 // FIXME(kenton): What is the best way to compute this hash? I have 197 // no idea! This seems a bit better than an XOR. 198 return first_hash * ((1 << 16) - 1) + second_hash; 199 } 200 201 static const size_t bucket_size = 4; 202 static const size_t min_buckets = 8; 203 inline size_t operator()(const pair<First, Second>& a, 204 const pair<First, Second>& b) const { 205 return a < b; 206 } 207 }; 208 209 // Used by GCC/SGI STL only. (Why isn't this provided by the standard 210 // library? :( ) 211 struct streq { 212 inline bool operator()(const char* a, const char* b) const { 213 return strcmp(a, b) == 0; 214 } 215 }; 216 217 } // namespace protobuf 218 } // namespace google 219 220 #endif // GOOGLE_PROTOBUF_STUBS_HASH_H__ 221
