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 - \p opt::lock_type - mutex type, default is \p cds::sync::spin
98 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::delay_of<2>
99 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
100 - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
101 - \p opt::memory_model - C++ memory ordering model.
102 List of all available memory ordering see opt::memory_model.
103 Default if cds::opt::v:relaxed_ordering
104 - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
105 By default, the elimination is disabled. For queue, the elimination is possible if the queue
108 template <typename... Options>
110 # ifdef CDS_DOXYGEN_INVOKED
111 typedef implementation_defined type ; ///< Metafunction result
113 typedef typename cds::opt::make_options<
114 typename cds::opt::find_type_traits< traits, Options... >::type
120 } // namespace fcqueue
122 /// Flat-combining deque
124 @ingroup cds_nonintrusive_deque
125 @ingroup cds_flat_combining_container
127 \ref cds_flat_combining_description "Flat combining" sequential deque.
128 The class can be considered as a concurrent FC-based wrapper for \p std::deque.
131 - \p T - a value type stored in the deque
132 - \p Deque - sequential deque implementation, for example, \p std::deque<T> (the default)
133 or \p boost::container::deque
134 - \p Trats - type traits of flat combining, default is \p fcdeque::traits.
135 \p fcdeque::make_traits metafunction can be used to construct specialized \p %fcdeque::traits
137 template <typename T,
138 class Deque = std::deque<T>,
139 typename Traits = fcdeque::traits
142 #ifndef CDS_DOXYGEN_INVOKED
143 : public cds::algo::flat_combining::container
147 typedef T value_type; ///< Value type
148 typedef Deque deque_type; ///< Sequential deque class
149 typedef Traits traits; ///< Deque type traits
151 typedef typename traits::stat stat; ///< Internal statistics type
152 static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
156 /// Deque operation IDs
158 op_push_front = cds::algo::flat_combining::req_Operation, ///< Push front
159 op_push_front_move, ///< Push front (move semantics)
160 op_push_back, ///< Push back
161 op_push_back_move, ///< Push back (move semantics)
162 op_pop_front, ///< Pop front
163 op_pop_back, ///< Pop back
168 /// Flat combining publication list record
169 struct fc_record: public cds::algo::flat_combining::publication_record
172 value_type const * pValPush; ///< Value to push
173 value_type * pValPop; ///< Pop destination
175 bool bEmpty; ///< \p true if the deque is empty
179 /// Flat combining kernel
180 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
184 fc_kernel m_FlatCombining;
189 /// Initializes empty deque object
193 /// Initializes empty deque object and gives flat combining parameters
195 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
196 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
198 : m_FlatCombining( nCompactFactor, nCombinePassCount )
201 /// Inserts a new element at the beginning of the deque container
203 The function always returns \p true
206 value_type const& val ///< Value to be copied to inserted element
209 fc_record * pRec = m_FlatCombining.acquire_record();
210 pRec->pValPush = &val;
212 if ( c_bEliminationEnabled )
213 m_FlatCombining.batch_combine( op_push_front, pRec, *this );
215 m_FlatCombining.combine( op_push_front, pRec, *this );
217 assert( pRec->is_done() );
218 m_FlatCombining.release_record( pRec );
219 m_FlatCombining.internal_statistics().onPushFront();
223 /// Inserts a new element at the beginning of the deque container (move semantics)
225 The function always returns \p true
228 value_type&& val ///< Value to be moved to inserted element
231 fc_record * pRec = m_FlatCombining.acquire_record();
232 pRec->pValPush = &val;
234 if ( c_bEliminationEnabled )
235 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
237 m_FlatCombining.combine( op_push_front_move, pRec, *this );
239 assert( pRec->is_done() );
240 m_FlatCombining.release_record( pRec );
241 m_FlatCombining.internal_statistics().onPushFrontMove();
245 /// Inserts a new element at the end of the deque container
247 The function always returns \p true
250 value_type const& val ///< Value to be copied to inserted element
253 fc_record * pRec = m_FlatCombining.acquire_record();
254 pRec->pValPush = &val;
256 if ( c_bEliminationEnabled )
257 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
259 m_FlatCombining.combine( op_push_back, pRec, *this );
261 assert( pRec->is_done() );
262 m_FlatCombining.release_record( pRec );
263 m_FlatCombining.internal_statistics().onPushBack();
267 /// Inserts a new element at the end of the deque container (move semantics)
269 The function always returns \p true
272 value_type&& val ///< Value to be moved to inserted element
275 fc_record * pRec = m_FlatCombining.acquire_record();
276 pRec->pValPush = &val;
278 if ( c_bEliminationEnabled )
279 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
281 m_FlatCombining.combine( op_push_back_move, pRec, *this );
283 assert( pRec->is_done() );
284 m_FlatCombining.release_record( pRec );
285 m_FlatCombining.internal_statistics().onPushBackMove();
289 /// Removes the first element in the deque container
291 The function returns \p false if the deque is empty, \p true otherwise.
292 If the deque is empty \p val is not changed.
295 value_type& val ///< Target to be received the copy of removed element
298 fc_record * pRec = m_FlatCombining.acquire_record();
299 pRec->pValPop = &val;
301 if ( c_bEliminationEnabled )
302 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
304 m_FlatCombining.combine( op_pop_front, pRec, *this );
306 assert( pRec->is_done() );
307 m_FlatCombining.release_record( pRec );
308 m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
309 return !pRec->bEmpty;
312 /// Removes the last element in the deque container
314 The function returns \p false if the deque is empty, \p true otherwise.
315 If the deque is empty \p val is not changed.
318 value_type& val ///< Target to be received the copy of removed element
321 fc_record * pRec = m_FlatCombining.acquire_record();
322 pRec->pValPop = &val;
324 if ( c_bEliminationEnabled )
325 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
327 m_FlatCombining.combine( op_pop_back, pRec, *this );
329 assert( pRec->is_done() );
330 m_FlatCombining.release_record( pRec );
331 m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
332 return !pRec->bEmpty;
338 fc_record * pRec = m_FlatCombining.acquire_record();
340 if ( c_bEliminationEnabled )
341 m_FlatCombining.batch_combine( op_clear, pRec, *this );
343 m_FlatCombining.combine( op_clear, pRec, *this );
345 assert( pRec->is_done() );
346 m_FlatCombining.release_record( pRec );
349 /// Returns the number of elements in the deque.
351 Note that <tt>size() == 0</tt> is not mean that the deque is empty because
352 combining record can be in process.
353 To check emptiness use \ref empty function.
357 return m_Deque.size();
360 /// Checks if the deque is empty
362 If the combining is in process the function waits while combining done.
366 fc_record * pRec = m_FlatCombining.acquire_record();
368 if ( c_bEliminationEnabled )
369 m_FlatCombining.batch_combine( op_empty, pRec, *this );
371 m_FlatCombining.combine( op_empty, pRec, *this );
373 assert( pRec->is_done() );
374 m_FlatCombining.release_record( pRec );
378 /// Internal statistics
379 stat const& statistics() const
381 return m_FlatCombining.statistics();
384 public: // flat combining cooperation, not for direct use!
386 /// Flat combining supporting function. Do not call it directly!
388 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
389 object if the current thread becomes a combiner. Invocation of the function means that
390 the deque should perform an action recorded in \p pRec.
392 void fc_apply( fc_record * pRec )
396 // this function is called under FC mutex, so switch TSan off
397 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
399 switch ( pRec->op() ) {
401 assert( pRec->pValPush );
402 m_Deque.push_front( *(pRec->pValPush) );
404 case op_push_front_move:
405 assert( pRec->pValPush );
406 m_Deque.push_front( std::move( *(pRec->pValPush )) );
409 assert( pRec->pValPush );
410 m_Deque.push_back( *(pRec->pValPush) );
412 case op_push_back_move:
413 assert( pRec->pValPush );
414 m_Deque.push_back( std::move( *(pRec->pValPush )) );
417 assert( pRec->pValPop );
418 pRec->bEmpty = m_Deque.empty();
419 if ( !pRec->bEmpty ) {
420 *(pRec->pValPop) = m_Deque.front();
425 assert( pRec->pValPop );
426 pRec->bEmpty = m_Deque.empty();
427 if ( !pRec->bEmpty ) {
428 *(pRec->pValPop) = m_Deque.back();
433 while ( !m_Deque.empty() )
437 pRec->bEmpty = m_Deque.empty();
443 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
446 /// Batch-processing flat combining
447 void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
449 typedef typename fc_kernel::iterator fc_iterator;
451 // this function is called under FC mutex, so switch TSan off
452 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
454 for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
455 switch ( it->op() ) {
457 case op_push_front_move:
459 && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
461 collide( *it, *itPrev );
468 case op_push_back_move:
470 && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
472 collide( *it, *itPrev );
480 && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
481 || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
483 collide( *itPrev, *it );
491 && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
492 || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
494 collide( *itPrev, *it );
502 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
508 void collide( fc_record& recPush, fc_record& recPop )
510 *(recPop.pValPop) = *(recPush.pValPush);
511 recPop.bEmpty = false;
512 m_FlatCombining.operation_done( recPush );
513 m_FlatCombining.operation_done( recPop );
514 m_FlatCombining.internal_statistics().onCollide();
519 }} // namespace cds::container
521 #endif // #ifndef CDSLIB_CONTAINER_FCDEQUE_H