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