cds/intrusive/treiber_stack.h

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