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