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 functions
71 Default is \p opt::v::assignment_move_policy.
73 typedef cds::opt::v::assignment_move_policy move_policy;
76 /// Metafunction converting option list to traits
79 - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer.
80 Default is \p %opt::v::initialized_dynamic_buffer.
81 You may specify any type of values for the buffer since at instantiation time
82 the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer.
83 - \p opt::compare - priority compare functor. No default functor is provided.
84 If the option is not specified, the \p opt::less is used.
85 - \p opt::less - specifies binary predicate used for priority compare. Default is \p std::less<T>.
86 - \p opt::lock_type - lock type. Default is \p cds::sync::spin.
87 - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield
88 - \p opt::allocator - allocator (like \p std::allocator) for the values of queue's items.
89 Default is \ref CDS_DEFAULT_ALLOCATOR
90 - \p opt::move_policy - policy for moving item's value. Default is \p opt::v::assignment_move_policy.
91 If the compiler supports move semantics it would be better to specify the move policy
92 based on the move semantics for type \p T.
93 - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead)
95 template <typename... Options>
97 # ifdef CDS_DOXYGEN_INVOKED
98 typedef implementation_defined type ; ///< Metafunction result
100 typedef typename cds::opt::make_options<
101 typename cds::opt::find_type_traits< traits, Options... >::type
106 } // namespace mspriority_queue
108 /// Michael & Scott array-based lock-based concurrent priority queue heap
109 /** @ingroup cds_nonintrusive_priority_queue
111 - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
112 "An efficient algorithm for concurrent priority queue heaps"
114 \p %MSPriorityQueue augments the standard array-based heap data structure with
115 a mutual-exclusion lock on the heap's size and locks on each node in the heap.
116 Each node also has a tag that indicates whether
117 it is empty, valid, or in a transient state due to an update to the heap
118 by an inserting thread.
119 The algorithm allows concurrent insertions and deletions in opposite directions,
120 without risking deadlock and without the need for special server threads.
121 It also uses a "bit-reversal" technique to scatter accesses across the fringe
122 of the tree to reduce contention.
123 On large heaps the algorithm achieves significant performance improvements
124 over serialized single-lock algorithm, for various insertion/deletion
125 workloads. For small heaps it still performs well, but not as well as
126 single-lock algorithm.
129 - \p T - type to be stored in the list. The priority is a part of \p T type.
130 - \p Traits - the traits. See \p mspriority_queue::traits for explanation.
131 It is possible to declare option-based queue with \p mspriority_queue::make_traits
132 metafunction instead of \p Traits template argument.
134 template <typename T, class Traits = mspriority_queue::traits >
135 class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
138 typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
141 typedef T value_type ; ///< Value type stored in the queue
142 typedef Traits traits ; ///< Traits template parameter
144 typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
145 typedef typename base_class::lock_type lock_type; ///< heap's size lock type
146 typedef typename base_class::back_off back_off ; ///< Back-off strategy
147 typedef typename traits::stat stat; ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat
148 typedef typename base_class::item_counter item_counter;///< Item counter type
149 typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
150 typedef typename traits::move_policy move_policy; ///< Move policy for type \p T
154 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
156 struct value_deleter {
157 void operator()( value_type * p ) const
159 cxx_allocator().Delete( p );
162 typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
166 /// Constructs empty priority queue
168 For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
170 MSPriorityQueue( size_t nCapacity )
171 : base_class( nCapacity )
174 /// Clears priority queue and destructs the object
180 /// Inserts an item into priority queue
182 If the priority queue is full, the function returns \p false,
183 no item has been added.
184 Otherwise, the function inserts the copy of \p val into the heap
187 The function use copy constructor to create new heap item from \p val.
189 bool push( value_type const& val )
191 scoped_ptr pVal( cxx_allocator().New( val ));
192 if ( base_class::push( *(pVal.get()))) {
199 /// Inserts an item into the queue using a functor
201 \p Func is a functor called to create node.
202 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
204 cds::container::MSPriorityQueue< Foo > myQueue;
206 myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
209 template <typename Func>
210 bool push_with( Func f )
212 scoped_ptr pVal( cxx_allocator().New());
214 if ( base_class::push( *pVal )) {
221 /// Inserts a item into priority queue
223 If the priority queue is full, the function returns \p false,
224 no item has been added.
225 Otherwise, the function inserts a new item created from \p args arguments
226 into the heap and returns \p true.
228 template <typename... Args>
229 bool emplace( Args&&... args )
231 scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
232 if ( base_class::push( *(pVal.get()))) {
239 /// Extracts item with high priority
241 If the priority queue is empty, the function returns \p false.
242 Otherwise, it returns \p true and \p dest contains the copy of extracted item.
243 The item is deleted from the heap.
245 The function uses \ref move_policy to move extracted value from the heap's top
248 The function is equivalent of such call:
250 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
253 bool pop( value_type& dest )
255 return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
258 /// Extracts an item with high priority
260 If the priority queue is empty, the function returns \p false.
261 Otherwise, it returns \p true and \p dest contains the copy of extracted item.
262 The item is deleted from the heap.
264 \p Func is a functor called to copy popped value.
265 The functor takes one argument - a reference to removed node:
267 cds:container::MSPriorityQueue< Foo > myQueue;
269 myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
272 template <typename Func>
273 bool pop_with( Func f )
275 value_type * pVal = base_class::pop();
278 cxx_allocator().Delete( pVal );
284 /// Clears the queue (not atomic)
286 This function is not atomic, but thread-safe
290 base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
293 /// Clears the queue (not atomic)
295 This function is not atomic, but thread-safe.
297 For each item removed the functor \p f is called.
298 \p Func interface is:
302 void operator()( value_type& item );
306 template <typename Func>
307 void clear_with( Func f )
309 base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
312 /// Checks is the priority queue is empty
315 return base_class::empty();
318 /// Checks if the priority queue is full
321 return base_class::full();
324 /// Returns current size of priority queue
327 return base_class::size();
330 /// Return capacity of the priority queue
331 size_t capacity() const
333 return base_class::capacity();
336 /// Returns const reference to internal statistics
337 stat const& statistics() const
339 return base_class::statistics();
343 }} // namespace cds::container
345 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H