3 #ifndef __CDS_INTRUSIVE_MICHAEL_DEQUE_H
4 #define __CDS_INTRUSIVE_MICHAEL_DEQUE_H
7 #include <cds/intrusive/michael_list_impl.h>
8 #include <cds/intrusive/michael_set.h>
9 #include <cds/intrusive/deque_stat.h>
11 #include <cds/details/aligned_type.h>
12 #include <cds/gc/default_gc.h>
14 namespace cds { namespace intrusive {
17 struct michael_deque_tag;
20 /// MichaelDeque related definitions
21 /** @ingroup cds_intrusive_helper
23 namespace michael_deque
25 /// Anchor contains left/right sibling items
27 The anchor object is maintained by one CAS instruction.
31 unsigned int idxLeft ; ///< Left sibling index; the most-significant bit contains left-stable flag
32 unsigned int idxRight ; ///< Right sibling index; the most-significant bit contains right-stable flag
34 # ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
36 anchor() CDS_NOEXCEPT_DEFAULTED = default;
37 anchor( anchor const& ) CDS_NOEXCEPT_DEFAULTED = default;
38 ~anchor() CDS_NOEXCEPT_DEFAULTED = default;
39 anchor& operator=(anchor const&) CDS_NOEXCEPT_DEFAULTED = default;
40 # if defined(CDS_MOVE_SEMANTICS_SUPPORT) && !defined(CDS_DISABLE_DEFAULT_MOVE_CTOR)
41 anchor( anchor&&) CDS_NOEXCEPT_DEFAULTED = default;
42 anchor& operator=(anchor&&) CDS_NOEXCEPT_DEFAULTED = default;
46 /// Default ctor does not initialize left/right indices
54 anchor( anchor const& a) CDS_NOEXCEPT
55 : idxLeft( a.idxLeft )
56 , idxRight( a.idxRight )
62 /// Constructor sets \p left / \p right indices
63 anchor( unsigned int left, unsigned int right ) CDS_NOEXCEPT
70 /// Anchor equal operator
71 bool operator ==( anchor const& a) const CDS_NOEXCEPT
73 return idxLeft == a.idxLeft && idxRight == a.idxRight;
76 /// Anchor non-equal operator
77 bool operator !=( anchor const& a) const CDS_NOEXCEPT
79 return !( *this == a );
84 static void static_check()
86 static_assert( sizeof(unsigned int) * 2 <= 8, "The index type must be no more than 32bit long" );
87 static_assert( sizeof(anchor) <= 8, "The anchor type must be no more than 64bit long" );
92 /// Michael's deque node
95 - GC - garbage collector
96 - Tag - a tag used to distinguish between different implementation
98 template <class GC, typename Tag = opt::none>
99 struct node: public michael_list::node< GC, michael_deque_tag >
101 typedef GC gc ; ///< Garbage collector
102 typedef Tag tag ; ///< tag
105 typedef michael_list::node< gc, michael_deque_tag > mapper_node_type;
108 typedef typename gc::template atomic_type< anchor > atomic_anchor ; ///< atomic reference to left/right node
110 CDS_DATA_ALIGNMENT(8) atomic_anchor m_Links ; ///< Left/right sibling links
111 unsigned int m_nIndex; ///< Item index
116 m_Links.store( anchor(0,0), CDS_ATOMIC::memory_order_release );
119 explicit node( anchor const& a )
123 m_Links.store( a, CDS_ATOMIC::memory_order_release );
129 struct default_hook {
130 typedef cds::gc::default_gc gc;
131 typedef opt::none tag;
132 typedef unsigned int index_type;
137 template < typename HookType, CDS_DECL_OPTIONS3>
140 typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type options;
141 typedef typename options::gc gc;
142 typedef typename options::tag tag;
143 typedef typename options::index_type index_type;
145 typedef node<gc, tag> node_type;
146 typedef HookType hook_type;
154 - opt::gc - garbage collector used.
156 - opt::index_type - integral index type
158 template < CDS_DECL_OPTIONS3 >
159 struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 >
164 \p MemberOffset defines offset in bytes of \ref node member into your structure.
165 Use \p offsetof macro to define \p MemberOffset
168 - opt::gc - garbage collector used.
170 - opt::index_type - integral index type
172 template < size_t MemberOffset, CDS_DECL_OPTIONS3 >
173 struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 >
176 static const size_t c_nMemberOffset = MemberOffset;
182 \p NodeTraits defines type traits for node.
183 See \ref node_traits for \p NodeTraits interface description
186 - opt::gc - garbage collector used.
188 - opt::index_type - integral index type
190 template <typename NodeTraits, CDS_DECL_OPTIONS3 >
191 struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 >
194 typedef NodeTraits node_traits;
198 /// Deque internal statistics. May be used for debugging or profiling
200 Template argument \p Counter defines type of counter.
201 Default is cds::atomics::event_counter.
202 You may use other counter type like as cds::atomics::item_counter,
203 or even integral type, for example, \p int.
205 The class extends intrusive::deque_stat interface for MichaelDeque.
207 template <typename Counter = cds::atomicity::event_counter >
208 struct stat: public cds::intrusive::deque_stat<Counter>
211 typedef cds::intrusive::deque_stat<Counter> base_class;
212 typedef typename base_class::counter_type counter_type;
215 counter_type m_StabilizeFrontCount ; ///< stabilize left event count
216 counter_type m_StabilizeBackCount ; ///< stabilize right event count
218 /// Register "stabilize left" event
219 void onStabilizeFront() { ++m_StabilizeFrontCount; }
221 /// Register "stabilize right" event
222 void onStabilizeBack() { ++m_StabilizeBackCount; }
225 /// Dummy deque statistics - no counting is performed. Support interface like \ref michael_deque::stat
226 struct dummy_stat: public cds::intrusive::deque_dummy_stat
229 void onStabilizeFront() {}
230 void onStabilizeBack() {}
235 template < typename NodeType, opt::link_check_type LinkType>
238 typedef NodeType node_type;
240 static void is_empty( const node_type * pNode )
243 anchor a = pNode->m_Links.load(CDS_ATOMIC::memory_order_relaxed);
244 assert( a.idxLeft == 0 && a.idxRight == 0 );
249 template < typename NodeType>
250 struct link_checker<NodeType, opt::never_check_link>
252 typedef NodeType node_type;
254 static void is_empty( const node_type * /*pNode*/ )
258 } // namespace michael_deque
260 /// Michael's intrusive deque
261 /** @ingroup cds_intrusive_deque
262 Implementation of Michael's deque algorithm.
265 [2003] Maged Michael "CAS-based Lock-free Algorithm for Shared Deque"
267 <b>Short description</b> (from Michael's paper)
269 The deque is represented as a doubly-linked list. Each node in the list contains two link pointers,
270 \p pRight and \p pLeft, and a data field. A shared variable, \p Anchor, holds the two anchor
271 pointers to the leftmost and rightmost nodes in the list, if any, and a three-value
272 status tag. Anchor must fit in a memory block that can be read and manipulated
273 using CAS or LL/SC, atomically. Initially both anchor pointers have null values
274 and the status tag holds the value stable, indicating an empty deque.
276 The status tag serves to indicate if the deque is in an unstable state. When
277 a process finds the deque in an unstable state, it must first attempt to take it
278 to a stable state before attempting its own operation.
280 The algorithm can use single-word CAS or LL/SC.
281 In \p libcds implementation of the algorithm the node contains two
282 31bit link indices instead of pointers + one bit for status tag;
283 this trick allows use 64bit CAS to manipulate \p Anchor. Internal mapper
284 (based on MichaelHashSet intrusive container)
285 reflects link indices to item pointers. The maximum number of item in
286 the deque is limited by 2**31 that is practically unbounded.
289 - \p GC - garbage collector type: gc::HP or gc::PTB. Note that gc::HRC is not supported
290 - \p T - type to be stored in the queue, should be convertible to michael_deque::node
291 - \p Options - options
293 Type of node: \ref michael_deque::node
296 - opt::hook - hook used. Possible values are: michael_deque::base_hook, michael_deque::member_hook, michael_deque::traits_hook.
297 If the option is not specified, <tt>michael_deque::base_hook<></tt> is used.
298 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
299 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used
300 in \ref pop_front and \ref pop_back functions.
301 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
302 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter (no item counting feature)
303 - opt::stat - the type to gather internal statistics.
304 Possible option value are: \ref michael_deque::stat, \ref michael_deque::dummy_stat, user-provided class that supports michael_deque::stat interface.
305 Default is \ref michael_deque::dummy_stat.
306 - opt::alignment - the alignment for internal deque data. Default is opt::cache_line_alignment
307 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
308 or opt::v::sequential_consistent (sequentially consisnent memory model).
309 - opt::allocator - allocator using for internal memory mapper based on MichaelHashSet. Default is CDS_DEFAULT_ALLOCATOR.
311 template <typename GC, typename T, CDS_DECL_OPTIONS10>
315 struct default_options
317 typedef cds::backoff::empty back_off;
318 typedef michael_deque::base_hook<> hook;
319 typedef opt::v::empty_disposer disposer;
320 typedef atomicity::empty_item_counter item_counter;
321 typedef michael_deque::dummy_stat stat;
322 typedef opt::v::relaxed_ordering memory_model;
323 static const opt::link_check_type link_checker = opt::debug_check_link;
324 enum { alignment = opt::cache_line_alignment };
325 typedef CDS_DEFAULT_ALLOCATOR allocator;
331 typedef typename opt::make_options<
332 typename cds::opt::find_type_traits< default_options, CDS_OPTIONS10 >::type
339 typedef typename std::conditional<
340 std::is_same<typename options::stat, cds::intrusive::deque_stat<> >::value
341 ,michael_deque::stat<>
342 ,typename std::conditional<
343 std::is_same<typename options::stat, cds::intrusive::deque_dummy_stat>::value
344 ,michael_deque::dummy_stat
345 ,typename options::stat
352 typedef T value_type ; ///< type of value stored in the deque
353 typedef typename options::hook hook ; ///< hook type
354 typedef typename hook::node_type node_type ; ///< node type
355 typedef typename options::disposer disposer ; ///< disposer used
356 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
357 typedef michael_deque::link_checker< node_type, options::link_checker > link_checker ; ///< link checker
359 typedef GC gc ; ///< Garbage collector
360 typedef typename options::back_off back_off ; ///< back-off strategy
361 typedef typename options::item_counter item_counter ; ///< Item counting policy used
362 typedef stat_type_ stat ; ///< Internal statistics policy used
363 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
364 typedef typename options::allocator allocator_type ; ///< Allocator using for internal memory mapping
366 typedef typename node_type::atomic_anchor atomic_anchor ; ///< Atomic anchor
372 struct node_less_comparator
374 bool operator ()( value_type const & n1, value_type const& n2) const
376 return node_traits::to_node_ptr(n1)->m_nIndex < node_traits::to_node_ptr(n2)->m_nIndex;
378 bool operator ()( unsigned int i, value_type const& n2) const
380 return i < node_traits::to_node_ptr(n2)->m_nIndex;
382 bool operator ()( value_type const & n1, unsigned int i) const
384 return node_traits::to_node_ptr(n1)->m_nIndex < i;
388 struct internal_disposer
390 void operator()( value_type * p )
392 assert( p != nullptr );
394 MichaelDeque::clear_links( node_traits::to_node_ptr(p) );
399 struct mapper_node_traits
401 typedef typename node_type::mapper_node_type mapper_node_type;
403 static mapper_node_type * to_node_ptr( value_type& v )
405 return static_cast<mapper_node_type *>( node_traits::to_node_ptr(v) );
408 static mapper_node_type * to_node_ptr( value_type * v )
410 return static_cast<mapper_node_type *>( node_traits::to_node_ptr(v) );
413 static mapper_node_type const * to_node_ptr( value_type const& v )
415 return static_cast<mapper_node_type const *>( node_traits::to_node_ptr(v) );
418 static mapper_node_type const * to_node_ptr( value_type const * v )
420 return static_cast<mapper_node_type const *>( node_traits::to_node_ptr(v) );
423 static value_type * to_value_ptr( mapper_node_type& n )
425 return node_traits::to_value_ptr( static_cast<node_type&>(n));
428 static value_type * to_value_ptr( mapper_node_type * n )
430 return node_traits::to_value_ptr( static_cast<node_type *>(n));
433 static const value_type * to_value_ptr( mapper_node_type const& n )
435 return node_traits::to_value_ptr( static_cast<node_type const&>(n));
438 static const value_type * to_value_ptr( mapper_node_type const * n )
440 return node_traits::to_value_ptr( static_cast<node_type const *>(n));
444 typedef MichaelList< gc, value_type,
445 typename michael_list::make_traits<
446 opt::hook< michael_list::traits_hook<
449 ,cds::opt::tag<michael_deque_tag> >
451 ,opt::less< node_less_comparator >
452 ,opt::back_off< back_off >
453 ,opt::disposer< internal_disposer >
454 ,opt::memory_model< memory_model >
456 > mapper_ordered_list;
459 size_t operator()( value_type const& v ) const
461 return cds::opt::v::hash<unsigned int>()( node_traits::to_node_ptr(v)->m_nIndex );
463 size_t operator()( unsigned int i ) const
465 return cds::opt::v::hash<unsigned int>()(i);
469 typedef MichaelHashSet< gc, mapper_ordered_list,
470 typename michael_set::make_traits<
471 opt::hash< mapper_hash >
472 ,opt::allocator< allocator_type >
476 # if !(defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER < 1700))
484 void operator()( value_type& v, unsigned int nIdx )
486 pNode = node_traits::to_node_ptr(v);
487 assert( pNode->m_nIndex == nIdx );
493 CDS_ATOMIC::atomic<unsigned int> m_nLastIndex;
497 index_mapper( size_t nEstimatedItemCount, size_t nLoadFactor )
498 : m_set( nEstimatedItemCount, nLoadFactor )
502 unsigned int map( value_type& v )
505 node_type * pNode = node_traits::to_node_ptr( v );
506 pNode->m_nIndex = m_nLastIndex.fetch_add( 1, memory_model::memory_order_relaxed );
507 if ( pNode->m_nIndex && m_set.insert( v ))
508 return pNode->m_nIndex;
512 bool unmap( unsigned int nIdx )
514 return m_set.erase( nIdx );
517 node_type * at( unsigned int nIdx )
519 # if defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC ||CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER < 1700)
520 // MS VC++2010 bug: error C2955: 'cds::intrusive::node_traits' : use of class template requires template argument list
521 // see declaration of 'cds::intrusive::node_traits'
522 node_type * pNode = nullptr;
523 if ( m_set.find( nIdx,
524 [&pNode](value_type& v, unsigned int nIdx) {
525 pNode = node_traits::to_node_ptr(v);
526 assert( pNode->m_nIndex == nIdx );
532 if ( m_set.find( nIdx, cds::ref(f) ))
541 /// Rebind template arguments
542 template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS10>
544 typedef MichaelDeque< GC2, T2, CDS_OTHER_OPTIONS10> other ; ///< Rebinding result
548 typename cds::opt::details::alignment_setter< atomic_anchor, options::alignment >::type m_Anchor ; ///< Left/right heads
549 typename cds::opt::details::alignment_setter< index_mapper, options::alignment >::type m_Mapper ; ///< Memory mapper
551 item_counter m_ItemCounter ; ///< item counter
552 stat m_Stat ; ///< Internal statistics
555 static const unsigned int c_nIndexMask = ((unsigned int)(0 - 1)) >> 1;
556 static const unsigned int c_nFlagMask = ((unsigned int)(1)) << (sizeof(unsigned int) * 8 - 1);
557 static const unsigned int c_nEmptyIndex = 0;
562 typedef michael_deque::anchor CDS_TYPE_ALIGNMENT(8) anchor_type;
563 typedef intrusive::node_to_value<MichaelDeque> node_to_value;
565 static void clear_links( node_type * pNode )
567 pNode->m_Links.store( anchor_type(), memory_model::memory_order_release );
576 static anchor_status status( anchor_type const& a )
578 if ( a.idxLeft & c_nFlagMask )
580 if ( a.idxRight & c_nFlagMask )
585 static unsigned int index( unsigned int i )
587 return i & c_nIndexMask;
590 void stabilize( anchor_type& a )
592 switch ( status(a)) {
604 void stabilize_front( anchor_type& a )
606 m_Stat.onStabilizeFront();
608 typename gc::template GuardArray<3> guards;
611 unsigned int const idxLeft = index( a.idxLeft );
612 unsigned int const idxRight = index( a.idxRight );
614 guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
615 guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
616 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
619 unsigned int idxPrev = index( pLeft->m_Links.load(memory_model::memory_order_relaxed ).idxRight );
621 guards.assign( 2, node_traits::to_value_ptr( pPrev = m_Mapper.at( idxPrev )) );
622 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
625 anchor_type prevLinks( pPrev->m_Links.load( memory_model::memory_order_acquire ));
626 if ( index( prevLinks.idxLeft ) != idxLeft ) {
627 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
630 if ( !pPrev->m_Links.compare_exchange_strong( prevLinks, anchor_type( idxLeft, prevLinks.idxRight ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
634 // clear RPush/LPush flags
635 m_Anchor.compare_exchange_weak( a, anchor_type(idxLeft, idxRight), memory_model::memory_order_release, memory_model::memory_order_relaxed );
638 void stabilize_back( anchor_type& a )
640 m_Stat.onStabilizeBack();
642 typename gc::template GuardArray<3> guards;
645 unsigned int const idxLeft = index( a.idxLeft );
646 unsigned int const idxRight = index( a.idxRight );
648 guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
649 guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
650 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
653 unsigned int idxPrev = index( pRight->m_Links.load(memory_model::memory_order_relaxed ).idxLeft );
655 guards.assign( 2, node_traits::to_value_ptr( pPrev = m_Mapper.at( idxPrev )) );
656 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
659 anchor_type prevLinks( pPrev->m_Links.load( memory_model::memory_order_acquire ));
660 if ( index( prevLinks.idxRight ) != idxRight ) {
661 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
664 if ( !pPrev->m_Links.compare_exchange_strong( prevLinks, anchor_type( prevLinks.idxLeft, idxRight ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
668 // clear RPush/LPush flags
669 m_Anchor.compare_exchange_weak( a, anchor_type(idxLeft, idxRight), memory_model::memory_order_release, memory_model::memory_order_relaxed );
677 value_type * pPopped;
678 unsigned int nIdxPopped;
679 typename gc::template GuardArray<2> guards;
682 void dispose_result( pop_result& res )
684 m_Mapper.unmap( res.nIdxPopped );
687 bool do_pop_back( pop_result& res )
693 a = m_Anchor.load( memory_model::memory_order_acquire );
695 if ( a.idxRight == c_nEmptyIndex ) {
700 if ( a.idxLeft == a.idxRight ) {
701 if ( m_Anchor.compare_exchange_weak( a, anchor_type( c_nEmptyIndex, c_nEmptyIndex ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
705 else if ( status( a ) == Stable ) {
706 unsigned int idxLeft = index( a.idxLeft );
707 unsigned int idxRight = index( a.idxRight );
709 res.guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
711 res.guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
713 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a ) {
714 m_Stat.onPopBackContention();
718 unsigned int nPrev = pRight->m_Links.load( memory_model::memory_order_acquire ).idxLeft;
719 if ( m_Anchor.compare_exchange_weak( a, anchor_type( a.idxLeft, nPrev ), memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
722 m_Stat.onPopBackContention();
728 res.nIdxPopped = a.idxRight;
729 res.pPopped = node_traits::to_value_ptr( m_Mapper.at( a.idxRight ));
737 bool do_pop_front( pop_result& res )
743 a = m_Anchor.load( memory_model::memory_order_acquire );
745 if ( a.idxLeft == c_nEmptyIndex ) {
750 if ( a.idxLeft == a.idxRight ) {
751 if ( m_Anchor.compare_exchange_weak( a, anchor_type( c_nEmptyIndex, c_nEmptyIndex ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
755 else if ( status( a ) == Stable ) {
756 unsigned int idxLeft = index( a.idxLeft );
757 unsigned int idxRight = index( a.idxRight );
759 res.guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
761 res.guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
763 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a ) {
764 m_Stat.onPopFrontContention();
768 unsigned int nPrev = pLeft->m_Links.load( memory_model::memory_order_acquire ).idxRight;
769 if ( m_Anchor.compare_exchange_weak( a, anchor_type( nPrev, a.idxRight ), memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
772 m_Stat.onPopFrontContention();
778 res.nIdxPopped = a.idxLeft;
779 res.pPopped = node_traits::to_value_ptr( m_Mapper.at( a.idxLeft ));
790 /// Default constructor
792 Initializes the deque object with up to <tt>2**16 - 2</tt> items
798 m_Anchor.store( anchor_type( c_nEmptyIndex, c_nEmptyIndex ), CDS_ATOMIC::memory_order_release );
800 // GC and node_type::gc must be the same
801 static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
803 // cds::gc::HRC is not allowed
804 static_assert(( !std::is_same<gc, cds::gc::HRC>::value ), "cds::gc::HRC is not allowed here");
809 Initializes the deque object with estimated item count \p nMaxItemCount.
810 \p nLoadFactor is a parameter of internal memory mapper based on MichaelHashSet;
811 see MichaelHashSet ctor for details
813 MichaelDeque( unsigned int nMaxItemCount, unsigned int nLoadFactor = 4 )
815 ,m_Mapper( nMaxItemCount, nLoadFactor )
817 m_Anchor.store( anchor_type( c_nEmptyIndex, c_nEmptyIndex ), CDS_ATOMIC::memory_order_release );
819 // GC and node_type::gc must be the same
820 static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
822 // cds::gc::HRC is not allowed
823 static_assert(( !std::is_same<gc, cds::gc::HRC>::value ), "cds::gc::HRC is not allowed here");
826 /// Destructor clears the deque
833 /// Push back (right) side
835 Push new item \p val to right side of the deque.
837 bool push_back( value_type& val )
841 node_type * pNode = node_traits::to_node_ptr( val );
842 link_checker::is_empty( pNode );
844 unsigned int nIdx = m_Mapper.map( val );
845 if ( nIdx == c_nEmptyIndex )
849 anchor_type a = m_Anchor.load( memory_model::memory_order_acquire );
850 if ( a.idxRight == c_nEmptyIndex ) {
851 if ( m_Anchor.compare_exchange_weak( a, anchor_type( nIdx, nIdx ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
854 m_Stat.onPushBackContention();
856 else if ( status(a) == Stable ) {
857 pNode->m_Links.store( anchor_type( a.idxRight, c_nEmptyIndex ), memory_model::memory_order_release );
858 anchor_type aNew( a.idxLeft, nIdx | c_nFlagMask );
859 if ( m_Anchor.compare_exchange_weak( a, aNew, memory_model::memory_order_release, memory_model::memory_order_relaxed) ) {
860 stabilize_back( aNew );
864 m_Stat.onPushBackContention();
875 /// Push front (left) side
877 Push new item \p val to left side of the deque.
879 bool push_front( value_type& val )
882 node_type * pNode = node_traits::to_node_ptr( val );
883 link_checker::is_empty( pNode );
885 unsigned int nIdx = m_Mapper.map( val );
886 if ( nIdx == c_nEmptyIndex )
890 anchor_type a = m_Anchor.load( memory_model::memory_order_acquire );
891 if ( a.idxLeft == c_nEmptyIndex ) {
892 if ( m_Anchor.compare_exchange_weak( a, anchor_type( nIdx, nIdx ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
895 m_Stat.onPushFrontContention();
897 else if ( status(a) == Stable ) {
898 pNode->m_Links.store( anchor_type( c_nEmptyIndex, a.idxLeft ), memory_model::memory_order_release );
899 anchor_type aNew( nIdx | c_nFlagMask, a.idxRight );
900 if ( m_Anchor.compare_exchange_weak( a, aNew, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
901 stabilize_front( aNew );
905 m_Stat.onPushFrontContention();
912 m_Stat.onPushFront();
918 Pops rightmost item from the deque. If the deque is empty then returns \p NULL.
920 For popped object the disposer specified in \p Options template parameters is called.
922 value_type * pop_back()
925 if ( do_pop_back( res )) {
926 dispose_result( res );
935 Pops leftmost item from the deque. If the deque is empty then returns \p NULL.
937 For popped object the disposer specified in \p Options template parameters is called.
939 value_type * pop_front()
942 if ( do_pop_front( res )) {
943 dispose_result( res );
950 /// Returns deque's item count
952 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
953 this function always returns 0.
955 <b>Warning</b>: even if you use real item counter and it returns 0, this fact does not mean that the deque
956 is empty. To check deque emptyness use \ref empty() method.
960 return m_ItemCounter.value();
963 /// Checks if the dequeue is empty
966 anchor_type a = m_Anchor.load( memory_model::memory_order_relaxed );
967 return a.idxLeft == c_nEmptyIndex && a.idxRight == c_nEmptyIndex;
972 The function repeatedly calls \ref pop_back until it returns \p NULL.
973 The disposer defined in template \p Options is called for each item
974 that can be safely disposed.
978 while ( pop_back() != nullptr );
981 /// Returns reference to internal statistics
982 const stat& statistics() const
989 }} // namespace cds::intrusive
992 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_DEQUE_H