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