dune-common  2.3.1
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 
8 
9 #if HAVE_STD_HASH
10 #include <functional>
11 #endif
12 
13 #if HAVE_TR1_HASH
14 #include <tr1/functional>
15 #endif
16 
17 #if HAVE_DUNE_BOOST
18 
19 #include <boost/version.hpp>
20 
21 // Boost 1.34.0 seems to be the first usable version of boost::functional::hash
22 #if BOOST_VERSION >= 103400
23 #define HAVE_BOOST_HASH 1
24 
25 // only pull in boost if really necessary
26 #if !HAVE_STD_HASH && !HAVE_TR1_HASH
27 
28 #include <boost/functional/hash.hpp>
29 
30 #endif // !HAVE_STD_HASH && !HAVE_TR1_HASH
31 #endif // BOOST_VERSION >= 103400
32 #endif // HAVE_DUNE_BOOST
33 
46 // ********************************************************************************
47 // Doxygen documentation
48 // ********************************************************************************
49 
50 #ifdef DOXYGEN
51 
52 namespace Dune {
53 
55 
64  template<typename T>
65  struct hash
66  {
67 
69  std::size_t operator()(const T& t) const
70  {
71  return hash(t);
72  }
73 
74  };
75 
76 }
77 
79 
126 #define DUNE_DEFINE_HASH(template_args,type)
127 
128 
130 
135 #define DUNE_HASH_TEMPLATE_ARGS(...)
136 
138 
143 #define DUNE_HASH_TYPE(...)
144 
145 #else // DOXYGEN - hide all the ugly implementation
146 
147 
148 
149 // ********************************************************************************
150 // C++11 support
151 // ********************************************************************************
152 
153 #if HAVE_STD_HASH
154 // We have std::hash from C++11
155 
156 // Announce that we provide Dune::hash
157 #define HAVE_DUNE_HASH 1
158 
159 // import std::hash into Dune namespace
160 namespace Dune {
161 
162  using std::hash;
163 
164 }
165 
166 // Macro for defining a std::hash specialization for type.
167 // This should not be called directly. Call DUNE_DEFINE_HASH
168 // instead.
169 #define DUNE_DEFINE_STD_HASH(template_args,type) \
170  namespace std { \
171  \
172  template<template_args> \
173  struct hash<type> \
174  { \
175  std::size_t operator()(const type& arg) const \
176  { \
177  return hash_value(arg); \
178  } \
179  }; \
180  \
181  } \
182 
183 #else // HAVE_STD_HASH
184 
185 // We do not support std::hash, so don't do anything here.
186 #define DUNE_DEFINE_STD_HASH(template_args,type)
187 
188 #endif // HAVE_STD_HASH
189 
190 
191 
192 // ********************************************************************************
193 // TR1 support
194 // ********************************************************************************
195 
196 #if HAVE_TR1_HASH
197 // We have std::tr1::hash from TR1
198 
199 #ifndef HAVE_DUNE_HASH
200 // std::hash wasn't found, so use std::tr1::hash
201 
202 // Announce that we provide Dune::hash
203 #define HAVE_DUNE_HASH 1
204 
205 // import std::tr1::hash into Dune namespace
206 namespace Dune {
207 
208  using std::tr1::hash;
209 
210 }
211 
212 #endif // HAVE_DUNE_HASH
213 
214 // Macro for defining a std::tr1::hash specialization for type.
215 // This should not be called directly. Call DUNE_DEFINE_HASH
216 // instead.
217 #define DUNE_DEFINE_TR1_HASH(template_args,type) \
218  namespace std { \
219  namespace tr1 { \
220  \
221  template<template_args> \
222  struct hash<type> \
223  { \
224  std::size_t operator()(const type& arg) const \
225  { \
226  return hash_value(arg); \
227  } \
228  }; \
229  \
230  } \
231  } \
232 
233 #else // HAVE_TR1_HASH
234 
235 // We do not support std::tr1::hash, so don't do anything here.
236 #define DUNE_DEFINE_TR1_HASH(template_args,type)
237 
238 #endif // HAVE_TR1_HASH
239 
240 
241 
242 // ********************************************************************************
243 // common macros for both C++11 and TR1 support
244 // ********************************************************************************
245 
246 #if HAVE_STD_HASH || HAVE_TR1_HASH
247 
248 // Wrapper macro for template arguments.
249 // This is required because the template arguments can contain commas,
250 // which will create a macro argument list of unknown length. That in itself
251 // would not be a problem, but DUNE_DEFINE_HASH has to be called with two argument
252 // lists of unknown length. So this macro wraps its arguments with parentheses,
253 // turning it into a single argument. The result is used as the parameter list of
254 // an expansion macro in the calls to the implementation-specific macros
255 // for C++11 and TR1. Noto that technically, this trick is only legal for C++11,
256 // but pretty much every compiler supports variadic macros in C++03 mode, as they
257 // are part of C99.
258 #define DUNE_HASH_TEMPLATE_ARGS(...) (__VA_ARGS__)
259 
260 // Wrapper macro for type to be hashed.
261 // See above for rationale.
262 #define DUNE_HASH_TYPE(...) (__VA_ARGS__)
263 
264 // Expansion macro for the parenthesed argument lists created by
265 // DUNE_HASH_TEMPLATE_ARGS and DUNE_HASH_TYPE.
266 #define DUNE_HASH_EXPAND_VA_ARGS(...) __VA_ARGS__
267 
268 // Define specializations for all discovered hash implementations.
269 #define DUNE_DEFINE_HASH(template_args,type) \
270  DUNE_DEFINE_STD_HASH(DUNE_HASH_EXPAND_VA_ARGS template_args, DUNE_HASH_EXPAND_VA_ARGS type) \
271  DUNE_DEFINE_TR1_HASH(DUNE_HASH_EXPAND_VA_ARGS template_args,DUNE_HASH_EXPAND_VA_ARGS type) \
272 
273 
274 #else // HAVE_STD_HASH || HAVE_TR1_HASH
275 
276 
277 // Fallback implementation that doesn't do anything.
278 #define DUNE_DEFINE_HASH(template_args,type)
279 
280 // Consider DUNE_HASH_TEMPLATE_ARGS as an argument-less macro and
281 // replace it with an empty token.
282 // This will leave its arguments in parentheses, causing them
283 // to be considered as a single argument to DUNE_DEFINE_HASH, which
284 // will ignore them anyway.
285 #define DUNE_HASH_TEMPLATE_ARGS
286 
287 // Replace DUNE_HASH_TYPE with an empty token. See above for rationale.
288 #define DUNE_HASH_TYPE
289 
290 #endif // HAVE_STD_HASH || HAVE_TR1_HASH
291 
292 
293 
294 // ********************************************************************************
295 // Boost support
296 // ********************************************************************************
297 
298 #if !HAVE_DUNE_HASH && HAVE_BOOST_HASH
299 // We haven't found a hash implementation yet and Boost is available
300 
301 // Announce that we provide Dune::hash
302 #define HAVE_DUNE_HASH 1
303 
304 // import boost::hash into Dune namespace
305 namespace Dune {
306 
307  using boost::hash;
308 
309 }
310 
311 // We no not need to register our types with boost::hash, as its extension
312 // mechanism will automatically pick up the global hash_value() functions.
313 
314 #endif // !HAVE_DUNE_HASH && HAVE_BOOST_HASH
315 
316 #endif // DOXYGEN
317 
318 
319 
320 // ********************************************************************************
321 // Some utility functions for combining hashes of member variables.
322 // ********************************************************************************
323 
324 #if HAVE_DUNE_HASH || defined(DOXYGEN)
325 
326 namespace Dune {
327 
328  // The following functions are an implementation of the proposed hash extensions for
329  // the C++ standard by Peter Dimov
330  // (cf. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, issue 6.18).
331  // They are also contained in the boost::functional::hash library by Daniel James, but
332  // that implementation uses boost::hash internally, while we want to use Dune::hash. They
333  // are also considered for inclusion in TR2 (then based on std::hash, of course).
334 
335 #ifndef DOXYGEN
336 
337  // helper struct for providing different hash combining algorithms dependent on
338  // the size of size_t.
339  // hash_combiner has to be specialized for the size (in bytes) of std::size_t.
340  // Specialized versions should provide a method
341  //
342  // template <typename typeof_size_t, typename T>
343  // void operator()(typeof_size_t& seed, const T& arg) const;
344  //
345  // that will be called by the interface function hash_combine() described further below.
346  // The redundant template parameter typeof_size_t is needed to avoid warnings for the
347  // unused 64-bit specialization on 32-bit systems.
348  //
349  // There is no default implementation!
350  template<int sizeof_size_t>
351  struct hash_combiner;
352 
353 
354  // hash combining for 64-bit platforms.
355  template<>
356  struct hash_combiner<8>
357  {
358 
359  template<typename typeof_size_t, typename T>
360  void operator()(typeof_size_t& seed, const T& arg) const
361  {
362  dune_static_assert(sizeof(typeof_size_t)==8, "hash_combiner::operator() instantiated with nonmatching type and size");
363 
364  // The following algorithm for combining two 64-bit hash values is inspired by a similar
365  // function in CityHash (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.h),
366  // which is in turn based on ideas from the MurmurHash library. The basic idea is easy to
367  // grasp, though: New information is XORed into the existing hash multiple times at different
368  // places (using shift operations), and the resulting pattern is spread over the complete
369  // range of available bits via multiplication with a "magic" constant. The constants used
370  // below (47 and 0x9ddfea08eb382d69ULL) are taken from the CityHash implementation.
371  //
372  // We opted not to use the mixing algorithm proposed in the C++ working group defect list at
373  // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, p. 57f. because it
374  // has very bad hash distribution properties if you apply it to lists of very small numbers,
375  // an application that is frequent in PDELab's ordering framework.
376 
377  Dune::hash<T> hasher;
378  const typeof_size_t kMul = 0x9ddfea08eb382d69ULL;
379  typeof_size_t h = hasher(arg);
380  typeof_size_t a = (seed ^ h) * kMul;
381  a ^= (a >> 47);
382  typeof_size_t b = (h ^ a) * kMul;
383  b ^= (b >> 47);
384  b *= kMul;
385  seed = b;
386  }
387 
388  };
389 
390 
391  // hash combining for 32-bit platforms.
392  template<>
393  struct hash_combiner<4>
394  {
395 
396  template<typename typeof_size_t, typename T>
397  void operator()(typeof_size_t& seed, const T& arg) const
398  {
399  dune_static_assert(sizeof(typeof_size_t)==4, "hash_combiner::operator() instantiated with nonmatching type and size");
400 
401  // The default algorithm above requires a 64-bit std::size_t. The following algorithm is a
402  // 32-bit compatible fallback, again inspired by CityHash and MurmurHash
403  // (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.cc).
404  // It uses 32-bit constants and relies on rotation instead of multiplication to spread the
405  // mixed bits as that is apparently more efficient on IA-32. The constants used below are again
406  // taken from CityHash, in particular from the file referenced above.
407 
408  Dune::hash<T> hasher;
409  const typeof_size_t c1 = 0xcc9e2d51;
410  const typeof_size_t c2 = 0x1b873593;
411  const typeof_size_t c3 = 0xe6546b64;
412  typeof_size_t h = hasher(arg);
413  typeof_size_t a = seed * c1;
414  a = (a >> 17) | (a << (32 - 17));
415  a *= c2;
416  h ^= a;
417  h = (h >> 19) | (h << (32 - 19));
418  seed = h * 5 + c3;
419  }
420 
421  };
422 
423 #endif // DOXYGEN
424 
426 
432  template<typename T>
433  inline void hash_combine(std::size_t& seed, const T& arg)
434  {
435  hash_combiner<sizeof(std::size_t)>()(seed,arg);
436  }
437 
439 
448  template<typename It>
449  inline std::size_t hash_range(It first, It last)
450  {
451  std::size_t seed = 0;
452  for (; first != last; ++first)
453  {
454  hash_combine(seed,*first);
455  }
456  return seed;
457  }
458 
460 
468  template<typename It>
469  inline void hash_range(std::size_t& seed, It first, It last)
470  {
471  for (; first != last; ++first)
472  {
473  hash_combine(seed,*first);
474  }
475  }
476 
477 } // end namespace Dune
478 
479 #endif // HAVE_DUNE_HASH || defined(DOXYGEN)
480 
481 #endif // DUNE_COMMON_HASH_HH
Traits for type conversions and type information.
T t
Definition: alignment.hh:38
Dune namespace.
Definition: alignment.hh:13
Fallback implementation of the C++0x static_assert feature.
std::size_t operator()(const T &t) const
Calculates the hash of t.
Definition: hash.hh:69
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:449
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:433
Functor for hashing objects of type T.
Definition: hash.hh:65
#define dune_static_assert(COND, MSG)
Helper template so that compilation fails if condition is not true.
Definition: static_assert.hh:79