--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
+#define CDSLIB_INTRUSIVE_TREIBER_STACK_H
+
+#include <type_traits>
+#include <mutex> // unique_lock
+#include <cds/intrusive/details/single_link_struct.h>
+#include <cds/algo/elimination.h>
+#include <cds/opt/buffer.h>
+#include <cds/sync/spinlock.h>
+#include <cds/details/type_padding.h>
+
+namespace cds { namespace intrusive {
+
+ /// TreiberStack related definitions
+ /** @ingroup cds_intrusive_helper
+ */
+ namespace treiber_stack {
+
+ /// Stack node
+ /**
+ Template parameters:
+ - GC - garbage collector used
+ - Tag - a \ref cds_intrusive_hook_tag "tag"
+ */
+ template <class GC, typename Tag = opt::none >
+ using node = cds::intrusive::single_link::node< GC, Tag >;
+
+ /// Base hook
+ /**
+ \p Options are:
+ - opt::gc - garbage collector used.
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
+ */
+ template < typename... Options >
+ using base_hook = cds::intrusive::single_link::base_hook< Options...>;
+
+ /// Member hook
+ /**
+ \p MemberOffset specifies offset in bytes of \ref node member into your structure.
+ Use \p offsetof macro to define \p MemberOffset
+
+ \p Options are:
+ - opt::gc - garbage collector used.
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
+ */
+ template < size_t MemberOffset, typename... Options >
+ using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
+
+ /// Traits hook
+ /**
+ \p NodeTraits defines type traits for node.
+ See \ref node_traits for \p NodeTraits interface description
+
+ \p Options are:
+ - opt::gc - garbage collector used.
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
+ */
+ template <typename NodeTraits, typename... Options >
+ using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
+
+ //@cond
+ /// Operation id for the \ref cds_elimination_description "elimination back-off"
+ enum operation_id {
+ op_push, ///< push op id
+ op_pop ///< pop op id
+ };
+
+ /// Operation descriptor for the \ref cds_elimination_description "elimination back-off"
+ template <typename T>
+ struct operation: public cds::algo::elimination::operation_desc
+ {
+ operation_id idOp; ///< Op id
+ T * pVal; ///< for push: pointer to argument; for pop: accepts a return value
+ atomics::atomic<unsigned int> nStatus; ///< Internal elimination status
+
+ operation()
+ : pVal( nullptr )
+ , nStatus( 0 /*op_free*/ )
+ {}
+ };
+ //@endcond
+
+ /// Stack internal statistics. May be useful for debugging or profiling
+ /**
+ Template argument \p Counter defines type of counter.
+ Default is cds::atomicity::event_counter.
+ You may use stronger type of counter like as cds::atomicity::item_counter,
+ or even an integral type, for example, \p int
+ */
+ template <typename Counter = cds::atomicity::event_counter >
+ struct stat
+ {
+ typedef Counter counter_type ; ///< Counter type
+
+ counter_type m_PushCount ; ///< Push call count
+ counter_type m_PopCount ; ///< Pop call count
+ counter_type m_PushRace ; ///< Count of push race conditions encountered
+ counter_type m_PopRace ; ///< Count of pop race conditions encountered
+ counter_type m_ActivePushCollision ; ///< Count of active push collision for elimination back-off
+ counter_type m_ActivePopCollision ; ///< Count of active pop collision for elimination back-off
+ counter_type m_PassivePushCollision ; ///< Count of passive push collision for elimination back-off
+ counter_type m_PassivePopCollision ; ///< Count of passive pop collision for elimination back-off
+ counter_type m_EliminationFailed ; ///< Count of unsuccessful elimination back-off
+
+ //@cond
+ void onPush() { ++m_PushCount; }
+ void onPop() { ++m_PopCount; }
+ void onPushRace() { ++m_PushRace; }
+ void onPopRace() { ++m_PopRace; }
+ void onActiveCollision( operation_id opId )
+ {
+ if ( opId == treiber_stack::op_push )
+ ++m_ActivePushCollision;
+ else
+ ++m_ActivePopCollision;
+ }
+ void onPassiveCollision( operation_id opId )
+ {
+ if ( opId == treiber_stack::op_push )
+ ++m_PassivePushCollision;
+ else
+ ++m_PassivePopCollision;
+ }
+ void onEliminationFailed()
+ {
+ ++m_EliminationFailed;
+ }
+ //@endcond
+ };
+
+ /// Empty (no overhead) stack statistics. Support interface like treiber_stack::stat
+ struct empty_stat
+ {
+ //@cond
+ void onPush() {}
+ void onPop() {}
+ void onPushRace() {}
+ void onPopRace() {}
+ void onActiveCollision( operation_id ) {}
+ void onPassiveCollision( operation_id ) {}
+ void onEliminationFailed() {}
+ //@endcond
+ };
+
+ /// TreiberStack default type traits
+ struct traits
+ {
+ /// Back-off strategy
+ typedef cds::backoff::Default back_off;
+
+ /// Hook, possible types are \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook
+ typedef treiber_stack::base_hook<> hook;
+
+ /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p TreiberStack::clear() function
+ typedef opt::v::empty_disposer disposer;
+
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
+ typedef cds::atomicity::empty_item_counter item_counter;
+
+ /// C++ memory ordering model
+ /**
+ Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ */
+ typedef opt::v::relaxed_ordering memory_model;
+
+ /// Internal statistics (by default, disabled)
+ /**
+ Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
+ user-provided class that supports \p %treiber_stack::stat interface.
+ */
+ typedef treiber_stack::empty_stat stat;
+
+ /// Link checking, see \p cds::opt::link_checker
+ static constexpr const opt::link_check_type link_checker = opt::debug_check_link;
+
+ /** @name Elimination back-off traits
+ The following traits is used only if elimination enabled
+ */
+ ///@{
+
+ /// Enable elimination back-off; by default, it is disabled
+ static constexpr const bool enable_elimination = false;
+
+ /// Back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
+ typedef cds::backoff::delay<> elimination_backoff;
+
+ /// Buffer type for elimination array
+ /**
+ Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
+ The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
+ The size should be selected empirically for your application and hardware, there are no common rules for that.
+ Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
+ */
+ typedef opt::v::initialized_static_buffer< int, 4 > buffer;
+
+ /// Random engine to generate a random position in elimination array
+ typedef opt::v::c_rand random_engine;
+
+ /// Lock type used in elimination, default is cds::sync::spin
+ typedef cds::sync::spin lock_type;
+
+ ///@}
+ };
+
+ /// Metafunction converting option list to \p treiber_stack::traits
+ /**
+ Supported \p Options are:
+ - \p opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
+ If the option is not specified, \p %treiber_stack::base_hook<> is used.
+ - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+ - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
+ in \p TreiberStack::clear function.
+ - \p opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
+ no item counting. Use \p cds::atomicity::item_counter to enable item counting.
+ - \p opt::stat - the type to gather internal statistics.
+ Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
+ user-provided class that supports \p treiber_stack::stat interface.
+ - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
+
+ If elimination back-off is enabled, additional options can be specified:
+ - \p opt::buffer - a buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
+ The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
+ The size should be selected empirically for your application and hardware, there are no common rules for that.
+ Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
+ - \p opt::random_engine - a random engine to generate a random position in elimination array.
+ Default is \p opt::v::c_rand.
+ - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
+ - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin
+
+ Example: declare \p %TreiberStack with elimination enabled and internal statistics
+ \code
+ typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
+ typename cds::intrusive::treiber_stack::make_traits<
+ cds::opt::enable_elimination< true >,
+ cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
+ >::type
+ > myStack;
+ \endcode
+ */
+ template <typename... Options>
+ struct make_traits {
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined type; ///< Metafunction result
+# else
+ typedef typename cds::opt::make_options<
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ , Options...
+ >::type type;
+# endif
+ };
+
+
+ //@cond
+ namespace details {
+
+ template <bool EnableElimination, typename T, typename Traits>
+ class elimination_backoff;
+
+ template <typename T, typename Traits>
+ class elimination_backoff<false, T, Traits>
+ {
+ typedef typename Traits::back_off back_off;
+
+ struct wrapper
+ {
+ back_off m_bkoff;
+
+ void reset()
+ {
+ m_bkoff.reset();
+ }
+
+ template <typename Stat>
+ bool backoff( treiber_stack::operation< T >&, Stat& )
+ {
+ m_bkoff();
+ return false;
+ }
+ };
+
+ public:
+ elimination_backoff()
+ {}
+
+ elimination_backoff( size_t )
+ {}
+
+ typedef wrapper type;
+ type init()
+ {
+ return wrapper();
+ }
+ };
+
+ template <typename T, typename Traits>
+ class elimination_backoff<true, T, Traits>
+ {
+ typedef typename Traits::back_off back_off;
+
+ /// Back-off for elimination (usually delay)
+ typedef typename Traits::elimination_backoff elimination_backoff_type;
+ /// Lock type used in elimination back-off
+ typedef typename Traits::lock_type elimination_lock_type;
+ /// Random engine used in elimination back-off
+ typedef typename Traits::random_engine elimination_random_engine;
+
+ /// Per-thread elimination record
+ typedef cds::algo::elimination::record elimination_rec;
+
+ /// Collision array record
+ struct collision_array_record {
+ elimination_rec * pRec;
+ elimination_lock_type lock;
+ };
+
+ /// Collision array used in elimination-backoff; each item is optimized for cache-line size
+ typedef typename Traits::buffer::template rebind<
+ typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
+ >::other collision_array;
+
+ /// Operation descriptor used in elimination back-off
+ typedef treiber_stack::operation< T > operation_desc;
+
+ /// Elimination back-off data
+ struct elimination_data {
+ mutable elimination_random_engine randEngine; ///< random engine
+ collision_array collisions; ///< collision array
+
+ elimination_data()
+ {
+ //TODO: check Traits::buffer must be static!
+ }
+ elimination_data( size_t nCollisionCapacity )
+ : collisions( nCollisionCapacity )
+ {}
+ };
+
+ elimination_data m_Elimination;
+
+ enum operation_status {
+ op_free = 0,
+ op_waiting = 1,
+ op_collided = 2
+ };
+
+ typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
+
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
+ }
+
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< !Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
+ }
+
+ public:
+ elimination_backoff()
+ {
+ m_Elimination.collisions.zeroize();
+ }
+
+ elimination_backoff( size_t nCollisionCapacity )
+ : m_Elimination( nCollisionCapacity )
+ {
+ m_Elimination.collisions.zeroize();
+ }
+
+ typedef elimination_backoff& type;
+
+ type init()
+ {
+ return *this;
+ }
+
+ void reset()
+ {}
+
+ template <typename Stat>
+ bool backoff( operation_desc& op, Stat& stat )
+ {
+ elimination_backoff_type bkoff;
+ op.nStatus.store( op_waiting, atomics::memory_order_relaxed );
+
+ elimination_rec * myRec = cds::algo::elimination::init_record( op );
+
+ collision_array_record& slot = m_Elimination.collisions[ slot_index() ];
+ {
+ slot.lock.lock();
+ elimination_rec * himRec = slot.pRec;
+ if ( himRec ) {
+ operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
+ assert( himOp );
+ if ( himOp->idOp != op.idOp ) {
+
+ if ( op.idOp == treiber_stack::op_push )
+ himOp->pVal = op.pVal;
+ else
+ op.pVal = himOp->pVal;
+
+ slot.pRec = nullptr;
+ himOp->nStatus.store( op_collided, atomics::memory_order_release );
+ slot.lock.unlock();
+
+ cds::algo::elimination::clear_record();
+ stat.onActiveCollision( op.idOp );
+ return true;
+ }
+ //himOp->nStatus.store( op_free, atomics::memory_order_release );
+ }
+ slot.pRec = myRec;
+ slot.lock.unlock();
+ }
+
+ // Wait for colliding operation
+ bkoff( [&op]() noexcept -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_waiting; } );
+
+ {
+ slot_scoped_lock l( slot.lock );
+ if ( slot.pRec == myRec )
+ slot.pRec = nullptr;
+ }
+
+ bool bCollided = op.nStatus.load( atomics::memory_order_relaxed ) == op_collided;
+
+ if ( !bCollided )
+ stat.onEliminationFailed();
+ else
+ stat.onPassiveCollision( op.idOp );
+
+ cds::algo::elimination::clear_record();
+ return bCollided;
+ }
+ };
+
+ } // namespace details
+ //@endcond
+ } // namespace treiber_stack
+
+ /// Treiber intrusive stack
+ /** @ingroup cds_intrusive_stack
+ Intrusive implementation of well-known Treiber's stack algorithm:
+ - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
+
+ \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
+ The idea of elimination algorithm is taken from:
+ - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
+
+ The elimination algorithm uses a single elimination array as a back-off schema
+ on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
+ on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
+
+ @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
+ The main difficulty is the managing life-time of elimination record.
+ This implementation uses simplified lock-based (spin-based) approach which allows
+ the elimination record allocation on thread's stack.
+ This approach demonstrates sufficient performance under high load.
+
+ Template arguments:
+ - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
+ Garbage collecting schema must be the same as \p treiber_stack::node GC.
+ - \p T - a type the stack contains. A value of type \p T must be derived
+ from \p treiber_stack::node for \p treiber_stack::base_hook,
+ or it should have a member of type \p %treiber_stack::node for \p treiber_stack::member_hook,
+ or it should be convertible to \p %treiber_stack::node for \p treiber_stack::traits_hook.
+ - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
+ metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
+ \code
+ struct myTraits: public cds::intrusive::treiber_stack::traits {
+ typedef cds::intrusive::treiber_stack::stat<> stat;
+ };
+ typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
+
+ // Equivalent make_traits example:
+ typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
+ typename cds::intrusive::treiber_stack::make_traits<
+ cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
+ >::type
+ > myStack;
+ \endcode
+
+ @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
+
+ @anchor cds_intrusive_TreiberStack_examples
+ \par Examples
+
+ Example of how to use \p treiber_stack::base_hook.
+ Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class
+ \code
+ #include <cds/intrusive/treiber_stack.h>
+ #include <cds/gc/hp.h>
+
+ namespace ci = cds::intrusive;
+ typedef cds::gc::HP gc;
+
+ struct myData: public ci::treiber_stack::node< gc >
+ {
+ // ...
+ };
+
+ // Stack type
+ typedef ci::TreiberStack< gc,
+ myData,
+ typename cds::intrusive::treiber_stack::make_traits<
+ ci::opt::hook< ci::treiber_stack::base_hook< gc > >
+ >::type
+ > stack_t;
+
+ // Stack with elimination back-off enabled
+ typedef ci::TreiberStack< gc,
+ myData,
+ typename ci::treiber_stack::make_traits<
+ ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
+ cds::opt::enable_elimination< true >
+ >::type
+ > elimination_stack_t;
+ \endcode
+
+ Example of how to use \p treiber_stack::base_hook with different tags.
+ \code
+ #include <cds/intrusive/treiber_stack.h>
+ #include <cds/gc/hp.h>
+
+ namespace ci = cds::intrusive;
+ typedef cds::gc::HP gc;
+
+ // It is not necessary to declare complete type for tags
+ struct tag1;
+ struct tag2;
+
+ struct myData
+ : public ci::treiber_stack::node< gc, tag1 >
+ , public ci::treiber_stack::node< gc, tag2 >
+ {
+ // ...
+ };
+
+ typedef ci::TreiberStack< gc,
+ myData,
+ typename ci::treiber_stack::make_traits<
+ ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
+ >::type
+ > stack1_t;
+
+ typedef ci::TreiberStack< gc,
+ myData,
+ typename ci::treiber_stack::make_traits<
+ ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 > >
+ >::type
+ > stack2_t;
+
+ // You may add myData objects into stack1_t and stack2_t independently
+ void foo() {
+ stack1_t s1;
+ stack2_t s2;
+
+ myData i1, i2;
+ s1.push( i1 );
+ s2.push( i2 );
+ s2.push( i1 ) ; // i1 is now contained in s1 and s2.
+
+ myData * p;
+
+ p = s1.pop() ; // pop i1 from s1
+ p = s1.pop() ; // p == nullptr, s1 is empty
+ p = s2.pop() ; // pop i1 from s2
+ p = s2.pop() ; // pop i2 from s2
+ p = s2.pop() ; // p == nullptr, s2 is empty
+ }
+ \endcode
+
+ Example of how to use \p treiber_stack::member_hook.
+ Your class should have a member of type \p treiber_stack::node
+ \code
+ #include <stddef.h> // offsetof macro
+ #include <cds/intrusive/treiber_stack.h>
+ #include <cds/gc/hp.h>
+
+ namespace ci = cds::intrusive;
+ typedef cds::gc::HP gc;
+
+ struct myData
+ {
+ // ...
+ ci::treiber_stack::node< gc > member_hook_;
+ // ...
+ };
+
+ typedef ci::TreiberStack< gc,
+ myData,
+ typename ci::treiber_stack::make_traits<
+ ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >>
+ >::type
+ > stack_t;
+ \endcode
+ */
+ template <
+ typename GC,
+ typename T,
+ typename Traits = treiber_stack::traits
+ >
+ class TreiberStack
+ {
+ public:
+ /// Rebind template arguments
+ template <typename GC2, typename T2, typename Traits2>
+ struct rebind {
+ typedef TreiberStack< GC2, T2, Traits2 > other ; ///< Rebinding result
+ };
+
+ public:
+ typedef GC gc; ///< Garbage collector
+ typedef T value_type; ///< type of value stored in the stack
+ typedef Traits traits; ///< Stack traits
+
+ typedef typename traits::hook hook; ///< hook type
+ typedef typename hook::node_type node_type; ///< node type
+ typedef typename traits::disposer disposer; ///< disposer used
+ typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
+ typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker ; ///< link checker
+ typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
+ typedef typename traits::item_counter item_counter; ///< Item counter class
+ typedef typename traits::stat stat; ///< Internal statistics
+ typedef typename traits::back_off back_off; ///< back-off strategy
+
+ /// How many Hazard pointers is required for Treiber's stack implementation
+ static constexpr size_t const c_nHazardPtrCount = 1;
+
+ public: // related to elimination back-off
+
+ /// Elimination back-off is enabled or not
+ static constexpr const bool enable_elimination = traits::enable_elimination;
+ /// back-off strategy used to wait for elimination
+ typedef typename traits::elimination_backoff elimination_backoff_type;
+ /// Lock type used in elimination back-off
+ typedef typename traits::lock_type elimination_lock_type;
+ /// Random engine used in elimination back-off
+ typedef typename traits::random_engine elimination_random_engine;
+
+ protected:
+ typename node_type::atomic_node_ptr m_Top; ///< Top of the stack
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_stat; ///< Internal statistics
+
+ //@cond
+ typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
+ elimination_backoff m_Backoff;
+
+ typedef treiber_stack::operation< value_type > operation_desc;
+
+ // GC and node_type::gc must be the same
+ static_assert( std::is_same<gc, typename node_type::gc>::value, "GC and node_type::gc must be the same");
+
+ static_assert( !enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value,
+ "Random engine result type must be unsigned int");
+ //@endcond
+
+ protected:
+ //@cond
+ void clear_links( node_type * pNode ) noexcept
+ {
+ pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
+ }
+
+ template <bool EnableElimination>
+ struct elimination_backoff_impl;
+ //@endcond
+
+ public:
+ /// Constructs empty stack
+ TreiberStack()
+ : m_Top( nullptr )
+ {}
+
+ /// Constructs empty stack and initializes elimination back-off data
+ /**
+ This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
+ \p Traits contains <tt>typedef cds::opt::v::initialized_dynamic_buffer buffer</tt>.
+ \p nCollisionCapacity parameter specifies the capacity of collision array.
+ */
+ TreiberStack( size_t nCollisionCapacity )
+ : m_Top( nullptr )
+ , m_Backoff( nCollisionCapacity )
+ {}
+
+ /// \p %TreiberStack is not copy-constructible
+ TreiberStack( TreiberStack const& ) = delete;
+
+ /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
+ ~TreiberStack()
+ {
+ clear();
+ }
+
+ /// Push the item \p val on the stack
+ /**
+ No copying is made since it is intrusive stack.
+ */
+ bool push( value_type& val )
+ {
+ node_type * pNew = node_traits::to_node_ptr( val );
+ link_checker::is_empty( pNew );
+
+ typename elimination_backoff::type bkoff = m_Backoff.init();
+
+ operation_desc op;
+ if ( enable_elimination ) {
+ op.idOp = treiber_stack::op_push;
+ op.pVal = &val;
+ }
+
+ node_type * t = m_Top.load( memory_model::memory_order_relaxed );
+ while ( true ) {
+ pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
+ if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_acquire )) {
+ ++m_ItemCounter;
+ m_stat.onPush();
+ return true;
+ }
+ m_stat.onPushRace();
+
+ if ( bkoff.backoff( op, m_stat ))
+ return true;
+ }
+ }
+
+ /// Pop an item from the stack
+ /**
+ If stack is empty, returns \p nullptr.
+ The disposer is <b>not</b> called for popped item.
+ See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
+ */
+ value_type * pop()
+ {
+ typename elimination_backoff::type bkoff = m_Backoff.init();
+ typename gc::Guard guard;
+
+ operation_desc op;
+ if ( enable_elimination ) {
+ op.idOp = treiber_stack::op_pop;
+ }
+
+ while ( true ) {
+ node_type * t = guard.protect( m_Top,
+ []( node_type * p ) -> value_type * {
+ return node_traits::to_value_ptr( p );
+ });
+ if ( t == nullptr )
+ return nullptr; // stack is empty
+
+ node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
+ if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ clear_links( t );
+ --m_ItemCounter;
+ m_stat.onPop();
+ return node_traits::to_value_ptr( *t );
+ }
+
+ m_stat.onPopRace();
+ if ( bkoff.backoff( op, m_stat )) {
+ // may return nullptr if stack is empty
+ return op.pVal;
+ }
+ }
+ }
+
+ /// Check if stack is empty
+ bool empty() const
+ {
+ return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
+ }
+
+ /// Clear the stack
+ /** @anchor cds_intrusive_TreiberStack_clear
+ For each removed item the disposer is called.
+
+ @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
+ if some other thread pushes an item into the stack during \p clear works
+ */
+ void clear()
+ {
+ back_off bkoff;
+ node_type * pTop;
+ while ( true ) {
+ pTop = m_Top.load( memory_model::memory_order_relaxed );
+ if ( pTop == nullptr )
+ return;
+ if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ m_ItemCounter.reset();
+ break;
+ }
+ bkoff();
+ }
+
+ while( pTop ) {
+ node_type * p = pTop;
+ pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
+ clear_links( p );
+ gc::template retire<disposer>( node_traits::to_value_ptr( *p ));
+ }
+ }
+
+ /// Returns stack's item count
+ /**
+ The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
+ this function always returns 0.
+
+ @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack
+ is empty. To check emptyness use \ref empty() method.
+ */
+ size_t size() const
+ {
+ return m_ItemCounter.value();
+ }
+
+ /// Returns reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_stat;
+ }
+ };
+
+}} // namespace cds::intrusive
+
+#endif // #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
projects / c11concurrency-benchmarks.git / blobdiff