Program Listing for File DenseHashMap.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File DenseHashMap.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS DenseHashMap ---------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Key = K;
 using Value = V;

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

 DenseHashMap( const DenseHashMap & o );

 DenseHashMap( DenseHashMap && o ) noexcept;

 DenseHashMap & operator=( DenseHashMap o ) noexcept;

 ~DenseHashMap() = default;

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

 [[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;

 [[nodiscard]] const std::pair< K , V > * data( void ) const;

 void swap( DenseHashMap & o ) noexcept;

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

 // a constant view of the pairs, in the order of the vector, random
 // access; an insertion of a new key or a removal invalidates them

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

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

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

 static constexpr std::uint8_t EMPTY = 0;
 static constexpr std::size_t SLOTS = 12;
 static constexpr std::size_t OVER = 15;
 static constexpr std::uint32_t PLACES = 0xFFF;

 struct alignas( 64 ) Group {
  std::uint8_t c[ 16 ];
  std::uint32_t at[ SLOTS ];
  };

 using Mask = std::uint32_t;

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

 inline static Group s_none[ 2 ] = {};

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

 [[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 );

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

 [[nodiscard]] std::size_t locate( std::uint64_t x , 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 std::pair< std::size_t , std::size_t > further(
                    std::uint64_t x , std::size_t g , KeyArg k ) const;

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

 std::uint32_t & holder( std::uint64_t x , std::size_t p );

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

 void unlink( Group & g , std::size_t j , std::size_t p );

 void rebuild( std::size_t G );

 ADS_FLAT_NOINLINE bool recount( void );

 ADS_FLAT_NOINLINE void grow( void );

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

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

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

 struct Free {
  void operator()( Group * g ) const noexcept;
  };

 std::vector< std::pair< K , V > > f_kv;
 std::unique_ptr< Group[] , Free > f_g;
 Group * f_ctrl = s_none;
 std::size_t f_mask = 0;
 std::size_t f_cap = 0;
 int f_shift = 63;
 std::size_t f_max = 0;
 std::size_t f_deleted = 0;
 H f_h;
 Eq f_eq;

 };  // end( class DenseHashMap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* DenseHashMap.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File DenseHashMap.h -------------------------*/
/*--------------------------------------------------------------------------*/