3 #ifndef CDSLIB_CONTAINER_FCDEQUE_H
4 #define CDSLIB_CONTAINER_FCDEQUE_H
6 #include <cds/algo/flat_combining.h>
7 #include <cds/algo/elimination_opt.h>
10 namespace cds { namespace container {
12 /// FCDeque related definitions
13 /** @ingroup cds_nonintrusive_helper
17 /// FCDeque 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_nPushFront ; ///< Count of push_front operations
25 counter_type m_nPushFrontMove ; ///< Count of push_front operations with move semantics
26 counter_type m_nPushBack ; ///< Count of push_back operations
27 counter_type m_nPushBackMove ; ///< Count of push_back operations with move semantics
28 counter_type m_nPopFront ; ///< Count of success pop_front operations
29 counter_type m_nFailedPopFront; ///< Count of failed pop_front operations (pop from empty deque)
30 counter_type m_nPopBack ; ///< Count of success pop_back operations
31 counter_type m_nFailedPopBack ; ///< Count of failed pop_back operations (pop from empty deque)
32 counter_type m_nCollided ; ///< How many pairs of push/pop were collided, if elimination is enabled
35 void onPushFront() { ++m_nPushFront; }
36 void onPushFrontMove() { ++m_nPushFrontMove; }
37 void onPushBack() { ++m_nPushBack; }
38 void onPushBackMove() { ++m_nPushBackMove; }
39 void onPopFront( bool bFailed ) { if ( bFailed ) ++m_nFailedPopFront; else ++m_nPopFront; }
40 void onPopBack( bool bFailed ) { if ( bFailed ) ++m_nFailedPopBack; else ++m_nPopBack; }
41 void onCollide() { ++m_nCollided; }
45 /// FCDeque dummy statistics, no overhead
46 struct empty_stat: public cds::algo::flat_combining::empty_stat
50 void onPushFrontMove() {}
52 void onPushBackMove() {}
53 void onPopFront(bool) {}
54 void onPopBack(bool) {}
59 /// FCDeque type traits
60 struct traits: public cds::algo::flat_combining::traits
62 typedef empty_stat stat; ///< Internal statistics
63 static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
66 /// Metafunction converting option list to traits
69 - \p opt::lock_type - mutex type, default is \p cds::sync::spin
70 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::delay_of<2>
71 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
72 - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
73 - \p opt::memory_model - C++ memory ordering model.
74 List of all available memory ordering see opt::memory_model.
75 Default if cds::opt::v:relaxed_ordering
76 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
77 By default, the elimination is disabled. For queue, the elimination is possible if the queue
80 template <typename... Options>
82 # ifdef CDS_DOXYGEN_INVOKED
83 typedef implementation_defined type ; ///< Metafunction result
85 typedef typename cds::opt::make_options<
86 typename cds::opt::find_type_traits< traits, Options... >::type
92 } // namespace fcqueue
94 /// Flat-combining deque
96 @ingroup cds_nonintrusive_deque
97 @ingroup cds_flat_combining_container
99 \ref cds_flat_combining_description "Flat combining" sequential deque.
100 The class can be considered as a concurrent FC-based wrapper for \p std::deque.
103 - \p T - a value type stored in the deque
104 - \p Deque - sequential deque implementation, for example, \p std::deque<T> (the default)
105 or \p boost::container::deque
106 - \p Trats - type traits of flat combining, default is \p fcdeque::traits.
107 \p fcdeque::make_traits metafunction can be used to construct specialized \p %fcdeque::traits
109 template <typename T,
110 class Deque = std::deque<T>,
111 typename Traits = fcdeque::traits
114 #ifndef CDS_DOXYGEN_INVOKED
115 : public cds::algo::flat_combining::container
119 typedef T value_type; ///< Value type
120 typedef Deque deque_type; ///< Sequential deque class
121 typedef Traits traits; ///< Deque type traits
123 typedef typename traits::stat stat; ///< Internal statistics type
124 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
128 /// Deque operation IDs
130 op_push_front = cds::algo::flat_combining::req_Operation, ///< Push front
131 op_push_front_move, ///< Push front (move semantics)
132 op_push_back, ///< Push back
133 op_push_back_move, ///< Push back (move semantics)
134 op_pop_front, ///< Pop front
135 op_pop_back, ///< Pop back
139 /// Flat combining publication list record
140 struct fc_record: public cds::algo::flat_combining::publication_record
143 value_type const * pValPush; ///< Value to push
144 value_type * pValPop; ///< Pop destination
146 bool bEmpty; ///< \p true if the deque is empty
150 /// Flat combining kernel
151 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
155 fc_kernel m_FlatCombining;
160 /// Initializes empty deque object
164 /// Initializes empty deque object and gives flat combining parameters
166 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
167 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
169 : m_FlatCombining( nCompactFactor, nCombinePassCount )
172 /// Inserts a new element at the beginning of the deque container
174 The function always returns \p true
177 value_type const& val ///< Value to be copied to inserted element
180 fc_record * pRec = m_FlatCombining.acquire_record();
181 pRec->pValPush = &val;
183 if ( c_bEliminationEnabled )
184 m_FlatCombining.batch_combine( op_push_front, pRec, *this );
186 m_FlatCombining.combine( op_push_front, pRec, *this );
188 assert( pRec->is_done() );
189 m_FlatCombining.release_record( pRec );
190 m_FlatCombining.internal_statistics().onPushFront();
194 /// Inserts a new element at the beginning of the deque container (move semantics)
196 The function always returns \p true
199 value_type&& val ///< Value to be moved to inserted element
202 fc_record * pRec = m_FlatCombining.acquire_record();
203 pRec->pValPush = &val;
205 if ( c_bEliminationEnabled )
206 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
208 m_FlatCombining.combine( op_push_front_move, pRec, *this );
210 assert( pRec->is_done() );
211 m_FlatCombining.release_record( pRec );
212 m_FlatCombining.internal_statistics().onPushFrontMove();
216 /// Inserts a new element at the end of the deque container
218 The function always returns \p true
221 value_type const& val ///< Value to be copied to inserted element
224 fc_record * pRec = m_FlatCombining.acquire_record();
225 pRec->pValPush = &val;
227 if ( c_bEliminationEnabled )
228 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
230 m_FlatCombining.combine( op_push_back, pRec, *this );
232 assert( pRec->is_done() );
233 m_FlatCombining.release_record( pRec );
234 m_FlatCombining.internal_statistics().onPushBack();
238 /// Inserts a new element at the end of the deque container (move semantics)
240 The function always returns \p true
243 value_type&& val ///< Value to be moved to inserted element
246 fc_record * pRec = m_FlatCombining.acquire_record();
247 pRec->pValPush = &val;
249 if ( c_bEliminationEnabled )
250 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
252 m_FlatCombining.combine( op_push_back_move, pRec, *this );
254 assert( pRec->is_done() );
255 m_FlatCombining.release_record( pRec );
256 m_FlatCombining.internal_statistics().onPushBackMove();
260 /// Removes the first element in the deque container
262 The function returns \p false if the deque is empty, \p true otherwise.
263 If the deque is empty \p val is not changed.
266 value_type& val ///< Target to be received the copy of removed element
269 fc_record * pRec = m_FlatCombining.acquire_record();
270 pRec->pValPop = &val;
272 if ( c_bEliminationEnabled )
273 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
275 m_FlatCombining.combine( op_pop_front, pRec, *this );
277 assert( pRec->is_done() );
278 m_FlatCombining.release_record( pRec );
279 m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
280 return !pRec->bEmpty;
283 /// Removes the last element in the deque container
285 The function returns \p false if the deque is empty, \p true otherwise.
286 If the deque is empty \p val is not changed.
289 value_type& val ///< Target to be received the copy of removed element
292 fc_record * pRec = m_FlatCombining.acquire_record();
293 pRec->pValPop = &val;
295 if ( c_bEliminationEnabled )
296 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
298 m_FlatCombining.combine( op_pop_back, pRec, *this );
300 assert( pRec->is_done() );
301 m_FlatCombining.release_record( pRec );
302 m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
303 return !pRec->bEmpty;
309 fc_record * pRec = m_FlatCombining.acquire_record();
311 if ( c_bEliminationEnabled )
312 m_FlatCombining.batch_combine( op_clear, pRec, *this );
314 m_FlatCombining.combine( op_clear, pRec, *this );
316 assert( pRec->is_done() );
317 m_FlatCombining.release_record( pRec );
320 /// Returns the number of elements in the deque.
322 Note that <tt>size() == 0</tt> is not mean that the deque is empty because
323 combining record can be in process.
324 To check emptiness use \ref empty function.
328 return m_Deque.size();
331 /// Checks if the deque is empty
333 If the combining is in process the function waits while combining done.
337 m_FlatCombining.wait_while_combining();
338 return m_Deque.empty();
341 /// Internal statistics
342 stat const& statistics() const
344 return m_FlatCombining.statistics();
347 public: // flat combining cooperation, not for direct use!
349 /// Flat combining supporting function. Do not call it directly!
351 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
352 object if the current thread becomes a combiner. Invocation of the function means that
353 the deque should perform an action recorded in \p pRec.
355 void fc_apply( fc_record * pRec )
359 switch ( pRec->op() ) {
361 assert( pRec->pValPush );
362 m_Deque.push_front( *(pRec->pValPush) );
364 case op_push_front_move:
365 assert( pRec->pValPush );
366 m_Deque.push_front( std::move( *(pRec->pValPush )) );
369 assert( pRec->pValPush );
370 m_Deque.push_back( *(pRec->pValPush) );
372 case op_push_back_move:
373 assert( pRec->pValPush );
374 m_Deque.push_back( std::move( *(pRec->pValPush )) );
377 assert( pRec->pValPop );
378 pRec->bEmpty = m_Deque.empty();
379 if ( !pRec->bEmpty ) {
380 *(pRec->pValPop) = m_Deque.front();
385 assert( pRec->pValPop );
386 pRec->bEmpty = m_Deque.empty();
387 if ( !pRec->bEmpty ) {
388 *(pRec->pValPop) = m_Deque.back();
393 while ( !m_Deque.empty() )
402 /// Batch-processing flat combining
403 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
405 typedef typename fc_kernel::iterator fc_iterator;
406 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
407 switch ( it->op() ) {
409 case op_push_front_move:
411 && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
413 collide( *it, *itPrev );
420 case op_push_back_move:
422 && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
424 collide( *it, *itPrev );
432 && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
433 || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
435 collide( *itPrev, *it );
443 && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
444 || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
446 collide( *itPrev, *it );
459 void collide( fc_record& recPush, fc_record& recPop )
461 *(recPop.pValPop) = *(recPush.pValPush);
462 recPop.bEmpty = false;
463 m_FlatCombining.operation_done( recPush );
464 m_FlatCombining.operation_done( recPop );
465 m_FlatCombining.internal_statistics().onCollide();
470 }} // namespace cds::container
472 #endif // #ifndef CDSLIB_CONTAINER_FCDEQUE_H