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