-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ 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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
#ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
#define CDSLIB_INTRUSIVE_TREIBER_STACK_H
operation()
: pVal( nullptr )
- , nStatus(0)
- {}
+ {
+ nStatus.store( 0 /*op_free*/, atomics::memory_order_release );
+ }
};
//@endcond
{
typedef typename Traits::back_off back_off;
- back_off m_bkoff;
+ struct wrapper
+ {
+ back_off m_bkoff;
+
+ void reset()
+ {
+ m_bkoff.reset();
+ }
+
+ template <typename Stat>
+ bool backoff( treiber_stack::operation< T >&, Stat& )
+ {
+ m_bkoff();
+ return false;
+ }
+ };
+
public:
elimination_backoff()
{}
elimination_backoff( size_t )
{}
- void reset()
- {
- m_bkoff.reset();
- }
-
- template <typename Stat>
- bool backoff(treiber_stack::operation< T >&, Stat& )
+ typedef wrapper type;
+ type init()
{
- m_bkoff();
- return false;
+ return wrapper();
}
};
/// Elimination back-off data
struct elimination_data {
- elimination_random_engine randEngine; ///< random engine
- collision_array collisions; ///< collision array
+ mutable elimination_random_engine randEngine; ///< random engine
+ collision_array collisions; ///< collision array
elimination_data()
{
typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
+ }
+
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< !Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
+ }
+
public:
elimination_backoff()
{
m_Elimination.collisions.zeroize();
}
+ typedef elimination_backoff& type;
+
+ type init()
+ {
+ return *this;
+ }
+
void reset()
{}
bool backoff( operation_desc& op, Stat& stat )
{
elimination_backoff_type bkoff;
- op.nStatus.store( op_busy, atomics::memory_order_relaxed );
+ op.nStatus.store( op_busy, atomics::memory_order_release );
elimination_rec * myRec = cds::algo::elimination::init_record( op );
- collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
+ collision_array_record& slot = m_Elimination.collisions[ slot_index() ];
{
slot.lock.lock();
elimination_rec * himRec = slot.pRec;
else
op.pVal = himOp->pVal;
slot.pRec = nullptr;
+ himOp->nStatus.store( op_collided, atomics::memory_order_release );
slot.lock.unlock();
- himOp->nStatus.store( op_collided, atomics::memory_order_release );
cds::algo::elimination::clear_record();
stat.onActiveCollision( op.idOp );
return true;
stat m_stat; ///< Internal statistics
//@cond
- treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
+ typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
+ elimination_backoff m_Backoff;
- typedef intrusive::node_to_value<TreiberStack> node_to_value;
typedef treiber_stack::operation< value_type > operation_desc;
// GC and node_type::gc must be the same
node_type * pNew = node_traits::to_node_ptr( val );
link_checker::is_empty( pNew );
- m_Backoff.reset();
+ typename elimination_backoff::type bkoff = m_Backoff.init();
operation_desc op;
if ( enable_elimination ) {
node_type * t = m_Top.load(memory_model::memory_order_relaxed);
while ( true ) {
pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
- if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) { // #1 sync-with #2
+ if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
++m_ItemCounter;
m_stat.onPush();
return true;
}
m_stat.onPushRace();
- if ( m_Backoff.backoff( op, m_stat ))
+ if ( bkoff.backoff( op, m_stat ))
return true;
}
}
*/
value_type * pop()
{
- m_Backoff.reset();
+ typename elimination_backoff::type bkoff = m_Backoff.init();
typename gc::Guard guard;
operation_desc op;
}
while ( true ) {
- node_type * t = guard.protect( m_Top, node_to_value() );
+ node_type * t = guard.protect( m_Top,
+ []( node_type * p ) -> value_type * {
+ return node_traits::to_value_ptr( p );
+ });
if ( t == nullptr )
return nullptr; // stack is empty
node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
- if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { // #2
+ if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
clear_links( t );
--m_ItemCounter;
m_stat.onPop();
}
m_stat.onPopRace();
- if ( m_Backoff.backoff( op, m_stat )) {
+ if ( bkoff.backoff( op, m_stat )) {
// may return nullptr if stack is empty
return op.pVal;
}
/// Check if stack is empty
bool empty() const
{
- // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0
return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
}
pTop = m_Top.load( memory_model::memory_order_relaxed );
if ( pTop == nullptr )
return;
- if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) { // sync-with #1 and #2
+ if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
m_ItemCounter.reset();
break;
}
projects / libcds.git / blobdiff