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/details/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 <typename... Options>
  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, Options... >::type
  61                 ,Options...
  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         };
 137         typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
 138         //@endcond
 139
 140     public:
 141         /// Constructs empty priority queue
 142         /**
 143             For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
 144         */
 145         MSPriorityQueue( size_t nCapacity )
 146             : base_class( nCapacity )
 147         {}
 148
 149         /// Clears priority queue and destructs the object
 150         ~MSPriorityQueue()
 151         {
 152             clear();
 153         }
 154
 155         /// Inserts a item into priority queue
 156         /**
 157             If the priority queue is full, the function returns \p false,
 158             no item has been added.
 159             Otherwise, the function inserts the copy of \p val into the heap
 160             and returns \p true.
 161
 162             The function use copy constructor to create new heap item from \p val.
 163         */
 164         bool push( value_type const& val )
 165         {
 166             scoped_ptr pVal( cxx_allocator().New( val ));
 167             if ( base_class::push( *(pVal.get()) )) {
 168                 pVal.release();
 169                 return true;
 170             }
 171             return false;
 172         }
 173
 174         /// Inserts a item into priority queue
 175         /**
 176             If the priority queue is full, the function returns \p false,
 177             no item has been added.
 178             Otherwise, the function inserts a new item created from \p args arguments
 179             into the heap and returns \p true.
 180         */
 181         template <typename... Args>
 182         bool emplace( Args&&... args )
 183         {
 184             scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
 185             if ( base_class::push( *(pVal.get()) )) {
 186                 pVal.release();
 187                 return true;
 188             }
 189             return false;
 190         }
 191
 192         /// Extracts item with high priority
 193         /**
 194             If the priority queue is empty, the function returns \p false.
 195             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 196             The item is deleted from the heap.
 197
 198             The function uses \ref move_policy to move extracted value from the heap's top
 199             to \p dest.
 200
 201             The function is equivalent of such call:
 202             \code
 203                 pop_with( dest, move_policy() );
 204             \endcode
 205         */
 206         bool pop( value_type& dest )
 207         {
 208             return pop_with( dest, move_policy() );
 209         }
 210
 211         /// Extracts item with high priority
 212         /**
 213             If the priority queue is empty, the function returns \p false.
 214             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 215             The item is deleted from the heap.
 216
 217             The function uses \p MoveFunc \p f to move extracted value from the heap's top
 218             to \p dest. The interface of \p MoveFunc is:
 219             \code
 220             struct move_functor {
 221                 void operator()( Q& dest, T& src );
 222             };
 223             \endcode
 224             In \p MoveFunc you may use move semantics for \p src argument
 225             since \p src will be destroyed.
 226         */
 227         template <typename Q, typename MoveFunc>
 228         bool pop_with( Q& dest, MoveFunc f )
 229         {
 230             value_type * pVal = base_class::pop();
 231             if ( pVal ) {
 232                 f( dest, *pVal );
 233                 cxx_allocator().Delete( pVal );
 234                 return true;
 235             }
 236             return false;
 237         }
 238
 239         /// Clears the queue (not atomic)
 240         /**
 241             This function is no atomic, but thread-safe
 242         */
 243         void clear()
 244         {
 245             base_class::clear_with( []( value_type& src ) { cxx_allocator().Delete( &src ); });
 246         }
 247
 248         /// Clears the queue (not atomic)
 249         /**
 250             This function is no atomic, but thread-safe.
 251
 252             For each item removed the functor \p f is called.
 253             \p Func interface is:
 254             \code
 255                 struct clear_functor
 256                 {
 257                     void operator()( value_type& item );
 258                 };
 259             \endcode
 260             A lambda function or a function pointer can be used as \p f.
 261         */
 262         template <typename Func>
 263         void clear_with( Func f )
 264         {
 265             base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
 266         }
 267
 268         /// Checks is the priority queue is empty
 269         bool empty() const
 270         {
 271             return base_class::empty();
 272         }
 273
 274         /// Checks if the priority queue is full
 275         bool full() const
 276         {
 277             return base_class::full();
 278         }
 279
 280         /// Returns current size of priority queue
 281         size_t size() const
 282         {
 283             return base_class::size();
 284         }
 285
 286         /// Return capacity of the priority queue
 287         size_t capacity() const
 288         {
 289             return base_class::capacity();
 290         }
 291
 292         /// Returns const reference to internal statistics
 293         stat const& statistics() const
 294         {
 295             return base_class::statistics();
 296         }
 297     };
 298
 299 }} // namespace cds::container
 300
 301 #endif // #ifndef __CDS_CONTAINER_MSPRIORITY_QUEUE_H