Program Listing for File BucketCuckooTable.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File BucketCuckooTable.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <bit>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#include <optional>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS BucketCuckooTable -------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Key = K;
 using Value = V;

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

 [[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 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 rehashes( void ) const;

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

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

 struct Slot {
  K key{};
  V value{};
  };

 static constexpr int kDepth = 5;
 static constexpr std::size_t kNodes = 1024;

 public:

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

 // a constant view of the pairs ( key , value ), in the order of the
 // places, bidirectional

 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_T[ i >> 2 ] >> ( 8 * ( i & 3 ) ) ) & 0xFF );
   }
  static auto read( const auto & o , std::size_t i ) {
   return( std::pair< const K & , const V & >( o.f_S[ i ].key ,
                                              o.f_S[ 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< BucketCuckooTable , 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 , f_S.size() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

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

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

 [[nodiscard]] std::size_t first( std::uint64_t h ) const;

 [[nodiscard]] std::size_t other( std::size_t b , std::uint32_t t ) const;

 [[nodiscard]] std::size_t locate( const K & k , std::uint64_t h ) const;

 [[nodiscard]] int freePlace( std::size_t b ) const;

 template< class KK , class VV >
 void put( std::size_t b , int i , std::uint32_t t , KK && k , VV && v );

 std::size_t makeRoom( std::uint64_t h );

 void grow( void );

 template< class KK , class VV >
 bool place( std::uint64_t h , KK && k , VV && v );

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

 std::vector< std::uint32_t > f_T;
 std::vector< Slot > f_S;
 int f_lg = 1;
 std::size_t f_n = 0;
 std::size_t f_rehashes = 0;
 std::size_t f_moves = 0;
 H f_h;
 Eq f_eq;

 };  // end( class BucketCuckooTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BucketCuckooTable.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File BucketCuckooTable.h ----------------------*/
/*--------------------------------------------------------------------------*/