2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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 /// Synonym for \p cds::intrusive::mspriority_queue::monotonic_counter
53 typedef cds::intrusive::mspriority_queue::monotonic_counter monotonic_counter;
55 using cds::intrusive::mspriority_queue::stat;
56 using cds::intrusive::mspriority_queue::empty_stat;
57 using cds::intrusive::mspriority_queue::monotonic_counter;
60 /// MSPriorityQueue traits
62 The traits for \p %cds::container::MSPriorityQueue is the same as for
63 \p cds::intrusive::MSPriorityQueue (see \p cds::intrusive::mspriority_queue::traits)
64 plus some additional properties.
66 struct traits: public cds::intrusive::mspriority_queue::traits
68 /// The allocator use to allocate memory for values
69 typedef CDS_DEFAULT_ALLOCATOR allocator;
73 The move policy used in \p MSPriorityQueue::pop functions
75 Default is \p opt::v::assignment_move_policy.
77 typedef cds::opt::v::assignment_move_policy move_policy;
80 /// Metafunction converting option list to traits
83 - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer.
84 Default is \p %opt::v::initialized_dynamic_buffer.
85 You may specify any type of values for the buffer since at instantiation time
86 the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer.
87 - \p opt::compare - priority compare functor. No default functor is provided.
88 If the option is not specified, the \p opt::less is used.
89 - \p opt::less - specifies binary predicate used for priority compare. Default is \p std::less<T>.
90 - \p opt::lock_type - lock type. Default is \p cds::sync::spin.
91 - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield
92 - \p opt::allocator - allocator (like \p std::allocator) for the values of queue's items.
93 Default is \ref CDS_DEFAULT_ALLOCATOR
94 - \p opt::move_policy - policy for moving item's value. Default is \p opt::v::assignment_move_policy.
95 If the compiler supports move semantics it would be better to specify the move policy
96 based on the move semantics for type \p T.
97 - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead)
98 - \p opt::item_counter - an item counter type for \p MSPriorityQueue.
99 Available type: \p cds::bitop::bit_reverse_counter, \p mspriority_queue::monotonic_counter. See \p cds::intrusive::mspriority_queue::traits::item_counter for details.
101 template <typename... Options>
103 # ifdef CDS_DOXYGEN_INVOKED
104 typedef implementation_defined type ; ///< Metafunction result
106 typedef typename cds::opt::make_options<
107 typename cds::opt::find_type_traits< traits, Options... >::type
112 } // namespace mspriority_queue
114 /// Michael & Scott array-based lock-based concurrent priority queue heap
115 /** @ingroup cds_nonintrusive_priority_queue
117 - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
118 "An efficient algorithm for concurrent priority queue heaps"
120 \p %MSPriorityQueue augments the standard array-based heap data structure with
121 a mutual-exclusion lock on the heap's size and locks on each node in the heap.
122 Each node also has a tag that indicates whether
123 it is empty, valid, or in a transient state due to an update to the heap
124 by an inserting thread.
125 The algorithm allows concurrent insertions and deletions in opposite directions,
126 without risking deadlock and without the need for special server threads.
127 It also uses a "bit-reversal" technique to scatter accesses across the fringe
128 of the tree to reduce contention.
129 On large heaps the algorithm achieves significant performance improvements
130 over serialized single-lock algorithm, for various insertion/deletion
131 workloads. For small heaps it still performs well, but not as well as
132 single-lock algorithm.
135 - \p T - type to be stored in the list. The priority is a part of \p T type.
136 - \p Traits - the traits. See \p mspriority_queue::traits for explanation.
137 It is possible to declare option-based queue with \p mspriority_queue::make_traits
138 metafunction instead of \p Traits template argument.
140 template <typename T, class Traits = mspriority_queue::traits >
141 class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
144 typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
147 typedef T value_type ; ///< Value type stored in the queue
148 typedef Traits traits ; ///< Traits template parameter
150 typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
151 typedef typename base_class::lock_type lock_type; ///< heap's size lock type
152 typedef typename base_class::back_off back_off ; ///< Back-off strategy
153 typedef typename traits::stat stat; ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat
154 typedef typename traits::item_counter item_counter;///< Item counter type, see \p intrusive::mspriority_queue::traits::item_counter
155 typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
156 typedef typename traits::move_policy move_policy; ///< Move policy for type \p T
160 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
162 struct value_deleter {
163 void operator()( value_type * p ) const
165 cxx_allocator().Delete( p );
168 typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
172 /// Constructs empty priority queue
174 For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
176 MSPriorityQueue( size_t nCapacity )
177 : base_class( nCapacity )
180 /// Clears priority queue and destructs the object
186 /// Inserts an item into priority queue
188 If the priority queue is full, the function returns \p false,
189 no item has been added.
190 Otherwise, the function inserts the copy of \p val into the heap
193 The function use copy constructor to create new heap item from \p val.
195 bool push( value_type const& val )
197 scoped_ptr pVal( cxx_allocator().New( val ));
198 if ( base_class::push( *(pVal.get()) )) {
205 /// Inserts an item into the queue using a functor
207 \p Func is a functor called to create node.
208 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
210 cds::container::MSPriorityQueue< Foo > myQueue;
212 myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
215 template <typename Func>
216 bool push_with( Func f )
218 scoped_ptr pVal( cxx_allocator().New() );
220 if ( base_class::push( *pVal )) {
227 /// Inserts a item into priority queue
229 If the priority queue is full, the function returns \p false,
230 no item has been added.
231 Otherwise, the function inserts a new item created from \p args arguments
232 into the heap and returns \p true.
234 template <typename... Args>
235 bool emplace( Args&&... args )
237 scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
238 if ( base_class::push( *(pVal.get()) )) {
245 /// Extracts item with high priority
247 If the priority queue is empty, the function returns \p false.
248 Otherwise, it returns \p true and \p dest contains the copy of extracted item.
249 The item is deleted from the heap.
251 The function uses \ref move_policy to move extracted value from the heap's top
254 The function is equivalent of such call:
256 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
259 bool pop( value_type& dest )
261 return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
264 /// Extracts an item with high priority
266 If the priority queue is empty, the function returns \p false.
267 Otherwise, it returns \p true and \p dest contains the copy of extracted item.
268 The item is deleted from the heap.
270 \p Func is a functor called to copy popped value.
271 The functor takes one argument - a reference to removed node:
273 cds:container::MSPriorityQueue< Foo > myQueue;
275 myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
278 template <typename Func>
279 bool pop_with( Func f )
281 value_type * pVal = base_class::pop();
284 cxx_allocator().Delete( pVal );
290 /// Clears the queue (not atomic)
292 This function is not atomic, but thread-safe
296 base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
299 /// Clears the queue (not atomic)
301 This function is not atomic, but thread-safe.
303 For each item removed the functor \p f is called.
304 \p Func interface is:
308 void operator()( value_type& item );
312 template <typename Func>
313 void clear_with( Func f )
315 base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
318 /// Checks is the priority queue is empty
321 return base_class::empty();
324 /// Checks if the priority queue is full
327 return base_class::full();
330 /// Returns current size of priority queue
333 return base_class::size();
336 /// Return capacity of the priority queue
337 size_t capacity() const
339 return base_class::capacity();
342 /// Returns const reference to internal statistics
343 stat const& statistics() const
345 return base_class::statistics();
349 }} // namespace cds::container
351 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H