cds/container/treiber_stack.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H
  32 #define CDSLIB_CONTAINER_TREIBER_STACK_H
  33
  34 #include <memory>   // unique_ptr
  35 #include <cds/intrusive/treiber_stack.h>
  36 #include <cds/container/details/base.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// TreiberStack related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace treiber_stack {
  44         /// Internal statistics
  45         template <typename Counter = cds::intrusive::treiber_stack::stat<>::counter_type >
  46         using stat = cds::intrusive::treiber_stack::stat< Counter >;
  47
  48         /// Dummy internal statistics
  49         typedef cds::intrusive::treiber_stack::empty_stat empty_stat;
  50
  51         /// TreiberStack default type traits
  52         struct traits
  53         {
  54             /// Back-off strategy
  55             typedef cds::backoff::Default       back_off;
  56
  57             /// Node allocator
  58             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  59
  60             /// C++ memory ordering model
  61             /**
  62                 Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  63                 or opt::v::sequential_consistent (sequentially consisnent memory model).
  64             */
  65             typedef opt::v::relaxed_ordering    memory_model;
  66
  67             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  68             typedef cds::atomicity::empty_item_counter  item_counter;
  69
  70             /// Internal statistics (by default, no internal statistics)
  71             /**
  72                 Possible types are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
  73                 user-provided class that supports treiber_stack::stat interface.
  74             */
  75             typedef empty_stat stat;
  76
  77             /** @name Elimination back-off traits
  78                 The following traits is used only if elimination enabled
  79             */
  80             ///@{
  81
  82             /// Enable elimination back-off; by default, it is disabled
  83             static CDS_CONSTEXPR const bool enable_elimination = false;
  84
  85             /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
  86             typedef cds::backoff::delay<>          elimination_backoff;
  87
  88             /// Buffer type for elimination array
  89             /**
  90                 Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
  91                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
  92                 The size should be selected empirically for your application and hardware, there are no common rules for that.
  93                 Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
  94             */
  95             typedef opt::v::initialized_static_buffer< int, 4 > buffer;
  96
  97             /// Random engine to generate a random position in elimination array
  98             typedef opt::v::c_rand  random_engine;
  99
 100             /// Lock type used in elimination, default is cds::sync::spin
 101             typedef cds::sync::spin lock_type;
 102
 103             ///@}
 104         };
 105
 106         /// Metafunction converting option list to \p TreiberStack traits
 107         /**
 108             Supported \p Options are:
 109             - \p opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
 110             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 111             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 112                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 113             - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
 114                 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
 115             - \p opt::stat - the type to gather internal statistics.
 116                 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
 117                 user-provided class that supports \p %treiber_stack::stat interface.
 118             - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
 119
 120             If elimination back-off is enabled, additional options can be specified:
 121             - \p opt::buffer - an initialized buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
 122                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
 123                 The size should be selected empirically for your application and hardware, there are no common rules for that.
 124                 Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
 125             - \p opt::random_engine - a random engine to generate a random position in elimination array.
 126                 Default is \p opt::v::c_rand.
 127             - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
 128             - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin.
 129
 130             Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
 131             \code
 132             typedef cds::container::TreiberStack< cds::gc::HP, Foo,
 133                 typename cds::container::treiber_stack::make_traits<
 134                     cds::opt::item_counter< cds::atomicity::item_counter >,
 135                     cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
 136                 >::type
 137             > myStack;
 138             \endcode
 139         */
 140         template <typename... Options>
 141         struct make_traits {
 142 #   ifdef CDS_DOXYGEN_INVOKED
 143             typedef implementation_defined type;   ///< Metafunction result
 144 #   else
 145             typedef typename cds::opt::make_options<
 146                 typename cds::opt::find_type_traits< traits, Options... >::type
 147                 , Options...
 148             >::type   type;
 149 #   endif
 150         };
 151     } // namespace treiber_stack
 152
 153     //@cond
 154     namespace details {
 155         template <typename GC, typename T, typename Traits>
 156         struct make_treiber_stack
 157         {
 158             typedef GC gc;
 159             typedef T       value_type;
 160             typedef Traits  traits;
 161
 162             struct node_type: public cds::intrusive::treiber_stack::node< gc >
 163             {
 164                 value_type  m_value;
 165
 166                 node_type( const value_type& val )
 167                     : m_value( val )
 168                 {}
 169
 170                 template <typename... Args>
 171                 node_type( Args&&... args )
 172                     : m_value( std::forward<Args>( args )... )
 173                 {}
 174             };
 175
 176             typedef typename traits::allocator::template rebind<node_type>::other  allocator_type;
 177             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
 178
 179             struct node_deallocator
 180             {
 181                 void operator ()( node_type * pNode )
 182                 {
 183                     cxx_allocator().Delete( pNode );
 184                 }
 185             };
 186
 187             struct intrusive_traits: public traits
 188             {
 189                 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
 190                 typedef node_deallocator disposer;
 191                 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;
 192             };
 193
 194             // Result of metafunction
 195             typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
 196         };
 197     } // namespace details
 198     //@endcond
 199
 200     /// Treiber's stack algorithm
 201     /** @ingroup cds_nonintrusive_stack
 202         It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation
 203         intrusive::TreiberStack.
 204
 205         Template arguments:
 206         - \p GC - garbage collector type: \p gc::HP, gc::DHP
 207         - \p T - type stored in the stack.
 208         - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
 209             metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
 210             \code
 211             struct myTraits: public cds::container::treiber_stack::traits {
 212                 typedef cds::intrusive::treiber_stack::stat<> stat;
 213                 typedef cds::atomicity::item_counter  item_counter;
 214             };
 215             typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
 216
 217             // Equivalent make_traits example:
 218             typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
 219                 typename cds::intrusive::treiber_stack::make_traits<
 220                     cds::opt::item_counter< cds::atomicity::item_counter >,
 221                     cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
 222                 >::type
 223             > myStack;
 224             \endcode
 225     */
 226     template <
 227         typename GC,
 228         typename T,
 229         typename Traits = treiber_stack::traits
 230     >
 231     class TreiberStack
 232         : public
 233 #ifdef CDS_DOXYGEN_INVOKED
 234         intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
 235 #else
 236         details::make_treiber_stack< GC, T, Traits >::type
 237 #endif
 238     {
 239         //@cond
 240         typedef details::make_treiber_stack< GC, T, Traits > maker;
 241         typedef typename maker::type base_class;
 242         //@endcond
 243
 244     public:
 245         /// Rebind template arguments
 246         template <typename GC2, typename T2, typename Traits2>
 247         struct rebind {
 248             typedef TreiberStack< GC2, T2, Traits2 > other;   ///< Rebinding result
 249         };
 250
 251     public:
 252         typedef T value_type ; ///< Value type stored in the stack
 253         typedef typename base_class::gc gc                     ;   ///< Garbage collector used
 254         typedef typename base_class::back_off  back_off        ;   ///< Back-off strategy used
 255         typedef typename maker::allocator_type allocator_type  ;   ///< Allocator type used for allocating/deallocating the nodes
 256         typedef typename base_class::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_order option
 257         typedef typename base_class::stat       stat           ;   ///< Internal statistics policy used
 258
 259     protected:
 260         typedef typename maker::node_type  node_type   ;   ///< stack node type (derived from \p intrusive::treiber_stack::node)
 261
 262         //@cond
 263         typedef typename maker::cxx_allocator     cxx_allocator;
 264         typedef typename maker::node_deallocator  node_deallocator;
 265         //@endcond
 266
 267     protected:
 268         ///@cond
 269         static node_type * alloc_node( const value_type& val )
 270         {
 271             return cxx_allocator().New( val );
 272         }
 273         template <typename... Args>
 274         static node_type * alloc_node_move( Args&&... args )
 275         {
 276             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 277         }
 278
 279         static void free_node( node_type * p )
 280         {
 281             node_deallocator()( p );
 282         }
 283         static void retire_node( node_type * p )
 284         {
 285             gc::template retire<typename base_class::disposer>( p );
 286         }
 287
 288         struct node_disposer {
 289             void operator()( node_type * pNode )
 290             {
 291                 free_node( pNode );
 292             }
 293         };
 294         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 295         //@endcond
 296
 297     public:
 298         /// Constructs empty stack
 299         TreiberStack()
 300         {}
 301
 302         /// Constructs empty stack and initializes elimination back-off data
 303         /**
 304             This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
 305             \p Options... contains cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer >.
 306             \p nCollisionCapacity parameter specifies the capacity of collision array.
 307         */
 308         TreiberStack( size_t nCollisionCapacity )
 309             : base_class( nCollisionCapacity )
 310         {}
 311
 312         /// \p %TreiberStack is not copy-constructible
 313         TreiberStack( TreiberStack const& ) = delete;
 314
 315         /// Clears the stack on destruction
 316         ~TreiberStack()
 317         {}
 318
 319         /// Pushes copy of \p val on the stack
 320         bool push( value_type const& val )
 321         {
 322             scoped_node_ptr p( alloc_node(val));
 323             if ( base_class::push( *p )) {
 324                 p.release();
 325                 return true;
 326             }
 327             return false;
 328         }
 329
 330         /// Pushes data of type \ref value_type created from <tt>std::forward<Args>(args)...</tt>
 331         template <typename... Args>
 332         bool emplace( Args&&... args )
 333         {
 334             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 335             if ( base_class::push( *p )) {
 336                 p.release();
 337                 return true;
 338             }
 339             return false;
 340         }
 341
 342         /// Pops an item from the stack
 343         /**
 344             The value of popped item is stored in \p val using assignment operator.
 345             On success functions returns \p true, \p val contains value popped from the stack.
 346             If stack is empty the function returns \p false, \p val is unchanged.
 347         */
 348         bool pop( value_type& val )
 349         {
 350             return pop_with( [&val]( value_type& src ) { val = std::move(src); } );
 351         }
 352
 353         /// Pops an item from the stack with functor
 354         /**
 355             \p Func can be used to copy/move popped item from the stack.
 356             \p Func interface is:
 357             \code
 358             void func( value_type& src );
 359             \endcode
 360             where \p src - item popped.
 361         */
 362         template <typename Func>
 363         bool pop_with( Func f )
 364         {
 365             node_type * p = base_class::pop();
 366             if ( !p )
 367                 return false;
 368
 369             f( p->m_value );
 370             retire_node( p );
 371
 372             return true;
 373         }
 374
 375         /// Check if stack is empty
 376         bool empty() const
 377         {
 378             return base_class::empty();
 379         }
 380
 381         /// Clear the stack
 382         void clear()
 383         {
 384             base_class::clear();
 385         }
 386
 387         /// Returns stack's item count
 388         /**
 389             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 390             this function always returns 0.
 391
 392             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
 393             is empty. To check emptyness use \ref empty() method.
 394         */
 395         size_t    size() const
 396         {
 397             return base_class::size();
 398         }
 399
 400         /// Returns reference to internal statistics
 401         stat const& statistics() const
 402         {
 403             return base_class::statistics();
 404         }
 405     };
 406
 407 }}  // namespace cds::container
 408
 409 #endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H