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_FCDEQUE_H
32 #define CDSLIB_CONTAINER_FCDEQUE_H
34 #include <cds/algo/flat_combining.h>
35 #include <cds/algo/elimination_opt.h>
38 namespace cds { namespace container {
40 /// FCDeque related definitions
41 /** @ingroup cds_nonintrusive_helper
45 /// FCDeque 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_nPushFront ; ///< Count of push_front operations
53 counter_type m_nPushFrontMove ; ///< Count of push_front operations with move semantics
54 counter_type m_nPushBack ; ///< Count of push_back operations
55 counter_type m_nPushBackMove ; ///< Count of push_back operations with move semantics
56 counter_type m_nPopFront ; ///< Count of success pop_front operations
57 counter_type m_nFailedPopFront; ///< Count of failed pop_front operations (pop from empty deque)
58 counter_type m_nPopBack ; ///< Count of success pop_back operations
59 counter_type m_nFailedPopBack ; ///< Count of failed pop_back operations (pop from empty deque)
60 counter_type m_nCollided ; ///< How many pairs of push/pop were collided, if elimination is enabled
63 void onPushFront() { ++m_nPushFront; }
64 void onPushFrontMove() { ++m_nPushFrontMove; }
65 void onPushBack() { ++m_nPushBack; }
66 void onPushBackMove() { ++m_nPushBackMove; }
67 void onPopFront( bool bFailed ) { if ( bFailed ) ++m_nFailedPopFront; else ++m_nPopFront; }
68 void onPopBack( bool bFailed ) { if ( bFailed ) ++m_nFailedPopBack; else ++m_nPopBack; }
69 void onCollide() { ++m_nCollided; }
73 /// FCDeque dummy statistics, no overhead
74 struct empty_stat: public cds::algo::flat_combining::empty_stat
78 void onPushFrontMove() {}
80 void onPushBackMove() {}
81 void onPopFront(bool) {}
82 void onPopBack(bool) {}
87 /// FCDeque type traits
88 struct traits: public cds::algo::flat_combining::traits
90 typedef empty_stat stat; ///< Internal statistics
91 static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
94 /// Metafunction converting option list to traits
97 - any \p cds::algo::flat_combining::make_traits options
98 - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
99 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
100 By default, the elimination is disabled. For queue, the elimination is possible if the queue
103 template <typename... Options>
105 # ifdef CDS_DOXYGEN_INVOKED
106 typedef implementation_defined type ; ///< Metafunction result
108 typedef typename cds::opt::make_options<
109 typename cds::opt::find_type_traits< traits, Options... >::type
115 } // namespace fcqueue
117 /// Flat-combining deque
119 @ingroup cds_nonintrusive_deque
120 @ingroup cds_flat_combining_container
122 \ref cds_flat_combining_description "Flat combining" sequential deque.
123 The class can be considered as a concurrent FC-based wrapper for \p std::deque.
126 - \p T - a value type stored in the deque
127 - \p Deque - sequential deque implementation, for example, \p std::deque<T> (the default)
128 or \p boost::container::deque
129 - \p Trats - type traits of flat combining, default is \p fcdeque::traits.
130 \p fcdeque::make_traits metafunction can be used to construct specialized \p %fcdeque::traits
132 template <typename T,
133 class Deque = std::deque<T>,
134 typename Traits = fcdeque::traits
137 #ifndef CDS_DOXYGEN_INVOKED
138 : public cds::algo::flat_combining::container
142 typedef T value_type; ///< Value type
143 typedef Deque deque_type; ///< Sequential deque class
144 typedef Traits traits; ///< Deque type traits
146 typedef typename traits::stat stat; ///< Internal statistics type
147 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
151 /// Deque operation IDs
153 op_push_front = cds::algo::flat_combining::req_Operation, ///< Push front
154 op_push_front_move, ///< Push front (move semantics)
155 op_push_back, ///< Push back
156 op_push_back_move, ///< Push back (move semantics)
157 op_pop_front, ///< Pop front
158 op_pop_back, ///< Pop back
162 /// Flat combining publication list record
163 struct fc_record: public cds::algo::flat_combining::publication_record
166 value_type const * pValPush; ///< Value to push
167 value_type * pValPop; ///< Pop destination
169 bool bEmpty; ///< \p true if the deque is empty
173 /// Flat combining kernel
174 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
178 mutable fc_kernel m_FlatCombining;
183 /// Initializes empty deque object
187 /// Initializes empty deque object and gives flat combining parameters
189 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
190 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
192 : m_FlatCombining( nCompactFactor, nCombinePassCount )
195 /// Inserts a new element at the beginning of the deque container
197 The function always returns \p true
200 value_type const& val ///< Value to be copied to inserted element
203 auto pRec = m_FlatCombining.acquire_record();
204 pRec->pValPush = &val;
206 if ( c_bEliminationEnabled )
207 m_FlatCombining.batch_combine( op_push_front, pRec, *this );
209 m_FlatCombining.combine( op_push_front, pRec, *this );
211 assert( pRec->is_done());
212 m_FlatCombining.release_record( pRec );
213 m_FlatCombining.internal_statistics().onPushFront();
217 /// Inserts a new element at the beginning of the deque container (move semantics)
219 The function always returns \p true
222 value_type&& val ///< Value to be moved to inserted element
225 auto pRec = m_FlatCombining.acquire_record();
226 pRec->pValPush = &val;
228 if ( c_bEliminationEnabled )
229 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
231 m_FlatCombining.combine( op_push_front_move, pRec, *this );
233 assert( pRec->is_done());
234 m_FlatCombining.release_record( pRec );
235 m_FlatCombining.internal_statistics().onPushFrontMove();
239 /// Inserts a new element at the end of the deque container
241 The function always returns \p true
244 value_type const& val ///< Value to be copied to inserted element
247 auto pRec = m_FlatCombining.acquire_record();
248 pRec->pValPush = &val;
250 if ( c_bEliminationEnabled )
251 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
253 m_FlatCombining.combine( op_push_back, pRec, *this );
255 assert( pRec->is_done());
256 m_FlatCombining.release_record( pRec );
257 m_FlatCombining.internal_statistics().onPushBack();
261 /// Inserts a new element at the end of the deque container (move semantics)
263 The function always returns \p true
266 value_type&& val ///< Value to be moved to inserted element
269 auto pRec = m_FlatCombining.acquire_record();
270 pRec->pValPush = &val;
272 if ( c_bEliminationEnabled )
273 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
275 m_FlatCombining.combine( op_push_back_move, pRec, *this );
277 assert( pRec->is_done());
278 m_FlatCombining.release_record( pRec );
279 m_FlatCombining.internal_statistics().onPushBackMove();
283 /// Removes the first 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 auto pRec = m_FlatCombining.acquire_record();
293 pRec->pValPop = &val;
295 if ( c_bEliminationEnabled )
296 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
298 m_FlatCombining.combine( op_pop_front, pRec, *this );
300 assert( pRec->is_done());
301 m_FlatCombining.release_record( pRec );
302 m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
303 return !pRec->bEmpty;
306 /// Removes the last element in the deque container
308 The function returns \p false if the deque is empty, \p true otherwise.
309 If the deque is empty \p val is not changed.
312 value_type& val ///< Target to be received the copy of removed element
315 auto pRec = m_FlatCombining.acquire_record();
316 pRec->pValPop = &val;
318 if ( c_bEliminationEnabled )
319 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
321 m_FlatCombining.combine( op_pop_back, pRec, *this );
323 assert( pRec->is_done());
324 m_FlatCombining.release_record( pRec );
325 m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
326 return !pRec->bEmpty;
332 auto pRec = m_FlatCombining.acquire_record();
334 if ( c_bEliminationEnabled )
335 m_FlatCombining.batch_combine( op_clear, pRec, *this );
337 m_FlatCombining.combine( op_clear, pRec, *this );
339 assert( pRec->is_done());
340 m_FlatCombining.release_record( pRec );
343 /// Returns the number of elements in the deque.
345 Note that <tt>size() == 0</tt> is not mean that the deque is empty because
346 combining record can be in process.
347 To check emptiness use \ref empty function.
351 return m_Deque.size();
354 /// Checks if the deque is empty
356 If the combining is in process the function waits while combining done.
361 auto const& deq = m_Deque;
362 m_FlatCombining.invoke_exclusive( [&deq, &bRet]() { bRet = deq.empty(); } );
366 /// Internal statistics
367 stat const& statistics() const
369 return m_FlatCombining.statistics();
372 public: // flat combining cooperation, not for direct use!
374 /// Flat combining supporting function. Do not call it directly!
376 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
377 object if the current thread becomes a combiner. Invocation of the function means that
378 the deque should perform an action recorded in \p pRec.
380 void fc_apply( fc_record * pRec )
384 // this function is called under FC mutex, so switch TSan off
385 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
387 switch ( pRec->op()) {
389 assert( pRec->pValPush );
390 m_Deque.push_front( *(pRec->pValPush));
392 case op_push_front_move:
393 assert( pRec->pValPush );
394 m_Deque.push_front( std::move( *(pRec->pValPush )));
397 assert( pRec->pValPush );
398 m_Deque.push_back( *(pRec->pValPush));
400 case op_push_back_move:
401 assert( pRec->pValPush );
402 m_Deque.push_back( std::move( *(pRec->pValPush )));
405 assert( pRec->pValPop );
406 pRec->bEmpty = m_Deque.empty();
407 if ( !pRec->bEmpty ) {
408 *(pRec->pValPop) = std::move( m_Deque.front());
413 assert( pRec->pValPop );
414 pRec->bEmpty = m_Deque.empty();
415 if ( !pRec->bEmpty ) {
416 *(pRec->pValPop) = std::move( m_Deque.back());
421 while ( !m_Deque.empty())
428 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
431 /// Batch-processing flat combining
432 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
434 typedef typename fc_kernel::iterator fc_iterator;
436 // this function is called under FC mutex, so switch TSan off
437 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
439 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
443 && (itPrev->op() == op_pop_front || (m_Deque.empty() && itPrev->op() == op_pop_back)))
445 collide( *it, *itPrev );
451 case op_push_front_move:
453 && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
455 collide_move( *it, *itPrev );
463 && (itPrev->op() == op_pop_back || (m_Deque.empty() && itPrev->op() == op_pop_front)))
465 collide( *it, *itPrev );
471 case op_push_back_move:
473 && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
475 collide_move( *it, *itPrev );
482 if ( itPrev != itEnd ) {
483 if ( m_Deque.empty()) {
484 switch ( itPrev->op()) {
486 collide( *itPrev, *it );
489 case op_push_back_move:
490 collide_move( *itPrev, *it );
499 switch ( itPrev->op()) {
501 collide( *itPrev, *it );
504 case op_push_front_move:
505 collide_move( *itPrev, *it );
518 if ( itPrev != itEnd ) {
519 if ( m_Deque.empty()) {
520 switch ( itPrev->op()) {
522 collide( *itPrev, *it );
525 case op_push_front_move:
526 collide_move( *itPrev, *it );
535 switch ( itPrev->op()) {
537 collide( *itPrev, *it );
540 case op_push_back_move:
541 collide_move( *itPrev, *it );
555 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
561 void collide( fc_record& recPush, fc_record& recPop )
563 *(recPop.pValPop) = *(recPush.pValPush);
564 recPop.bEmpty = false;
565 m_FlatCombining.operation_done( recPush );
566 m_FlatCombining.operation_done( recPop );
567 m_FlatCombining.internal_statistics().onCollide();
570 void collide_move( fc_record& recPush, fc_record& recPop )
572 *(recPop.pValPop) = std::move( *(recPush.pValPush));
573 recPop.bEmpty = false;
574 m_FlatCombining.operation_done( recPush );
575 m_FlatCombining.operation_done( recPop );
576 m_FlatCombining.internal_statistics().onCollide();
581 }} // namespace cds::container
583 #endif // #ifndef CDSLIB_CONTAINER_FCDEQUE_H