test/stress/pqueue/pqueue_type.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #ifndef CDSSTRESS_PQUEUE_TYPES_H
  32 #define CDSSTRESS_PQUEUE_TYPES_H
  33
  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>
  38 #include <cds/urcu/signal_threaded.h>
  39
  40 #include <cds/container/mspriority_queue.h>
  41 #include <cds/container/fcpriority_queue.h>
  42
  43 #include <cds/container/ellen_bintree_set_hp.h>
  44 #include <cds/container/ellen_bintree_set_dhp.h>
  45 #include <cds/container/ellen_bintree_set_rcu.h>
  46
  47 #include <cds/container/skip_list_set_hp.h>
  48 #include <cds/container/skip_list_set_dhp.h>
  49 #include <cds/container/skip_list_set_rcu.h>
  50
  51 #include <cds/sync/spinlock.h>
  52
  53 #include <queue>
  54 #include <vector>
  55 #include <deque>
  56 #include <mutex> //unique_lock
  57
  58 #include <boost/container/stable_vector.hpp>
  59 #include <boost/container/deque.hpp>
  60
  61 #include <cds_test/stress_test.h>
  62 #include <cds_test/stat_ellenbintree_out.h>
  63 #include <cds_test/stat_skiplist_out.h>
  64 #include <cds_test/stat_flat_combining_out.h>
  65
  66 namespace pqueue {
  67     namespace cc = cds::container;
  68     namespace co = cds::opt;
  69
  70     namespace details {
  71         template <typename T, typename Container, typename Lock, typename Less = std::less<typename Container::value_type> >
  72         class StdPQueue
  73         {
  74         public:
  75             typedef T value_type;
  76             typedef std::priority_queue<value_type, Container, Less> pqueue_type;
  77
  78         private:
  79             pqueue_type     m_PQueue;
  80             mutable Lock    m_Lock;
  81
  82             typedef std::unique_lock<Lock> scoped_lock;
  83
  84         public:
  85             bool push( value_type const& val )
  86             {
  87                 scoped_lock l( m_Lock );
  88                 m_PQueue.push( val );
  89                 return true;
  90             }
  91
  92             bool pop( value_type& dest )
  93             {
  94                 scoped_lock l( m_Lock );
  95                 if ( !m_PQueue.empty() ) {
  96                     dest = m_PQueue.top();
  97                     m_PQueue.pop();
  98                     return true;
  99                 }
 100                 return false;
 101             }
 102
 103             template <typename Q, typename MoveFunc>
 104             bool pop_with( Q& dest, MoveFunc f )
 105             {
 106                 scoped_lock l( m_Lock );
 107                 if ( !m_PQueue.empty() ) {
 108                     f( dest, m_PQueue.top() );
 109                     m_PQueue.pop();
 110                     return true;
 111                 }
 112                 return false;
 113             }
 114
 115             void clear()
 116             {
 117                 scoped_lock l( m_Lock );
 118                 while ( !m_PQueue.empty() )
 119                     m_PQueue.pop();
 120             }
 121
 122             template <typename Func>
 123             void clear_with( Func f )
 124             {
 125                 scoped_lock l( m_Lock );
 126                 while ( !m_PQueue.empty() ) {
 127                     f( m_PQueue.top() );
 128                     m_PQueue.pop();
 129                 }
 130             }
 131
 132             bool empty() const
 133             {
 134                 return m_PQueue.empty();
 135             }
 136
 137             size_t size() const
 138             {
 139                 return m_PQueue.size();
 140             }
 141
 142             cds::opt::none statistics() const
 143             {
 144                 return cds::opt::none();
 145             }
 146         };
 147
 148         // EllenBinTree priority queue
 149         template <typename GC>
 150         struct EllenBinTreePQueue_pop_max
 151         {
 152             template <typename T, typename Tree>
 153             bool operator()( T& dest, Tree& container ) const
 154             {
 155                 typename Tree::guarded_ptr gp( container.extract_max() );
 156                 if ( gp )
 157                     dest = *gp;
 158                 return !gp.empty();
 159             }
 160         };
 161
 162         template <typename RCU>
 163         struct EllenBinTreePQueue_pop_max< cds::urcu::gc<RCU> >
 164         {
 165             template <typename T, typename Tree>
 166             bool operator()( T& dest, Tree& container ) const
 167             {
 168                 typename Tree::exempt_ptr ep( container.extract_max() );
 169                 if ( ep )
 170                     dest = *ep;
 171                 return !ep.empty();
 172             }
 173         };
 174
 175         template <typename GC>
 176         struct EllenBinTreePQueue_pop_min
 177         {
 178             template <typename T, typename Tree>
 179             bool operator()( T& dest, Tree& container ) const
 180             {
 181                 typename Tree::guarded_ptr gp( container.extract_min() );
 182                 if ( gp )
 183                     dest = *gp;
 184                 return !gp.empty();
 185             }
 186         };
 187
 188         template <typename RCU>
 189         struct EllenBinTreePQueue_pop_min< cds::urcu::gc<RCU> >
 190         {
 191             template <typename T, typename Tree>
 192             bool operator()( T& dest, Tree& container ) const
 193             {
 194                 typename Tree::exempt_ptr ep( container.extract_min() );
 195                 if ( ep )
 196                     dest = *ep;
 197                 return !ep.empty();
 198             }
 199         };
 200
 201         template <typename GC, typename Key, typename T, typename Traits, bool Max = true>
 202         class EllenBinTreePQueue : protected cds::container::EllenBinTreeSet< GC, Key, T, Traits >
 203         {
 204             typedef cds::container::EllenBinTreeSet< GC, Key, T, Traits > base_class;
 205             template <typename GC2> friend struct EllenBinTreePQueue_pop_max;
 206             template <typename GC2> friend struct EllenBinTreePQueue_pop_min;
 207
 208         public:
 209             typedef T value_type;
 210
 211             bool push( value_type const& val )
 212             {
 213                 return base_class::insert( val );
 214             }
 215
 216             bool pop( value_type& dest )
 217             {
 218                 return Max ? EllenBinTreePQueue_pop_max< typename base_class::gc >()(dest, *this)
 219                     : EllenBinTreePQueue_pop_min< typename base_class::gc >()(dest, *this);
 220             }
 221
 222             void clear()
 223             {
 224                 base_class::clear();
 225             }
 226
 227             bool empty() const
 228             {
 229                 return base_class::empty();
 230             }
 231
 232             size_t size() const
 233             {
 234                 return base_class::size();
 235             }
 236
 237             typename base_class::stat const& statistics() const
 238             {
 239                 return base_class::statistics();
 240             }
 241         };
 242
 243
 244         // SkipList property queue
 245         template <typename GC>
 246         struct SkipListPQueue_pop_max
 247         {
 248             template <typename T, typename Set>
 249             bool operator()( T& dest, Set& container ) const
 250             {
 251                 typename Set::guarded_ptr gp( container.extract_max() );
 252                 if ( gp )
 253                     dest = *gp;
 254                 return !gp.empty();
 255             }
 256         };
 257
 258         template <typename RCU>
 259         struct SkipListPQueue_pop_max< cds::urcu::gc<RCU> >
 260         {
 261             template <typename T, typename Set>
 262             bool operator()( T& dest, Set& container ) const
 263             {
 264                 typename Set::exempt_ptr ep( container.extract_max() );
 265                 if ( ep )
 266                     dest = *ep;
 267                 return !ep.empty();
 268             }
 269         };
 270
 271         template <typename GC>
 272         struct SkipListPQueue_pop_min
 273         {
 274             template <typename T, typename Set>
 275             bool operator()( T& dest, Set& container ) const
 276             {
 277                 typename Set::guarded_ptr gp( container.extract_min() );
 278                 if ( gp )
 279                     dest = *gp;
 280                 return !gp.empty();
 281             }
 282         };
 283
 284         template <typename RCU>
 285         struct SkipListPQueue_pop_min< cds::urcu::gc<RCU> >
 286         {
 287             template <typename T, typename Set>
 288             bool operator()( T& dest, Set& container ) const
 289             {
 290                 typename Set::exempt_ptr ep( container.extract_min() );
 291                 if ( ep )
 292                     dest = *ep;
 293                 return !ep.empty();
 294             }
 295         };
 296
 297         template <typename GC, typename T, typename Traits, bool Max = true>
 298         class SkipListPQueue : protected cds::container::SkipListSet< GC, T, Traits >
 299         {
 300             typedef cds::container::SkipListSet< GC, T, Traits > base_class;
 301             template <typename GC2> friend struct SkipListPQueue_pop_max;
 302             template <typename GC2> friend struct SkipListPQueue_pop_min;
 303
 304         public:
 305             typedef T value_type;
 306
 307             bool push( value_type const& val )
 308             {
 309                 return base_class::insert( val );
 310             }
 311
 312             bool pop( value_type& dest )
 313             {
 314                 return Max ? SkipListPQueue_pop_max< typename base_class::gc >()(dest, *this)
 315                     : SkipListPQueue_pop_min< typename base_class::gc >()(dest, *this);
 316             }
 317
 318             void clear()
 319             {
 320                 base_class::clear();
 321             }
 322
 323             bool empty() const
 324             {
 325                 return base_class::empty();
 326             }
 327
 328             size_t size() const
 329             {
 330                 return base_class::size();
 331             }
 332
 333             typename base_class::stat const& statistics() const
 334             {
 335                 return base_class::statistics();
 336             }
 337         };
 338
 339     } // namespace details
 340
 341     template <typename Value>
 342     struct Types
 343     {
 344         static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
 345
 346         typedef std::less<Value>    less;
 347
 348         struct cmp {
 349             int operator()( Value const& v1, Value const& v2 ) const
 350             {
 351                 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
 352             }
 353         };
 354
 355         typedef cds::urcu::gc< cds::urcu::general_instant<> >   rcu_gpi;
 356         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  rcu_gpb;
 357         typedef cds::urcu::gc< cds::urcu::general_threaded<> >  rcu_gpt;
 358 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 359         typedef cds::urcu::gc< cds::urcu::signal_buffered<> >  rcu_shb;
 360         typedef cds::urcu::gc< cds::urcu::signal_threaded<> >  rcu_sht;
 361 #endif
 362
 363
 364         // MSPriorityQueue
 365         struct traits_MSPriorityQueue_static_less : public
 366             cc::mspriority_queue::make_traits <
 367                 co::buffer < co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
 368             > ::type
 369         {};
 370         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less;
 371
 372         struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits
 373         {
 374             typedef co::v::initialized_static_buffer< char, c_nBoundedCapacity > buffer;
 375             typedef cc::mspriority_queue::stat<> stat;
 376         };
 377         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat;
 378
 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 >
 383             > ::type
 384         {};
 385         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_cmp > MSPriorityQueue_static_cmp;
 386
 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>
 391             >::type
 392         {};
 393         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
 394
 395         struct traits_MSPriorityQueue_dyn: public cc::mspriority_queue::traits
 396         {
 397             typedef co::v::initialized_dynamic_buffer< char > buffer;
 398         };
 399         struct traits_MSPriorityQueue_dyn_fair: public traits_MSPriorityQueue_dyn
 400         {
 401             enum { fairness = true };
 402         };
 403         struct traits_MSPriorityQueue_dyn_unfair: public traits_MSPriorityQueue_dyn
 404         {
 405             enum { fairness = false };
 406         };
 407
 408
 409         struct traits_MSPriorityQueue_dyn_fair_bitreverse_less : public traits_MSPriorityQueue_dyn_fair
 410         {
 411             typedef cds::bitop::bit_reverse_counter<> item_counter;
 412         };
 413         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_bitreverse_less > MSPriorityQueue_dyn_fair_bitreverse_less;
 414
 415         struct traits_MSPriorityQueue_dyn_fair_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_fair_bitreverse_less
 416         {
 417             typedef cc::mspriority_queue::stat<> stat;
 418         };
 419         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_bitreverse_less_stat > MSPriorityQueue_dyn_fair_bitreverse_less_stat;
 420
 421         struct traits_MSPriorityQueue_dyn_fair_monotonic_less: public traits_MSPriorityQueue_dyn_fair
 422         {
 423             typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter;
 424         };
 425         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_monotonic_less > MSPriorityQueue_dyn_fair_monotonic_less;
 426
 427         struct traits_MSPriorityQueue_dyn_fair_monotonic_less_stat: public traits_MSPriorityQueue_dyn_fair_monotonic_less
 428         {
 429             typedef cc::mspriority_queue::stat<> stat;
 430         };
 431         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_monotonic_less_stat > MSPriorityQueue_dyn_fair_monotonic_less_stat;
 432
 433         struct traits_MSPriorityQueue_dyn_unfair_bitreverse_less: public traits_MSPriorityQueue_dyn_unfair
 434         {
 435             typedef cds::bitop::bit_reverse_counter<> item_counter;
 436         };
 437         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_bitreverse_less > MSPriorityQueue_dyn_unfair_bitreverse_less;
 438
 439         struct traits_MSPriorityQueue_dyn_unfair_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_unfair_bitreverse_less
 440         {
 441             typedef cc::mspriority_queue::stat<> stat;
 442         };
 443         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_bitreverse_less_stat > MSPriorityQueue_dyn_unfair_bitreverse_less_stat;
 444
 445         struct traits_MSPriorityQueue_dyn_unfair_monotonic_less: public traits_MSPriorityQueue_dyn_unfair
 446         {
 447             typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter;
 448         };
 449         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_monotonic_less > MSPriorityQueue_dyn_unfair_monotonic_less;
 450
 451         struct traits_MSPriorityQueue_dyn_unfair_monotonic_less_stat: public traits_MSPriorityQueue_dyn_unfair_monotonic_less
 452         {
 453             typedef cc::mspriority_queue::stat<> stat;
 454         };
 455         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_monotonic_less_stat > MSPriorityQueue_dyn_unfair_monotonic_less_stat;
 456
 457
 458         struct traits_MSPriorityQueue_dyn_cmp : public
 459             cc::mspriority_queue::make_traits <
 460                 co::buffer< co::v::initialized_dynamic_buffer< char > >
 461                 , co::compare < cmp >
 462             > ::type
 463         {};
 464         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
 465
 466         struct traits_MSPriorityQueue_dyn_mutex : public
 467             cc::mspriority_queue::make_traits <
 468                 co::buffer< co::v::initialized_dynamic_buffer< char > >
 469                 , co::lock_type < std::mutex >
 470             > ::type
 471         {};
 472         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
 473
 474
 475         // Priority queue based on EllenBinTreeSet
 476         struct traits_EllenBinTree_max :
 477             public cc::ellen_bintree::make_set_traits<
 478                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 479                 ,cc::opt::less< std::less<Value> >
 480                 ,co::stat< cc::ellen_bintree::stat<> >
 481             >::type
 482         {};
 483         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
 484         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
 485         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
 486         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
 487         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
 488 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 489         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
 490         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_sht_max;
 491 #endif
 492
 493         struct traits_EllenBinTree_max_stat :
 494             public cc::ellen_bintree::make_set_traits<
 495                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 496                 ,cc::opt::less< std::less<Value> >
 497                 ,co::stat< cc::ellen_bintree::stat<> >
 498             >::type
 499         {};
 500         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
 501         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
 502         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
 503         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
 504         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
 505 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 506         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
 507         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_sht_max_stat;
 508 #endif
 509
 510         struct traits_EllenBinTree_min :
 511             public cc::ellen_bintree::make_set_traits<
 512                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 513                 ,cc::opt::less< std::greater<Value> >
 514             >::type
 515         {};
 516         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
 517         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
 518         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
 519         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
 520         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
 521 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 522         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
 523         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_sht_min;
 524 #endif
 525
 526         struct traits_EllenBinTree_min_stat :
 527             public cc::ellen_bintree::make_set_traits<
 528                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 529                 ,cc::opt::less< std::greater<Value> >
 530                 ,co::stat< cc::ellen_bintree::stat<> >
 531             >::type
 532         {};
 533         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
 534         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
 535         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
 536         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
 537         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
 538 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 539         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
 540         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_sht_min_stat;
 541 #endif
 542
 543         // Priority queue based on SkipListSet
 544         struct traits_SkipList_max :
 545             public cc::skip_list::make_traits <
 546             cc::opt::less < std::less<Value> >
 547             > ::type
 548         {};
 549         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList_HP_max;
 550         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList_DHP_max;
 551         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList_RCU_gpi_max;
 552         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList_RCU_gpb_max;
 553         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList_RCU_gpt_max;
 554 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 555         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList_RCU_shb_max;
 556         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_max > SkipList_RCU_sht_max;
 557 #endif
 558
 559         struct traits_SkipList_max_stat :
 560             public cc::skip_list::make_traits<
 561                 cc::opt::less< std::less<Value> >
 562                 ,co::stat< cc::skip_list::stat<> >
 563             >::type
 564         {};
 565         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList_HP_max_stat;
 566         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList_DHP_max_stat;
 567         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList_RCU_gpi_max_stat;
 568         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList_RCU_gpb_max_stat;
 569         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList_RCU_gpt_max_stat;
 570 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 571         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList_RCU_shb_max_stat;
 572         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_max_stat > SkipList_RCU_sht_max_stat;
 573 #endif
 574
 575         struct traits_SkipList_min :
 576             public cc::skip_list::make_traits<
 577                 cc::opt::less< std::greater<Value> >
 578             >::type
 579         {};
 580         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList_HP_min;
 581         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList_DHP_min;
 582         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList_RCU_gpi_min;
 583         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList_RCU_gpb_min;
 584         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList_RCU_gpt_min;
 585 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 586         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList_RCU_shb_min;
 587         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_min, false > SkipList_RCU_sht_min;
 588 #endif
 589
 590         struct traits_SkipList_min_stat :
 591             public cc::skip_list::make_traits<
 592                 cc::opt::less< std::greater<Value> >
 593                 ,co::stat< cc::skip_list::stat<> >
 594             >::type
 595         {};
 596         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList_HP_min_stat;
 597         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList_DHP_min_stat;
 598         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpi_min_stat;
 599         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpb_min_stat;
 600         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpt_min_stat;
 601 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 602         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList_RCU_shb_min_stat;
 603         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_min_stat, false > SkipList_RCU_sht_min_stat;
 604 #endif
 605
 606
 607         // FCPriorityQueue
 608         struct traits_FCPQueue_stat : public
 609             cds::container::fcpqueue::make_traits <
 610             cds::opt::stat < cds::container::fcpqueue::stat<> >
 611             > ::type
 612         {};
 613
 614         typedef cds::container::FCPriorityQueue< Value >    FCPQueue_vector;
 615         typedef cds::container::FCPriorityQueue< Value
 616             ,std::priority_queue<Value>
 617             ,traits_FCPQueue_stat
 618         >    FCPQueue_vector_stat;
 619
 620         typedef cds::container::FCPriorityQueue< Value
 621             ,std::priority_queue<Value, std::deque<Value> >
 622         > FCPQueue_deque;
 623         typedef cds::container::FCPriorityQueue< Value
 624             ,std::priority_queue<Value, std::deque<Value> >
 625             ,traits_FCPQueue_stat
 626         > FCPQueue_deque_stat;
 627
 628         typedef cds::container::FCPriorityQueue< Value
 629             ,std::priority_queue<Value, boost::container::deque<Value> >
 630         > FCPQueue_boost_deque;
 631         typedef cds::container::FCPriorityQueue< Value
 632             ,std::priority_queue<Value, boost::container::deque<Value> >
 633             ,traits_FCPQueue_stat
 634         > FCPQueue_boost_deque_stat;
 635
 636         typedef cds::container::FCPriorityQueue< Value
 637             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 638         > FCPQueue_boost_stable_vector;
 639         typedef cds::container::FCPriorityQueue< Value
 640             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 641             ,traits_FCPQueue_stat
 642         > FCPQueue_boost_stable_vector_stat;
 643
 644         /// Standard priority_queue
 645         typedef details::StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
 646         typedef details::StdPQueue< Value, std::vector<Value>, std::mutex >  StdPQueue_vector_mutex;
 647         typedef details::StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
 648         typedef details::StdPQueue< Value, std::deque<Value>,  std::mutex >  StdPQueue_deque_mutex;
 649     };
 650
 651 }   // namespace pqueue
 652
 653
 654 // *********************************************
 655 // Priority queue statistics
 656 namespace cds_test {
 657
 658     static inline property_stream& operator <<( property_stream& o, cds::opt::none )
 659     {
 660         return o;
 661     }
 662
 663     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::empty_stat const& )
 664     {
 665         return o;
 666     }
 667
 668     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::stat<> const& s )
 669     {
 670         return o
 671             << CDSSTRESS_STAT_OUT( s, m_nPush )
 672             << CDSSTRESS_STAT_OUT( s, m_nPushMove )
 673             << CDSSTRESS_STAT_OUT( s, m_nPop )
 674             << CDSSTRESS_STAT_OUT( s, m_nFailedPop )
 675             << static_cast<cds::algo::flat_combining::stat<> const&>(s);
 676     }
 677
 678     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::empty_stat const& /*s*/ )
 679     {
 680         return o;
 681     }
 682
 683     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::stat<> const& s )
 684     {
 685         return o
 686             << CDSSTRESS_STAT_OUT( s, m_nPushCount )
 687             << CDSSTRESS_STAT_OUT( s, m_nPopCount )
 688             << CDSSTRESS_STAT_OUT( s, m_nPushFailCount )
 689             << CDSSTRESS_STAT_OUT( s, m_nPopFailCount )
 690             << CDSSTRESS_STAT_OUT( s, m_nPushHeapifySwapCount )
 691             << CDSSTRESS_STAT_OUT( s, m_nPopHeapifySwapCount )
 692             << CDSSTRESS_STAT_OUT( s, m_nItemMovedTop )
 693             << CDSSTRESS_STAT_OUT( s, m_nItemMovedUp )
 694             << CDSSTRESS_STAT_OUT( s, m_nPushEmptyPass );
 695     }
 696
 697 } // namespace cds_test
 698
 699 #endif // #ifndef CDSSTRESS_PQUEUE_TYPES_H