DUNE PDELab (git)

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