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