Program Listing for File OpenHashTable.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File OpenHashTable.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <atomic>
#include <concepts>
#include <cstddef>
#include <functional>
#include <numeric>
#include <optional>
#include <random>
#include <stdexcept>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS Probing ------------------------------*/
/*--------------------------------------------------------------------------*/

class Probing {

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

 enum class Kind { LINEAR , QUADRATIC , DOUBLE , TRIANGULAR , RANDOM };

 using Step = std::function< std::size_t( std::size_t ) >;

 static Probing linear( long delta = 1 );

 static Probing quadratic( long c1 , long c2 );

 static Probing double_hashing( void );

 static Probing double_hashing( Step g );

 static Probing triangular( void );

 static Probing pseudo_random( unsigned long seed = 1 );

 [[nodiscard]] Kind kind( void ) const;

 [[nodiscard]] std::size_t at( std::size_t h , std::size_t i ,
                               std::size_t m ) const;

 [[nodiscard]] static std::size_t step( std::size_t h , std::size_t m );

 [[nodiscard]] std::size_t stride( std::size_t h , std::size_t m ) const;

 [[nodiscard]] bool works( std::size_t m ) const;

 void check( std::size_t m ) const;

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

 Probing( Kind k , long c1 , long c2 );

 static std::size_t mod( long c , std::size_t m );

 const std::vector< std::size_t > & permutation( std::size_t m ) const;

 Kind f_kind;
 long f_c1;
 long f_c2;
 Step f_g;
 unsigned long f_seed = 0;
 mutable std::vector< std::size_t > f_p;
 mutable std::size_t f_m = 0;

 };  // end( class Probing )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS OpenHashTable ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class K , class V , class H = std::hash< K > >
class OpenHashTable {

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

 using Key = K;
 using Value = V;

 enum class Slot { NIL , FULL , DELETED };

 OpenHashTable( std::size_t m , Probing probe , bool restructure = false ,
                H h = H() );

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

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

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

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

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

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

 [[nodiscard]] const K & keyAt( std::size_t i ) const;

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

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

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

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

 // a constant view of the pairs ( key , value ), in the order of the
 // places, bidirectional; it skips the empty and the deleted places, and a
 // rebuild after an insertion or a removal invalidates it

 struct Places {
  static std::size_t size( const auto & o ) { return( o.f_T.size() ); }
  static bool occupied( const auto & o , std::size_t i ) {
   return( o.f_T[ i ].slot == Slot::FULL );
   }
  static auto read( const auto & o , std::size_t i ) {
   return( std::pair< const K & , const V & >( o.f_T[ i ].key ,
                                              o.f_T[ i ].value ) );
   }
  };

 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 & >;
 using const_iterator = SlotIterator< OpenHashTable , 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 Cell {
  Slot slot = Slot::NIL;
  K key{};
  V value{};
  };

 [[nodiscard]] bool is( std::size_t i , const K & k ) const;

 std::size_t scan( const K & k , bool insert ) const;

 [[nodiscard]] std::size_t where( const K & k ) const;

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

 void rebuild( std::size_t m );

 std::vector< Cell > f_T;
 Probing f_probe;
 std::size_t f_m0;
 std::size_t f_linear = 0;
 bool f_restructure;
 H f_h;
 std::size_t f_size = 0;
 std::size_t f_deleted = 0;
 struct Probes {
  std::atomic< std::size_t > n{ 0 };
  Probes( void ) = default;
  Probes( const Probes & o ) : n( o.n.load( std::memory_order_relaxed ) ) {}
  Probes & operator=( const Probes & o ) {
   n.store( o.n.load( std::memory_order_relaxed ) ,
            std::memory_order_relaxed );
   return( *this );
   }
  };
 mutable Probes f_probes;
 std::size_t f_rebuilds = 0;
 std::size_t f_moved = 0;

 };  // end( class OpenHashTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* OpenHashTable.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File OpenHashTable.h ------------------------*/
/*--------------------------------------------------------------------------*/