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