Program Listing for File ConcurrentCuckooTable.h
↰ Return to documentation for file (ADS/concurrent/ConcurrentCuckooTable.h)
/*--------------------------------------------------------------------------*/
/*---------------------- File ConcurrentCuckooTable.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
#ifndef __ADS_ConcurrentCuckooTable
#define __ADS_ConcurrentCuckooTable
/* self-identification: #endif constant */
/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/
#include "ADS/Contract.h"
#include "ADS/dictionary/BucketCuckooTable.h"
#include "ADS/dictionary/FastHash.h"
#include "ADS/memory/HugePageAllocator.h"
#include <atomic>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <optional>
#include <type_traits>
#include <vector>
/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/
namespace ADS {
/*--------------------------------------------------------------------------*/
/*---------------------- CLASS ConcurrentCuckooTable -----------------------*/
/*--------------------------------------------------------------------------*/
template< class K , class V , class H = DefaultHash< K > ,
class Eq = std::equal_to< K > >
class ConcurrentCuckooTable {
/*--------------------------------------------------------------------------*/
public:
using Key = K;
using Value = V;
explicit ConcurrentCuckooTable( std::size_t n = 0 , H h = H() ,
Eq eq = Eq() );
ConcurrentCuckooTable( const ConcurrentCuckooTable & ) = delete;
ConcurrentCuckooTable & operator=( const ConcurrentCuckooTable & ) =
delete;
[[nodiscard]] std::optional< V > find( const K & k ) const;
[[nodiscard]] bool contains( const K & k ) const;
bool insert( const K & k , const V & v );
bool insertOrAssign( const K & k , const V & v );
template< class F >
bool update( const K & k , F && f );
bool erase( const K & k );
[[nodiscard]] std::size_t size( void ) const;
[[nodiscard]] bool empty( void ) const;
[[nodiscard]] std::size_t capacity( void ) const;
[[nodiscard]] std::size_t rehashes( void ) const;
void reserve( std::size_t n );
void clear( void );
template< class F >
void forEach( F && f );
template< class F >
void forEach( F && f ) const;
[[nodiscard]] bool consistent( void ) const;
/*--------------------------------------------------------------------------*/
private:
template< class T >
static constexpr std::size_t refAlign( void ) {
if constexpr( std::is_trivially_copyable_v< T > )
return( std::atomic_ref< T >::required_alignment );
else
return( alignof( T ) );
}
template< class T >
static constexpr bool refLockFree( void ) {
if constexpr( std::is_trivially_copyable_v< T > )
return( std::atomic_ref< T >::is_always_lock_free );
else
return( false );
}
public:
static constexpr bool optimistic = refLockFree< K >() &&
refLockFree< V >();
/*--------------------------------------------------------------------------*/
private:
struct Slot {
alignas( refAlign< K >() ) K key{};
alignas( refAlign< V >() ) V value{};
};
static constexpr std::size_t line = 64;
struct alignas( ( 4 * sizeof( Slot ) <= line ) &&
std::has_single_bit( 4 * sizeof( Slot ) ) ?
4 * sizeof( Slot ) : alignof( Slot ) ) Bucket {
Slot s[ 4 ];
};
static constexpr std::size_t kStripes = 2048;
static constexpr int kLgStripes = 11;
static constexpr int kLgRegion = 8;
static constexpr int kDepth = 5;
static constexpr int kNodes = 1024;
struct alignas( line ) Stripe {
std::atomic< std::uint64_t > version{ 0 };
std::atomic< std::int64_t > count{ 0 };
};
struct Table {
int lg , rg;
std::uint32_t * T;
Bucket * B;
explicit Table( int l );
Table( const Table & ) = delete;
Table & operator=( const Table & ) = delete;
~Table();
[[nodiscard]] Slot & S( std::size_t i ) const {
return( B[ i >> 2 ].s[ i & 3 ] );
}
[[nodiscard]] std::size_t buckets( void ) const {
return( std::size_t( 1 ) << lg );
}
};
class Hold {
public:
explicit Hold( Stripe & s ) : f_s( s ) {}
Hold( const Hold & ) = delete;
Hold & operator=( const Hold & ) = delete;
~Hold() { unlock( f_s ); }
private:
Stripe & f_s;
};
class HoldAll {
public:
explicit HoldAll( const ConcurrentCuckooTable & t );
HoldAll( const HoldAll & ) = delete;
HoldAll & operator=( const HoldAll & ) = delete;
~HoldAll();
void extend( int lg );
[[nodiscard]] std::size_t held( void ) const { return( f_n ); }
private:
Stripe * f_L;
std::size_t f_n = 0;
};
struct Node {
std::size_t b;
int parent , from , depth;
std::uint32_t tag;
};
static void lock( Stripe & s );
static void unlock( Stripe & s );
[[nodiscard]] static int regionLg( int lg );
[[nodiscard]] std::uint64_t hash( const K & k ) const;
[[nodiscard]] static std::uint32_t tag( std::uint64_t h );
[[nodiscard]] static std::size_t first( std::uint64_t h , int lg );
[[nodiscard]] static std::size_t other( std::size_t b , std::uint32_t t ,
int rg );
[[nodiscard]] static std::uint32_t tags( const Table & T , std::size_t b );
static void setTags( Table & T , std::size_t b , std::uint32_t w );
[[nodiscard]] Table * lockRegion( std::uint64_t h ) const;
[[nodiscard]] std::size_t locate( const Table & T , const K & k ,
std::uint32_t t , std::size_t b1 ,
std::size_t b2 ) const;
static void fetch( const Table & T , std::size_t b1 , std::size_t b2 );
int peek( const K & k , std::uint64_t h , V * out ) const;
[[nodiscard]] static int freePlace( const Table & T , std::size_t b );
template< class KK , class VV >
static void put( Table & T , std::size_t b , int i , std::uint32_t t ,
KK && k , VV && v );
static void assign( Table & T , std::size_t i , const V & v );
static void clearPlace( Table & T , std::size_t i );
static void move( Table & T , std::size_t a , int i , std::size_t d ,
int j );
[[nodiscard]] int search( const Table & T , std::uint64_t h ,
Node * N ) const;
std::size_t makeRoom( Table & T , std::uint64_t h ) const;
std::size_t room( Table & T , std::uint64_t h , std::int64_t n ) const;
bool placeInto( Table & N , std::uint64_t h , Slot && x ) const;
bool add( const K & k , const V & v , bool assign );
void rehash( int lg , HoldAll & g );
void grow( int lg );
[[nodiscard]] bool inBucket( const Table & T , std::size_t b ) const;
std::unique_ptr< Stripe[] > f_L;
std::atomic< int > f_lg{ 1 };
std::atomic< Table * > f_table{ nullptr };
std::vector< std::unique_ptr< Table > > f_old;
std::unique_ptr< Table > f_cur;
std::atomic< std::size_t > f_rehashes{ 0 };
H f_h;
Eq f_eq;
}; // end( class ConcurrentCuckooTable )
/*--------------------------------------------------------------------------*/
} // end( namespace ADS )
/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/
#include "ADS/concurrent/impl/ConcurrentCuckooTable.tpp"
/*--------------------------------------------------------------------------*/
#endif /* ConcurrentCuckooTable.h included */
/*--------------------------------------------------------------------------*/