3 #ifndef __CDSUNIT_INTRUSIVE_QUEUE_TYPES_H
4 #define __CDSUNIT_INTRUSIVE_QUEUE_TYPES_H
6 #include <cds/intrusive/msqueue.h>
7 #include <cds/intrusive/moir_queue.h>
8 #include <cds/intrusive/optimistic_queue.h>
9 #include <cds/intrusive/tsigas_cycle_queue.h>
10 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
11 #include <cds/intrusive/basket_queue.h>
12 #include <cds/intrusive/fcqueue.h>
13 #include <cds/intrusive/segmented_queue.h>
15 #include <cds/gc/hp.h>
16 #include <cds/gc/hrc.h>
17 #include <cds/gc/dhp.h>
19 #include <boost/intrusive/slist.hpp>
21 #include "print_segmentedqueue_stat.h"
28 template <typename T, typename Lock=std::mutex>
31 typedef boost::intrusive::slist< T, boost::intrusive::cache_last<true> > slist_type;
32 typedef Lock lock_type;
33 typedef std::lock_guard<lock_type> lock_guard;
36 mutable lock_type m_Lock;
41 bool push( value_type& v )
43 lock_guard l( m_Lock );
44 m_List.push_back( v );
48 bool enqueue( value_type& v )
55 lock_guard l( m_Lock );
58 value_type& v = m_List.front();
69 lock_guard l( m_Lock );
70 return m_List.empty();
75 lock_guard l( m_Lock );
79 empty_stat statistics() const
90 struct traits_MSQueue_HP : public cds::intrusive::msqueue::traits
92 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::HP > > hook;
94 typedef cds::intrusive::MSQueue< cds::gc::HP, T, traits_MSQueue_HP > MSQueue_HP;
95 typedef cds::intrusive::MoirQueue< cds::gc::HP, T, traits_MSQueue_HP > MoirQueue_HP;
97 struct traits_MSQueue_HP_seqcst : public cds::intrusive::msqueue::traits
99 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::HP > > hook;
100 typedef cds::opt::v::sequential_consistent memory_model;
102 typedef cds::intrusive::MSQueue< cds::gc::HP, T, traits_MSQueue_HP_seqcst > MSQueue_HP_seqcst;
103 typedef cds::intrusive::MoirQueue< cds::gc::HP, T, traits_MSQueue_HP_seqcst > MoirQueue_HP_seqcst;
105 struct traits_MSQueue_DHP : public cds::intrusive::msqueue::traits
107 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
109 typedef cds::intrusive::MSQueue< cds::gc::DHP, T, traits_MSQueue_DHP > MSQueue_DHP;
110 typedef cds::intrusive::MoirQueue< cds::gc::DHP, T, traits_MSQueue_DHP > MoirQueue_DHP;
112 struct traits_MSQueue_DHP_seqcst : public cds::intrusive::msqueue::traits
114 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
115 typedef cds::opt::v::sequential_consistent memory_model;
117 typedef cds::intrusive::MSQueue< cds::gc::DHP, T, traits_MSQueue_DHP_seqcst > MSQueue_DHP_seqcst;
118 typedef cds::intrusive::MoirQueue< cds::gc::DHP, T, traits_MSQueue_DHP_seqcst > MoirQueue_DHP_seqcst;
120 // MSQueue + item counter
121 struct traits_MSQueue_HP_ic : public cds::intrusive::msqueue::traits
123 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::HP > > hook;
124 typedef cds::atomicity::item_counter item_counter;
126 typedef cds::intrusive::MSQueue< cds::gc::HP, T, traits_MSQueue_HP_ic > MSQueue_HP_ic;
127 typedef cds::intrusive::MoirQueue< cds::gc::HP, T, traits_MSQueue_HP_ic > MoirQueue_HP_ic;
129 struct traits_MSQueue_DHP_ic : public cds::intrusive::msqueue::traits
131 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
132 typedef cds::atomicity::item_counter item_counter;
134 typedef cds::intrusive::MSQueue< cds::gc::DHP, T, traits_MSQueue_DHP_ic > MSQueue_DHP_ic;
135 typedef cds::intrusive::MoirQueue< cds::gc::DHP, T, traits_MSQueue_DHP_ic > MoirQueue_DHP_ic;
138 struct traits_MSQueue_HP_stat : public cds::intrusive::msqueue::traits
140 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::HP > > hook;
141 typedef cds::intrusive::msqueue::stat<> stat;
143 typedef cds::intrusive::MSQueue< cds::gc::HP, T, traits_MSQueue_HP_stat > MSQueue_HP_stat;
144 typedef cds::intrusive::MoirQueue< cds::gc::HP, T, traits_MSQueue_HP_stat > MoirQueue_HP_stat;
146 struct traits_MSQueue_DHP_stat : public cds::intrusive::msqueue::traits
148 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
149 typedef cds::intrusive::msqueue::stat<> stat;
151 typedef cds::intrusive::MSQueue< cds::gc::DHP, T, traits_MSQueue_DHP_stat > MSQueue_DHP_stat;
152 typedef cds::intrusive::MoirQueue< cds::gc::DHP, T, traits_MSQueue_DHP_stat > MoirQueue_DHP_stat;
156 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, T
157 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
158 > OptimisticQueue_HP;
160 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, T
161 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
162 ,cds::opt::memory_model< cds::opt::v::sequential_consistent >
163 > OptimisticQueue_HP_seqcst;
165 typedef cds::intrusive::OptimisticQueue< cds::gc::PTB, T
166 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
167 > OptimisticQueue_PTB;
169 typedef cds::intrusive::OptimisticQueue< cds::gc::PTB, T
170 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
171 ,cds::opt::memory_model< cds::opt::v::sequential_consistent >
172 > OptimisticQueue_PTB_seqcst;
175 // OptimisticQueue + item counter
176 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, T
177 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
178 ,cds::opt::item_counter< cds::atomicity::item_counter >
179 > OptimisticQueue_HP_ic;
181 typedef cds::intrusive::OptimisticQueue< cds::gc::PTB, T
182 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
183 ,cds::opt::item_counter< cds::atomicity::item_counter >
184 > OptimisticQueue_PTB_ic;
186 // OptimisticQueue + stat
187 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, T
188 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
189 ,cds::opt::stat< cds::intrusive::queue_stat<> >
190 > OptimisticQueue_HP_stat;
192 typedef cds::intrusive::OptimisticQueue< cds::gc::PTB, T
193 ,cds::intrusive::opt::hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
194 ,cds::opt::stat< cds::intrusive::queue_stat<> >
195 > OptimisticQueue_PTB_stat;
198 class TsigasCycleQueue_dyn
199 : public cds::intrusive::TsigasCycleQueue< T
200 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
203 typedef cds::intrusive::TsigasCycleQueue< T
204 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
207 TsigasCycleQueue_dyn()
208 : base_class( 1024 * 64 )
211 TsigasCycleQueue_dyn( size_t nCapacity )
212 : base_class( nCapacity )
215 cds::opt::none statistics() const
217 return cds::opt::none();
221 class TsigasCycleQueue_dyn_ic
222 : public cds::intrusive::TsigasCycleQueue< T
223 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
224 ,cds::opt::item_counter< cds::atomicity::item_counter >
227 typedef cds::intrusive::TsigasCycleQueue< T
228 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
229 ,cds::opt::item_counter< cds::atomicity::item_counter >
232 TsigasCycleQueue_dyn_ic()
233 : base_class( 1024 * 64 )
235 TsigasCycleQueue_dyn_ic( size_t nCapacity )
236 : base_class( nCapacity )
239 cds::opt::none statistics() const
241 return cds::opt::none();
245 // VyukovMPMCCycleQueue
246 class VyukovMPMCCycleQueue_dyn
247 : public cds::intrusive::VyukovMPMCCycleQueue< T
248 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
251 typedef cds::intrusive::VyukovMPMCCycleQueue< T
252 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
255 VyukovMPMCCycleQueue_dyn()
256 : base_class( 1024 * 64 )
258 VyukovMPMCCycleQueue_dyn( size_t nCapacity )
259 : base_class( nCapacity )
262 cds::opt::none statistics() const
264 return cds::opt::none();
268 class VyukovMPMCCycleQueue_dyn_ic
269 : public cds::intrusive::VyukovMPMCCycleQueue< T
270 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
271 ,cds::opt::item_counter< cds::atomicity::item_counter >
274 typedef cds::intrusive::VyukovMPMCCycleQueue< T
275 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< int > >
276 ,cds::opt::item_counter< cds::atomicity::item_counter >
279 VyukovMPMCCycleQueue_dyn_ic()
280 : base_class( 1024 * 64 )
282 VyukovMPMCCycleQueue_dyn_ic( size_t nCapacity )
283 : base_class( nCapacity )
286 cds::opt::none statistics() const
288 return cds::opt::none();
293 typedef cds::intrusive::BasketQueue< cds::gc::HP, T
294 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
297 typedef cds::intrusive::BasketQueue<cds::gc::HP, T
298 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
299 ,cds::opt::memory_model< cds::opt::v::sequential_consistent >
300 > BasketQueue_HP_seqcst;
302 typedef cds::intrusive::BasketQueue< cds::gc::HRC, T
303 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HRC > > >
306 typedef cds::intrusive::BasketQueue< cds::gc::HRC, T
307 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HRC > > >
308 ,cds::opt::memory_model< cds::opt::v::sequential_consistent >
309 > BasketQueue_HRC_seqcst;
311 typedef cds::intrusive::BasketQueue< cds::gc::PTB, T
312 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
315 typedef cds::intrusive::BasketQueue< cds::gc::PTB, T
316 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
317 ,cds::opt::memory_model< cds::opt::v::sequential_consistent >
318 > BasketQueue_PTB_seqcst;
320 // BasketQueue + item counter
321 typedef cds::intrusive::BasketQueue< cds::gc::HP, T
322 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
323 ,cds::opt::item_counter< cds::atomicity::item_counter >
326 typedef cds::intrusive::BasketQueue< cds::gc::HRC, T
327 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HRC > > >
328 ,cds::opt::item_counter< cds::atomicity::item_counter >
329 > BasketQueue_HRC_ic;
331 typedef cds::intrusive::BasketQueue< cds::gc::PTB, T
332 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
333 ,cds::opt::item_counter< cds::atomicity::item_counter >
334 > BasketQueue_PTB_ic;
336 // BasketQueue + stat
337 typedef cds::intrusive::BasketQueue< cds::gc::HP, T
338 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
339 ,cds::opt::stat< cds::intrusive::queue_stat<> >
340 > BasketQueue_HP_stat;
342 typedef cds::intrusive::BasketQueue< cds::gc::HRC, T
343 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HRC > > >
344 ,cds::opt::stat< cds::intrusive::queue_stat<> >
345 > BasketQueue_HRC_stat;
347 typedef cds::intrusive::BasketQueue< cds::gc::PTB, T
348 ,cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::PTB > > >
349 ,cds::opt::stat< cds::intrusive::queue_stat<> >
350 > BasketQueue_PTB_stat;
353 class traits_FCQueue_delay2:
354 public cds::intrusive::fcqueue::make_traits<
355 cds::opt::back_off< cds::backoff::delay_of<2> >
358 class traits_FCQueue_delay2_elimination:
359 public cds::intrusive::fcqueue::make_traits<
360 cds::opt::back_off< cds::backoff::delay_of<2> >
361 ,cds::opt::enable_elimination< true >
364 class traits_FCQueue_delay2_elimination_stat:
365 public cds::intrusive::fcqueue::make_traits<
366 cds::opt::back_off< cds::backoff::delay_of<2> >
367 ,cds::opt::stat< cds::intrusive::fcqueue::stat<> >
368 ,cds::opt::enable_elimination< true >
371 class traits_FCQueue_expbackoff_elimination:
372 public cds::intrusive::fcqueue::make_traits<
373 cds::opt::enable_elimination< true >
374 ,cds::opt::elimination_backoff< cds::backoff::Default >
377 class traits_FCQueue_expbackoff_elimination_stat:
378 public cds::intrusive::fcqueue::make_traits<
379 cds::opt::enable_elimination< true >
380 ,cds::opt::stat< cds::intrusive::fcqueue::stat<> >
381 ,cds::opt::elimination_backoff< cds::backoff::Default >
385 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_delay2 > FCQueue_list_delay2;
386 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_delay2_elimination > FCQueue_list_delay2_elimination;
387 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_delay2_elimination_stat > FCQueue_list_delay2_elimination_stat;
388 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_expbackoff_elimination > FCQueue_list_expbackoff_elimination;
389 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_expbackoff_elimination_stat > FCQueue_list_expbackoff_elimination_stat;
392 class traits_SegmentedQueue_spin_stat:
393 public cds::intrusive::segmented_queue::make_traits<
394 cds::opt::stat< cds::intrusive::segmented_queue::stat<> >
397 class traits_SegmentedQueue_mutex_stat:
398 public cds::intrusive::segmented_queue::make_traits<
399 cds::opt::stat< cds::intrusive::segmented_queue::stat<> >
400 ,cds::opt::lock_type< std::mutex >
403 class traits_SegmentedQueue_mutex:
404 public cds::intrusive::segmented_queue::make_traits<
405 cds::opt::lock_type< std::mutex >
409 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T > SegmentedQueue_HP_spin;
410 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T, traits_SegmentedQueue_spin_stat > SegmentedQueue_HP_spin_stat;
411 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T, traits_SegmentedQueue_mutex > SegmentedQueue_HP_mutex;
412 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T, traits_SegmentedQueue_mutex_stat > SegmentedQueue_HP_mutex_stat;
414 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T > SegmentedQueue_PTB_spin;
415 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T, traits_SegmentedQueue_spin_stat > SegmentedQueue_PTB_spin_stat;
416 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T, traits_SegmentedQueue_mutex > SegmentedQueue_PTB_mutex;
417 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T, traits_SegmentedQueue_mutex_stat > SegmentedQueue_PTB_mutex_stat;
420 typedef details::BoostSList< T, std::mutex > BoostSList_mutex;
421 typedef details::BoostSList< T, cds::lock::Spin > BoostSList_spin;
426 // *********************************************
430 // cds::intrusive::queue_stat
431 template <typename Counter>
432 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::msqueue::stat<Counter> const& s )
436 << "\t\t Enqueue count: " << s.m_EnqueueCount.get() << "\n"
437 << "\t\t Enqueue race: " << s.m_EnqueueRace.get() << "\n"
438 << "\t\t Dequeue count: " << s.m_DequeueCount.get() << "\n"
439 << "\t\t Dequeue race: " << s.m_DequeueRace.get() << "\n"
440 << "\t\tAdvance tail error: " << s.m_AdvanceTailError.get() << "\n"
441 << "\t\t Bad tail: " << s.m_BadTail.get() << "\n";
444 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::queue_dummy_stat const& s )
449 static inline std::ostream& operator <<( std::ostream& o, cds::opt::none )
454 // cds::intrusive::optimistic_queue::stat
455 template <typename Counter>
456 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::optimistic_queue::stat<Counter> const& s )
459 << static_cast<cds::intrusive::queue_stat<Counter> const&>( s )
461 << "\t\t fix list call: " << s.m_FixListCount.get() << "\n";
464 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::optimistic_queue::dummy_stat const& s )
469 // cds::intrusive::basket_queue::stat
470 template <typename Counter>
471 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::basket_queue::stat<Counter> const& s )
474 << static_cast<cds::intrusive::queue_stat<Counter> const&>( s )
475 << "\t\tTry Add basket count: " << s.m_TryAddBasket.get() << "\n"
476 << "\t\t Add basket count: " << s.m_AddBasketCount.get() << "\n";
479 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::basket_queue::dummy_stat const& s )
484 // cds::intrusive::fcqueue::stat
485 template <typename Counter>
486 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::fcqueue::stat<Counter> const& s )
488 return o << "\tStatistics:\n"
489 << "\t Push: " << s.m_nEnqueue.get() << "\n"
490 << "\t Pop: " << s.m_nDequeue.get() << "\n"
491 << "\t FailedPop: " << s.m_nFailedDeq.get() << "\n"
492 << "\t Collided push/pop pair: " << s.m_nCollided.get() << "\n"
493 << "\tFlat combining statistics:\n"
494 << "\t Combining factor: " << s.combining_factor() << "\n"
495 << "\t Operation count: " << s.m_nOperationCount.get() << "\n"
496 << "\t Combine call count: " << s.m_nCombiningCount.get() << "\n"
497 << "\t Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
498 << "\t Deactivate pub-record: " << s.m_nDeactivatePubRecord.get() << "\n"
499 << "\t Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
500 << "\t Create pub-record: " << s.m_nPubRecordCreated.get() << "\n"
501 << "\t Delete pub-record: " << s.m_nPubRecordDeteted.get() << "\n"
502 << "\t Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
503 << "\t Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
506 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::fcqueue::empty_stat const& s )
511 static inline std::ostream& operator <<( std::ostream& o, queue::details::empty_stat const& s )
518 #endif // #ifndef __CDSUNIT_INTRUSIVE_QUEUE_TYPES_H