temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 1 | // Protocol Buffers - Google's data interchange format |
kenton@google.com | 24bf56f | 2008-09-24 20:31:01 +0000 | [diff] [blame] | 2 | // Copyright 2008 Google Inc. All rights reserved. |
Feng Xiao | e428862 | 2014-10-01 16:26:23 -0700 | [diff] [blame] | 3 | // https://developers.google.com/protocol-buffers/ |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 4 | // |
kenton@google.com | 24bf56f | 2008-09-24 20:31:01 +0000 | [diff] [blame] | 5 | // Redistribution and use in source and binary forms, with or without |
| 6 | // modification, are permitted provided that the following conditions are |
| 7 | // met: |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 8 | // |
kenton@google.com | 24bf56f | 2008-09-24 20:31:01 +0000 | [diff] [blame] | 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. |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 18 | // |
kenton@google.com | 24bf56f | 2008-09-24 20:31:01 +0000 | [diff] [blame] | 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. |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 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> |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 40 | #include <google/protobuf/stubs/pbconfig.h> |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 41 | |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 42 | #if defined(GOOGLE_PROTOBUF_HAVE_HASH_MAP) && \ |
| 43 | defined(GOOGLE_PROTOBUF_HAVE_HASH_SET) |
| 44 | #include GOOGLE_PROTOBUF_HASH_MAP_H |
| 45 | #include GOOGLE_PROTOBUF_HASH_SET_H |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 46 | #else |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 47 | #define GOOGLE_PROTOBUF_MISSING_HASH |
kenton@google.com | 4410396 | 2008-09-19 16:53:32 +0000 | [diff] [blame] | 48 | #include <map> |
| 49 | #include <set> |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 50 | #endif |
| 51 | |
| 52 | namespace google { |
| 53 | namespace protobuf { |
| 54 | |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 55 | #ifdef GOOGLE_PROTOBUF_MISSING_HASH |
kenton@google.com | 4410396 | 2008-09-19 16:53:32 +0000 | [diff] [blame] | 56 | |
| 57 | // This system doesn't have hash_map or hash_set. Emulate them using map and |
| 58 | // set. |
| 59 | |
| 60 | // Make hash<T> be the same as less<T>. Note that everywhere where custom |
| 61 | // hash functions are defined in the protobuf code, they are also defined such |
| 62 | // that they can be used as "less" functions, which is required by MSVC anyway. |
| 63 | template <typename Key> |
| 64 | struct hash { |
| 65 | // Dummy, just to make derivative hash functions compile. |
| 66 | int operator()(const Key& key) { |
| 67 | GOOGLE_LOG(FATAL) << "Should never be called."; |
| 68 | return 0; |
| 69 | } |
| 70 | |
| 71 | inline bool operator()(const Key& a, const Key& b) const { |
| 72 | return a < b; |
| 73 | } |
| 74 | }; |
| 75 | |
| 76 | // Make sure char* is compared by value. |
| 77 | template <> |
| 78 | struct hash<const char*> { |
| 79 | // Dummy, just to make derivative hash functions compile. |
| 80 | int operator()(const char* key) { |
| 81 | GOOGLE_LOG(FATAL) << "Should never be called."; |
| 82 | return 0; |
| 83 | } |
| 84 | |
| 85 | inline bool operator()(const char* a, const char* b) const { |
| 86 | return strcmp(a, b) < 0; |
| 87 | } |
| 88 | }; |
| 89 | |
| 90 | template <typename Key, typename Data, |
| 91 | typename HashFcn = hash<Key>, |
| 92 | typename EqualKey = int > |
| 93 | class hash_map : public std::map<Key, Data, HashFcn> { |
xiaofeng@google.com | b55a20f | 2012-09-22 02:40:50 +0000 | [diff] [blame] | 94 | public: |
| 95 | hash_map(int = 0) {} |
kenton@google.com | 4410396 | 2008-09-19 16:53:32 +0000 | [diff] [blame] | 96 | }; |
| 97 | |
| 98 | template <typename Key, |
| 99 | typename HashFcn = hash<Key>, |
| 100 | typename EqualKey = int > |
| 101 | class hash_set : public std::set<Key, HashFcn> { |
xiaofeng@google.com | b55a20f | 2012-09-22 02:40:50 +0000 | [diff] [blame] | 102 | public: |
| 103 | hash_set(int = 0) {} |
kenton@google.com | 4410396 | 2008-09-19 16:53:32 +0000 | [diff] [blame] | 104 | }; |
| 105 | |
kenton@google.com | 3aa7a0d | 2009-08-17 20:34:29 +0000 | [diff] [blame] | 106 | #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION) |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 107 | |
| 108 | template <typename Key> |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 109 | struct hash : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash_compare<Key> { |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 110 | }; |
| 111 | |
| 112 | // MSVC's hash_compare<const char*> hashes based on the string contents but |
| 113 | // compares based on the string pointer. WTF? |
| 114 | class CstringLess { |
| 115 | public: |
| 116 | inline bool operator()(const char* a, const char* b) const { |
| 117 | return strcmp(a, b) < 0; |
| 118 | } |
| 119 | }; |
| 120 | |
| 121 | template <> |
| 122 | struct hash<const char*> |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 123 | : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash_compare< |
| 124 | const char*, CstringLess> {}; |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 125 | |
| 126 | template <typename Key, typename Data, |
| 127 | typename HashFcn = hash<Key>, |
| 128 | typename EqualKey = int > |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 129 | class hash_map : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash_map< |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 130 | Key, Data, HashFcn> { |
xiaofeng@google.com | b55a20f | 2012-09-22 02:40:50 +0000 | [diff] [blame] | 131 | public: |
| 132 | hash_map(int = 0) {} |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 133 | }; |
| 134 | |
| 135 | template <typename Key, |
| 136 | typename HashFcn = hash<Key>, |
| 137 | typename EqualKey = int > |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 138 | class hash_set : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash_set< |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 139 | Key, HashFcn> { |
xiaofeng@google.com | b55a20f | 2012-09-22 02:40:50 +0000 | [diff] [blame] | 140 | public: |
| 141 | hash_set(int = 0) {} |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 142 | }; |
| 143 | |
| 144 | #else |
| 145 | |
| 146 | template <typename Key> |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 147 | struct hash : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash<Key> { |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 148 | }; |
| 149 | |
| 150 | template <typename Key> |
| 151 | struct hash<const Key*> { |
| 152 | inline size_t operator()(const Key* key) const { |
| 153 | return reinterpret_cast<size_t>(key); |
| 154 | } |
| 155 | }; |
| 156 | |
kenton@google.com | ee7e942 | 2009-12-21 18:58:23 +0000 | [diff] [blame] | 157 | // Unlike the old SGI version, the TR1 "hash" does not special-case char*. So, |
| 158 | // we go ahead and provide our own implementation. |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 159 | template <> |
kenton@google.com | ee7e942 | 2009-12-21 18:58:23 +0000 | [diff] [blame] | 160 | struct hash<const char*> { |
| 161 | inline size_t operator()(const char* str) const { |
| 162 | size_t result = 0; |
| 163 | for (; *str != '\0'; str++) { |
| 164 | result = 5 * result + *str; |
| 165 | } |
| 166 | return result; |
| 167 | } |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 168 | }; |
| 169 | |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 170 | template <typename Key, typename Data, typename HashFcn = hash<Key>, |
Jisi Liu | 885b612 | 2015-02-28 14:51:22 -0800 | [diff] [blame^] | 171 | typename EqualKey = std::equal_to<Key>, |
| 172 | typename Alloc = std::allocator< std::pair<const Key, Data> > > |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 173 | class hash_map |
| 174 | : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS< |
Jisi Liu | 885b612 | 2015-02-28 14:51:22 -0800 | [diff] [blame^] | 175 | Key, Data, HashFcn, EqualKey, Alloc> { |
xiaofeng@google.com | b55a20f | 2012-09-22 02:40:50 +0000 | [diff] [blame] | 176 | public: |
Jisi Liu | 885b612 | 2015-02-28 14:51:22 -0800 | [diff] [blame^] | 177 | hash_map(int = 0, const HashFcn& = HashFcn(), const EqualKey& = EqualKey(), |
| 178 | const Alloc& = Alloc()) {} |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 179 | }; |
| 180 | |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 181 | template <typename Key, typename HashFcn = hash<Key>, |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 182 | typename EqualKey = std::equal_to<Key> > |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 183 | class hash_set |
| 184 | : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS< |
| 185 | Key, HashFcn, EqualKey> { |
xiaofeng@google.com | b55a20f | 2012-09-22 02:40:50 +0000 | [diff] [blame] | 186 | public: |
| 187 | hash_set(int = 0) {} |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 188 | }; |
| 189 | |
Jisi Liu | df184fb | 2015-02-25 15:28:44 -0800 | [diff] [blame] | 190 | #undef GOOGLE_PROTOBUF_MISSING_HASH |
| 191 | #endif // !GOOGLE_PROTOBUF_MISSING_HASH |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 192 | |
| 193 | template <> |
| 194 | struct hash<string> { |
| 195 | inline size_t operator()(const string& key) const { |
| 196 | return hash<const char*>()(key.c_str()); |
| 197 | } |
| 198 | |
| 199 | static const size_t bucket_size = 4; |
| 200 | static const size_t min_buckets = 8; |
| 201 | inline size_t operator()(const string& a, const string& b) const { |
| 202 | return a < b; |
| 203 | } |
| 204 | }; |
| 205 | |
kenton@google.com | d37d46d | 2009-04-25 02:53:47 +0000 | [diff] [blame] | 206 | template <typename First, typename Second> |
| 207 | struct hash<pair<First, Second> > { |
| 208 | inline size_t operator()(const pair<First, Second>& key) const { |
| 209 | size_t first_hash = hash<First>()(key.first); |
| 210 | size_t second_hash = hash<Second>()(key.second); |
| 211 | |
| 212 | // FIXME(kenton): What is the best way to compute this hash? I have |
| 213 | // no idea! This seems a bit better than an XOR. |
| 214 | return first_hash * ((1 << 16) - 1) + second_hash; |
| 215 | } |
| 216 | |
| 217 | static const size_t bucket_size = 4; |
| 218 | static const size_t min_buckets = 8; |
| 219 | inline size_t operator()(const pair<First, Second>& a, |
| 220 | const pair<First, Second>& b) const { |
| 221 | return a < b; |
| 222 | } |
| 223 | }; |
| 224 | |
| 225 | // Used by GCC/SGI STL only. (Why isn't this provided by the standard |
| 226 | // library? :( ) |
| 227 | struct streq { |
| 228 | inline bool operator()(const char* a, const char* b) const { |
| 229 | return strcmp(a, b) == 0; |
| 230 | } |
| 231 | }; |
| 232 | |
temporal | 40ee551 | 2008-07-10 02:12:20 +0000 | [diff] [blame] | 233 | } // namespace protobuf |
| 234 | } // namespace google |
| 235 | |
| 236 | #endif // GOOGLE_PROTOBUF_STUBS_HASH_H__ |