Line data Source code
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 :
41 : #define GOOGLE_PROTOBUF_HAVE_HASH_MAP 1
42 : #define GOOGLE_PROTOBUF_HAVE_HASH_SET 1
43 :
44 : // Use C++11 unordered_{map|set} if available. Otherwise, libc++ always support
45 : // unordered_{map|set}
46 : #if __cplusplus >= 201103L || defined(__GXX_EXPERIMENTAL_CXX0X) || \
47 : defined(_LIBCPP_VERSION)
48 : # define GOOGLE_PROTOBUF_HAS_CXX11_HASH
49 :
50 : // For XCode >= 4.6: the compiler is clang with libc++.
51 : // For earlier XCode version: the compiler is gcc-4.2.1 with libstdc++.
52 : // libc++ provides <unordered_map> and friends even in non C++11 mode,
53 : // and it does not provide the tr1 library. Therefore the following macro
54 : // checks against this special case.
55 : // Note that we should not test the __APPLE_CC__ version number or the
56 : // __clang__ macro, since the new compiler can still use -stdlib=libstdc++, in
57 : // which case <unordered_map> is not compilable without -std=c++11
58 : #elif defined(__APPLE_CC__)
59 : # if __GNUC__ >= 4
60 : # define GOOGLE_PROTOBUF_HAS_TR1
61 : # else
62 : // Not tested for gcc < 4... These setting can compile under 4.2.1 though.
63 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx
64 : # include <ext/hash_map>
65 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
66 : # include <ext/hash_set>
67 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
68 : # endif
69 :
70 : // Version checks for gcc.
71 : #elif defined(__GNUC__)
72 : // For GCC 4.x+, use tr1::unordered_map/set; otherwise, follow the
73 : // instructions from:
74 : // https://gcc.gnu.org/onlinedocs/libstdc++/manual/backwards.html
75 : # if __GNUC__ >= 4
76 : # define GOOGLE_PROTOBUF_HAS_TR1
77 : # elif __GNUC__ >= 3
78 : # include <backward/hash_map>
79 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
80 : # include <backward/hash_set>
81 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
82 : # if __GNUC__ == 3 && __GNUC_MINOR__ == 0
83 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE std // GCC 3.0
84 : # else
85 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE __gnu_cxx // GCC 3.1 and later
86 : # endif
87 : # else
88 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE
89 : # include <hash_map>
90 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
91 : # include <hash_set>
92 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
93 : # endif
94 :
95 : // Version checks for MSC.
96 : // Apparently Microsoft decided to move hash_map *back* to the std namespace in
97 : // MSVC 2010:
98 : // http://blogs.msdn.com/vcblog/archive/2009/05/25/stl-breaking-changes-in-visual-studio-2010-beta-1.aspx
99 : // And.. they are moved back to stdext in MSVC 2013 (haven't checked 2012). That
100 : // said, use unordered_map for MSVC 2010 and beyond is our safest bet.
101 : #elif defined(_MSC_VER)
102 : # if _MSC_VER >= 1600 // Since Visual Studio 2010
103 : # define GOOGLE_PROTOBUF_HAS_CXX11_HASH
104 : # define GOOGLE_PROTOBUF_HASH_COMPARE std::hash_compare
105 : # elif _MSC_VER >= 1500 // Since Visual Studio 2008
106 : # undef GOOGLE_PROTOBUF_HAVE_HASH_MAP
107 : # undef GOOGLE_PROTOBUF_HAVE_HASH_SET
108 : # elif _MSC_VER >= 1310
109 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE stdext
110 : # include <hash_map>
111 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
112 : # include <hash_set>
113 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
114 : # define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
115 : # else
116 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE std
117 : # include <hash_map>
118 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS hash_map
119 : # include <hash_set>
120 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS hash_set
121 : # define GOOGLE_PROTOBUF_HASH_COMPARE stdext::hash_compare
122 : # endif
123 :
124 : // **ADD NEW COMPILERS SUPPORT HERE.**
125 : // For other compilers, undefine the macro and fallback to use std::map, in
126 : // google/protobuf/stubs/hash.h
127 : #else
128 : # undef GOOGLE_PROTOBUF_HAVE_HASH_MAP
129 : # undef GOOGLE_PROTOBUF_HAVE_HASH_SET
130 : #endif
131 :
132 : #if defined(GOOGLE_PROTOBUF_HAS_CXX11_HASH)
133 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE std
134 : # include <unordered_map>
135 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map
136 : # include <unordered_set>
137 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set
138 : #elif defined(GOOGLE_PROTOBUF_HAS_TR1)
139 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE std::tr1
140 : # include <tr1/unordered_map>
141 : # define GOOGLE_PROTOBUF_HASH_MAP_CLASS unordered_map
142 : # include <tr1/unordered_set>
143 : # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set
144 : #endif
145 :
146 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \
147 : namespace google { \
148 : namespace protobuf {
149 : # define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END }}
150 :
151 : #undef GOOGLE_PROTOBUF_HAS_CXX11_HASH
152 : #undef GOOGLE_PROTOBUF_HAS_TR1
153 :
154 : #if defined(GOOGLE_PROTOBUF_HAVE_HASH_MAP) && \
155 : defined(GOOGLE_PROTOBUF_HAVE_HASH_SET)
156 : #else
157 : #define GOOGLE_PROTOBUF_MISSING_HASH
158 : #include <map>
159 : #include <set>
160 : #endif
161 :
162 : namespace google {
163 : namespace protobuf {
164 :
165 : #ifdef GOOGLE_PROTOBUF_MISSING_HASH
166 : #undef GOOGLE_PROTOBUF_MISSING_HASH
167 :
168 : // This system doesn't have hash_map or hash_set. Emulate them using map and
169 : // set.
170 :
171 : // Make hash<T> be the same as less<T>. Note that everywhere where custom
172 : // hash functions are defined in the protobuf code, they are also defined such
173 : // that they can be used as "less" functions, which is required by MSVC anyway.
174 : template <typename Key>
175 : struct hash {
176 : // Dummy, just to make derivative hash functions compile.
177 : int operator()(const Key& key) {
178 : GOOGLE_LOG(FATAL) << "Should never be called.";
179 : return 0;
180 : }
181 :
182 : inline bool operator()(const Key& a, const Key& b) const {
183 : return a < b;
184 : }
185 : };
186 :
187 : // Make sure char* is compared by value.
188 : template <>
189 : struct hash<const char*> {
190 : // Dummy, just to make derivative hash functions compile.
191 : int operator()(const char* key) {
192 : GOOGLE_LOG(FATAL) << "Should never be called.";
193 : return 0;
194 : }
195 :
196 : inline bool operator()(const char* a, const char* b) const {
197 : return strcmp(a, b) < 0;
198 : }
199 : };
200 :
201 : template <typename Key, typename Data,
202 : typename HashFcn = hash<Key>,
203 : typename EqualKey = std::equal_to<Key>,
204 : typename Alloc = std::allocator< std::pair<const Key, Data> > >
205 : class hash_map : public std::map<Key, Data, HashFcn, Alloc> {
206 : typedef std::map<Key, Data, HashFcn, Alloc> BaseClass;
207 :
208 : public:
209 : hash_map(int a = 0, const HashFcn& b = HashFcn(),
210 : const EqualKey& c = EqualKey(),
211 : const Alloc& d = Alloc()) : BaseClass(b, d) {}
212 : };
213 :
214 : template <typename Key,
215 : typename HashFcn = hash<Key>,
216 : typename EqualKey = std::equal_to<Key> >
217 : class hash_set : public std::set<Key, HashFcn> {
218 : public:
219 : hash_set(int = 0) {}
220 : };
221 :
222 : #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)
223 :
224 : template <typename Key>
225 : struct hash : public GOOGLE_PROTOBUF_HASH_COMPARE<Key> {
226 : };
227 :
228 : // MSVC's hash_compare<const char*> hashes based on the string contents but
229 : // compares based on the string pointer. WTF?
230 : class CstringLess {
231 : public:
232 : inline bool operator()(const char* a, const char* b) const {
233 : return strcmp(a, b) < 0;
234 : }
235 : };
236 :
237 : template <>
238 : struct hash<const char*>
239 : : public GOOGLE_PROTOBUF_HASH_COMPARE<const char*, CstringLess> {};
240 :
241 : template <typename Key, typename Data,
242 : typename HashFcn = hash<Key>,
243 : typename EqualKey = std::equal_to<Key>,
244 : typename Alloc = std::allocator< std::pair<const Key, Data> > >
245 : class hash_map
246 : : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
247 : Key, Data, HashFcn, EqualKey, Alloc> {
248 : typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
249 : Key, Data, HashFcn, EqualKey, Alloc> BaseClass;
250 :
251 : public:
252 : hash_map(int a = 0, const HashFcn& b = HashFcn(),
253 : const EqualKey& c = EqualKey(),
254 : const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {}
255 : };
256 :
257 : template <typename Key, typename HashFcn = hash<Key>,
258 : typename EqualKey = std::equal_to<Key> >
259 : class hash_set
260 : : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
261 : Key, HashFcn, EqualKey> {
262 : public:
263 : hash_set(int = 0) {}
264 : };
265 :
266 : #else
267 :
268 : template <typename Key>
269 : struct hash : public GOOGLE_PROTOBUF_HASH_NAMESPACE::hash<Key> {
270 : };
271 :
272 : template <typename Key>
273 : struct hash<const Key*> {
274 : inline size_t operator()(const Key* key) const {
275 2940 : return reinterpret_cast<size_t>(key);
276 : }
277 : };
278 :
279 : // Unlike the old SGI version, the TR1 "hash" does not special-case char*. So,
280 : // we go ahead and provide our own implementation.
281 : template <>
282 : struct hash<const char*> {
283 : inline size_t operator()(const char* str) const {
284 : size_t result = 0;
285 5408737 : for (; *str != '\0'; str++) {
286 5408737 : result = 5 * result + *str;
287 : }
288 : return result;
289 : }
290 : };
291 :
292 : template<>
293 : struct hash<bool> {
294 : size_t operator()(bool x) const {
295 0 : return static_cast<size_t>(x);
296 : }
297 : };
298 :
299 : template <typename Key, typename Data,
300 : typename HashFcn = hash<Key>,
301 : typename EqualKey = std::equal_to<Key>,
302 : typename Alloc = std::allocator< std::pair<const Key, Data> > >
303 2880 : class hash_map
304 : : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
305 : Key, Data, HashFcn, EqualKey, Alloc> {
306 : typedef GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_MAP_CLASS<
307 : Key, Data, HashFcn, EqualKey, Alloc> BaseClass;
308 :
309 : public:
310 : hash_map(int a = 0, const HashFcn& b = HashFcn(),
311 : const EqualKey& c = EqualKey(),
312 3082 : const Alloc& d = Alloc()) : BaseClass(a, b, c, d) {}
313 : };
314 :
315 : template <typename Key, typename HashFcn = hash<Key>,
316 : typename EqualKey = std::equal_to<Key> >
317 1951 : class hash_set
318 : : public GOOGLE_PROTOBUF_HASH_NAMESPACE::GOOGLE_PROTOBUF_HASH_SET_CLASS<
319 : Key, HashFcn, EqualKey> {
320 : public:
321 4076 : hash_set(int = 0) {}
322 : };
323 :
324 : #endif // !GOOGLE_PROTOBUF_MISSING_HASH
325 :
326 : template <>
327 : struct hash<string> {
328 : inline size_t operator()(const string& key) const {
329 77258 : return hash<const char*>()(key.c_str());
330 : }
331 :
332 : static const size_t bucket_size = 4;
333 : static const size_t min_buckets = 8;
334 : inline bool operator()(const string& a, const string& b) const {
335 : return a < b;
336 : }
337 : };
338 :
339 : template <typename First, typename Second>
340 : struct hash<pair<First, Second> > {
341 : inline size_t operator()(const pair<First, Second>& key) const {
342 0 : size_t first_hash = hash<First>()(key.first);
343 0 : size_t second_hash = hash<Second>()(key.second);
344 :
345 : // FIXME(kenton): What is the best way to compute this hash? I have
346 : // no idea! This seems a bit better than an XOR.
347 0 : return first_hash * ((1 << 16) - 1) + second_hash;
348 : }
349 :
350 : static const size_t bucket_size = 4;
351 : static const size_t min_buckets = 8;
352 : inline bool operator()(const pair<First, Second>& a,
353 : const pair<First, Second>& b) const {
354 : return a < b;
355 : }
356 : };
357 :
358 : // Used by GCC/SGI STL only. (Why isn't this provided by the standard
359 : // library? :( )
360 : struct streq {
361 : inline bool operator()(const char* a, const char* b) const {
362 10474 : return strcmp(a, b) == 0;
363 : }
364 : };
365 :
366 : } // namespace protobuf
367 : } // namespace google
368 :
369 : #endif // GOOGLE_PROTOBUF_STUBS_HASH_H__
|
