EIC code displayed by LXR master/​include/​boost/​openmethod/​policies/​fast_perfect_hash.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-08-17 08:52:04

 // Copyright (c) 2018-2025 Jean-Louis Leroy
 // Distributed under the Boost Software License, Version 1.0.
 // See accompanying file LICENSE_1_0.txt
 // or copy at http://www.boost.org/LICENSE_1_0.txt)
 
 #ifndef BOOST_OPENMETHOD_POLICY_FAST_PERFECT_HASH_HPP
 #define BOOST_OPENMETHOD_POLICY_FAST_PERFECT_HASH_HPP
 
 #include <boost/openmethod/preamble.hpp>
 
 #include <limits>
 #include <random>
 #ifdef _MSC_VER
 #pragma warning(push)
 #pragma warning(disable : 4702) // unreachable code
 #endif
 
 namespace boost::openmethod {
 
 namespace detail {
 
 #if defined(UINTPTR_MAX)
 using uintptr = std::uintptr_t;
 constexpr uintptr uintptr_max = UINTPTR_MAX;
 #else
 static_assert(
     sizeof(std::size_t) == sizeof(void*),
     "This implementation requires that size_t and void* have the same size.");
 using uintptr = std::size_t;
 constexpr uintptr uintptr_max = (std::numeric_limits<std::size_t>::max)();
 #endif
 
 template<class Registry>
 std::vector<type_id> fast_perfect_hash_control;
 
 } // namespace detail
 
 namespace policies {
 
 //! Hash type ids using a fast, perfect hash function.
 //!
 //! `fast_perfect_hash` implements the @ref type_hash policy using a hash
 //! function in the form `H(x)=(M*x)>>S`. It attempts to determine values for
 //! `M` and `S` that do not result in collisions for the set of registered
 //! type_ids. This may fail for certain sets of inputs, although it is very
 //! likely to succeed for addresses of `std::type_info` objects.
 //!
 //! There is no guarantee that every value in the codomain of the function
 //! corresponds to a value in the domain, or even that the codomain is a dense
 //! range of integers. In other words, a lot of space may be wasted in presence
 //! of large sets of type_ids.
 struct fast_perfect_hash : type_hash {
 
     //! Cannot find hash factors
     struct search_error : openmethod_error {
         //! Number of attempts to find hash factors
         std::size_t attempts;
         //! Number of buckets used in the last attempt
         std::size_t buckets;
 
         //! Write a short description to an output stream
         //! @param os The output stream
         //! @tparam Registry The registry
         //! @tparam Stream A @ref LightweightOutputStream
         template<class Registry, class Stream>
         auto write(Stream& os) const -> void;
     };
 
     using errors = std::variant<search_error>;
 
     //! A TypeHashFn metafunction.
     //!
     //! @tparam Registry The registry containing this policy
     template<class Registry>
     class fn {
         static std::size_t mult;
         static std::size_t shift;
         static std::size_t min_value;
         static std::size_t max_value;
 
         static void check(std::size_t index, type_id type);
 
         template<class InitializeContext, class... Options>
         static void initialize(
             const InitializeContext& ctx, std::vector<type_id>& buckets,
             const std::tuple<Options...>& options);
 
       public:
         //! Find the hash factors
         //!
         //! Attempts to find suitable values for the multiplication factor `M`
         //! and the shift amount `S` to that do not result in collisions for the
         //! specified input values.
         //!
         //! If no suitable values are found, calls the error handler with
         //! a @ref hash_error object then calls `abort`.
         //!
         //! @tparam Context An @ref InitializeContext.
         //! @param ctx A Context object.
         //! @return A pair containing the minimum and maximum hash values.
         template<class Context, class... Options>
         static auto
         initialize(const Context& ctx, const std::tuple<Options...>& options) {
             if constexpr (Registry::has_runtime_checks) {
                 initialize(
                     ctx, detail::fast_perfect_hash_control<Registry>, options);
             } else {
                 std::vector<type_id> buckets;
                 initialize(ctx, buckets, options);
             }
 
             return std::pair{min_value, max_value};
         }
 
         //! Hash a type id
         //!
         //! Hash a type id.
         //!
         //! If `Registry` contains the @ref runtime_checks policy, checks that
         //! the type id is valid, i.e. if it was present in the set passed to
         //! @ref initialize. Its absence indicates that a class involved in a
         //! method definition, method overrider, or method call was not
         //! registered. In this case, signal a @ref missing_class using
         //! the registry's @ref error_handler if present; then calls `abort`.
         //!
         //! @param type The type_id to hash
         //! @return The hash value
         BOOST_FORCEINLINE
         static auto hash(type_id type) -> std::size_t {
             auto index =
                 (mult * reinterpret_cast<detail::uintptr>(type)) >> shift;
 
             if constexpr (Registry::has_runtime_checks) {
                 check(index, type);
             }
 
             return index;
         }
 
         //! Releases the memory allocated by `initialize`.
         //!
         //! @tparam Options... Zero or more option types, deduced from the function
         //! arguments.
         //! @param options Zero or more option objects.
         template<class... Options>
         static auto finalize(const std::tuple<Options...>&) -> void {
             detail::fast_perfect_hash_control<Registry>.clear();
         }
     };
 };
 
 template<class Registry>
 std::size_t fast_perfect_hash::fn<Registry>::mult;
 
 template<class Registry>
 std::size_t fast_perfect_hash::fn<Registry>::shift;
 
 template<class Registry>
 std::size_t fast_perfect_hash::fn<Registry>::min_value;
 
 template<class Registry>
 std::size_t fast_perfect_hash::fn<Registry>::max_value;
 
 template<class Registry>
 template<class InitializeContext, class... Options>
 void fast_perfect_hash::fn<Registry>::initialize(
     const InitializeContext& ctx, std::vector<type_id>& buckets,
     const std::tuple<Options...>& options) {
     (void)options;
 
     const auto N = std::distance(ctx.classes_begin(), ctx.classes_end());
 
     if constexpr (mp11::mp_contains<mp11::mp_list<Options...>, trace>::value) {
         Registry::output::os << "Finding hash factor for " << N << " types\n";
     }
 
     std::default_random_engine rnd(13081963);
     std::size_t total_attempts = 0;
     std::size_t M = 1;
 
     for (auto size = N * 5 / 4; size >>= 1;) {
         ++M;
     }
 
     std::uniform_int_distribution<std::size_t> uniform_dist;
 
     for (std::size_t pass = 0; pass < 4; ++pass, ++M) {
         shift = 8 * sizeof(type_id) - M;
         auto hash_size = 1 << M;
         min_value = (std::numeric_limits<std::size_t>::max)();
         max_value = (std::numeric_limits<std::size_t>::min)();
 
         if constexpr (InitializeContext::template has_option<trace>) {
             ctx.tr << "  trying with M = " << M << ", " << hash_size
                    << " buckets\n";
         }
 
         std::size_t attempts = 0;
         buckets.resize(hash_size);
 
         while (attempts < 100000) {
             std::fill(
                 buckets.begin(), buckets.end(), type_id(detail::uintptr_max));
             ++attempts;
             ++total_attempts;
             mult = uniform_dist(rnd) | 1;
 
             for (auto iter = ctx.classes_begin(); iter != ctx.classes_end();
                  ++iter) {
                 for (auto type_iter = iter->type_id_begin();
                      type_iter != iter->type_id_end(); ++type_iter) {
                     auto type = *type_iter;
                     auto index = (detail::uintptr(type) * mult) >> shift;
                     min_value = (std::min)(min_value, index);
                     max_value = (std::max)(max_value, index);
 
                     if (detail::uintptr(buckets[index]) !=
                         detail::uintptr_max) {
                         goto collision;
                     }
 
                     buckets[index] = type;
                 }
             }
 
             if constexpr (InitializeContext::template has_option<trace>) {
                 ctx.tr << "  found " << mult << " after " << total_attempts
                        << " attempts; span = [" << min_value << ", "
                        << max_value << "]\n";
             }
 
             return;
 
         collision: {}
         }
     }
 
     search_error error;
     error.attempts = total_attempts;
     error.buckets = std::size_t(1) << M;
 
     if constexpr (Registry::has_error_handler) {
         Registry::error_handler::error(error);
     }
 
     abort();
 }
 
 template<class Registry>
 void fast_perfect_hash::fn<Registry>::check(std::size_t index, type_id type) {
     if (index < min_value || index > max_value ||
         detail::fast_perfect_hash_control<Registry>[index] != type) {
 
         if constexpr (Registry::has_error_handler) {
             missing_class error;
             error.type = type;
             Registry::error_handler::error(error);
         }
 
         abort();
     }
 }
 
 template<class Registry, class Stream>
 auto fast_perfect_hash::search_error::write(Stream& os) const -> void {
     os << "could not find hash factors after " << attempts << "s using "
        << buckets << " buckets\n";
 }
 
 } // namespace policies
 } // namespace boost::openmethod
 
 #endif

This page was automatically generated by the 2.3.7 LXR engine. The LXR team