Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
-
+
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
protected:
static value_type * gc_protect( marked_ptr p )
{
- return node_traits::to_value_ptr( p.ptr() );
+ return node_traits::to_value_ptr( p.ptr());
}
void next()
back_off bkoff;
for (;;) {
- if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
+ if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
// Current node is marked as deleted. So, its next pointer can point to anything
// In this case we interrupt our iteration and returns end() iterator.
*this = iterator();
marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
node_type * pp = p.ptr();
- if ( p.bits() ) {
+ if ( p.bits()) {
// p is marked as deleted. Spin waiting for physical removal
bkoff();
continue;
}
- else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits() ) {
+ else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits()) {
// p is marked as deleted. Spin waiting for physical removal
bkoff();
continue;
for (;;) {
marked_ptr p = m_guard.protect( refHead[0], gc_protect );
- if ( !p.ptr() ) {
+ if ( !p.ptr()) {
// empty skip-list
m_guard.clear();
break;
node_type * pp = p.ptr();
// Logically deleted node is marked from highest level
- if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
+ if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
m_pNode = pp;
break;
}
iterator( iterator const& s)
: m_pNode( s.m_pNode )
{
- m_guard.assign( node_traits::to_value_ptr(m_pNode) );
+ m_guard.assign( node_traits::to_value_ptr(m_pNode));
}
value_type * operator ->() const
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 )
{
assert( pVal != nullptr );
- typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
+ typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal));
disposer()( pVal );
}
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.
- marked_node_ptr p( pCur.ptr() );
- if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
+ 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 );
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
m_Stat.onEraseWhileFind();
}
}
// 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.
- marked_node_ptr p( pCur.ptr() );
- if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
+ 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 );
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
m_Stat.onEraseWhileFind();
}
}
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.
- marked_node_ptr p( pCur.ptr() );
- if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
+ 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 );
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
m_Stat.onEraseWhileFind();
}
}
goto retry;
}
else {
- if ( !pSucc.ptr() )
+ if ( !pSucc.ptr())
break;
pPred = pCur.ptr();
if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
// pNode has been marked as removed while we are inserting it
// Stop inserting
- assert( p.bits() );
+ assert( p.bits());
m_Stat.onLogicDeleteWhileInsert();
return true;
}
}
while ( true ) {
- marked_node_ptr p( pDel->next(0).load(memory_model::memory_order_relaxed).ptr() );
+ 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 ))
{
f( *node_traits::to_value_ptr( 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) )
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed))
{
// Make slow erase
find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
return true;
}
else {
- if ( p.bits() ) {
+ if ( p.bits()) {
// Another thread is deleting pDel right now
return false;
}
continue;
while ( pCur != pNull ) {
- if ( pCur.bits() ) {
+ if ( pCur.bits()) {
unsigned int nAttempt = 0;
while ( pCur.bits() && nAttempt++ < 16 ) {
bkoff();
}
bkoff.reset();
- if ( pCur.bits() ) {
+ if ( pCur.bits()) {
// Maybe, we are on deleted node sequence
// Abort searching, try slow-path
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
}
template <typename Q, typename Compare>
- bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+ guarded_ptr get_with_( Q const& val, Compare cmp )
{
- return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
+ guarded_ptr gp;
+ if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } ))
+ return gp;
+ return guarded_ptr();
}
template <typename Q, typename Compare, typename Func>
{
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();
}
template <typename Q, typename Compare>
- bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+ guarded_ptr extract_( Q const& val, Compare cmp )
{
position pos;
+ guarded_ptr gp;
for (;;) {
- if ( !find_position( val, pos, cmp, false ) ) {
+ if ( !find_position( val, pos, cmp, false )) {
m_Stat.onExtractFailed();
- guard.clear();
- return false;
+ return guarded_ptr();
}
node_type * pDel = pos.pCur;
- guard.set( 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();
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractSuccess();
- return true;
+ return gp;
}
m_Stat.onExtractRetry();
}
}
- bool extract_min_( typename guarded_ptr::native_guard& gDel )
+ guarded_ptr extract_min_()
{
position pos;
+ guarded_ptr gp;
for (;;) {
- if ( !find_min_position( pos ) ) {
+ if ( !find_min_position( pos )) {
// The list is empty
m_Stat.onExtractMinFailed();
- gDel.clear();
- return false;
+ return guarded_ptr();
}
node_type * pDel = pos.pCur;
unsigned int nHeight = pDel->height();
- gDel.set( node_traits::to_value_ptr(pDel) );
+ gp.reset( node_traits::to_value_ptr(pDel));
if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractMinSuccess();
- return true;
+ return gp;
}
m_Stat.onExtractMinRetry();
}
}
- bool extract_max_( typename guarded_ptr::native_guard& gDel )
+ guarded_ptr extract_max_()
{
position pos;
+ guarded_ptr gp;
for (;;) {
- if ( !find_max_position( pos ) ) {
+ if ( !find_max_position( pos )) {
// The list is empty
m_Stat.onExtractMaxFailed();
- gDel.clear();
- return false;
+ return guarded_ptr();
}
node_type * pDel = pos.pCur;
unsigned int nHeight = pDel->height();
- gDel.set( node_traits::to_value_ptr(pDel) );
+ gp.reset( node_traits::to_value_ptr(pDel));
if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractMaxSuccess();
- return true;
+ return gp;
}
m_Stat.onExtractMaxRetry();
may be thrown if the limit of guard count per thread is exceeded.
- The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
- Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
- deleting operations there is no guarantee that you iterate all item in the list.
+ deleting operations there is no guarantee that you iterate all item in the list.
Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
@warning Use this iterator on the concurrent container for debugging purpose only.
/// Returns a forward iterator addressing the first element in a set
iterator begin()
{
- return iterator( *m_Head.head() );
+ return iterator( *m_Head.head());
}
/// Returns a forward const iterator addressing the first element in a set
const_iterator begin() const
{
- return const_iterator( *m_Head.head() );
+ return const_iterator( *m_Head.head());
}
/// Returns a forward const iterator addressing the first element in a set
const_iterator cbegin() const
{
- return const_iterator( *m_Head.head() );
+ return const_iterator( *m_Head.head());
}
/// Returns a forward iterator that addresses the location succeeding the last element in a set.
{
position pos;
- if ( !find_position( val, pos, key_comparator(), false ) ) {
+ if ( !find_position( val, pos, key_comparator(), false )) {
m_Stat.onUnlinkFailed();
return false;
}
unsigned int nHeight = pDel->height();
typename gc::Guard gDel;
- gDel.assign( node_traits::to_value_ptr(pDel) );
+ gDel.assign( node_traits::to_value_ptr(pDel));
if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
--m_ItemCounter;
template <typename Q>
guarded_ptr extract( Q const& key )
{
- guarded_ptr gp;
- extract_( gp.guard(), key, key_comparator() );
- return gp;
+ return extract_( key, key_comparator());
}
/// Extracts the item from the set with comparing functor \p pred
guarded_ptr extract_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- guarded_ptr gp;
- extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
- return gp;
+ return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Extracts an item with minimal key from the list
*/
guarded_ptr extract_min()
{
- guarded_ptr gp;
- extract_min_( gp.guard() );
- return gp;
+ return extract_min_();
}
/// Extracts an item with maximal key from the list
*/
guarded_ptr extract_max()
{
- guarded_ptr gp;
- extract_max_( gp.guard() );
- return gp;
+ return extract_max_();
}
/// Deletes the item from the set
template <typename Q>
guarded_ptr get( Q const& key )
{
- guarded_ptr gp;
- get_with_( gp.guard(), key, key_comparator() );
- return gp;
+ return get_with_( key, key_comparator());
}
/// Finds \p key and return the item found
guarded_ptr get_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- guarded_ptr gp;
- get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
- return gp;
+ return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Returns item count in the set
this sequence
\code
set.clear();
- assert( set.empty() );
+ assert( set.empty());
\endcode
the assertion could be raised.
*/
void clear()
{
- guarded_ptr gp;
- while ( extract_min_( gp.guard() ));
+ while ( extract_min_());
}
/// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.