2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_CONTAINER_FCSTACK_H
32 #define CDSLIB_CONTAINER_FCSTACK_H
34 #include <cds/algo/flat_combining.h>
35 #include <cds/algo/elimination_opt.h>
38 namespace cds { namespace container {
40 /// FCStack related definitions
41 /** @ingroup cds_nonintrusive_helper
45 /// FCStack internal statistics
46 template <typename Counter = cds::atomicity::event_counter >
47 struct stat: public cds::algo::flat_combining::stat<Counter>
49 typedef cds::algo::flat_combining::stat<Counter> flat_combining_stat; ///< Flat-combining statistics
50 typedef typename flat_combining_stat::counter_type counter_type; ///< Counter type
52 counter_type m_nPush ; ///< Count of push operations
53 counter_type m_nPushMove ; ///< Count of push operations with move semantics
54 counter_type m_nPop ; ///< Count of success pop operations
55 counter_type m_nFailedPop; ///< Count of failed pop operations (pop from empty stack)
56 counter_type m_nCollided ; ///< How many pairs of push/pop were collided, if elimination is enabled
59 void onPush() { ++m_nPush; }
60 void onPushMove() { ++m_nPushMove; }
61 void onPop( bool bFailed ) { if ( bFailed ) ++m_nFailedPop; else ++m_nPop; }
62 void onCollide() { ++m_nCollided; }
66 /// FCStack dummy statistics, no overhead
67 struct empty_stat: public cds::algo::flat_combining::empty_stat
77 /// FCStack type traits
78 struct traits: public cds::algo::flat_combining::traits
80 typedef empty_stat stat; ///< Internal statistics
81 static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
84 /// Metafunction converting option list to traits
87 - any \p cds::algo::flat_combining::make_traits options
88 - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
89 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
90 By default, the elimination is disabled.
92 template <typename... Options>
94 # ifdef CDS_DOXYGEN_INVOKED
95 typedef implementation_defined type ; ///< Metafunction result
97 typedef typename cds::opt::make_options<
98 typename cds::opt::find_type_traits< traits, Options... >::type
104 } // namespace fcstack
106 /// Flat-combining stack
108 @ingroup cds_nonintrusive_stack
109 @ingroup cds_flat_combining_container
111 \ref cds_flat_combining_description "Flat combining" sequential stack.
114 - \p T - a value type stored in the stack
115 - \p Stack - sequential stack implementation, default is \p std::stack<T>
116 - \p Trats - type traits of flat combining, default is \p fcstack::traits
117 \p fcstack::make_traits metafunction can be used to construct specialized \p %fcstack::traits
119 template <typename T,
120 class Stack = std::stack<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 Stack stack_type; ///< Sequential stack class
131 typedef Traits traits; ///< Stack traits
133 typedef typename traits::stat stat; ///< Internal statistics type
134 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
138 /// Stack operation IDs
140 op_push = cds::algo::flat_combining::req_Operation, ///< Push
141 op_push_move, ///< Push (move semantics)
147 /// Flat combining publication list record
148 struct fc_record: public cds::algo::flat_combining::publication_record
151 value_type const * pValPush; ///< Value to push
152 value_type * pValPop; ///< Pop destination
154 bool bEmpty; ///< \p true if the stack is empty
158 /// Flat combining kernel
159 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
163 mutable fc_kernel m_FlatCombining;
168 /// Initializes empty stack object
172 /// Initializes empty stack object and gives flat combining parameters
174 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
175 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
177 : m_FlatCombining( nCompactFactor, nCombinePassCount )
180 /// Inserts a new element at the top of stack
182 The content of the new element initialized to a copy of \p val.
184 bool push( value_type const& val )
186 auto pRec = m_FlatCombining.acquire_record();
187 pRec->pValPush = &val;
189 if ( c_bEliminationEnabled )
190 m_FlatCombining.batch_combine( op_push, pRec, *this );
192 m_FlatCombining.combine( op_push, pRec, *this );
194 assert( pRec->is_done() );
195 m_FlatCombining.release_record( pRec );
196 m_FlatCombining.internal_statistics().onPush();
200 /// Inserts a new element at the top of stack (move semantics)
202 The content of the new element initialized to a copy of \p val.
204 bool push( value_type&& val )
206 auto pRec = m_FlatCombining.acquire_record();
207 pRec->pValPush = &val;
209 if ( c_bEliminationEnabled )
210 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
212 m_FlatCombining.combine( op_push_move, pRec, *this );
214 assert( pRec->is_done() );
215 m_FlatCombining.release_record( pRec );
217 m_FlatCombining.internal_statistics().onPushMove();
221 /// Removes the element on top of the stack
223 \p val takes a copy of top element
225 bool pop( value_type& val )
227 auto pRec = m_FlatCombining.acquire_record();
228 pRec->pValPop = &val;
230 if ( c_bEliminationEnabled )
231 m_FlatCombining.batch_combine( op_pop, pRec, *this );
233 m_FlatCombining.combine( op_pop, pRec, *this );
235 assert( pRec->is_done() );
236 m_FlatCombining.release_record( pRec );
238 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
239 return !pRec->bEmpty;
245 auto pRec = m_FlatCombining.acquire_record();
247 if ( c_bEliminationEnabled )
248 m_FlatCombining.batch_combine( op_clear, pRec, *this );
250 m_FlatCombining.combine( op_clear, pRec, *this );
252 assert( pRec->is_done() );
253 m_FlatCombining.release_record( pRec );
256 /// Returns the number of elements in the stack.
258 Note that <tt>size() == 0</tt> is not mean that the stack is empty because
259 combining record can be in process.
260 To check emptiness use \ref empty function.
264 return m_Stack.size();
267 /// Checks if the stack is empty
269 If the combining is in process the function waits while combining done.
273 auto pRec = m_FlatCombining.acquire_record();
275 if ( c_bEliminationEnabled )
276 m_FlatCombining.batch_combine( op_empty, pRec, *this );
278 m_FlatCombining.combine( op_empty, pRec, *this );
280 assert( pRec->is_done() );
281 m_FlatCombining.release_record( pRec );
285 /// Internal statistics
286 stat const& statistics() const
288 return m_FlatCombining.statistics();
292 public: // flat combining cooperation, not for direct use!
294 /// Flat combining supporting function. Do not call it directly!
296 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
297 object if the current thread becomes a combiner. Invocation of the function means that
298 the stack should perform an action recorded in \p pRec.
300 void fc_apply( fc_record * pRec )
304 // this function is called under FC mutex, so switch TSan off
305 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
306 switch ( pRec->op() ) {
308 assert( pRec->pValPush );
309 m_Stack.push( *(pRec->pValPush ) );
312 assert( pRec->pValPush );
313 m_Stack.push( std::move( *(pRec->pValPush )) );
316 assert( pRec->pValPop );
317 pRec->bEmpty = m_Stack.empty();
318 if ( !pRec->bEmpty ) {
319 *(pRec->pValPop) = std::move( m_Stack.top());
324 while ( !m_Stack.empty() )
328 pRec->bEmpty = m_Stack.empty();
334 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
337 /// Batch-processing flat combining
338 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
340 // this function is called under FC mutex, so switch TSan off
341 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
343 typedef typename fc_kernel::iterator fc_iterator;
344 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
345 switch ( it->op() ) {
349 if ( itPrev != itEnd && collide( *itPrev, *it ))
356 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
362 bool collide( fc_record& rec1, fc_record& rec2 )
364 switch ( rec1.op() ) {
366 if ( rec2.op() == op_pop ) {
367 assert(rec1.pValPush);
368 assert(rec2.pValPop);
369 *rec2.pValPop = *rec1.pValPush;
375 if ( rec2.op() == op_pop ) {
376 assert(rec1.pValPush);
377 assert(rec2.pValPop);
378 *rec2.pValPop = std::move( *rec1.pValPush );
384 switch ( rec2.op() ) {
387 return collide( rec2, rec1 );
393 m_FlatCombining.operation_done( rec1 );
394 m_FlatCombining.operation_done( rec2 );
395 m_FlatCombining.internal_statistics().onCollide();
400 }} // namespace cds::container
402 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H