3 #ifndef __CDS_CONTAINER_TREIBER_STACK_H
4 #define __CDS_CONTAINER_TREIBER_STACK_H
7 #include <cds/intrusive/treiber_stack.h>
8 #include <cds/container/details/base.h>
10 namespace cds { namespace container {
13 namespace treiber_stack {
14 using cds::intrusive::treiber_stack::stat;
15 using cds::intrusive::treiber_stack::empty_stat;
17 template <typename GC, typename T, typename... Options>
18 struct make_treiber_stack
22 struct default_options {
23 typedef cds::backoff::Default back_off;
24 typedef CDS_DEFAULT_ALLOCATOR allocator;
25 typedef cds::opt::v::relaxed_ordering memory_model;
26 typedef cds::atomicity::empty_item_counter item_counter;
27 typedef empty_stat stat;
29 // Elimination back-off options
30 static CDS_CONSTEXPR_CONST bool enable_elimination = false;
31 typedef cds::backoff::delay<> elimination_backoff;
32 typedef opt::v::static_buffer< int, 4 > buffer;
33 typedef opt::v::c_rand random_engine;
34 typedef cds::lock::Spin lock_type;
37 typedef typename cds::opt::make_options<
38 typename cds::opt::find_type_traits< default_options, Options... >::type
43 typedef typename options::memory_model memory_model;
45 struct node_type: public cds::intrusive::single_link::node< gc >
49 node_type( const value_type& val )
52 template <typename... Args>
53 node_type( Args&&... args )
54 : m_value( std::forward<Args>(args)...)
58 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
59 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
61 struct node_deallocator
63 void operator ()( node_type * pNode )
65 cxx_allocator().Delete( pNode );
69 typedef intrusive::TreiberStack<
72 ,intrusive::opt::hook<
73 intrusive::single_link::base_hook< cds::opt::gc<gc> >
75 ,cds::opt::back_off< typename options::back_off >
76 ,cds::intrusive::opt::disposer< node_deallocator >
77 ,cds::opt::memory_model< memory_model >
78 ,cds::opt::item_counter< typename options::item_counter >
79 ,cds::opt::stat< typename options::stat >
80 ,cds::opt::enable_elimination< options::enable_elimination >
81 ,cds::opt::buffer< typename options::buffer >
82 ,cds::opt::random_engine< typename options::random_engine >
83 ,cds::opt::elimination_backoff< typename options::elimination_backoff >
84 ,cds::opt::lock_type< typename options::lock_type >
87 } // namespace treiber_stack
90 /// Treiber's stack algorithm
91 /** @ingroup cds_nonintrusive_stack
92 It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
93 intrusive::TreiberStack.
96 - \p GC - garbage collector type: gc::HP, gc::PTB
97 - \p T - type stored in the stack. It should be default-constructible, copy-constructible, assignable type.
98 - \p Options - options
100 Available \p Options:
101 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
102 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used
103 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
104 or opt::v::sequential_consistent (sequentially consisnent memory model).
105 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
106 - opt::stat - the type to gather internal statistics.
107 Possible option value are: \ref cds::intrusive::treiber_stack::stat "treiber_stack::stat",
108 \ref cds::intrusive::treiber_stack::empty_stat "treiber_stack::empty_stat" (the default),
109 user-provided class that supports treiber_stack::stat interface.
110 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p valse.
112 If elimination back-off is enabled (\p %cds::opt::enable_elimination< true >) additional options can be specified:
113 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
114 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
115 The size should be selected empirically for your application and hardware, there are no common rules for that.
116 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
117 - opt::random_engine - a random engine to generate a random position in elimination array.
118 Default is opt::v::c_rand.
119 - opt::elimination_backoff - back-off strategy to wait for elimination, default is cds::backoff::delay<>
120 - opt::lock_type - a lock type used in elimination back-off, default is cds::lock::Spin.
122 template < typename GC, typename T, typename... Options >
125 #ifdef CDS_DOXYGEN_INVOKED
126 intrusive::TreiberStack< GC, cds::intrusive::single_link::node< T >, Options... >
128 treiber_stack::make_treiber_stack< GC, T, Options... >::type
132 typedef treiber_stack::make_treiber_stack< GC, T, Options... > options;
133 typedef typename options::type base_class;
137 /// Rebind template arguments
138 template <typename GC2, typename T2, typename... Options2>
140 typedef TreiberStack< GC2, T2, Options2...> other ; ///< Rebinding result
144 typedef T value_type ; ///< Value type stored in the stack
145 typedef typename base_class::gc gc ; ///< Garbage collector used
146 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
147 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
148 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_order option
149 typedef typename base_class::stat stat ; ///< Internal statistics policy used
152 typedef typename options::node_type node_type ; ///< stack node type (derived from intrusive::single_link::node)
155 typedef typename options::cxx_allocator cxx_allocator;
156 typedef typename options::node_deallocator node_deallocator; // deallocate node
161 static node_type * alloc_node( const value_type& val )
163 return cxx_allocator().New( val );
165 template <typename... Args>
166 static node_type * alloc_node_move( Args&&... args )
168 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
171 static void free_node( node_type * p )
173 node_deallocator()( p );
175 static void retire_node( node_type * p )
177 gc::template retire<typename base_class::disposer>( p );
180 struct node_disposer {
181 void operator()( node_type * pNode )
186 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
190 /// Constructs empty stack
194 /// Constructs empty stack and initializes elimination back-off data
196 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
197 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
198 \p nCollisionCapacity parameter specifies the capacity of collision array.
200 TreiberStack( size_t nCollisionCapacity )
201 : base_class( nCollisionCapacity )
204 TreiberStack( TreiberStack const& ) = delete;
206 /// Clears the stack on destruction
210 /// Push the item \p val on the stack
211 bool push( value_type const& val )
213 scoped_node_ptr p( alloc_node(val));
214 if ( base_class::push( *p )) {
221 /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
222 template <typename... Args>
223 bool emplace( Args&&... args )
225 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
226 if ( base_class::push( *p )) {
233 /// Pop an item from the stack
235 The value of popped item is stored in \p val.
236 On success functions returns \p true, \p val contains value popped from the stack.
237 If stack is empty the function returns \p false, \p val is unchanged.
239 bool pop( value_type& val )
241 node_type * p = base_class::pop();
251 /// Check if stack is empty
254 return base_class::empty();
263 /// Returns stack's item count
265 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
266 this function always returns 0.
268 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
269 is empty. To check emptyness use \ref empty() method.
273 return base_class::size();
276 /// Returns reference to internal statistics
277 stat const& statistics() const
279 return base_class::statistics();
283 }} // namespace cds::container
286 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H