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