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