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 <memory>
   7 #include <cds/container/base.h>
   8 #include <cds/intrusive/mspriority_queue.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         /// Inserts a item into priority queue
 197         /**
 198             If the priority queue is full, the function returns \p false,
 199             no item has been added.
 200             Otherwise, the function inserts a new item created from \p args arguments
 201             into the heap and returns \p true.
 202         */
 203         template <typename... Args>
 204         bool emplace( Args&&... args )
 205         {
 206             scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
 207             if ( base_class::push( *(pVal.get()) )) {
 208                 pVal.release();
 209                 return true;
 210             }
 211             return false;
 212         }
 213
 214         /// Extracts item with high priority
 215         /**
 216             If the priority queue is empty, the function returns \p false.
 217             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 218             The item is deleted from the heap.
 219
 220             The function uses \ref move_policy to move extracted value from the heap's top
 221             to \p dest.
 222
 223             The function is equivalent of such call:
 224             \code
 225                 pop_with( dest, move_policy() );
 226             \endcode
 227         */
 228         bool pop( value_type& dest )
 229         {
 230             return pop_with( dest, move_policy() );
 231         }
 232
 233         /// Extracts item with high priority
 234         /**
 235             If the priority queue is empty, the function returns \p false.
 236             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 237             The item is deleted from the heap.
 238
 239             The function uses \p MoveFunc \p f to move extracted value from the heap's top
 240             to \p dest. The interface of \p MoveFunc is:
 241             \code
 242             struct move_functor {
 243                 void operator()( Q& dest, T& src );
 244             };
 245             \endcode
 246             In \p MoveFunc you may use move semantics for \p src argument
 247             since \p src will be destroyed.
 248         */
 249         template <typename Q, typename MoveFunc>
 250         bool pop_with( Q& dest, MoveFunc f )
 251         {
 252             value_type * pVal = base_class::pop();
 253             if ( pVal ) {
 254                 cds::unref(f)( dest, *pVal );
 255                 cxx_allocator().Delete( pVal );
 256                 return true;
 257             }
 258             return false;
 259         }
 260
 261         /// Clears the queue (not atomic)
 262         /**
 263             This function is no atomic, but thread-safe
 264         */
 265         void clear()
 266         {
 267 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 268             base_class::clear_with( []( value_type& src ) { cxx_allocator().Delete( &src ); });
 269 #       else
 270             base_class::clear_with( value_deleter() );
 271 #       endif
 272         }
 273
 274         /// Clears the queue (not atomic)
 275         /**
 276             This function is no atomic, but thread-safe.
 277
 278             For each item removed the functor \p f is called.
 279             \p Func interface is:
 280             \code
 281                 struct clear_functor
 282                 {
 283                     void operator()( value_type& item );
 284                 };
 285             \endcode
 286             A lambda function or a function pointer can be used as \p f.
 287         */
 288         template <typename Func>
 289         void clear_with( Func f )
 290         {
 291 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 292             base_class::clear_with( [&f]( value_type& val ) { cds::unref(f)(val); value_deleter()( &val ); } );
 293 #       else
 294             clear_wrapper<Func> c(f);
 295             base_class::clear_with( cds::ref(c));
 296 #       endif
 297         }
 298
 299         /// Checks is the priority queue is empty
 300         bool empty() const
 301         {
 302             return base_class::empty();
 303         }
 304
 305         /// Checks if the priority queue is full
 306         bool full() const
 307         {
 308             return base_class::full();
 309         }
 310
 311         /// Returns current size of priority queue
 312         size_t size() const
 313         {
 314             return base_class::size();
 315         }
 316
 317         /// Return capacity of the priority queue
 318         size_t capacity() const
 319         {
 320             return base_class::capacity();
 321         }
 322
 323         /// Returns const reference to internal statistics
 324         stat const& statistics() const
 325         {
 326             return base_class::statistics();
 327         }
 328     };
 329
 330 }} // namespace cds::container
 331
 332 #endif // #ifndef __CDS_CONTAINER_MSPRIORITY_QUEUE_H