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             node() CDS_NOEXCEPT
  36             {
  37                 m_pPrev.store( nullptr, atomics::memory_order_release );
  38                 m_pNext.store( nullptr, atomics::memory_order_release );
  39             }
  40         };
  41
  42         //@cond
  43         struct default_hook {
  44             typedef cds::gc::default_gc gc;
  45             typedef opt::none           tag;
  46         };
  47         //@endcond
  48
  49         //@cond
  50         template < typename HookType, typename... Options>
  51         struct hook
  52         {
  53             typedef typename opt::make_options< default_hook, Options...>::type  options;
  54             typedef typename options::gc    gc;
  55             typedef typename options::tag   tag;
  56             typedef node<gc, tag> node_type;
  57             typedef HookType     hook_type;
  58         };
  59         //@endcond
  60
  61         /// Base hook
  62         /**
  63             \p Options are:
  64             - opt::gc - garbage collector used.
  65             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  66         */
  67         template < typename... Options >
  68         struct base_hook: public hook< opt::base_hook_tag, Options... >
  69         {};
  70
  71         /// Member hook
  72         /**
  73             \p MemberOffset specifies offset in bytes of \ref node member into your structure.
  74             Use \p offsetof macro to define \p MemberOffset
  75
  76             \p Options are:
  77             - opt::gc - garbage collector used.
  78             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  79         */
  80         template < size_t MemberOffset, typename... Options >
  81         struct member_hook: public hook< opt::member_hook_tag, Options... >
  82         {
  83             //@cond
  84             static const size_t c_nMemberOffset = MemberOffset;
  85             //@endcond
  86         };
  87
  88         /// Traits hook
  89         /**
  90             \p NodeTraits defines type traits for node.
  91             See \ref node_traits for \p NodeTraits interface description
  92
  93             \p Options are:
  94             - opt::gc - garbage collector used.
  95             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  96         */
  97         template <typename NodeTraits, typename... Options >
  98         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
  99         {
 100             //@cond
 101             typedef NodeTraits node_traits;
 102             //@endcond
 103         };
 104
 105         /// Check link
 106         template <typename Node>
 107         struct link_checker {
 108             //@cond
 109             typedef Node node_type;
 110             //@endcond
 111
 112             /// Checks if the link fields of node \p pNode is \p nullptr
 113             /**
 114                 An asserting is generated if \p pNode link fields is not \p nullptr
 115             */
 116             static void is_empty( const node_type * pNode )
 117             {
 118                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 119                 assert( pNode->m_pPrev.load( atomics::memory_order_relaxed ) == nullptr );
 120                 CDS_UNUSED( pNode );
 121             }
 122         };
 123
 124         /// Metafunction for selecting appropriate link checking policy
 125         template < typename Node, opt::link_check_type LinkType >
 126         struct get_link_checker
 127         {
 128             //@cond
 129             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 130             //@endcond
 131         };
 132
 133         //@cond
 134         template < typename Node >
 135         struct get_link_checker< Node, opt::always_check_link >
 136         {
 137             typedef link_checker<Node>  type;
 138         };
 139         template < typename Node >
 140         struct get_link_checker< Node, opt::debug_check_link >
 141         {
 142 #       ifdef _DEBUG
 143             typedef link_checker<Node>  type;
 144 #       else
 145             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 146 #       endif
 147         };
 148         //@endcond
 149
 150         /// OptimisticQueue internal statistics. May be used for debugging or profiling
 151         /**
 152             Template argument \p Counter defines type of counter.
 153             Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
 154             strict event counting.
 155             You may use stronger type of counter like as \p cds::atomicity::item_counter,
 156             or even integral type, for example, \p int.
 157         */
 158         template <typename Counter = cds::atomicity::event_counter >
 159         struct stat
 160         {
 161             typedef Counter     counter_type;   ///< Counter type
 162
 163             counter_type m_EnqueueCount;    ///< Enqueue call count
 164             counter_type m_DequeueCount;    ///< Dequeue call count
 165             counter_type m_EnqueueRace;     ///< Count of enqueue race conditions encountered
 166             counter_type m_DequeueRace;     ///< Count of dequeue race conditions encountered
 167             counter_type m_AdvanceTailError; ///< Count of "advance tail failed" events
 168             counter_type m_BadTail;         ///< Count of events "Tail is not pointed to the last item in the queue"
 169             counter_type m_FixListCount;    ///< Count of fix list event
 170             counter_type m_EmptyDequeue;    ///< Count of dequeue from empty queue
 171
 172             /// Register enqueue call
 173             void onEnqueue() { ++m_EnqueueCount; }
 174             /// Register dequeue call
 175             void onDequeue() { ++m_DequeueCount; }
 176             /// Register enqueue race event
 177             void onEnqueueRace() { ++m_EnqueueRace; }
 178             /// Register dequeue race event
 179             void onDequeueRace() { ++m_DequeueRace; }
 180             /// Register "advance tail failed" event
 181             void onAdvanceTailFailed() { ++m_AdvanceTailError; }
 182             /// Register event "Tail is not pointed to last item in the queue"
 183             void onBadTail() { ++m_BadTail; }
 184             /// Register fix list event
 185             void onFixList()    { ++m_FixListCount; }
 186             /// Register dequeuing from empty queue
 187             void onEmptyDequeue() { ++m_EmptyDequeue; }
 188
 189             //@cond
 190             void reset()
 191             {
 192                 m_EnqueueCount.reset();
 193                 m_DequeueCount.reset();
 194                 m_EnqueueRace.reset();
 195                 m_DequeueRace.reset();
 196                 m_AdvanceTailError.reset();
 197                 m_BadTail.reset();
 198                 m_FixListCount.reset();
 199                 m_EmptyDequeue.reset();
 200             }
 201
 202             stat& operator +=( stat const& s )
 203             {
 204                 m_EnqueueCount += s.m_EnqueueCount.get();
 205                 m_DequeueCount += s.m_DequeueCount.get();
 206                 m_EnqueueRace += s.m_EnqueueRace.get();
 207                 m_DequeueRace += s.m_DequeueRace.get();
 208                 m_AdvanceTailError += s.m_AdvanceTailError.get();
 209                 m_BadTail += s.m_BadTail.get();
 210                 m_FixListCount += s.m_FixListCount.get();
 211                 m_EmptyDequeue += s.m_EmptyDequeue.get();
 212
 213                 return *this;
 214             }
 215             //@endcond
 216         };
 217
 218         /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
 219         struct empty_stat
 220         {
 221             //@cond
 222             void onEnqueue()            const {}
 223             void onDequeue()            const {}
 224             void onEnqueueRace()        const {}
 225             void onDequeueRace()        const {}
 226             void onAdvanceTailFailed()  const {}
 227             void onBadTail()            const {}
 228             void onFixList()            const {}
 229             void onEmptyDequeue()       const {}
 230
 231             void reset() {}
 232             empty_stat& operator +=( empty_stat const& )
 233             {
 234                 return *this;
 235             }
 236             //@endcond
 237         };
 238
 239         /// OptimisticQueue default type traits
 240         struct traits
 241         {
 242             /// Back-off strategy
 243             typedef cds::backoff::empty             back_off;
 244
 245             /// Hook, possible types are \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook
 246             typedef optimistic_queue::base_hook<>   hook;
 247
 248             /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
 249             typedef opt::v::empty_disposer          disposer;
 250
 251             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 252             typedef cds::atomicity::empty_item_counter   item_counter;
 253
 254             /// C++ memory ordering model
 255             /**
 256                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 257                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 258             */
 259             typedef opt::v::relaxed_ordering        memory_model;
 260
 261             /// Internal statistics (by default, disabled)
 262             /**
 263                 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
 264                 user-provided class that supports \p %optimistic_queue::stat interface.
 265             */
 266             typedef optimistic_queue::empty_stat    stat;
 267
 268             /// Link checking, see \p cds::opt::link_checker
 269             static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
 270
 271             /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
 272             enum { alignment = opt::cache_line_alignment };
 273         };
 274
 275         /// Metafunction converting option list to \p optimistic_queue::traits
 276         /**
 277             Supported \p Options are:
 278
 279             - opt::hook - hook used. Possible hooks are: \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook.
 280                 If the option is not specified, \p %optimistic_queue::base_hook<> is used.
 281             - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
 282             - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
 283                 when dequeuing.
 284             - opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 285             - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
 286                 To enable item counting use \p cds::atomicity::item_counter
 287             - opt::stat - the type to gather internal statistics.
 288                 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
 289                 user-provided class that supports \p %optimistic_queue::stat interface.
 290                 Default is \p %optimistic_queue::empty_stat (internal statistics disabled).
 291             - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
 292             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 293                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 294
 295             Example: declare \p %OptimisticQueue with item counting and internal statistics
 296             \code
 297             typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
 298                 typename cds::intrusive::optimistic_queue::make_traits<
 299                     cds::intrusive::opt:hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
 300                     cds::opt::item_counte< cds::atomicity::item_counter >,
 301                     cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >
 302                 >::type
 303             > myQueue;
 304             \endcode
 305         */
 306         template <typename... Options>
 307         struct make_traits {
 308 #   ifdef CDS_DOXYGEN_INVOKED
 309             typedef implementation_defined type;   ///< Metafunction result
 310 #   else
 311             typedef typename cds::opt::make_options<
 312                 typename cds::opt::find_type_traits< traits, Options... >::type
 313                 , Options...
 314             >::type type;
 315 #   endif
 316         };
 317     }   // namespace optimistic_queue
 318
 319     /// Optimistic intruive lock-free queue
 320     /** @ingroup cds_intrusive_queue
 321         Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
 322             [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
 323
 324         Template arguments:
 325         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
 326         - \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,
 327             or it should have a member of type \p %optimistic_queue::node for \p optimistic_queue::member_hook,
 328             or it should be convertible to \p %optimistic_queue::node for \p optimistic_queue::traits_hook.
 329         - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
 330             metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
 331             \code
 332             struct myTraits: public cds::intrusive::optimistic_queue::traits {
 333                 typedef cds::intrusive::optimistic_queue::stat<> stat;
 334                 typedef cds::atomicity::item_counter    item_counter;
 335             };
 336             typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
 337
 338             // Equivalent make_traits example:
 339             typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
 340                 typename cds::intrusive::optimistic_queue::make_traits<
 341                     cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
 342                     cds::opt::item_counter< cds::atomicity::item_counter >
 343                 >::type
 344             > myQueue;
 345             \endcode
 346
 347         Garbage collecting schema \p GC must be consistent with the optimistic_queue::node GC.
 348
 349         \par About item disposing
 350         The optimistic queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
 351         the standpoint of the algo. See \p dequeue() function for explanation.
 352
 353         \par Examples
 354         \code
 355         #include <cds/gc/hp.h>
 356         #include <cds/intrusive/optimistic_queue.h>
 357
 358         namespace ci = cds::inrtusive;
 359         typedef cds::gc::HP hp_gc;
 360
 361         // Optimistic queue with Hazard Pointer garbage collector, base hook + item counter:
 362         struct Foo: public ci::optimistic_queue::node< hp_gc >
 363         {
 364             // Your data
 365             ...
 366         };
 367
 368         typedef ci::OptimisticQueue< hp_gc,
 369             Foo,
 370             typename ci::optimistic_queue::make_traits<
 371                 ci::opt::hook<
 372                     ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
 373                 >
 374                 ,cds::opt::item_counter< cds::atomicity::item_counter >
 375             >::type
 376         > FooQueue;
 377
 378         // Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
 379         struct Bar
 380         {
 381             // Your data
 382             ...
 383             ci::optimistic_queue::node< hp_gc > hMember;
 384         };
 385
 386         typedef ci::OptimisticQueue< hp_gc,
 387             Bar,
 388             typename ci::optimistic_queue::make_traits<
 389                 ci::opt::hook<
 390                     ci::optimistic_queue::member_hook<
 391                         offsetof(Bar, hMember)
 392                         ,ci::opt::gc< hp_gc >
 393                     >
 394                 >
 395             >::type
 396         > BarQueue;
 397         \endcode
 398     */
 399     template <typename GC, typename T, typename Traits = optimistic_queue::traits >
 400     class OptimisticQueue
 401     {
 402     public:
 403         typedef GC gc;          ///< Garbage collector
 404         typedef T  value_type;  ///< type of value to be stored in the queue
 405         typedef Traits traits;  ///< Queue traits
 406
 407         typedef typename traits::hook       hook;       ///< hook type
 408         typedef typename hook::node_type    node_type;  ///< node type
 409         typedef typename traits::disposer   disposer;   ///< disposer used
 410         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;    ///< node traits
 411         typedef typename optimistic_queue::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
 412         typedef typename traits::back_off  back_off;        ///< back-off strategy
 413         typedef typename traits::item_counter item_counter; ///< Item counting policy used
 414         typedef typename traits::memory_model  memory_model;///< Memory ordering. See cds::opt::memory_model option
 415         typedef typename traits::stat      stat;            ///< Internal statistics policy used
 416
 417         /// Rebind template arguments
 418         template <typename GC2, typename T2, typename Traits2>
 419         struct rebind {
 420             typedef OptimisticQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
 421         };
 422
 423     protected:
 424         //@cond
 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_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
 464                 pTail = res.guards.protect( 1, m_pTail, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
 465                 assert( pHead != nullptr );
 466                 pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
 467
 468                 if ( pHead == m_pHead.load(memory_model::memory_order_acquire)) {
 469                     if ( pTail != pHead ) {
 470                         if ( pFirstNodePrev == nullptr
 471                           || pFirstNodePrev->m_pNext.load(memory_model::memory_order_acquire) != 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_type * p) -> value_type * { return node_traits::to_value_ptr(p);});
 514                 if ( pHead != m_pHead.load(memory_model::memory_order_acquire))
 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_type * p) -> value_type * {return node_traits::to_value_ptr(p);} );   // 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