X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Ftreiber_stack.h;h=ab164016857a442abad1b21471e9d96e72526b16;hb=cd515d6402be81b84e2eb0c9d4cf0a1ca9e4d95a;hp=a7e5621b841e8bb8efa8bf38d173ed8c9f8b2ef8;hpb=3caf0699346f9cb714809664697aa29efc7eb429;p=libcds.git diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h index a7e5621b..ab164016 100644 --- a/cds/intrusive/treiber_stack.h +++ b/cds/intrusive/treiber_stack.h @@ -1,4 +1,32 @@ -//$$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 @@ -77,8 +105,9 @@ namespace cds { namespace intrusive { operation() : pVal( nullptr ) - , nStatus(0) - {} + { + nStatus.store( 0 /*op_free*/, atomics::memory_order_release ); + } }; //@endcond @@ -267,7 +296,23 @@ namespace cds { namespace intrusive { { typedef typename Traits::back_off back_off; - back_off m_bkoff; + struct wrapper + { + back_off m_bkoff; + + void reset() + { + m_bkoff.reset(); + } + + template + bool backoff( treiber_stack::operation< T >&, Stat& ) + { + m_bkoff(); + return false; + } + }; + public: elimination_backoff() {} @@ -275,16 +320,10 @@ namespace cds { namespace intrusive { elimination_backoff( size_t ) {} - void reset() - { - m_bkoff.reset(); - } - - template - bool backoff(treiber_stack::operation< T >&, Stat& ) + typedef wrapper type; + type init() { - m_bkoff(); - return false; + return wrapper(); } }; @@ -319,8 +358,8 @@ namespace cds { namespace intrusive { /// 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() { @@ -341,6 +380,18 @@ namespace cds { namespace intrusive { typedef std::unique_lock< elimination_lock_type > slot_scoped_lock; + template + typename std::enable_if< Exp2, size_t >::type slot_index() const + { + return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1); + } + + template + typename std::enable_if< !Exp2, size_t >::type slot_index() const + { + return m_Elimination.randEngine() % m_Elimination.collisions.capacity(); + } + public: elimination_backoff() { @@ -353,6 +404,13 @@ namespace cds { namespace intrusive { m_Elimination.collisions.zeroize(); } + typedef elimination_backoff& type; + + type init() + { + return *this; + } + void reset() {} @@ -360,11 +418,11 @@ namespace cds { namespace intrusive { 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; @@ -377,9 +435,9 @@ namespace cds { namespace intrusive { 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; @@ -617,9 +675,9 @@ namespace cds { namespace intrusive { stat m_stat; ///< Internal statistics //@cond - treiber_stack::details::elimination_backoff m_Backoff; + typedef treiber_stack::details::elimination_backoff elimination_backoff; + elimination_backoff m_Backoff; - typedef intrusive::node_to_value node_to_value; typedef treiber_stack::operation< value_type > operation_desc; // GC and node_type::gc must be the same @@ -675,7 +733,7 @@ namespace cds { namespace intrusive { 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 ) { @@ -686,14 +744,14 @@ namespace cds { namespace intrusive { 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; } } @@ -706,7 +764,7 @@ namespace cds { namespace intrusive { */ value_type * pop() { - m_Backoff.reset(); + typename elimination_backoff::type bkoff = m_Backoff.init(); typename gc::Guard guard; operation_desc op; @@ -715,12 +773,15 @@ namespace cds { namespace intrusive { } 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(); @@ -728,7 +789,7 @@ namespace cds { namespace intrusive { } 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; } @@ -738,7 +799,6 @@ namespace cds { namespace intrusive { /// 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; } @@ -757,7 +817,7 @@ namespace cds { namespace intrusive { 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; }