Program Listing for File FastHash.h

↰ Return to documentation for file (ADS/dictionary/FastHash.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File FastHash.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_FastHash
 #define __ADS_FastHash
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"

#include <array>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <functional>
#include <string>
#include <string_view>
#include <type_traits>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- THE HASH FUNCTIONS ---------------------------*/
/*--------------------------------------------------------------------------*/

struct Product128 {
 std::uint64_t lo , hi;
 };

[[nodiscard]] constexpr Product128 product128( std::uint64_t a ,
                                               std::uint64_t b );

[[nodiscard]] constexpr std::uint64_t foldedProduct( std::uint64_t a ,
                                                     std::uint64_t b );

[[nodiscard]] constexpr std::uint64_t hashWord( std::uint64_t x ,
                                                std::uint64_t seed = 0 );

[[nodiscard]] std::uint64_t hashBytes( const void * p , std::size_t n ,
                                       std::uint64_t seed = 0 );

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS FastHash ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
struct FastHash;

// the hash of an integer, an enumeration, a pointer or a floating point
// number, +0 and -0 the same; out of the documentation, which describes it
// with the primary template
template< class T >
 requires( std::is_integral_v< T > || std::is_enum_v< T > ||
           std::is_pointer_v< T > ||
           ( std::is_floating_point_v< T > && ( sizeof( T ) <= 8 ) ) )
struct FastHash< T > {
 using is_avalanching = void;

 std::uint64_t seed = 0;

 [[nodiscard]] std::size_t operator()( T x ) const noexcept {
  if constexpr( std::is_pointer_v< T > )
   return( std::size_t( hashWord( std::uint64_t(
                         reinterpret_cast< std::uintptr_t >( x ) ) ,
                         seed ) ) );
  else if constexpr( std::is_enum_v< T > )
   return( std::size_t( hashWord( std::uint64_t(
                         std::underlying_type_t< T >( x ) ) , seed ) ) );
  else if constexpr( std::is_floating_point_v< T > ) {
   if( x == T( 0 ) )
    x = T( 0 );                     // -0 == +0
   std::uint64_t w = 0;
   std::memcpy( &w , &x , sizeof( T ) );
   return( std::size_t( hashWord( w , seed ) ) );
   }
  else
   return( std::size_t( hashWord( std::uint64_t( x ) , seed ) ) );
  }
 };


template<>
struct FastHash< std::string_view > {
 using is_avalanching = void;
 using is_transparent = void;

 std::uint64_t seed = 0;

 [[nodiscard]] std::size_t operator()( std::string_view s ) const noexcept
 {
  return( std::size_t( hashBytes( s.data() , s.size() , seed ) ) );
  }
 };

template<>
struct FastHash< std::string > : FastHash< std::string_view > {};

template<>
struct FastHash< const char * > : FastHash< std::string_view > {};

namespace detail {

template< class K >
struct DefaultHashOf {
 using type = std::hash< K >;
 };

template< class K >
 requires requires { sizeof( FastHash< K > ); }
struct DefaultHashOf< K > {
 using type = FastHash< K >;
 };

template< class K >
inline constexpr bool kIndirectKey = requires( const K & k ) {
 { k.data() } -> std::convertible_to< const void * >;
 k.size();
 };

template< class K >
inline void prefetchKey( const K & k )
{
 if constexpr( kIndirectKey< K > ) {
#if defined( __GNUC__ ) || defined( __clang__ )
  __builtin_prefetch( static_cast< const void * >( k.data() ) );
#else
  ( void ) k;
#endif
  }
 }

}  // end( namespace detail )

template< class K >
using DefaultHash = typename detail::DefaultHashOf< K >::type;

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/dictionary/impl/FastHash.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* FastHash.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File FastHash.h ---------------------------*/
/*--------------------------------------------------------------------------*/