cds/intrusive/treiber_stack.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
   4 #define __CDS_INTRUSIVE_TREIBER_STACK_H
   5
   6 #include <type_traits>
   7 #include <functional>   // ref
   8 #include <mutex>        // unique_lock
   9 #include <cds/intrusive/details/single_link_struct.h>
  10 #include <cds/algo/elimination.h>
  11 #include <cds/opt/buffer.h>
  12 #include <cds/lock/spinlock.h>
  13 #include <cds/details/type_padding.h>
  14
  15 namespace cds { namespace intrusive {
  16
  17     /// TreiberStack related definitions
  18     /** @ingroup cds_intrusive_helper
  19     */
  20     namespace treiber_stack {
  21
  22         /// Stack node
  23         /**
  24             Template parameters:
  25             - GC - garbage collector used
  26             - Tag - a tag used to distinguish between different type
  27         */
  28         template <class GC, typename Tag = opt::none >
  29         using node = cds::intrusive::single_link::node< GC, Tag > ;
  30
  31         /// Base hook
  32         /**
  33             \p Options are:
  34             - opt::gc - garbage collector used.
  35             - opt::tag - tag
  36         */
  37         template < typename... Options >
  38         using base_hook = cds::intrusive::single_link::base_hook< Options...>;
  39
  40         /// Member hook
  41         /**
  42             \p MemberOffset specifies offset in bytes of \ref node member into your structure.
  43             Use \p offsetof macro to define \p MemberOffset
  44
  45             \p Options are:
  46             - opt::gc - garbage collector used.
  47             - opt::tag - tag
  48         */
  49         template < size_t MemberOffset, typename... Options >
  50         using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
  51
  52         /// Traits hook
  53         /**
  54             \p NodeTraits defines type traits for node.
  55             See \ref node_traits for \p NodeTraits interface description
  56
  57             \p Options are:
  58             - opt::gc - garbage collector used.
  59             - opt::tag - tag
  60         */
  61         template <typename NodeTraits, typename... Options >
  62         using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
  63
  64         //@cond
  65         /// Operation id for the \ref cds_elimination_description "elimination back-off"
  66         enum operation_id {
  67             op_push,    ///< push op id
  68             op_pop      ///< pop op id
  69         };
  70
  71         /// Operation descriptor for the \ref cds_elimination_description "elimination back-off"
  72         template <typename T>
  73         struct operation: public cds::algo::elimination::operation_desc
  74         {
  75             operation_id    idOp;   ///< Op id
  76             T *             pVal;   ///< for push: pointer to argument; for pop: accepts a return value
  77             atomics::atomic<unsigned int> nStatus; ///< Internal elimination status
  78
  79             operation()
  80                 : pVal( nullptr )
  81                 , nStatus(0)
  82             {}
  83         };
  84         //@endcond
  85
  86         /// Stack internal statistics. May be useful for debugging or profiling
  87         /**
  88             Template argument \p Counter defines type of counter.
  89             Default is cds::atomicity::event_counter.
  90             You may use stronger type of counter like as cds::atomicity::item_counter,
  91             or even an integral type, for example, \p int
  92         */
  93         template <typename Counter = cds::atomicity::event_counter >
  94         struct stat
  95         {
  96             typedef Counter     counter_type    ;   ///< Counter type
  97
  98             counter_type m_PushCount        ;  ///< Push call count
  99             counter_type m_PopCount         ;  ///< Pop call count
 100             counter_type m_PushRace         ;  ///< Count of push race conditions encountered
 101             counter_type m_PopRace          ;  ///< Count of pop race conditions encountered
 102             counter_type m_ActivePushCollision  ; ///< Count of active push collision for elimination back-off
 103             counter_type m_ActivePopCollision   ; ///< Count of active pop collision for elimination back-off
 104             counter_type m_PassivePushCollision ; ///< Count of passive push collision for elimination back-off
 105             counter_type m_PassivePopCollision  ; ///< Count of passive pop collision for elimination back-off
 106             counter_type m_EliminationFailed    ; ///< Count of unsuccessful elimination back-off
 107
 108             //@cond
 109             void onPush()               { ++m_PushCount; }
 110             void onPop()                { ++m_PopCount; }
 111             void onPushRace()           { ++m_PushRace; }
 112             void onPopRace()            { ++m_PopRace; }
 113             void onActiveCollision( operation_id opId )
 114             {
 115                 if ( opId == treiber_stack::op_push )
 116                     ++m_ActivePushCollision;
 117                 else
 118                     ++m_ActivePopCollision;
 119             }
 120             void onPassiveCollision( operation_id opId )
 121             {
 122                 if ( opId == treiber_stack::op_push )
 123                     ++m_PassivePushCollision;
 124                 else
 125                     ++m_PassivePopCollision;
 126             }
 127             void onEliminationFailed()          { ++m_EliminationFailed;}
 128             //@endcond
 129         };
 130
 131         /// Empty (no overhead) stack statistics. Support interface like treiber_stack::stat
 132         struct empty_stat
 133         {
 134             //@cond
 135             void onPush()       {}
 136             void onPop()        {}
 137             void onPushRace()   {}
 138             void onPopRace()    {}
 139             void onActiveCollision( operation_id )  {}
 140             void onPassiveCollision( operation_id ) {}
 141             void onEliminationFailed() {}
 142             //@endcond
 143         };
 144
 145         /// TreiberStack default type traits
 146         struct traits
 147         {
 148             /// Back-off strategy
 149             typedef cds::backoff::Default           back_off;
 150
 151             /// Hook, possible types are treiber_stack::base_hook, treiber_stack::member_hook, treiber_stack::traits_hook
 152             typedef treiber_stack::base_hook<>      hook;
 153
 154             /// The functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used only in \ref TreiberStack::clear function
 155             typedef opt::v::empty_disposer          disposer;
 156
 157             /// Item counting feature; by default, disabled
 158             typedef cds::atomicity::empty_item_counter   item_counter;
 159
 160             /// C++ memory ordering model
 161             /**
 162                 Can be opt::v::relaxed_ordering (relaxed memory model, the default)
 163                 or opt::v::sequential_consistent (sequentially consisnent memory model).
 164             */
 165             typedef opt::v::relaxed_ordering        memory_model;
 166
 167             /// Internal statistics (by default, no internal statistics)
 168             /**
 169                 Possible option value are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
 170                 user-provided class that supports treiber_stack::stat interface.
 171             */
 172             typedef treiber_stack::empty_stat       stat;
 173
 174             /// Link checking, see cds::opt::link_checker
 175             static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = opt::debug_check_link;
 176
 177             /** @name Elimination back-off traits
 178                 The following traits is used only if elimination enabled
 179             */
 180             ///@{
 181
 182             /// Enable elimination back-off; by default, it is disabled
 183             static CDS_CONSTEXPR_CONST bool enable_elimination = false;
 184
 185             /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
 186             typedef cds::backoff::delay<>          elimination_backoff;
 187
 188             /// Buffer type for elimination array
 189             /**
 190                 Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
 191                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
 192                 The size should be selected empirically for your application and hardware, there are no common rules for that.
 193                 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
 194             */
 195             typedef opt::v::static_buffer< int, 4 > buffer;
 196
 197             /// Random engine to generate a random position in elimination array
 198             typedef opt::v::c_rand  random_engine;
 199
 200             /// Lock type used in elimination, default is cds::lock::Spin
 201             typedef cds::lock::Spin lock_type;
 202
 203             ///@}
 204         };
 205
 206         /// Metafunction converting option list to \p TreiberStack traits
 207         /**
 208             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 209             Supported \p Options are:
 210
 211             - opt::hook - hook used. Possible values are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
 212                 If the option is not specified, \p %treiber_stack::base_hook<> is used.
 213             - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 214             - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
 215                 in \p TreiberStack::clear function.
 216             - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
 217             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 218                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 219             - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter
 220             - opt::stat - the type to gather internal statistics.
 221                 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
 222                 user-provided class that supports \p treiber_stack::stat interface.
 223             - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
 224
 225             If elimination back-off is enabled, additional options can be specified:
 226             - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
 227                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
 228                 The size should be selected empirically for your application and hardware, there are no common rules for that.
 229                 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
 230             - opt::random_engine - a random engine to generate a random position in elimination array.
 231                 Default is \p opt::v::c_rand.
 232             - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
 233             - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin.
 234         */
 235         template <typename... Options>
 236         struct make_traits {
 237 #   ifdef CDS_DOXYGEN_INVOKED
 238             typedef implementation_defined type;   ///< Metafunction result
 239 #   else
 240             typedef typename cds::opt::make_options<
 241                 typename cds::opt::find_type_traits< traits, Options... >::type
 242                 , Options...
 243             >::type   type;
 244 #   endif
 245         };
 246
 247
 248         //@cond
 249         namespace details {
 250
 251             template <bool EnableElimination, typename T, typename Traits>
 252             class elimination_backoff;
 253
 254             template <typename T, typename Traits>
 255             class elimination_backoff<false, T, Traits>
 256             {
 257                 typedef typename Traits::back_off   back_off;
 258
 259                 back_off    m_bkoff;
 260             public:
 261                 elimination_backoff()
 262                 {}
 263
 264                 elimination_backoff( size_t )
 265                 {}
 266
 267                 void reset()
 268                 {
 269                     m_bkoff.reset();
 270                 }
 271
 272                 template <typename Stat>
 273                 bool backoff(treiber_stack::operation< T >&, Stat& )
 274                 {
 275                     m_bkoff();
 276                     return false;
 277                 }
 278             };
 279
 280             template <typename T, typename Traits>
 281             class elimination_backoff<true, T, Traits>
 282             {
 283                 typedef typename Traits::back_off   back_off;
 284
 285                 /// Back-off for elimination (usually delay)
 286                 typedef typename Traits::elimination_backoff elimination_backoff_type;
 287                 /// Lock type used in elimination back-off
 288                 typedef typename Traits::lock_type elimination_lock_type;
 289                 /// Random engine used in elimination back-off
 290                 typedef typename Traits::random_engine elimination_random_engine;
 291
 292                 /// Per-thread elimination record
 293                 typedef cds::algo::elimination::record  elimination_rec;
 294
 295                 /// Collision array record
 296                 struct collision_array_record {
 297                     elimination_rec *     pRec;
 298                     elimination_lock_type lock;
 299                 };
 300
 301                 /// Collision array used in elimination-backoff; each item is optimized for cache-line size
 302                 typedef typename Traits::buffer::template rebind<
 303                     typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
 304                 >::other collision_array;
 305
 306                 /// Operation descriptor used in elimination back-off
 307                 typedef treiber_stack::operation< T >  operation_desc;
 308
 309                 /// Elimination back-off data
 310                 struct elimination_data {
 311                     elimination_random_engine   randEngine; ///< random engine
 312                     collision_array             collisions; ///< collision array
 313
 314                     elimination_data()
 315                     {
 316                         //TODO: check Traits::buffer must be static!
 317                     }
 318                     elimination_data( size_t nCollisionCapacity )
 319                         : collisions( nCollisionCapacity )
 320                     {}
 321                 };
 322
 323                 elimination_data m_Elimination;
 324
 325                 enum operation_status {
 326                     op_free = 0,
 327                     op_busy = 1,
 328                     op_collided = 2
 329                 };
 330
 331                 typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
 332
 333             public:
 334                 elimination_backoff()
 335                 {
 336                     m_Elimination.collisions.zeroize();
 337                 }
 338
 339                 elimination_backoff( size_t nCollisionCapacity )
 340                     : m_Elimination( nCollisionCapacity )
 341                 {
 342                     m_Elimination.collisions.zeroize();
 343                 }
 344
 345                 void reset()
 346                 {}
 347
 348                 template <typename Stat>
 349                 bool backoff( operation_desc& op, Stat& stat )
 350                 {
 351                     elimination_backoff_type bkoff;
 352                     op.nStatus.store( op_busy, atomics::memory_order_relaxed );
 353
 354                     elimination_rec * myRec = cds::algo::elimination::init_record( op );
 355
 356                     collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
 357                     {
 358                         slot.lock.lock();
 359                         elimination_rec * himRec = slot.pRec;
 360                         if ( himRec ) {
 361                             operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
 362                             assert( himOp );
 363                             if ( himOp->idOp != op.idOp ) {
 364                                 if ( op.idOp == treiber_stack::op_push )
 365                                     himOp->pVal = op.pVal;
 366                                 else
 367                                     op.pVal = himOp->pVal;
 368                                 slot.pRec = nullptr;
 369                                 slot.lock.unlock();
 370
 371                                 himOp->nStatus.store( op_collided, atomics::memory_order_release );
 372                                 cds::algo::elimination::clear_record();
 373                                 stat.onActiveCollision( op.idOp );
 374                                 return true;
 375                             }
 376                             himOp->nStatus.store( op_free, atomics::memory_order_release );
 377                         }
 378                         slot.pRec = myRec;
 379                         slot.lock.unlock();
 380                     }
 381
 382                     // Wait for colliding operation
 383                     bkoff( [&op]() -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
 384                     {
 385                         slot_scoped_lock l( slot.lock );
 386                         if ( slot.pRec == myRec )
 387                             slot.pRec = nullptr;
 388                     }
 389
 390                     bool bCollided = op.nStatus.load( atomics::memory_order_acquire ) == op_collided;
 391
 392                     if ( !bCollided )
 393                         stat.onEliminationFailed();
 394                     else
 395                         stat.onPassiveCollision( op.idOp );
 396
 397                     cds::algo::elimination::clear_record();
 398                     return bCollided;
 399                 }
 400             };
 401
 402         } // namespace details
 403         //@endcond
 404     } // namespace treiber_stack
 405
 406     /// Treiber stack
 407     /** @ingroup cds_intrusive_stack
 408         Intrusive implementation of well-known Treiber's stack algorithm:
 409         - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
 410
 411         \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
 412         The idea of elimination algorithm is taken from:
 413         - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
 414
 415         The elimination algorithm uses a single elimination array as a back-off schema
 416         on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
 417         on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
 418
 419         @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
 420         The main difficulty is the managing life-time of elimination record.
 421         Our implementation uses simplified lock-based (spin-based) approach which allows
 422         the elimination record allocation on thread's stack.
 423         This approach demonstrates sufficient performance under high load.
 424
 425         Template arguments:
 426         - \p GC - garbage collector type: gc::HP, gc::PTB.
 427             Garbage collecting schema must be consistent with the treiber_stack::node GC.
 428         - \p T - type to be inserted into the stack
 429         - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
 430             metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
 431             \code
 432             struct myTraits: public cds::intrusive::treiber_stack::traits {
 433                 typedef cds::intrusive::treiber_stack::stat<> stat;
 434             };
 435             typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
 436             \endcode
 437
 438         @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
 439
 440         @anchor cds_intrusive_TreiberStack_examples
 441         \par Examples
 442
 443         Example of how to use \p treiber_stack::base_hook.
 444         Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class
 445         \code
 446         #include <cds/intrusive/stack/treiber_stack.h>
 447         #include <cds/gc/hp.h>
 448
 449         namespace ci = cds::intrusive;
 450         typedef cds::gc::HP gc;
 451
 452         struct myData: public ci::treiber_stack::node< gc >
 453         {
 454             // ...
 455         };
 456
 457         // Stack type
 458         typedef ci::TreiberStack< gc,
 459             myData,
 460             ci::opt::hook< ci::treiber_stack::base_hook< gc > >
 461         > stack_t;
 462
 463         // Stack with elimination back-off enabled
 464         typedef ci::TreiberStack< gc,
 465             myData,
 466             typename ci::treiber_stack::make_traits<
 467                 ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
 468                 cds::opt::enable_elimination< true >
 469             >::type
 470         > elimination_stack_t;
 471         \endcode
 472
 473         Example of how to use \p treiber_stack::base_hook with different tags.
 474         \code
 475         #include <cds/intrusive/stack/treiber_stack.h>
 476         #include <cds/gc/hp.h>
 477
 478         namespace ci = cds::intrusive;
 479         typedef cds::gc::HP gc;
 480
 481         // It is not necessary to declare complete type for tags
 482         struct tag1;
 483         struct tag2;
 484
 485         struct myData
 486             : public ci::treiber_stack::node< gc, tag1 >
 487             , public ci::treiber_stack::node< gc, tag2 >
 488         {
 489             // ...
 490         };
 491
 492         typedef ci::TreiberStack< gc,
 493             myData,
 494             typename ci::treiber_stack::make_traits<
 495                 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
 496             >::type
 497         > stack1_t;
 498
 499         typedef ci::TreiberStack< gc,
 500             myData,
 501             typename ci::treiber_stack::make_traits<
 502                 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 >
 503             >::type
 504         > stack2_t;
 505
 506         // You may add myData objects in the objects of type stack1_t and stack2_t independently
 507         void foo() {
 508             stack1_t    s1;
 509             stack2_t    s2;
 510
 511             myData i1, i2;
 512             s1.push( i1 );
 513             s2.push( i2 );
 514             s2.push( i1 )   ;   // i1 is now contained in s1 and s2.
 515
 516             myData * p;
 517
 518             p = s1.pop()    ;   // pop i1 from s1
 519             p = s1.pop()    ;   // p == nullptr, s1 is empty
 520             p = s2.pop()    ;   // pop i1 from s2
 521             p = s2.pop()    ;   // pop i2 from s2
 522             p = s2.pop()    ;   // p == nullptr, s2 is empty
 523         }
 524         \endcode
 525
 526         Example of how to use \p treiber_stack::member_hook.
 527         Your class that will be pushed on \p %TreiberStack should have a member of type \p treiber_stack::node
 528         \code
 529         #include <stddef.h>     // offsetof macro
 530         #include <cds/intrusive/stack/treiber_stack.h>
 531         #include <cds/gc/hp.h>
 532
 533         namespace ci = cds::intrusive;
 534         typedef cds::gc::HP gc;
 535
 536         struct myData
 537         {
 538             // ...
 539             ci::treiber_stack::node< gc >      member_hook_;
 540             // ...
 541         };
 542
 543         typedef ci::TreiberStack< gc,
 544             myData,
 545             typename ci::treiber_stack::make_traits<
 546                 ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >
 547             >::type
 548         > stack_t;
 549         \endcode
 550     */
 551     template <typename GC, typename T, typename Traits = treiber_stack::traits >
 552     class TreiberStack
 553     {
 554     public:
 555         /// Rebind template arguments
 556         template <typename GC2, typename T2, typename Traits2>
 557         struct rebind {
 558             typedef TreiberStack< GC2, T2, Traits2 > other   ;   ///< Rebinding result
 559         };
 560
 561     public:
 562         typedef GC  gc;                 ///< Garbage collector
 563         typedef T       value_type;     ///< type of value stored in the stack
 564         typedef Traits  traits;         ///< Stack traits
 565
 566         typedef typename traits::hook      hook;        ///< hook type
 567         typedef typename traits::node_type node_type;   ///< node type
 568         typedef typename traits::disposer  disposer;    ///< disposer used
 569         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
 570         typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker   ;   ///< link checker
 571         typedef typename traits::memory_model   memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 572         typedef typename traits::item_counter   item_counter;   ///< Item counting policy used
 573         typedef typename traits::stat           stat;           ///< Internal statistics policy used
 574         typedef typename traits::back_off       back_off;       ///< back-off strategy
 575
 576     public: // related to elimination back-off
 577
 578         /// Elimination back-off is enabled or not
 579         static CDS_CONSTEXPR_CONST bool enable_elimination = traits::enable_elimination;
 580         /// back-off strategy used to wait for elimination
 581         typedef typename traits::elimination_backoff elimination_backoff_type;
 582         /// Lock type used in elimination back-off
 583         typedef typename traits::lock_type elimination_lock_type;
 584         /// Random engine used in elimination back-off
 585         typedef typename traits::random_engine elimination_random_engine;
 586
 587
 588     protected:
 589         typename node_type::atomic_node_ptr m_Top;  ///< Top of the stack
 590         item_counter        m_ItemCounter;          ///< Item counter
 591         stat                m_stat;                 ///< Internal statistics
 592
 593         //@cond
 594         treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
 595
 596         typedef intrusive::node_to_value<TreiberStack>  node_to_value;
 597         typedef treiber_stack::operation< value_type >  operation_desc;
 598         //@endcond
 599
 600     protected:
 601         //@cond
 602         void clear_links( node_type * pNode ) CDS_NOEXCEPT
 603         {
 604             pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 605         }
 606
 607         template <bool EnableElimination>
 608         struct elimination_backoff_impl;
 609
 610         void init()
 611         {
 612             // GC and node_type::gc must be the same
 613             static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
 614
 615             static_assert( (!enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value),
 616                 "Random engine result type must be unsigned int" );
 617         }
 618
 619         //@endcond
 620
 621     public:
 622         /// Constructs empty stack
 623         TreiberStack()
 624             : m_Top( nullptr )
 625         {
 626             init();
 627         }
 628
 629         /// Constructs empty stack and initializes elimination back-off data
 630         /**
 631             This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
 632             \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
 633             \p nCollisionCapacity parameter specifies the capacity of collision array.
 634         */
 635         TreiberStack( size_t nCollisionCapacity )
 636             : m_Top( nullptr )
 637             , m_Backoff( nCollisionCapacity )
 638         {
 639             init();
 640         }
 641
 642         /// %TreiberStack is not copy-constructible
 643         TreiberStack( TreiberStack const& ) = delete;
 644
 645         /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
 646         ~TreiberStack()
 647         {
 648             clear();
 649         }
 650
 651         /// Push the item \p val on the stack
 652         /**
 653             No copying is made since it is intrusive stack.
 654         */
 655         bool push( value_type& val )
 656         {
 657             node_type * pNew = node_traits::to_node_ptr( val );
 658             link_checker::is_empty( pNew );
 659
 660             m_Backoff.reset();
 661
 662             operation_desc op;
 663             if ( enable_elimination ) {
 664                 op.idOp = treiber_stack::op_push;
 665                 op.pVal = &val;
 666             }
 667
 668             node_type * t = m_Top.load(memory_model::memory_order_relaxed);
 669             while ( true ) {
 670                 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
 671                 if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {     // #1 sync-with #2
 672                     ++m_ItemCounter;
 673                     m_stat.onPush();
 674                     return true;
 675                 }
 676                 m_stat.onPushRace();
 677
 678                 if ( m_Backoff.backoff( op, m_stat ))
 679                     return true;
 680             }
 681         }
 682
 683         /// Pop an item from the stack
 684         /**
 685             If stack is empty, returns \p nullptr.
 686             The disposer is <b>not</b> called for popped item.
 687             See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
 688         */
 689         value_type * pop()
 690         {
 691             m_Backoff.reset();
 692             typename gc::Guard  guard;
 693
 694             operation_desc op;
 695             if ( enable_elimination ) {
 696                 op.idOp = treiber_stack::op_pop;
 697             }
 698
 699             while ( true ) {
 700                 node_type * t = guard.protect( m_Top, node_to_value() );
 701                 if ( t == nullptr )
 702                     return nullptr;    // stack is empty
 703
 704                 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
 705                 if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {              // #2
 706                     clear_links( t );
 707                     --m_ItemCounter;
 708                     m_stat.onPop();
 709                     return node_traits::to_value_ptr( *t );
 710                 }
 711
 712                 m_stat.onPopRace();
 713                 if ( m_Backoff.backoff( op, m_stat )) {
 714                     // may return nullptr if stack is empty
 715                     return op.pVal;
 716                 }
 717             }
 718         }
 719
 720         /// Check if stack is empty
 721         bool empty() const
 722         {
 723             // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0
 724             return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
 725         }
 726
 727         /// Clear the stack
 728         /** @anchor cds_intrusive_TreiberStack_clear
 729             For each removed item the disposer is called.
 730
 731             @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
 732             if some other thread pushes an item into the stack during \p clear works
 733         */
 734         void clear()
 735         {
 736             back_off bkoff;
 737             node_type * pTop;
 738             while ( true ) {
 739                 pTop = m_Top.load( memory_model::memory_order_relaxed );
 740                 if ( pTop == nullptr )
 741                     return;
 742                 if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) {    // sync-with #1 and #2
 743                     m_ItemCounter.reset();
 744                     break;
 745                 }
 746                 bkoff();
 747             }
 748
 749             while( pTop ) {
 750                 node_type * p = pTop;
 751                 pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
 752                 clear_links( p );
 753                 gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
 754             }
 755         }
 756
 757         /// Returns stack's item count
 758         /**
 759             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 760             this function always returns 0.
 761
 762             @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack
 763             is empty. To check emptyness use \ref empty() method.
 764         */
 765         size_t    size() const
 766         {
 767             return m_ItemCounter.value();
 768         }
 769
 770         /// Returns reference to internal statistics
 771         stat const& statistics() const
 772         {
 773             return m_stat;
 774         }
 775     };
 776
 777 }} // namespace cds::intrusive
 778
 779 #endif  // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H