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