/*
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/
// c_nMaxHeight * 2 - pPred/pSucc guards
// + 1 - for erase, unlink
// + 1 - for clear
- static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2; ///< Count of hazard pointer required for the skip-list
+ // + 1 - for help_remove()
+ static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list
protected:
typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
/// Clears and destructs the skip-list
~SkipListSet()
{
- clear();
+ destroy();
}
public:
static value_type * gc_protect( marked_node_ptr p )
{
- return node_traits::to_value_ptr( p.ptr() );
+ return node_traits::to_value_ptr( p.ptr());
}
- static void dispose_node( value_type * pVal )
+ static void dispose_node( void* p )
{
- assert( pVal != nullptr );
- typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ) );
+ assert( p != nullptr );
+ value_type* pVal = reinterpret_cast<value_type*>( p );
+ typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ));
disposer()( pVal );
}
- void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur, marked_node_ptr pSucc )
+ void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur )
{
- marked_node_ptr p( pCur.ptr() );
- if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
- {
- if ( nLevel == 0 ) {
- gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
- m_Stat.onEraseWhileFind();
+ if ( pCur->is_upper_level( nLevel )) {
+ marked_node_ptr p( pCur.ptr());
+ typename gc::Guard hp;
+ marked_node_ptr pSucc = hp.protect( pCur->next( nLevel ), gc_protect );
+
+ if ( pSucc.bits() &&
+ pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
+ {
+ if ( pCur->level_unlinked()) {
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
+ m_Stat.onEraseWhileFind();
+ }
}
}
}
int nCmp = 1;
for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
- pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
+ pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
while ( true ) {
pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
- if ( pCur.bits() ) {
+ if ( pCur.bits()) {
// pCur.bits() means that pPred is logically deleted
goto retry;
}
// pSucc contains deletion mark for pCur
pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
goto retry;
- if ( pSucc.bits() ) {
+ if ( pSucc.bits()) {
// pCur is marked, i.e. logically deleted
- // try to help deleting pCur if pSucc is not being deleted
- help_remove( nLevel, pPred, pCur, pSucc );
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
goto retry;
}
else {
- nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
+ nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
if ( nCmp < 0 ) {
pPred = pCur.ptr();
pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
pPred = m_Head.head();
for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
- pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
+ pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
// pCur.bits() means that pPred is logically deleted
// head cannot be deleted
assert( pCur.bits() == 0 );
- if ( pCur.ptr() ) {
+ if ( pCur.ptr()) {
// pSucc contains deletion mark for pCur
pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
goto retry;
- if ( pSucc.bits() ) {
+ if ( pSucc.bits()) {
// pCur is marked, i.e. logically deleted.
- // try to help deleting pCur if pSucc is not being deleted
- help_remove( nLevel, pPred, pCur, pSucc );
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
goto retry;
}
}
pos.pSucc[nLevel] = pCur.ptr();
}
- return ( pos.pCur = pCur.ptr() ) != nullptr;
+ return ( pos.pCur = pCur.ptr()) != nullptr;
}
bool find_max_position( position& pos )
pPred = m_Head.head();
for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
- pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
+ pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
while ( true ) {
pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
- if ( pCur.bits() ) {
+ if ( pCur.bits()) {
// pCur.bits() means that pPred is logically deleted
goto retry;
}
// pSucc contains deletion mark for pCur
pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
goto retry;
- if ( pSucc.bits() ) {
+ if ( pSucc.bits()) {
// pCur is marked, i.e. logically deleted.
- // try to help deleting pCur if pSucc is not being deleted
- help_remove( nLevel, pPred, pCur, pSucc );
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
goto retry;
}
else {
- if ( !pSucc.ptr() )
+ if ( !pSucc.ptr())
break;
pPred = pCur.ptr();
- pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );
+ pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );
+ }
+ }
+
+ // Next level
+ pos.pPrev[nLevel] = pPred;
+ pos.pSucc[nLevel] = pCur.ptr();
+ }
+
+ return ( pos.pCur = pCur.ptr()) != nullptr;
+ }
+
+ bool renew_insert_position( value_type& val, node_type * pNode, position& pos )
+ {
+ node_type * pPred;
+ marked_node_ptr pSucc;
+ marked_node_ptr pCur;
+ key_comparator cmp;
+
+ // Hazard pointer array:
+ // pPred: [nLevel * 2]
+ // pSucc: [nLevel * 2 + 1]
+
+ retry:
+ pPred = m_Head.head();
+ int nCmp = 1;
+
+ for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
+ pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
+ while ( true ) {
+ pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
+ if ( pCur.bits()) {
+ // pCur.bits() means that pPred is logically deleted
+ goto retry;
+ }
+
+ if ( pCur.ptr() == nullptr ) {
+ // end of list at level nLevel - goto next level
+ break;
+ }
+
+ // pSucc contains deletion mark for pCur
+ pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
+
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
+ goto retry;
+
+ if ( pSucc.bits()) {
+ // pCur is marked, i.e. logically deleted
+ if ( pCur.ptr() == pNode ) {
+ // Node is removing while we are inserting it
+ return false;
+ }
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
+ goto retry;
+ }
+ else {
+ nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
+ if ( nCmp < 0 ) {
+ pPred = pCur.ptr();
+ pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
+ }
+ else
+ break;
}
}
pos.pSucc[nLevel] = pCur.ptr();
}
- return ( pos.pCur = pCur.ptr() ) != nullptr;
+ return nCmp == 0;
}
template <typename Func>
bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
{
- unsigned int nHeight = pNode->height();
+ unsigned int const nHeight = pNode->height();
for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
pNode->next( nLevel ).store( marked_node_ptr(), memory_model::memory_order_relaxed );
// Insert at level 0
{
- node_type* succ = pos.pSucc[0];
-
- marked_node_ptr p( succ );
+ marked_node_ptr p( pos.pSucc[0] );
pNode->next( 0 ).store( p, memory_model::memory_order_release );
if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
return false;
for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
marked_node_ptr p;
while ( true ) {
- marked_node_ptr q( pos.pSucc[nLevel] );
+ marked_node_ptr pSucc( pos.pSucc[nLevel] );
- if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+ // Set pNode->next
+ // pNode->next can have "logical deleted" flag if another thread is removing pNode right now
+ if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc,
+ memory_model::memory_order_release, atomics::memory_order_acquire ))
+ {
// pNode has been marked as removed while we are inserting it
// Stop inserting
- assert( p.bits() );
+ assert( p.bits() != 0 );
+
+ // Here pNode is linked at least level 0 so level_unlinked() cannot returns true
+ CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
+
+ // pNode is linked up to nLevel - 1
+ // Remove it via find_position()
+ find_position( val, pos, key_comparator(), false );
+
m_Stat.onLogicDeleteWhileInsert();
return true;
}
+ p = pSucc;
- p = q;
- bool const result = pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( q, marked_node_ptr( pNode ),
- memory_model::memory_order_release, atomics::memory_order_relaxed );
- if ( result )
+ // Link pNode into the list at nLevel
+ if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( pSucc, marked_node_ptr( pNode ),
+ memory_model::memory_order_release, atomics::memory_order_relaxed ))
+ {
+ // go to next level
break;
+ }
// Renew insert position
m_Stat.onRenewInsertPosition();
- if ( !find_position( val, pos, key_comparator(), false ) ) {
+
+ if ( !renew_insert_position( val, pNode, pos )) {
// The node has been deleted while we are inserting it
- m_Stat.onNotFoundWhileInsert();
+ // Update current height for concurent removing
+ CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
+
+ m_Stat.onRemoveWhileInsert();
+
+ // help to removing val
+ find_position( val, pos, key_comparator(), false );
return true;
}
}
assert( pDel != nullptr );
marked_node_ptr pSucc;
+ back_off bkoff;
// logical deletion (marking)
for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
- while ( true ) {
- pSucc = pDel->next( nLevel );
- if ( pSucc.bits() || pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
- memory_model::memory_order_release, atomics::memory_order_relaxed ) )
+ pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
+ if ( pSucc.bits() == 0 ) {
+ bkoff.reset();
+ while ( !( pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
+ memory_model::memory_order_release, atomics::memory_order_acquire )
+ || pSucc.bits() != 0 ))
{
- break;
+ bkoff();
+ m_Stat.onMarkFailed();
}
}
}
+ marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr());
while ( true ) {
- marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr() );
- if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_relaxed ) )
+ if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_acquire ))
{
- f( *node_traits::to_value_ptr( pDel ) );
+ f( *node_traits::to_value_ptr( pDel ));
// Physical deletion
// try fast erase
p = pDel;
+
for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
- pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
- if ( !pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
+
+ pSucc = pDel->next( nLevel ).load( memory_model::memory_order_acquire );
+ if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
+ memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
{
+ pDel->level_unlinked();
+ }
+ else {
// Make slow erase
+# ifdef CDS_DEBUG
+ if ( find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ))
+ assert( pDel != pos.pCur );
+# else
find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
+# endif
m_Stat.onSlowErase();
return true;
}
m_Stat.onFastErase();
return true;
}
- else {
- if ( p.bits() ) {
- // Another thread is deleting pDel right now
- return false;
- }
+ else if ( p.bits()) {
+ // Another thread is deleting pDel right now
+ m_Stat.onEraseContention();
+ return false;
}
m_Stat.onEraseRetry();
+ bkoff();
}
}
finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
{
node_type * pPred;
- typename gc::template GuardArray<2> guards;
marked_node_ptr pCur;
marked_node_ptr pNull;
+ // guard array:
+ // 0 - pPred on level N
+ // 1 - pCur on level N
+ typename gc::template GuardArray<2> guards;
back_off bkoff;
+ unsigned attempt = 0;
+ try_again:
pPred = m_Head.head();
for ( int nLevel = static_cast<int>( m_nHeight.load( memory_model::memory_order_relaxed ) - 1 ); nLevel >= 0; --nLevel ) {
pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
- if ( pCur == pNull )
- continue;
while ( pCur != pNull ) {
- if ( pCur.bits() ) {
- unsigned int nAttempt = 0;
- bkoff.reset();
- while ( pCur.bits() && nAttempt++ < 16 ) {
+ if ( pCur.bits()) {
+ // pPred is being removed
+ if ( ++attempt < 4 ) {
bkoff();
- pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
+ goto try_again;
}
- if ( pCur.bits() ) {
- // Maybe, we are on deleted node sequence
- // Abort searching, try slow-path
- return find_fastpath_abort;
- }
+ return find_fastpath_abort;
}
- if ( pCur.ptr() ) {
- int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
+ if ( pCur.ptr()) {
+ int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
if ( nCmp < 0 ) {
guards.copy( 0, 1 );
pPred = pCur.ptr();
}
else if ( nCmp == 0 ) {
// found
- f( *node_traits::to_value_ptr( pCur.ptr() ), val );
+ f( *node_traits::to_value_ptr( pCur.ptr()), val );
return find_fastpath_found;
}
- else // pCur > val - go down
+ else {
+ // pCur > val - go down
break;
+ }
}
}
}
bool find_slowpath( Q& val, Compare cmp, Func f )
{
position pos;
- if ( find_position( val, pos, cmp, true ) ) {
+ if ( find_position( val, pos, cmp, true )) {
assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
f( *node_traits::to_value_ptr( pos.pCur ), val );
template <typename Q, typename Compare, typename Func>
bool find_with_( Q& val, Compare cmp, Func f )
{
- switch ( find_fastpath( val, cmp, f ) ) {
+ switch ( find_fastpath( val, cmp, f )) {
case find_fastpath_found:
m_Stat.onFindFastSuccess();
return true;
break;
}
- if ( find_slowpath( val, cmp, f ) ) {
+ if ( find_slowpath( val, cmp, f )) {
m_Stat.onFindSlowSuccess();
return true;
}
guarded_ptr get_with_( Q const& val, Compare cmp )
{
guarded_ptr gp;
- if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ) )
+ if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ))
return gp;
return guarded_ptr();
}
{
position pos;
- if ( !find_position( val, pos, cmp, false ) ) {
+ if ( !find_position( val, pos, cmp, false )) {
m_Stat.onEraseFailed();
return false;
}
node_type * pDel = pos.pCur;
typename gc::Guard gDel;
- gDel.assign( node_traits::to_value_ptr( pDel ) );
+ gDel.assign( node_traits::to_value_ptr( pDel ));
assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
unsigned int nHeight = pDel->height();
- if ( try_remove_at( pDel, pos, f ) ) {
+ if ( try_remove_at( pDel, pos, f )) {
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onEraseSuccess();
guarded_ptr gp;
for (;;) {
- if ( !find_position( val, pos, cmp, false ) ) {
+ if ( !find_position( val, pos, cmp, false )) {
m_Stat.onExtractFailed();
return guarded_ptr();
}
node_type * pDel = pos.pCur;
- gp.reset( node_traits::to_value_ptr( pDel ) );
+ gp.reset( node_traits::to_value_ptr( pDel ));
assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
unsigned int nHeight = pDel->height();
- if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
+ if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractSuccess();
guarded_ptr gp;
for ( ;;) {
- if ( !find_min_position( pos ) ) {
+ if ( !find_min_position( pos )) {
// The list is empty
m_Stat.onExtractMinFailed();
return guarded_ptr();
node_type * pDel = pos.pCur;
unsigned int nHeight = pDel->height();
- gp.reset( node_traits::to_value_ptr( pDel ) );
+ gp.reset( node_traits::to_value_ptr( pDel ));
- if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
+ if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractMinSuccess();
guarded_ptr gp;
for ( ;;) {
- if ( !find_max_position( pos ) ) {
+ if ( !find_max_position( pos )) {
// The list is empty
m_Stat.onExtractMaxFailed();
return guarded_ptr();
node_type * pDel = pos.pCur;
unsigned int nHeight = pDel->height();
- gp.reset( node_traits::to_value_ptr( pDel ) );
+ gp.reset( node_traits::to_value_ptr( pDel ));
- if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
+ if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractMaxSuccess();
{
unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
if ( nCur < nHeight )
- m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
+ m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
+ }
+
+ void destroy()
+ {
+ node_type* p = m_Head.head()->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
+ while ( p ) {
+ node_type* pNext = p->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
+ dispose_node( node_traits::to_value_ptr( p ));
+ p = pNext;
+ }
}
+
//@endcond
private:
//@cond
skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
- item_counter m_ItemCounter; ///< item counter
random_level_generator m_RandomLevelGen; ///< random level generator instance
atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
+ item_counter m_ItemCounter; ///< item counter
mutable stat m_Stat; ///< internal statistics
//@endcond
};
projects / libcds.git / blobdiff