3 #ifndef __CDS_CONTAINER_FCSTACK_H
4 #define __CDS_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::type_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::lock::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)
123 /// Flat combining publication list record
124 struct fc_record: public cds::algo::flat_combining::publication_record
127 value_type const * pValPush; ///< Value to push
128 value_type * pValPop; ///< Pop destination
130 bool bEmpty; ///< \p true if the stack is empty
134 /// Flat combining kernel
135 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
139 fc_kernel m_FlatCombining;
144 /// Initializes empty stack object
148 /// Initializes empty stack object and gives flat combining parameters
150 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
151 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
153 : m_FlatCombining( nCompactFactor, nCombinePassCount )
156 /// Inserts a new element at the top of stack
158 The content of the new element initialized to a copy of \p val.
160 bool push( value_type const& val )
162 fc_record * pRec = m_FlatCombining.acquire_record();
163 pRec->pValPush = &val;
165 if ( c_bEliminationEnabled )
166 m_FlatCombining.batch_combine( op_push, pRec, *this );
168 m_FlatCombining.combine( op_push, pRec, *this );
170 assert( pRec->is_done() );
171 m_FlatCombining.release_record( pRec );
172 m_FlatCombining.internal_statistics().onPush();
176 /// Inserts a new element at the top of stack (move semantics)
178 The content of the new element initialized to a copy of \p val.
180 bool push( value_type&& val )
182 fc_record * pRec = m_FlatCombining.acquire_record();
183 pRec->pValPush = &val;
185 if ( c_bEliminationEnabled )
186 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
188 m_FlatCombining.combine( op_push_move, pRec, *this );
190 assert( pRec->is_done() );
191 m_FlatCombining.release_record( pRec );
193 m_FlatCombining.internal_statistics().onPushMove();
197 /// Removes the element on top of the stack
199 \p val takes a copy of top element
201 bool pop( value_type& val )
203 fc_record * pRec = m_FlatCombining.acquire_record();
204 pRec->pValPop = &val;
206 if ( c_bEliminationEnabled )
207 m_FlatCombining.batch_combine( op_pop, pRec, *this );
209 m_FlatCombining.combine( op_pop, pRec, *this );
211 assert( pRec->is_done() );
212 m_FlatCombining.release_record( pRec );
214 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
215 return !pRec->bEmpty;
221 fc_record * pRec = m_FlatCombining.acquire_record();
223 if ( c_bEliminationEnabled )
224 m_FlatCombining.batch_combine( op_clear, pRec, *this );
226 m_FlatCombining.combine( op_clear, pRec, *this );
228 assert( pRec->is_done() );
229 m_FlatCombining.release_record( pRec );
232 /// Returns the number of elements in the stack.
234 Note that <tt>size() == 0</tt> is not mean that the stack is empty because
235 combining record can be in process.
236 To check emptiness use \ref empty function.
240 return m_Stack.size();
243 /// Checks if the stack is empty
245 If the combining is in process the function waits while combining done.
249 m_FlatCombining.wait_while_combining();
250 return m_Stack.empty();
253 /// Internal statistics
254 stat const& statistics() const
256 return m_FlatCombining.statistics();
260 public: // flat combining cooperation, not for direct use!
262 /// Flat combining supporting function. Do not call it directly!
264 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
265 object if the current thread becomes a combiner. Invocation of the function means that
266 the stack should perform an action recorded in \p pRec.
268 void fc_apply( fc_record * pRec )
272 switch ( pRec->op() ) {
274 assert( pRec->pValPush );
275 m_Stack.push( *(pRec->pValPush ) );
278 assert( pRec->pValPush );
279 m_Stack.push( std::move( *(pRec->pValPush )) );
282 assert( pRec->pValPop );
283 pRec->bEmpty = m_Stack.empty();
284 if ( !pRec->bEmpty ) {
285 *(pRec->pValPop) = m_Stack.top();
290 while ( !m_Stack.empty() )
299 /// Batch-processing flat combining
300 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
302 typedef typename fc_kernel::iterator fc_iterator;
303 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
304 switch ( it->op() ) {
308 if ( itPrev != itEnd && collide( *itPrev, *it ))
320 bool collide( fc_record& rec1, fc_record& rec2 )
322 switch ( rec1.op() ) {
324 if ( rec2.op() == op_pop ) {
325 assert(rec1.pValPush);
326 assert(rec2.pValPop);
327 *rec2.pValPop = *rec1.pValPush;
333 if ( rec2.op() == op_pop ) {
334 assert(rec1.pValPush);
335 assert(rec2.pValPop);
336 *rec2.pValPop = std::move( *rec1.pValPush );
342 switch ( rec2.op() ) {
345 return collide( rec2, rec1 );
351 m_FlatCombining.operation_done( rec1 );
352 m_FlatCombining.operation_done( rec2 );
353 m_FlatCombining.internal_statistics().onCollide();
358 }} // namespace cds::container
360 #endif // #ifndef __CDS_CONTAINER_FCSTACK_H