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             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.
  91
  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::lock::Spin.
 101
 102             Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
 103             \code
 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<> >
 108                 >::type
 109             > myStack;
 110             \endcode
 111         */
 112         template <typename... Options>
 113         struct make_traits {
 114 #   ifdef CDS_DOXYGEN_INVOKED
 115             typedef implementation_defined type;   ///< Metafunction result
 116 #   else
 117             typedef typename cds::opt::make_options<
 118                 typename cds::opt::find_type_traits< traits, Options... >::type
 119                 , Options...
 120             >::type   type;
 121 #   endif
 122         };
 123     } // namespace treiber_stack
 124
 125     //@cond
 126     namespace details {
 127         template <typename GC, typename T, typename Traits>
 128         struct make_treiber_stack
 129         {
 130             typedef GC gc;
 131             typedef T       value_type;
 132             typedef Traits  traits;
 133
 134             struct node_type: public cds::intrusive::treiber_stack::node< gc >
 135             {
 136                 value_type  m_value;
 137
 138                 node_type( const value_type& val )
 139                     : m_value( val )
 140                 {}
 141
 142                 template <typename... Args>
 143                 node_type( Args&&... args )
 144                     : m_value( std::forward<Args>( args )... )
 145                 {}
 146             };
 147
 148             typedef typename traits::allocator::template rebind<node_type>::other  allocator_type;
 149             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
 150
 151             struct node_deallocator
 152             {
 153                 void operator ()( node_type * pNode )
 154                 {
 155                     cxx_allocator().Delete( pNode );
 156                 }
 157             };
 158
 159             struct intrusive_traits: public traits
 160             {
 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;
 164             };
 165
 166             // Result of metafunction
 167             typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
 168         };
 169     } // namespace details
 170     //@endcond
 171
 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.
 176
 177         Template arguments:
 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:
 182             \code
 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;
 186             };
 187             typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
 188
 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<> >
 194                 >::type
 195             > myStack;
 196             \endcode
 197     */
 198     template <
 199         typename GC,
 200         typename T,
 201         typename Traits = treiber_stack::traits
 202     >
 203     class TreiberStack
 204         : public
 205 #ifdef CDS_DOXYGEN_INVOKED
 206         intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
 207 #else
 208         details::make_treiber_stack< GC, T, Traits >::type
 209 #endif
 210     {
 211         //@cond
 212         typedef details::make_treiber_stack< GC, T, Traits > maker;
 213         typedef typename maker::type base_class;
 214         //@endcond
 215
 216     public:
 217         /// Rebind template arguments
 218         template <typename GC2, typename T2, typename Traits2>
 219         struct rebind {
 220             typedef TreiberStack< GC2, T2, Traits2 > other;   ///< Rebinding result
 221         };
 222
 223     public:
 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
 230
 231     protected:
 232         typedef typename maker::node_type  node_type   ;   ///< stack node type (derived from \p intrusive::treiber_stack::node)
 233
 234         //@cond
 235         typedef typename maker::cxx_allocator     cxx_allocator;
 236         typedef typename maker::node_deallocator  node_deallocator;
 237         //@endcond
 238
 239     protected:
 240         ///@cond
 241         static node_type * alloc_node( const value_type& val )
 242         {
 243             return cxx_allocator().New( val );
 244         }
 245         template <typename... Args>
 246         static node_type * alloc_node_move( Args&&... args )
 247         {
 248             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 249         }
 250
 251         static void free_node( node_type * p )
 252         {
 253             node_deallocator()( p );
 254         }
 255         static void retire_node( node_type * p )
 256         {
 257             gc::template retire<typename base_class::disposer>( p );
 258         }
 259
 260         struct node_disposer {
 261             void operator()( node_type * pNode )
 262             {
 263                 free_node( pNode );
 264             }
 265         };
 266         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 267         //@endcond
 268
 269     public:
 270         /// Constructs empty stack
 271         TreiberStack()
 272         {}
 273
 274         /// Constructs empty stack and initializes elimination back-off data
 275         /**
 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.
 279         */
 280         TreiberStack( size_t nCollisionCapacity )
 281             : base_class( nCollisionCapacity )
 282         {}
 283
 284         /// \p %TreiberStack is not copy-constructible
 285         TreiberStack( TreiberStack const& ) = delete;
 286
 287         /// Clears the stack on destruction
 288         ~TreiberStack()
 289         {}
 290
 291         /// Pushes copy of \p val on the stack
 292         bool push( value_type const& val )
 293         {
 294             scoped_node_ptr p( alloc_node(val));
 295             if ( base_class::push( *p )) {
 296                 p.release();
 297                 return true;
 298             }
 299             return false;
 300         }
 301
 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 )
 305         {
 306             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 307             if ( base_class::push( *p )) {
 308                 p.release();
 309                 return true;
 310             }
 311             return false;
 312         }
 313
 314         /// Pops an item from the stack
 315         /**
 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.
 319         */
 320         bool pop( value_type& val )
 321         {
 322             return pop_with( [&val]( value_type& src ) { val = src; } );
 323         }
 324
 325         /// Pops an item from the stack with functor
 326         /**
 327             \p Func interface is:
 328             \code
 329             void func( value_type& src );
 330             \endcond
 331             where \p src - item popped.
 332
 333             The \p %pop_with can be used to move item from the stack to user-provided storage:
 334             \code
 335             cds::container::TreiberStack<cds::gc::HP, std::string > myStack;
 336             //...
 337
 338             std::string dest;
 339             myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } );
 340             \endcode
 341         */
 342         template <typename Func>
 343         bool pop_with( Func f )
 344         {
 345             node_type * p = base_class::pop();
 346             if ( !p )
 347                 return false;
 348
 349             f( p->m_value );
 350             retire_node( p );
 351
 352             return true;
 353         }
 354
 355         /// Check if stack is empty
 356         bool empty() const
 357         {
 358             return base_class::empty();
 359         }
 360
 361         /// Clear the stack
 362         void clear()
 363         {
 364             base_class::clear();
 365         }
 366
 367         /// Returns stack's item count
 368         /**
 369             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 370             this function always returns 0.
 371
 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.
 374         */
 375         size_t    size() const
 376         {
 377             return base_class::size();
 378         }
 379
 380         /// Returns reference to internal statistics
 381         stat const& statistics() const
 382         {
 383             return base_class::statistics();
 384         }
 385     };
 386
 387 }}  // namespace cds::container
 388
 389 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H