Dune Core Modules (2.6.0)

hash.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3#ifndef DUNE_COMMON_HASH_HH
4#define DUNE_COMMON_HASH_HH
5
6#include <functional>
7
9
22// ********************************************************************************
23// Doxygen documentation
24// ********************************************************************************
25
26#ifdef DOXYGEN
27
28namespace Dune {
29
31
36 template<typename T>
37 struct hash
38 {
39
41 std::size_t operator()(const T& t) const
42 {
43 return hash(t);
44 }
45
46 };
47
48}
49
51
98#define DUNE_DEFINE_HASH(template_args,type)
99
100
102
107#define DUNE_HASH_TEMPLATE_ARGS(...)
108
110
115#define DUNE_HASH_TYPE(...)
116
117#else // DOXYGEN - hide all the ugly implementation
118
119
120
121// ********************************************************************************
122// C++11 support
123// ********************************************************************************
124
125// import std::hash into Dune namespace
126namespace Dune {
127
128 using std::hash;
129
130}
131
132// Macro for defining a std::hash specialization for type.
133// This should not be called directly. Call DUNE_DEFINE_HASH
134// instead.
135#define DUNE_DEFINE_STD_HASH(template_args,type) \
136 namespace std { \
137 \
138 template<template_args> \
139 struct hash<type> \
140 { \
141 \
142 typedef type argument_type; \
143 typedef std::size_t result_type; \
144 \
145 std::size_t operator()(const type& arg) const \
146 { \
147 return hash_value(arg); \
148 } \
149 }; \
150 \
151 template<template_args> \
152 struct hash<const type> \
153 { \
154 \
155 typedef type argument_type; \
156 typedef std::size_t result_type; \
157 \
158 std::size_t operator()(const type& arg) const \
159 { \
160 return hash_value(arg); \
161 } \
162 }; \
163 \
164 } \
165
166// Wrapper macro for template arguments.
167// This is required because the template arguments can contain commas,
168// which will create a macro argument list of unknown length. That in itself
169// would not be a problem, but DUNE_DEFINE_HASH has to be called with two argument
170// lists of unknown length. So this macro wraps its arguments with parentheses,
171// turning it into a single argument. The result is used as the parameter list of
172// an expansion macro in the calls to the implementation-specific macros
173// for C++11 and TR1. Noto that technically, this trick is only legal for C++11,
174// but pretty much every compiler supports variadic macros in C++03 mode, as they
175// are part of C99.
176#define DUNE_HASH_TEMPLATE_ARGS(...) (__VA_ARGS__)
177
178// Wrapper macro for type to be hashed.
179// See above for rationale.
180#define DUNE_HASH_TYPE(...) (__VA_ARGS__)
181
182// Expansion macro for the parenthesed argument lists created by
183// DUNE_HASH_TEMPLATE_ARGS and DUNE_HASH_TYPE.
184#define DUNE_HASH_EXPAND_VA_ARGS(...) __VA_ARGS__
185
186// Define specializations for all discovered hash implementations.
187#define DUNE_DEFINE_HASH(template_args,type) \
188 DUNE_DEFINE_STD_HASH(DUNE_HASH_EXPAND_VA_ARGS template_args, DUNE_HASH_EXPAND_VA_ARGS type) \
189
190
191#endif // DOXYGEN
192
193
194
195// ********************************************************************************
196// Some utility functions for combining hashes of member variables.
197// ********************************************************************************
198
199namespace Dune {
200
201 // The following functions are an implementation of the proposed hash extensions for
202 // the C++ standard by Peter Dimov
203 // (cf. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, issue 6.18).
204 // They are also contained in the boost::functional::hash library by Daniel James, but
205 // that implementation uses boost::hash internally, while we want to use Dune::hash. They
206 // are also considered for inclusion in TR2 (then based on std::hash, of course).
207
208#ifndef DOXYGEN
209
210 // helper struct for providing different hash combining algorithms dependent on
211 // the size of size_t.
212 // hash_combiner has to be specialized for the size (in bytes) of std::size_t.
213 // Specialized versions should provide a method
214 //
215 // template <typename typeof_size_t, typename T>
216 // void operator()(typeof_size_t& seed, const T& arg) const;
217 //
218 // that will be called by the interface function hash_combine() described further below.
219 // The redundant template parameter typeof_size_t is needed to avoid warnings for the
220 // unused 64-bit specialization on 32-bit systems.
221 //
222 // There is no default implementation!
223 template<int sizeof_size_t>
224 struct hash_combiner;
225
226
227 // hash combining for 64-bit platforms.
228 template<>
229 struct hash_combiner<8>
230 {
231
232 template<typename typeof_size_t, typename T>
233 void operator()(typeof_size_t& seed, const T& arg) const
234 {
235 static_assert(sizeof(typeof_size_t)==8, "hash_combiner::operator() instantiated with nonmatching type and size");
236
237 // The following algorithm for combining two 64-bit hash values is inspired by a similar
238 // function in CityHash (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.h),
239 // which is in turn based on ideas from the MurmurHash library. The basic idea is easy to
240 // grasp, though: New information is XORed into the existing hash multiple times at different
241 // places (using shift operations), and the resulting pattern is spread over the complete
242 // range of available bits via multiplication with a "magic" constant. The constants used
243 // below (47 and 0x9ddfea08eb382d69ULL) are taken from the CityHash implementation.
244 //
245 // We opted not to use the mixing algorithm proposed in the C++ working group defect list at
246 // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, p. 57f. because it
247 // has very bad hash distribution properties if you apply it to lists of very small numbers,
248 // an application that is frequent in PDELab's ordering framework.
249
250 Dune::hash<T> hasher;
251 const typeof_size_t kMul = 0x9ddfea08eb382d69ULL;
252 typeof_size_t h = hasher(arg);
253 typeof_size_t a = (seed ^ h) * kMul;
254 a ^= (a >> 47);
255 typeof_size_t b = (h ^ a) * kMul;
256 b ^= (b >> 47);
257 b *= kMul;
258 seed = b;
259 }
260
261 };
262
263
264 // hash combining for 32-bit platforms.
265 template<>
266 struct hash_combiner<4>
267 {
268
269 template<typename typeof_size_t, typename T>
270 void operator()(typeof_size_t& seed, const T& arg) const
271 {
272 static_assert(sizeof(typeof_size_t)==4, "hash_combiner::operator() instantiated with nonmatching type and size");
273
274 // The default algorithm above requires a 64-bit std::size_t. The following algorithm is a
275 // 32-bit compatible fallback, again inspired by CityHash and MurmurHash
276 // (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.cc).
277 // It uses 32-bit constants and relies on rotation instead of multiplication to spread the
278 // mixed bits as that is apparently more efficient on IA-32. The constants used below are again
279 // taken from CityHash, in particular from the file referenced above.
280
281 Dune::hash<T> hasher;
282 const typeof_size_t c1 = 0xcc9e2d51;
283 const typeof_size_t c2 = 0x1b873593;
284 const typeof_size_t c3 = 0xe6546b64;
285 typeof_size_t h = hasher(arg);
286 typeof_size_t a = seed * c1;
287 a = (a >> 17) | (a << (32 - 17));
288 a *= c2;
289 h ^= a;
290 h = (h >> 19) | (h << (32 - 19));
291 seed = h * 5 + c3;
292 }
293
294 };
295
296#endif // DOXYGEN
297
299
304 template<typename T>
305 inline void hash_combine(std::size_t& seed, const T& arg)
306 {
307 hash_combiner<sizeof(std::size_t)>()(seed,arg);
308 }
309
311
319 template<typename It>
320 inline std::size_t hash_range(It first, It last)
321 {
322 std::size_t seed = 0;
323 for (; first != last; ++first)
324 {
325 hash_combine(seed,*first);
326 }
327 return seed;
328 }
329
331
338 template<typename It>
339 inline void hash_range(std::size_t& seed, It first, It last)
340 {
341 for (; first != last; ++first)
342 {
343 hash_combine(seed,*first);
344 }
345 }
346
347} // end namespace Dune
348
349#endif // DUNE_COMMON_HASH_HH
Dune namespace.
Definition: alignedallocator.hh:10
std::size_t hash_range(It first, It last)
Hashes all elements in the range [first,last) and returns the combined hash.
Definition: hash.hh:320
void hash_combine(std::size_t &seed, const T &arg)
Calculates the hash value of arg and combines it in-place with seed.
Definition: hash.hh:305
Functor for hashing objects of type T.
Definition: hash.hh:38
std::size_t operator()(const T &t) const
Calculates the hash of t.
Definition: hash.hh:41
Traits for type conversions and type information.
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 24, 23:30, 2024)