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
 400         struct traits_MSPriorityQueue_dyn_bitreverse_less : public traits_MSPriorityQueue_dyn
 401         {
 402             typedef cds::bitop::bit_reverse_counter<> item_counter;
 403         };
 404         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_bitreverse_less > MSPriorityQueue_dyn_bitreverse_less;
 405
 406         struct traits_MSPriorityQueue_dyn_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_bitreverse_less
 407         {
 408             typedef cc::mspriority_queue::stat<> stat;
 409         };
 410         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_bitreverse_less_stat > MSPriorityQueue_dyn_bitreverse_less_stat;
 411
 412         struct traits_MSPriorityQueue_dyn_monotonic_less: public traits_MSPriorityQueue_dyn
 413         {
 414             typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter;
 415         };
 416         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_monotonic_less > MSPriorityQueue_dyn_monotonic_less;
 417
 418         struct traits_MSPriorityQueue_dyn_monotonic_less_stat: public traits_MSPriorityQueue_dyn_monotonic_less
 419         {
 420             typedef cc::mspriority_queue::stat<> stat;
 421         };
 422         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_monotonic_less_stat > MSPriorityQueue_dyn_monotonic_less_stat;
 423
 424
 425         struct traits_MSPriorityQueue_dyn_cmp : public
 426             cc::mspriority_queue::make_traits <
 427                 co::buffer< co::v::initialized_dynamic_buffer< char > >
 428                 , co::compare < cmp >
 429             > ::type
 430         {};
 431         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
 432
 433         struct traits_MSPriorityQueue_dyn_mutex : public
 434             cc::mspriority_queue::make_traits <
 435                 co::buffer< co::v::initialized_dynamic_buffer< char > >
 436                 , co::lock_type < std::mutex >
 437             > ::type
 438         {};
 439         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
 440
 441
 442         // Priority queue based on EllenBinTreeSet
 443         struct traits_EllenBinTree_max :
 444             public cc::ellen_bintree::make_set_traits<
 445                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 446                 ,cc::opt::less< std::less<Value> >
 447                 ,co::stat< cc::ellen_bintree::stat<> >
 448             >::type
 449         {};
 450         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
 451         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
 452         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
 453         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
 454         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
 455 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 456         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
 457         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_sht_max;
 458 #endif
 459
 460         struct traits_EllenBinTree_max_stat :
 461             public cc::ellen_bintree::make_set_traits<
 462                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 463                 ,cc::opt::less< std::less<Value> >
 464                 ,co::stat< cc::ellen_bintree::stat<> >
 465             >::type
 466         {};
 467         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
 468         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
 469         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
 470         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
 471         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
 472 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 473         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
 474         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_sht_max_stat;
 475 #endif
 476
 477         struct traits_EllenBinTree_min :
 478             public cc::ellen_bintree::make_set_traits<
 479                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 480                 ,cc::opt::less< std::greater<Value> >
 481             >::type
 482         {};
 483         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
 484         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
 485         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
 486         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
 487         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
 488 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 489         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
 490         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_sht_min;
 491 #endif
 492
 493         struct traits_EllenBinTree_min_stat :
 494             public cc::ellen_bintree::make_set_traits<
 495                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 496                 ,cc::opt::less< std::greater<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_min_stat, false > EllenBinTree_HP_min_stat;
 501         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
 502         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
 503         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
 504         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
 505 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 506         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
 507         typedef details::EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_sht_min_stat;
 508 #endif
 509
 510         // Priority queue based on SkipListSet
 511         struct traits_SkipList_max :
 512             public cc::skip_list::make_traits <
 513             cc::opt::less < std::less<Value> >
 514             > ::type
 515         {};
 516         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList_HP_max;
 517         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList_DHP_max;
 518         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList_RCU_gpi_max;
 519         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList_RCU_gpb_max;
 520         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList_RCU_gpt_max;
 521 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 522         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList_RCU_shb_max;
 523         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_max > SkipList_RCU_sht_max;
 524 #endif
 525
 526         struct traits_SkipList_max_stat :
 527             public cc::skip_list::make_traits<
 528                 cc::opt::less< std::less<Value> >
 529                 ,co::stat< cc::skip_list::stat<> >
 530             >::type
 531         {};
 532         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList_HP_max_stat;
 533         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList_DHP_max_stat;
 534         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList_RCU_gpi_max_stat;
 535         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList_RCU_gpb_max_stat;
 536         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList_RCU_gpt_max_stat;
 537 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 538         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList_RCU_shb_max_stat;
 539         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_max_stat > SkipList_RCU_sht_max_stat;
 540 #endif
 541
 542         struct traits_SkipList_min :
 543             public cc::skip_list::make_traits<
 544                 cc::opt::less< std::greater<Value> >
 545             >::type
 546         {};
 547         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList_HP_min;
 548         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList_DHP_min;
 549         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList_RCU_gpi_min;
 550         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList_RCU_gpb_min;
 551         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList_RCU_gpt_min;
 552 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 553         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList_RCU_shb_min;
 554         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_min, false > SkipList_RCU_sht_min;
 555 #endif
 556
 557         struct traits_SkipList_min_stat :
 558             public cc::skip_list::make_traits<
 559                 cc::opt::less< std::greater<Value> >
 560                 ,co::stat< cc::skip_list::stat<> >
 561             >::type
 562         {};
 563         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList_HP_min_stat;
 564         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList_DHP_min_stat;
 565         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpi_min_stat;
 566         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpb_min_stat;
 567         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpt_min_stat;
 568 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 569         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList_RCU_shb_min_stat;
 570         typedef details::SkipListPQueue< rcu_sht, Value, traits_SkipList_min_stat, false > SkipList_RCU_sht_min_stat;
 571 #endif
 572
 573
 574         // FCPriorityQueue
 575         struct traits_FCPQueue_stat : public
 576             cds::container::fcpqueue::make_traits <
 577             cds::opt::stat < cds::container::fcpqueue::stat<> >
 578             > ::type
 579         {};
 580
 581         typedef cds::container::FCPriorityQueue< Value >    FCPQueue_vector;
 582         typedef cds::container::FCPriorityQueue< Value
 583             ,std::priority_queue<Value>
 584             ,traits_FCPQueue_stat
 585         >    FCPQueue_vector_stat;
 586
 587         typedef cds::container::FCPriorityQueue< Value
 588             ,std::priority_queue<Value, std::deque<Value> >
 589         > FCPQueue_deque;
 590         typedef cds::container::FCPriorityQueue< Value
 591             ,std::priority_queue<Value, std::deque<Value> >
 592             ,traits_FCPQueue_stat
 593         > FCPQueue_deque_stat;
 594
 595         typedef cds::container::FCPriorityQueue< Value
 596             ,std::priority_queue<Value, boost::container::deque<Value> >
 597         > FCPQueue_boost_deque;
 598         typedef cds::container::FCPriorityQueue< Value
 599             ,std::priority_queue<Value, boost::container::deque<Value> >
 600             ,traits_FCPQueue_stat
 601         > FCPQueue_boost_deque_stat;
 602
 603         typedef cds::container::FCPriorityQueue< Value
 604             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 605         > FCPQueue_boost_stable_vector;
 606         typedef cds::container::FCPriorityQueue< Value
 607             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 608             ,traits_FCPQueue_stat
 609         > FCPQueue_boost_stable_vector_stat;
 610
 611         /// Standard priority_queue
 612         typedef details::StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
 613         typedef details::StdPQueue< Value, std::vector<Value>, std::mutex >  StdPQueue_vector_mutex;
 614         typedef details::StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
 615         typedef details::StdPQueue< Value, std::deque<Value>,  std::mutex >  StdPQueue_deque_mutex;
 616     };
 617
 618 }   // namespace pqueue
 619
 620
 621 // *********************************************
 622 // Priority queue statistics
 623 namespace cds_test {
 624
 625     static inline property_stream& operator <<( property_stream& o, cds::opt::none )
 626     {
 627         return o;
 628     }
 629
 630     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::empty_stat const& )
 631     {
 632         return o;
 633     }
 634
 635     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::stat<> const& s )
 636     {
 637         return o
 638             << CDSSTRESS_STAT_OUT( s, m_nPush )
 639             << CDSSTRESS_STAT_OUT( s, m_nPushMove )
 640             << CDSSTRESS_STAT_OUT( s, m_nPop )
 641             << CDSSTRESS_STAT_OUT( s, m_nFailedPop )
 642             << static_cast<cds::algo::flat_combining::stat<> const&>(s);
 643     }
 644
 645     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::empty_stat const& /*s*/ )
 646     {
 647         return o;
 648     }
 649
 650     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::stat<> const& s )
 651     {
 652         return o
 653             << CDSSTRESS_STAT_OUT( s, m_nPushCount )
 654             << CDSSTRESS_STAT_OUT( s, m_nPopCount )
 655             << CDSSTRESS_STAT_OUT( s, m_nPushFailCount )
 656             << CDSSTRESS_STAT_OUT( s, m_nPopFailCount )
 657             << CDSSTRESS_STAT_OUT( s, m_nPushHeapifySwapCount )
 658             << CDSSTRESS_STAT_OUT( s, m_nPopHeapifySwapCount )
 659             << CDSSTRESS_STAT_OUT( s, m_nItemMovedTop )
 660             << CDSSTRESS_STAT_OUT( s, m_nItemMovedUp )
 661             << CDSSTRESS_STAT_OUT( s, m_nPushEmptyPass );
 662     }
 663
 664 } // namespace cds_test
 665
 666 #endif // #ifndef CDSSTRESS_PQUEUE_TYPES_H