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