Program Listing for File FlatHashTable.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File FlatHashTable.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"
#include "ADS/dictionary/FastHash.h"

#include <array>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <functional>
#include <memory>
#include <new>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

#ifndef ADS_FLAT_SIMD
 #if defined( __SSE2__ ) || defined( _M_X64 ) || \
     ( defined( _M_IX86_FP ) && ( _M_IX86_FP >= 2 ) )
  #define ADS_FLAT_SIMD 1
 #elif ( defined( __ARM_NEON ) && defined( __AARCH64EL__ ) ) || \
       defined( _M_ARM64 )
  #define ADS_FLAT_SIMD 2
 #else
  #define ADS_FLAT_SIMD 0
 #endif
#endif

#if ADS_FLAT_SIMD == 1
 #include <emmintrin.h>
#elif ADS_FLAT_SIMD == 2
 #include <arm_neon.h>
#endif

#if defined( _MSC_VER ) && ( defined( _M_X64 ) || defined( _M_ARM64 ) )
 #include <intrin.h>
#endif

#if defined( __GNUC__ ) || defined( __clang__ )
 #define ADS_FLAT_PREFETCH( p ) __builtin_prefetch( ( const void * )( p ) )
#elif ( ADS_FLAT_SIMD == 1 ) && defined( _MSC_VER )
 #define ADS_FLAT_PREFETCH( p ) \
  _mm_prefetch( ( const char * )( p ) , _MM_HINT_T0 )
#else
 #define ADS_FLAT_PREFETCH( p ) ( ( void ) 0 )
#endif

#if defined( __GNUC__ ) || defined( __clang__ )
 #define ADS_FLAT_INLINE inline __attribute__(( always_inline ))
#elif defined( _MSC_VER )
 #define ADS_FLAT_INLINE __forceinline
#else
 #define ADS_FLAT_INLINE inline
#endif

#if defined( __GNUC__ ) || defined( __clang__ )
 #define ADS_FLAT_NOINLINE __attribute__(( noinline ))
#elif defined( _MSC_VER )
 #define ADS_FLAT_NOINLINE __declspec( noinline )
#else
 #define ADS_FLAT_NOINLINE
#endif

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

namespace ADS {

namespace detail {

[[nodiscard]] inline std::uint64_t mulx( std::uint64_t a , std::uint64_t b );

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

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS FlatHashTable ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class K , class V , class H = DefaultHash< K > ,
          class Eq = std::equal_to< K > >
class FlatHashTable {

/*--------------------------------------------------------------------------*/
 public:

 using Key = K;
 using Value = V;

 explicit FlatHashTable( std::size_t n = 0 , H h = H() , Eq eq = Eq() );

 FlatHashTable( const FlatHashTable & o );

 FlatHashTable( FlatHashTable && o ) noexcept;

 FlatHashTable & operator=( FlatHashTable o ) noexcept;

 ~FlatHashTable();

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

 [[nodiscard]] std::optional< V > lookup( const K & k ) const;

 [[nodiscard]] const V * find( const K & k ) const;

 [[nodiscard]] V * find( const K & k );

 bool insert( const K & k , const V & v );

 bool insert( K && k , V && v );

 bool remove( const K & k );

 [[nodiscard]] bool contains( const K & k ) const;

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] bool empty( void ) const;

 [[nodiscard]] std::size_t capacity( void ) const;

 [[nodiscard]] double load( void ) const;

 [[nodiscard]] std::size_t deleted( void ) const;

 void reserve( std::size_t n );

 void clear( void );

 template< class F >
 void forEach( F && f ) const;

 template< class F >
 void forEach( F && f );

 void swap( FlatHashTable & o ) noexcept;

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the pairs ( key , value ), in the order of the
 // places, bidirectional; a removal invalidates only the iterators on the
 // removed pair, an insertion that rebuilds the table all of them

 using value_type = std::pair< const K & , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = std::pair< const K & , const V & >;
 using const_reference = std::pair< const K & , const V & >;

 class const_iterator;

 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const;
 [[nodiscard]] const_iterator end( void ) const;
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 const_iterator erase( const_iterator it );

/*--------------------------------------------------------------------------*/
 private:

 static constexpr std::uint8_t EMPTY = 0;
 static constexpr std::size_t GROUP = 16;
 static constexpr std::size_t SLOTS = 15;
 static constexpr std::size_t OVER = 15;

 struct alignas( 16 ) Group {
  std::uint8_t c[ GROUP ];
  };

#if ADS_FLAT_SIMD == 2
 using Mask = std::uint64_t;
 static constexpr int STRIDE = 2;
#else
 using Mask = std::uint32_t;
 static constexpr int STRIDE = 0;
#endif

 static constexpr Mask FIRST = Mask( 1 ) << ( ( 1 << STRIDE ) - 1 );

 union Slot {
  Slot( void ) {}
  ~Slot() {}
  std::pair< K , V > kv;
  };

 static constexpr std::size_t ALIGN = alignof( Slot ) > 64 ? alignof( Slot )
                                                           : 64;

 [[nodiscard]] static Group * control( std::size_t G );

 [[nodiscard]] static Slot * allocate( std::size_t G );

 struct Free {
  void operator()( Group * c ) const noexcept;
  void operator()( Slot * s ) const noexcept;
  };

 static constexpr bool AVALANCHING = ( sizeof( std::size_t ) >= 8 ) &&
  requires { typename H::is_avalanching; };

 inline static Group s_none[ 3 ] = { {} , {} , { { 1 } } };

 [[nodiscard]] std::uint64_t mix( const K & k ) const;

 [[nodiscard]] static std::uint32_t tag( std::uint64_t x );

 [[nodiscard]] static std::uint8_t bit( std::uint64_t x );

 [[nodiscard]] std::size_t home( std::uint64_t x ) const;

 [[nodiscard]] static Mask match( const Group & c , std::uint32_t t );

 [[nodiscard]] static Mask empties( const Group & c );

 [[nodiscard]] static Mask fulls( const Group & c );

 [[nodiscard]] static std::size_t lowest( Mask m );

#if ADS_FLAT_SIMD == 0
 [[nodiscard]] static std::uint64_t word( const std::uint8_t * c );

 [[nodiscard]] static std::uint64_t zeros( std::uint64_t w );

 [[nodiscard]] static Mask gather( std::uint64_t z );
#endif

 [[nodiscard]] std::uint8_t & ctrl( std::size_t i ) const;

 [[nodiscard]] Slot * slot( std::size_t i ) const;

 [[nodiscard]] Slot * locate( std::uint64_t x , const K & k ) const;

 [[nodiscard]] Slot * scan( std::size_t g , Mask m , const K & k ) const;

 using KeyArg = std::conditional_t< std::is_trivially_copyable_v< K > &&
                                    ( sizeof( K ) <= 2 * sizeof( void * ) ) ,
                                    K , const K & >;

 ADS_FLAT_NOINLINE Slot * further( std::uint64_t x , std::size_t g ,
                                   KeyArg k ) const;

 std::size_t claim( std::uint64_t x );

 template< class KK , class VV >
 bool put( KK && k , VV && v );

 template< class KK , class VV >
 ADS_FLAT_NOINLINE std::size_t grow( std::uint64_t x , KK && k , VV && v );

 void drop( std::size_t i );

 ADS_FLAT_NOINLINE bool recount( void );

 static void vacate( Group & c , std::size_t j );

 template< class F >
 void rebuild( std::size_t G , F && first );

 [[nodiscard]] static std::size_t groups( std::size_t n );

 [[nodiscard]] static constexpr std::size_t bound( std::size_t m );

 template< class F >
 void each( F && f ) const;

 void release( void ) noexcept;

 [[nodiscard]] bool consistent( std::uint64_t x ) const;

 Group * f_ctrl = s_none;
 Slot * f_slot = nullptr;
 std::size_t f_cap = 0;
 std::size_t f_mask = 0;
 int f_shift = 63;
 std::size_t f_max = 0;
 std::size_t f_size = 0;
 std::size_t f_deleted = 0;
 H f_h;
 Eq f_eq;

/*--------------------------------------------------------------------------*/
 public:

 class const_iterator {
  public:
  using value_type = std::pair< const K & , const V & >;
  using reference = value_type;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::bidirectional_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;

  reference operator*( void ) const {
   const auto & kv = f_b[ lowest( f_m ) ].kv;
   return( reference( kv.first , kv.second ) );
   }

  const_iterator & operator++( void ) {
   f_m &= ( f_m - 1 ) & fulls( *f_g );
   if( ! f_m ) [[unlikely]]
    forward();
   return( *this );
   }

  const_iterator & operator--( void );

  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  const_iterator operator--( int ) { auto t = *this; --*this; return( t ); }

  bool operator==( const const_iterator & o ) const {
   return( f_b + lowest( f_m ) == o.f_b + lowest( o.f_m ) );
   }

  private:
  friend class FlatHashTable;

  const_iterator( const Group * g , const Slot * b , Mask m )
   : f_g( g ) , f_b( b ) , f_m( m ) {}

  void forward( void );

  const Group * f_g = nullptr;
  const Slot * f_b = nullptr;
  Mask f_m = FIRST;

 };  // end( class const_iterator )

 };  // end( class FlatHashTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* FlatHashTable.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File FlatHashTable.h ------------------------*/
/*--------------------------------------------------------------------------*/