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/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, CDS_DECL_OPTIONS11>
  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, CDS_OPTIONS11 >::type
  39                 ,CDS_OPTIONS11
  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::HRC, 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, CDS_DECL_OPTIONS11 >
 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, CDS_OPTIONS11 >::type
 129 #endif
 130     {
 131         //@cond
 132         typedef treiber_stack::make_treiber_stack< GC, T, CDS_OPTIONS11 > options;
 133         typedef typename options::type base_class;
 134         //@endcond
 135
 136     public:
 137         /// Rebind template arguments
 138         template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS11>
 139         struct rebind {
 140             typedef TreiberStack< GC2, T2, CDS_OTHER_OPTIONS11> 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         /// Clears the stack on destruction
 205         ~TreiberStack()
 206         {}
 207
 208         /// Push the item \p val on the stack
 209         bool push( const value_type& val )
 210         {
 211             scoped_node_ptr p( alloc_node(val));
 212             if ( base_class::push( *p )) {
 213                 p.release();
 214                 return true;
 215             }
 216             return false;
 217         }
 218
 219         /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
 220         template <typename... Args>
 221         bool emplace( Args&&... args )
 222         {
 223             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 224             if ( base_class::push( *p )) {
 225                 p.release();
 226                 return true;
 227             }
 228             return false;
 229         }
 230
 231         /// Pop an item from the stack
 232         /**
 233             The value of popped item is stored in \p val.
 234             On success functions returns \p true, \p val contains value popped from the stack.
 235             If stack is empty the function returns \p false, \p val is unchanged.
 236         */
 237         bool pop( value_type& val )
 238         {
 239             node_type * p = base_class::pop();
 240             if ( !p )
 241                 return false;
 242
 243             val = p->m_value;
 244             retire_node( p );
 245
 246             return true;
 247         }
 248
 249         /// Check if stack is empty
 250         bool empty() const
 251         {
 252             return base_class::empty();
 253         }
 254
 255         /// Clear the stack
 256         void clear()
 257         {
 258             base_class::clear();
 259         }
 260
 261         /// Returns stack's item count
 262         /**
 263             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 264             this function always returns 0.
 265
 266             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
 267             is empty. To check emptyness use \ref empty() method.
 268         */
 269         size_t    size() const
 270         {
 271             return base_class::size();
 272         }
 273
 274         /// Returns reference to internal statistics
 275         stat const& statistics() const
 276         {
 277             return base_class::statistics();
 278         }
 279     };
 280
 281 }}  // namespace cds::container
 282
 283
 284 #endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H