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 \ref cds_intrusive_hook_tag "tag"
  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 - a \ref cds_intrusive_hook_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 - a \ref cds_intrusive_hook_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 - a \ref cds_intrusive_hook_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. Use \p cds::atomicity::item_counter to enable item counting
 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, i.e.
 220                 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
 221             - opt::stat - the type to gather internal statistics.
 222                 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
 223                 user-provided class that supports \p treiber_stack::stat interface.
 224             - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
 225
 226             If elimination back-off is enabled, additional options can be specified:
 227             - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
 228                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
 229                 The size should be selected empirically for your application and hardware, there are no common rules for that.
 230                 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
 231             - opt::random_engine - a random engine to generate a random position in elimination array.
 232                 Default is \p opt::v::c_rand.
 233             - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
 234             - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin.
 235         */
 236         template <typename... Options>
 237         struct make_traits {
 238 #   ifdef CDS_DOXYGEN_INVOKED
 239             typedef implementation_defined type;   ///< Metafunction result
 240 #   else
 241             typedef typename cds::opt::make_options<
 242                 typename cds::opt::find_type_traits< traits, Options... >::type
 243                 , Options...
 244             >::type   type;
 245 #   endif
 246         };
 247
 248
 249         //@cond
 250         namespace details {
 251
 252             template <bool EnableElimination, typename T, typename Traits>
 253             class elimination_backoff;
 254
 255             template <typename T, typename Traits>
 256             class elimination_backoff<false, T, Traits>
 257             {
 258                 typedef typename Traits::back_off   back_off;
 259
 260                 back_off    m_bkoff;
 261             public:
 262                 elimination_backoff()
 263                 {}
 264
 265                 elimination_backoff( size_t )
 266                 {}
 267
 268                 void reset()
 269                 {
 270                     m_bkoff.reset();
 271                 }
 272
 273                 template <typename Stat>
 274                 bool backoff(treiber_stack::operation< T >&, Stat& )
 275                 {
 276                     m_bkoff();
 277                     return false;
 278                 }
 279             };
 280
 281             template <typename T, typename Traits>
 282             class elimination_backoff<true, T, Traits>
 283             {
 284                 typedef typename Traits::back_off   back_off;
 285
 286                 /// Back-off for elimination (usually delay)
 287                 typedef typename Traits::elimination_backoff elimination_backoff_type;
 288                 /// Lock type used in elimination back-off
 289                 typedef typename Traits::lock_type elimination_lock_type;
 290                 /// Random engine used in elimination back-off
 291                 typedef typename Traits::random_engine elimination_random_engine;
 292
 293                 /// Per-thread elimination record
 294                 typedef cds::algo::elimination::record  elimination_rec;
 295
 296                 /// Collision array record
 297                 struct collision_array_record {
 298                     elimination_rec *     pRec;
 299                     elimination_lock_type lock;
 300                 };
 301
 302                 /// Collision array used in elimination-backoff; each item is optimized for cache-line size
 303                 typedef typename Traits::buffer::template rebind<
 304                     typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
 305                 >::other collision_array;
 306
 307                 /// Operation descriptor used in elimination back-off
 308                 typedef treiber_stack::operation< T >  operation_desc;
 309
 310                 /// Elimination back-off data
 311                 struct elimination_data {
 312                     elimination_random_engine   randEngine; ///< random engine
 313                     collision_array             collisions; ///< collision array
 314
 315                     elimination_data()
 316                     {
 317                         //TODO: check Traits::buffer must be static!
 318                     }
 319                     elimination_data( size_t nCollisionCapacity )
 320                         : collisions( nCollisionCapacity )
 321                     {}
 322                 };
 323
 324                 elimination_data m_Elimination;
 325
 326                 enum operation_status {
 327                     op_free = 0,
 328                     op_busy = 1,
 329                     op_collided = 2
 330                 };
 331
 332                 typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
 333
 334             public:
 335                 elimination_backoff()
 336                 {
 337                     m_Elimination.collisions.zeroize();
 338                 }
 339
 340                 elimination_backoff( size_t nCollisionCapacity )
 341                     : m_Elimination( nCollisionCapacity )
 342                 {
 343                     m_Elimination.collisions.zeroize();
 344                 }
 345
 346                 void reset()
 347                 {}
 348
 349                 template <typename Stat>
 350                 bool backoff( operation_desc& op, Stat& stat )
 351                 {
 352                     elimination_backoff_type bkoff;
 353                     op.nStatus.store( op_busy, atomics::memory_order_relaxed );
 354
 355                     elimination_rec * myRec = cds::algo::elimination::init_record( op );
 356
 357                     collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
 358                     {
 359                         slot.lock.lock();
 360                         elimination_rec * himRec = slot.pRec;
 361                         if ( himRec ) {
 362                             operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
 363                             assert( himOp );
 364                             if ( himOp->idOp != op.idOp ) {
 365                                 if ( op.idOp == treiber_stack::op_push )
 366                                     himOp->pVal = op.pVal;
 367                                 else
 368                                     op.pVal = himOp->pVal;
 369                                 slot.pRec = nullptr;
 370                                 slot.lock.unlock();
 371
 372                                 himOp->nStatus.store( op_collided, atomics::memory_order_release );
 373                                 cds::algo::elimination::clear_record();
 374                                 stat.onActiveCollision( op.idOp );
 375                                 return true;
 376                             }
 377                             himOp->nStatus.store( op_free, atomics::memory_order_release );
 378                         }
 379                         slot.pRec = myRec;
 380                         slot.lock.unlock();
 381                     }
 382
 383                     // Wait for colliding operation
 384                     bkoff( [&op]() -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
 385                     {
 386                         slot_scoped_lock l( slot.lock );
 387                         if ( slot.pRec == myRec )
 388                             slot.pRec = nullptr;
 389                     }
 390
 391                     bool bCollided = op.nStatus.load( atomics::memory_order_acquire ) == op_collided;
 392
 393                     if ( !bCollided )
 394                         stat.onEliminationFailed();
 395                     else
 396                         stat.onPassiveCollision( op.idOp );
 397
 398                     cds::algo::elimination::clear_record();
 399                     return bCollided;
 400                 }
 401             };
 402
 403         } // namespace details
 404         //@endcond
 405     } // namespace treiber_stack
 406
 407     /// Treiber stack
 408     /** @ingroup cds_intrusive_stack
 409         Intrusive implementation of well-known Treiber's stack algorithm:
 410         - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
 411
 412         \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
 413         The idea of elimination algorithm is taken from:
 414         - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
 415
 416         The elimination algorithm uses a single elimination array as a back-off schema
 417         on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
 418         on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
 419
 420         @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
 421         The main difficulty is the managing life-time of elimination record.
 422         Our implementation uses simplified lock-based (spin-based) approach which allows
 423         the elimination record allocation on thread's stack.
 424         This approach demonstrates sufficient performance under high load.
 425
 426         Template arguments:
 427         - \p GC - garbage collector type: \p gc::HP, gc::DHP.
 428             Garbage collecting schema must be the same as \p treiber_stack::node GC.
 429         - \p T - a type the stack contains
 430         - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
 431             metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
 432             \code
 433             struct myTraits: public cds::intrusive::treiber_stack::traits {
 434                 typedef cds::intrusive::treiber_stack::stat<> stat;
 435             };
 436             typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
 437
 438             // Equivalent make_traits example:
 439             typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
 440                 typename cds::intrusive::treiber_stack::make_traits<
 441                     cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
 442                 >::type
 443             > myStack;
 444             \endcode
 445
 446         @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
 447
 448         @anchor cds_intrusive_TreiberStack_examples
 449         \par Examples
 450
 451         Example of how to use \p treiber_stack::base_hook.
 452         Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class
 453         \code
 454         #include <cds/intrusive/treiber_stack.h>
 455         #include <cds/gc/hp.h>
 456
 457         namespace ci = cds::intrusive;
 458         typedef cds::gc::HP gc;
 459
 460         struct myData: public ci::treiber_stack::node< gc >
 461         {
 462             // ...
 463         };
 464
 465         // Stack type
 466         typedef ci::TreiberStack< gc,
 467             myData,
 468             typename cds::intrusive::treiber_stack::make_traits<
 469                 ci::opt::hook< ci::treiber_stack::base_hook< gc > >
 470             >::type
 471         > stack_t;
 472
 473         // Stack with elimination back-off enabled
 474         typedef ci::TreiberStack< gc,
 475             myData,
 476             typename ci::treiber_stack::make_traits<
 477                 ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
 478                 cds::opt::enable_elimination< true >
 479             >::type
 480         > elimination_stack_t;
 481         \endcode
 482
 483         Example of how to use \p treiber_stack::base_hook with different tags.
 484         \code
 485         #include <cds/intrusive/treiber_stack.h>
 486         #include <cds/gc/hp.h>
 487
 488         namespace ci = cds::intrusive;
 489         typedef cds::gc::HP gc;
 490
 491         // It is not necessary to declare complete type for tags
 492         struct tag1;
 493         struct tag2;
 494
 495         struct myData
 496             : public ci::treiber_stack::node< gc, tag1 >
 497             , public ci::treiber_stack::node< gc, tag2 >
 498         {
 499             // ...
 500         };
 501
 502         typedef ci::TreiberStack< gc,
 503             myData,
 504             typename ci::treiber_stack::make_traits<
 505                 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
 506             >::type
 507         > stack1_t;
 508
 509         typedef ci::TreiberStack< gc,
 510             myData,
 511             typename ci::treiber_stack::make_traits<
 512                 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 > >
 513             >::type
 514         > stack2_t;
 515
 516         // You may add myData objects into stack1_t and stack2_t independently
 517         void foo() {
 518             stack1_t    s1;
 519             stack2_t    s2;
 520
 521             myData i1, i2;
 522             s1.push( i1 );
 523             s2.push( i2 );
 524             s2.push( i1 )   ;   // i1 is now contained in s1 and s2.
 525
 526             myData * p;
 527
 528             p = s1.pop()    ;   // pop i1 from s1
 529             p = s1.pop()    ;   // p == nullptr, s1 is empty
 530             p = s2.pop()    ;   // pop i1 from s2
 531             p = s2.pop()    ;   // pop i2 from s2
 532             p = s2.pop()    ;   // p == nullptr, s2 is empty
 533         }
 534         \endcode
 535
 536         Example of how to use \p treiber_stack::member_hook.
 537         Your class should have a member of type \p treiber_stack::node
 538         \code
 539         #include <stddef.h>     // offsetof macro
 540         #include <cds/intrusive/treiber_stack.h>
 541         #include <cds/gc/hp.h>
 542
 543         namespace ci = cds::intrusive;
 544         typedef cds::gc::HP gc;
 545
 546         struct myData
 547         {
 548             // ...
 549             ci::treiber_stack::node< gc >      member_hook_;
 550             // ...
 551         };
 552
 553         typedef ci::TreiberStack< gc,
 554             myData,
 555             typename ci::treiber_stack::make_traits<
 556                 ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >>
 557             >::type
 558         > stack_t;
 559         \endcode
 560     */
 561     template <
 562         typename GC,
 563         typename T,
 564         typename Traits = treiber_stack::traits
 565     >
 566     class TreiberStack
 567     {
 568     public:
 569         /// Rebind template arguments
 570         template <typename GC2, typename T2, typename Traits2>
 571         struct rebind {
 572             typedef TreiberStack< GC2, T2, Traits2 > other   ;   ///< Rebinding result
 573         };
 574
 575     public:
 576         typedef GC      gc;             ///< Garbage collector
 577         typedef T       value_type;     ///< type of value stored in the stack
 578         typedef Traits  traits;         ///< Stack traits
 579
 580         typedef typename traits::hook      hook;        ///< hook type
 581         typedef typename traits::node_type node_type;   ///< node type
 582         typedef typename traits::disposer  disposer;    ///< disposer used
 583         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
 584         typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker   ;   ///< link checker
 585         typedef typename traits::memory_model   memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 586         typedef typename traits::item_counter   item_counter;   ///< Item counting policy used
 587         typedef typename traits::stat           stat;           ///< Internal statistics policy used
 588         typedef typename traits::back_off       back_off;       ///< back-off strategy
 589
 590     public: // related to elimination back-off
 591
 592         /// Elimination back-off is enabled or not
 593         static CDS_CONSTEXPR_CONST bool enable_elimination = traits::enable_elimination;
 594         /// back-off strategy used to wait for elimination
 595         typedef typename traits::elimination_backoff elimination_backoff_type;
 596         /// Lock type used in elimination back-off
 597         typedef typename traits::lock_type elimination_lock_type;
 598         /// Random engine used in elimination back-off
 599         typedef typename traits::random_engine elimination_random_engine;
 600
 601     protected:
 602         typename node_type::atomic_node_ptr m_Top;  ///< Top of the stack
 603         item_counter        m_ItemCounter;          ///< Item counter
 604         stat                m_stat;                 ///< Internal statistics
 605
 606         //@cond
 607         treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
 608
 609         typedef intrusive::node_to_value<TreiberStack>  node_to_value;
 610         typedef treiber_stack::operation< value_type >  operation_desc;
 611         //@endcond
 612
 613     protected:
 614         //@cond
 615         void clear_links( node_type * pNode ) CDS_NOEXCEPT
 616         {
 617             pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 618         }
 619
 620         template <bool EnableElimination>
 621         struct elimination_backoff_impl;
 622
 623         void init()
 624         {
 625             // GC and node_type::gc must be the same
 626             static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
 627
 628             static_assert( (!enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value),
 629                 "Random engine result type must be unsigned int" );
 630         }
 631         //@endcond
 632
 633     public:
 634         /// Constructs empty stack
 635         TreiberStack()
 636             : m_Top( nullptr )
 637         {
 638             init();
 639         }
 640
 641         /// Constructs empty stack and initializes elimination back-off data
 642         /**
 643             This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
 644             \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
 645             \p nCollisionCapacity parameter specifies the capacity of collision array.
 646         */
 647         TreiberStack( size_t nCollisionCapacity )
 648             : m_Top( nullptr )
 649             , m_Backoff( nCollisionCapacity )
 650         {
 651             init();
 652         }
 653
 654         /// \p %TreiberStack is not copy-constructible
 655         TreiberStack( TreiberStack const& ) = delete;
 656
 657         /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
 658         ~TreiberStack()
 659         {
 660             clear();
 661         }
 662
 663         /// Push the item \p val on the stack
 664         /**
 665             No copying is made since it is intrusive stack.
 666         */
 667         bool push( value_type& val )
 668         {
 669             node_type * pNew = node_traits::to_node_ptr( val );
 670             link_checker::is_empty( pNew );
 671
 672             m_Backoff.reset();
 673
 674             operation_desc op;
 675             if ( enable_elimination ) {
 676                 op.idOp = treiber_stack::op_push;
 677                 op.pVal = &val;
 678             }
 679
 680             node_type * t = m_Top.load(memory_model::memory_order_relaxed);
 681             while ( true ) {
 682                 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
 683                 if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {     // #1 sync-with #2
 684                     ++m_ItemCounter;
 685                     m_stat.onPush();
 686                     return true;
 687                 }
 688                 m_stat.onPushRace();
 689
 690                 if ( m_Backoff.backoff( op, m_stat ))
 691                     return true;
 692             }
 693         }
 694
 695         /// Pop an item from the stack
 696         /**
 697             If stack is empty, returns \p nullptr.
 698             The disposer is <b>not</b> called for popped item.
 699             See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
 700         */
 701         value_type * pop()
 702         {
 703             m_Backoff.reset();
 704             typename gc::Guard  guard;
 705
 706             operation_desc op;
 707             if ( enable_elimination ) {
 708                 op.idOp = treiber_stack::op_pop;
 709             }
 710
 711             while ( true ) {
 712                 node_type * t = guard.protect( m_Top, node_to_value() );
 713                 if ( t == nullptr )
 714                     return nullptr;    // stack is empty
 715
 716                 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
 717                 if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {              // #2
 718                     clear_links( t );
 719                     --m_ItemCounter;
 720                     m_stat.onPop();
 721                     return node_traits::to_value_ptr( *t );
 722                 }
 723
 724                 m_stat.onPopRace();
 725                 if ( m_Backoff.backoff( op, m_stat )) {
 726                     // may return nullptr if stack is empty
 727                     return op.pVal;
 728                 }
 729             }
 730         }
 731
 732         /// Check if stack is empty
 733         bool empty() const
 734         {
 735             // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0
 736             return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
 737         }
 738
 739         /// Clear the stack
 740         /** @anchor cds_intrusive_TreiberStack_clear
 741             For each removed item the disposer is called.
 742
 743             @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
 744             if some other thread pushes an item into the stack during \p clear works
 745         */
 746         void clear()
 747         {
 748             back_off bkoff;
 749             node_type * pTop;
 750             while ( true ) {
 751                 pTop = m_Top.load( memory_model::memory_order_relaxed );
 752                 if ( pTop == nullptr )
 753                     return;
 754                 if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) {    // sync-with #1 and #2
 755                     m_ItemCounter.reset();
 756                     break;
 757                 }
 758                 bkoff();
 759             }
 760
 761             while( pTop ) {
 762                 node_type * p = pTop;
 763                 pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
 764                 clear_links( p );
 765                 gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
 766             }
 767         }
 768
 769         /// Returns stack's item count
 770         /**
 771             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 772             this function always returns 0.
 773
 774             @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack
 775             is empty. To check emptyness use \ref empty() method.
 776         */
 777         size_t    size() const
 778         {
 779             return m_ItemCounter.value();
 780         }
 781
 782         /// Returns reference to internal statistics
 783         stat const& statistics() const
 784         {
 785             return m_stat;
 786         }
 787     };
 788
 789 }} // namespace cds::intrusive
 790
 791 #endif  // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H