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
140 /// Flat combining publication list record
141 struct fc_record: public cds::algo::flat_combining::publication_record
144 value_type const * pValPush; ///< Value to push
145 value_type * pValPop; ///< Pop destination
147 bool bEmpty; ///< \p true if the deque is empty
151 /// Flat combining kernel
152 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
156 fc_kernel m_FlatCombining;
161 /// Initializes empty deque object
165 /// Initializes empty deque object and gives flat combining parameters
167 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
168 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
170 : m_FlatCombining( nCompactFactor, nCombinePassCount )
173 /// Inserts a new element at the beginning of the deque container
175 The function always returns \p true
178 value_type const& val ///< Value to be copied to inserted element
181 fc_record * pRec = m_FlatCombining.acquire_record();
182 pRec->pValPush = &val;
184 if ( c_bEliminationEnabled )
185 m_FlatCombining.batch_combine( op_push_front, pRec, *this );
187 m_FlatCombining.combine( op_push_front, pRec, *this );
189 assert( pRec->is_done() );
190 m_FlatCombining.release_record( pRec );
191 m_FlatCombining.internal_statistics().onPushFront();
195 /// Inserts a new element at the beginning of the deque container (move semantics)
197 The function always returns \p true
200 value_type&& val ///< Value to be moved to inserted element
203 fc_record * pRec = m_FlatCombining.acquire_record();
204 pRec->pValPush = &val;
206 if ( c_bEliminationEnabled )
207 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
209 m_FlatCombining.combine( op_push_front_move, pRec, *this );
211 assert( pRec->is_done() );
212 m_FlatCombining.release_record( pRec );
213 m_FlatCombining.internal_statistics().onPushFrontMove();
217 /// Inserts a new element at the end of the deque container
219 The function always returns \p true
222 value_type const& val ///< Value to be copied to inserted element
225 fc_record * pRec = m_FlatCombining.acquire_record();
226 pRec->pValPush = &val;
228 if ( c_bEliminationEnabled )
229 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
231 m_FlatCombining.combine( op_push_back, pRec, *this );
233 assert( pRec->is_done() );
234 m_FlatCombining.release_record( pRec );
235 m_FlatCombining.internal_statistics().onPushBack();
239 /// Inserts a new element at the end of the deque container (move semantics)
241 The function always returns \p true
244 value_type&& val ///< Value to be moved to inserted element
247 fc_record * pRec = m_FlatCombining.acquire_record();
248 pRec->pValPush = &val;
250 if ( c_bEliminationEnabled )
251 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
253 m_FlatCombining.combine( op_push_back_move, pRec, *this );
255 assert( pRec->is_done() );
256 m_FlatCombining.release_record( pRec );
257 m_FlatCombining.internal_statistics().onPushBackMove();
261 /// Removes the first element in the deque container
263 The function returns \p false if the deque is empty, \p true otherwise.
264 If the deque is empty \p val is not changed.
267 value_type& val ///< Target to be received the copy of removed element
270 fc_record * pRec = m_FlatCombining.acquire_record();
271 pRec->pValPop = &val;
273 if ( c_bEliminationEnabled )
274 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
276 m_FlatCombining.combine( op_pop_front, pRec, *this );
278 assert( pRec->is_done() );
279 m_FlatCombining.release_record( pRec );
280 m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
281 return !pRec->bEmpty;
284 /// Removes the last element in the deque container
286 The function returns \p false if the deque is empty, \p true otherwise.
287 If the deque is empty \p val is not changed.
290 value_type& val ///< Target to be received the copy of removed element
293 fc_record * pRec = m_FlatCombining.acquire_record();
294 pRec->pValPop = &val;
296 if ( c_bEliminationEnabled )
297 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
299 m_FlatCombining.combine( op_pop_back, pRec, *this );
301 assert( pRec->is_done() );
302 m_FlatCombining.release_record( pRec );
303 m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
304 return !pRec->bEmpty;
310 fc_record * pRec = m_FlatCombining.acquire_record();
312 if ( c_bEliminationEnabled )
313 m_FlatCombining.batch_combine( op_clear, pRec, *this );
315 m_FlatCombining.combine( op_clear, pRec, *this );
317 assert( pRec->is_done() );
318 m_FlatCombining.release_record( pRec );
321 /// Returns the number of elements in the deque.
323 Note that <tt>size() == 0</tt> is not mean that the deque is empty because
324 combining record can be in process.
325 To check emptiness use \ref empty function.
329 return m_Deque.size();
332 /// Checks if the deque is empty
334 If the combining is in process the function waits while combining done.
338 fc_record * pRec = m_FlatCombining.acquire_record();
340 if ( c_bEliminationEnabled )
341 m_FlatCombining.batch_combine( op_empty, pRec, *this );
343 m_FlatCombining.combine( op_empty, pRec, *this );
345 assert( pRec->is_done() );
346 m_FlatCombining.release_record( pRec );
350 /// Internal statistics
351 stat const& statistics() const
353 return m_FlatCombining.statistics();
356 public: // flat combining cooperation, not for direct use!
358 /// Flat combining supporting function. Do not call it directly!
360 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
361 object if the current thread becomes a combiner. Invocation of the function means that
362 the deque should perform an action recorded in \p pRec.
364 void fc_apply( fc_record * pRec )
368 // this function is called under FC mutex, so switch TSan off
369 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
371 switch ( pRec->op() ) {
373 assert( pRec->pValPush );
374 m_Deque.push_front( *(pRec->pValPush) );
376 case op_push_front_move:
377 assert( pRec->pValPush );
378 m_Deque.push_front( std::move( *(pRec->pValPush )) );
381 assert( pRec->pValPush );
382 m_Deque.push_back( *(pRec->pValPush) );
384 case op_push_back_move:
385 assert( pRec->pValPush );
386 m_Deque.push_back( std::move( *(pRec->pValPush )) );
389 assert( pRec->pValPop );
390 pRec->bEmpty = m_Deque.empty();
391 if ( !pRec->bEmpty ) {
392 *(pRec->pValPop) = m_Deque.front();
397 assert( pRec->pValPop );
398 pRec->bEmpty = m_Deque.empty();
399 if ( !pRec->bEmpty ) {
400 *(pRec->pValPop) = m_Deque.back();
405 while ( !m_Deque.empty() )
409 pRec->bEmpty = m_Deque.empty();
415 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
418 /// Batch-processing flat combining
419 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
421 typedef typename fc_kernel::iterator fc_iterator;
423 // this function is called under FC mutex, so switch TSan off
424 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
426 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
427 switch ( it->op() ) {
429 case op_push_front_move:
431 && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
433 collide( *it, *itPrev );
440 case op_push_back_move:
442 && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
444 collide( *it, *itPrev );
452 && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
453 || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
455 collide( *itPrev, *it );
463 && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
464 || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
466 collide( *itPrev, *it );
474 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
480 void collide( fc_record& recPush, fc_record& recPop )
482 *(recPop.pValPop) = *(recPush.pValPush);
483 recPop.bEmpty = false;
484 m_FlatCombining.operation_done( recPush );
485 m_FlatCombining.operation_done( recPop );
486 m_FlatCombining.internal_statistics().onCollide();
491 }} // namespace cds::container
493 #endif // #ifndef CDSLIB_CONTAINER_FCDEQUE_H