OsmAnd
|
00001 // Protocol Buffers - Google's data interchange format 00002 // Copyright 2008 Google Inc. All rights reserved. 00003 // http://code.google.com/p/protobuf/ 00004 // 00005 // Redistribution and use in source and binary forms, with or without 00006 // modification, are permitted provided that the following conditions are 00007 // met: 00008 // 00009 // * Redistributions of source code must retain the above copyright 00010 // notice, this list of conditions and the following disclaimer. 00011 // * Redistributions in binary form must reproduce the above 00012 // copyright notice, this list of conditions and the following disclaimer 00013 // in the documentation and/or other materials provided with the 00014 // distribution. 00015 // * Neither the name of Google Inc. nor the names of its 00016 // contributors may be used to endorse or promote products derived from 00017 // this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00020 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00021 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 00022 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 00023 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00024 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00025 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00026 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00027 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00028 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00029 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00030 00031 // Author: kenton@google.com (Kenton Varda) 00032 // 00033 // Deals with the fact that hash_map is not defined everywhere. 00034 00035 #ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__ 00036 #define GOOGLE_PROTOBUF_STUBS_HASH_H__ 00037 00038 #include <string.h> 00039 #include <google/protobuf/stubs/common.h> 00040 #include "config.h" 00041 00042 #if defined(HAVE_HASH_MAP) && defined(HAVE_HASH_SET) 00043 #include HASH_MAP_H 00044 #include HASH_SET_H 00045 #else 00046 #define MISSING_HASH 00047 #include <map> 00048 #include <set> 00049 #endif 00050 00051 namespace google { 00052 namespace protobuf { 00053 00054 #ifdef MISSING_HASH 00055 00056 // This system doesn't have hash_map or hash_set. Emulate them using map and 00057 // set. 00058 00059 // Make hash<T> be the same as less<T>. Note that everywhere where custom 00060 // hash functions are defined in the protobuf code, they are also defined such 00061 // that they can be used as "less" functions, which is required by MSVC anyway. 00062 template <typename Key> 00063 struct hash { 00064 // Dummy, just to make derivative hash functions compile. 00065 int operator()(const Key& key) { 00066 GOOGLE_LOG(FATAL) << "Should never be called."; 00067 return 0; 00068 } 00069 00070 inline bool operator()(const Key& a, const Key& b) const { 00071 return a < b; 00072 } 00073 }; 00074 00075 // Make sure char* is compared by value. 00076 template <> 00077 struct hash<const char*> { 00078 // Dummy, just to make derivative hash functions compile. 00079 int operator()(const char* key) { 00080 GOOGLE_LOG(FATAL) << "Should never be called."; 00081 return 0; 00082 } 00083 00084 inline bool operator()(const char* a, const char* b) const { 00085 return strcmp(a, b) < 0; 00086 } 00087 }; 00088 00089 template <typename Key, typename Data, 00090 typename HashFcn = hash<Key>, 00091 typename EqualKey = int > 00092 class hash_map : public std::map<Key, Data, HashFcn> { 00093 }; 00094 00095 template <typename Key, 00096 typename HashFcn = hash<Key>, 00097 typename EqualKey = int > 00098 class hash_set : public std::set<Key, HashFcn> { 00099 }; 00100 00101 #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION) 00102 00103 template <typename Key> 00104 struct hash : public HASH_NAMESPACE::hash_compare<Key> { 00105 }; 00106 00107 // MSVC's hash_compare<const char*> hashes based on the string contents but 00108 // compares based on the string pointer. WTF? 00109 class CstringLess { 00110 public: 00111 inline bool operator()(const char* a, const char* b) const { 00112 return strcmp(a, b) < 0; 00113 } 00114 }; 00115 00116 template <> 00117 struct hash<const char*> 00118 : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> { 00119 }; 00120 00121 template <typename Key, typename Data, 00122 typename HashFcn = hash<Key>, 00123 typename EqualKey = int > 00124 class hash_map : public HASH_NAMESPACE::hash_map< 00125 Key, Data, HashFcn> { 00126 }; 00127 00128 template <typename Key, 00129 typename HashFcn = hash<Key>, 00130 typename EqualKey = int > 00131 class hash_set : public HASH_NAMESPACE::hash_set< 00132 Key, HashFcn> { 00133 }; 00134 00135 #else 00136 00137 template <typename Key> 00138 struct hash : public HASH_NAMESPACE::hash<Key> { 00139 }; 00140 00141 template <typename Key> 00142 struct hash<const Key*> { 00143 inline size_t operator()(const Key* key) const { 00144 return reinterpret_cast<size_t>(key); 00145 } 00146 }; 00147 00148 // Unlike the old SGI version, the TR1 "hash" does not special-case char*. So, 00149 // we go ahead and provide our own implementation. 00150 template <> 00151 struct hash<const char*> { 00152 inline size_t operator()(const char* str) const { 00153 size_t result = 0; 00154 for (; *str != '\0'; str++) { 00155 result = 5 * result + *str; 00156 } 00157 return result; 00158 } 00159 }; 00160 00161 template <typename Key, typename Data, 00162 typename HashFcn = hash<Key>, 00163 typename EqualKey = std::equal_to<Key> > 00164 class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS< 00165 Key, Data, HashFcn, EqualKey> { 00166 }; 00167 00168 template <typename Key, 00169 typename HashFcn = hash<Key>, 00170 typename EqualKey = std::equal_to<Key> > 00171 class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS< 00172 Key, HashFcn, EqualKey> { 00173 }; 00174 00175 #endif 00176 00177 template <> 00178 struct hash<string> { 00179 inline size_t operator()(const string& key) const { 00180 return hash<const char*>()(key.c_str()); 00181 } 00182 00183 static const size_t bucket_size = 4; 00184 static const size_t min_buckets = 8; 00185 inline size_t operator()(const string& a, const string& b) const { 00186 return a < b; 00187 } 00188 }; 00189 00190 template <typename First, typename Second> 00191 struct hash<pair<First, Second> > { 00192 inline size_t operator()(const pair<First, Second>& key) const { 00193 size_t first_hash = hash<First>()(key.first); 00194 size_t second_hash = hash<Second>()(key.second); 00195 00196 // FIXME(kenton): What is the best way to compute this hash? I have 00197 // no idea! This seems a bit better than an XOR. 00198 return first_hash * ((1 << 16) - 1) + second_hash; 00199 } 00200 00201 static const size_t bucket_size = 4; 00202 static const size_t min_buckets = 8; 00203 inline size_t operator()(const pair<First, Second>& a, 00204 const pair<First, Second>& b) const { 00205 return a < b; 00206 } 00207 }; 00208 00209 // Used by GCC/SGI STL only. (Why isn't this provided by the standard 00210 // library? :( ) 00211 struct streq { 00212 inline bool operator()(const char* a, const char* b) const { 00213 return strcmp(a, b) == 0; 00214 } 00215 }; 00216 00217 } // namespace protobuf 00218 } // namespace google 00219 00220 #endif // GOOGLE_PROTOBUF_STUBS_HASH_H__