cds/container/moir_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-2016
   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_CONTAINER_MOIR_QUEUE_H
  32 #define CDSLIB_CONTAINER_MOIR_QUEUE_H
  33
  34 #include <memory>
  35 #include <cds/container/msqueue.h>
  36 #include <cds/intrusive/moir_queue.h>
  37
  38 namespace cds { namespace container {
  39
  40     //@cond
  41     namespace details {
  42         template <typename GC, typename T, typename Traits>
  43         struct make_moir_queue: public cds::container::details::make_msqueue< GC, T, Traits >
  44         {
  45             typedef cds::container::details::make_msqueue< GC, T, Traits > base_class;
  46             typedef cds::intrusive::MoirQueue< GC, typename base_class::node_type, typename base_class::intrusive_traits > type;
  47         };
  48     }
  49     //@endcond
  50
  51     /// A variation of Michael & Scott's lock-free queue
  52     /** @ingroup cds_nonintrusive_queue
  53         It is non-intrusive version of \p cds::intrusive::MoirQueue.
  54
  55         Template arguments:
  56         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
  57         - \p T - a type stored in the queue.
  58         - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
  59             metafunction to make your traits or just derive your traits from \p %msqueue::traits:
  60             \code
  61             struct myTraits: public cds::container::msqueue::traits {
  62                 typedef cds::intrusive::msqueue::stat<> stat;
  63                 typedef cds::atomicity::item_counter    item_counter;
  64             };
  65             typedef cds::container::MoirQueue< cds::gc::HP, Foo, myTraits > myQueue;
  66
  67             // Equivalent make_traits example:
  68             typedef cds::container::MoirQueue< cds::gc::HP, Foo,
  69                 typename cds::container::msqueue::make_traits<
  70                     cds::opt::stat< cds::container::msqueue::stat<> >,
  71                     cds::opt::item_counter< cds::atomicity::item_counter >
  72                 >::type
  73             > myQueue;
  74             \endcode
  75     */
  76     template <typename GC, typename T, typename Traits = cds::container::msqueue::traits >
  77     class MoirQueue:
  78 #ifdef CDS_DOXYGEN_INVOKED
  79         private intrusive::MoirQueue< GC, intrusive::msqueue::node< T >, Traits >
  80 #else
  81         private details::make_moir_queue< GC, T, Traits >::type
  82 #endif
  83     {
  84         //@cond
  85         typedef details::make_moir_queue< GC, T, Traits > maker;
  86         typedef typename maker::type base_class;
  87         //@endcond
  88
  89     public:
  90         /// Rebind template arguments
  91         template <typename GC2, typename T2, typename Traits2>
  92         struct rebind {
  93             typedef MoirQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
  94         };
  95
  96     public:
  97         typedef T value_type ; ///< Value type stored in the queue
  98         typedef typename base_class::gc                 gc;             ///< Garbage collector
  99         typedef typename base_class::back_off           back_off;       ///< Back-off strategy
 100         typedef typename maker::allocator_type          allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 101         typedef typename base_class::item_counter       item_counter;   ///< Item counting policy used
 102         typedef typename base_class::stat               stat;           ///< Internal statistics policy used
 103         typedef typename base_class::memory_model       memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 104
 105     protected:
 106         //@cond
 107         typedef typename maker::node_type  node_type;   ///< queue node type (derived from intrusive::msqueue::node)
 108
 109         typedef typename maker::cxx_allocator     cxx_allocator;
 110         typedef typename maker::node_deallocator  node_deallocator;   // deallocate node
 111         typedef typename base_class::node_traits  node_traits;
 112         //@endcond
 113
 114     protected:
 115         ///@cond
 116         static node_type * alloc_node()
 117         {
 118             return cxx_allocator().New();
 119         }
 120         static node_type * alloc_node( const value_type& val )
 121         {
 122             return cxx_allocator().New( val );
 123         }
 124         template <typename... Args>
 125         static node_type * alloc_node_move( Args&&... args )
 126         {
 127             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 128         }
 129         static void free_node( node_type * p )
 130         {
 131             node_deallocator()( p );
 132         }
 133
 134         struct node_disposer {
 135             void operator()( node_type * pNode )
 136             {
 137                 free_node( pNode );
 138             }
 139         };
 140         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 141         //@endcond
 142
 143     public:
 144         /// Initializes empty queue
 145         MoirQueue()
 146         {}
 147
 148         /// Destructor clears the queue
 149         ~MoirQueue()
 150         {}
 151
 152         /// Enqueues \p val value into the queue.
 153         /**
 154             The function makes queue node in dynamic memory calling copy constructor for \p val
 155             and then it calls intrusive::MoirQueue::enqueue.
 156             Returns \p true if success, \p false otherwise.
 157         */
 158         bool enqueue( value_type const& val )
 159         {
 160             scoped_node_ptr p( alloc_node(val) );
 161             if ( base_class::enqueue( *p )) {
 162                 p.release();
 163                 return true;
 164             }
 165             return false;
 166         }
 167
 168         /// Enqueues \p data to queue using a functor
 169         /**
 170             \p Func is a functor calling to create a new node.
 171             The functor should initialize creating node
 172             and it takes one argument - a reference to a new node of type \ref value_type :
 173             \code
 174             cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
 175             Bar bar;
 176             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 177             \endcode
 178         */
 179         template <typename Func>
 180         bool enqueue_with( Func f )
 181         {
 182             scoped_node_ptr p( alloc_node() );
 183             f( p->m_value );
 184             if ( base_class::enqueue( *p )) {
 185                 p.release();
 186                 return true;
 187             }
 188             return false;
 189         }
 190
 191         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 192         template <typename... Args>
 193         bool emplace( Args&&... args )
 194         {
 195             scoped_node_ptr p( alloc_node_move( std::forward<Args>( args )... ) );
 196             if ( base_class::enqueue( *p ) ) {
 197                 p.release();
 198                 return true;
 199             }
 200             return false;
 201         }
 202
 203         /// Synonym for \p enqueue() function
 204         bool push( value_type const& val )
 205         {
 206             return enqueue( val );
 207         }
 208
 209         /// Synonym for \p enqueue_with() function
 210         template <typename Func>
 211         bool push_with( Func f )
 212         {
 213             return enqueue_with( f );
 214         }
 215
 216         /// Dequeues a value from the queue
 217         /**
 218             If queue is not empty, the function returns \p true, \p dest contains copy of
 219             dequeued value. The assignment operator for type \ref value_type is invoked.
 220             If queue is empty, the function returns \p false, \p dest is unchanged.
 221         */
 222         bool dequeue( value_type& dest )
 223         {
 224             return dequeue_with( [&dest]( value_type& src ) { dest = src;  } );
 225         }
 226
 227         /// Dequeues a value using a functor
 228         /**
 229             \p Func is a functor called to copy dequeued value.
 230             The functor takes one argument - a reference to removed node:
 231             \code
 232             cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
 233             Bar bar;
 234             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 235             \endcode
 236             The functor is called only if the queue is not empty.
 237         */
 238         template <typename Func>
 239         bool dequeue_with( Func f )
 240         {
 241             typename base_class::dequeue_result res;
 242             if ( base_class::do_dequeue( res )) {
 243                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 244                 base_class::dispose_result( res );
 245                 return true;
 246             }
 247             return false;
 248         }
 249
 250         /// Synonym for \p dequeue() function
 251         bool pop( value_type& dest )
 252         {
 253             return dequeue( dest );
 254         }
 255
 256         /// Synonym for \p dequeue_with() function
 257         template <typename Func>
 258         bool pop_with( Func f )
 259         {
 260             return dequeue_with( f );
 261         }
 262
 263         /// Clear the queue
 264         /**
 265             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 266             The disposer defined in template \p Traits is called for each item
 267             that can be safely disposed.
 268         */
 269         void clear()
 270         {
 271             base_class::clear();
 272         }
 273
 274         /// Checks if the queue is empty
 275         bool empty() const
 276         {
 277             return base_class::empty();
 278         }
 279
 280         /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
 281         size_t size() const
 282         {
 283             return base_class::size();
 284         }
 285
 286         /// Returns refernce to internal statistics
 287         const stat& statistics() const
 288         {
 289             return base_class::statistics();
 290         }
 291
 292     };
 293
 294 }}  // namespace cds::container
 295
 296 #endif  // #ifndef CDSLIB_CONTAINER_MOIR_QUEUE_H
 297
 298