cds/intrusive/treiber_stack.h

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