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 public:
94  hash_map(int = 0) {}
95};
96
97template <typename Key,
98          typename HashFcn = hash<Key>,
99          typename EqualKey = int >
100class 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
107template <typename Key>
108struct 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?
113class CstringLess {
114 public:
115  inline bool operator()(const char* a, const char* b) const {
116    return strcmp(a, b) < 0;
117  }
118};
119
120template <>
121struct hash<const char*>
122  : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> {
123};
124
125template <typename Key, typename Data,
126          typename HashFcn = hash<Key>,
127          typename EqualKey = int >
128class hash_map : public HASH_NAMESPACE::hash_map<
129    Key, Data, HashFcn> {
130 public:
131  hash_map(int = 0) {}
132};
133
134template <typename Key,
135          typename HashFcn = hash<Key>,
136          typename EqualKey = int >
137class hash_set : public HASH_NAMESPACE::hash_set<
138    Key, HashFcn> {
139 public:
140  hash_set(int = 0) {}
141};
142
143#else
144
145template <typename Key>
146struct hash : public HASH_NAMESPACE::hash<Key> {
147};
148
149template <typename Key>
150struct 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.
158template <>
159struct 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
169template <typename Key, typename Data,
170          typename HashFcn = hash<Key>,
171          typename EqualKey = std::equal_to<Key> >
172class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
173    Key, Data, HashFcn, EqualKey> {
174 public:
175  hash_map(int = 0) {}
176};
177
178template <typename Key,
179          typename HashFcn = hash<Key>,
180          typename EqualKey = std::equal_to<Key> >
181class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
182    Key, HashFcn, EqualKey> {
183 public:
184  hash_set(int = 0) {}
185};
186
187#endif
188
189template <>
190struct 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
202template <typename First, typename Second>
203struct 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?  :( )
223struct 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