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     /// TreiberStack related definitions
  13     /** @ingroup cds_nonintrusive_helper
  14     */
  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 >;
  19
  20         /// Dummy internal statistics
  21         typedef cds::intrusive::treiber_stack::empty_stat empty_stat;
  22
  23         /// TreiberStack default type traits
  24         struct traits
  25         {
  26             /// Back-off strategy
  27             typedef cds::backoff::Default       back_off;
  28
  29             /// Node allocator
  30             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  31
  32             /// C++ memory ordering model
  33             /**
  34                 Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  35                 or opt::v::sequential_consistent (sequentially consisnent memory model).
  36             */
  37             typedef opt::v::relaxed_ordering    memory_model;
  38
  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;
  41
  42             /// Internal statistics (by default, no internal statistics)
  43             /**
  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.
  46             */
  47             typedef empty_stat stat;
  48
  49             /** @name Elimination back-off traits
  50                 The following traits is used only if elimination enabled
  51             */
  52             ///@{
  53
  54             /// Enable elimination back-off; by default, it is disabled
  55             static CDS_CONSTEXPR_CONST bool enable_elimination = false;
  56
  57             /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
  58             typedef cds::backoff::delay<>          elimination_backoff;
  59
  60             /// Buffer type for elimination array
  61             /**
  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>.
  66             */
  67             typedef opt::v::static_buffer< int, 4 > buffer;
  68
  69             /// Random engine to generate a random position in elimination array
  70             typedef opt::v::c_rand  random_engine;
  71
  72             /// Lock type used in elimination, default is cds::lock::Spin
  73             typedef cds::lock::Spin lock_type;
  74
  75             ///@}
  76         };
  77
  78         /// Metafunction converting option list to \p TreiberStack traits
  79         /**
  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.
  92
  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.
 102
 103             Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
 104             \code
 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<> >
 109                 >::type
 110             > myStack;
 111             \endcode
 112         */
 113         template <typename... Options>
 114         struct make_traits {
 115 #   ifdef CDS_DOXYGEN_INVOKED
 116             typedef implementation_defined type;   ///< Metafunction result
 117 #   else
 118             typedef typename cds::opt::make_options<
 119                 typename cds::opt::find_type_traits< traits, Options... >::type
 120                 , Options...
 121             >::type   type;
 122 #   endif
 123         };
 124     } // namespace treiber_stack
 125
 126     //@cond
 127     namespace details {
 128         template <typename GC, typename T, typename Traits>
 129         struct make_treiber_stack
 130         {
 131             typedef GC gc;
 132             typedef T       value_type;
 133             typedef Traits  traits;
 134
 135             struct node_type: public cds::intrusive::treiber_stack::node< gc >
 136             {
 137                 value_type  m_value;
 138
 139                 node_type( const value_type& val )
 140                     : m_value( val )
 141                 {}
 142
 143                 template <typename... Args>
 144                 node_type( Args&&... args )
 145                     : m_value( std::forward<Args>( args )... )
 146                 {}
 147             };
 148
 149             typedef typename traits::allocator::template rebind<node_type>::other  allocator_type;
 150             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
 151
 152             struct node_deallocator
 153             {
 154                 void operator ()( node_type * pNode )
 155                 {
 156                     cxx_allocator().Delete( pNode );
 157                 }
 158             };
 159
 160             struct intrusive_traits: public traits
 161             {
 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;
 165             };
 166
 167             // Result of metafunction
 168             typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
 169         };
 170     } // namespace details
 171     //@endcond
 172
 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.
 177
 178         Template arguments:
 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:
 183             \code
 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;
 187             };
 188             typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
 189
 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<> >
 195                 >::type
 196             > myStack;
 197             \endcode
 198     */
 199     template <
 200         typename GC,
 201         typename T,
 202         typename Traits = treiber_stack::traits
 203     >
 204     class TreiberStack
 205         : public
 206 #ifdef CDS_DOXYGEN_INVOKED
 207         intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
 208 #else
 209         details::make_treiber_stack< GC, T, Traits >::type
 210 #endif
 211     {
 212         //@cond
 213         typedef details::make_treiber_stack< GC, T, Traits > maker;
 214         typedef typename maker::type base_class;
 215         //@endcond
 216
 217     public:
 218         /// Rebind template arguments
 219         template <typename GC2, typename T2, typename Traits2>
 220         struct rebind {
 221             typedef TreiberStack< GC2, T2, Traits2 > other;   ///< Rebinding result
 222         };
 223
 224     public:
 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
 231
 232     protected:
 233         typedef typename maker::node_type  node_type   ;   ///< stack node type (derived from \p intrusive::treiber_stack::node)
 234
 235         //@cond
 236         typedef typename maker::cxx_allocator     cxx_allocator;
 237         typedef typename maker::node_deallocator  node_deallocator;
 238         //@endcond
 239
 240     protected:
 241         ///@cond
 242         static node_type * alloc_node( const value_type& val )
 243         {
 244             return cxx_allocator().New( val );
 245         }
 246         template <typename... Args>
 247         static node_type * alloc_node_move( Args&&... args )
 248         {
 249             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 250         }
 251
 252         static void free_node( node_type * p )
 253         {
 254             node_deallocator()( p );
 255         }
 256         static void retire_node( node_type * p )
 257         {
 258             gc::template retire<typename base_class::disposer>( p );
 259         }
 260
 261         struct node_disposer {
 262             void operator()( node_type * pNode )
 263             {
 264                 free_node( pNode );
 265             }
 266         };
 267         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 268         //@endcond
 269
 270     public:
 271         /// Constructs empty stack
 272         TreiberStack()
 273         {}
 274
 275         /// Constructs empty stack and initializes elimination back-off data
 276         /**
 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.
 280         */
 281         TreiberStack( size_t nCollisionCapacity )
 282             : base_class( nCollisionCapacity )
 283         {}
 284
 285         /// \p %TreiberStack is not copy-constructible
 286         TreiberStack( TreiberStack const& ) = delete;
 287
 288         /// Clears the stack on destruction
 289         ~TreiberStack()
 290         {}
 291
 292         /// Pushes copy of \p val on the stack
 293         bool push( value_type const& val )
 294         {
 295             scoped_node_ptr p( alloc_node(val));
 296             if ( base_class::push( *p )) {
 297                 p.release();
 298                 return true;
 299             }
 300             return false;
 301         }
 302
 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 )
 306         {
 307             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 308             if ( base_class::push( *p )) {
 309                 p.release();
 310                 return true;
 311             }
 312             return false;
 313         }
 314
 315         /// Pops an item from the stack
 316         /**
 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.
 320         */
 321         bool pop( value_type& val )
 322         {
 323             return pop_with( [&val]( value_type& src ) { val = src; } );
 324         }
 325
 326         /// Pops an item from the stack with functor
 327         /**
 328             \p Func interface is:
 329             \code
 330             void func( value_type& src );
 331             \endcond
 332             where \p src - item popped.
 333
 334             The \p %pop_with can be used to move item from the stack to user-provided storage:
 335             \code
 336             cds::container::TreiberStack<cds::gc::HP, std::string > myStack;
 337             //...
 338
 339             std::string dest;
 340             myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } );
 341             \endcode
 342         */
 343         template <typename Func>
 344         bool pop_with( Func f )
 345         {
 346             node_type * p = base_class::pop();
 347             if ( !p )
 348                 return false;
 349
 350             f( p->m_value );
 351             retire_node( p );
 352
 353             return true;
 354         }
 355
 356         /// Check if stack is empty
 357         bool empty() const
 358         {
 359             return base_class::empty();
 360         }
 361
 362         /// Clear the stack
 363         void clear()
 364         {
 365             base_class::clear();
 366         }
 367
 368         /// Returns stack's item count
 369         /**
 370             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 371             this function always returns 0.
 372
 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.
 375         */
 376         size_t    size() const
 377         {
 378             return base_class::size();
 379         }
 380
 381         /// Returns reference to internal statistics
 382         stat const& statistics() const
 383         {
 384             return base_class::statistics();
 385         }
 386     };
 387
 388 }}  // namespace cds::container
 389
 390 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H