3 #ifndef __UNIT_PQUEUE_TYPES_H
4 #define __UNIT_PQUEUE_TYPES_H
6 #include <cds/container/mspriority_queue.h>
7 #include <cds/container/fcpriority_queue.h>
9 #include "pqueue/std_pqueue.h"
10 #include "pqueue/ellen_bintree_pqueue.h"
11 #include "pqueue/skiplist_pqueue.h"
15 #include <boost/container/stable_vector.hpp>
16 #include <boost/container/deque.hpp>
18 #include <cds/lock/spinlock.h>
20 #include "print_ellenbintree_stat.h"
21 #include "print_skip_list_stat.h"
22 #include "print_mspriorityqueue_stat.h"
25 namespace cc = cds::container;
26 namespace co = cds::opt;
28 template <typename Value>
31 static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
33 typedef std::less<Value> less;
36 int operator()( Value const& v1, Value const& v2 ) const
38 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
45 typedef cc::MSPriorityQueue< Value,
46 typename cc::mspriority_queue::make_traits<
47 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
49 > MSPriorityQueue_static_less;
51 typedef cc::MSPriorityQueue< Value,
52 typename cc::mspriority_queue::make_traits<
53 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
54 ,co::stat< cc::mspriority_queue::stat<> >
56 > MSPriorityQueue_static_less_stat;
58 typedef cc::MSPriorityQueue< Value,
59 typename cc::mspriority_queue::make_traits<
60 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
63 > MSPriorityQueue_static_cmp;
65 typedef cc::MSPriorityQueue< Value,
66 typename cc::mspriority_queue::make_traits<
67 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
68 ,co::lock_type<std::mutex>
70 > MSPriorityQueue_static_mutex;
72 typedef cc::MSPriorityQueue< Value,
73 typename cc::mspriority_queue::make_traits<
74 co::buffer< co::v::dynamic_buffer< char > >
76 > MSPriorityQueue_dyn_less;
78 typedef cc::MSPriorityQueue< Value,
79 typename cc::mspriority_queue::make_traits<
80 co::buffer< co::v::dynamic_buffer< char > >
81 ,co::stat< cc::mspriority_queue::stat<> >
83 > MSPriorityQueue_dyn_less_stat;
85 typedef cc::MSPriorityQueue< Value,
86 typename cc::mspriority_queue::make_traits<
87 co::buffer< co::v::dynamic_buffer< char > >
90 > MSPriorityQueue_dyn_cmp;
92 typedef cc::MSPriorityQueue< Value,
93 typename cc::mspriority_queue::make_traits<
94 co::buffer< co::v::dynamic_buffer< char > >
95 ,co::lock_type<std::mutex>
97 > MSPriorityQueue_dyn_mutex;
100 // Priority queue based on EllenBinTreeSet
101 typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value,
102 typename cc::ellen_bintree::make_set_traits<
103 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
104 ,cc::opt::less< std::less<Value> >
106 > EllenBinTree_HP_max;
108 typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value,
109 typename cc::ellen_bintree::make_set_traits<
110 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
111 ,cc::opt::less< std::less<Value> >
112 ,co::stat< cc::ellen_bintree::stat<> >
114 > EllenBinTree_HP_max_stat;
116 typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value,
117 typename cc::ellen_bintree::make_set_traits<
118 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
119 ,cc::opt::less< std::greater<Value> >
121 > EllenBinTree_HP_min;
123 typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value,
124 typename cc::ellen_bintree::make_set_traits<
125 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
126 ,cc::opt::less< std::greater<Value> >
127 ,co::stat< cc::ellen_bintree::stat<> >
129 > EllenBinTree_HP_min_stat;
131 typedef EllenBinTreePQueue< cds::gc::PTB, typename Value::key_type, Value,
132 typename cc::ellen_bintree::make_set_traits<
133 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
134 ,cc::opt::less< std::less<Value> >
136 > EllenBinTree_PTB_max;
138 typedef EllenBinTreePQueue< cds::gc::PTB, typename Value::key_type, Value,
139 typename cc::ellen_bintree::make_set_traits<
140 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
141 ,cc::opt::less< std::greater<Value> >
143 > EllenBinTree_PTB_min;
145 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_instant<> >, typename Value::key_type, Value,
146 typename cc::ellen_bintree::make_set_traits<
147 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
148 ,cc::opt::less< std::less<Value> >
150 > EllenBinTree_RCU_gpi_max;
152 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_instant<> >, typename Value::key_type, Value,
153 typename cc::ellen_bintree::make_set_traits<
154 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
155 ,cc::opt::less< std::less<Value> >
156 ,co::stat< cc::ellen_bintree::stat<> >
158 > EllenBinTree_RCU_gpi_max_stat;
160 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_instant<> >, typename Value::key_type, Value,
161 typename cc::ellen_bintree::make_set_traits<
162 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
163 ,cc::opt::less< std::greater<Value> >
165 > EllenBinTree_RCU_gpi_min;
167 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_instant<> >, typename Value::key_type, Value,
168 typename cc::ellen_bintree::make_set_traits<
169 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
170 ,cc::opt::less< std::greater<Value> >
171 ,co::stat< cc::ellen_bintree::stat<> >
173 > EllenBinTree_RCU_gpi_min_stat;
175 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_buffered<> >, typename Value::key_type, Value,
176 typename cc::ellen_bintree::make_set_traits<
177 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
178 ,cc::opt::less< std::less<Value> >
180 > EllenBinTree_RCU_gpb_max;
182 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_buffered<> >, typename Value::key_type, Value,
183 typename cc::ellen_bintree::make_set_traits<
184 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
185 ,cc::opt::less< std::less<Value> >
186 ,co::stat< cc::ellen_bintree::stat<> >
188 > EllenBinTree_RCU_gpb_max_stat;
190 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_buffered<> >, typename Value::key_type, Value,
191 typename cc::ellen_bintree::make_set_traits<
192 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
193 ,cc::opt::less< std::greater<Value> >
195 > EllenBinTree_RCU_gpb_min;
197 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_buffered<> >, typename Value::key_type, Value,
198 typename cc::ellen_bintree::make_set_traits<
199 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
200 ,cc::opt::less< std::greater<Value> >
201 ,co::stat< cc::ellen_bintree::stat<> >
203 > EllenBinTree_RCU_gpb_min_stat;
205 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_threaded<> >, typename Value::key_type, Value,
206 typename cc::ellen_bintree::make_set_traits<
207 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
208 ,cc::opt::less< std::less<Value> >
210 > EllenBinTree_RCU_gpt_max;
212 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_threaded<> >, typename Value::key_type, Value,
213 typename cc::ellen_bintree::make_set_traits<
214 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
215 ,cc::opt::less< std::less<Value> >
216 ,co::stat< cc::ellen_bintree::stat<> >
218 > EllenBinTree_RCU_gpt_max_stat;
220 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_threaded<> >, typename Value::key_type, Value,
221 typename cc::ellen_bintree::make_set_traits<
222 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
223 ,cc::opt::less< std::greater<Value> >
225 > EllenBinTree_RCU_gpt_min;
227 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::general_threaded<> >, typename Value::key_type, Value,
228 typename cc::ellen_bintree::make_set_traits<
229 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
230 ,cc::opt::less< std::greater<Value> >
231 ,co::stat< cc::ellen_bintree::stat<> >
233 > EllenBinTree_RCU_gpt_min_stat;
235 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
236 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_buffered<> >, typename Value::key_type, Value,
237 typename cc::ellen_bintree::make_set_traits<
238 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
239 ,cc::opt::less< std::less<Value> >
241 > EllenBinTree_RCU_shb_max;
243 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_buffered<> >, typename Value::key_type, Value,
244 typename cc::ellen_bintree::make_set_traits<
245 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
246 ,cc::opt::less< std::less<Value> >
247 ,co::stat< cc::ellen_bintree::stat<> >
249 > EllenBinTree_RCU_shb_max_stat;
251 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_buffered<> >, typename Value::key_type, Value,
252 typename cc::ellen_bintree::make_set_traits<
253 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
254 ,cc::opt::less< std::greater<Value> >
256 > EllenBinTree_RCU_shb_min;
258 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_buffered<> >, typename Value::key_type, Value,
259 typename cc::ellen_bintree::make_set_traits<
260 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
261 ,cc::opt::less< std::greater<Value> >
262 ,co::stat< cc::ellen_bintree::stat<> >
264 > EllenBinTree_RCU_shb_min_stat;
266 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_threaded<> >, typename Value::key_type, Value,
267 typename cc::ellen_bintree::make_set_traits<
268 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
269 ,cc::opt::less< std::less<Value> >
271 > EllenBinTree_RCU_sht_max;
273 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_threaded<> >, typename Value::key_type, Value,
274 typename cc::ellen_bintree::make_set_traits<
275 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
276 ,cc::opt::less< std::less<Value> >
277 ,co::stat< cc::ellen_bintree::stat<> >
279 > EllenBinTree_RCU_sht_max_stat;
281 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_threaded<> >, typename Value::key_type, Value,
282 typename cc::ellen_bintree::make_set_traits<
283 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
284 ,cc::opt::less< std::greater<Value> >
286 > EllenBinTree_RCU_sht_min;
288 typedef EllenBinTreePQueue< cds::urcu::gc< cds::urcu::signal_threaded<> >, typename Value::key_type, Value,
289 typename cc::ellen_bintree::make_set_traits<
290 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
291 ,cc::opt::less< std::greater<Value> >
292 ,co::stat< cc::ellen_bintree::stat<> >
294 > EllenBinTree_RCU_sht_min_stat;
297 // Priority queue based on SkipListSet
298 typedef SkipListPQueue< cds::gc::HP, Value,
299 typename cc::skip_list::make_traits<
300 cc::opt::less< std::less<Value> >
304 typedef SkipListPQueue< cds::gc::HP, Value,
305 typename cc::skip_list::make_traits<
306 cc::opt::less< std::less<Value> >
307 ,co::stat< cc::skip_list::stat<> >
309 > SkipList_HP_max_stat;
311 typedef SkipListPQueue< cds::gc::HP, Value,
312 typename cc::skip_list::make_traits<
313 cc::opt::less< std::greater<Value> >
317 typedef SkipListPQueue< cds::gc::HP, Value,
318 typename cc::skip_list::make_traits<
319 cc::opt::less< std::greater<Value> >
320 ,co::stat< cc::skip_list::stat<> >
322 > SkipList_HP_min_stat;
324 typedef SkipListPQueue< cds::gc::HRC, Value,
325 typename cc::skip_list::make_traits<
326 cc::opt::less< std::less<Value> >
330 typedef SkipListPQueue< cds::gc::HRC, Value,
331 typename cc::skip_list::make_traits<
332 cc::opt::less< std::greater<Value> >
336 typedef SkipListPQueue< cds::gc::PTB, Value,
337 typename cc::skip_list::make_traits<
338 cc::opt::less< std::less<Value> >
342 typedef SkipListPQueue< cds::gc::PTB, Value,
343 typename cc::skip_list::make_traits<
344 cc::opt::less< std::greater<Value> >
348 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::general_instant<> >, Value,
349 typename cc::skip_list::make_traits<
350 cc::opt::less< std::less<Value> >
352 > SkipList_RCU_gpi_max;
354 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::general_instant<> >, Value,
355 typename cc::skip_list::make_traits<
356 cc::opt::less< std::greater<Value> >
358 > SkipList_RCU_gpi_min;
360 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::general_buffered<> >, Value,
361 typename cc::skip_list::make_traits<
362 cc::opt::less< std::less<Value> >
364 > SkipList_RCU_gpb_max;
366 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::general_buffered<> >, Value,
367 typename cc::skip_list::make_traits<
368 cc::opt::less< std::greater<Value> >
370 > SkipList_RCU_gpb_min;
372 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::general_threaded<> >, Value,
373 typename cc::skip_list::make_traits<
374 cc::opt::less< std::less<Value> >
376 > SkipList_RCU_gpt_max;
378 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::general_threaded<> >, Value,
379 typename cc::skip_list::make_traits<
380 cc::opt::less< std::greater<Value> >
382 > SkipList_RCU_gpt_min;
384 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
385 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::signal_buffered<> >, Value,
386 typename cc::skip_list::make_traits<
387 cc::opt::less< std::less<Value> >
389 > SkipList_RCU_shb_max;
391 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::signal_buffered<> >, Value,
392 typename cc::skip_list::make_traits<
393 cc::opt::less< std::greater<Value> >
395 > SkipList_RCU_shb_min;
397 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::signal_threaded<> >, Value,
398 typename cc::skip_list::make_traits<
399 cc::opt::less< std::less<Value> >
401 > SkipList_RCU_sht_max;
403 typedef SkipListPQueue< cds::urcu::gc< cds::urcu::signal_threaded<> >, Value,
404 typename cc::skip_list::make_traits<
405 cc::opt::less< std::greater<Value> >
407 > SkipList_RCU_sht_min;
411 struct traits_FCPQueue_stat : public
412 cds::container::fcpqueue::make_traits <
413 cds::opt::stat < cds::container::fcpqueue::stat<> >
417 typedef cds::container::FCPriorityQueue< Value > FCPQueue_vector;
418 typedef cds::container::FCPriorityQueue< Value
419 ,std::priority_queue<Value>
420 ,traits_FCPQueue_stat
421 > FCPQueue_vector_stat;
423 typedef cds::container::FCPriorityQueue< Value
424 ,std::priority_queue<Value, std::deque<Value> >
426 typedef cds::container::FCPriorityQueue< Value
427 ,std::priority_queue<Value, std::deque<Value> >
428 ,traits_FCPQueue_stat
429 > FCPQueue_deque_stat;
431 typedef cds::container::FCPriorityQueue< Value
432 ,std::priority_queue<Value, boost::container::deque<Value> >
433 > FCPQueue_boost_deque;
434 typedef cds::container::FCPriorityQueue< Value
435 ,std::priority_queue<Value, boost::container::deque<Value> >
436 ,traits_FCPQueue_stat
437 > FCPQueue_boost_deque_stat;
439 typedef cds::container::FCPriorityQueue< Value
440 ,std::priority_queue<Value, boost::container::stable_vector<Value> >
441 > FCPQueue_boost_stable_vector;
442 typedef cds::container::FCPriorityQueue< Value
443 ,std::priority_queue<Value, boost::container::stable_vector<Value> >
444 ,traits_FCPQueue_stat
445 > FCPQueue_boost_stable_vector_stat;
447 /// Standard priority_queue
448 typedef StdPQueue< Value, std::vector<Value>, cds::lock::Spin > StdPQueue_vector_spin;
449 typedef StdPQueue< Value, std::vector<Value>, std::mutex > StdPQueue_vector_mutex;
450 typedef StdPQueue< Value, std::deque<Value>, cds::lock::Spin > StdPQueue_deque_spin;
451 typedef StdPQueue< Value, std::deque<Value>, std::mutex > StdPQueue_deque_mutex;
455 template <typename Stat>
456 static inline void check_statistics( Stat const& s )
459 static inline void check_statistics( cds::container::ellen_bintree::stat<> const& s )
461 CPPUNIT_CHECK_CURRENT( s.m_nInternalNodeCreated.get() == s.m_nInternalNodeDeleted.get() );
462 CPPUNIT_CHECK_CURRENT( s.m_nUpdateDescCreated.get() == s.m_nUpdateDescDeleted.get() );
464 } // namespace pqueue
468 static inline std::ostream& operator <<( std::ostream& o, cds::container::fcpqueue::empty_stat const& )
473 static inline std::ostream& operator <<( std::ostream& o, cds::container::fcpqueue::stat<> const& s )
475 return o << "\tStatistics:\n"
476 << "\t Push: " << s.m_nPush.get() << "\n"
477 << "\t Push move: " << s.m_nPushMove.get() << "\n"
478 << "\t Pop: " << s.m_nPop.get() << "\n"
479 << "\t Failed pop: " << s.m_nFailedPop.get() << "\n"
480 << "\tFlat combining statistics:\n"
481 << "\t Combining factor: " << s.combining_factor() << "\n"
482 << "\t Operation count: " << s.m_nOperationCount.get() << "\n"
483 << "\t Combine call count: " << s.m_nCombiningCount.get() << "\n"
484 << "\t Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
485 << "\t Deactivate pub-record: " << s.m_nDeactivatePubRecord.get() << "\n"
486 << "\t Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
487 << "\t Create pub-record: " << s.m_nPubRecordCreated.get() << "\n"
488 << "\t Delete pub-record: " << s.m_nPubRecordDeteted.get() << "\n"
489 << "\t Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
490 << "\t Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
495 #endif // #ifndef __UNIT_PQUEUE_TYPES_H