boost/hash2/hash_append.hpp

0001 #ifndef BOOST_HASH2_HASH_APPEND_HPP_INCLUDED
0002 #define BOOST_HASH2_HASH_APPEND_HPP_INCLUDED
0003
0004 // Copyright 2017, 2018, 2023, 2024 Peter Dimov.
0005 // Distributed under the Boost Software License, Version 1.0.
0006 // https://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // Based on
0009 //
0010 // Types Don't Know #
0011 // Howard E. Hinnant, Vinnie Falco, John Bytheway
0012 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html
0013
0014 #include <boost/hash2/hash_append_fwd.hpp>
0015 #include <boost/hash2/is_contiguously_hashable.hpp>
0016 #include <boost/hash2/has_constant_size.hpp>
0017 #include <boost/hash2/get_integral_result.hpp>
0018 #include <boost/hash2/flavor.hpp>
0019 #include <boost/hash2/detail/is_constant_evaluated.hpp>
0020 #include <boost/hash2/detail/bit_cast.hpp>
0021 #include <boost/hash2/detail/write.hpp>
0022 #include <boost/hash2/detail/has_tag_invoke.hpp>
0023 #include <boost/container_hash/is_range.hpp>
0024 #include <boost/container_hash/is_contiguous_range.hpp>
0025 #include <boost/container_hash/is_unordered_range.hpp>
0026 #include <boost/container_hash/is_tuple_like.hpp>
0027 #include <boost/container_hash/is_described_class.hpp>
0028 #include <boost/describe/bases.hpp>
0029 #include <boost/describe/members.hpp>
0030 #include <boost/mp11/algorithm.hpp>
0031 #include <boost/mp11/integer_sequence.hpp>
0032 #include <cstdint>
0033 #include <type_traits>
0034 #include <iterator>
0035
0036 namespace boost
0037 {
0038
0039 template<class T, std::size_t N> class array;
0040
0041 namespace hash2
0042 {
0043
0044 // hash_append_range
0045
0046 namespace detail
0047 {
0048
0049 template<class Hash, class Flavor, class It> BOOST_CXX14_CONSTEXPR void hash_append_range_( Hash& h, Flavor const& f, It first, It last )
0050 {
0051     for( ; first != last; ++first )
0052     {
0053         typename std::iterator_traits<It>::value_type const& v = *first;
0054         hash2::hash_append( h, f, v );
0055     }
0056 }
0057
0058 template<class Hash, class Flavor> BOOST_CXX14_CONSTEXPR void hash_append_range_( Hash& h, Flavor const& /*f*/, unsigned char* first, unsigned char* last )
0059 {
0060     h.update( first, last - first );
0061 }
0062
0063 template<class Hash, class Flavor> BOOST_CXX14_CONSTEXPR void hash_append_range_( Hash& h, Flavor const& /*f*/, unsigned char const* first, unsigned char const* last )
0064 {
0065     h.update( first, last - first );
0066 }
0067
0068 #if defined(BOOST_NO_CXX14_CONSTEXPR)
0069
0070 template<class Hash, class Flavor, class T>
0071     typename std::enable_if<
0072         is_contiguously_hashable<T, Flavor::byte_order>::value, void >::type
0073     hash_append_range_( Hash& h, Flavor const& /*f*/, T* first, T* last )
0074 {
0075     h.update( first, (last - first) * sizeof(T) );
0076 }
0077
0078 #else
0079
0080 template<class Hash, class Flavor, class T>
0081     BOOST_CXX14_CONSTEXPR
0082     typename std::enable_if<
0083         is_contiguously_hashable<T, Flavor::byte_order>::value, void >::type
0084     hash_append_range_( Hash& h, Flavor const& f, T* first, T* last )
0085 {
0086     if( !detail::is_constant_evaluated() )
0087     {
0088         h.update( first, (last - first) * sizeof(T) );
0089     }
0090     else
0091     {
0092         for( ; first != last; ++first )
0093         {
0094             hash2::hash_append( h, f, *first );
0095         }
0096     }
0097 }
0098
0099 #endif
0100
0101 } // namespace detail
0102
0103 template<class Hash, class Flavor = default_flavor, class It> BOOST_CXX14_CONSTEXPR void hash_append_range( Hash& h, Flavor const& f, It first, It last )
0104 {
0105     detail::hash_append_range_( h, f, first, last );
0106 }
0107
0108 // hash_append_size
0109
0110 template<class Hash, class Flavor = default_flavor, class T> BOOST_CXX14_CONSTEXPR void hash_append_size( Hash& h, Flavor const& f, T const& v )
0111 {
0112     hash2::hash_append( h, f, static_cast<typename Flavor::size_type>( v ) );
0113 }
0114
0115 // hash_append_range_and_size
0116
0117 namespace detail
0118 {
0119
0120 template<class Hash, class Flavor, class It> void BOOST_CXX14_CONSTEXPR hash_append_range_and_size_( Hash& h, Flavor const& f, It first, It last, std::input_iterator_tag )
0121 {
0122     typename std::iterator_traits<It>::difference_type m = 0;
0123
0124     for( ; first != last; ++first, ++m )
0125     {
0126         hash2::hash_append( h, f, *first );
0127     }
0128
0129     hash2::hash_append_size( h, f, m );
0130 }
0131
0132 template<class Hash, class Flavor, class It> BOOST_CXX14_CONSTEXPR void hash_append_range_and_size_( Hash& h, Flavor const& f, It first, It last, std::random_access_iterator_tag )
0133 {
0134     hash2::hash_append_range( h, f, first, last );
0135     hash2::hash_append_size( h, f, last - first );
0136 }
0137
0138 } // namespace detail
0139
0140 template<class Hash, class Flavor = default_flavor, class It> BOOST_CXX14_CONSTEXPR void hash_append_range_and_size( Hash& h, Flavor const& f, It first, It last )
0141 {
0142     detail::hash_append_range_and_size_( h, f, first, last, typename std::iterator_traits<It>::iterator_category() );
0143 }
0144
0145 // hash_append_unordered_range
0146
0147 template<class Hash, class Flavor = default_flavor, class It> BOOST_CXX14_CONSTEXPR void hash_append_unordered_range( Hash& h, Flavor const& f, It first, It last )
0148 {
0149     typename std::iterator_traits<It>::difference_type m = 0;
0150
0151     std::uint64_t w = 0;
0152
0153     for( ; first != last; ++first, ++m )
0154     {
0155         Hash h2( h );
0156         hash2::hash_append( h2, f, *first );
0157
0158         w += hash2::get_integral_result<std::uint64_t>( h2 );
0159     }
0160
0161     hash2::hash_append( h, f, w );
0162     hash2::hash_append_size( h, f, m );
0163 }
0164
0165 // do_hash_append
0166
0167 namespace detail
0168 {
0169
0170 // integral types
0171
0172 template<class Hash, class Flavor, class T>
0173     BOOST_CXX14_CONSTEXPR
0174     typename std::enable_if< std::is_integral<T>::value, void >::type
0175     do_hash_append( Hash& h, Flavor const& /*f*/, T const& v )
0176 {
0177     constexpr auto N = sizeof(T);
0178
0179     unsigned char tmp[ N ] = {};
0180     detail::write( v, Flavor::byte_order, tmp );
0181
0182     h.update( tmp, N );
0183 }
0184
0185 // enum types
0186
0187 template<class Hash, class Flavor, class T>
0188     BOOST_CXX14_CONSTEXPR
0189     typename std::enable_if< std::is_enum<T>::value, void >::type
0190     do_hash_append( Hash& h, Flavor const& f, T const& v )
0191 {
0192     hash2::hash_append( h, f, static_cast<typename std::underlying_type<T>::type>( v ) );
0193 }
0194
0195 // pointer types
0196 // never constexpr
0197
0198 template<class Hash, class Flavor, class T>
0199     typename std::enable_if< std::is_pointer<T>::value, void >::type
0200     do_hash_append( Hash& h, Flavor const& f, T const& v )
0201 {
0202     hash2::hash_append( h, f, reinterpret_cast<std::uintptr_t>( v ) );
0203 }
0204
0205 // floating point
0206
0207 template<class Hash, class Flavor, class T>
0208     BOOST_CXX14_CONSTEXPR
0209     typename std::enable_if< std::is_floating_point<T>::value && sizeof(T) == 4, void >::type
0210     do_hash_append( Hash& h, Flavor const& f, T const& v )
0211 {
0212     hash2::hash_append( h, f, detail::bit_cast<std::uint32_t>( v + 0 ) );
0213 }
0214
0215 template<class Hash, class Flavor, class T>
0216     BOOST_CXX14_CONSTEXPR
0217     typename std::enable_if< std::is_floating_point<T>::value && sizeof(T) == 8, void >::type
0218     do_hash_append( Hash& h, Flavor const& f, T const& v )
0219 {
0220     hash2::hash_append( h, f, detail::bit_cast<std::uint64_t>( v + 0 ) );
0221 }
0222
0223 // std::nullptr_t
0224 // not constexpr for consistency with T*
0225
0226 template<class Hash, class Flavor, class T>
0227     typename std::enable_if< std::is_same<T, std::nullptr_t>::value, void >::type
0228     do_hash_append( Hash& h, Flavor const& f, T const& v )
0229 {
0230     hash2::hash_append( h, f, static_cast<void*>( v ) );
0231 }
0232
0233 // C arrays
0234
0235 template<class Hash, class Flavor, class T, std::size_t N> BOOST_CXX14_CONSTEXPR void do_hash_append( Hash& h, Flavor const& f, T const (&v)[ N ] )
0236 {
0237     hash2::hash_append_range( h, f, v + 0, v + N );
0238 }
0239
0240 // contiguous containers and ranges, w/ size
0241
0242 template<class Hash, class Flavor, class T>
0243     BOOST_CXX14_CONSTEXPR
0244     typename std::enable_if< container_hash::is_contiguous_range<T>::value && !has_constant_size<T>::value, void >::type
0245     do_hash_append( Hash& h, Flavor const& f, T const& v )
0246 {
0247     hash2::hash_append_range( h, f, v.data(), v.data() + v.size() );
0248     hash2::hash_append_size( h, f, v.size() );
0249 }
0250
0251 // containers and ranges, w/ size
0252
0253 template<class Hash, class Flavor, class T>
0254     BOOST_CXX14_CONSTEXPR
0255     typename std::enable_if< container_hash::is_range<T>::value && !has_constant_size<T>::value && !container_hash::is_contiguous_range<T>::value && !container_hash::is_unordered_range<T>::value, void >::type
0256     do_hash_append( Hash& h, Flavor const& f, T const& v )
0257 {
0258     hash2::hash_append_range_and_size( h, f, v.begin(), v.end() );
0259 }
0260
0261 #if defined(BOOST_MSVC)
0262 # pragma warning(push)
0263 # pragma warning(disable: 4702) // unreachable code
0264 #endif
0265
0266 // constant size contiguous containers and ranges (std::array, boost::array, hash2::digest)
0267
0268 template<class Hash, class Flavor, class T>
0269     BOOST_CXX14_CONSTEXPR
0270     typename std::enable_if< container_hash::is_contiguous_range<T>::value && has_constant_size<T>::value, void >::type
0271     do_hash_append( Hash& h, Flavor const& f, T const& v )
0272 {
0273     if( v.size() == 0 )
0274     {
0275         // A hash_append call must always result in a call to Hash::update
0276         hash2::hash_append( h, f, '\x00' );
0277     }
0278     else
0279     {
0280         // std::array<>::data() is only constexpr in C++17; boost::array<>::operator[] isn't constexpr
0281         hash2::hash_append_range( h, f, &v.front(), &v.front() + v.size() );
0282     }
0283 }
0284
0285 // constant size non-contiguous containers and ranges
0286
0287 template<class Hash, class Flavor, class T>
0288     BOOST_CXX14_CONSTEXPR
0289     typename std::enable_if< container_hash::is_range<T>::value && has_constant_size<T>::value && !container_hash::is_contiguous_range<T>::value, void >::type
0290     do_hash_append( Hash& h, Flavor const& f, T const& v )
0291 {
0292     if( v.begin() == v.end() )
0293     {
0294         // A hash_append call must always result in a call to Hash::update
0295         hash2::hash_append( h, f, '\x00' );
0296     }
0297     else
0298     {
0299         hash2::hash_append_range( h, f, v.begin(), v.end() );
0300     }
0301 }
0302
0303 #if defined(BOOST_MSVC)
0304 # pragma warning(pop)
0305 #endif
0306
0307 // unordered containers (is_unordered_range implies is_range)
0308
0309 template<class Hash, class Flavor, class T>
0310     BOOST_CXX14_CONSTEXPR
0311     typename std::enable_if< container_hash::is_unordered_range<T>::value, void >::type
0312     do_hash_append( Hash& h, Flavor const& f, T const& v )
0313 {
0314     hash2::hash_append_unordered_range( h, f, v.begin(), v.end() );
0315 }
0316
0317 // tuple-likes
0318
0319 template<class Hash, class Flavor, class T, std::size_t... J> BOOST_CXX14_CONSTEXPR void hash_append_tuple( Hash& h, Flavor const& f, T const& v, mp11::integer_sequence<std::size_t, J...> )
0320 {
0321     using std::get;
0322     int a[] = { ((void)hash2::hash_append( h, f, get<J>(v) ), 0)... };
0323     (void)a;
0324 }
0325
0326 template<class Hash, class Flavor, class T> BOOST_CXX14_CONSTEXPR void hash_append_tuple( Hash& h, Flavor const& f, T const& /*v*/, mp11::integer_sequence<std::size_t> )
0327 {
0328     // A hash_append call must always result in a call to Hash::update
0329     hash2::hash_append( h, f, '\x00' );
0330 }
0331
0332 template<class Hash, class Flavor, class T>
0333     BOOST_CXX14_CONSTEXPR
0334     typename std::enable_if< !container_hash::is_range<T>::value && container_hash::is_tuple_like<T>::value, void >::type
0335     do_hash_append( Hash& h, Flavor const& f, T const& v )
0336 {
0337     using Seq = mp11::make_index_sequence<std::tuple_size<T>::value>;
0338     detail::hash_append_tuple( h, f, v, Seq() );
0339 }
0340
0341 // described classes
0342
0343 #if defined(BOOST_DESCRIBE_CXX14)
0344
0345 #if defined(_MSC_VER) && _MSC_VER == 1900
0346 # pragma warning(push)
0347 # pragma warning(disable: 4100) // unreferenced formal parameter
0348 #endif
0349
0350 template<class Hash, class Flavor, class T>
0351     BOOST_CXX14_CONSTEXPR
0352     typename std::enable_if< container_hash::is_described_class<T>::value, void >::type
0353     do_hash_append( Hash& h, Flavor const& f, T const& v )
0354 {
0355     static_assert( !std::is_union<T>::value, "Described unions are not supported" );
0356
0357     std::size_t r = 0;
0358
0359     using Bd = describe::describe_bases<T, describe::mod_any_access>;
0360
0361     mp11::mp_for_each<Bd>([&](auto D){
0362
0363         using B = typename decltype(D)::type;
0364         hash2::hash_append( h, f, (B const&)v );
0365         ++r;
0366
0367     });
0368
0369     using Md = describe::describe_members<T, describe::mod_any_access>;
0370
0371     mp11::mp_for_each<Md>([&](auto D){
0372
0373         hash2::hash_append( h, f, v.*D.pointer );
0374         ++r;
0375
0376     });
0377
0378     // A hash_append call must always result in a call to Hash::update
0379
0380     if( r == 0 )
0381     {
0382         hash2::hash_append( h, f, '\x00' );
0383     }
0384 }
0385
0386 #if defined(_MSC_VER) && _MSC_VER == 1900
0387 # pragma warning(pop)
0388 #endif
0389
0390 #endif // defined(BOOST_DESCRIBE_CXX14)
0391
0392 // classes with tag_invoke
0393
0394 } // namespace detail
0395
0396 struct hash_append_tag
0397 {
0398 };
0399
0400 struct hash_append_provider
0401 {
0402     template<class Hash, class Flavor, class T>
0403     static BOOST_CXX14_CONSTEXPR void hash_append( Hash& h, Flavor const& f, T const& v )
0404     {
0405         hash2::hash_append( h, f, v );
0406     }
0407
0408     template<class Hash, class Flavor, class It>
0409     static BOOST_CXX14_CONSTEXPR void hash_append_range( Hash& h, Flavor const& f, It first, It last )
0410     {
0411         hash2::hash_append_range( h, f, first, last );
0412     }
0413
0414     template<class Hash, class Flavor, class T>
0415     static BOOST_CXX14_CONSTEXPR void hash_append_size( Hash& h, Flavor const& f, T const& v )
0416     {
0417         hash2::hash_append_size( h, f, v );
0418     }
0419
0420     template<class Hash, class Flavor, class It>
0421     static BOOST_CXX14_CONSTEXPR void hash_append_range_and_size( Hash& h, Flavor const& f, It first, It last )
0422     {
0423         hash2::hash_append_range_and_size( h, f, first, last );
0424     }
0425
0426     template<class Hash, class Flavor, class It>
0427     static BOOST_CXX14_CONSTEXPR void hash_append_unordered_range( Hash& h, Flavor const& f, It first, It last )
0428     {
0429         hash2::hash_append_unordered_range( h, f, first, last );
0430     }
0431 };
0432
0433 namespace detail
0434 {
0435
0436 template<class Hash, class Flavor, class T>
0437     BOOST_CXX14_CONSTEXPR
0438     typename std::enable_if< detail::has_tag_invoke<T>::value, void >::type
0439     do_hash_append( Hash& h, Flavor const& f, T const& v )
0440 {
0441     tag_invoke( hash_append_tag(), hash_append_provider(), h, f, &v );
0442 }
0443
0444 } // namespace detail
0445
0446 // hash_append
0447
0448 template<class Hash, class Flavor = default_flavor, class T>
0449 BOOST_CXX14_CONSTEXPR void hash_append( Hash& h, Flavor const& f, T const& v )
0450 {
0451     if( !detail::is_constant_evaluated() && is_contiguously_hashable<T, Flavor::byte_order>::value )
0452     {
0453         h.update( &v, sizeof(T) );
0454     }
0455     else
0456     {
0457         detail::do_hash_append( h, f, v );
0458     }
0459 }
0460
0461 } // namespace hash2
0462 } // namespace boost
0463
0464 #endif // #ifndef BOOST_HASH2_HASH_APPEND_HPP_INCLUDED