3 #ifndef __CDS_CONTAINER_FCDEQUE_H
4 #define __CDS_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 type_traits: public cds::algo::flat_combining::type_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
68 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
70 - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
71 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
72 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
73 - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
74 - \p opt::memory_model - C++ memory ordering model.
75 List of all available memory ordering see opt::memory_model.
76 Default if cds::opt::v:relaxed_ordering
77 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
78 By default, the elimination is disabled. For queue, the elimination is possible if the queue
81 template <typename... Options>
83 # ifdef CDS_DOXYGEN_INVOKED
84 typedef implementation_defined type ; ///< Metafunction result
86 typedef typename cds::opt::make_options<
87 typename cds::opt::find_type_traits< type_traits, Options... >::type
93 } // namespace fcqueue
95 /// Flat-combining deque
97 @ingroup cds_nonintrusive_deque
98 @ingroup cds_flat_combining_container
100 \ref cds_flat_combining_description "Flat combining" sequential deque.
101 The class can be considered as a concurrent FC-based wrapper for \p std::deque.
104 - \p T - a value type stored in the deque
105 - \p Deque - sequential deque implementation, for example, \p std::deque<T> (the default)
106 or \p boost::container::deque
107 - \p Trats - type traits of flat combining, default is \p fcdeque::type_traits.
108 \p fcdeque::make_traits metafunction can be used to construct specialized \p %type_traits
110 template <typename T,
111 class Deque = std::deque<T>,
112 typename Traits = fcdeque::type_traits
115 #ifndef CDS_DOXYGEN_INVOKED
116 : public cds::algo::flat_combining::container
120 typedef T value_type; ///< Value type
121 typedef Deque deque_type; ///< Sequential deque class
122 typedef Traits type_traits; ///< Deque type traits
124 typedef typename type_traits::stat stat; ///< Internal statistics type
125 static CDS_CONSTEXPR_CONST bool c_bEliminationEnabled = type_traits::enable_elimination; ///< \p true if elimination is enabled
129 /// Deque operation IDs
131 op_push_front = cds::algo::flat_combining::req_Operation, ///< Push front
132 op_push_front_move, ///< Push front (move semantics)
133 op_push_back, ///< Push back
134 op_push_back_move, ///< Push back (move semantics)
135 op_pop_front, ///< Pop front
136 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, type_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 m_FlatCombining.wait_while_combining();
339 return m_Deque.empty();
342 /// Internal statistics
343 stat const& statistics() const
345 return m_FlatCombining.statistics();
348 public: // flat combining cooperation, not for direct use!
350 /// Flat combining supporting function. Do not call it directly!
352 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
353 object if the current thread becomes a combiner. Invocation of the function means that
354 the deque should perform an action recorded in \p pRec.
356 void fc_apply( fc_record * pRec )
360 switch ( pRec->op() ) {
362 assert( pRec->pValPush );
363 m_Deque.push_front( *(pRec->pValPush) );
365 case op_push_front_move:
366 assert( pRec->pValPush );
367 m_Deque.push_front( std::move( *(pRec->pValPush )) );
370 assert( pRec->pValPush );
371 m_Deque.push_back( *(pRec->pValPush) );
373 case op_push_back_move:
374 assert( pRec->pValPush );
375 m_Deque.push_back( std::move( *(pRec->pValPush )) );
378 assert( pRec->pValPop );
379 pRec->bEmpty = m_Deque.empty();
380 if ( !pRec->bEmpty ) {
381 *(pRec->pValPop) = m_Deque.front();
386 assert( pRec->pValPop );
387 pRec->bEmpty = m_Deque.empty();
388 if ( !pRec->bEmpty ) {
389 *(pRec->pValPop) = m_Deque.back();
394 while ( !m_Deque.empty() )
403 /// Batch-processing flat combining
404 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
406 typedef typename fc_kernel::iterator fc_iterator;
407 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
408 switch ( it->op() ) {
410 case op_push_front_move:
412 && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
414 collide( *it, *itPrev );
421 case op_push_back_move:
423 && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
425 collide( *it, *itPrev );
433 && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
434 || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
436 collide( *itPrev, *it );
444 && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
445 || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
447 collide( *itPrev, *it );
460 void collide( fc_record& recPush, fc_record& recPop )
462 *(recPop.pValPop) = *(recPush.pValPush);
463 recPop.bEmpty = false;
464 m_FlatCombining.operation_done( recPush );
465 m_FlatCombining.operation_done( recPop );
466 m_FlatCombining.internal_statistics().onCollide();
471 }} // namespace cds::container
473 #endif // #ifndef __CDS_CONTAINER_FCDEQUE_H