2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
32 #define CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
35 #include <cds/container/details/base.h>
36 #include <cds/intrusive/mspriority_queue.h>
38 namespace cds { namespace container {
40 /// MSPriorityQueue related definitions
41 /** @ingroup cds_nonintrusive_helper
43 namespace mspriority_queue {
45 #ifdef CDS_DOXYGEN_INVOKED
46 /// Synonym for \p cds::intrusive::mspriority_queue::stat
47 typedef cds::intrusive::mspriority_queue::stat<> stat;
49 /// Synonym for \p cds::intrusive::mspriority_queue::empty_stat
50 typedef cds::intrusive::mspriority_queue::empty_stat empty_stat;
52 using cds::intrusive::mspriority_queue::stat;
53 using cds::intrusive::mspriority_queue::empty_stat;
56 /// MSPriorityQueue traits
58 The traits for \p %cds::container::MSPriorityQueue is the same as for
59 \p cds::intrusive::MSPriorityQueue (see \p cds::intrusive::mspriority_queue::traits)
60 plus some additional properties.
62 struct traits: public cds::intrusive::mspriority_queue::traits
64 /// The allocator use to allocate memory for values
65 typedef CDS_DEFAULT_ALLOCATOR allocator;
69 The move policy used in \p MSPriorityQueue::pop() function to move item's value.
70 Default is \p opt::v::assignment_move_policy.
72 typedef cds::opt::v::assignment_move_policy move_policy;
75 /// Metafunction converting option list to traits
78 - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer.
79 Default is \p %opt::v::initialized_dynamic_buffer.
80 You may specify any type of values for the buffer since at instantiation time
81 the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer.
82 - \p opt::compare - priority compare functor. No default functor is provided.
83 If the option is not specified, the \p opt::less is used.
84 - \p opt::less - specifies binary predicate used for priority compare. Default is \p std::less<T>.
85 - \p opt::lock_type - lock type. Default is \p cds::sync::spin.
86 - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield
87 - \p opt::allocator - allocator (like \p std::allocator) for the values of queue's items.
88 Default is \ref CDS_DEFAULT_ALLOCATOR
89 - \p opt::move_policy - policy for moving item's value. Default is \p opt::v::assignment_move_policy.
90 If the compiler supports move semantics it would be better to specify the move policy
91 based on the move semantics for type \p T.
92 - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead)
94 template <typename... Options>
96 # ifdef CDS_DOXYGEN_INVOKED
97 typedef implementation_defined type ; ///< Metafunction result
99 typedef typename cds::opt::make_options<
100 typename cds::opt::find_type_traits< traits, Options... >::type
105 } // namespace mspriority_queue
107 /// Michael & Scott array-based lock-based concurrent priority queue heap
108 /** @ingroup cds_nonintrusive_priority_queue
110 - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
111 "An efficient algorithm for concurrent priority queue heaps"
113 \p %MSPriorityQueue augments the standard array-based heap data structure with
114 a mutual-exclusion lock on the heap's size and locks on each node in the heap.
115 Each node also has a tag that indicates whether
116 it is empty, valid, or in a transient state due to an update to the heap
117 by an inserting thread.
118 The algorithm allows concurrent insertions and deletions in opposite directions,
119 without risking deadlock and without the need for special server threads.
120 It also uses a "bit-reversal" technique to scatter accesses across the fringe
121 of the tree to reduce contention.
122 On large heaps the algorithm achieves significant performance improvements
123 over serialized single-lock algorithm, for various insertion/deletion
124 workloads. For small heaps it still performs well, but not as well as
125 single-lock algorithm.
128 - \p T - type to be stored in the list. The priority is a part of \p T type.
129 - \p Traits - the traits. See \p mspriority_queue::traits for explanation.
130 It is possible to declare option-based queue with \p mspriority_queue::make_traits
131 metafunction instead of \p Traits template argument.
133 template <typename T, class Traits = mspriority_queue::traits >
134 class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
137 typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
140 typedef T value_type ; ///< Value type stored in the queue
141 typedef Traits traits ; ///< Traits template parameter
143 typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
144 typedef typename base_class::lock_type lock_type; ///< heap's size lock type
145 typedef typename base_class::back_off back_off ; ///< Back-off strategy
146 typedef typename traits::stat stat; ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat
147 typedef typename base_class::item_counter item_counter;///< Item counter type
148 typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
149 typedef typename traits::move_policy move_policy; ///< Move policy for type \p T
153 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
155 struct value_deleter {
156 void operator()( value_type * p ) const
158 cxx_allocator().Delete( p );
161 typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
165 /// Constructs empty priority queue
167 For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
169 MSPriorityQueue( size_t nCapacity )
170 : base_class( nCapacity )
173 /// Clears priority queue and destructs the object
179 /// Inserts an item into priority queue
181 If the priority queue is full, the function returns \p false,
182 no item has been added.
183 Otherwise, the function inserts the copy of \p val into the heap
186 The function use copy constructor to create new heap item from \p val.
188 bool push( value_type const& val )
190 scoped_ptr pVal( cxx_allocator().New( val ));
191 if ( base_class::push( *(pVal.get()))) {
198 /// Inserts an item into the queue using a functor
200 \p Func is a functor called to create node.
201 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
203 cds::container::MSPriorityQueue< Foo > myQueue;
205 myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
208 template <typename Func>
209 bool push_with( Func f )
211 scoped_ptr pVal( cxx_allocator().New());
213 if ( base_class::push( *pVal )) {
220 /// Inserts a item into priority queue
222 If the priority queue is full, the function returns \p false,
223 no item has been added.
224 Otherwise, the function inserts a new item created from \p args arguments
225 into the heap and returns \p true.
227 template <typename... Args>
228 bool emplace( Args&&... args )
230 scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
231 if ( base_class::push( *(pVal.get()))) {
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 \ref move_policy to move extracted value from the heap's top
247 The function is equivalent of such call:
249 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
252 bool pop( value_type& dest )
254 return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
257 /// Extracts an item with high priority
259 If the priority queue is empty, the function returns \p false.
260 Otherwise, it returns \p true and \p dest contains the copy of extracted item.
261 The item is deleted from the heap.
263 \p Func is a functor called to copy popped value.
264 The functor takes one argument - a reference to removed node:
266 cds:container::MSPriorityQueue< Foo > myQueue;
268 myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
271 template <typename Func>
272 bool pop_with( Func f )
274 value_type * pVal = base_class::pop();
277 cxx_allocator().Delete( pVal );
283 /// Clears the queue (not atomic)
285 This function is not atomic, but thread-safe
289 base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
292 /// Clears the queue (not atomic)
294 This function is not atomic, but thread-safe.
296 For each item removed the functor \p f is called.
297 \p Func interface is:
301 void operator()( value_type& item );
305 template <typename Func>
306 void clear_with( Func f )
308 base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
311 /// Checks is the priority queue is empty
314 return base_class::empty();
317 /// Checks if the priority queue is full
320 return base_class::full();
323 /// Returns current size of priority queue
326 return base_class::size();
329 /// Return capacity of the priority queue
330 size_t capacity() const
332 return base_class::capacity();
335 /// Returns const reference to internal statistics
336 stat const& statistics() const
338 return base_class::statistics();
342 }} // namespace cds::container
344 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H