2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_FCSTACK_H
32 #define CDSLIB_INTRUSIVE_FCSTACK_H
34 #include <cds/algo/flat_combining.h>
35 #include <cds/algo/elimination_opt.h>
36 #include <cds/intrusive/options.h>
37 #include <boost/intrusive/slist.hpp>
39 namespace cds { namespace intrusive {
41 /// FCStack related definitions
44 /// FCStack internal statistics
45 template <typename Counter = cds::atomicity::event_counter >
46 struct stat: public cds::algo::flat_combining::stat<Counter>
48 typedef cds::algo::flat_combining::stat<Counter> flat_combining_stat; ///< Flat-combining statistics
49 typedef typename flat_combining_stat::counter_type counter_type; ///< Counter type
51 counter_type m_nPush ; ///< Count of push operations
52 counter_type m_nPop ; ///< Count of success pop operations
53 counter_type m_nFailedPop; ///< Count of failed pop operations (pop from empty stack)
54 counter_type m_nCollided ; ///< How many pairs of push/pop were collided, if elimination is enabled
57 void onPush() { ++m_nPush; }
58 void onPop( bool bFailed ) { if ( bFailed ) ++m_nFailedPop; else ++m_nPop; }
59 void onCollide() { ++m_nCollided; }
63 /// FCStack dummy statistics, no overhead
64 struct empty_stat: public cds::algo::flat_combining::empty_stat
73 /// FCStack type traits
74 struct traits: public cds::algo::flat_combining::traits
76 typedef cds::intrusive::opt::v::empty_disposer disposer ; ///< Disposer to erase removed elements. Used only in \p FCStack::clear() function
77 typedef empty_stat stat; ///< Internal statistics
78 static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
81 /// Metafunction converting option list to traits
84 - \p opt::lock_type - mutex type, default is \p cds::sync::spin
85 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
86 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::intrusive::v::empty_disposer.
87 This option is used only in \p FCStack::clear() function.
88 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
89 - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
90 - \p opt::memory_model - C++ memory ordering model.
91 List of all available memory ordering see \p opt::memory_model.
92 Default is \p cds::opt::v:relaxed_ordering
93 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
94 By default, the elimination is disabled.
96 template <typename... Options>
98 # ifdef CDS_DOXYGEN_INVOKED
99 typedef implementation_defined type ; ///< Metafunction result
101 typedef typename cds::opt::make_options<
102 typename cds::opt::find_type_traits< traits, Options... >::type
108 } // namespace fcstack
110 /// Flat-combining intrusive stack
112 @ingroup cds_intrusive_stack
113 @ingroup cds_flat_combining_intrusive
115 \ref cds_flat_combining_description "Flat combining" sequential intrusive stack.
118 - \p T - a value type stored in the stack
119 - \p Container - sequential intrusive container with \p push_front and \p pop_front functions.
120 Possible containers are \p boost::intrusive::slist (the default), \p boost::inrtrusive::list
121 - \p Traits - type traits of flat combining, default is \p fcstack::traits.
122 \p fcstack::make_traits metafunction can be used to construct specialized \p %traits
125 ,class Container = boost::intrusive::slist<T>
126 ,typename Traits = fcstack::traits
129 #ifndef CDS_DOXYGEN_INVOKED
130 : public cds::algo::flat_combining::container
134 typedef T value_type; ///< Value type
135 typedef Container container_type; ///< Sequential container type
136 typedef Traits traits; ///< Stack traits
138 typedef typename traits::disposer disposer; ///< The disposer functor. The disposer is used only in \ref clear() function
139 typedef typename traits::stat stat; ///< Internal statistics type
140 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
144 /// Stack operation IDs
146 op_push = cds::algo::flat_combining::req_Operation, ///< Push
149 op_clear_and_dispose ///< Clear and dispose
152 /// Flat combining publication list record
153 struct fc_record: public cds::algo::flat_combining::publication_record
155 value_type * pVal; ///< Value to push or pop
156 bool bEmpty; ///< \p true if the stack is empty
160 /// Flat combining kernel
161 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
165 fc_kernel m_FlatCombining;
166 container_type m_Stack;
170 /// Initializes empty stack object
174 /// Initializes empty stack object and gives flat combining parameters
176 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
177 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
179 : m_FlatCombining( nCompactFactor, nCombinePassCount )
182 /// Inserts a new element at the top of stack
184 The content of the new element initialized to a copy of \p val.
186 bool push( value_type& val )
188 fc_record * pRec = m_FlatCombining.acquire_record();
191 if ( c_bEliminationEnabled )
192 m_FlatCombining.batch_combine( op_push, pRec, *this );
194 m_FlatCombining.combine( op_push, pRec, *this );
196 assert( pRec->is_done() );
197 m_FlatCombining.release_record( pRec );
198 m_FlatCombining.internal_statistics().onPush();
202 /// Removes the element on top of the stack
205 fc_record * pRec = m_FlatCombining.acquire_record();
206 pRec->pVal = nullptr;
208 if ( c_bEliminationEnabled )
209 m_FlatCombining.batch_combine( op_pop, pRec, *this );
211 m_FlatCombining.combine( op_pop, pRec, *this );
213 assert( pRec->is_done() );
214 m_FlatCombining.release_record( pRec );
216 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
222 If \p bDispose is \p true, the disposer provided in \p Traits class' template parameter
223 will be called for each removed element.
225 void clear( bool bDispose = false )
227 fc_record * pRec = m_FlatCombining.acquire_record();
229 if ( c_bEliminationEnabled )
230 m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
232 m_FlatCombining.combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
234 assert( pRec->is_done() );
235 m_FlatCombining.release_record( pRec );
238 /// Returns the number of elements in the stack.
240 Note that <tt>size() == 0</tt> is not mean that the stack is empty because
241 combining record can be in process.
242 To check emptiness use \ref empty function.
246 return m_Stack.size();
249 /// Checks if the stack is empty
251 If the combining is in process the function waits while it is done.
255 m_FlatCombining.wait_while_combining();
256 return m_Stack.empty();
259 /// Internal statistics
260 stat const& statistics() const
262 return m_FlatCombining.statistics();
266 public: // flat combining cooperation, not for direct use!
268 /// Flat combining supporting function. Do not call it directly!
270 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
271 object if the current thread becomes a combiner. Invocation of the function means that
272 the stack should perform an action recorded in \p pRec.
274 void fc_apply( fc_record * pRec )
278 // this function is called under FC mutex, so switch TSan off
279 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
280 switch ( pRec->op() ) {
282 assert( pRec->pVal );
283 m_Stack.push_front( *(pRec->pVal ) );
286 pRec->bEmpty = m_Stack.empty();
287 if ( !pRec->bEmpty ) {
288 pRec->pVal = &m_Stack.front();
295 case op_clear_and_dispose:
296 m_Stack.clear_and_dispose( disposer() );
302 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
305 /// Batch-processing flat combining
306 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
308 // this function is called under FC mutex, so switch TSan off
309 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
311 typedef typename fc_kernel::iterator fc_iterator;
312 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
313 switch ( it->op() ) {
316 if ( itPrev != itEnd && collide( *itPrev, *it ))
323 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
329 bool collide( fc_record& rec1, fc_record& rec2 )
331 switch ( rec1.op() ) {
333 if ( rec2.op() == op_pop ) {
335 rec2.pVal = rec1.pVal;
337 m_FlatCombining.operation_done( rec1 );
338 m_FlatCombining.operation_done( rec2 );
339 m_FlatCombining.internal_statistics().onCollide();
344 if ( rec2.op() == op_push ) {
346 rec1.pVal = rec2.pVal;
348 m_FlatCombining.operation_done( rec1 );
349 m_FlatCombining.operation_done( rec2 );
350 m_FlatCombining.internal_statistics().onCollide();
361 }} // namespace cds::intrusive
363 #endif // #ifndef CDSLIB_INTRUSIVE_FCSTACK_H