3 #ifndef CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H
4 #define CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H
6 #include <cds/algo/flat_combining.h>
7 #include <cds/algo/elimination_opt.h>
10 namespace cds { namespace container {
12 /// FCPriorityQueue related definitions
13 /** @ingroup cds_nonintrusive_helper
17 /// FCPriorityQueue internal statistics
18 template <typename Counter = cds::atomicity::event_counter >
19 struct stat: public cds::algo::flat_combining::stat<Counter>
21 typedef cds::algo::flat_combining::stat<Counter> flat_combining_stat; ///< Flat-combining statistics
22 typedef typename flat_combining_stat::counter_type counter_type; ///< Counter type
24 counter_type m_nPush ; ///< Count of push operations
25 counter_type m_nPushMove ; ///< Count of push operations with move semantics
26 counter_type m_nPop ; ///< Count of success pop operations
27 counter_type m_nFailedPop; ///< Count of failed pop operations (pop from empty queue)
30 void onPush() { ++m_nPush; }
31 void onPushMove() { ++m_nPushMove; }
32 void onPop( bool bFailed ) { if ( bFailed ) ++m_nFailedPop; else ++m_nPop; }
36 /// FCPriorityQueue dummy statistics, no overhead
37 struct empty_stat: public cds::algo::flat_combining::empty_stat
46 /// FCPriorityQueue traits
47 struct traits: public cds::algo::flat_combining::traits
49 typedef empty_stat stat; ///< Internal statistics
52 /// Metafunction converting option list to traits
55 - \p opt::lock_type - mutex type, default is \p cds::sync::spin
56 - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::delay_of<2>
57 - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
58 - \p opt::stat - internal statistics, possible type: \p fcpqueue::stat, \p fcpqueue::empty_stat (the default)
59 - \p opt::memory_model - C++ memory ordering model.
60 List of all available memory ordering see \p opt::memory_model.
61 Default is \p cds::opt::v:relaxed_ordering
63 template <typename... Options>
65 # ifdef CDS_DOXYGEN_INVOKED
66 typedef implementation_defined type ; ///< Metafunction result
68 typedef typename cds::opt::make_options<
69 typename cds::opt::find_type_traits< traits, Options... >::type
75 } // namespace fcpqueue
77 /// Flat-combining priority queue
79 @ingroup cds_nonintrusive_priority_queue
80 @ingroup cds_flat_combining_container
82 \ref cds_flat_combining_description "Flat combining" sequential priority queue.
83 The class can be considered as a concurrent FC-based wrapper for \p std::priority_queue.
86 - \p T - a value type stored in the queue
87 - \p PriorityQueue - sequential priority queue implementation, default is \p std::priority_queue<T>
88 - \p Traits - type traits of flat combining, default is \p fcpqueue::traits.
89 \p fcpqueue::make_traits metafunction can be used to construct specialized \p %fcpqueue::traits
92 class PriorityQueue = std::priority_queue<T>,
93 typename Traits = fcpqueue::traits
96 #ifndef CDS_DOXYGEN_INVOKED
97 : public cds::algo::flat_combining::container
101 typedef T value_type; ///< Value type
102 typedef PriorityQueue priority_queue_type; ///< Sequential priority queue class
103 typedef Traits traits; ///< Priority queue type traits
105 typedef typename traits::stat stat; ///< Internal statistics type
109 // Priority queue operation IDs
111 op_push = cds::algo::flat_combining::req_Operation,
118 // Flat combining publication list record
119 struct fc_record: public cds::algo::flat_combining::publication_record
122 value_type const * pValPush; // Value to push
123 value_type * pValPop; // Pop destination
125 bool bEmpty; // true if the queue is empty
129 /// Flat combining kernel
130 typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
134 fc_kernel m_FlatCombining;
135 priority_queue_type m_PQueue;
139 /// Initializes empty priority queue object
143 /// Initializes empty priority queue object and gives flat combining parameters
145 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
146 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
148 : m_FlatCombining( nCompactFactor, nCombinePassCount )
151 /// Inserts a new element in the priority queue
153 The function always returns \p true
156 value_type const& val ///< Value to be copied to inserted element
159 fc_record * pRec = m_FlatCombining.acquire_record();
160 pRec->pValPush = &val;
162 m_FlatCombining.combine( op_push, pRec, *this );
164 assert( pRec->is_done() );
165 m_FlatCombining.release_record( pRec );
166 m_FlatCombining.internal_statistics().onPush();
170 /// Inserts a new element in the priority queue (move semantics)
172 The function always returns \p true
175 value_type&& val ///< Value to be moved to inserted element
178 fc_record * pRec = m_FlatCombining.acquire_record();
179 pRec->pValPush = &val;
181 m_FlatCombining.combine( op_push_move, pRec, *this );
183 assert( pRec->is_done() );
184 m_FlatCombining.release_record( pRec );
185 m_FlatCombining.internal_statistics().onPushMove();
189 /// Removes the top element from priority queue
191 The function returns \p false if the queue is empty, \p true otherwise.
192 If the queue is empty \p val is not changed.
195 value_type& val ///< Target to be received the copy of top element
198 fc_record * pRec = m_FlatCombining.acquire_record();
199 pRec->pValPop = &val;
201 m_FlatCombining.combine( op_pop, pRec, *this );
203 assert( pRec->is_done() );
204 m_FlatCombining.release_record( pRec );
205 m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
206 return !pRec->bEmpty;
209 /// Clears the priority queue
212 fc_record * pRec = m_FlatCombining.acquire_record();
214 m_FlatCombining.combine( op_clear, pRec, *this );
216 assert( pRec->is_done() );
217 m_FlatCombining.release_record( pRec );
220 /// Returns the number of elements in the priority queue.
222 Note that <tt>size() == 0</tt> does not mean that the queue is empty because
223 combining record can be in process.
224 To check emptiness use \ref empty function.
228 return m_PQueue.size();
231 /// Checks if the priority queue is empty
233 If the combining is in process the function waits while combining done.
237 fc_record * pRec = m_FlatCombining.acquire_record();
239 m_FlatCombining.combine( op_empty, pRec, *this );
240 assert( pRec->is_done() );
241 m_FlatCombining.release_record( pRec );
245 /// Internal statistics
246 stat const& statistics() const
248 return m_FlatCombining.statistics();
251 public: // flat combining cooperation, not for direct use!
254 The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
255 object if the current thread becomes a combiner. Invocation of the function means that
256 the priority queue should perform an action recorded in \p pRec.
258 void fc_apply( fc_record * pRec )
262 // this function is called under FC mutex, so switch TSan off
263 CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
265 switch ( pRec->op() ) {
267 assert( pRec->pValPush );
268 m_PQueue.push( *(pRec->pValPush) );
271 assert( pRec->pValPush );
272 m_PQueue.push( std::move( *(pRec->pValPush )) );
275 assert( pRec->pValPop );
276 pRec->bEmpty = m_PQueue.empty();
277 if ( !pRec->bEmpty ) {
278 *(pRec->pValPop) = m_PQueue.top();
283 while ( !m_PQueue.empty() )
287 pRec->bEmpty = m_PQueue.empty();
294 CDS_TSAN_ANNOTATE_IGNORE_RW_END;
299 }} // namespace cds::container
301 #endif // #ifndef CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H