2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 - any \p cds::algo::flat_combining::make_traits options
85 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::intrusive::v::empty_disposer.
86 This option is used only in \p FCStack::clear() function.
87 - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
88 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
89 By default, the elimination is disabled.
91 template <typename... Options>
93 # ifdef CDS_DOXYGEN_INVOKED
94 typedef implementation_defined type ; ///< Metafunction result
96 typedef typename cds::opt::make_options<
97 typename cds::opt::find_type_traits< traits, Options... >::type
103 } // namespace fcstack
105 /// Flat-combining intrusive stack
107 @ingroup cds_intrusive_stack
108 @ingroup cds_flat_combining_intrusive
110 \ref cds_flat_combining_description "Flat combining" sequential intrusive stack.
113 - \p T - a value type stored in the stack
114 - \p Container - sequential intrusive container with \p push_front and \p pop_front functions.
115 Possible containers are \p boost::intrusive::slist (the default), \p boost::inrtrusive::list
116 - \p Traits - type traits of flat combining, default is \p fcstack::traits.
117 \p fcstack::make_traits metafunction can be used to construct specialized \p %traits
120 ,class Container = boost::intrusive::slist<T>
121 ,typename Traits = fcstack::traits
124 #ifndef CDS_DOXYGEN_INVOKED
125 : public cds::algo::flat_combining::container
129 typedef T value_type; ///< Value type
130 typedef Container container_type; ///< Sequential container type
131 typedef Traits traits; ///< Stack traits
133 typedef typename traits::disposer disposer; ///< The disposer functor. The disposer is used only in \ref clear() function
134 typedef typename traits::stat stat; ///< Internal statistics type
135 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
139 /// Stack operation IDs
141 op_push = cds::algo::flat_combining::req_Operation, ///< Push
144 op_clear_and_dispose ///< Clear and dispose
147 /// Flat combining publication list record
148 struct fc_record: public cds::algo::flat_combining::publication_record
150 value_type * pVal; ///< Value to push or pop
151 bool bEmpty; ///< \p true if the stack is empty
155 /// Flat combining kernel
156 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
160 mutable fc_kernel m_FlatCombining;
161 container_type m_Stack;
165 /// Initializes empty stack object
169 /// Initializes empty stack object and gives flat combining parameters
171 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
172 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
174 : m_FlatCombining( nCompactFactor, nCombinePassCount )
177 /// Inserts a new element at the top of stack
179 The content of the new element initialized to a copy of \p val.
181 bool push( value_type& val )
183 auto pRec = m_FlatCombining.acquire_record();
186 if ( c_bEliminationEnabled )
187 m_FlatCombining.batch_combine( op_push, pRec, *this );
189 m_FlatCombining.combine( op_push, pRec, *this );
191 assert( pRec->is_done());
192 m_FlatCombining.release_record( pRec );
193 m_FlatCombining.internal_statistics().onPush();
197 /// Removes the element on top of the stack
200 auto pRec = m_FlatCombining.acquire_record();
201 pRec->pVal = nullptr;
203 if ( c_bEliminationEnabled )
204 m_FlatCombining.batch_combine( op_pop, pRec, *this );
206 m_FlatCombining.combine( op_pop, pRec, *this );
208 assert( pRec->is_done());
209 m_FlatCombining.release_record( pRec );
211 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
217 If \p bDispose is \p true, the disposer provided in \p Traits class' template parameter
218 will be called for each removed element.
220 void clear( bool bDispose = false )
222 auto pRec = m_FlatCombining.acquire_record();
224 if ( c_bEliminationEnabled )
225 m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
227 m_FlatCombining.combine( bDispose ? op_clear_and_dispose : 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 it is done.
251 auto const& stack = m_Stack;
252 m_FlatCombining.invoke_exclusive( [&stack, &bRet]() { bRet = stack.empty(); } );
256 /// Internal statistics
257 stat const& statistics() const
259 return m_FlatCombining.statistics();
263 public: // flat combining cooperation, not for direct use!
265 /// Flat combining supporting function. Do not call it directly!
267 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
268 object if the current thread becomes a combiner. Invocation of the function means that
269 the stack should perform an action recorded in \p pRec.
271 void fc_apply( fc_record* pRec )
275 // this function is called under FC mutex, so switch TSan off
276 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
277 switch ( pRec->op()) {
279 assert( pRec->pVal );
280 m_Stack.push_front( *(pRec->pVal ));
283 pRec->bEmpty = m_Stack.empty();
284 if ( !pRec->bEmpty ) {
285 pRec->pVal = &m_Stack.front();
292 case op_clear_and_dispose:
293 m_Stack.clear_and_dispose( disposer());
299 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
302 /// Batch-processing flat combining
303 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
305 // this function is called under FC mutex, so switch TSan off
306 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
308 typedef typename fc_kernel::iterator fc_iterator;
309 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
313 if ( itPrev != itEnd && collide( *itPrev, *it ))
320 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
326 bool collide( fc_record& rec1, fc_record& rec2 )
328 switch ( rec1.op()) {
330 if ( rec2.op() == op_pop ) {
332 rec2.pVal = rec1.pVal;
334 m_FlatCombining.operation_done( rec1 );
335 m_FlatCombining.operation_done( rec2 );
336 m_FlatCombining.internal_statistics().onCollide();
341 if ( rec2.op() == op_push ) {
343 rec1.pVal = rec2.pVal;
345 m_FlatCombining.operation_done( rec1 );
346 m_FlatCombining.operation_done( rec2 );
347 m_FlatCombining.internal_statistics().onCollide();
358 }} // namespace cds::intrusive
360 #endif // #ifndef CDSLIB_INTRUSIVE_FCSTACK_H