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