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 <CDS_DECL_OPTIONS8>
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, CDS_OPTIONS8 >::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 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
196 /// Inserts a new element at the beginning of the deque container (move semantics)
198 The function always returns \p true
201 value_type&& val ///< Value to be moved to inserted element
204 fc_record * pRec = m_FlatCombining.acquire_record();
205 pRec->pValPush = &val;
207 if ( c_bEliminationEnabled )
208 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
210 m_FlatCombining.combine( op_push_front_move, pRec, *this );
212 assert( pRec->is_done() );
213 m_FlatCombining.release_record( pRec );
214 m_FlatCombining.internal_statistics().onPushFrontMove();
219 /// Inserts a new element at the end of the deque container
221 The function always returns \p true
224 value_type const& val ///< Value to be copied to inserted element
227 fc_record * pRec = m_FlatCombining.acquire_record();
228 pRec->pValPush = &val;
230 if ( c_bEliminationEnabled )
231 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
233 m_FlatCombining.combine( op_push_back, pRec, *this );
235 assert( pRec->is_done() );
236 m_FlatCombining.release_record( pRec );
237 m_FlatCombining.internal_statistics().onPushBack();
241 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
242 /// Inserts a new element at the end of the deque container (move semantics)
244 The function always returns \p true
247 value_type&& val ///< Value to be moved to inserted element
250 fc_record * pRec = m_FlatCombining.acquire_record();
251 pRec->pValPush = &val;
253 if ( c_bEliminationEnabled )
254 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
256 m_FlatCombining.combine( op_push_back_move, pRec, *this );
258 assert( pRec->is_done() );
259 m_FlatCombining.release_record( pRec );
260 m_FlatCombining.internal_statistics().onPushBackMove();
265 /// Removes the first element in the deque container
267 The function returns \p false if the deque is empty, \p true otherwise.
268 If the deque is empty \p val is not changed.
271 value_type& val ///< Target to be received the copy of removed element
274 fc_record * pRec = m_FlatCombining.acquire_record();
275 pRec->pValPop = &val;
277 if ( c_bEliminationEnabled )
278 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
280 m_FlatCombining.combine( op_pop_front, pRec, *this );
282 assert( pRec->is_done() );
283 m_FlatCombining.release_record( pRec );
284 m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
285 return !pRec->bEmpty;
288 /// Removes the last element in the deque container
290 The function returns \p false if the deque is empty, \p true otherwise.
291 If the deque is empty \p val is not changed.
294 value_type& val ///< Target to be received the copy of removed element
297 fc_record * pRec = m_FlatCombining.acquire_record();
298 pRec->pValPop = &val;
300 if ( c_bEliminationEnabled )
301 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
303 m_FlatCombining.combine( op_pop_back, pRec, *this );
305 assert( pRec->is_done() );
306 m_FlatCombining.release_record( pRec );
307 m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
308 return !pRec->bEmpty;
314 fc_record * pRec = m_FlatCombining.acquire_record();
316 if ( c_bEliminationEnabled )
317 m_FlatCombining.batch_combine( op_clear, pRec, *this );
319 m_FlatCombining.combine( op_clear, pRec, *this );
321 assert( pRec->is_done() );
322 m_FlatCombining.release_record( pRec );
325 /// Returns the number of elements in the deque.
327 Note that <tt>size() == 0</tt> is not mean that the deque is empty because
328 combining record can be in process.
329 To check emptiness use \ref empty function.
333 return m_Deque.size();
336 /// Checks if the deque is empty
338 If the combining is in process the function waits while combining done.
342 m_FlatCombining.wait_while_combining();
343 return m_Deque.empty();
346 /// Internal statistics
347 stat const& statistics() const
349 return m_FlatCombining.statistics();
352 public: // flat combining cooperation, not for direct use!
354 /// Flat combining supporting function. Do not call it directly!
356 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
357 object if the current thread becomes a combiner. Invocation of the function means that
358 the deque should perform an action recorded in \p pRec.
360 void fc_apply( fc_record * pRec )
364 switch ( pRec->op() ) {
366 assert( pRec->pValPush );
367 m_Deque.push_front( *(pRec->pValPush) );
369 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
370 case op_push_front_move:
371 assert( pRec->pValPush );
372 m_Deque.push_front( std::move( *(pRec->pValPush )) );
376 assert( pRec->pValPush );
377 m_Deque.push_back( *(pRec->pValPush) );
379 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
380 case op_push_back_move:
381 assert( pRec->pValPush );
382 m_Deque.push_back( std::move( *(pRec->pValPush )) );
386 assert( pRec->pValPop );
387 pRec->bEmpty = m_Deque.empty();
388 if ( !pRec->bEmpty ) {
389 *(pRec->pValPop) = m_Deque.front();
394 assert( pRec->pValPop );
395 pRec->bEmpty = m_Deque.empty();
396 if ( !pRec->bEmpty ) {
397 *(pRec->pValPop) = m_Deque.back();
402 while ( !m_Deque.empty() )
411 /// Batch-processing flat combining
412 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
414 typedef typename fc_kernel::iterator fc_iterator;
415 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
416 switch ( it->op() ) {
418 case op_push_front_move:
420 && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
422 collide( *it, *itPrev );
429 case op_push_back_move:
431 && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
433 collide( *it, *itPrev );
441 && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
442 || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
444 collide( *itPrev, *it );
452 && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
453 || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
455 collide( *itPrev, *it );
468 void collide( fc_record& recPush, fc_record& recPop )
470 *(recPop.pValPop) = *(recPush.pValPush);
471 recPop.bEmpty = false;
472 m_FlatCombining.operation_done( recPush );
473 m_FlatCombining.operation_done( recPop );
474 m_FlatCombining.internal_statistics().onCollide();
479 }} // namespace cds::container
481 #endif // #ifndef __CDS_CONTAINER_FCDEQUE_H