/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
/// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
+ typedef typename traits::bit_reversal bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal
typedef typename traits::item_counter item_counter; ///< Item counter type
typedef typename traits::back_off back_off; ///< back-off strategy for spinning
typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
*/
SplitListSet()
: m_nBucketCountLog2(1)
- , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
+ , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
{
init();
}
)
: m_Buckets( nItemCount, nLoadFactor )
, m_nBucketCountLog2(1)
- , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
+ , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
{
init();
}
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
+ node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
if ( m_List.insert_at( pHead, val )) {
inc_item_count();
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
+ node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
if ( m_List.insert_at( pHead, val, f )) {
inc_item_count();
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
+ node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
if ( bRet.first && bRet.second ) {
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- if ( m_List.unlink_at( pHead, val ) ) {
+ if ( m_List.unlink_at( pHead, val )) {
--m_ItemCounter;
m_Stat.onEraseSuccess();
return true;
template <typename Q>
bool erase( Q const& key )
{
- return erase_( key, key_comparator() );
+ return erase_( key, key_comparator());
}
/// Deletes the item from the set using \p pred for searching
bool erase_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>() );
+ return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
}
/// Deletes the item from the set
template <typename Q>
exempt_ptr extract( Q const& key )
{
- return exempt_ptr(extract_( key, key_comparator() ));
+ return exempt_ptr(extract_( key, key_comparator()));
}
/// Extracts an item from the set using \p pred for searching
template <typename Q>
bool contains( Q const& key )
{
- return find_value( key, key_comparator() );
+ return find_value( key, key_comparator());
}
//@cond
template <typename Q>
bool contains( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return find_value( key, typename ordered_list_adapter::template make_compare_from_less<Less>() );
+ return find_value( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
}
//@cond
template <typename Q, typename Less>
template <typename Q>
raw_ptr get( Q const& key )
{
- return get_( key, key_comparator() );
+ return get_( key, key_comparator());
}
/// Finds the key \p key and return the item found
void clear()
{
iterator it = begin();
- while ( it != end() ) {
+ while ( it != end()) {
iterator i(it);
++i;
unlink( *it );
return m_Stat;
}
+ /// Returns internal statistics for \p OrderedList
+ typename OrderedList::stat const& list_statistics() const
+ {
+ return m_List.statistics();
+ }
+
protected:
//@cond
template <bool IsConst>
*/
iterator begin()
{
- return iterator( m_List.begin(), m_List.end() );
+ return iterator( m_List.begin(), m_List.end());
}
/// Returns an iterator that addresses the location succeeding the last element in a split-list
*/
iterator end()
{
- return iterator( m_List.end(), m_List.end() );
+ return iterator( m_List.end(), m_List.end());
}
/// Returns a forward const iterator addressing the first element in a split-list
/// Returns a forward const iterator addressing the first element in a split-list
const_iterator cbegin() const
{
- return const_iterator( m_List.cbegin(), m_List.cend() );
+ return const_iterator( m_List.cbegin(), m_List.cend());
}
/// Returns an const iterator that addresses the location succeeding the last element in a split-list
/// Returns an const iterator that addresses the location succeeding the last element in a split-list
const_iterator cend() const
{
- return const_iterator( m_List.cend(), m_List.cend() );
+ return const_iterator( m_List.cend(), m_List.cend());
}
//@}
static size_t parent_bucket( size_t nBucket )
{
assert( nBucket > 0 );
- return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
+ return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
}
aux_node_type * init_bucket( size_t const nBucket )
aux_node_type * pBucket = m_Buckets.bucket( nBucket );
back_off bkoff;
- for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) {
+ for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
if ( pBucket )
return pBucket;
- pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
+ pBucket = alloc_aux_node( split_list::dummy_hash<bit_reversal>( nBucket ));
if ( pBucket ) {
- if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
+ if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
m_Buckets.bucket( nBucket, pBucket );
m_Stat.onNewBucket();
return pBucket;
}
// Another thread set the bucket. Wait while it done
- for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) {
+ for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
bkoff();
m_Stat.onBusyWaitBucketInit();
}
if ( pHead == nullptr )
pHead = init_bucket( nBucket );
- assert( pHead->is_dummy() );
+ assert( pHead->is_dummy());
return pHead;
}
void init()
{
// Initialize bucket 0
- aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
+ aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash<bit_reversal>(0)*/ );
// insert_aux_node cannot return false for empty list
CDS_VERIFY( m_List.insert_aux_node( pNode ));
size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
const size_t nBucketCount = static_cast<size_t>(1) << sz;
- if ( nBucketCount < m_Buckets.capacity() ) {
+ if ( nBucketCount < m_Buckets.capacity()) {
// we may grow the bucket table
const size_t nLoadFactor = m_Buckets.load_factor();
if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
bool find_( Q& val, Compare cmp, Func f )
{
size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
+ split_list::details::search_value_type<Q> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
bool find_value( Q const& val, Compare cmp )
{
size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
raw_ptr get_( Q const& val, Compare cmp )
{
size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
value_type * extract_( Q const& val, Compare cmp )
{
size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
bool erase_( const Q& val, Compare cmp )
{
size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- if ( m_List.erase_at( pHead, sv, cmp ) ) {
+ if ( m_List.erase_at( pHead, sv, cmp )) {
--m_ItemCounter;
m_Stat.onEraseSuccess();
return true;
bool erase_( Q const& val, Compare cmp, Func f )
{
size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics accumulator
//@endcond
};