cds/container/mspriority_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_MSPRIORITY_QUEUE_H
   4 #define __CDS_CONTAINER_MSPRIORITY_QUEUE_H
   5
   6 #include <cds/container/base.h>
   7 #include <cds/intrusive/mspriority_queue.h>
   8 #include <cds/details/std/memory.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// MSPriorityQueue related definitions
  13     /** @ingroup cds_nonintrusive_helper
  14     */
  15     namespace mspriority_queue {
  16
  17 #ifdef CDS_DOXYGEN_INVOKED
  18         /// Synonym for cds::intrusive::mspriority_queue::stat
  19         typedef cds::intrusive::mspriority_queue::stat<> stat;
  20
  21         /// Synonym for cds::intrusive::mspriority_queue::empty_stat
  22         typedef cds::intrusive::mspriority_queue::empty_stat empty_stat;
  23 #else
  24         using cds::intrusive::mspriority_queue::stat;
  25         using cds::intrusive::mspriority_queue::empty_stat;
  26 #endif
  27
  28         /// Type traits for MSPriorityQueue
  29         /**
  30             The type traits for cds::container::MSPriorityQueue is the same as for
  31             cds::intrusive::MSPriorityQueue (see cds::intrusive::mspriority_queue::type_traits)
  32             plus some additional properties.
  33         */
  34         struct type_traits: public cds::intrusive::mspriority_queue::type_traits
  35         {
  36             /// The allocator use to allocate memory for values
  37             typedef CDS_DEFAULT_ALLOCATOR   allocator;
  38
  39             /// Move policy
  40             /**
  41                 The move policy used in MSPriorityQueue::pop functions
  42                 to move item's value.
  43                 Default is opt::v::assignment_move_policy.
  44             */
  45             typedef cds::opt::v::assignment_move_policy  move_policy;
  46         };
  47
  48         /// Metafunction converting option list to traits
  49         /**
  50             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
  51
  52             See \ref MSPriorityQueue, \ref type_traits, \ref cds::opt::make_options.
  53         */
  54         template <CDS_DECL_OPTIONS9>
  55         struct make_traits {
  56 #   ifdef CDS_DOXYGEN_INVOKED
  57             typedef implementation_defined type ;   ///< Metafunction result
  58 #   else
  59             typedef typename cds::opt::make_options<
  60                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS9 >::type
  61                 ,CDS_OPTIONS9
  62             >::type   type;
  63 #   endif
  64         };
  65     }   // namespace mspriority_queue
  66
  67     /// Michael & Scott array-based lock-based concurrent priority queue heap
  68     /** @ingroup cds_nonintrusive_priority_queue
  69         Source:
  70             - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
  71                 "An efficient algorithm for concurrent priority queue heaps"
  72
  73         \p %MSPriorityQueue augments the standard array-based heap data structure with
  74         a mutual-exclusion lock on the heap's size and locks on each node in the heap.
  75         Each node also has a tag that indicates whether
  76         it is empty, valid, or in a transient state due to an update to the heap
  77         by an inserting thread.
  78         The algorithm allows concurrent insertions and deletions in opposite directions,
  79         without risking deadlock and without the need for special server threads.
  80         It also uses a "bit-reversal" technique to scatter accesses across the fringe
  81         of the tree to reduce contention.
  82         On large heaps the algorithm achieves significant performance improvements
  83         over serialized single-lock algorithm, for various insertion/deletion
  84         workloads. For small heaps it still performs well, but not as well as
  85         single-lock algorithm.
  86
  87         Template parameters:
  88         - \p T - type to be stored in the list. The priority is a part of \p T type.
  89         - \p Traits - type traits. See mspriority_queue::type_traits for explanation.
  90
  91         It is possible to declare option-based queue with cds::container::mspriority_queue::make_traits
  92         metafunction instead of \p Traits template argument.
  93         Template argument list \p Options of \p %cds::container::mspriority_queue::make_traits metafunction are:
  94         - opt::buffer - the buffer type for heap array. Possible type are: opt::v::static_buffer, opt::v::dynamic_buffer.
  95             Default is \p %opt::v::dynamic_buffer.
  96             You may specify any type of values for the buffer since at instantiation time
  97             the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer.
  98         - opt::compare - priority compare functor. No default functor is provided.
  99             If the option is not specified, the opt::less is used.
 100         - opt::less - specifies binary predicate used for priority compare. Default is \p std::less<T>.
 101         - opt::lock_type - lock type. Default is cds::lock::Spin.
 102         - opt::back_off - back-off strategy. Default is cds::backoff::yield
 103         - opt::allocator - allocator (like \p std::allocator) for the values of queue's items.
 104             Default is \ref CDS_DEFAULT_ALLOCATOR
 105         - opt::move_policy - policy for moving item's value. Default is opt::v::assignment_move_policy.
 106             If the compiler supports move semantics it would be better to specify the move policy
 107             based on the move semantics for type \p T.
 108         - opt::stat - internal statistics. Available types: mspriority_queue::stat, mspriority_queue::empty_stat (the default)
 109     */
 110     template <typename T, class Traits>
 111     class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
 112     {
 113         //@cond
 114         typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
 115         //@endcond
 116     public:
 117         typedef T           value_type  ;   ///< Value type stored in the queue
 118         typedef Traits      traits      ;   ///< Traits template parameter
 119
 120         typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
 121         typedef typename base_class::lock_type lock_type; ///< heap's size lock type
 122         typedef typename base_class::back_off  back_off ; ///< Back-off strategy
 123         typedef typename base_class::stat          stat ; ///< internal statistics type
 124         typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
 125         typedef typename traits::move_policy move_policy; ///< Move policy for type \p T
 126
 127     protected:
 128         //@cond
 129         typedef cds::details::Allocator< value_type, allocator_type >  cxx_allocator;
 130
 131         struct value_deleter {
 132             void operator()( value_type * p ) const
 133             {
 134                 cxx_allocator().Delete( p );
 135             }
 136 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
 137             void operator()( value_type& p ) const
 138             {
 139                 cxx_allocator().Delete( &p );
 140             }
 141 #       endif
 142         };
 143         typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
 144
 145 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 146         template <typename Func>
 147         struct clear_wrapper
 148         {
 149             Func& func;
 150             clear_wrapper( Func& f ): func(f) {}
 151
 152             void operator()( value_type& src ) const
 153             {
 154                 cds::unref(func)( src );
 155                 value_deleter()( &src );
 156             }
 157         };
 158 #   endif
 159
 160         //@endcond
 161
 162     public:
 163         /// Constructs empty priority queue
 164         /**
 165             For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
 166         */
 167         MSPriorityQueue( size_t nCapacity )
 168             : base_class( nCapacity )
 169         {}
 170
 171         /// Clears priority queue and destructs the object
 172         ~MSPriorityQueue()
 173         {
 174             clear();
 175         }
 176
 177         /// Inserts a item into priority queue
 178         /**
 179             If the priority queue is full, the function returns \p false,
 180             no item has been added.
 181             Otherwise, the function inserts the copy of \p val into the heap
 182             and returns \p true.
 183
 184             The function use copy constructor to create new heap item from \p val.
 185         */
 186         bool push( value_type const& val )
 187         {
 188             scoped_ptr pVal( cxx_allocator().New( val ));
 189             if ( base_class::push( *(pVal.get()) )) {
 190                 pVal.release();
 191                 return true;
 192             }
 193             return false;
 194         }
 195
 196 #ifdef CDS_EMPLACE_SUPPORT
 197         /// Inserts a item into priority queue
 198         /**
 199             If the priority queue is full, the function returns \p false,
 200             no item has been added.
 201             Otherwise, the function inserts a new item created from \p args arguments
 202             into the heap and returns \p true.
 203
 204             The function is available only for compilers supporting variable template
 205             and move semantics C++11 feature.
 206         */
 207         template <typename... Args>
 208         bool emplace( Args&&... args )
 209         {
 210             scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
 211             if ( base_class::push( *(pVal.get()) )) {
 212                 pVal.release();
 213                 return true;
 214             }
 215             return false;
 216         }
 217 #endif
 218
 219         /// Extracts item with high priority
 220         /**
 221             If the priority queue is empty, the function returns \p false.
 222             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 223             The item is deleted from the heap.
 224
 225             The function uses \ref move_policy to move extracted value from the heap's top
 226             to \p dest.
 227
 228             The function is equivalent of such call:
 229             \code
 230                 pop_with( dest, move_policy() );
 231             \endcode
 232         */
 233         bool pop( value_type& dest )
 234         {
 235             return pop_with( dest, move_policy() );
 236         }
 237
 238         /// Extracts item with high priority
 239         /**
 240             If the priority queue is empty, the function returns \p false.
 241             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 242             The item is deleted from the heap.
 243
 244             The function uses \p MoveFunc \p f to move extracted value from the heap's top
 245             to \p dest. The interface of \p MoveFunc is:
 246             \code
 247             struct move_functor {
 248                 void operator()( Q& dest, T& src );
 249             };
 250             \endcode
 251             In \p MoveFunc you may use move semantics for \p src argument
 252             since \p src will be destroyed.
 253         */
 254         template <typename Q, typename MoveFunc>
 255         bool pop_with( Q& dest, MoveFunc f )
 256         {
 257             value_type * pVal = base_class::pop();
 258             if ( pVal ) {
 259                 cds::unref(f)( dest, *pVal );
 260                 cxx_allocator().Delete( pVal );
 261                 return true;
 262             }
 263             return false;
 264         }
 265
 266         /// Clears the queue (not atomic)
 267         /**
 268             This function is no atomic, but thread-safe
 269         */
 270         void clear()
 271         {
 272 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 273             base_class::clear_with( []( value_type& src ) { cxx_allocator().Delete( &src ); });
 274 #       else
 275             base_class::clear_with( value_deleter() );
 276 #       endif
 277         }
 278
 279         /// Clears the queue (not atomic)
 280         /**
 281             This function is no atomic, but thread-safe.
 282
 283             For each item removed the functor \p f is called.
 284             \p Func interface is:
 285             \code
 286                 struct clear_functor
 287                 {
 288                     void operator()( value_type& item );
 289                 };
 290             \endcode
 291             A lambda function or a function pointer can be used as \p f.
 292         */
 293         template <typename Func>
 294         void clear_with( Func f )
 295         {
 296 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 297             base_class::clear_with( [&f]( value_type& val ) { cds::unref(f)(val); value_deleter()( &val ); } );
 298 #       else
 299             clear_wrapper<Func> c(f);
 300             base_class::clear_with( cds::ref(c));
 301 #       endif
 302         }
 303
 304         /// Checks is the priority queue is empty
 305         bool empty() const
 306         {
 307             return base_class::empty();
 308         }
 309
 310         /// Checks if the priority queue is full
 311         bool full() const
 312         {
 313             return base_class::full();
 314         }
 315
 316         /// Returns current size of priority queue
 317         size_t size() const
 318         {
 319             return base_class::size();
 320         }
 321
 322         /// Return capacity of the priority queue
 323         size_t capacity() const
 324         {
 325             return base_class::capacity();
 326         }
 327
 328         /// Returns const reference to internal statistics
 329         stat const& statistics() const
 330         {
 331             return base_class::statistics();
 332         }
 333     };
 334
 335 }} // namespace cds::container
 336
 337 #endif // #ifndef __CDS_CONTAINER_MSPRIORITY_QUEUE_H