3 #ifndef __CDS_CONTAINER_MSPRIORITY_QUEUE_H
4 #define __CDS_CONTAINER_MSPRIORITY_QUEUE_H
6 #include <cds/container/base.h>
7 #include <cds/intrusive/mspriority_queue.h>
8 #include <cds/details/std/memory.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 /// Type traits for MSPriorityQueue
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.
34 struct type_traits: public cds::intrusive::mspriority_queue::type_traits
36 /// The allocator use to allocate memory for values
37 typedef CDS_DEFAULT_ALLOCATOR allocator;
41 The move policy used in MSPriorityQueue::pop functions
43 Default is opt::v::assignment_move_policy.
45 typedef cds::opt::v::assignment_move_policy move_policy;
48 /// Metafunction converting option list to traits
50 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
52 See \ref MSPriorityQueue, \ref type_traits, \ref cds::opt::make_options.
54 template <CDS_DECL_OPTIONS9>
56 # ifdef CDS_DOXYGEN_INVOKED
57 typedef implementation_defined type ; ///< Metafunction result
59 typedef typename cds::opt::make_options<
60 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS9 >::type
65 } // namespace mspriority_queue
67 /// Michael & Scott array-based lock-based concurrent priority queue heap
68 /** @ingroup cds_nonintrusive_priority_queue
70 - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
71 "An efficient algorithm for concurrent priority queue heaps"
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.
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.
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)
110 template <typename T, class Traits>
111 class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
114 typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
117 typedef T value_type ; ///< Value type stored in the queue
118 typedef Traits traits ; ///< Traits template parameter
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
129 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
131 struct value_deleter {
132 void operator()( value_type * p ) const
134 cxx_allocator().Delete( p );
136 # ifndef CDS_CXX11_LAMBDA_SUPPORT
137 void operator()( value_type& p ) const
139 cxx_allocator().Delete( &p );
143 typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
145 # ifndef CDS_CXX11_LAMBDA_SUPPORT
146 template <typename Func>
150 clear_wrapper( Func& f ): func(f) {}
152 void operator()( value_type& src ) const
154 cds::unref(func)( src );
155 value_deleter()( &src );
163 /// Constructs empty priority queue
165 For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
167 MSPriorityQueue( size_t nCapacity )
168 : base_class( nCapacity )
171 /// Clears priority queue and destructs the object
177 /// Inserts a item into priority queue
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
184 The function use copy constructor to create new heap item from \p val.
186 bool push( value_type const& val )
188 scoped_ptr pVal( cxx_allocator().New( val ));
189 if ( base_class::push( *(pVal.get()) )) {
196 #ifdef CDS_EMPLACE_SUPPORT
197 /// Inserts a item into priority queue
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.
204 The function is available only for compilers supporting variable template
205 and move semantics C++11 feature.
207 template <typename... Args>
208 bool emplace( Args&&... args )
210 scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
211 if ( base_class::push( *(pVal.get()) )) {
219 /// Extracts item with high priority
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.
225 The function uses \ref move_policy to move extracted value from the heap's top
228 The function is equivalent of such call:
230 pop_with( dest, move_policy() );
233 bool pop( value_type& dest )
235 return pop_with( dest, move_policy() );
238 /// Extracts item with high priority
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.
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:
247 struct move_functor {
248 void operator()( Q& dest, T& src );
251 In \p MoveFunc you may use move semantics for \p src argument
252 since \p src will be destroyed.
254 template <typename Q, typename MoveFunc>
255 bool pop_with( Q& dest, MoveFunc f )
257 value_type * pVal = base_class::pop();
259 cds::unref(f)( dest, *pVal );
260 cxx_allocator().Delete( pVal );
266 /// Clears the queue (not atomic)
268 This function is no atomic, but thread-safe
272 # ifdef CDS_CXX11_LAMBDA_SUPPORT
273 base_class::clear_with( []( value_type& src ) { cxx_allocator().Delete( &src ); });
275 base_class::clear_with( value_deleter() );
279 /// Clears the queue (not atomic)
281 This function is no atomic, but thread-safe.
283 For each item removed the functor \p f is called.
284 \p Func interface is:
288 void operator()( value_type& item );
291 A lambda function or a function pointer can be used as \p f.
293 template <typename Func>
294 void clear_with( Func f )
296 # ifdef CDS_CXX11_LAMBDA_SUPPORT
297 base_class::clear_with( [&f]( value_type& val ) { cds::unref(f)(val); value_deleter()( &val ); } );
299 clear_wrapper<Func> c(f);
300 base_class::clear_with( cds::ref(c));
304 /// Checks is the priority queue is empty
307 return base_class::empty();
310 /// Checks if the priority queue is full
313 return base_class::full();
316 /// Returns current size of priority queue
319 return base_class::size();
322 /// Return capacity of the priority queue
323 size_t capacity() const
325 return base_class::capacity();
328 /// Returns const reference to internal statistics
329 stat const& statistics() const
331 return base_class::statistics();
335 }} // namespace cds::container
337 #endif // #ifndef __CDS_CONTAINER_MSPRIORITY_QUEUE_H