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 type_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
58 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
60 - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
61 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
62 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
63 - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
64 - \p opt::memory_model - C++ memory ordering model.
65 List of all available memory ordering see opt::memory_model.
66 Default if cds::opt::v:relaxed_ordering
67 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
68 By default, the elimination is disabled.
70 template <typename... Options>
72 # ifdef CDS_DOXYGEN_INVOKED
73 typedef implementation_defined type ; ///< Metafunction result
75 typedef typename cds::opt::make_options<
76 typename cds::opt::find_type_traits< type_traits, Options... >::type
82 } // namespace fcstack
84 /// Flat-combining stack
86 @ingroup cds_nonintrusive_stack
87 @ingroup cds_flat_combining_container
89 \ref cds_flat_combining_description "Flat combining" sequential stack.
92 - \p T - a value type stored in the stack
93 - \p Stack - sequential stack implementation, default is \p std::stack<T>
94 - \p Trats - type traits of flat combining, default is \p fcstack::type_traits
95 \p fcstack::make_traits metafunction can be used to construct specialized \p %type_traits
98 class Stack = std::stack<T>,
99 typename Traits = fcstack::type_traits
102 #ifndef CDS_DOXYGEN_INVOKED
103 : public cds::algo::flat_combining::container
107 typedef T value_type; ///< Value type
108 typedef Stack stack_type; ///< Sequential stack class
109 typedef Traits type_traits; ///< Stack type traits
111 typedef typename type_traits::stat stat; ///< Internal statistics type
112 static CDS_CONSTEXPR_CONST bool c_bEliminationEnabled = type_traits::enable_elimination; ///< \p true if elimination is enabled
116 /// Stack operation IDs
118 op_push = cds::algo::flat_combining::req_Operation, ///< Push
119 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, type_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 m_FlatCombining.wait_while_combining();
251 return m_Stack.empty();
254 /// Internal statistics
255 stat const& statistics() const
257 return m_FlatCombining.statistics();
261 public: // flat combining cooperation, not for direct use!
263 /// Flat combining supporting function. Do not call it directly!
265 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
266 object if the current thread becomes a combiner. Invocation of the function means that
267 the stack should perform an action recorded in \p pRec.
269 void fc_apply( fc_record * pRec )
273 switch ( pRec->op() ) {
275 assert( pRec->pValPush );
276 m_Stack.push( *(pRec->pValPush ) );
279 assert( pRec->pValPush );
280 m_Stack.push( std::move( *(pRec->pValPush )) );
283 assert( pRec->pValPop );
284 pRec->bEmpty = m_Stack.empty();
285 if ( !pRec->bEmpty ) {
286 *(pRec->pValPop) = m_Stack.top();
291 while ( !m_Stack.empty() )
300 /// Batch-processing flat combining
301 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
303 typedef typename fc_kernel::iterator fc_iterator;
304 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
305 switch ( it->op() ) {
309 if ( itPrev != itEnd && collide( *itPrev, *it ))
321 bool collide( fc_record& rec1, fc_record& rec2 )
323 switch ( rec1.op() ) {
325 if ( rec2.op() == op_pop ) {
326 assert(rec1.pValPush);
327 assert(rec2.pValPop);
328 *rec2.pValPop = *rec1.pValPush;
334 if ( rec2.op() == op_pop ) {
335 assert(rec1.pValPush);
336 assert(rec2.pValPop);
337 *rec2.pValPop = std::move( *rec1.pValPush );
343 switch ( rec2.op() ) {
346 return collide( rec2, rec1 );
352 m_FlatCombining.operation_done( rec1 );
353 m_FlatCombining.operation_done( rec2 );
354 m_FlatCombining.internal_statistics().onCollide();
359 }} // namespace cds::container
361 #endif // #ifndef __CDS_CONTAINER_FCSTACK_H