2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H
32 #define CDSLIB_CONTAINER_TREIBER_STACK_H
34 #include <memory> // unique_ptr
35 #include <cds/intrusive/treiber_stack.h>
36 #include <cds/container/details/base.h>
38 namespace cds { namespace container {
40 /// TreiberStack related definitions
41 /** @ingroup cds_nonintrusive_helper
43 namespace treiber_stack {
44 /// Internal statistics
45 template <typename Counter = cds::intrusive::treiber_stack::stat<>::counter_type >
46 using stat = cds::intrusive::treiber_stack::stat< Counter >;
48 /// Dummy internal statistics
49 typedef cds::intrusive::treiber_stack::empty_stat empty_stat;
51 /// TreiberStack default type traits
55 typedef cds::backoff::Default back_off;
58 typedef CDS_DEFAULT_ALLOCATOR allocator;
60 /// C++ memory ordering model
62 Can be opt::v::relaxed_ordering (relaxed memory model, the default)
63 or opt::v::sequential_consistent (sequentially consisnent memory model).
65 typedef opt::v::relaxed_ordering memory_model;
67 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
68 typedef cds::atomicity::empty_item_counter item_counter;
70 /// Internal statistics (by default, no internal statistics)
72 Possible types are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
73 user-provided class that supports treiber_stack::stat interface.
75 typedef empty_stat stat;
77 /** @name Elimination back-off traits
78 The following traits is used only if elimination enabled
82 /// Enable elimination back-off; by default, it is disabled
83 static CDS_CONSTEXPR const bool enable_elimination = false;
85 /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
86 typedef cds::backoff::delay<> elimination_backoff;
88 /// Buffer type for elimination array
90 Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
91 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
92 The size should be selected empirically for your application and hardware, there are no common rules for that.
93 Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
95 typedef opt::v::initialized_static_buffer< int, 4 > buffer;
97 /// Random engine to generate a random position in elimination array
98 typedef opt::v::c_rand random_engine;
100 /// Lock type used in elimination, default is cds::sync::spin
101 typedef cds::sync::spin lock_type;
106 /// Metafunction converting option list to \p TreiberStack traits
108 Supported \p Options are:
109 - \p opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
110 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
111 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
112 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
113 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
114 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
115 - \p opt::stat - the type to gather internal statistics.
116 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
117 user-provided class that supports \p %treiber_stack::stat interface.
118 - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
120 If elimination back-off is enabled, additional options can be specified:
121 - \p opt::buffer - an initialized buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
122 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
123 The size should be selected empirically for your application and hardware, there are no common rules for that.
124 Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
125 - \p opt::random_engine - a random engine to generate a random position in elimination array.
126 Default is \p opt::v::c_rand.
127 - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
128 - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin.
130 Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
132 typedef cds::container::TreiberStack< cds::gc::HP, Foo,
133 typename cds::container::treiber_stack::make_traits<
134 cds::opt::item_counter< cds::atomicity::item_counter >,
135 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
140 template <typename... Options>
142 # ifdef CDS_DOXYGEN_INVOKED
143 typedef implementation_defined type; ///< Metafunction result
145 typedef typename cds::opt::make_options<
146 typename cds::opt::find_type_traits< traits, Options... >::type
151 } // namespace treiber_stack
155 template <typename GC, typename T, typename Traits>
156 struct make_treiber_stack
159 typedef T value_type;
160 typedef Traits traits;
162 struct node_type: public cds::intrusive::treiber_stack::node< gc >
166 node_type( const value_type& val )
170 template <typename... Args>
171 node_type( Args&&... args )
172 : m_value( std::forward<Args>( args )... )
176 typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
177 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
179 struct node_deallocator
181 void operator ()( node_type * pNode )
183 cxx_allocator().Delete( pNode );
187 struct intrusive_traits: public traits
189 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
190 typedef node_deallocator disposer;
191 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;
194 // Result of metafunction
195 typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
197 } // namespace details
200 /// Treiber's stack algorithm
201 /** @ingroup cds_nonintrusive_stack
202 It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
203 intrusive::TreiberStack.
206 - \p GC - garbage collector type: \p gc::HP, gc::DHP
207 - \p T - type stored in the stack.
208 - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
209 metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
211 struct myTraits: public cds::container::treiber_stack::traits {
212 typedef cds::intrusive::treiber_stack::stat<> stat;
213 typedef cds::atomicity::item_counter item_counter;
215 typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
217 // Equivalent make_traits example:
218 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
219 typename cds::intrusive::treiber_stack::make_traits<
220 cds::opt::item_counter< cds::atomicity::item_counter >,
221 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
229 typename Traits = treiber_stack::traits
233 #ifdef CDS_DOXYGEN_INVOKED
234 intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
236 details::make_treiber_stack< GC, T, Traits >::type
240 typedef details::make_treiber_stack< GC, T, Traits > maker;
241 typedef typename maker::type base_class;
245 /// Rebind template arguments
246 template <typename GC2, typename T2, typename Traits2>
248 typedef TreiberStack< GC2, T2, Traits2 > other; ///< Rebinding result
252 typedef T value_type ; ///< Value type stored in the stack
253 typedef typename base_class::gc gc ; ///< Garbage collector used
254 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
255 typedef typename maker::allocator_type allocator_type ; ///< Allocator type used for allocating/deallocating the nodes
256 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_order option
257 typedef typename base_class::stat stat ; ///< Internal statistics policy used
260 typedef typename maker::node_type node_type ; ///< stack node type (derived from \p intrusive::treiber_stack::node)
263 typedef typename maker::cxx_allocator cxx_allocator;
264 typedef typename maker::node_deallocator node_deallocator;
269 static node_type * alloc_node( const value_type& val )
271 return cxx_allocator().New( val );
273 template <typename... Args>
274 static node_type * alloc_node_move( Args&&... args )
276 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
279 static void free_node( node_type * p )
281 node_deallocator()( p );
283 static void retire_node( node_type * p )
285 gc::template retire<typename base_class::disposer>( p );
288 struct node_disposer {
289 void operator()( node_type * pNode )
294 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
298 /// Constructs empty stack
302 /// Constructs empty stack and initializes elimination back-off data
304 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
305 \p Options... contains cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer >.
306 \p nCollisionCapacity parameter specifies the capacity of collision array.
308 TreiberStack( size_t nCollisionCapacity )
309 : base_class( nCollisionCapacity )
312 /// \p %TreiberStack is not copy-constructible
313 TreiberStack( TreiberStack const& ) = delete;
315 /// Clears the stack on destruction
319 /// Pushes copy of \p val on the stack
320 bool push( value_type const& val )
322 scoped_node_ptr p( alloc_node(val));
323 if ( base_class::push( *p )) {
330 /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
331 template <typename... Args>
332 bool emplace( Args&&... args )
334 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
335 if ( base_class::push( *p )) {
342 /// Pops an item from the stack
344 The value of popped item is stored in \p val using assignment operator.
345 On success functions returns \p true, \p val contains value popped from the stack.
346 If stack is empty the function returns \p false, \p val is unchanged.
348 bool pop( value_type& val )
350 return pop_with( [&val]( value_type& src ) { val = std::move(src); } );
353 /// Pops an item from the stack with functor
355 \p Func can be used to copy/move popped item from the stack.
356 \p Func interface is:
358 void func( value_type& src );
360 where \p src - item popped.
362 template <typename Func>
363 bool pop_with( Func f )
365 node_type * p = base_class::pop();
375 /// Check if stack is empty
378 return base_class::empty();
387 /// Returns stack's item count
389 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
390 this function always returns 0.
392 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
393 is empty. To check emptyness use \ref empty() method.
397 return base_class::size();
400 /// Returns reference to internal statistics
401 stat const& statistics() const
403 return base_class::statistics();
407 }} // namespace cds::container
409 #endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H