← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/hash.h

  • Committer: Brian Aker
  • Date: 2010-04-05 23:46:43 UTC
  • Revision ID: brian@gaz-20100405234643-0he3xnj902rc70r8
Fixing tests to work with PBXT.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
    assert(0);
 
84
    return 0;
 
85
  }
 
86
 
 
87
  inline bool operator()(const Key& a, const Key& b) const {
 
88
    return a < b;
 
89
  }
 
90
};
 
91
 
 
92
// Make sure char* is compared by value.
 
93
template <>
 
94
struct hash<const char*> {
 
95
  // Dummy, just to make derivative hash functions compile.
 
96
  int operator()(const char*) {
 
97
    assert(0);
 
98
    return 0;
 
99
  }
 
100
 
 
101
  inline bool operator()(const char* a, const char* b) const {
 
102
    return strcmp(a, b) < 0;
 
103
  }
 
104
};
 
105
 
 
106
template <typename Key, typename Data,
 
107
          typename HashFcn = hash<Key>,
 
108
          typename EqualKey = int >
 
109
class hash_map : public std::map<Key, Data, HashFcn> {
 
110
 
 
111
  void rehash(size_t buckets_in)
 
112
  {
 
113
    resize(buckets_in);
 
114
  }
 
115
};
 
116
 
 
117
template <typename Key,
 
118
          typename HashFcn = hash<Key>,
 
119
          typename EqualKey = int >
 
120
class hash_set : public std::set<Key, HashFcn> {
 
121
  void rehash(size_t buckets_in)
 
122
  {
 
123
    resize(buckets_in);
 
124
  }
 
125
};
 
126
 
 
127
#elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)
 
128
 
 
129
template <typename Key>
 
130
struct hash : public HASH_NAMESPACE::hash_compare<Key> {
 
131
};
 
132
 
 
133
// MSVC's hash_compare<const char*> hashes based on the string contents but
 
134
// compares based on the string pointer.  WTF?
 
135
class CstringLess {
 
136
 public:
 
137
  inline bool operator()(const char* a, const char* b) const {
 
138
    return strcmp(a, b) < 0;
 
139
  }
 
140
};
 
141
 
 
142
template <>
 
143
struct hash<const char*>
 
144
  : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> {
 
145
};
 
146
 
 
147
template <typename Key, typename Data,
 
148
          typename HashFcn = hash<Key>,
 
149
          typename EqualKey = int >
 
150
class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
 
151
    Key, Data, HashFcn> {
 
152
#if !defined(HASH_MAP_HAS_REHASH)
 
153
public:
 
154
  void rehash(size_t buckets_in)
 
155
  {
 
156
# if defined(HASH_MAP_HAS_RESIZE)
 
157
    resize(buckets_in);
 
158
# endif /* HASH_MAP_HAS_RESIZE */
 
159
  }
 
160
#endif /* HASH_MAP_HAS_REHASH */
 
161
};
 
162
 
 
163
template <typename Key,
 
164
          typename HashFcn = hash<Key>,
 
165
          typename EqualKey = int >
 
166
class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
 
167
    Key, HashFcn> {
 
168
#if !defined(HASH_MAP_HAS_REHASH)
 
169
public:
 
170
  void rehash(size_t buckets_in)
 
171
  {
 
172
# if defined(HASH_MAP_HAS_RESIZE)
 
173
    resize(buckets_in);
 
174
# endif /* HASH_MAP_HAS_RESIZE */
 
175
  }
 
176
#endif /* HASH_MAP_HAS_REHASH */
 
177
};
 
178
 
 
179
#else
 
180
 
 
181
template <typename Key>
 
182
struct hash : public HASH_NAMESPACE::hash<Key> {
 
183
};
 
184
 
 
185
template <typename Key>
 
186
struct hash<const Key*> {
 
187
  inline size_t operator()(const Key* key) const {
 
188
    return reinterpret_cast<size_t>(key);
 
189
  }
 
190
};
 
191
 
 
192
template <>
 
193
struct hash<const char*> : public HASH_NAMESPACE::hash<const char*> {
 
194
};
 
195
 
 
196
template <typename Key, typename Data,
 
197
          typename HashFcn = hash<Key>,
 
198
          typename EqualKey = std::equal_to<Key> >
 
199
class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
 
200
    Key, Data, HashFcn, EqualKey> {
 
201
#if !defined(HASH_MAP_HAS_REHASH)
 
202
public:
 
203
  void rehash(size_t buckets_in)
 
204
  {
 
205
# if defined(HASH_MAP_HAS_RESIZE)
 
206
    HASH_NAMESPACE::HASH_MAP_CLASS<Key, Data, HashFcn, EqualKey>::resize(buckets_in);
 
207
# endif /* HASH_MAP_HAS_RESIZE */
 
208
  }
 
209
#endif /* HASH_MAP_HAS_REHASH */
 
210
};
 
211
 
 
212
template <typename Key,
 
213
          typename HashFcn = hash<Key>,
 
214
          typename EqualKey = std::equal_to<Key> >
 
215
class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
 
216
    Key, HashFcn, EqualKey> {
 
217
#if !defined(HASH_MAP_HAS_REHASH)
 
218
public:
 
219
  void rehash(size_t buckets_in)
 
220
  {
 
221
# if defined(HASH_MAP_HAS_RESIZE)
 
222
    HASH_NAMESPACE::HASH_SET_CLASS<Key, HashFcn, EqualKey>::resize(buckets_in);
 
223
# endif /* HASH_MAP_HAS_RESIZE */
 
224
  }
 
225
#endif /* HASH_MAP_HAS_REHASH */
 
226
};
 
227
 
 
228
#endif
 
229
 
 
230
#if defined(REDEFINE_HASH_STRING)
 
231
template <>
 
232
struct hash<std::string> {
 
233
  inline size_t operator()(const std::string& key) const {
 
234
    return hash<const char*>()(key.c_str());
 
235
  }
 
236
 
 
237
  static const size_t bucket_size = 4;
 
238
  static const size_t min_buckets = 8;
 
239
  inline size_t operator()(const std::string& a, const std::string& b) const {
 
240
    return a < b;
 
241
  }
 
242
};
 
243
#endif
 
244
 
 
245
template <typename First, typename Second>
 
246
struct hash<std::pair<First, Second> > {
 
247
  inline size_t operator()(const std::pair<First, Second>& key) const {
 
248
    size_t first_hash = hash<First>()(key.first);
 
249
    size_t second_hash = hash<Second>()(key.second);
 
250
 
 
251
    // FIXME(kenton):  What is the best way to compute this hash?  I have
 
252
    // no idea!  This seems a bit better than an XOR.
 
253
    return first_hash * ((1 << 16) - 1) + second_hash;
 
254
  }
 
255
 
 
256
  static const size_t bucket_size = 4;
 
257
  static const size_t min_buckets = 8;
 
258
  inline size_t operator()(const std::pair<First, Second>& a,
 
259
                           const std::pair<First, Second>& b) const {
 
260
    return a < b;
 
261
  }
 
262
};
 
263
 
 
264
// Used by GCC/SGI STL only.  (Why isn't this provided by the standard
 
265
// library?  :( )
 
266
struct streq {
 
267
  inline bool operator()(const char* a, const char* b) const {
 
268
    return strcmp(a, b) == 0;
 
269
  }
 
270
};
 
271
 
 
272
}  /* namespace drizzled */
 
273
 
 
274
#endif /* DRIZZLED_HASH_H */