Program Listing for File PointerTable.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File PointerTable.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <bit>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <utility>
#include <vector>

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

namespace ADS {

struct StateEqual {
 template< class P , class K >
 bool operator()( const P * p , const K & key ) const {
  return( p->state == key );
  }
 };

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS PointerTable ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Eq = StateEqual ,
          class A = std::allocator< std::byte > >
class PointerTable {

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

 explicit PointerTable( std::size_t capacity = 16 , Eq eq = Eq() ,
                        const A & alloc = A() );

 PointerTable( const PointerTable & ) = default;
 PointerTable & operator=( const PointerTable & ) = default;

 PointerTable( PointerTable && o ) noexcept;
 PointerTable & operator=( PointerTable && o ) noexcept;

 void clear( void );

 void reserve( std::size_t n );

 template< class K , class Make >
 std::pair< T * , bool > find_or_insert( const K & key ,
                                         std::uint64_t hash , Make && make );

 template< class K >
 [[nodiscard]] T * find( const K & key , std::uint64_t hash ) const;

 void prefetch( std::uint64_t hash ) const;

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

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

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

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

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

 // a view of the pointers to the objects, in the order of the places,
 // bidirectional; the key of an object must not change through it, and an
 // insertion that grows the table invalidates it

 struct Places {
  static std::size_t size( const auto & o ) { return( o.f_S.size() ); }
  static bool occupied( const auto & o , std::size_t i ) {
   return( o.f_S[ i ].p != nullptr );
   }
  static auto read( const auto & o , std::size_t i ) {
   return( o.f_S[ i ].p );
   }
  };

 using value_type = T *;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = T *;
 using const_reference = T *;
 using const_iterator = SlotIterator< PointerTable , Places >;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , Places::size( *this ) ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 struct Slot {
  std::uint64_t hash = 0;
  T * p = nullptr;
  };

 using SA = typename std::allocator_traits< A >::template
            rebind_alloc< Slot >;

 [[nodiscard]] std::size_t place( std::uint64_t hash ) const;

 void reset( std::size_t m );

 void grow( void );

 template< class K >
 [[nodiscard]] bool reached( const K & key , std::uint64_t hash ) const;

 std::vector< Slot , SA > f_S;
 std::size_t f_mask = 0;
 int f_bits = 0;
 std::size_t f_size = 0;
 Eq f_eq;

 };  // end( class PointerTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* PointerTable.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File PointerTable.h -------------------------*/
/*--------------------------------------------------------------------------*/