3 #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H
4 #define CDSLIB_CONTAINER_TREIBER_STACK_H
6 #include <memory> // unique_ptr
7 #include <cds/intrusive/treiber_stack.h>
8 #include <cds/container/details/base.h>
10 namespace cds { namespace container {
12 /// TreiberStack related definitions
13 /** @ingroup cds_nonintrusive_helper
15 namespace treiber_stack {
16 /// Internal statistics
17 template <typename Counter = cds::intrusive::treiber_stack::stat<>::counter_type >
18 using stat = cds::intrusive::treiber_stack::stat< Counter >;
20 /// Dummy internal statistics
21 typedef cds::intrusive::treiber_stack::empty_stat empty_stat;
23 /// TreiberStack default type traits
27 typedef cds::backoff::Default back_off;
30 typedef CDS_DEFAULT_ALLOCATOR allocator;
32 /// C++ memory ordering model
34 Can be opt::v::relaxed_ordering (relaxed memory model, the default)
35 or opt::v::sequential_consistent (sequentially consisnent memory model).
37 typedef opt::v::relaxed_ordering memory_model;
39 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
40 typedef cds::atomicity::empty_item_counter item_counter;
42 /// Internal statistics (by default, no internal statistics)
44 Possible types are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
45 user-provided class that supports treiber_stack::stat interface.
47 typedef empty_stat stat;
49 /** @name Elimination back-off traits
50 The following traits is used only if elimination enabled
54 /// Enable elimination back-off; by default, it is disabled
55 static CDS_CONSTEXPR const bool enable_elimination = false;
57 /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
58 typedef cds::backoff::delay<> elimination_backoff;
60 /// Buffer type for elimination array
62 Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
63 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
64 The size should be selected empirically for your application and hardware, there are no common rules for that.
65 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
67 typedef opt::v::static_buffer< int, 4 > buffer;
69 /// Random engine to generate a random position in elimination array
70 typedef opt::v::c_rand random_engine;
72 /// Lock type used in elimination, default is cds::sync::spin
73 typedef cds::sync::spin lock_type;
78 /// Metafunction converting option list to \p TreiberStack traits
80 Supported \p Options are:
81 - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
82 - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
83 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
84 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
85 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
86 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
87 - opt::stat - the type to gather internal statistics.
88 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
89 user-provided class that supports \p %treiber_stack::stat interface.
90 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
92 If elimination back-off is enabled, additional options can be specified:
93 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
94 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
95 The size should be selected empirically for your application and hardware, there are no common rules for that.
96 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
97 - opt::random_engine - a random engine to generate a random position in elimination array.
98 Default is \p opt::v::c_rand.
99 - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
100 - opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin.
102 Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
104 typedef cds::container::TreiberStack< cds::gc::HP, Foo,
105 typename cds::container::treiber_stack::make_traits<
106 cds::opt::item_counter< cds::atomicity::item_counter >,
107 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
112 template <typename... Options>
114 # ifdef CDS_DOXYGEN_INVOKED
115 typedef implementation_defined type; ///< Metafunction result
117 typedef typename cds::opt::make_options<
118 typename cds::opt::find_type_traits< traits, Options... >::type
123 } // namespace treiber_stack
127 template <typename GC, typename T, typename Traits>
128 struct make_treiber_stack
131 typedef T value_type;
132 typedef Traits traits;
134 struct node_type: public cds::intrusive::treiber_stack::node< gc >
138 node_type( const value_type& val )
142 template <typename... Args>
143 node_type( Args&&... args )
144 : m_value( std::forward<Args>( args )... )
148 typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
149 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
151 struct node_deallocator
153 void operator ()( node_type * pNode )
155 cxx_allocator().Delete( pNode );
159 struct intrusive_traits: public traits
161 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
162 typedef node_deallocator disposer;
163 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;
166 // Result of metafunction
167 typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
169 } // namespace details
172 /// Treiber's stack algorithm
173 /** @ingroup cds_nonintrusive_stack
174 It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
175 intrusive::TreiberStack.
178 - \p GC - garbage collector type: \p gc::HP, gc::DHP
179 - \p T - type stored in the stack.
180 - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
181 metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
183 struct myTraits: public cds::container::treiber_stack::traits {
184 typedef cds::intrusive::treiber_stack::stat<> stat;
185 typedef cds::atomicity::item_counter item_counter;
187 typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
189 // Equivalent make_traits example:
190 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
191 typename cds::intrusive::treiber_stack::make_traits<
192 cds::opt::item_counter< cds::atomicity::item_counter >,
193 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
201 typename Traits = treiber_stack::traits
205 #ifdef CDS_DOXYGEN_INVOKED
206 intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
208 details::make_treiber_stack< GC, T, Traits >::type
212 typedef details::make_treiber_stack< GC, T, Traits > maker;
213 typedef typename maker::type base_class;
217 /// Rebind template arguments
218 template <typename GC2, typename T2, typename Traits2>
220 typedef TreiberStack< GC2, T2, Traits2 > other; ///< Rebinding result
224 typedef T value_type ; ///< Value type stored in the stack
225 typedef typename base_class::gc gc ; ///< Garbage collector used
226 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
227 typedef typename maker::allocator_type allocator_type ; ///< Allocator type used for allocating/deallocating the nodes
228 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_order option
229 typedef typename base_class::stat stat ; ///< Internal statistics policy used
232 typedef typename maker::node_type node_type ; ///< stack node type (derived from \p intrusive::treiber_stack::node)
235 typedef typename maker::cxx_allocator cxx_allocator;
236 typedef typename maker::node_deallocator node_deallocator;
241 static node_type * alloc_node( const value_type& val )
243 return cxx_allocator().New( val );
245 template <typename... Args>
246 static node_type * alloc_node_move( Args&&... args )
248 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
251 static void free_node( node_type * p )
253 node_deallocator()( p );
255 static void retire_node( node_type * p )
257 gc::template retire<typename base_class::disposer>( p );
260 struct node_disposer {
261 void operator()( node_type * pNode )
266 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
270 /// Constructs empty stack
274 /// Constructs empty stack and initializes elimination back-off data
276 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
277 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
278 \p nCollisionCapacity parameter specifies the capacity of collision array.
280 TreiberStack( size_t nCollisionCapacity )
281 : base_class( nCollisionCapacity )
284 /// \p %TreiberStack is not copy-constructible
285 TreiberStack( TreiberStack const& ) = delete;
287 /// Clears the stack on destruction
291 /// Pushes copy of \p val on the stack
292 bool push( value_type const& val )
294 scoped_node_ptr p( alloc_node(val));
295 if ( base_class::push( *p )) {
302 /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
303 template <typename... Args>
304 bool emplace( Args&&... args )
306 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
307 if ( base_class::push( *p )) {
314 /// Pops an item from the stack
316 The value of popped item is stored in \p val using assignment operator.
317 On success functions returns \p true, \p val contains value popped from the stack.
318 If stack is empty the function returns \p false, \p val is unchanged.
320 bool pop( value_type& val )
322 return pop_with( [&val]( value_type& src ) { val = src; } );
325 /// Pops an item from the stack with functor
327 \p Func interface is:
329 void func( value_type& src );
331 where \p src - item popped.
333 The \p %pop_with can be used to move item from the stack to user-provided storage:
335 cds::container::TreiberStack<cds::gc::HP, std::string > myStack;
339 myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } );
342 template <typename Func>
343 bool pop_with( Func f )
345 node_type * p = base_class::pop();
355 /// Check if stack is empty
358 return base_class::empty();
367 /// Returns stack's item count
369 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
370 this function always returns 0.
372 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
373 is empty. To check emptyness use \ref empty() method.
377 return base_class::size();
380 /// Returns reference to internal statistics
381 stat const& statistics() const
383 return base_class::statistics();
387 }} // namespace cds::container
389 #endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H