cds/container/mspriority_queue.h

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