3 #ifndef __CDS_CONTAINER_TREIBER_STACK_H
4 #define __CDS_CONTAINER_TREIBER_STACK_H
6 #include <cds/intrusive/treiber_stack.h>
7 #include <cds/container/base.h>
8 #include <cds/details/std/memory.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, CDS_DECL_OPTIONS11>
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, CDS_OPTIONS11 >::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 # ifdef CDS_EMPLACE_SUPPORT
53 template <typename... Args>
54 node_type( Args&&... args )
55 : m_value( std::forward<Args>(args)...)
63 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
64 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
66 struct node_deallocator
68 void operator ()( node_type * pNode )
70 cxx_allocator().Delete( pNode );
74 typedef intrusive::TreiberStack<
77 ,intrusive::opt::hook<
78 intrusive::single_link::base_hook< cds::opt::gc<gc> >
80 ,cds::opt::back_off< typename options::back_off >
81 ,cds::intrusive::opt::disposer< node_deallocator >
82 ,cds::opt::memory_model< memory_model >
83 ,cds::opt::item_counter< typename options::item_counter >
84 ,cds::opt::stat< typename options::stat >
85 ,cds::opt::enable_elimination< options::enable_elimination >
86 ,cds::opt::buffer< typename options::buffer >
87 ,cds::opt::random_engine< typename options::random_engine >
88 ,cds::opt::elimination_backoff< typename options::elimination_backoff >
89 ,cds::opt::lock_type< typename options::lock_type >
92 } // namespace treiber_stack
95 /// Treiber's stack algorithm
96 /** @ingroup cds_nonintrusive_stack
97 It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
98 intrusive::TreiberStack.
101 - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
102 - \p T - type stored in the stack. It should be default-constructible, copy-constructible, assignable type.
103 - \p Options - options
105 Available \p Options:
106 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
107 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used
108 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
109 or opt::v::sequential_consistent (sequentially consisnent memory model).
110 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
111 - opt::stat - the type to gather internal statistics.
112 Possible option value are: \ref cds::intrusive::treiber_stack::stat "treiber_stack::stat",
113 \ref cds::intrusive::treiber_stack::empty_stat "treiber_stack::empty_stat" (the default),
114 user-provided class that supports treiber_stack::stat interface.
115 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p valse.
117 If elimination back-off is enabled (\p %cds::opt::enable_elimination< true >) additional options can be specified:
118 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
119 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
120 The size should be selected empirically for your application and hardware, there are no common rules for that.
121 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
122 - opt::random_engine - a random engine to generate a random position in elimination array.
123 Default is opt::v::c_rand.
124 - opt::elimination_backoff - back-off strategy to wait for elimination, default is cds::backoff::delay<>
125 - opt::lock_type - a lock type used in elimination back-off, default is cds::lock::Spin.
127 template < typename GC, typename T, CDS_DECL_OPTIONS11 >
130 #ifdef CDS_DOXYGEN_INVOKED
131 intrusive::TreiberStack< GC, cds::intrusive::single_link::node< T >, Options... >
133 treiber_stack::make_treiber_stack< GC, T, CDS_OPTIONS11 >::type
137 typedef treiber_stack::make_treiber_stack< GC, T, CDS_OPTIONS11 > options;
138 typedef typename options::type base_class;
142 /// Rebind template arguments
143 template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS11>
145 typedef TreiberStack< GC2, T2, CDS_OTHER_OPTIONS11> other ; ///< Rebinding result
149 typedef T value_type ; ///< Value type stored in the stack
150 typedef typename base_class::gc gc ; ///< Garbage collector used
151 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
152 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
153 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_order option
154 typedef typename base_class::stat stat ; ///< Internal statistics policy used
157 typedef typename options::node_type node_type ; ///< stack node type (derived from intrusive::single_link::node)
160 typedef typename options::cxx_allocator cxx_allocator;
161 typedef typename options::node_deallocator node_deallocator; // deallocate node
166 static node_type * alloc_node( const value_type& val )
168 return cxx_allocator().New( val );
170 # ifdef CDS_EMPLACE_SUPPORT
171 template <typename... Args>
172 static node_type * alloc_node_move( Args&&... args )
174 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
178 static void free_node( node_type * p )
180 node_deallocator()( p );
182 static void retire_node( node_type * p )
184 gc::template retire<typename base_class::disposer>( p );
187 struct node_disposer {
188 void operator()( node_type * pNode )
193 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
197 /// Constructs empty stack
201 /// Constructs empty stack and initializes elimination back-off data
203 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
204 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
205 \p nCollisionCapacity parameter specifies the capacity of collision array.
207 TreiberStack( size_t nCollisionCapacity )
208 : base_class( nCollisionCapacity )
211 /// Clears the stack on destruction
215 /// Push the item \p val on the stack
216 bool push( const value_type& val )
218 scoped_node_ptr p( alloc_node(val));
219 if ( base_class::push( *p )) {
226 # ifdef CDS_EMPLACE_SUPPORT
227 /// Pushes data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
229 This function is available only for compiler that supports
230 variadic template and move semantics
232 template <typename... Args>
233 bool emplace( Args&&... args )
235 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
236 if ( base_class::push( *p )) {
244 /// Pop an item from the stack
246 The value of popped item is stored in \p val.
247 On success functions returns \p true, \p val contains value popped from the stack.
248 If stack is empty the function returns \p false, \p val is unchanged.
250 bool pop( value_type& val )
252 node_type * p = base_class::pop();
262 /// Check if stack is empty
265 return base_class::empty();
274 /// Returns stack's item count
276 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
277 this function always returns 0.
279 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
280 is empty. To check emptyness use \ref empty() method.
284 return base_class::size();
287 /// Returns reference to internal statistics
288 stat const& statistics() const
290 return base_class::statistics();
294 }} // namespace cds::container
297 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H