3 #ifndef __CDS_CONTAINER_TREIBER_STACK_H
4 #define __CDS_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::lock::Spin
73 typedef cds::lock::Spin lock_type;
78 /// Metafunction converting option list to \p TreiberStack traits
80 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
81 Supported \p Options are:
82 - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
83 - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
84 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
85 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
86 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
87 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
88 - opt::stat - the type to gather internal statistics.
89 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
90 user-provided class that supports \p %treiber_stack::stat interface.
91 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
93 If elimination back-off is enabled, additional options can be specified:
94 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
95 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
96 The size should be selected empirically for your application and hardware, there are no common rules for that.
97 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
98 - opt::random_engine - a random engine to generate a random position in elimination array.
99 Default is \p opt::v::c_rand.
100 - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
101 - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin.
103 Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
105 typedef cds::container::TreiberStack< cds::gc::HP, Foo,
106 typename cds::container::treiber_stack::make_traits<
107 cds::opt::item_counter< cds::atomicity::item_counter >,
108 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
113 template <typename... Options>
115 # ifdef CDS_DOXYGEN_INVOKED
116 typedef implementation_defined type; ///< Metafunction result
118 typedef typename cds::opt::make_options<
119 typename cds::opt::find_type_traits< traits, Options... >::type
124 } // namespace treiber_stack
128 template <typename GC, typename T, typename Traits>
129 struct make_treiber_stack
132 typedef T value_type;
133 typedef Traits traits;
135 struct node_type: public cds::intrusive::treiber_stack::node< gc >
139 node_type( const value_type& val )
143 template <typename... Args>
144 node_type( Args&&... args )
145 : m_value( std::forward<Args>( args )... )
149 typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
150 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
152 struct node_deallocator
154 void operator ()( node_type * pNode )
156 cxx_allocator().Delete( pNode );
160 struct intrusive_traits: public traits
162 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
163 typedef node_deallocator disposer;
164 static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;
167 // Result of metafunction
168 typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
170 } // namespace details
173 /// Treiber's stack algorithm
174 /** @ingroup cds_nonintrusive_stack
175 It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
176 intrusive::TreiberStack.
179 - \p GC - garbage collector type: \p gc::HP, gc::DHP
180 - \p T - type stored in the stack.
181 - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
182 metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
184 struct myTraits: public cds::container::treiber_stack::traits {
185 typedef cds::intrusive::treiber_stack::stat<> stat;
186 typedef cds::atomicity::item_counter item_counter;
188 typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
190 // Equivalent make_traits example:
191 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
192 typename cds::intrusive::treiber_stack::make_traits<
193 cds::opt::item_counter< cds::atomicity::item_counter >,
194 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
202 typename Traits = treiber_stack::traits
206 #ifdef CDS_DOXYGEN_INVOKED
207 intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
209 details::make_treiber_stack< GC, T, Traits >::type
213 typedef details::make_treiber_stack< GC, T, Traits > maker;
214 typedef typename maker::type base_class;
218 /// Rebind template arguments
219 template <typename GC2, typename T2, typename Traits2>
221 typedef TreiberStack< GC2, T2, Traits2 > other; ///< Rebinding result
225 typedef T value_type ; ///< Value type stored in the stack
226 typedef typename base_class::gc gc ; ///< Garbage collector used
227 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
228 typedef typename maker::allocator_type allocator_type ; ///< Allocator type used for allocating/deallocating the nodes
229 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_order option
230 typedef typename base_class::stat stat ; ///< Internal statistics policy used
233 typedef typename maker::node_type node_type ; ///< stack node type (derived from \p intrusive::treiber_stack::node)
236 typedef typename maker::cxx_allocator cxx_allocator;
237 typedef typename maker::node_deallocator node_deallocator;
242 static node_type * alloc_node( const value_type& val )
244 return cxx_allocator().New( val );
246 template <typename... Args>
247 static node_type * alloc_node_move( Args&&... args )
249 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
252 static void free_node( node_type * p )
254 node_deallocator()( p );
256 static void retire_node( node_type * p )
258 gc::template retire<typename base_class::disposer>( p );
261 struct node_disposer {
262 void operator()( node_type * pNode )
267 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
271 /// Constructs empty stack
275 /// Constructs empty stack and initializes elimination back-off data
277 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
278 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
279 \p nCollisionCapacity parameter specifies the capacity of collision array.
281 TreiberStack( size_t nCollisionCapacity )
282 : base_class( nCollisionCapacity )
285 /// \p %TreiberStack is not copy-constructible
286 TreiberStack( TreiberStack const& ) = delete;
288 /// Clears the stack on destruction
292 /// Pushes copy of \p val on the stack
293 bool push( value_type const& val )
295 scoped_node_ptr p( alloc_node(val));
296 if ( base_class::push( *p )) {
303 /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
304 template <typename... Args>
305 bool emplace( Args&&... args )
307 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
308 if ( base_class::push( *p )) {
315 /// Pops an item from the stack
317 The value of popped item is stored in \p val using assignment operator.
318 On success functions returns \p true, \p val contains value popped from the stack.
319 If stack is empty the function returns \p false, \p val is unchanged.
321 bool pop( value_type& val )
323 return pop_with( [&val]( value_type& src ) { val = src; } );
326 /// Pops an item from the stack with functor
328 \p Func interface is:
330 void func( value_type& src );
332 where \p src - item popped.
334 The \p %pop_with can be used to move item from the stack to user-provided storage:
336 cds::container::TreiberStack<cds::gc::HP, std::string > myStack;
340 myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } );
343 template <typename Func>
344 bool pop_with( Func f )
346 node_type * p = base_class::pop();
356 /// Check if stack is empty
359 return base_class::empty();
368 /// Returns stack's item count
370 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
371 this function always returns 0.
373 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
374 is empty. To check emptyness use \ref empty() method.
378 return base_class::size();
381 /// Returns reference to internal statistics
382 stat const& statistics() const
384 return base_class::statistics();
388 }} // namespace cds::container
390 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H