3 #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
4 #define CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
7 #include <cds/container/details/base.h>
8 #include <cds/intrusive/mspriority_queue.h>
10 namespace cds { namespace container {
12 /// MSPriorityQueue related definitions
13 /** @ingroup cds_nonintrusive_helper
15 namespace mspriority_queue {
17 #ifdef CDS_DOXYGEN_INVOKED
18 /// Synonym for cds::intrusive::mspriority_queue::stat
19 typedef cds::intrusive::mspriority_queue::stat<> stat;
21 /// Synonym for cds::intrusive::mspriority_queue::empty_stat
22 typedef cds::intrusive::mspriority_queue::empty_stat empty_stat;
24 using cds::intrusive::mspriority_queue::stat;
25 using cds::intrusive::mspriority_queue::empty_stat;
28 /// MSPriorityQueue traits
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.
34 struct traits: public cds::intrusive::mspriority_queue::traits
36 /// The allocator use to allocate memory for values
37 typedef CDS_DEFAULT_ALLOCATOR allocator;
41 The move policy used in \p MSPriorityQueue::pop functions
43 Default is \p opt::v::assignment_move_policy.
45 typedef cds::opt::v::assignment_move_policy move_policy;
48 /// Metafunction converting option list to traits
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)
67 template <typename... Options>
69 # ifdef CDS_DOXYGEN_INVOKED
70 typedef implementation_defined type ; ///< Metafunction result
72 typedef typename cds::opt::make_options<
73 typename cds::opt::find_type_traits< traits, Options... >::type
78 } // namespace mspriority_queue
80 /// Michael & Scott array-based lock-based concurrent priority queue heap
81 /** @ingroup cds_nonintrusive_priority_queue
83 - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
84 "An efficient algorithm for concurrent priority queue heaps"
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.
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.
106 template <typename T, class Traits = mspriority_queue::traits >
107 class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
110 typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
113 typedef T value_type ; ///< Value type stored in the queue
114 typedef Traits traits ; ///< Traits template parameter
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
125 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
127 struct value_deleter {
128 void operator()( value_type * p ) const
130 cxx_allocator().Delete( p );
133 typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
137 /// Constructs empty priority queue
139 For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
141 MSPriorityQueue( size_t nCapacity )
142 : base_class( nCapacity )
145 /// Clears priority queue and destructs the object
151 /// Inserts an item into priority queue
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
158 The function use copy constructor to create new heap item from \p val.
160 bool push( value_type const& val )
162 scoped_ptr pVal( cxx_allocator().New( val ));
163 if ( base_class::push( *(pVal.get()) )) {
170 /// Inserts an item into the queue using a functor
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 :
175 cds::container::MSPriorityQueue< Foo > myQueue;
177 myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
180 template <typename Func>
181 bool push_with( Func f )
183 scoped_ptr pVal( cxx_allocator().New() );
185 if ( base_class::push( *pVal )) {
192 /// Inserts a item into priority queue
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.
199 template <typename... Args>
200 bool emplace( Args&&... args )
202 scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
203 if ( base_class::push( *(pVal.get()) )) {
210 /// Extracts item with high priority
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.
216 The function uses \ref move_policy to move extracted value from the heap's top
219 The function is equivalent of such call:
221 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
224 bool pop( value_type& dest )
226 return pop_with( [&dest]( value_type& src ) { move_policy()(dest, src); } );
229 /// Extracts an item with high priority
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.
235 \p Func is a functor called to copy popped value.
236 The functor takes one argument - a reference to removed node:
238 cds:container::MSPriorityQueue< Foo > myQueue;
240 myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
243 template <typename Func>
244 bool pop_with( Func f )
246 value_type * pVal = base_class::pop();
249 cxx_allocator().Delete( pVal );
255 /// Clears the queue (not atomic)
257 This function is not atomic, but thread-safe
261 base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
264 /// Clears the queue (not atomic)
266 This function is not atomic, but thread-safe.
268 For each item removed the functor \p f is called.
269 \p Func interface is:
273 void operator()( value_type& item );
277 template <typename Func>
278 void clear_with( Func f )
280 base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
283 /// Checks is the priority queue is empty
286 return base_class::empty();
289 /// Checks if the priority queue is full
292 return base_class::full();
295 /// Returns current size of priority queue
298 return base_class::size();
301 /// Return capacity of the priority queue
302 size_t capacity() const
304 return base_class::capacity();
307 /// Returns const reference to internal statistics
308 stat const& statistics() const
310 return base_class::statistics();
314 }} // namespace cds::container
316 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H