EIC code displayed by LXR |
|
|
|
|||
Warning, file /include/boost/intrusive/detail/hash_mix.hpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 ///////////////////////////////////////////////////////////////////////////// 0002 // 0003 // Copyright 2022 Peter Dimov 0004 // Copyright 2024 Ion Gaztanaga 0005 // Distributed under the Boost Software License, Version 1.0. 0006 // https://www.boost.org/LICENSE_1_0.txt 0007 // 0008 // The original C++11 implementation was done by Peter Dimov 0009 // The C++03 porting was done by Ion Gaztanaga 0010 // 0011 // Refactored the original Boost ContainerHash library to avoid 0012 // any heavy std header dependencies to just mix a hash 0013 // value represented in a std::size_t type. 0014 // 0015 // See http://www.boost.org/libs/intrusive for documentation. 0016 // 0017 ///////////////////////////////////////////////////////////////////////////// 0018 0019 0020 #ifndef BOOST_INTRUSIVE_DETAIL_HASH_MIX_HPP 0021 #define BOOST_INTRUSIVE_DETAIL_HASH_MIX_HPP 0022 0023 #include <boost/cstdint.hpp> //boost::uint64_t 0024 #include <cstddef> 0025 #include <climits> 0026 0027 namespace boost { 0028 namespace intrusive { 0029 namespace detail { 0030 0031 0032 template<std::size_t Bits> struct hash_mix_impl; 0033 0034 // hash_mix for 64 bit size_t 0035 // 0036 // The general "xmxmx" form of state of the art 64 bit mixers originates 0037 // from Murmur3 by Austin Appleby, which uses the following function as 0038 // its "final mix": 0039 // 0040 // k ^= k >> 33; 0041 // k *= 0xff51afd7ed558ccd; 0042 // k ^= k >> 33; 0043 // k *= 0xc4ceb9fe1a85ec53; 0044 // k ^= k >> 33; 0045 // 0046 // (https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp) 0047 // 0048 // It has subsequently been improved multiple times by different authors 0049 // by changing the constants. The most well known improvement is the 0050 // so-called "variant 13" function by David Stafford: 0051 // 0052 // k ^= k >> 30; 0053 // k *= 0xbf58476d1ce4e5b9; 0054 // k ^= k >> 27; 0055 // k *= 0x94d049bb133111eb; 0056 // k ^= k >> 31; 0057 // 0058 // (https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html) 0059 // 0060 // This mixing function is used in the splitmix64 RNG: 0061 // http://xorshift.di.unimi.it/splitmix64.c 0062 // 0063 // We use Jon Maiga's implementation from 0064 // http://jonkagstrom.com/mx3/mx3_rev2.html 0065 // 0066 // x ^= x >> 32; 0067 // x *= 0xe9846af9b1a615d; 0068 // x ^= x >> 32; 0069 // x *= 0xe9846af9b1a615d; 0070 // x ^= x >> 28; 0071 // 0072 // An equally good alternative is Pelle Evensen's Moremur: 0073 // 0074 // x ^= x >> 27; 0075 // x *= 0x3C79AC492BA7B653; 0076 // x ^= x >> 33; 0077 // x *= 0x1C69B3F74AC4AE35; 0078 // x ^= x >> 27; 0079 // 0080 // (https://mostlymangling.blogspot.com/2019/12/stronger-better-morer-moremur-better.html) 0081 0082 template<> struct hash_mix_impl<64> 0083 { 0084 inline static boost::uint64_t fn( boost::uint64_t x ) 0085 { 0086 boost::uint64_t const m = 0xe9846af9b1a615d; 0087 0088 x ^= x >> 32; 0089 x *= m; 0090 x ^= x >> 32; 0091 x *= m; 0092 x ^= x >> 28; 0093 0094 return x; 0095 } 0096 }; 0097 0098 // hash_mix for 32 bit size_t 0099 // 0100 // We use the "best xmxmx" implementation from 0101 // https://github.com/skeeto/hash-prospector/issues/19 0102 0103 template<> struct hash_mix_impl<32> 0104 { 0105 inline static boost::uint32_t fn( boost::uint32_t x ) 0106 { 0107 boost::uint32_t const m1 = 0x21f0aaad; 0108 boost::uint32_t const m2 = 0x735a2d97; 0109 0110 x ^= x >> 16; 0111 x *= m1; 0112 x ^= x >> 15; 0113 x *= m2; 0114 x ^= x >> 15; 0115 0116 return x; 0117 } 0118 }; 0119 0120 inline std::size_t hash_mix( std::size_t v ) 0121 { 0122 return hash_mix_impl<sizeof(std::size_t) * CHAR_BIT>::fn( v ); 0123 } 0124 0125 0126 } // namespace detail 0127 } // namespace intrusive 0128 } // namespace boost 0129 0130 #endif // #ifndef BOOST_INTRUSIVE_DETAIL_HASH_MIX_HPP
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|