corecel/math/HashUtils.hh

0001 //------------------------------- -*- C++ -*- -------------------------------//
0002 // Copyright Celeritas contributors: see top-level COPYRIGHT file for details
0003 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0004 //---------------------------------------------------------------------------//
0005 //! \file corecel/math/HashUtils.hh
0006 // TODO for v1.0: rename to Hasher.hh
0007 //---------------------------------------------------------------------------//
0008 #pragma once
0009
0010 #include <cstddef>
0011 #include <functional>
0012 #include <initializer_list>
0013 #include <type_traits>
0014
0015 #include "corecel/Macros.hh"
0016 #include "corecel/cont/Span.hh"
0017
0018 #include "detail/FnvHasher.hh"
0019
0020 namespace celeritas
0021 {
0022 //---------------------------------------------------------------------------//
0023 // TODO: add CMake configuration argument so this can be swapped out with e.g.
0024 // xxHash
0025 using Hasher = detail::FnvHasher<std::size_t>;
0026
0027 //---------------------------------------------------------------------------//
0028 /*!
0029  * Hash a span of contiguous data without padding.
0030  *
0031  * This should generally only be used if \c has_unique_object_representations_v
0032  * is \c true, because e.g. structs have padding so this may result in reading
0033  * uninitialized data or giving two equal structs different hashes.
0034  */
0035 template<class T, std::size_t N>
0036 std::size_t hash_as_bytes(Span<T const, N> s)
0037 {
0038     std::size_t result{};
0039     Hasher hash{&result};
0040     // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
0041     hash(Span<std::byte const>{reinterpret_cast<std::byte const*>(s.data()),
0042                                s.size() * sizeof(T)});
0043     return result;
0044 }
0045
0046 //---------------------------------------------------------------------------//
0047 /*!
0048  * Combine hashes of the given arguments using a fast hash algorithm.
0049  *
0050  * See https://florianjw.de/en/variadic_templates.html for why we constructed
0051  * this as such. By making the variadic template use function argument
0052  * expansion rather than recursion, we can unpack the args in a left-to-right
0053  * order. The `(HASH,0)` construction is to give the unpacked expression a
0054  * return type; and putting these in an `initializer_list` constructor
0055  * guarantees the hashes are evaluated from left to right (unlike a typical
0056  * argument expansion where the orders may be arbitrary).
0057  */
0058 template<class... Args>
0059 std::size_t hash_combine(Args const&... args)
0060 {
0061     // Construct a hasher and initialize
0062     std::size_t result{};
0063     [[maybe_unused]] Hasher hash{&result};
0064
0065     // Hash each one of the arguments sequentially by expanding into an unused
0066     // initializer list.
0067     (void)std::initializer_list<int>{(hash(std::hash<Args>()(args)), 0)...};
0068
0069     return result;
0070 }
0071 //---------------------------------------------------------------------------//
0072 }  // namespace celeritas
0073
0074 //---------------------------------------------------------------------------//
0075 //! \cond
0076 namespace std
0077 {
0078 //---------------------------------------------------------------------------//
0079 /*!
0080  * Hash specialization for celeritas span.
0081  *
0082  * This has three distinct cases:
0083  * 1. Unique object representation: use for structs without padding or floats.
0084  * 2. Floating point values: these will hash uniquely if they're not NaN.
0085  * 3. All other types: combine the hash of their individual values.
0086  */
0087 template<class T, std::size_t Extent>
0088 struct hash<celeritas::Span<T, Extent>>
0089 {
0090     std::size_t operator()(celeritas::Span<T, Extent> const& s) const
0091     {
0092         if constexpr (std::has_unique_object_representations_v<T>)
0093         {
0094             return celeritas::hash_as_bytes(s);
0095         }
0096         else if constexpr (std::is_floating_point_v<T>)
0097         {
0098             CELER_EXPECT(([&s] {
0099                 for (auto const& v : s)
0100                 {
0101                     if (v != v)
0102                         return false;
0103                 }
0104                 return true;
0105             }()));
0106             return celeritas::hash_as_bytes(s);
0107         }
0108         else
0109         {
0110             std::size_t result{};
0111             celeritas::Hasher hash{&result};
0112             for (auto const& v : s)
0113             {
0114                 hash(std::hash<std::remove_cv_t<T>>{}(v));
0115             }
0116             return result;
0117         }
0118     }
0119 };
0120
0121 //---------------------------------------------------------------------------//
0122 }  // namespace std
0123 //! \endcond