cds/intrusive/optimistic_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H
   4 #define __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H
   5
   6 #include <type_traits>
   7 #include <cds/intrusive/details/base.h>
   8 #include <cds/cxx11_atomic.h>
   9 #include <cds/gc/default_gc.h>
  10
  11 namespace cds { namespace intrusive {
  12
  13     /// OptimisticQueue related definitions
  14     /** @ingroup cds_intrusive_helper
  15     */
  16     namespace optimistic_queue {
  17
  18         /// Optimistic queue node
  19         /**
  20             Template parameters:
  21             - \p GC - garbage collector
  22             - \p Tag - a \ref cds_intrusive_hook_tag "tag"
  23         */
  24         template <class GC, typename Tag = opt::none>
  25         struct node
  26         {
  27             typedef GC  gc  ;   ///< Garbage collector
  28             typedef Tag tag ;   ///< tag
  29
  30             typedef typename gc::template atomic_ref<node>    atomic_node_ptr    ;    ///< atomic pointer
  31
  32             atomic_node_ptr m_pPrev ;   ///< Pointer to previous node
  33             atomic_node_ptr m_pNext ;   ///< Pointer to next node
  34
  35             CDS_CONSTEXPR node() CDS_NOEXCEPT
  36                 : m_pPrev( nullptr )
  37                 , m_pNext( nullptr )
  38             {}
  39         };
  40
  41         //@cond
  42         struct default_hook {
  43             typedef cds::gc::default_gc gc;
  44             typedef opt::none           tag;
  45         };
  46         //@endcond
  47
  48         //@cond
  49         template < typename HookType, typename... Options>
  50         struct hook
  51         {
  52             typedef typename opt::make_options< default_hook, Options...>::type  options;
  53             typedef typename options::gc    gc;
  54             typedef typename options::tag   tag;
  55             typedef node<gc, tag> node_type;
  56             typedef HookType     hook_type;
  57         };
  58         //@endcond
  59
  60         /// Base hook
  61         /**
  62             \p Options are:
  63             - opt::gc - garbage collector used.
  64             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  65         */
  66         template < typename... Options >
  67         struct base_hook: public hook< opt::base_hook_tag, Options... >
  68         {};
  69
  70         /// Member hook
  71         /**
  72             \p MemberOffset specifies offset in bytes of \ref node member into your structure.
  73             Use \p offsetof macro to define \p MemberOffset
  74
  75             \p Options are:
  76             - opt::gc - garbage collector used.
  77             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  78         */
  79         template < size_t MemberOffset, typename... Options >
  80         struct member_hook: public hook< opt::member_hook_tag, Options... >
  81         {
  82             //@cond
  83             static const size_t c_nMemberOffset = MemberOffset;
  84             //@endcond
  85         };
  86
  87         /// Traits hook
  88         /**
  89             \p NodeTraits defines type traits for node.
  90             See \ref node_traits for \p NodeTraits interface description
  91
  92             \p Options are:
  93             - opt::gc - garbage collector used.
  94             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  95         */
  96         template <typename NodeTraits, typename... Options >
  97         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
  98         {
  99             //@cond
 100             typedef NodeTraits node_traits;
 101             //@endcond
 102         };
 103
 104         /// Check link
 105         template <typename Node>
 106         struct link_checker {
 107             //@cond
 108             typedef Node node_type;
 109             //@endcond
 110
 111             /// Checks if the link fields of node \p pNode is \p nullptr
 112             /**
 113                 An asserting is generated if \p pNode link fields is not \p nullptr
 114             */
 115             static void is_empty( const node_type * pNode )
 116             {
 117                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 118                 assert( pNode->m_pPrev.load( atomics::memory_order_relaxed ) == nullptr );
 119                 CDS_UNUSED( pNode );
 120             }
 121         };
 122
 123         /// Metafunction for selecting appropriate link checking policy
 124         template < typename Node, opt::link_check_type LinkType >
 125         struct get_link_checker
 126         {
 127             //@cond
 128             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 129             //@endcond
 130         };
 131
 132         //@cond
 133         template < typename Node >
 134         struct get_link_checker< Node, opt::always_check_link >
 135         {
 136             typedef link_checker<Node>  type;
 137         };
 138         template < typename Node >
 139         struct get_link_checker< Node, opt::debug_check_link >
 140         {
 141 #       ifdef _DEBUG
 142             typedef link_checker<Node>  type;
 143 #       else
 144             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 145 #       endif
 146         };
 147         //@endcond
 148
 149         /// OptimisticQueue internal statistics. May be used for debugging or profiling
 150         /**
 151             Template argument \p Counter defines type of counter.
 152             Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
 153             strict event counting.
 154             You may use stronger type of counter like as \p cds::atomicity::item_counter,
 155             or even integral type, for example, \p int.
 156         */
 157         template <typename Counter = cds::atomicity::event_counter >
 158         struct stat
 159         {
 160             typedef Counter     counter_type;   ///< Counter type
 161
 162             counter_type m_EnqueueCount;  ///< Enqueue call count
 163             counter_type m_DequeueCount;  ///< Dequeue call count
 164             counter_type m_EnqueueRace;  ///< Count of enqueue race conditions encountered
 165             counter_type m_DequeueRace;  ///< Count of dequeue race conditions encountered
 166             counter_type m_AdvanceTailError;  ///< Count of "advance tail failed" events
 167             counter_type m_BadTail;  ///< Count of events "Tail is not pointed to the last item in the queue"
 168             counter_type    m_FixListCount;   ///< Count of fix list event
 169
 170             /// Register enqueue call
 171             void onEnqueue() { ++m_EnqueueCount; }
 172             /// Register dequeue call
 173             void onDequeue() { ++m_DequeueCount; }
 174             /// Register enqueue race event
 175             void onEnqueueRace() { ++m_EnqueueRace; }
 176             /// Register dequeue race event
 177             void onDequeueRace() { ++m_DequeueRace; }
 178             /// Register "advance tail failed" event
 179             void onAdvanceTailFailed() { ++m_AdvanceTailError; }
 180             /// Register event "Tail is not pointed to last item in the queue"
 181             void onBadTail() { ++m_BadTail; }
 182             /// Register fix list event
 183             void onFixList()    { ++m_FixListCount; }
 184
 185             //@cond
 186             void reset()
 187             {
 188                 m_EnqueueCount.reset();
 189                 m_DequeueCount.reset();
 190                 m_EnqueueRace.reset();
 191                 m_DequeueRace.reset();
 192                 m_AdvanceTailError.reset();
 193                 m_BadTail.reset();
 194                 m_FixListCount.reset();
 195             }
 196
 197             stat& operator +=( stat const& s )
 198             {
 199                 m_EnqueueCount += s.m_EnqueueCount.get();
 200                 m_DequeueCount += s.m_DequeueCount.get();
 201                 m_EnqueueRace += s.m_EnqueueRace.get();
 202                 m_DequeueRace += s.m_DequeueRace.get();
 203                 m_AdvanceTailError += s.m_AdvanceTailError.get();
 204                 m_BadTail += s.m_BadTail.get();
 205                 m_FixListCount += s.m_FixListCount.get();
 206                 return *this;
 207             }
 208             //@endcond
 209         };
 210
 211         /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
 212         struct empty_stat
 213         {
 214             //@cond
 215             void onEnqueue() {}
 216             void onDequeue() {}
 217             void onEnqueueRace() {}
 218             void onDequeueRace() {}
 219             void onAdvanceTailFailed() {}
 220             void onBadTail() {}
 221             void onFixList() {}
 222
 223             void reset() {}
 224             empty_stat& operator +=( empty_stat const& )
 225             {
 226                 return *this;
 227             }
 228             //@endcond
 229         };
 230
 231         /// OptimisticQueue default type traits
 232         struct traits
 233         {
 234             /// Back-off strategy
 235             typedef cds::backoff::empty             back_off;
 236
 237             /// Hook, possible types are \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook
 238             typedef optimistic_queue::base_hook<>   hook;
 239
 240             /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
 241             typedef opt::v::empty_disposer          disposer;
 242
 243             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 244             typedef cds::atomicity::empty_item_counter   item_counter;
 245
 246             /// C++ memory ordering model
 247             /**
 248                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 249                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 250             */
 251             typedef opt::v::relaxed_ordering        memory_model;
 252
 253             /// Internal statistics (by default, disabled)
 254             /**
 255                 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
 256                 user-provided class that supports \p %optimistic_queue::stat interface.
 257             */
 258             typedef optimistic_queue::empty_stat    stat;
 259
 260             /// Link checking, see \p cds::opt::link_checker
 261             static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
 262
 263             /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
 264             enum { alignment = opt::cache_line_alignment };
 265         };
 266
 267         /// Metafunction converting option list to \p optimistic_queue::traits
 268         /**
 269             Supported \p Options are:
 270
 271             - opt::hook - hook used. Possible hooks are: \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook.
 272                 If the option is not specified, \p %optimistic_queue::base_hook<> is used.
 273             - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
 274             - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
 275                 when dequeuing.
 276             - opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 277             - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
 278                 To enable item counting use \p cds::atomicity::item_counter
 279             - opt::stat - the type to gather internal statistics.
 280                 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
 281                 user-provided class that supports \p %optimistic_queue::stat interface.
 282                 Default is \p %optimistic_queue::empty_stat (internal statistics disabled).
 283             - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
 284             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 285                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 286
 287             Example: declare \p %OptimisticQueue with item counting and internal statistics
 288             \code
 289             typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
 290                 typename cds::intrusive::optimistic_queue::make_traits<
 291                     cds::intrusive::opt:hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
 292                     cds::opt::item_counte< cds::atomicity::item_counter >,
 293                     cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >
 294                 >::type
 295             > myQueue;
 296             \endcode
 297         */
 298         template <typename... Options>
 299         struct make_traits {
 300 #   ifdef CDS_DOXYGEN_INVOKED
 301             typedef implementation_defined type;   ///< Metafunction result
 302 #   else
 303             typedef typename cds::opt::make_options<
 304                 typename cds::opt::find_type_traits< traits, Options... >::type
 305                 , Options...
 306             >::type type;
 307 #   endif
 308         };
 309     }   // namespace optimistic_queue
 310
 311     /// Optimistic intruive lock-free queue
 312     /** @ingroup cds_intrusive_queue
 313         Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
 314             [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
 315
 316         Template arguments:
 317         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
 318         - \p T - type of value to be stored in the queue. A value of type \p T must be derived from \p optimistic_queue::node for \p optimistic_queue::base_hook,
 319             or it should have a member of type \p %optimistic_queue::node for \p optimistic_queue::member_hook,
 320             or it should be convertible to \p %optimistic_queue::node for \p optimistic_queue::traits_hook.
 321         - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
 322             metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
 323             \code
 324             struct myTraits: public cds::intrusive::optimistic_queue::traits {
 325                 typedef cds::intrusive::optimistic_queue::stat<> stat;
 326                 typedef cds::atomicity::item_counter    item_counter;
 327             };
 328             typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
 329
 330             // Equivalent make_traits example:
 331             typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
 332                 typename cds::intrusive::optimistic_queue::make_traits<
 333                     cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
 334                     cds::opt::item_counter< cds::atomicity::item_counter >
 335                 >::type
 336             > myQueue;
 337             \endcode
 338
 339         Garbage collecting schema \p GC must be consistent with the optimistic_queue::node GC.
 340
 341         \par About item disposing
 342         The optimistic queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
 343         the standpoint of the algo. See \p dequeue() function for explanation.
 344
 345         \par Examples
 346         \code
 347         #include <cds/gc/hp.h>
 348         #include <cds/intrusive/optimistic_queue.h>
 349
 350         namespace ci = cds::inrtusive;
 351         typedef cds::gc::HP hp_gc;
 352
 353         // Optimistic queue with Hazard Pointer garbage collector, base hook + item counter:
 354         struct Foo: public ci::optimistic_queue::node< hp_gc >
 355         {
 356             // Your data
 357             ...
 358         };
 359
 360         typedef ci::OptimisticQueue< hp_gc,
 361             Foo,
 362             typename ci::optimistic_queue::make_traits<
 363                 ci::opt::hook<
 364                     ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
 365                 >
 366                 ,cds::opt::item_counter< cds::atomicity::item_counter >
 367             >::type
 368         > FooQueue;
 369
 370         // Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
 371         struct Bar
 372         {
 373             // Your data
 374             ...
 375             ci::optimistic_queue::node< hp_gc > hMember;
 376         };
 377
 378         typedef ci::OptimisticQueue< hp_gc,
 379             Bar,
 380             typename ci::optimistic_queue::make_traits<
 381                 ci::opt::hook<
 382                     ci::optimistic_queue::member_hook<
 383                         offsetof(Bar, hMember)
 384                         ,ci::opt::gc< hp_gc >
 385                     >
 386                 >
 387             >::type
 388         > BarQueue;
 389         \endcode
 390     */
 391     template <typename GC, typename T, typename Traits = optimistic_queue::traits >
 392     class OptimisticQueue
 393     {
 394     public:
 395         typedef GC gc;          ///< Garbage collector
 396         typedef T  value_type;  ///< type of value to be stored in the queue
 397         typedef Traits traits;  ///< Queue traits
 398
 399         typedef typename traits::hook       hook;       ///< hook type
 400         typedef typename hook::node_type    node_type;  ///< node type
 401         typedef typename traits::disposer   disposer;   ///< disposer used
 402         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;    ///< node traits
 403         typedef typename optimistic_queue::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
 404         typedef typename traits::back_off  back_off;        ///< back-off strategy
 405         typedef typename traits::item_counter item_counter; ///< Item counting policy used
 406         typedef typename traits::memory_model  memory_model;///< Memory ordering. See cds::opt::memory_model option
 407         typedef typename traits::stat      stat;            ///< Internal statistics policy used
 408
 409         /// Rebind template arguments
 410         template <typename GC2, typename T2, typename Traits2>
 411         struct rebind {
 412             typedef OptimisticQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
 413         };
 414
 415     protected:
 416         //@cond
 417         typedef intrusive::node_to_value<OptimisticQueue> node_to_value;
 418         typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
 419
 420         // GC and node_type::gc must be the same
 421         static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
 422
 423         //@endcond
 424
 425         aligned_node_ptr m_pTail ;   ///< Pointer to tail node
 426         aligned_node_ptr m_pHead ;   ///< Pointer to head node
 427         node_type        m_Dummy ;   ///< dummy node
 428         item_counter        m_ItemCounter   ;   ///< Item counter
 429         stat                m_Stat          ;   ///< Internal statistics
 430
 431         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5 ; ///< Count of hazard pointer required for the algorithm
 432
 433     protected:
 434         //@cond
 435         static void clear_links( node_type * pNode )
 436         {
 437             pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
 438             pNode->m_pPrev.store( nullptr, memory_model::memory_order_release );
 439         }
 440
 441         struct dequeue_result {
 442             typename gc::template GuardArray<3>  guards;
 443
 444             node_type * pHead;
 445             node_type * pNext;
 446         };
 447
 448         bool do_dequeue( dequeue_result& res )
 449         {
 450             node_type * pTail;
 451             node_type * pHead;
 452             node_type * pFirstNodePrev;
 453             back_off bkoff;
 454
 455             while ( true ) { // Try till success or empty
 456                 pHead = res.guards.protect( 0, m_pHead, node_to_value() );
 457                 pTail = res.guards.protect( 1, m_pTail, node_to_value() );
 458                 assert( pHead != nullptr );
 459                 pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, node_to_value() );
 460
 461                 if ( pHead == m_pHead.load(memory_model::memory_order_relaxed)) {
 462                     if ( pTail != pHead ) {
 463                         if ( pFirstNodePrev == nullptr
 464                           || pFirstNodePrev->m_pNext.load(memory_model::memory_order_relaxed) != pHead )
 465                         {
 466                             fix_list( pTail, pHead );
 467                             continue;
 468                         }
 469                         if ( m_pHead.compare_exchange_weak( pHead, pFirstNodePrev, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 470                             // dequeue success
 471                             break;
 472                         }
 473                     }
 474                     else {
 475                         // the queue is empty
 476                         return false;
 477                     }
 478                 }
 479
 480                 m_Stat.onDequeueRace();
 481                 bkoff();
 482             }
 483
 484             --m_ItemCounter;
 485             m_Stat.onDequeue();
 486
 487             res.pHead = pHead;
 488             res.pNext = pFirstNodePrev;
 489             return true;
 490         }
 491
 492
 493         /// Helper function for optimistic queue. Corrects \p prev pointer of queue's nodes if it is needed
 494         void fix_list( node_type * pTail, node_type * pHead )
 495         {
 496             // pTail and pHead are already guarded
 497
 498             node_type * pCurNode;
 499             node_type * pCurNodeNext;
 500
 501             typename gc::template GuardArray<2> guards;
 502
 503             pCurNode = pTail;
 504             while ( pCurNode != pHead ) { // While not at head
 505                 pCurNodeNext = guards.protect(0, pCurNode->m_pNext, node_to_value() );
 506                 if ( pHead != m_pHead.load(memory_model::memory_order_relaxed) )
 507                     break;
 508                 pCurNodeNext->m_pPrev.store( pCurNode, memory_model::memory_order_release );
 509                 guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext ));
 510             }
 511
 512             m_Stat.onFixList();
 513         }
 514
 515         void dispose_result( dequeue_result& res )
 516         {
 517             dispose_node( res.pHead );
 518         }
 519
 520         void dispose_node( node_type * p )
 521         {
 522             assert( p != nullptr );
 523
 524             if ( p != &m_Dummy ) {
 525                 struct internal_disposer
 526                 {
 527                     void operator ()( value_type * p )
 528                     {
 529                         assert( p != nullptr );
 530
 531                         OptimisticQueue::clear_links( node_traits::to_node_ptr( *p ) );
 532                         disposer()(p);
 533                     }
 534                 };
 535                 gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
 536             }
 537         }
 538
 539         //@endcond
 540
 541     public:
 542         /// Constructor creates empty queue
 543         OptimisticQueue()
 544             : m_pTail( &m_Dummy )
 545             , m_pHead( &m_Dummy )
 546         {}
 547
 548         ~OptimisticQueue()
 549         {
 550             clear();
 551             node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
 552             CDS_DEBUG_ONLY( node_type * pTail = m_pTail.load(memory_model::memory_order_relaxed); )
 553             CDS_DEBUG_ONLY( assert( pHead == pTail ); )
 554             assert( pHead != nullptr );
 555
 556             m_pHead.store( nullptr, memory_model::memory_order_relaxed );
 557             m_pTail.store( nullptr, memory_model::memory_order_relaxed );
 558
 559             dispose_node( pHead );
 560         }
 561
 562         /// @anchor cds_intrusive_OptimisticQueue_enqueue Enqueues \p data in lock-free manner. Always return \a true
 563         bool enqueue( value_type& val )
 564         {
 565             node_type * pNew = node_traits::to_node_ptr( val );
 566             link_checker::is_empty( pNew );
 567
 568             typename gc::template GuardArray<2> guards;
 569             back_off bkoff;
 570
 571             guards.assign( 1, &val );
 572             node_type * pTail = guards.protect( 0, m_pTail, node_to_value() )  ;   // Read the tail
 573             while( true ) {
 574                 pNew->m_pNext.store( pTail, memory_model::memory_order_release );
 575                 if ( m_pTail.compare_exchange_strong( pTail, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {     // Try to CAS the tail
 576                     pTail->m_pPrev.store( pNew, memory_model::memory_order_release )     ;           // Success, write prev
 577                     ++m_ItemCounter;
 578                     m_Stat.onEnqueue();
 579                     break ;     // Enqueue done!
 580                 }
 581                 guards.assign( 0, node_traits::to_value_ptr( pTail ) )   ;  // pTail has been changed by CAS above
 582                 m_Stat.onEnqueueRace();
 583                 bkoff();
 584             }
 585             return true;
 586         }
 587
 588         /// Dequeues a value from the queue
 589         /** @anchor cds_intrusive_OptimisticQueue_dequeue
 590             If the queue is empty the function returns \p nullptr
 591
 592             \par Warning
 593             The queue algorithm has following feature: when \p dequeue is called,
 594             the item returning is still queue's top, and previous top is disposed:
 595
 596             \code
 597             before dequeuing         Dequeue               after dequeuing
 598             +------------------+                           +------------------+
 599       Top ->|      Item 1      |  -> Dispose Item 1        |      Item 2      | <- Top
 600             +------------------+                           +------------------+
 601             |      Item 2      |  -> Return Item 2         |       ...        |
 602             +------------------+
 603             |       ...        |
 604             \endcode
 605
 606             \p dequeue function returns Item 2, that becomes new top of queue, and calls
 607             the disposer for Item 1, that was queue's top on function entry.
 608             Thus, you cannot manually delete item returned because it is still included in
 609             item sequence and it has valuable link field that must not be zeroed.
 610             The item may be deleted only in disposer call.
 611         */
 612         value_type * dequeue()
 613         {
 614             dequeue_result res;
 615             if ( do_dequeue( res )) {
 616                 dispose_result( res );
 617
 618                 return node_traits::to_value_ptr( *res.pNext );
 619             }
 620             return nullptr;
 621         }
 622
 623         /// Synonym for \p enqueue()
 624         bool push( value_type& val )
 625         {
 626             return enqueue( val );
 627         }
 628
 629         /// Synonym for \p dequeue()
 630         value_type * pop()
 631         {
 632             return dequeue();
 633         }
 634
 635         /// Checks if the queue is empty
 636         bool empty() const
 637         {
 638             return m_pTail.load(memory_model::memory_order_relaxed) == m_pHead.load(memory_model::memory_order_relaxed);
 639         }
 640
 641         /// Clear the stack
 642         /**
 643             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 644             The disposer defined in template \p Traits is called for each item
 645             that can be safely disposed.
 646         */
 647         void clear()
 648         {
 649             value_type * pv;
 650             while ( (pv = dequeue()) != nullptr );
 651         }
 652
 653         /// Returns queue's item count
 654         /**
 655             The value returned depends on \p optimistic_queue::traits::item_counter.
 656             For \p atomicity::empty_item_counter, this function always returns 0.
 657
 658             @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
 659             is empty. To check queue emptyness use \p empty() method.
 660         */
 661         size_t size() const
 662         {
 663             return m_ItemCounter.value();
 664         }
 665
 666         /// Returns refernce to internal statistics
 667         const stat& statistics() const
 668         {
 669             return m_Stat;
 670         }
 671     };
 672
 673 }}  // namespace cds::intrusive
 674
 675 #endif // #ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H