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