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.
If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
refer to the same thing.
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
i.e. the node has been inserted or updated,
\p second is \p true if new item has been added or \p false if the item with \p key
already exists.
{
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.
projects / libcds.git / blobdiff