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 - \p opt::lock_type - mutex type, default is \p cds::sync::spin
88 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
89 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
90 - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
91 - \p opt::memory_model - C++ memory ordering model.
92 List of all available memory ordering see \p opt::memory_model.
93 Default is \p cds::opt::v:relaxed_ordering
94 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
95 By default, the elimination is disabled.
97 template <typename... Options>
99 # ifdef CDS_DOXYGEN_INVOKED
100 typedef implementation_defined type ; ///< Metafunction result
102 typedef typename cds::opt::make_options<
103 typename cds::opt::find_type_traits< traits, Options... >::type
109 } // namespace fcstack
111 /// Flat-combining stack
113 @ingroup cds_nonintrusive_stack
114 @ingroup cds_flat_combining_container
116 \ref cds_flat_combining_description "Flat combining" sequential stack.
119 - \p T - a value type stored in the stack
120 - \p Stack - sequential stack implementation, default is \p std::stack<T>
121 - \p Trats - type traits of flat combining, default is \p fcstack::traits
122 \p fcstack::make_traits metafunction can be used to construct specialized \p %fcstack::traits
124 template <typename T,
125 class Stack = std::stack<T>,
126 typename Traits = fcstack::traits
129 #ifndef CDS_DOXYGEN_INVOKED
130 : public cds::algo::flat_combining::container
134 typedef T value_type; ///< Value type
135 typedef Stack stack_type; ///< Sequential stack class
136 typedef Traits traits; ///< Stack traits
138 typedef typename traits::stat stat; ///< Internal statistics type
139 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
143 /// Stack operation IDs
145 op_push = cds::algo::flat_combining::req_Operation, ///< Push
146 op_push_move, ///< Push (move semantics)
152 /// Flat combining publication list record
153 struct fc_record: public cds::algo::flat_combining::publication_record
156 value_type const * pValPush; ///< Value to push
157 value_type * pValPop; ///< Pop destination
159 bool bEmpty; ///< \p true if the stack is empty
163 /// Flat combining kernel
164 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
168 fc_kernel m_FlatCombining;
173 /// Initializes empty stack object
177 /// Initializes empty stack object and gives flat combining parameters
179 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
180 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
182 : m_FlatCombining( nCompactFactor, nCombinePassCount )
185 /// Inserts a new element at the top of stack
187 The content of the new element initialized to a copy of \p val.
189 bool push( value_type const& val )
191 fc_record * pRec = m_FlatCombining.acquire_record();
192 pRec->pValPush = &val;
194 if ( c_bEliminationEnabled )
195 m_FlatCombining.batch_combine( op_push, pRec, *this );
197 m_FlatCombining.combine( op_push, pRec, *this );
199 assert( pRec->is_done() );
200 m_FlatCombining.release_record( pRec );
201 m_FlatCombining.internal_statistics().onPush();
205 /// Inserts a new element at the top of stack (move semantics)
207 The content of the new element initialized to a copy of \p val.
209 bool push( value_type&& val )
211 fc_record * pRec = m_FlatCombining.acquire_record();
212 pRec->pValPush = &val;
214 if ( c_bEliminationEnabled )
215 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
217 m_FlatCombining.combine( op_push_move, pRec, *this );
219 assert( pRec->is_done() );
220 m_FlatCombining.release_record( pRec );
222 m_FlatCombining.internal_statistics().onPushMove();
226 /// Removes the element on top of the stack
228 \p val takes a copy of top element
230 bool pop( value_type& val )
232 fc_record * pRec = m_FlatCombining.acquire_record();
233 pRec->pValPop = &val;
235 if ( c_bEliminationEnabled )
236 m_FlatCombining.batch_combine( op_pop, pRec, *this );
238 m_FlatCombining.combine( op_pop, pRec, *this );
240 assert( pRec->is_done() );
241 m_FlatCombining.release_record( pRec );
243 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
244 return !pRec->bEmpty;
250 fc_record * pRec = m_FlatCombining.acquire_record();
252 if ( c_bEliminationEnabled )
253 m_FlatCombining.batch_combine( op_clear, pRec, *this );
255 m_FlatCombining.combine( op_clear, pRec, *this );
257 assert( pRec->is_done() );
258 m_FlatCombining.release_record( pRec );
261 /// Returns the number of elements in the stack.
263 Note that <tt>size() == 0</tt> is not mean that the stack is empty because
264 combining record can be in process.
265 To check emptiness use \ref empty function.
269 return m_Stack.size();
272 /// Checks if the stack is empty
274 If the combining is in process the function waits while combining done.
278 fc_record * pRec = m_FlatCombining.acquire_record();
280 if ( c_bEliminationEnabled )
281 m_FlatCombining.batch_combine( op_empty, pRec, *this );
283 m_FlatCombining.combine( op_empty, pRec, *this );
285 assert( pRec->is_done() );
286 m_FlatCombining.release_record( pRec );
290 /// Internal statistics
291 stat const& statistics() const
293 return m_FlatCombining.statistics();
297 public: // flat combining cooperation, not for direct use!
299 /// Flat combining supporting function. Do not call it directly!
301 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
302 object if the current thread becomes a combiner. Invocation of the function means that
303 the stack should perform an action recorded in \p pRec.
305 void fc_apply( fc_record * pRec )
309 // this function is called under FC mutex, so switch TSan off
310 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
311 switch ( pRec->op() ) {
313 assert( pRec->pValPush );
314 m_Stack.push( *(pRec->pValPush ) );
317 assert( pRec->pValPush );
318 m_Stack.push( std::move( *(pRec->pValPush )) );
321 assert( pRec->pValPop );
322 pRec->bEmpty = m_Stack.empty();
323 if ( !pRec->bEmpty ) {
324 *(pRec->pValPop) = std::move( m_Stack.top());
329 while ( !m_Stack.empty() )
333 pRec->bEmpty = m_Stack.empty();
339 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
342 /// Batch-processing flat combining
343 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
345 // this function is called under FC mutex, so switch TSan off
346 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
348 typedef typename fc_kernel::iterator fc_iterator;
349 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
350 switch ( it->op() ) {
354 if ( itPrev != itEnd && collide( *itPrev, *it ))
361 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
367 bool collide( fc_record& rec1, fc_record& rec2 )
369 switch ( rec1.op() ) {
371 if ( rec2.op() == op_pop ) {
372 assert(rec1.pValPush);
373 assert(rec2.pValPop);
374 *rec2.pValPop = *rec1.pValPush;
380 if ( rec2.op() == op_pop ) {
381 assert(rec1.pValPush);
382 assert(rec2.pValPop);
383 *rec2.pValPop = std::move( *rec1.pValPush );
389 switch ( rec2.op() ) {
392 return collide( rec2, rec1 );
398 m_FlatCombining.operation_done( rec1 );
399 m_FlatCombining.operation_done( rec2 );
400 m_FlatCombining.internal_statistics().onCollide();
405 }} // namespace cds::container
407 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H