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_INTRUSIVE_TREIBER_STACK_H
32 #define CDSLIB_INTRUSIVE_TREIBER_STACK_H
34 #include <type_traits>
35 #include <mutex> // unique_lock
36 #include <cds/intrusive/details/single_link_struct.h>
37 #include <cds/algo/elimination.h>
38 #include <cds/opt/buffer.h>
39 #include <cds/sync/spinlock.h>
40 #include <cds/details/type_padding.h>
42 namespace cds { namespace intrusive {
44 /// TreiberStack related definitions
45 /** @ingroup cds_intrusive_helper
47 namespace treiber_stack {
52 - GC - garbage collector used
53 - Tag - a \ref cds_intrusive_hook_tag "tag"
55 template <class GC, typename Tag = opt::none >
56 using node = cds::intrusive::single_link::node< GC, Tag >;
61 - opt::gc - garbage collector used.
62 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
64 template < typename... Options >
65 using base_hook = cds::intrusive::single_link::base_hook< Options...>;
69 \p MemberOffset specifies offset in bytes of \ref node member into your structure.
70 Use \p offsetof macro to define \p MemberOffset
73 - opt::gc - garbage collector used.
74 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
76 template < size_t MemberOffset, typename... Options >
77 using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
81 \p NodeTraits defines type traits for node.
82 See \ref node_traits for \p NodeTraits interface description
85 - opt::gc - garbage collector used.
86 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
88 template <typename NodeTraits, typename... Options >
89 using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
92 /// Operation id for the \ref cds_elimination_description "elimination back-off"
94 op_push, ///< push op id
98 /// Operation descriptor for the \ref cds_elimination_description "elimination back-off"
100 struct operation: public cds::algo::elimination::operation_desc
102 operation_id idOp; ///< Op id
103 T * pVal; ///< for push: pointer to argument; for pop: accepts a return value
104 atomics::atomic<unsigned int> nStatus; ///< Internal elimination status
109 nStatus.store( 0 /*op_free*/, atomics::memory_order_release );
114 /// Stack internal statistics. May be useful for debugging or profiling
116 Template argument \p Counter defines type of counter.
117 Default is cds::atomicity::event_counter.
118 You may use stronger type of counter like as cds::atomicity::item_counter,
119 or even an integral type, for example, \p int
121 template <typename Counter = cds::atomicity::event_counter >
124 typedef Counter counter_type ; ///< Counter type
126 counter_type m_PushCount ; ///< Push call count
127 counter_type m_PopCount ; ///< Pop call count
128 counter_type m_PushRace ; ///< Count of push race conditions encountered
129 counter_type m_PopRace ; ///< Count of pop race conditions encountered
130 counter_type m_ActivePushCollision ; ///< Count of active push collision for elimination back-off
131 counter_type m_ActivePopCollision ; ///< Count of active pop collision for elimination back-off
132 counter_type m_PassivePushCollision ; ///< Count of passive push collision for elimination back-off
133 counter_type m_PassivePopCollision ; ///< Count of passive pop collision for elimination back-off
134 counter_type m_EliminationFailed ; ///< Count of unsuccessful elimination back-off
137 void onPush() { ++m_PushCount; }
138 void onPop() { ++m_PopCount; }
139 void onPushRace() { ++m_PushRace; }
140 void onPopRace() { ++m_PopRace; }
141 void onActiveCollision( operation_id opId )
143 if ( opId == treiber_stack::op_push )
144 ++m_ActivePushCollision;
146 ++m_ActivePopCollision;
148 void onPassiveCollision( operation_id opId )
150 if ( opId == treiber_stack::op_push )
151 ++m_PassivePushCollision;
153 ++m_PassivePopCollision;
155 void onEliminationFailed()
157 ++m_EliminationFailed;
162 /// Empty (no overhead) stack statistics. Support interface like treiber_stack::stat
170 void onActiveCollision( operation_id ) {}
171 void onPassiveCollision( operation_id ) {}
172 void onEliminationFailed() {}
176 /// TreiberStack default type traits
179 /// Back-off strategy
180 typedef cds::backoff::Default back_off;
182 /// Hook, possible types are \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook
183 typedef treiber_stack::base_hook<> hook;
185 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p TreiberStack::clear() function
186 typedef opt::v::empty_disposer disposer;
188 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
189 typedef cds::atomicity::empty_item_counter item_counter;
191 /// C++ memory ordering model
193 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
194 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
196 typedef opt::v::relaxed_ordering memory_model;
198 /// Internal statistics (by default, disabled)
200 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
201 user-provided class that supports \p %treiber_stack::stat interface.
203 typedef treiber_stack::empty_stat stat;
205 /// Link checking, see \p cds::opt::link_checker
206 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
208 /** @name Elimination back-off traits
209 The following traits is used only if elimination enabled
213 /// Enable elimination back-off; by default, it is disabled
214 static CDS_CONSTEXPR const bool enable_elimination = false;
216 /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
217 typedef cds::backoff::delay<> elimination_backoff;
219 /// Buffer type for elimination array
221 Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
222 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
223 The size should be selected empirically for your application and hardware, there are no common rules for that.
224 Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
226 typedef opt::v::initialized_static_buffer< int, 4 > buffer;
228 /// Random engine to generate a random position in elimination array
229 typedef opt::v::c_rand random_engine;
231 /// Lock type used in elimination, default is cds::sync::spin
232 typedef cds::sync::spin lock_type;
237 /// Metafunction converting option list to \p treiber_stack::traits
239 Supported \p Options are:
240 - \p opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
241 If the option is not specified, \p %treiber_stack::base_hook<> is used.
242 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
243 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
244 in \p TreiberStack::clear function.
245 - \p opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
246 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
247 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
248 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
249 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
250 - \p opt::stat - the type to gather internal statistics.
251 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
252 user-provided class that supports \p treiber_stack::stat interface.
253 - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
255 If elimination back-off is enabled, additional options can be specified:
256 - \p opt::buffer - a buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
257 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
258 The size should be selected empirically for your application and hardware, there are no common rules for that.
259 Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
260 - \p opt::random_engine - a random engine to generate a random position in elimination array.
261 Default is \p opt::v::c_rand.
262 - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
263 - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin
265 Example: declare \p %TreiberStack with elimination enabled and internal statistics
267 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
268 typename cds::intrusive::treiber_stack::make_traits<
269 cds::opt::enable_elimination< true >,
270 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
275 template <typename... Options>
277 # ifdef CDS_DOXYGEN_INVOKED
278 typedef implementation_defined type; ///< Metafunction result
280 typedef typename cds::opt::make_options<
281 typename cds::opt::find_type_traits< traits, Options... >::type
291 template <bool EnableElimination, typename T, typename Traits>
292 class elimination_backoff;
294 template <typename T, typename Traits>
295 class elimination_backoff<false, T, Traits>
297 typedef typename Traits::back_off back_off;
308 template <typename Stat>
309 bool backoff( treiber_stack::operation< T >&, Stat& )
317 elimination_backoff()
320 elimination_backoff( size_t )
323 typedef wrapper type;
330 template <typename T, typename Traits>
331 class elimination_backoff<true, T, Traits>
333 typedef typename Traits::back_off back_off;
335 /// Back-off for elimination (usually delay)
336 typedef typename Traits::elimination_backoff elimination_backoff_type;
337 /// Lock type used in elimination back-off
338 typedef typename Traits::lock_type elimination_lock_type;
339 /// Random engine used in elimination back-off
340 typedef typename Traits::random_engine elimination_random_engine;
342 /// Per-thread elimination record
343 typedef cds::algo::elimination::record elimination_rec;
345 /// Collision array record
346 struct collision_array_record {
347 elimination_rec * pRec;
348 elimination_lock_type lock;
351 /// Collision array used in elimination-backoff; each item is optimized for cache-line size
352 typedef typename Traits::buffer::template rebind<
353 typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
354 >::other collision_array;
356 /// Operation descriptor used in elimination back-off
357 typedef treiber_stack::operation< T > operation_desc;
359 /// Elimination back-off data
360 struct elimination_data {
361 mutable elimination_random_engine randEngine; ///< random engine
362 collision_array collisions; ///< collision array
366 //TODO: check Traits::buffer must be static!
368 elimination_data( size_t nCollisionCapacity )
369 : collisions( nCollisionCapacity )
373 elimination_data m_Elimination;
375 enum operation_status {
381 typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
383 template <bool Exp2 = collision_array::c_bExp2>
384 typename std::enable_if< Exp2, size_t >::type slot_index() const
386 return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
389 template <bool Exp2 = collision_array::c_bExp2>
390 typename std::enable_if< !Exp2, size_t >::type slot_index() const
392 return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
396 elimination_backoff()
398 m_Elimination.collisions.zeroize();
401 elimination_backoff( size_t nCollisionCapacity )
402 : m_Elimination( nCollisionCapacity )
404 m_Elimination.collisions.zeroize();
407 typedef elimination_backoff& type;
417 template <typename Stat>
418 bool backoff( operation_desc& op, Stat& stat )
420 elimination_backoff_type bkoff;
421 op.nStatus.store( op_busy, atomics::memory_order_release );
423 elimination_rec * myRec = cds::algo::elimination::init_record( op );
425 collision_array_record& slot = m_Elimination.collisions[ slot_index() ];
428 elimination_rec * himRec = slot.pRec;
430 operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
432 if ( himOp->idOp != op.idOp ) {
433 if ( op.idOp == treiber_stack::op_push )
434 himOp->pVal = op.pVal;
436 op.pVal = himOp->pVal;
438 himOp->nStatus.store( op_collided, atomics::memory_order_release );
441 cds::algo::elimination::clear_record();
442 stat.onActiveCollision( op.idOp );
445 himOp->nStatus.store( op_free, atomics::memory_order_release );
451 // Wait for colliding operation
452 bkoff( [&op]() CDS_NOEXCEPT -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
454 slot_scoped_lock l( slot.lock );
455 if ( slot.pRec == myRec )
459 bool bCollided = op.nStatus.load( atomics::memory_order_acquire ) == op_collided;
462 stat.onEliminationFailed();
464 stat.onPassiveCollision( op.idOp );
466 cds::algo::elimination::clear_record();
471 } // namespace details
473 } // namespace treiber_stack
475 /// Treiber intrusive stack
476 /** @ingroup cds_intrusive_stack
477 Intrusive implementation of well-known Treiber's stack algorithm:
478 - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
480 \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
481 The idea of elimination algorithm is taken from:
482 - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
484 The elimination algorithm uses a single elimination array as a back-off schema
485 on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
486 on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
488 @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
489 The main difficulty is the managing life-time of elimination record.
490 Our implementation uses simplified lock-based (spin-based) approach which allows
491 the elimination record allocation on thread's stack.
492 This approach demonstrates sufficient performance under high load.
495 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
496 Garbage collecting schema must be the same as \p treiber_stack::node GC.
497 - \p T - a type the stack contains. A value of type \p T must be derived
498 from \p treiber_stack::node for \p treiber_stack::base_hook,
499 or it should have a member of type \p %treiber_stack::node for \p treiber_stack::member_hook,
500 or it should be convertible to \p %treiber_stack::node for \p treiber_stack::traits_hook.
501 - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
502 metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
504 struct myTraits: public cds::intrusive::treiber_stack::traits {
505 typedef cds::intrusive::treiber_stack::stat<> stat;
507 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
509 // Equivalent make_traits example:
510 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
511 typename cds::intrusive::treiber_stack::make_traits<
512 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
517 @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
519 @anchor cds_intrusive_TreiberStack_examples
522 Example of how to use \p treiber_stack::base_hook.
523 Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class
525 #include <cds/intrusive/treiber_stack.h>
526 #include <cds/gc/hp.h>
528 namespace ci = cds::intrusive;
529 typedef cds::gc::HP gc;
531 struct myData: public ci::treiber_stack::node< gc >
537 typedef ci::TreiberStack< gc,
539 typename cds::intrusive::treiber_stack::make_traits<
540 ci::opt::hook< ci::treiber_stack::base_hook< gc > >
544 // Stack with elimination back-off enabled
545 typedef ci::TreiberStack< gc,
547 typename ci::treiber_stack::make_traits<
548 ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
549 cds::opt::enable_elimination< true >
551 > elimination_stack_t;
554 Example of how to use \p treiber_stack::base_hook with different tags.
556 #include <cds/intrusive/treiber_stack.h>
557 #include <cds/gc/hp.h>
559 namespace ci = cds::intrusive;
560 typedef cds::gc::HP gc;
562 // It is not necessary to declare complete type for tags
567 : public ci::treiber_stack::node< gc, tag1 >
568 , public ci::treiber_stack::node< gc, tag2 >
573 typedef ci::TreiberStack< gc,
575 typename ci::treiber_stack::make_traits<
576 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
580 typedef ci::TreiberStack< gc,
582 typename ci::treiber_stack::make_traits<
583 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 > >
587 // You may add myData objects into stack1_t and stack2_t independently
595 s2.push( i1 ) ; // i1 is now contained in s1 and s2.
599 p = s1.pop() ; // pop i1 from s1
600 p = s1.pop() ; // p == nullptr, s1 is empty
601 p = s2.pop() ; // pop i1 from s2
602 p = s2.pop() ; // pop i2 from s2
603 p = s2.pop() ; // p == nullptr, s2 is empty
607 Example of how to use \p treiber_stack::member_hook.
608 Your class should have a member of type \p treiber_stack::node
610 #include <stddef.h> // offsetof macro
611 #include <cds/intrusive/treiber_stack.h>
612 #include <cds/gc/hp.h>
614 namespace ci = cds::intrusive;
615 typedef cds::gc::HP gc;
620 ci::treiber_stack::node< gc > member_hook_;
624 typedef ci::TreiberStack< gc,
626 typename ci::treiber_stack::make_traits<
627 ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >>
635 typename Traits = treiber_stack::traits
640 /// Rebind template arguments
641 template <typename GC2, typename T2, typename Traits2>
643 typedef TreiberStack< GC2, T2, Traits2 > other ; ///< Rebinding result
647 typedef GC gc; ///< Garbage collector
648 typedef T value_type; ///< type of value stored in the stack
649 typedef Traits traits; ///< Stack traits
651 typedef typename traits::hook hook; ///< hook type
652 typedef typename hook::node_type node_type; ///< node type
653 typedef typename traits::disposer disposer; ///< disposer used
654 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
655 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker ; ///< link checker
656 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
657 typedef typename traits::item_counter item_counter; ///< Item counter class
658 typedef typename traits::stat stat; ///< Internal statistics
659 typedef typename traits::back_off back_off; ///< back-off strategy
661 /// How many Hazard pointers is required for Treiber's stack implementation
662 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 1;
664 public: // related to elimination back-off
666 /// Elimination back-off is enabled or not
667 static CDS_CONSTEXPR const bool enable_elimination = traits::enable_elimination;
668 /// back-off strategy used to wait for elimination
669 typedef typename traits::elimination_backoff elimination_backoff_type;
670 /// Lock type used in elimination back-off
671 typedef typename traits::lock_type elimination_lock_type;
672 /// Random engine used in elimination back-off
673 typedef typename traits::random_engine elimination_random_engine;
676 typename node_type::atomic_node_ptr m_Top; ///< Top of the stack
677 item_counter m_ItemCounter; ///< Item counter
678 stat m_stat; ///< Internal statistics
681 typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
682 elimination_backoff m_Backoff;
684 typedef treiber_stack::operation< value_type > operation_desc;
686 // GC and node_type::gc must be the same
687 static_assert( std::is_same<gc, typename node_type::gc>::value, "GC and node_type::gc must be the same");
689 static_assert( !enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value,
690 "Random engine result type must be unsigned int");
695 void clear_links( node_type * pNode ) CDS_NOEXCEPT
697 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
700 template <bool EnableElimination>
701 struct elimination_backoff_impl;
705 /// Constructs empty stack
710 /// Constructs empty stack and initializes elimination back-off data
712 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
713 \p Traits contains <tt>typedef cds::opt::v::initialized_dynamic_buffer buffer</tt>.
714 \p nCollisionCapacity parameter specifies the capacity of collision array.
716 TreiberStack( size_t nCollisionCapacity )
718 , m_Backoff( nCollisionCapacity )
721 /// \p %TreiberStack is not copy-constructible
722 TreiberStack( TreiberStack const& ) = delete;
724 /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
730 /// Push the item \p val on the stack
732 No copying is made since it is intrusive stack.
734 bool push( value_type& val )
736 node_type * pNew = node_traits::to_node_ptr( val );
737 link_checker::is_empty( pNew );
739 typename elimination_backoff::type bkoff = m_Backoff.init();
742 if ( enable_elimination ) {
743 op.idOp = treiber_stack::op_push;
747 node_type * t = m_Top.load(memory_model::memory_order_relaxed);
749 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
750 if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
757 if ( bkoff.backoff( op, m_stat ))
762 /// Pop an item from the stack
764 If stack is empty, returns \p nullptr.
765 The disposer is <b>not</b> called for popped item.
766 See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
770 typename elimination_backoff::type bkoff = m_Backoff.init();
771 typename gc::Guard guard;
774 if ( enable_elimination ) {
775 op.idOp = treiber_stack::op_pop;
779 node_type * t = guard.protect( m_Top,
780 []( node_type * p ) -> value_type * {
781 return node_traits::to_value_ptr( p );
784 return nullptr; // stack is empty
786 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
787 if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
791 return node_traits::to_value_ptr( *t );
795 if ( bkoff.backoff( op, m_stat )) {
796 // may return nullptr if stack is empty
802 /// Check if stack is empty
805 return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
809 /** @anchor cds_intrusive_TreiberStack_clear
810 For each removed item the disposer is called.
812 @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
813 if some other thread pushes an item into the stack during \p clear works
820 pTop = m_Top.load( memory_model::memory_order_relaxed );
821 if ( pTop == nullptr )
823 if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
824 m_ItemCounter.reset();
831 node_type * p = pTop;
832 pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
834 gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
838 /// Returns stack's item count
840 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
841 this function always returns 0.
843 @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack
844 is empty. To check emptyness use \ref empty() method.
848 return m_ItemCounter.value();
851 /// Returns reference to internal statistics
852 stat const& statistics() const
858 }} // namespace cds::intrusive
860 #endif // #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H