« back to all changes in this revision
Viewing changes to drizzled/hash.h
- browse files at revision 1203
- compare with another revision
- download diff
- download tarball
- view history from revision 1203
- Committer: Brian Aker
- Date: 2009-11-02 21:42:57 UTC
- mfrom: (1193.1.2 check-is-test)
- Revision ID: brian@gaz-20091102214257-90sfbusjcibjvxf9
Merge Monty
- files added:
- drizzled/hash.h
- files modified:
- Makefile.am
added
removed
drizzled/hash.h
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
*
4
* Copyright (C) 2009 Sun Microsystems
5
*
6
* This program is free software; you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation; version 2 of the License.
9
*
10
* This program is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU General Public License for more details.
14
*
15
* You should have received a copy of the GNU General Public License
16
* along with this program; if not, write to the Free Software
17
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18
*/
19
20
// Protocol Buffers - Google's data interchange format
21
// Copyright 2008 Google Inc. All rights reserved.
22
// http://code.google.com/p/protobuf/
23
//
24
// Redistribution and use in source and binary forms, with or without
25
// modification, are permitted provided that the following conditions are
26
// met:
27
//
28
// * Redistributions of source code must retain the above copyright
29
// notice, this list of conditions and the following disclaimer.
30
// * Redistributions in binary form must reproduce the above
31
// copyright notice, this list of conditions and the following disclaimer
32
// in the documentation and/or other materials provided with the
33
// distribution.
34
// * Neither the name of Google Inc. nor the names of its
35
// contributors may be used to endorse or promote products derived from
36
// this software without specific prior written permission.
37
//
38
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
39
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
40
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
41
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
42
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
44
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
45
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
46
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
47
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
48
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
49
50
// Author: kenton@google.com (Kenton Varda)
51
//
52
// Deals with the fact that hash_map is not defined everywhere.
53
54
#ifndef DRIZZLED_HASH_H
55
#define DRIZZLED_HASH_H
56
57
#include <cstring>
58
#include <string>
59
60
#if defined(HAVE_HASH_MAP) && defined(HAVE_HASH_SET)
61
#include HASH_MAP_H
62
#include HASH_SET_H
63
#else
64
#define MISSING_HASH
65
#include <map>
66
#include <set>
67
#endif
68
69
namespace drizzled {
70
71
#ifdef MISSING_HASH
72
73
// This system doesn't have hash_map or hash_set. Emulate them using map and
74
// set.
75
76
// Make hash<T> be the same as less<T>. Note that everywhere where custom
77
// hash functions are defined in the protobuf code, they are also defined such
78
// that they can be used as "less" functions, which is required by MSVC anyway.
79
template <typename Key>
80
struct hash {
81
// Dummy, just to make derivative hash functions compile.
82
int operator()(const Key& key) {
83
errmsg_printf("Should never be called.\n");
84
assert(0);
85
return 0;
86
}
87
88
inline bool operator()(const Key& a, const Key& b) const {
89
return a < b;
90
}
91
};
92
93
// Make sure char* is compared by value.
94
template <>
95
struct hash<const char*> {
96
// Dummy, just to make derivative hash functions compile.
97
int operator()(const char* key) {
98
errmsg_printf("Should never be called.\n");
99
assert(0);
100
return 0;
101
}
102
103
inline bool operator()(const char* a, const char* b) const {
104
return strcmp(a, b) < 0;
105
}
106
};
107
108
template <typename Key, typename Data,
109
typename HashFcn = hash<Key>,
110
typename EqualKey = int >
111
class hash_map : public std::map<Key, Data, HashFcn> {
112
};
113
114
template <typename Key,
115
typename HashFcn = hash<Key>,
116
typename EqualKey = int >
117
class hash_set : public std::set<Key, HashFcn> {
118
};
119
120
#elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)
121
122
template <typename Key>
123
struct hash : public HASH_NAMESPACE::hash_compare<Key> {
124
};
125
126
// MSVC's hash_compare<const char*> hashes based on the string contents but
127
// compares based on the string pointer. WTF?
128
class CstringLess {
129
public:
130
inline bool operator()(const char* a, const char* b) const {
131
return strcmp(a, b) < 0;
132
}
133
};
134
135
template <>
136
struct hash<const char*>
137
: public HASH_NAMESPACE::hash_compare<const char*, CstringLess> {
138
};
139
140
template <typename Key, typename Data,
141
typename HashFcn = hash<Key>,
142
typename EqualKey = int >
143
class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
144
Key, Data, HashFcn> {
145
};
146
147
template <typename Key,
148
typename HashFcn = hash<Key>,
149
typename EqualKey = int >
150
class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
151
Key, HashFcn> {
152
};
153
154
#else
155
156
template <typename Key>
157
struct hash : public HASH_NAMESPACE::hash<Key> {
158
};
159
160
template <typename Key>
161
struct hash<const Key*> {
162
inline size_t operator()(const Key* key) const {
163
return reinterpret_cast<size_t>(key);
164
}
165
};
166
167
template <>
168
struct hash<const char*> : public HASH_NAMESPACE::hash<const char*> {
169
};
170
171
template <typename Key, typename Data,
172
typename HashFcn = hash<Key>,
173
typename EqualKey = std::equal_to<Key> >
174
class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
175
Key, Data, HashFcn, EqualKey> {
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
};
184
185
#endif
186
187
#if defined(REDEFINE_HASH_STRING)
188
template <>
189
struct hash<std::string> {
190
inline size_t operator()(const std::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
inline size_t operator()(const std::string& a, const std::string& b) const {
197
return a < b;
198
}
199
};
200
#endif
201
202
template <typename First, typename Second>
203
struct hash<std::pair<First, Second> > {
204
inline size_t operator()(const std::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 std::pair<First, Second>& a,
216
const std::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 drizzled */
230
231
#endif /* DRIZZLED_HASH_H */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1