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