gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/intrusive/optimistic_queue.h

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