/*
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
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 ( pCur->level_unlinked() ) {
- 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
- help_remove( nLevel, pPred, pCur, pSucc );
+ 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
- help_remove( nLevel, pPred, pCur, pSucc );
+ 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
- help_remove( nLevel, pPred, pCur, pSucc );
+ 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>
// Insert at level 0
{
marked_node_ptr p( pos.pSucc[0] );
- pNode->next( 0 ).store( p, memory_model::memory_order_relaxed );
+ 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;
marked_node_ptr pSucc( pos.pSucc[nLevel] );
// Set pNode->next
- // pNode->next must be null but can have a "logical deleted" flag if another thread is removing pNode right now
+ // 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_acq_rel, atomics::memory_order_acquire ))
+ 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() != 0 );
- if ( pNode->level_unlinked( nHeight - nLevel )) {
- gc::retire( node_traits::to_value_ptr( pNode ), dispose_node );
- m_Stat.onEraseWhileInsert();
- }
- else
- m_Stat.onLogicDeleteWhileInsert();
+ // 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;
// 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;
}
}
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 )
+ memory_model::memory_order_release, atomics::memory_order_acquire )
|| pSucc.bits() != 0 ))
{
bkoff();
while ( true ) {
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;
- unsigned nCount = 0;
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 ))
{
- // Maybe, another threads already helped us to delete the node?..
- if ( nCount ) {
- if ( pDel->level_unlinked( nCount )) {
- gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
- m_Stat.onFastEraseHelped();
- return true;
- }
- }
-
+ 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;
}
- ++nCount;
}
// Fast erasing success
m_Stat.onFastErase();
return true;
}
- else if ( p.bits() ) {
+ else if ( p.bits()) {
// Another thread is deleting pDel right now
+ m_Stat.onEraseContention();
return false;
}
m_Stat.onEraseRetry();
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() ) {
+ if ( pCur.bits()) {
// pPred is being removed
if ( ++attempt < 4 ) {
bkoff();
return find_fastpath_abort;
}
- if ( pCur.ptr() ) {
+ if ( pCur.ptr()) {
int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
if ( nCmp < 0 ) {
guards.copy( 0, 1 );
}
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 {
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();
//@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