cds/intrusive/optimistic_queue.h

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