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