00001 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- 00002 // vi: set et ts=4 sw=2 sts=2: 00003 #ifndef DUNE_COMMON_HASH_HH 00004 #define DUNE_COMMON_HASH_HH 00005 00006 #include <functional> 00007 00008 #include <dune/common/typetraits.hh> 00009 00022 // ******************************************************************************** 00023 // Doxygen documentation 00024 // ******************************************************************************** 00025 00026 #ifdef DOXYGEN 00027 00028 namespace Dune { 00029 00031 00036 template<typename T> 00037 struct hash 00038 { 00039 00041 std::size_t operator()(const T& t) const 00042 { 00043 return hash(t); 00044 } 00045 00046 }; 00047 00048 } 00049 00051 00098 #define DUNE_DEFINE_HASH(template_args,type) 00099 00100 00102 00107 #define DUNE_HASH_TEMPLATE_ARGS(...) 00108 00110 00115 #define DUNE_HASH_TYPE(...) 00116 00117 #else // DOXYGEN - hide all the ugly implementation 00118 00119 00120 00121 // ******************************************************************************** 00122 // C++11 support 00123 // ******************************************************************************** 00124 00125 // import std::hash into Dune namespace 00126 namespace Dune { 00127 00128 using std::hash; 00129 00130 } 00131 00132 // Macro for defining a std::hash specialization for type. 00133 // This should not be called directly. Call DUNE_DEFINE_HASH 00134 // instead. 00135 #define DUNE_DEFINE_STD_HASH(template_args,type) \ 00136 namespace std { \ 00137 \ 00138 template<template_args> \ 00139 struct hash<type> \ 00140 { \ 00141 \ 00142 typedef type argument_type; \ 00143 typedef std::size_t result_type; \ 00144 \ 00145 std::size_t operator()(const type& arg) const \ 00146 { \ 00147 return hash_value(arg); \ 00148 } \ 00149 }; \ 00150 \ 00151 } \ 00152 00153 // Wrapper macro for template arguments. 00154 // This is required because the template arguments can contain commas, 00155 // which will create a macro argument list of unknown length. That in itself 00156 // would not be a problem, but DUNE_DEFINE_HASH has to be called with two argument 00157 // lists of unknown length. So this macro wraps its arguments with parentheses, 00158 // turning it into a single argument. The result is used as the parameter list of 00159 // an expansion macro in the calls to the implementation-specific macros 00160 // for C++11 and TR1. Noto that technically, this trick is only legal for C++11, 00161 // but pretty much every compiler supports variadic macros in C++03 mode, as they 00162 // are part of C99. 00163 #define DUNE_HASH_TEMPLATE_ARGS(...) (__VA_ARGS__) 00164 00165 // Wrapper macro for type to be hashed. 00166 // See above for rationale. 00167 #define DUNE_HASH_TYPE(...) (__VA_ARGS__) 00168 00169 // Expansion macro for the parenthesed argument lists created by 00170 // DUNE_HASH_TEMPLATE_ARGS and DUNE_HASH_TYPE. 00171 #define DUNE_HASH_EXPAND_VA_ARGS(...) __VA_ARGS__ 00172 00173 // Define specializations for all discovered hash implementations. 00174 #define DUNE_DEFINE_HASH(template_args,type) \ 00175 DUNE_DEFINE_STD_HASH(DUNE_HASH_EXPAND_VA_ARGS template_args, DUNE_HASH_EXPAND_VA_ARGS type) \ 00176 00177 00178 #endif // DOXYGEN 00179 00180 00181 00182 // ******************************************************************************** 00183 // Some utility functions for combining hashes of member variables. 00184 // ******************************************************************************** 00185 00186 namespace Dune { 00187 00188 // The following functions are an implementation of the proposed hash extensions for 00189 // the C++ standard by Peter Dimov 00190 // (cf. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, issue 6.18). 00191 // They are also contained in the boost::functional::hash library by Daniel James, but 00192 // that implementation uses boost::hash internally, while we want to use Dune::hash. They 00193 // are also considered for inclusion in TR2 (then based on std::hash, of course). 00194 00195 #ifndef DOXYGEN 00196 00197 // helper struct for providing different hash combining algorithms dependent on 00198 // the size of size_t. 00199 // hash_combiner has to be specialized for the size (in bytes) of std::size_t. 00200 // Specialized versions should provide a method 00201 // 00202 // template <typename typeof_size_t, typename T> 00203 // void operator()(typeof_size_t& seed, const T& arg) const; 00204 // 00205 // that will be called by the interface function hash_combine() described further below. 00206 // The redundant template parameter typeof_size_t is needed to avoid warnings for the 00207 // unused 64-bit specialization on 32-bit systems. 00208 // 00209 // There is no default implementation! 00210 template<int sizeof_size_t> 00211 struct hash_combiner; 00212 00213 00214 // hash combining for 64-bit platforms. 00215 template<> 00216 struct hash_combiner<8> 00217 { 00218 00219 template<typename typeof_size_t, typename T> 00220 void operator()(typeof_size_t& seed, const T& arg) const 00221 { 00222 static_assert(sizeof(typeof_size_t)==8, "hash_combiner::operator() instantiated with nonmatching type and size"); 00223 00224 // The following algorithm for combining two 64-bit hash values is inspired by a similar 00225 // function in CityHash (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.h), 00226 // which is in turn based on ideas from the MurmurHash library. The basic idea is easy to 00227 // grasp, though: New information is XORed into the existing hash multiple times at different 00228 // places (using shift operations), and the resulting pattern is spread over the complete 00229 // range of available bits via multiplication with a "magic" constant. The constants used 00230 // below (47 and 0x9ddfea08eb382d69ULL) are taken from the CityHash implementation. 00231 // 00232 // We opted not to use the mixing algorithm proposed in the C++ working group defect list at 00233 // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, p. 57f. because it 00234 // has very bad hash distribution properties if you apply it to lists of very small numbers, 00235 // an application that is frequent in PDELab's ordering framework. 00236 00237 Dune::hash<T> hasher; 00238 const typeof_size_t kMul = 0x9ddfea08eb382d69ULL; 00239 typeof_size_t h = hasher(arg); 00240 typeof_size_t a = (seed ^ h) * kMul; 00241 a ^= (a >> 47); 00242 typeof_size_t b = (h ^ a) * kMul; 00243 b ^= (b >> 47); 00244 b *= kMul; 00245 seed = b; 00246 } 00247 00248 }; 00249 00250 00251 // hash combining for 32-bit platforms. 00252 template<> 00253 struct hash_combiner<4> 00254 { 00255 00256 template<typename typeof_size_t, typename T> 00257 void operator()(typeof_size_t& seed, const T& arg) const 00258 { 00259 static_assert(sizeof(typeof_size_t)==4, "hash_combiner::operator() instantiated with nonmatching type and size"); 00260 00261 // The default algorithm above requires a 64-bit std::size_t. The following algorithm is a 00262 // 32-bit compatible fallback, again inspired by CityHash and MurmurHash 00263 // (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.cc). 00264 // It uses 32-bit constants and relies on rotation instead of multiplication to spread the 00265 // mixed bits as that is apparently more efficient on IA-32. The constants used below are again 00266 // taken from CityHash, in particular from the file referenced above. 00267 00268 Dune::hash<T> hasher; 00269 const typeof_size_t c1 = 0xcc9e2d51; 00270 const typeof_size_t c2 = 0x1b873593; 00271 const typeof_size_t c3 = 0xe6546b64; 00272 typeof_size_t h = hasher(arg); 00273 typeof_size_t a = seed * c1; 00274 a = (a >> 17) | (a << (32 - 17)); 00275 a *= c2; 00276 h ^= a; 00277 h = (h >> 19) | (h << (32 - 19)); 00278 seed = h * 5 + c3; 00279 } 00280 00281 }; 00282 00283 #endif // DOXYGEN 00284 00286 00291 template<typename T> 00292 inline void hash_combine(std::size_t& seed, const T& arg) 00293 { 00294 hash_combiner<sizeof(std::size_t)>()(seed,arg); 00295 } 00296 00298 00306 template<typename It> 00307 inline std::size_t hash_range(It first, It last) 00308 { 00309 std::size_t seed = 0; 00310 for (; first != last; ++first) 00311 { 00312 hash_combine(seed,*first); 00313 } 00314 return seed; 00315 } 00316 00318 00325 template<typename It> 00326 inline void hash_range(std::size_t& seed, It first, It last) 00327 { 00328 for (; first != last; ++first) 00329 { 00330 hash_combine(seed,*first); 00331 } 00332 } 00333 00334 } // end namespace Dune 00335 00336 #endif // DUNE_COMMON_HASH_HH