3 #ifndef __CDS_INTRUSIVE_FCSTACK_H
4 #define __CDS_INTRUSIVE_FCSTACK_H
6 #include <cds/algo/flat_combining.h>
7 #include <cds/algo/elimination_opt.h>
8 #include <cds/intrusive/options.h>
9 #include <boost/intrusive/slist.hpp>
11 namespace cds { namespace intrusive {
13 /// FCStack related definitions
16 /// FCStack internal statistics
17 template <typename Counter = cds::atomicity::event_counter >
18 struct stat: public cds::algo::flat_combining::stat<Counter>
20 typedef cds::algo::flat_combining::stat<Counter> flat_combining_stat; ///< Flat-combining statistics
21 typedef typename flat_combining_stat::counter_type counter_type; ///< Counter type
23 counter_type m_nPush ; ///< Count of push operations
24 counter_type m_nPop ; ///< Count of success pop operations
25 counter_type m_nFailedPop; ///< Count of failed pop operations (pop from empty stack)
26 counter_type m_nCollided ; ///< How many pairs of push/pop were collided, if elimination is enabled
29 void onPush() { ++m_nPush; }
30 void onPop( bool bFailed ) { if ( bFailed ) ++m_nFailedPop; else ++m_nPop; }
31 void onCollide() { ++m_nCollided; }
35 /// FCStack dummy statistics, no overhead
36 struct empty_stat: public cds::algo::flat_combining::empty_stat
45 /// FCStack type traits
46 struct type_traits: public cds::algo::flat_combining::type_traits
48 typedef cds::intrusive::opt::v::empty_disposer disposer ; ///< Disposer to erase removed elements. Used only in \p FCStack::clear() function
49 typedef empty_stat stat; ///< Internal statistics
50 static CDS_CONSTEXPR_CONST bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
53 /// Metafunction converting option list to traits
55 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
57 - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
58 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
59 - \p opt::disposer - the functor used for dispose removed items. Default is opt::intrusive::v::empty_disposer.
60 This option is used only in \p FCStack::clear() function.
61 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
62 - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
63 - \p opt::memory_model - C++ memory ordering model.
64 List of all available memory ordering see opt::memory_model.
65 Default if 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< type_traits, Options... >::type
81 } // namespace fcstack
83 /// Flat-combining intrusive stack
85 @ingroup cds_intrusive_stack
86 @ingroup cds_flat_combining_intrusive
88 \ref cds_flat_combining_description "Flat combining" sequential intrusive stack.
91 - \p T - a value type stored in the stack
92 - \p Container - sequential intrusive container with \p push_front and \p pop_front functions.
93 Possible containers are \p boost::intrusive::slist (the default), \p boost::inrtrusive::list
94 - \p Traits - 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 Container = boost::intrusive::slist<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 Container container_type; ///< Sequential container type
109 typedef Traits type_traits; ///< Stack type traits
111 typedef typename type_traits::disposer disposer; ///< The disposer functor. The disposer is used only in \ref clear() function
112 typedef typename type_traits::stat stat; ///< Internal statistics type
113 static CDS_CONSTEXPR_CONST bool c_bEliminationEnabled = type_traits::enable_elimination; ///< \p true if elimination is enabled
117 /// Stack operation IDs
119 op_push = cds::algo::flat_combining::req_Operation, ///< Push
122 op_clear_and_dispose ///< Clear and dispose
125 /// Flat combining publication list record
126 struct fc_record: public cds::algo::flat_combining::publication_record
128 value_type * pVal; ///< Value to push or pop
129 bool bEmpty; ///< \p true if the stack is empty
133 /// Flat combining kernel
134 typedef cds::algo::flat_combining::kernel< fc_record, type_traits > fc_kernel;
138 fc_kernel m_FlatCombining;
139 container_type m_Stack;
143 /// Initializes empty stack object
147 /// Initializes empty stack object and gives flat combining parameters
149 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
150 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
152 : m_FlatCombining( nCompactFactor, nCombinePassCount )
155 /// Inserts a new element at the top of stack
157 The content of the new element initialized to a copy of \p val.
159 bool push( value_type& val )
161 fc_record * pRec = m_FlatCombining.acquire_record();
164 if ( c_bEliminationEnabled )
165 m_FlatCombining.batch_combine( op_push, pRec, *this );
167 m_FlatCombining.combine( op_push, pRec, *this );
169 assert( pRec->is_done() );
170 m_FlatCombining.release_record( pRec );
171 m_FlatCombining.internal_statistics().onPush();
175 /// Removes the element on top of the stack
178 fc_record * pRec = m_FlatCombining.acquire_record();
179 pRec->pVal = nullptr;
181 if ( c_bEliminationEnabled )
182 m_FlatCombining.batch_combine( op_pop, pRec, *this );
184 m_FlatCombining.combine( op_pop, pRec, *this );
186 assert( pRec->is_done() );
187 m_FlatCombining.release_record( pRec );
189 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
195 If \p bDispose is \p true, the disposer provided in \p Traits class' template parameter
196 will be called for each removed element.
198 void clear( bool bDispose = false )
200 fc_record * pRec = m_FlatCombining.acquire_record();
202 if ( c_bEliminationEnabled )
203 m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
205 m_FlatCombining.combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
207 assert( pRec->is_done() );
208 m_FlatCombining.release_record( pRec );
211 /// Returns the number of elements in the stack.
213 Note that <tt>size() == 0</tt> is not mean that the stack is empty because
214 combining record can be in process.
215 To check emptiness use \ref empty function.
219 return m_Stack.size();
222 /// Checks if the stack is empty
224 If the combining is in process the function waits while it is done.
228 m_FlatCombining.wait_while_combining();
229 return m_Stack.empty();
232 /// Internal statistics
233 stat const& statistics() const
235 return m_FlatCombining.statistics();
239 public: // flat combining cooperation, not for direct use!
241 /// Flat combining supporting function. Do not call it directly!
243 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
244 object if the current thread becomes a combiner. Invocation of the function means that
245 the stack should perform an action recorded in \p pRec.
247 void fc_apply( fc_record * pRec )
251 switch ( pRec->op() ) {
253 assert( pRec->pVal );
254 m_Stack.push_front( *(pRec->pVal ) );
257 pRec->bEmpty = m_Stack.empty();
258 if ( !pRec->bEmpty ) {
259 pRec->pVal = &m_Stack.front();
266 case op_clear_and_dispose:
267 m_Stack.clear_and_dispose( disposer() );
275 /// Batch-processing flat combining
276 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
278 typedef typename fc_kernel::iterator fc_iterator;
279 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
280 switch ( it->op() ) {
283 if ( itPrev != itEnd && collide( *itPrev, *it ))
295 bool collide( fc_record& rec1, fc_record& rec2 )
297 switch ( rec1.op() ) {
299 if ( rec2.op() == op_pop ) {
301 rec2.pVal = rec1.pVal;
303 m_FlatCombining.operation_done( rec1 );
304 m_FlatCombining.operation_done( rec2 );
305 m_FlatCombining.internal_statistics().onCollide();
310 if ( rec2.op() == op_push ) {
312 rec1.pVal = rec2.pVal;
314 m_FlatCombining.operation_done( rec1 );
315 m_FlatCombining.operation_done( rec2 );
316 m_FlatCombining.internal_statistics().onCollide();
327 }} // namespace cds::intrusive
329 #endif // #ifndef __CDS_INTRUSIVE_FCSTACK_H