2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 CDSSTRESS_PQUEUE_TYPES_H
32 #define CDSSTRESS_PQUEUE_TYPES_H
34 #include <cds/urcu/general_instant.h>
35 #include <cds/urcu/general_buffered.h>
36 #include <cds/urcu/general_threaded.h>
37 #include <cds/urcu/signal_buffered.h>
39 #include <cds/container/mspriority_queue.h>
40 #include <cds/container/fcpriority_queue.h>
42 #include <cds/container/ellen_bintree_set_hp.h>
43 #include <cds/container/ellen_bintree_set_dhp.h>
44 #include <cds/container/ellen_bintree_set_rcu.h>
46 #include <cds/container/skip_list_set_hp.h>
47 #include <cds/container/skip_list_set_dhp.h>
48 #include <cds/container/skip_list_set_rcu.h>
50 #include <cds/sync/spinlock.h>
55 #include <mutex> //unique_lock
57 #include <boost/container/stable_vector.hpp>
58 #include <boost/container/deque.hpp>
60 #include <cds_test/stress_test.h>
61 #include <cds_test/stat_ellenbintree_out.h>
62 #include <cds_test/stat_skiplist_out.h>
63 #include <cds_test/stat_flat_combining_out.h>
66 namespace cc = cds::container;
67 namespace co = cds::opt;
70 template <typename T, typename Container, typename Lock, typename Less = std::less<typename Container::value_type> >
75 typedef std::priority_queue<value_type, Container, Less> pqueue_type;
81 typedef std::unique_lock<Lock> scoped_lock;
84 bool push( value_type const& val )
86 scoped_lock l( m_Lock );
91 bool pop( value_type& dest )
93 scoped_lock l( m_Lock );
94 if ( !m_PQueue.empty()) {
95 dest = m_PQueue.top();
102 template <typename Q, typename MoveFunc>
103 bool pop_with( Q& dest, MoveFunc f )
105 scoped_lock l( m_Lock );
106 if ( !m_PQueue.empty()) {
107 f( dest, m_PQueue.top());
116 scoped_lock l( m_Lock );
117 while ( !m_PQueue.empty())
121 template <typename Func>
122 void clear_with( Func f )
124 scoped_lock l( m_Lock );
125 while ( !m_PQueue.empty()) {
133 return m_PQueue.empty();
138 return m_PQueue.size();
141 cds::opt::none statistics() const
143 return cds::opt::none();
147 // EllenBinTree priority queue
148 template <typename GC>
149 struct EllenBinTreePQueue_pop_max
151 template <typename T, typename Tree>
152 bool operator()( T& dest, Tree& container ) const
154 typename Tree::guarded_ptr gp( container.extract_max());
161 template <typename RCU>
162 struct EllenBinTreePQueue_pop_max< cds::urcu::gc<RCU> >
164 template <typename T, typename Tree>
165 bool operator()( T& dest, Tree& container ) const
167 typename Tree::exempt_ptr ep( container.extract_max());
174 template <typename GC>
175 struct EllenBinTreePQueue_pop_min
177 template <typename T, typename Tree>
178 bool operator()( T& dest, Tree& container ) const
180 typename Tree::guarded_ptr gp( container.extract_min());
187 template <typename RCU>
188 struct EllenBinTreePQueue_pop_min< cds::urcu::gc<RCU> >
190 template <typename T, typename Tree>
191 bool operator()( T& dest, Tree& container ) const
193 typename Tree::exempt_ptr ep( container.extract_min());
200 template <typename GC, typename Key, typename T, typename Traits, bool Max = true>
201 class EllenBinTreePQueue : protected cds::container::EllenBinTreeSet< GC, Key, T, Traits >
203 typedef cds::container::EllenBinTreeSet< GC, Key, T, Traits > base_class;
204 template <typename GC2> friend struct EllenBinTreePQueue_pop_max;
205 template <typename GC2> friend struct EllenBinTreePQueue_pop_min;
208 typedef T value_type;
210 bool push( value_type const& val )
212 return base_class::insert( val );
215 bool pop( value_type& dest )
217 return Max ? EllenBinTreePQueue_pop_max< typename base_class::gc >()(dest, *this)
218 : EllenBinTreePQueue_pop_min< typename base_class::gc >()(dest, *this);
228 return base_class::empty();
233 return base_class::size();
236 typename base_class::stat const& statistics() const
238 return base_class::statistics();
243 // SkipList property queue
244 template <typename GC>
245 struct SkipListPQueue_pop_max
247 template <typename T, typename Set>
248 bool operator()( T& dest, Set& container ) const
250 typename Set::guarded_ptr gp( container.extract_max());
257 template <typename RCU>
258 struct SkipListPQueue_pop_max< cds::urcu::gc<RCU> >
260 template <typename T, typename Set>
261 bool operator()( T& dest, Set& container ) const
263 typename Set::exempt_ptr ep( container.extract_max());
270 template <typename GC>
271 struct SkipListPQueue_pop_min
273 template <typename T, typename Set>
274 bool operator()( T& dest, Set& container ) const
276 typename Set::guarded_ptr gp( container.extract_min());
283 template <typename RCU>
284 struct SkipListPQueue_pop_min< cds::urcu::gc<RCU> >
286 template <typename T, typename Set>
287 bool operator()( T& dest, Set& container ) const
289 typename Set::exempt_ptr ep( container.extract_min());
296 template <typename GC, typename T, typename Traits, bool Max = true>
297 class SkipListPQueue : protected cds::container::SkipListSet< GC, T, Traits >
299 typedef cds::container::SkipListSet< GC, T, Traits > base_class;
300 template <typename GC2> friend struct SkipListPQueue_pop_max;
301 template <typename GC2> friend struct SkipListPQueue_pop_min;
304 typedef T value_type;
306 bool push( value_type const& val )
308 return base_class::insert( val );
311 bool pop( value_type& dest )
313 return Max ? SkipListPQueue_pop_max< typename base_class::gc >()(dest, *this)
314 : SkipListPQueue_pop_min< typename base_class::gc >()(dest, *this);
324 return base_class::empty();
329 return base_class::size();
332 typename base_class::stat const& statistics() const
334 return base_class::statistics();
338 } // namespace details
340 template <typename Value>
343 static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
345 typedef std::less<Value> less;
348 int operator()( Value const& v1, Value const& v2 ) const
350 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
354 typedef cds::urcu::gc< cds::urcu::general_instant<> > rcu_gpi;
355 typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_gpb;
356 typedef cds::urcu::gc< cds::urcu::general_threaded<> > rcu_gpt;
357 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
358 typedef cds::urcu::gc< cds::urcu::signal_buffered<> > rcu_shb;
363 struct traits_MSPriorityQueue_static_less : public
364 cc::mspriority_queue::make_traits <
365 co::buffer < co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
368 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less;
370 struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits
372 typedef co::v::initialized_static_buffer< char, c_nBoundedCapacity > buffer;
373 typedef cc::mspriority_queue::stat<> stat;
375 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat;
377 struct traits_MSPriorityQueue_static_cmp : public
378 cc::mspriority_queue::make_traits <
379 co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
380 , co::compare < cmp >
383 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_cmp > MSPriorityQueue_static_cmp;
385 struct traits_MSPriorityQueue_static_mutex : public
386 cc::mspriority_queue::make_traits<
387 co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
388 , co::lock_type<std::mutex>
391 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
393 struct traits_MSPriorityQueue_dyn: public cc::mspriority_queue::traits
395 typedef co::v::initialized_dynamic_buffer< char > buffer;
397 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn > MSPriorityQueue_dyn_less;
399 struct traits_MSPriorityQueue_dyn_less_stat: public traits_MSPriorityQueue_dyn
401 typedef cc::mspriority_queue::stat<> stat;
403 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat;
406 struct traits_MSPriorityQueue_dyn_cmp : public
407 cc::mspriority_queue::make_traits <
408 co::buffer< co::v::initialized_dynamic_buffer< char > >
409 , co::compare < cmp >
412 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
414 struct traits_MSPriorityQueue_dyn_mutex : public
415 cc::mspriority_queue::make_traits <
416 co::buffer< co::v::initialized_dynamic_buffer< char > >
417 , co::lock_type < std::mutex >
420 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
423 // Priority queue based on EllenBinTreeSet
424 struct traits_EllenBinTree_max :
425 public cc::ellen_bintree::make_set_traits<
426 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
427 ,cc::opt::less< std::less<Value> >
428 ,co::stat< cc::ellen_bintree::stat<> >
431 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
432 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
433 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
434 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
435 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
436 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
437 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
440 struct traits_EllenBinTree_max_stat :
441 public cc::ellen_bintree::make_set_traits<
442 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
443 ,cc::opt::less< std::less<Value> >
444 ,co::stat< cc::ellen_bintree::stat<> >
447 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
448 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
449 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
450 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
451 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
452 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
453 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
456 struct traits_EllenBinTree_min :
457 public cc::ellen_bintree::make_set_traits<
458 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
459 ,cc::opt::less< std::greater<Value> >
462 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
463 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
464 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
465 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
466 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
467 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
468 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
471 struct traits_EllenBinTree_min_stat :
472 public cc::ellen_bintree::make_set_traits<
473 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
474 ,cc::opt::less< std::greater<Value> >
475 ,co::stat< cc::ellen_bintree::stat<> >
478 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
479 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
480 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
481 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
482 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
483 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
484 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
487 // Priority queue based on SkipListSet
488 struct traits_SkipList_max :
489 public cc::skip_list::make_traits <
490 cc::opt::less < std::less<Value> >
493 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList32_HP_max;
494 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList32_DHP_max;
495 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList32_RCU_gpi_max;
496 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList32_RCU_gpb_max;
497 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList32_RCU_gpt_max;
498 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
499 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList32_RCU_shb_max;
502 struct traits_SkipList24_max: public traits_SkipList_max
504 typedef cc::skip_list::turbo24 random_level_generator;
506 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max > SkipList24_HP_max;
507 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max > SkipList24_DHP_max;
508 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max > SkipList24_RCU_gpi_max;
509 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max > SkipList24_RCU_gpb_max;
510 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max > SkipList24_RCU_gpt_max;
511 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
512 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max > SkipList24_RCU_shb_max;
515 struct traits_SkipList16_max: public traits_SkipList_max
517 typedef cc::skip_list::turbo16 random_level_generator;
519 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max > SkipList16_HP_max;
520 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max > SkipList16_DHP_max;
521 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max > SkipList16_RCU_gpi_max;
522 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max > SkipList16_RCU_gpb_max;
523 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max > SkipList16_RCU_gpt_max;
524 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
525 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max > SkipList16_RCU_shb_max;
528 struct traits_SkipList_max_stat :
529 public cc::skip_list::make_traits<
530 cc::opt::less< std::less<Value> >
531 ,co::stat< cc::skip_list::stat<> >
534 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList32_HP_max_stat;
535 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList32_DHP_max_stat;
536 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList32_RCU_gpi_max_stat;
537 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList32_RCU_gpb_max_stat;
538 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList32_RCU_gpt_max_stat;
539 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
540 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList32_RCU_shb_max_stat;
543 struct traits_SkipList24_max_stat: public traits_SkipList_max_stat
545 typedef cc::skip_list::turbo24 random_level_generator;
547 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max_stat > SkipList24_HP_max_stat;
548 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max_stat > SkipList24_DHP_max_stat;
549 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpi_max_stat;
550 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpb_max_stat;
551 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpt_max_stat;
552 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
553 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max_stat > SkipList24_RCU_shb_max_stat;
556 struct traits_SkipList16_max_stat: public traits_SkipList_max_stat
558 typedef cc::skip_list::turbo16 random_level_generator;
560 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max_stat > SkipList16_HP_max_stat;
561 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max_stat > SkipList16_DHP_max_stat;
562 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpi_max_stat;
563 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpb_max_stat;
564 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpt_max_stat;
565 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
566 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max_stat > SkipList16_RCU_shb_max_stat;
569 struct traits_SkipList_min :
570 public cc::skip_list::make_traits<
571 cc::opt::less< std::greater<Value> >
574 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList32_HP_min;
575 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList32_DHP_min;
576 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList32_RCU_gpi_min;
577 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList32_RCU_gpb_min;
578 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList32_RCU_gpt_min;
579 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
580 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList32_RCU_shb_min;
583 struct traits_SkipList24_min: public traits_SkipList_min
585 typedef cc::skip_list::turbo24 random_level_generator;
587 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min > SkipList24_HP_min;
588 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min > SkipList24_DHP_min;
589 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min > SkipList24_RCU_gpi_min;
590 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min > SkipList24_RCU_gpb_min;
591 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min > SkipList24_RCU_gpt_min;
592 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
593 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min > SkipList24_RCU_shb_min;
596 struct traits_SkipList16_min: public traits_SkipList_min
598 typedef cc::skip_list::turbo16 random_level_generator;
600 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min > SkipList16_HP_min;
601 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min > SkipList16_DHP_min;
602 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min > SkipList16_RCU_gpi_min;
603 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min > SkipList16_RCU_gpb_min;
604 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min > SkipList16_RCU_gpt_min;
605 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
606 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min > SkipList16_RCU_shb_min;
609 struct traits_SkipList_min_stat :
610 public cc::skip_list::make_traits<
611 cc::opt::less< std::greater<Value> >
612 ,co::stat< cc::skip_list::stat<> >
615 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList32_HP_min_stat;
616 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList32_DHP_min_stat;
617 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpi_min_stat;
618 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpb_min_stat;
619 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpt_min_stat;
620 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
621 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_shb_min_stat;
624 struct traits_SkipList24_min_stat: public traits_SkipList_min_stat
626 typedef cc::skip_list::turbo24 random_level_generator;
628 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min_stat > SkipList24_HP_min_stat;
629 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min_stat > SkipList24_DHP_min_stat;
630 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpi_min_stat;
631 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpb_min_stat;
632 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpt_min_stat;
633 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
634 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min_stat > SkipList24_RCU_shb_min_stat;
637 struct traits_SkipList16_min_stat: public traits_SkipList_min_stat
639 typedef cc::skip_list::turbo16 random_level_generator;
641 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min_stat > SkipList16_HP_min_stat;
642 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min_stat > SkipList16_DHP_min_stat;
643 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpi_min_stat;
644 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpb_min_stat;
645 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpt_min_stat;
646 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
647 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min_stat > SkipList16_RCU_shb_min_stat;
652 struct traits_FCPQueue_stat : public
653 cds::container::fcpqueue::make_traits <
654 cds::opt::stat < cds::container::fcpqueue::stat<> >
658 typedef cds::container::FCPriorityQueue< Value > FCPQueue_vector;
659 typedef cds::container::FCPriorityQueue< Value
660 ,std::priority_queue<Value>
661 ,traits_FCPQueue_stat
662 > FCPQueue_vector_stat;
664 typedef cds::container::FCPriorityQueue< Value
665 ,std::priority_queue<Value, std::deque<Value> >
667 typedef cds::container::FCPriorityQueue< Value
668 ,std::priority_queue<Value, std::deque<Value> >
669 ,traits_FCPQueue_stat
670 > FCPQueue_deque_stat;
672 typedef cds::container::FCPriorityQueue< Value
673 ,std::priority_queue<Value, boost::container::deque<Value> >
674 > FCPQueue_boost_deque;
675 typedef cds::container::FCPriorityQueue< Value
676 ,std::priority_queue<Value, boost::container::deque<Value> >
677 ,traits_FCPQueue_stat
678 > FCPQueue_boost_deque_stat;
680 typedef cds::container::FCPriorityQueue< Value
681 ,std::priority_queue<Value, boost::container::stable_vector<Value> >
682 > FCPQueue_boost_stable_vector;
683 typedef cds::container::FCPriorityQueue< Value
684 ,std::priority_queue<Value, boost::container::stable_vector<Value> >
685 ,traits_FCPQueue_stat
686 > FCPQueue_boost_stable_vector_stat;
688 /// Standard priority_queue
689 typedef details::StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
690 typedef details::StdPQueue< Value, std::vector<Value>, std::mutex > StdPQueue_vector_mutex;
691 typedef details::StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
692 typedef details::StdPQueue< Value, std::deque<Value>, std::mutex > StdPQueue_deque_mutex;
695 } // namespace pqueue
698 // *********************************************
699 // Priority queue statistics
702 static inline property_stream& operator <<( property_stream& o, cds::opt::none )
707 static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::empty_stat const& )
712 static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::stat<> const& s )
715 << CDSSTRESS_STAT_OUT( s, m_nPush )
716 << CDSSTRESS_STAT_OUT( s, m_nPushMove )
717 << CDSSTRESS_STAT_OUT( s, m_nPop )
718 << CDSSTRESS_STAT_OUT( s, m_nFailedPop )
719 << static_cast<cds::algo::flat_combining::stat<> const&>(s);
722 static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::empty_stat const& /*s*/ )
727 static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::stat<> const& s )
730 << CDSSTRESS_STAT_OUT( s, m_nPushCount )
731 << CDSSTRESS_STAT_OUT( s, m_nPopCount )
732 << CDSSTRESS_STAT_OUT( s, m_nPushFailCount )
733 << CDSSTRESS_STAT_OUT( s, m_nPopFailCount )
734 << CDSSTRESS_STAT_OUT( s, m_nPushHeapifySwapCount )
735 << CDSSTRESS_STAT_OUT( s, m_nPopHeapifySwapCount )
736 << CDSSTRESS_STAT_OUT( s, m_nItemMovedTop )
737 << CDSSTRESS_STAT_OUT( s, m_nItemMovedUp )
738 << CDSSTRESS_STAT_OUT( s, m_nPushEmptyPass );
741 } // namespace cds_test
743 #endif // #ifndef CDSSTRESS_PQUEUE_TYPES_H