X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Ffcstack.h;h=257079b03a758935b36ae96bcb93d0651769cab1;hb=173f94ff798becc6d4dbcdfa3289856214203803;hp=f03dd3fee0fa33e58c8d2133211d3971497a2b54;hpb=cca56d72a1606b58472a24d1d61b9cfa40635971;p=libcds.git diff --git a/cds/intrusive/fcstack.h b/cds/intrusive/fcstack.h index f03dd3fe..257079b0 100644 --- a/cds/intrusive/fcstack.h +++ b/cds/intrusive/fcstack.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-2017 + + 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_FCSTACK_H #define CDSLIB_INTRUSIVE_FCSTACK_H @@ -53,15 +81,10 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to traits /** \p Options are: - - \p opt::lock_type - mutex type, default is \p cds::sync::spin - - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default + - any \p cds::algo::flat_combining::make_traits options - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::intrusive::v::empty_disposer. This option is used only in \p FCStack::clear() function. - - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default) - - \p opt::memory_model - C++ memory ordering model. - List of all available memory ordering see \p opt::memory_model. - Default is \p cds::opt::v:relaxed_ordering - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination" By default, the elimination is disabled. */ @@ -134,8 +157,8 @@ namespace cds { namespace intrusive { protected: //@cond - fc_kernel m_FlatCombining; - container_type m_Stack; + mutable fc_kernel m_FlatCombining; + container_type m_Stack; //@endcond public: @@ -157,7 +180,7 @@ namespace cds { namespace intrusive { */ bool push( value_type& val ) { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); pRec->pVal = &val; if ( c_bEliminationEnabled ) @@ -165,7 +188,7 @@ namespace cds { namespace intrusive { else m_FlatCombining.combine( op_push, pRec, *this ); - assert( pRec->is_done() ); + assert( pRec->is_done()); m_FlatCombining.release_record( pRec ); m_FlatCombining.internal_statistics().onPush(); return true; @@ -174,7 +197,7 @@ namespace cds { namespace intrusive { /// Removes the element on top of the stack value_type * pop() { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); pRec->pVal = nullptr; if ( c_bEliminationEnabled ) @@ -182,7 +205,7 @@ namespace cds { namespace intrusive { else m_FlatCombining.combine( op_pop, pRec, *this ); - assert( pRec->is_done() ); + assert( pRec->is_done()); m_FlatCombining.release_record( pRec ); m_FlatCombining.internal_statistics().onPop( pRec->bEmpty ); @@ -196,14 +219,14 @@ namespace cds { namespace intrusive { */ void clear( bool bDispose = false ) { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); if ( c_bEliminationEnabled ) m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this ); else m_FlatCombining.combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this ); - assert( pRec->is_done() ); + assert( pRec->is_done()); m_FlatCombining.release_record( pRec ); } @@ -224,8 +247,10 @@ namespace cds { namespace intrusive { */ bool empty() const { - m_FlatCombining.wait_while_combining(); - return m_Stack.empty(); + bool bRet = false; + auto const& stack = m_Stack; + m_FlatCombining.invoke_exclusive( [&stack, &bRet]() { bRet = stack.empty(); } ); + return bRet; } /// Internal statistics @@ -234,7 +259,6 @@ namespace cds { namespace intrusive { return m_FlatCombining.statistics(); } - public: // flat combining cooperation, not for direct use! //@cond /// Flat combining supporting function. Do not call it directly! @@ -243,14 +267,14 @@ namespace cds { namespace intrusive { object if the current thread becomes a combiner. Invocation of the function means that the stack should perform an action recorded in \p pRec. */ - void fc_apply( fc_record * pRec ) + void fc_apply( fc_record* pRec ) { assert( pRec ); - switch ( pRec->op() ) { + switch ( pRec->op()) { case op_push: assert( pRec->pVal ); - m_Stack.push_front( *(pRec->pVal ) ); + m_Stack.push_front( *(pRec->pVal )); break; case op_pop: pRec->bEmpty = m_Stack.empty(); @@ -263,7 +287,7 @@ namespace cds { namespace intrusive { m_Stack.clear(); break; case op_clear_and_dispose: - m_Stack.clear_and_dispose( disposer() ); + m_Stack.clear_and_dispose( disposer()); break; default: assert(false); @@ -276,7 +300,7 @@ namespace cds { namespace intrusive { { typedef typename fc_kernel::iterator fc_iterator; for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) { - switch ( it->op() ) { + switch ( it->op( atomics::memory_order_acquire )) { case op_push: case op_pop: if ( itPrev != itEnd && collide( *itPrev, *it )) @@ -293,7 +317,7 @@ namespace cds { namespace intrusive { //@cond bool collide( fc_record& rec1, fc_record& rec2 ) { - switch ( rec1.op() ) { + switch ( rec1.op()) { case op_push: if ( rec2.op() == op_pop ) { assert(rec1.pVal);