3 #ifndef CDSLIB_CONTAINER_FCSTACK_H
4 #define CDSLIB_CONTAINER_FCSTACK_H
6 #include <cds/algo/flat_combining.h>
7 #include <cds/algo/elimination_opt.h>
10 namespace cds { namespace container {
12 /// FCStack related definitions
13 /** @ingroup cds_nonintrusive_helper
17 /// FCStack internal statistics
18 template <typename Counter = cds::atomicity::event_counter >
19 struct stat: public cds::algo::flat_combining::stat<Counter>
21 typedef cds::algo::flat_combining::stat<Counter> flat_combining_stat; ///< Flat-combining statistics
22 typedef typename flat_combining_stat::counter_type counter_type; ///< Counter type
24 counter_type m_nPush ; ///< Count of push operations
25 counter_type m_nPushMove ; ///< Count of push operations with move semantics
26 counter_type m_nPop ; ///< Count of success pop operations
27 counter_type m_nFailedPop; ///< Count of failed pop operations (pop from empty stack)
28 counter_type m_nCollided ; ///< How many pairs of push/pop were collided, if elimination is enabled
31 void onPush() { ++m_nPush; }
32 void onPushMove() { ++m_nPushMove; }
33 void onPop( bool bFailed ) { if ( bFailed ) ++m_nFailedPop; else ++m_nPop; }
34 void onCollide() { ++m_nCollided; }
38 /// FCStack dummy statistics, no overhead
39 struct empty_stat: public cds::algo::flat_combining::empty_stat
49 /// FCStack type traits
50 struct traits: public cds::algo::flat_combining::traits
52 typedef empty_stat stat; ///< Internal statistics
53 static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
56 /// Metafunction converting option list to traits
59 - \p opt::lock_type - mutex type, default is \p cds::sync::spin
60 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
61 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
62 - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
63 - \p opt::memory_model - C++ memory ordering model.
64 List of all available memory ordering see \p opt::memory_model.
65 Default is \p cds::opt::v:relaxed_ordering
66 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
67 By default, the elimination is disabled.
69 template <typename... Options>
71 # ifdef CDS_DOXYGEN_INVOKED
72 typedef implementation_defined type ; ///< Metafunction result
74 typedef typename cds::opt::make_options<
75 typename cds::opt::find_type_traits< traits, Options... >::type
81 } // namespace fcstack
83 /// Flat-combining stack
85 @ingroup cds_nonintrusive_stack
86 @ingroup cds_flat_combining_container
88 \ref cds_flat_combining_description "Flat combining" sequential stack.
91 - \p T - a value type stored in the stack
92 - \p Stack - sequential stack implementation, default is \p std::stack<T>
93 - \p Trats - type traits of flat combining, default is \p fcstack::traits
94 \p fcstack::make_traits metafunction can be used to construct specialized \p %fcstack::traits
97 class Stack = std::stack<T>,
98 typename Traits = fcstack::traits
101 #ifndef CDS_DOXYGEN_INVOKED
102 : public cds::algo::flat_combining::container
106 typedef T value_type; ///< Value type
107 typedef Stack stack_type; ///< Sequential stack class
108 typedef Traits traits; ///< Stack traits
110 typedef typename traits::stat stat; ///< Internal statistics type
111 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
115 /// Stack operation IDs
117 op_push = cds::algo::flat_combining::req_Operation, ///< Push
118 op_push_move, ///< Push (move semantics)
124 /// Flat combining publication list record
125 struct fc_record: public cds::algo::flat_combining::publication_record
128 value_type const * pValPush; ///< Value to push
129 value_type * pValPop; ///< Pop destination
131 bool bEmpty; ///< \p true if the stack is empty
135 /// Flat combining kernel
136 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
140 fc_kernel m_FlatCombining;
145 /// Initializes empty stack object
149 /// Initializes empty stack object and gives flat combining parameters
151 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
152 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
154 : m_FlatCombining( nCompactFactor, nCombinePassCount )
157 /// Inserts a new element at the top of stack
159 The content of the new element initialized to a copy of \p val.
161 bool push( value_type const& val )
163 fc_record * pRec = m_FlatCombining.acquire_record();
164 pRec->pValPush = &val;
166 if ( c_bEliminationEnabled )
167 m_FlatCombining.batch_combine( op_push, pRec, *this );
169 m_FlatCombining.combine( op_push, pRec, *this );
171 assert( pRec->is_done() );
172 m_FlatCombining.release_record( pRec );
173 m_FlatCombining.internal_statistics().onPush();
177 /// Inserts a new element at the top of stack (move semantics)
179 The content of the new element initialized to a copy of \p val.
181 bool push( value_type&& val )
183 fc_record * pRec = m_FlatCombining.acquire_record();
184 pRec->pValPush = &val;
186 if ( c_bEliminationEnabled )
187 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
189 m_FlatCombining.combine( op_push_move, pRec, *this );
191 assert( pRec->is_done() );
192 m_FlatCombining.release_record( pRec );
194 m_FlatCombining.internal_statistics().onPushMove();
198 /// Removes the element on top of the stack
200 \p val takes a copy of top element
202 bool pop( value_type& val )
204 fc_record * pRec = m_FlatCombining.acquire_record();
205 pRec->pValPop = &val;
207 if ( c_bEliminationEnabled )
208 m_FlatCombining.batch_combine( op_pop, pRec, *this );
210 m_FlatCombining.combine( op_pop, pRec, *this );
212 assert( pRec->is_done() );
213 m_FlatCombining.release_record( pRec );
215 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
216 return !pRec->bEmpty;
222 fc_record * pRec = m_FlatCombining.acquire_record();
224 if ( c_bEliminationEnabled )
225 m_FlatCombining.batch_combine( op_clear, pRec, *this );
227 m_FlatCombining.combine( op_clear, pRec, *this );
229 assert( pRec->is_done() );
230 m_FlatCombining.release_record( pRec );
233 /// Returns the number of elements in the stack.
235 Note that <tt>size() == 0</tt> is not mean that the stack is empty because
236 combining record can be in process.
237 To check emptiness use \ref empty function.
241 return m_Stack.size();
244 /// Checks if the stack is empty
246 If the combining is in process the function waits while combining done.
250 fc_record * pRec = m_FlatCombining.acquire_record();
252 if ( c_bEliminationEnabled )
253 m_FlatCombining.batch_combine( op_empty, pRec, *this );
255 m_FlatCombining.combine( op_empty, pRec, *this );
257 assert( pRec->is_done() );
258 m_FlatCombining.release_record( pRec );
262 /// Internal statistics
263 stat const& statistics() const
265 return m_FlatCombining.statistics();
269 public: // flat combining cooperation, not for direct use!
271 /// Flat combining supporting function. Do not call it directly!
273 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
274 object if the current thread becomes a combiner. Invocation of the function means that
275 the stack should perform an action recorded in \p pRec.
277 void fc_apply( fc_record * pRec )
281 // this function is called under FC mutex, so switch TSan off
282 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
283 switch ( pRec->op() ) {
285 assert( pRec->pValPush );
286 m_Stack.push( *(pRec->pValPush ) );
289 assert( pRec->pValPush );
290 m_Stack.push( std::move( *(pRec->pValPush )) );
293 assert( pRec->pValPop );
294 pRec->bEmpty = m_Stack.empty();
295 if ( !pRec->bEmpty ) {
296 *(pRec->pValPop) = m_Stack.top();
301 while ( !m_Stack.empty() )
305 pRec->bEmpty = m_Stack.empty();
311 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
314 /// Batch-processing flat combining
315 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
317 // this function is called under FC mutex, so switch TSan off
318 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
320 typedef typename fc_kernel::iterator fc_iterator;
321 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
322 switch ( it->op() ) {
326 if ( itPrev != itEnd && collide( *itPrev, *it ))
333 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
339 bool collide( fc_record& rec1, fc_record& rec2 )
341 switch ( rec1.op() ) {
343 if ( rec2.op() == op_pop ) {
344 assert(rec1.pValPush);
345 assert(rec2.pValPop);
346 *rec2.pValPop = *rec1.pValPush;
352 if ( rec2.op() == op_pop ) {
353 assert(rec1.pValPush);
354 assert(rec2.pValPop);
355 *rec2.pValPop = std::move( *rec1.pValPush );
361 switch ( rec2.op() ) {
364 return collide( rec2, rec1 );
370 m_FlatCombining.operation_done( rec1 );
371 m_FlatCombining.operation_done( rec2 );
372 m_FlatCombining.internal_statistics().onCollide();
377 }} // namespace cds::container
379 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H