cds/container/treiber_stack.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_TREIBER_STACK_H
   4 #define __CDS_CONTAINER_TREIBER_STACK_H
   5
   6 #include <memory>   // unique_ptr
   7 #include <cds/intrusive/treiber_stack.h>
   8 #include <cds/container/details/base.h>
   9
  10 namespace cds { namespace container {
  11
  12     namespace treiber_stack {
  13         /// Internal statistics
  14         template <typename Counter = cds::atomicity::event_counter>
  15         using stat = cds::intrusive::treiber_stack::stat < Counter >;
  16
  17         /// Dummy internal statistics
  18         typedef cds::intrusive::treiber_stack::empty_stat empty_stat;
  19
  20         /// TreiberStack default type traits
  21         struct traits
  22         {
  23             /// Back-off strategy
  24             typedef cds::backoff::Default       back_off;
  25
  26             /// Node allocator
  27             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  28
  29             /// C++ memory ordering model
  30             /**
  31                 Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  32                 or opt::v::sequential_consistent (sequentially consisnent memory model).
  33             */
  34             typedef opt::v::relaxed_ordering    memory_model;
  35
  36             /// Item counting feature; by default, disabled
  37             typedef cds::atomicity::empty_item_counter  item_counter;
  38
  39             /// Internal statistics (by default, no internal statistics)
  40             /**
  41                 Possible option value are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
  42                 user-provided class that supports treiber_stack::stat interface.
  43             */
  44             typedef empty_stat                          stat;
  45
  46             /** @name Elimination back-off traits
  47                 The following traits is used only if elimination enabled
  48             */
  49             ///@{
  50
  51             /// Enable elimination back-off; by default, it is disabled
  52             static CDS_CONSTEXPR_CONST bool enable_elimination = false;
  53
  54             /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
  55             typedef cds::backoff::delay<>          elimination_backoff;
  56
  57             /// Buffer type for elimination array
  58             /**
  59                 Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
  60                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
  61                 The size should be selected empirically for your application and hardware, there are no common rules for that.
  62                 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
  63             */
  64             typedef opt::v::static_buffer< int, 4 > buffer;
  65
  66             /// Random engine to generate a random position in elimination array
  67             typedef opt::v::c_rand  random_engine;
  68
  69             /// Lock type used in elimination, default is cds::lock::Spin
  70             typedef cds::lock::Spin lock_type;
  71
  72             ///@}
  73         };
  74
  75         /// Metafunction converting option list to \p TreiberStack traits
  76         /**
  77             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
  78             Supported \p Options are:
  79             - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
  80             - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
  81             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  82                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  83             - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter
  84             - opt::stat - the type to gather internal statistics.
  85                 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
  86                 user-provided class that supports \p treiber_stack::stat interface.
  87             - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
  88
  89             If elimination back-off is enabled, additional options can be specified:
  90             - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::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::static_buffer< any_type, 4 > </tt>.
  94             - opt::random_engine - a random engine to generate a random position in elimination array.
  95                 Default is \p opt::v::c_rand.
  96             - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
  97             - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin.
  98         */
  99         template <typename... Options>
 100         struct make_traits {
 101 #   ifdef CDS_DOXYGEN_INVOKED
 102             typedef implementation_defined type;   ///< Metafunction result
 103 #   else
 104             typedef typename cds::opt::make_options<
 105                 typename cds::opt::find_type_traits< traits, Options... >::type
 106                 , Options...
 107             >::type   type;
 108 #   endif
 109         };
 110     } // namespace treiber_stack
 111
 112     //@cond
 113     namespace details {
 114         template <typename GC, typename T, typename Traits>
 115         struct make_treiber_stack
 116         {
 117             typedef GC gc;
 118             typedef T       value_type;
 119             typedef Traits  traits;
 120
 121             struct node_type: public cds::intrusive::treiber_stack::node< gc >
 122             {
 123                 value_type  m_value;
 124
 125                 node_type( const value_type& val )
 126                     : m_value( val )
 127                 {}
 128
 129                 template <typename... Args>
 130                 node_type( Args&&... args )
 131                     : m_value( std::forward<Args>( args )... )
 132                 {}
 133             };
 134
 135             typedef typename traits::allocator::template rebind<node_type>::other  allocator_type;
 136             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
 137
 138             struct node_deallocator
 139             {
 140                 void operator ()( node_type * pNode )
 141                 {
 142                     cxx_allocator().Delete( pNode );
 143                 }
 144             };
 145
 146             struct intrusive_traits: public traits
 147             {
 148                 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
 149                 typedef node_deallocator disposer;
 150                 static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;
 151             };
 152
 153             // Result of metafunction
 154             typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
 155         };
 156     } // namespace details
 157     //@endecond
 158
 159     /// Treiber's stack algorithm
 160     /** @ingroup cds_nonintrusive_stack
 161         It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
 162         intrusive::TreiberStack.
 163
 164         Template arguments:
 165         - \p GC - garbage collector type: gc::HP, gc::PTB
 166         - \p T - type stored in the stack. It should be default-constructible, copy-constructible, assignable type.
 167         - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
 168             metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
 169             \code
 170             struct myTraits: public cds::container::treiber_stack::traits {
 171                 typedef cds::container::treiber_stack::stat<> stat;
 172             };
 173             typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
 174             \endcode
 175     */
 176     template <
 177         typename GC,
 178         typename T,
 179         typename Traits = treiber_stack::traits
 180     >
 181     class TreiberStack
 182         : public
 183 #ifdef CDS_DOXYGEN_INVOKED
 184         intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
 185 #else
 186         details::make_treiber_stack< GC, T, Traits >::type
 187 #endif
 188     {
 189         //@cond
 190         typedef details::make_treiber_stack< GC, T, Traits > maker;
 191         typedef typename maker::type base_class;
 192         //@endcond
 193
 194     public:
 195         /// Rebind template arguments
 196         template <typename GC2, typename T2, typename Traits2>
 197         struct rebind {
 198             typedef TreiberStack< GC2, T2, Traits2> other   ;   ///< Rebinding result
 199         };
 200
 201     public:
 202         typedef T value_type ; ///< Value type stored in the stack
 203         typedef typename base_class::gc gc                     ;   ///< Garbage collector used
 204         typedef typename base_class::back_off  back_off        ;   ///< Back-off strategy used
 205         typedef typename maker::allocator_type allocator_type  ;   ///< Allocator type used for allocating/deallocating the nodes
 206         typedef typename base_class::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_order option
 207         typedef typename base_class::stat       stat           ;   ///< Internal statistics policy used
 208
 209     protected:
 210         typedef typename maker::node_type  node_type   ;   ///< stack node type (derived from intrusive::treiber_stack::node)
 211
 212         //@cond
 213         typedef typename maker::cxx_allocator     cxx_allocator;
 214         typedef typename maker::node_deallocator  node_deallocator;
 215         //@endcond
 216
 217     protected:
 218         ///@cond
 219         static node_type * alloc_node( const value_type& val )
 220         {
 221             return cxx_allocator().New( val );
 222         }
 223         template <typename... Args>
 224         static node_type * alloc_node_move( Args&&... args )
 225         {
 226             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 227         }
 228
 229         static void free_node( node_type * p )
 230         {
 231             node_deallocator()( p );
 232         }
 233         static void retire_node( node_type * p )
 234         {
 235             gc::template retire<typename base_class::disposer>( p );
 236         }
 237
 238         struct node_disposer {
 239             void operator()( node_type * pNode )
 240             {
 241                 free_node( pNode );
 242             }
 243         };
 244         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 245         //@endcond
 246
 247     public:
 248         /// Constructs empty stack
 249         TreiberStack()
 250         {}
 251
 252         /// Constructs empty stack and initializes elimination back-off data
 253         /**
 254             This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
 255             \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
 256             \p nCollisionCapacity parameter specifies the capacity of collision array.
 257         */
 258         TreiberStack( size_t nCollisionCapacity )
 259             : base_class( nCollisionCapacity )
 260         {}
 261
 262         /// \p %TreiberStack is not copy-constructible
 263         TreiberStack( TreiberStack const& ) = delete;
 264
 265         /// Clears the stack on destruction
 266         ~TreiberStack()
 267         {}
 268
 269         /// Push the item \p val on the stack
 270         bool push( value_type const& val )
 271         {
 272             scoped_node_ptr p( alloc_node(val));
 273             if ( base_class::push( *p )) {
 274                 p.release();
 275                 return true;
 276             }
 277             return false;
 278         }
 279
 280         /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
 281         template <typename... Args>
 282         bool emplace( Args&&... args )
 283         {
 284             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 285             if ( base_class::push( *p )) {
 286                 p.release();
 287                 return true;
 288             }
 289             return false;
 290         }
 291
 292         /// Pop an item from the stack
 293         /**
 294             The value of popped item is stored in \p val.
 295             On success functions returns \p true, \p val contains value popped from the stack.
 296             If stack is empty the function returns \p false, \p val is unchanged.
 297         */
 298         bool pop( value_type& val )
 299         {
 300             node_type * p = base_class::pop();
 301             if ( !p )
 302                 return false;
 303
 304             val = p->m_value;
 305             retire_node( p );
 306
 307             return true;
 308         }
 309
 310         /// Check if stack is empty
 311         bool empty() const
 312         {
 313             return base_class::empty();
 314         }
 315
 316         /// Clear the stack
 317         void clear()
 318         {
 319             base_class::clear();
 320         }
 321
 322         /// Returns stack's item count
 323         /**
 324             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 325             this function always returns 0.
 326
 327             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
 328             is empty. To check emptyness use \ref empty() method.
 329         */
 330         size_t    size() const
 331         {
 332             return base_class::size();
 333         }
 334
 335         /// Returns reference to internal statistics
 336         stat const& statistics() const
 337         {
 338             return base_class::statistics();
 339         }
 340     };
 341
 342 }}  // namespace cds::container
 343
 344
 345 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H