← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/hash.h

  • Committer: Padraig O'Sullivan
  • Date: 2009-09-13 01:03:01 UTC
  • mto: (1126.9.2 captain-20090915-01)
  • mto: This revision was merged to the branch mainline in revision 1133.
  • Revision ID: osullivan.padraig@gmail.com-20090913010301-tcvvezipx1124acy
Added calls to the dtrace delete begin/end probes.

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 */