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 scoped_lock l( m_Lock );
134 return m_PQueue.empty();
139 scoped_lock l( m_Lock );
140 return m_PQueue.size();
143 cds::opt::none statistics() const
145 return cds::opt::none();
149 // EllenBinTree priority queue
150 template <typename GC>
151 struct EllenBinTreePQueue_pop_max
153 template <typename T, typename Tree>
154 bool operator()( T& dest, Tree& container ) const
156 typename Tree::guarded_ptr gp( container.extract_max());
163 template <typename RCU>
164 struct EllenBinTreePQueue_pop_max< cds::urcu::gc<RCU> >
166 template <typename T, typename Tree>
167 bool operator()( T& dest, Tree& container ) const
169 typename Tree::exempt_ptr ep( container.extract_max());
176 template <typename GC>
177 struct EllenBinTreePQueue_pop_min
179 template <typename T, typename Tree>
180 bool operator()( T& dest, Tree& container ) const
182 typename Tree::guarded_ptr gp( container.extract_min());
189 template <typename RCU>
190 struct EllenBinTreePQueue_pop_min< cds::urcu::gc<RCU> >
192 template <typename T, typename Tree>
193 bool operator()( T& dest, Tree& container ) const
195 typename Tree::exempt_ptr ep( container.extract_min());
202 template <typename GC, typename Key, typename T, typename Traits, bool Max = true>
203 class EllenBinTreePQueue : protected cds::container::EllenBinTreeSet< GC, Key, T, Traits >
205 typedef cds::container::EllenBinTreeSet< GC, Key, T, Traits > base_class;
206 template <typename GC2> friend struct EllenBinTreePQueue_pop_max;
207 template <typename GC2> friend struct EllenBinTreePQueue_pop_min;
210 typedef T value_type;
212 bool push( value_type const& val )
214 return base_class::insert( val );
217 bool pop( value_type& dest )
219 return Max ? EllenBinTreePQueue_pop_max< typename base_class::gc >()(dest, *this)
220 : EllenBinTreePQueue_pop_min< typename base_class::gc >()(dest, *this);
230 return base_class::empty();
235 return base_class::size();
238 typename base_class::stat const& statistics() const
240 return base_class::statistics();
245 // SkipList property queue
246 template <typename GC>
247 struct SkipListPQueue_pop_max
249 template <typename T, typename Set>
250 bool operator()( T& dest, Set& container ) const
252 typename Set::guarded_ptr gp( container.extract_max());
259 template <typename RCU>
260 struct SkipListPQueue_pop_max< cds::urcu::gc<RCU> >
262 template <typename T, typename Set>
263 bool operator()( T& dest, Set& container ) const
265 typename Set::exempt_ptr ep( container.extract_max());
272 template <typename GC>
273 struct SkipListPQueue_pop_min
275 template <typename T, typename Set>
276 bool operator()( T& dest, Set& container ) const
278 typename Set::guarded_ptr gp( container.extract_min());
285 template <typename RCU>
286 struct SkipListPQueue_pop_min< cds::urcu::gc<RCU> >
288 template <typename T, typename Set>
289 bool operator()( T& dest, Set& container ) const
291 typename Set::exempt_ptr ep( container.extract_min());
298 template <typename GC, typename T, typename Traits, bool Max = true>
299 class SkipListPQueue : protected cds::container::SkipListSet< GC, T, Traits >
301 typedef cds::container::SkipListSet< GC, T, Traits > base_class;
302 template <typename GC2> friend struct SkipListPQueue_pop_max;
303 template <typename GC2> friend struct SkipListPQueue_pop_min;
306 typedef T value_type;
308 bool push( value_type const& val )
310 return base_class::insert( val );
313 bool pop( value_type& dest )
315 return Max ? SkipListPQueue_pop_max< typename base_class::gc >()(dest, *this)
316 : SkipListPQueue_pop_min< typename base_class::gc >()(dest, *this);
326 return base_class::empty();
331 return base_class::size();
334 typename base_class::stat const& statistics() const
336 return base_class::statistics();
340 } // namespace details
342 template <typename Value>
345 static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
347 typedef std::less<Value> less;
350 int operator()( Value const& v1, Value const& v2 ) const
352 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
356 typedef cds::urcu::gc< cds::urcu::general_instant<> > rcu_gpi;
357 typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_gpb;
358 typedef cds::urcu::gc< cds::urcu::general_threaded<> > rcu_gpt;
359 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
360 typedef cds::urcu::gc< cds::urcu::signal_buffered<> > rcu_shb;
365 struct traits_MSPriorityQueue_static_less : public
366 cc::mspriority_queue::make_traits <
367 co::buffer < co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
370 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less;
372 struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits
374 typedef co::v::initialized_static_buffer< char, c_nBoundedCapacity > buffer;
375 typedef cc::mspriority_queue::stat<> stat;
377 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat;
379 struct traits_MSPriorityQueue_static_cmp : public
380 cc::mspriority_queue::make_traits <
381 co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
382 , co::compare < cmp >
385 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_cmp > MSPriorityQueue_static_cmp;
387 struct traits_MSPriorityQueue_static_mutex : public
388 cc::mspriority_queue::make_traits<
389 co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
390 , co::lock_type<std::mutex>
393 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
395 struct traits_MSPriorityQueue_dyn: public cc::mspriority_queue::traits
397 typedef co::v::initialized_dynamic_buffer< char > buffer;
399 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn > MSPriorityQueue_dyn_less;
401 struct traits_MSPriorityQueue_dyn_less_stat: public traits_MSPriorityQueue_dyn
403 typedef cc::mspriority_queue::stat<> stat;
405 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat;
408 struct traits_MSPriorityQueue_dyn_cmp : public
409 cc::mspriority_queue::make_traits <
410 co::buffer< co::v::initialized_dynamic_buffer< char > >
411 , co::compare < cmp >
414 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
416 struct traits_MSPriorityQueue_dyn_mutex : public
417 cc::mspriority_queue::make_traits <
418 co::buffer< co::v::initialized_dynamic_buffer< char > >
419 , co::lock_type < std::mutex >
422 typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
425 // Priority queue based on EllenBinTreeSet
426 struct traits_EllenBinTree_max :
427 public cc::ellen_bintree::make_set_traits<
428 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
429 ,cc::opt::less< std::less<Value> >
430 ,co::stat< cc::ellen_bintree::stat<> >
433 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
434 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
435 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
436 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
437 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
438 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
439 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
442 struct traits_EllenBinTree_max_stat :
443 public cc::ellen_bintree::make_set_traits<
444 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
445 ,cc::opt::less< std::less<Value> >
446 ,co::stat< cc::ellen_bintree::stat<> >
449 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
450 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
451 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
452 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
453 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
454 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
455 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
458 struct traits_EllenBinTree_min :
459 public cc::ellen_bintree::make_set_traits<
460 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
461 ,cc::opt::less< std::greater<Value> >
464 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
465 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
466 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
467 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
468 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
469 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
470 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
473 struct traits_EllenBinTree_min_stat :
474 public cc::ellen_bintree::make_set_traits<
475 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
476 ,cc::opt::less< std::greater<Value> >
477 ,co::stat< cc::ellen_bintree::stat<> >
480 typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
481 typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
482 typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
483 typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
484 typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
485 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
486 typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
489 // Priority queue based on SkipListSet
490 struct traits_SkipList_max :
491 public cc::skip_list::make_traits <
492 cc::opt::less < std::less<Value> >
495 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList32_HP_max;
496 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList32_DHP_max;
497 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList32_RCU_gpi_max;
498 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList32_RCU_gpb_max;
499 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList32_RCU_gpt_max;
500 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
501 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList32_RCU_shb_max;
504 struct traits_SkipList24_max: public traits_SkipList_max
506 typedef cc::skip_list::turbo24 random_level_generator;
508 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max > SkipList24_HP_max;
509 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max > SkipList24_DHP_max;
510 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max > SkipList24_RCU_gpi_max;
511 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max > SkipList24_RCU_gpb_max;
512 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max > SkipList24_RCU_gpt_max;
513 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
514 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max > SkipList24_RCU_shb_max;
517 struct traits_SkipList16_max: public traits_SkipList_max
519 typedef cc::skip_list::turbo16 random_level_generator;
521 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max > SkipList16_HP_max;
522 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max > SkipList16_DHP_max;
523 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max > SkipList16_RCU_gpi_max;
524 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max > SkipList16_RCU_gpb_max;
525 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max > SkipList16_RCU_gpt_max;
526 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
527 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max > SkipList16_RCU_shb_max;
530 struct traits_SkipList_max_stat :
531 public cc::skip_list::make_traits<
532 cc::opt::less< std::less<Value> >
533 ,co::stat< cc::skip_list::stat<> >
536 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList32_HP_max_stat;
537 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList32_DHP_max_stat;
538 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList32_RCU_gpi_max_stat;
539 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList32_RCU_gpb_max_stat;
540 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList32_RCU_gpt_max_stat;
541 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
542 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList32_RCU_shb_max_stat;
545 struct traits_SkipList24_max_stat: public traits_SkipList_max_stat
547 typedef cc::skip_list::turbo24 random_level_generator;
549 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max_stat > SkipList24_HP_max_stat;
550 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max_stat > SkipList24_DHP_max_stat;
551 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpi_max_stat;
552 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpb_max_stat;
553 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpt_max_stat;
554 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
555 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max_stat > SkipList24_RCU_shb_max_stat;
558 struct traits_SkipList16_max_stat: public traits_SkipList_max_stat
560 typedef cc::skip_list::turbo16 random_level_generator;
562 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max_stat > SkipList16_HP_max_stat;
563 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max_stat > SkipList16_DHP_max_stat;
564 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpi_max_stat;
565 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpb_max_stat;
566 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpt_max_stat;
567 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
568 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max_stat > SkipList16_RCU_shb_max_stat;
571 struct traits_SkipList_min :
572 public cc::skip_list::make_traits<
573 cc::opt::less< std::greater<Value> >
576 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList32_HP_min;
577 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList32_DHP_min;
578 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList32_RCU_gpi_min;
579 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList32_RCU_gpb_min;
580 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList32_RCU_gpt_min;
581 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
582 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList32_RCU_shb_min;
585 struct traits_SkipList24_min: public traits_SkipList_min
587 typedef cc::skip_list::turbo24 random_level_generator;
589 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min > SkipList24_HP_min;
590 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min > SkipList24_DHP_min;
591 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min > SkipList24_RCU_gpi_min;
592 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min > SkipList24_RCU_gpb_min;
593 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min > SkipList24_RCU_gpt_min;
594 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
595 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min > SkipList24_RCU_shb_min;
598 struct traits_SkipList16_min: public traits_SkipList_min
600 typedef cc::skip_list::turbo16 random_level_generator;
602 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min > SkipList16_HP_min;
603 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min > SkipList16_DHP_min;
604 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min > SkipList16_RCU_gpi_min;
605 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min > SkipList16_RCU_gpb_min;
606 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min > SkipList16_RCU_gpt_min;
607 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
608 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min > SkipList16_RCU_shb_min;
611 struct traits_SkipList_min_stat :
612 public cc::skip_list::make_traits<
613 cc::opt::less< std::greater<Value> >
614 ,co::stat< cc::skip_list::stat<> >
617 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList32_HP_min_stat;
618 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList32_DHP_min_stat;
619 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpi_min_stat;
620 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpb_min_stat;
621 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpt_min_stat;
622 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
623 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_shb_min_stat;
626 struct traits_SkipList24_min_stat: public traits_SkipList_min_stat
628 typedef cc::skip_list::turbo24 random_level_generator;
630 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min_stat > SkipList24_HP_min_stat;
631 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min_stat > SkipList24_DHP_min_stat;
632 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpi_min_stat;
633 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpb_min_stat;
634 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpt_min_stat;
635 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
636 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min_stat > SkipList24_RCU_shb_min_stat;
639 struct traits_SkipList16_min_stat: public traits_SkipList_min_stat
641 typedef cc::skip_list::turbo16 random_level_generator;
643 typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min_stat > SkipList16_HP_min_stat;
644 typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min_stat > SkipList16_DHP_min_stat;
645 typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpi_min_stat;
646 typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpb_min_stat;
647 typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpt_min_stat;
648 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
649 typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min_stat > SkipList16_RCU_shb_min_stat;
654 struct traits_FCPQueue_stat : public
655 cds::container::fcpqueue::make_traits <
656 cds::opt::stat < cds::container::fcpqueue::stat<> >
660 typedef cds::container::FCPriorityQueue< Value > FCPQueue_vector;
661 typedef cds::container::FCPriorityQueue< Value
662 ,std::priority_queue<Value>
663 ,traits_FCPQueue_stat
664 > FCPQueue_vector_stat;
666 typedef cds::container::FCPriorityQueue< Value
667 ,std::priority_queue<Value, std::deque<Value> >
669 typedef cds::container::FCPriorityQueue< Value
670 ,std::priority_queue<Value, std::deque<Value> >
671 ,traits_FCPQueue_stat
672 > FCPQueue_deque_stat;
674 typedef cds::container::FCPriorityQueue< Value
675 ,std::priority_queue<Value, boost::container::deque<Value> >
676 > FCPQueue_boost_deque;
677 typedef cds::container::FCPriorityQueue< Value
678 ,std::priority_queue<Value, boost::container::deque<Value> >
679 ,traits_FCPQueue_stat
680 > FCPQueue_boost_deque_stat;
682 typedef cds::container::FCPriorityQueue< Value
683 ,std::priority_queue<Value, boost::container::stable_vector<Value> >
684 > FCPQueue_boost_stable_vector;
685 typedef cds::container::FCPriorityQueue< Value
686 ,std::priority_queue<Value, boost::container::stable_vector<Value> >
687 ,traits_FCPQueue_stat
688 > FCPQueue_boost_stable_vector_stat;
690 /// Standard priority_queue
691 typedef details::StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
692 typedef details::StdPQueue< Value, std::vector<Value>, std::mutex > StdPQueue_vector_mutex;
693 typedef details::StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
694 typedef details::StdPQueue< Value, std::deque<Value>, std::mutex > StdPQueue_deque_mutex;
697 } // namespace pqueue
700 // *********************************************
701 // Priority queue statistics
704 static inline property_stream& operator <<( property_stream& o, cds::opt::none )
709 static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::empty_stat const& )
714 static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::stat<> const& s )
717 << CDSSTRESS_STAT_OUT( s, m_nPush )
718 << CDSSTRESS_STAT_OUT( s, m_nPushMove )
719 << CDSSTRESS_STAT_OUT( s, m_nPop )
720 << CDSSTRESS_STAT_OUT( s, m_nFailedPop )
721 << static_cast<cds::algo::flat_combining::stat<> const&>(s);
724 static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::empty_stat const& /*s*/ )
729 static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::stat<> const& s )
732 << CDSSTRESS_STAT_OUT( s, m_nPushCount )
733 << CDSSTRESS_STAT_OUT( s, m_nPopCount )
734 << CDSSTRESS_STAT_OUT( s, m_nPushFailCount )
735 << CDSSTRESS_STAT_OUT( s, m_nPopFailCount )
736 << CDSSTRESS_STAT_OUT( s, m_nPushHeapifySwapCount )
737 << CDSSTRESS_STAT_OUT( s, m_nPopHeapifySwapCount )
738 << CDSSTRESS_STAT_OUT( s, m_nItemMovedTop )
739 << CDSSTRESS_STAT_OUT( s, m_nItemMovedUp )
740 << CDSSTRESS_STAT_OUT( s, m_nPushEmptyPass );
743 } // namespace cds_test
745 #endif // #ifndef CDSSTRESS_PQUEUE_TYPES_H