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