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> //TODO: remove this line!
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 struct traits_BasketQueue_HP : public
294 cds::intrusive::basket_queue::make_traits <
295 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
298 typedef cds::intrusive::BasketQueue< cds::gc::HP, T, traits_BasketQueue_HP > BasketQueue_HP;
300 struct traits_BasketQueue_HP_seqcst: public
301 cds::intrusive::basket_queue::make_traits <
302 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
303 , cds::opt::memory_model< cds::opt::v::sequential_consistent >
306 typedef cds::intrusive::BasketQueue<cds::gc::HP, T, traits_BasketQueue_HP_seqcst > BasketQueue_HP_seqcst;
308 struct traits_BasketQueue_DHP : public
309 cds::intrusive::basket_queue::make_traits <
310 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::DHP > > >
313 typedef cds::intrusive::BasketQueue< cds::gc::DHP, T, traits_BasketQueue_DHP > BasketQueue_DHP;
315 struct traits_BasketQueue_DHP_seqcst: public
316 cds::intrusive::basket_queue::make_traits <
317 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::DHP > > >
318 , cds::opt::memory_model< cds::opt::v::sequential_consistent >
321 typedef cds::intrusive::BasketQueue< cds::gc::DHP, T, traits_BasketQueue_DHP_seqcst > BasketQueue_DHP_seqcst;
323 // BasketQueue + item counter
324 struct traits_BasketQueue_HP_ic : public
325 cds::intrusive::basket_queue::make_traits <
326 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
327 ,cds::opt::item_counter< cds::atomicity::item_counter >
330 typedef cds::intrusive::BasketQueue< cds::gc::HP, T, traits_BasketQueue_HP_ic > BasketQueue_HP_ic;
332 struct traits_BasketQueue_DHP_ic : public
333 cds::intrusive::basket_queue::make_traits <
334 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::DHP > > >
335 ,cds::opt::item_counter< cds::atomicity::item_counter >
338 typedef cds::intrusive::BasketQueue< cds::gc::DHP, T, traits_BasketQueue_DHP_ic > BasketQueue_DHP_ic;
340 // BasketQueue + stat
341 struct traits_BasketQueue_HP_stat : public
342 cds::intrusive::basket_queue::make_traits <
343 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::HP > > >
344 , cds::opt::stat< cds::intrusive::basket_queue::stat<> >
347 typedef cds::intrusive::BasketQueue< cds::gc::HP, T, traits_BasketQueue_HP_stat > BasketQueue_HP_stat;
349 struct traits_BasketQueue_DHP_stat : public
350 cds::intrusive::basket_queue::make_traits <
351 cds::intrusive::opt::hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc< cds::gc::DHP > > >
352 , cds::opt::stat< cds::intrusive::basket_queue::stat<> >
355 typedef cds::intrusive::BasketQueue< cds::gc::DHP, T, traits_BasketQueue_DHP_stat > BasketQueue_DHP_stat;
358 class traits_FCQueue_delay2:
359 public cds::intrusive::fcqueue::make_traits<
360 cds::opt::back_off< cds::backoff::delay_of<2> >
363 class traits_FCQueue_delay2_elimination:
364 public cds::intrusive::fcqueue::make_traits<
365 cds::opt::back_off< cds::backoff::delay_of<2> >
366 ,cds::opt::enable_elimination< true >
369 class traits_FCQueue_delay2_elimination_stat:
370 public cds::intrusive::fcqueue::make_traits<
371 cds::opt::back_off< cds::backoff::delay_of<2> >
372 ,cds::opt::stat< cds::intrusive::fcqueue::stat<> >
373 ,cds::opt::enable_elimination< true >
376 class traits_FCQueue_expbackoff_elimination:
377 public cds::intrusive::fcqueue::make_traits<
378 cds::opt::enable_elimination< true >
379 ,cds::opt::elimination_backoff< cds::backoff::Default >
382 class traits_FCQueue_expbackoff_elimination_stat:
383 public cds::intrusive::fcqueue::make_traits<
384 cds::opt::enable_elimination< true >
385 ,cds::opt::stat< cds::intrusive::fcqueue::stat<> >
386 ,cds::opt::elimination_backoff< cds::backoff::Default >
390 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_delay2 > FCQueue_list_delay2;
391 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_delay2_elimination > FCQueue_list_delay2_elimination;
392 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_delay2_elimination_stat > FCQueue_list_delay2_elimination_stat;
393 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_expbackoff_elimination > FCQueue_list_expbackoff_elimination;
394 typedef cds::intrusive::FCQueue< T, boost::intrusive::list<T>, traits_FCQueue_expbackoff_elimination_stat > FCQueue_list_expbackoff_elimination_stat;
397 class traits_SegmentedQueue_spin_stat:
398 public cds::intrusive::segmented_queue::make_traits<
399 cds::opt::stat< cds::intrusive::segmented_queue::stat<> >
402 class traits_SegmentedQueue_mutex_stat:
403 public cds::intrusive::segmented_queue::make_traits<
404 cds::opt::stat< cds::intrusive::segmented_queue::stat<> >
405 ,cds::opt::lock_type< std::mutex >
408 class traits_SegmentedQueue_mutex:
409 public cds::intrusive::segmented_queue::make_traits<
410 cds::opt::lock_type< std::mutex >
414 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T > SegmentedQueue_HP_spin;
415 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T, traits_SegmentedQueue_spin_stat > SegmentedQueue_HP_spin_stat;
416 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T, traits_SegmentedQueue_mutex > SegmentedQueue_HP_mutex;
417 typedef cds::intrusive::SegmentedQueue< cds::gc::HP, T, traits_SegmentedQueue_mutex_stat > SegmentedQueue_HP_mutex_stat;
419 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T > SegmentedQueue_PTB_spin;
420 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T, traits_SegmentedQueue_spin_stat > SegmentedQueue_PTB_spin_stat;
421 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T, traits_SegmentedQueue_mutex > SegmentedQueue_PTB_mutex;
422 typedef cds::intrusive::SegmentedQueue< cds::gc::PTB, T, traits_SegmentedQueue_mutex_stat > SegmentedQueue_PTB_mutex_stat;
425 typedef details::BoostSList< T, std::mutex > BoostSList_mutex;
426 typedef details::BoostSList< T, cds::lock::Spin > BoostSList_spin;
431 // *********************************************
435 // cds::intrusive::queue_stat
436 template <typename Counter>
437 static inline std::ostream& operator <<(std::ostream& o, cds::intrusive::queue_stat<Counter> const& s)
441 << "\t\t Enqueue count: " << s.m_EnqueueCount.get() << "\n"
442 << "\t\t Enqueue race: " << s.m_EnqueueRace.get() << "\n"
443 << "\t\t Dequeue count: " << s.m_DequeueCount.get() << "\n"
444 << "\t\t Dequeue race: " << s.m_DequeueRace.get() << "\n"
445 << "\t\tAdvance tail error: " << s.m_AdvanceTailError.get() << "\n"
446 << "\t\t Bad tail: " << s.m_BadTail.get() << "\n";
448 static inline std::ostream& operator <<(std::ostream& o, cds::intrusive::queue_dummy_stat const& s)
454 template <typename Counter>
455 static inline std::ostream& operator <<(std::ostream& o, cds::intrusive::basket_queue::stat<Counter> const& s)
459 << "\t\t Enqueue count: " << s.m_EnqueueCount.get() << "\n"
460 << "\t\t Enqueue race: " << s.m_EnqueueRace.get() << "\n"
461 << "\t\t Dequeue count: " << s.m_DequeueCount.get() << "\n"
462 << "\t\t Dequeue race: " << s.m_DequeueRace.get() << "\n"
463 << "\t\t Advance tail error: " << s.m_AdvanceTailError.get() << "\n"
464 << "\t\t Bad tail: " << s.m_BadTail.get() << "\n"
465 << "\t\tAdd basket attempts: " << s.m_TryAddBasket.get() << "\n"
466 << "\t\t Add basket success: " << s.m_AddBasketCount.get() << "\n";
468 static inline std::ostream& operator <<(std::ostream& o, cds::intrusive::basket_queue::empty_stat const& s)
473 template <typename Counter>
474 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::msqueue::stat<Counter> const& s )
478 << "\t\t Enqueue count: " << s.m_EnqueueCount.get() << "\n"
479 << "\t\t Enqueue race: " << s.m_EnqueueRace.get() << "\n"
480 << "\t\t Dequeue count: " << s.m_DequeueCount.get() << "\n"
481 << "\t\t Dequeue race: " << s.m_DequeueRace.get() << "\n"
482 << "\t\tAdvance tail error: " << s.m_AdvanceTailError.get() << "\n"
483 << "\t\t Bad tail: " << s.m_BadTail.get() << "\n";
486 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::msqueue::empty_stat const& s )
491 static inline std::ostream& operator <<( std::ostream& o, cds::opt::none )
496 // cds::intrusive::optimistic_queue::stat
497 template <typename Counter>
498 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::optimistic_queue::stat<Counter> const& s )
501 << static_cast<cds::intrusive::queue_stat<Counter> const&>( s )
503 << "\t\t fix list call: " << s.m_FixListCount.get() << "\n";
506 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::optimistic_queue::dummy_stat const& s )
511 // cds::intrusive::fcqueue::stat
512 template <typename Counter>
513 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::fcqueue::stat<Counter> const& s )
515 return o << "\tStatistics:\n"
516 << "\t Push: " << s.m_nEnqueue.get() << "\n"
517 << "\t Pop: " << s.m_nDequeue.get() << "\n"
518 << "\t FailedPop: " << s.m_nFailedDeq.get() << "\n"
519 << "\t Collided push/pop pair: " << s.m_nCollided.get() << "\n"
520 << "\tFlat combining statistics:\n"
521 << "\t Combining factor: " << s.combining_factor() << "\n"
522 << "\t Operation count: " << s.m_nOperationCount.get() << "\n"
523 << "\t Combine call count: " << s.m_nCombiningCount.get() << "\n"
524 << "\t Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
525 << "\t Deactivate pub-record: " << s.m_nDeactivatePubRecord.get() << "\n"
526 << "\t Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
527 << "\t Create pub-record: " << s.m_nPubRecordCreated.get() << "\n"
528 << "\t Delete pub-record: " << s.m_nPubRecordDeteted.get() << "\n"
529 << "\t Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
530 << "\t Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
533 static inline std::ostream& operator <<( std::ostream& o, cds::intrusive::fcqueue::empty_stat const& s )
538 static inline std::ostream& operator <<( std::ostream& o, queue::details::empty_stat const& s )
545 #endif // #ifndef __CDSUNIT_INTRUSIVE_QUEUE_TYPES_H