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