intrusive/detail/hash.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // Copyright 2005-2014 Daniel James.
0004 // Copyright 2021, 2022 Peter Dimov.
0005 // Copyright 2024 Ion Gaztanaga.
0006 // Distributed under the Boost Software License, Version 1.0.
0007 // https://www.boost.org/LICENSE_1_0.txt
0008 //
0009 // Based on Peter Dimov's proposal
0010 // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
0011 // issue 6.18.
0012 //
0013 // The original C++11 implementation was done by Peter Dimov
0014 // The C++03 porting was done by Ion Gaztanaga.
0015 //
0016 // The goal of this header is to avoid Intrusive's hard dependency on ContainerHash,
0017 // which adds additional dependencies and the minimum supported C++ standard can
0018 // differ between both libraries. However, a compatibility protocol is used so that
0019 // users compatible with ContainerHash are also compatible with Intrusive:
0020 //
0021 // - If users define `hash_value` (as required by boost::hash) for their classes
0022 //   are automatically compatible with Intrusive unordered containers.
0023 //
0024 // - If users include boost/container_hash/hash.hpp in their headers, Intrusive
0025 //   unordered containers will take advantage of boost::hash compatibility hash functions
0026 //   (such as hashing functions for range-compatible types, standard containers, etc.)
0027 //
0028 // See http://www.boost.org/libs/intrusive for documentation.
0029 //
0030 /////////////////////////////////////////////////////////////////////////////
0031
0032 #ifndef BOOST_INTRUSIVE_HASH_HASH_HPP
0033 #define BOOST_INTRUSIVE_HASH_HASH_HPP
0034
0035 #include <boost/intrusive/detail/config_begin.hpp>
0036 #include <boost/intrusive/detail/workaround.hpp>
0037 #include <boost/intrusive/detail/hash_integral.hpp>
0038 #include <boost/intrusive/detail/hash_mix.hpp>
0039 #include <boost/intrusive/detail/hash_combine.hpp>
0040 #include <boost/cstdint.hpp>
0041 #include <climits>
0042 #include <cstring>
0043 #include <cfloat>
0044 #include <boost/intrusive/detail/mpl.hpp>
0045
0046 namespace boost {
0047
0048 template<class T>
0049 struct hash;
0050
0051 } //namespace boost
0052
0053 //Fallback function to call boost::hash if scalar type and ADL fail.
0054 //The user must include boost/container_hash/hash.hpp when to make this call work,
0055 //this allows boost::intrusive to be compatible with boost::hash without
0056 //a mandatory physical (header inclusion) dependency
0057 namespace boost_intrusive_adl
0058 {
0059    template<class T>
0060    inline std::size_t hash_value(const T& v)
0061    {
0062       return boost::hash<T>()(v);
0063    }
0064 }
0065
0066 namespace boost {
0067 namespace intrusive {
0068 namespace detail {
0069
0070 //ADL-based lookup hash call
0071 template <class T>
0072 inline typename detail::disable_if_c<detail::is_scalar<T>::value, std::size_t>::type
0073    hash_value_dispatch(const T& v)
0074 {
0075    //Try ADL lookup, if it fails, boost_intrusive_adl::hash_value will retry with boost::hash
0076    using boost_intrusive_adl::hash_value;
0077    return hash_value(v);
0078 }
0079
0080 template <typename T>
0081 typename enable_if_c<is_enum<T>::value, std::size_t>::type
0082    hash_value( T v )
0083 {
0084    return static_cast<std::size_t>( v );
0085 }
0086
0087 ////////////////////////////////////////////////////////////
0088 //
0089 //          floating point types
0090 //
0091 ////////////////////////////////////////////////////////////
0092
0093 template<class T, std::size_t Bits = sizeof(T) * CHAR_BIT>
0094 struct hash_float_impl;
0095
0096 // float
0097 template<class T> struct hash_float_impl<T, 32>
0098 {
0099    static std::size_t fn( T v )
0100    {
0101          boost::uint32_t w;
0102          std::memcpy( &w, &v, sizeof( v ) );
0103
0104          return w;
0105    }
0106 };
0107
0108 // double
0109 template<class T> struct hash_float_impl<T, 64>
0110 {
0111    static std::size_t fn( T v )
0112    {
0113          boost::uint64_t w;
0114          std::memcpy( &w, &v, sizeof( v ) );
0115
0116          return hash_value( w );
0117    }
0118 };
0119
0120 // 80 bit long double in 12 bytes
0121 template<class T> struct hash_float_impl<T, 96>
0122 {
0123    static std::size_t fn( T v )
0124    {
0125          boost::uint64_t w[ 2 ] = {};
0126          std::memcpy( &w, &v, 80 / CHAR_BIT );
0127
0128          std::size_t seed = 0;
0129
0130          seed = hash_value( w[0] ) + (hash_mix)( seed );
0131          seed = hash_value( w[1] ) + (hash_mix)( seed );
0132
0133          return seed;
0134    }
0135 };
0136
0137 #if (LDBL_MAX_10_EXP == 4932)
0138
0139 // 80 bit long double in 16 bytes
0140 template<class T> struct hash_float_impl<T, 128>
0141 {
0142    static std::size_t fn( T v )
0143    {
0144       boost::uint64_t w[ 2 ] = {};
0145       std::memcpy( &w, &v, 80 / CHAR_BIT );
0146
0147       std::size_t seed = 0;
0148
0149       seed = hash_value( w[0] ) + (hash_mix)( seed );
0150       seed = hash_value( w[1] ) + (hash_mix)( seed );
0151
0152       return seed;
0153    }
0154 };
0155
0156 #elif (LDBL_MAX_10_EXP  > 4932)
0157 // 128 bit long double
0158 template<class T> struct hash_float_impl<T, 128>
0159 {
0160    static std::size_t fn( T v )
0161    {
0162       boost::uint64_t w[ 2 ];
0163       std::memcpy( &w, &v, sizeof( v ) );
0164
0165       std::size_t seed = 0;
0166
0167    #if defined(__FLOAT_WORD_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __FLOAT_WORD_ORDER__ == __ORDER_BIG_ENDIAN__
0168
0169       seed = hash_value( w[1] ) + (hash_mix)( seed );
0170       seed = hash_value( w[0] ) + (hash_mix)( seed );
0171
0172    #else
0173
0174       seed = hash_value( w[0] ) + (hash_mix)( seed );
0175       seed = hash_value( w[1] ) + (hash_mix)( seed );
0176
0177    #endif
0178       return seed;
0179    }
0180 };
0181 #endif   //#if (LDBL_MAX_10_EXP  == 4932)
0182
0183 template <typename T>
0184 typename enable_if_c<is_floating_point<T>::value, std::size_t>::type
0185    hash_value( T v )
0186 {
0187    return boost::intrusive::detail::hash_float_impl<T>::fn( v + 0 );
0188 }
0189
0190 ////////////////////////////////////////////////////////////
0191 //
0192 //          pointer types
0193 //
0194 ////////////////////////////////////////////////////////////
0195 // `x + (x >> 3)` adjustment by Alberto Barbati and Dave Harris.
0196 template <class T> std::size_t hash_value( T* const& v )
0197 {
0198    std::size_t x = reinterpret_cast<std::size_t>( v );
0199    return hash_value( x + (x >> 3) );
0200 }
0201
0202 ////////////////////////////////////////////////////////////
0203 //
0204 //          std::nullptr_t
0205 //
0206 ////////////////////////////////////////////////////////////
0207 #if !defined(BOOST_NO_CXX11_NULLPTR)
0208 template <typename T>
0209 typename enable_if_c<is_same<T, std::nullptr_t>::value, std::size_t>::type
0210    hash_value( T const &)
0211 {
0212    return (hash_value)( static_cast<void*>( nullptr ) );
0213 }
0214    #endif
0215
0216 ////////////////////////////////////////////////////////////
0217 //
0218 //          Array types
0219 //
0220 ////////////////////////////////////////////////////////////
0221
0222 //Forward declaration or internal hash functor, for array iteration
0223 template<class T>
0224 struct internal_hash_functor;
0225
0226 template<class T, std::size_t N>
0227 inline std::size_t hash_value_dispatch( T const (&x)[ N ] )
0228 {
0229    std::size_t seed = 0;
0230    for(std::size_t i = 0; i != N; ++i){
0231       hash_combine_size_t(seed, internal_hash_functor<T>()(x[i]));
0232    }
0233    return seed;
0234 }
0235
0236 template<class T, std::size_t N>
0237 inline std::size_t hash_value_dispatch( T (&x)[ N ] )
0238 {
0239    std::size_t seed = 0;
0240    for (std::size_t i = 0; i != N; ++i) {
0241       hash_combine_size_t(seed, internal_hash_functor<T>()(x[i]));
0242    }
0243    return seed;
0244 }
0245
0246 ////////////////////////////////////////////////////////////
0247 //
0248 //          Scalar types, calls proper overload
0249 //
0250 ////////////////////////////////////////////////////////////
0251 template <class T>
0252 inline typename detail::enable_if_c<detail::is_scalar<T>::value, std::size_t>::type
0253    hash_value_dispatch(const T &v)
0254 {
0255    return boost::intrusive::detail::hash_value(v);
0256 }
0257
0258 //Internal "anonymous" hash functor, first selects between "built-in" scalar/array types
0259 //and ADL-based lookup
0260
0261 template<class T>
0262 struct internal_hash_functor
0263 {
0264    inline std::size_t operator()(T const& val) const
0265    {
0266       return ::boost::intrusive::detail::hash_value_dispatch(val);
0267    }
0268 };
0269
0270 } // namespace detail {
0271 } // namespace intrusive {
0272 } // namespace boost
0273
0274 #include <boost/intrusive/detail/config_end.hpp>
0275
0276 #endif // #ifndef BOOST_INTRUSIVE_HASH_HASH_HPP
0277