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
  39 #include <cds/container/mspriority_queue.h>
  40 #include <cds/container/fcpriority_queue.h>
  41
  42 #include <cds/container/ellen_bintree_set_hp.h>
  43 #include <cds/container/ellen_bintree_set_dhp.h>
  44 #include <cds/container/ellen_bintree_set_rcu.h>
  45
  46 #include <cds/container/skip_list_set_hp.h>
  47 #include <cds/container/skip_list_set_dhp.h>
  48 #include <cds/container/skip_list_set_rcu.h>
  49
  50 #include <cds/sync/spinlock.h>
  51
  52 #include <queue>
  53 #include <vector>
  54 #include <deque>
  55 #include <mutex> //unique_lock
  56
  57 #include <boost/container/stable_vector.hpp>
  58 #include <boost/container/deque.hpp>
  59
  60 #include <cds_test/stress_test.h>
  61 #include <cds_test/stat_ellenbintree_out.h>
  62 #include <cds_test/stat_skiplist_out.h>
  63 #include <cds_test/stat_flat_combining_out.h>
  64
  65 namespace pqueue {
  66     namespace cc = cds::container;
  67     namespace co = cds::opt;
  68
  69     namespace details {
  70         template <typename T, typename Container, typename Lock, typename Less = std::less<typename Container::value_type> >
  71         class StdPQueue
  72         {
  73         public:
  74             typedef T value_type;
  75             typedef std::priority_queue<value_type, Container, Less> pqueue_type;
  76
  77         private:
  78             pqueue_type     m_PQueue;
  79             mutable Lock    m_Lock;
  80
  81             typedef std::unique_lock<Lock> scoped_lock;
  82
  83         public:
  84             bool push( value_type const& val )
  85             {
  86                 scoped_lock l( m_Lock );
  87                 m_PQueue.push( val );
  88                 return true;
  89             }
  90
  91             bool pop( value_type& dest )
  92             {
  93                 scoped_lock l( m_Lock );
  94                 if ( !m_PQueue.empty()) {
  95                     dest = m_PQueue.top();
  96                     m_PQueue.pop();
  97                     return true;
  98                 }
  99                 return false;
 100             }
 101
 102             template <typename Q, typename MoveFunc>
 103             bool pop_with( Q& dest, MoveFunc f )
 104             {
 105                 scoped_lock l( m_Lock );
 106                 if ( !m_PQueue.empty()) {
 107                     f( dest, m_PQueue.top());
 108                     m_PQueue.pop();
 109                     return true;
 110                 }
 111                 return false;
 112             }
 113
 114             void clear()
 115             {
 116                 scoped_lock l( m_Lock );
 117                 while ( !m_PQueue.empty())
 118                     m_PQueue.pop();
 119             }
 120
 121             template <typename Func>
 122             void clear_with( Func f )
 123             {
 124                 scoped_lock l( m_Lock );
 125                 while ( !m_PQueue.empty()) {
 126                     f( m_PQueue.top());
 127                     m_PQueue.pop();
 128                 }
 129             }
 130
 131             bool empty() const
 132             {
 133                 return m_PQueue.empty();
 134             }
 135
 136             size_t size() const
 137             {
 138                 return m_PQueue.size();
 139             }
 140
 141             cds::opt::none statistics() const
 142             {
 143                 return cds::opt::none();
 144             }
 145         };
 146
 147         // EllenBinTree priority queue
 148         template <typename GC>
 149         struct EllenBinTreePQueue_pop_max
 150         {
 151             template <typename T, typename Tree>
 152             bool operator()( T& dest, Tree& container ) const
 153             {
 154                 typename Tree::guarded_ptr gp( container.extract_max());
 155                 if ( gp )
 156                     dest = *gp;
 157                 return !gp.empty();
 158             }
 159         };
 160
 161         template <typename RCU>
 162         struct EllenBinTreePQueue_pop_max< cds::urcu::gc<RCU> >
 163         {
 164             template <typename T, typename Tree>
 165             bool operator()( T& dest, Tree& container ) const
 166             {
 167                 typename Tree::exempt_ptr ep( container.extract_max());
 168                 if ( ep )
 169                     dest = *ep;
 170                 return !ep.empty();
 171             }
 172         };
 173
 174         template <typename GC>
 175         struct EllenBinTreePQueue_pop_min
 176         {
 177             template <typename T, typename Tree>
 178             bool operator()( T& dest, Tree& container ) const
 179             {
 180                 typename Tree::guarded_ptr gp( container.extract_min());
 181                 if ( gp )
 182                     dest = *gp;
 183                 return !gp.empty();
 184             }
 185         };
 186
 187         template <typename RCU>
 188         struct EllenBinTreePQueue_pop_min< cds::urcu::gc<RCU> >
 189         {
 190             template <typename T, typename Tree>
 191             bool operator()( T& dest, Tree& container ) const
 192             {
 193                 typename Tree::exempt_ptr ep( container.extract_min());
 194                 if ( ep )
 195                     dest = *ep;
 196                 return !ep.empty();
 197             }
 198         };
 199
 200         template <typename GC, typename Key, typename T, typename Traits, bool Max = true>
 201         class EllenBinTreePQueue : protected cds::container::EllenBinTreeSet< GC, Key, T, Traits >
 202         {
 203             typedef cds::container::EllenBinTreeSet< GC, Key, T, Traits > base_class;
 204             template <typename GC2> friend struct EllenBinTreePQueue_pop_max;
 205             template <typename GC2> friend struct EllenBinTreePQueue_pop_min;
 206
 207         public:
 208             typedef T value_type;
 209
 210             bool push( value_type const& val )
 211             {
 212                 return base_class::insert( val );
 213             }
 214
 215             bool pop( value_type& dest )
 216             {
 217                 return Max ? EllenBinTreePQueue_pop_max< typename base_class::gc >()(dest, *this)
 218                     : EllenBinTreePQueue_pop_min< typename base_class::gc >()(dest, *this);
 219             }
 220
 221             void clear()
 222             {
 223                 base_class::clear();
 224             }
 225
 226             bool empty() const
 227             {
 228                 return base_class::empty();
 229             }
 230
 231             size_t size() const
 232             {
 233                 return base_class::size();
 234             }
 235
 236             typename base_class::stat const& statistics() const
 237             {
 238                 return base_class::statistics();
 239             }
 240         };
 241
 242
 243         // SkipList property queue
 244         template <typename GC>
 245         struct SkipListPQueue_pop_max
 246         {
 247             template <typename T, typename Set>
 248             bool operator()( T& dest, Set& container ) const
 249             {
 250                 typename Set::guarded_ptr gp( container.extract_max());
 251                 if ( gp )
 252                     dest = *gp;
 253                 return !gp.empty();
 254             }
 255         };
 256
 257         template <typename RCU>
 258         struct SkipListPQueue_pop_max< cds::urcu::gc<RCU> >
 259         {
 260             template <typename T, typename Set>
 261             bool operator()( T& dest, Set& container ) const
 262             {
 263                 typename Set::exempt_ptr ep( container.extract_max());
 264                 if ( ep )
 265                     dest = *ep;
 266                 return !ep.empty();
 267             }
 268         };
 269
 270         template <typename GC>
 271         struct SkipListPQueue_pop_min
 272         {
 273             template <typename T, typename Set>
 274             bool operator()( T& dest, Set& container ) const
 275             {
 276                 typename Set::guarded_ptr gp( container.extract_min());
 277                 if ( gp )
 278                     dest = *gp;
 279                 return !gp.empty();
 280             }
 281         };
 282
 283         template <typename RCU>
 284         struct SkipListPQueue_pop_min< cds::urcu::gc<RCU> >
 285         {
 286             template <typename T, typename Set>
 287             bool operator()( T& dest, Set& container ) const
 288             {
 289                 typename Set::exempt_ptr ep( container.extract_min());
 290                 if ( ep )
 291                     dest = *ep;
 292                 return !ep.empty();
 293             }
 294         };
 295
 296         template <typename GC, typename T, typename Traits, bool Max = true>
 297         class SkipListPQueue : protected cds::container::SkipListSet< GC, T, Traits >
 298         {
 299             typedef cds::container::SkipListSet< GC, T, Traits > base_class;
 300             template <typename GC2> friend struct SkipListPQueue_pop_max;
 301             template <typename GC2> friend struct SkipListPQueue_pop_min;
 302
 303         public:
 304             typedef T value_type;
 305
 306             bool push( value_type const& val )
 307             {
 308                 return base_class::insert( val );
 309             }
 310
 311             bool pop( value_type& dest )
 312             {
 313                 return Max ? SkipListPQueue_pop_max< typename base_class::gc >()(dest, *this)
 314                     : SkipListPQueue_pop_min< typename base_class::gc >()(dest, *this);
 315             }
 316
 317             void clear()
 318             {
 319                 base_class::clear();
 320             }
 321
 322             bool empty() const
 323             {
 324                 return base_class::empty();
 325             }
 326
 327             size_t size() const
 328             {
 329                 return base_class::size();
 330             }
 331
 332             typename base_class::stat const& statistics() const
 333             {
 334                 return base_class::statistics();
 335             }
 336         };
 337
 338     } // namespace details
 339
 340     template <typename Value>
 341     struct Types
 342     {
 343         static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
 344
 345         typedef std::less<Value>    less;
 346
 347         struct cmp {
 348             int operator()( Value const& v1, Value const& v2 ) const
 349             {
 350                 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
 351             }
 352         };
 353
 354         typedef cds::urcu::gc< cds::urcu::general_instant<> >   rcu_gpi;
 355         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  rcu_gpb;
 356         typedef cds::urcu::gc< cds::urcu::general_threaded<> >  rcu_gpt;
 357 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 358         typedef cds::urcu::gc< cds::urcu::signal_buffered<> >  rcu_shb;
 359 #endif
 360
 361
 362         // MSPriorityQueue
 363         struct traits_MSPriorityQueue_static_less : public
 364             cc::mspriority_queue::make_traits <
 365                 co::buffer < co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
 366             > ::type
 367         {};
 368         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less;
 369
 370         struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits
 371         {
 372             typedef co::v::initialized_static_buffer< char, c_nBoundedCapacity > buffer;
 373             typedef cc::mspriority_queue::stat<> stat;
 374         };
 375         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat;
 376
 377         struct traits_MSPriorityQueue_static_cmp : public
 378             cc::mspriority_queue::make_traits <
 379                 co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
 380                 , co::compare < cmp >
 381             > ::type
 382         {};
 383         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_cmp > MSPriorityQueue_static_cmp;
 384
 385         struct traits_MSPriorityQueue_static_mutex : public
 386             cc::mspriority_queue::make_traits<
 387                 co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > >
 388                 , co::lock_type<std::mutex>
 389             >::type
 390         {};
 391         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
 392
 393         struct traits_MSPriorityQueue_dyn: public cc::mspriority_queue::traits
 394         {
 395             typedef co::v::initialized_dynamic_buffer< char > buffer;
 396         };
 397         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn > MSPriorityQueue_dyn_less;
 398
 399         struct traits_MSPriorityQueue_dyn_less_stat: public traits_MSPriorityQueue_dyn
 400         {
 401             typedef cc::mspriority_queue::stat<> stat;
 402         };
 403         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat;
 404
 405
 406         struct traits_MSPriorityQueue_dyn_cmp : public
 407             cc::mspriority_queue::make_traits <
 408                 co::buffer< co::v::initialized_dynamic_buffer< char > >
 409                 , co::compare < cmp >
 410             > ::type
 411         {};
 412         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
 413
 414         struct traits_MSPriorityQueue_dyn_mutex : public
 415             cc::mspriority_queue::make_traits <
 416                 co::buffer< co::v::initialized_dynamic_buffer< char > >
 417                 , co::lock_type < std::mutex >
 418             > ::type
 419         {};
 420         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
 421
 422
 423         // Priority queue based on EllenBinTreeSet
 424         struct traits_EllenBinTree_max :
 425             public cc::ellen_bintree::make_set_traits<
 426                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 427                 ,cc::opt::less< std::less<Value> >
 428                 ,co::stat< cc::ellen_bintree::stat<> >
 429             >::type
 430         {};
 431         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
 432         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
 433         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
 434         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
 435         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
 436 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 437         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
 438 #endif
 439
 440         struct traits_EllenBinTree_max_stat :
 441             public cc::ellen_bintree::make_set_traits<
 442                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 443                 ,cc::opt::less< std::less<Value> >
 444                 ,co::stat< cc::ellen_bintree::stat<> >
 445             >::type
 446         {};
 447         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
 448         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
 449         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
 450         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
 451         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
 452 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 453         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
 454 #endif
 455
 456         struct traits_EllenBinTree_min :
 457             public cc::ellen_bintree::make_set_traits<
 458                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 459                 ,cc::opt::less< std::greater<Value> >
 460             >::type
 461         {};
 462         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
 463         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
 464         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
 465         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
 466         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
 467 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 468         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
 469 #endif
 470
 471         struct traits_EllenBinTree_min_stat :
 472             public cc::ellen_bintree::make_set_traits<
 473                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 474                 ,cc::opt::less< std::greater<Value> >
 475                 ,co::stat< cc::ellen_bintree::stat<> >
 476             >::type
 477         {};
 478         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
 479         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
 480         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
 481         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
 482         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
 483 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 484         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
 485 #endif
 486
 487         // Priority queue based on SkipListSet
 488         struct traits_SkipList_max :
 489             public cc::skip_list::make_traits <
 490                 cc::opt::less < std::less<Value> >
 491             > ::type
 492         {};
 493         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList32_HP_max;
 494         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList32_DHP_max;
 495         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList32_RCU_gpi_max;
 496         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList32_RCU_gpb_max;
 497         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList32_RCU_gpt_max;
 498 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 499         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList32_RCU_shb_max;
 500 #endif
 501
 502         struct traits_SkipList24_max: public traits_SkipList_max
 503         {
 504             typedef cc::skip_list::turbo24 random_level_generator;
 505         };
 506         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max > SkipList24_HP_max;
 507         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max > SkipList24_DHP_max;
 508         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max > SkipList24_RCU_gpi_max;
 509         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max > SkipList24_RCU_gpb_max;
 510         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max > SkipList24_RCU_gpt_max;
 511 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 512         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max > SkipList24_RCU_shb_max;
 513 #endif
 514
 515         struct traits_SkipList16_max: public traits_SkipList_max
 516         {
 517             typedef cc::skip_list::turbo16 random_level_generator;
 518         };
 519         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max > SkipList16_HP_max;
 520         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max > SkipList16_DHP_max;
 521         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max > SkipList16_RCU_gpi_max;
 522         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max > SkipList16_RCU_gpb_max;
 523         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max > SkipList16_RCU_gpt_max;
 524 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 525         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max > SkipList16_RCU_shb_max;
 526 #endif
 527
 528         struct traits_SkipList_max_stat :
 529             public cc::skip_list::make_traits<
 530                 cc::opt::less< std::less<Value> >
 531                 ,co::stat< cc::skip_list::stat<> >
 532             >::type
 533         {};
 534         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList32_HP_max_stat;
 535         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList32_DHP_max_stat;
 536         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList32_RCU_gpi_max_stat;
 537         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList32_RCU_gpb_max_stat;
 538         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList32_RCU_gpt_max_stat;
 539 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 540         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList32_RCU_shb_max_stat;
 541 #endif
 542
 543         struct traits_SkipList24_max_stat: public traits_SkipList_max_stat
 544         {
 545             typedef cc::skip_list::turbo24 random_level_generator;
 546         };
 547         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max_stat > SkipList24_HP_max_stat;
 548         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max_stat > SkipList24_DHP_max_stat;
 549         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpi_max_stat;
 550         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpb_max_stat;
 551         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpt_max_stat;
 552 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 553         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max_stat > SkipList24_RCU_shb_max_stat;
 554 #endif
 555
 556         struct traits_SkipList16_max_stat: public traits_SkipList_max_stat
 557         {
 558             typedef cc::skip_list::turbo16 random_level_generator;
 559         };
 560         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max_stat > SkipList16_HP_max_stat;
 561         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max_stat > SkipList16_DHP_max_stat;
 562         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpi_max_stat;
 563         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpb_max_stat;
 564         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpt_max_stat;
 565 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 566         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max_stat > SkipList16_RCU_shb_max_stat;
 567 #endif
 568
 569         struct traits_SkipList_min :
 570             public cc::skip_list::make_traits<
 571                 cc::opt::less< std::greater<Value> >
 572             >::type
 573         {};
 574         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList32_HP_min;
 575         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList32_DHP_min;
 576         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList32_RCU_gpi_min;
 577         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList32_RCU_gpb_min;
 578         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList32_RCU_gpt_min;
 579 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 580         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList32_RCU_shb_min;
 581 #endif
 582
 583         struct traits_SkipList24_min: public traits_SkipList_min
 584         {
 585             typedef cc::skip_list::turbo24 random_level_generator;
 586         };
 587         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min > SkipList24_HP_min;
 588         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min > SkipList24_DHP_min;
 589         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min > SkipList24_RCU_gpi_min;
 590         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min > SkipList24_RCU_gpb_min;
 591         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min > SkipList24_RCU_gpt_min;
 592 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 593         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min > SkipList24_RCU_shb_min;
 594 #endif
 595
 596         struct traits_SkipList16_min: public traits_SkipList_min
 597         {
 598             typedef cc::skip_list::turbo16 random_level_generator;
 599         };
 600         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min > SkipList16_HP_min;
 601         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min > SkipList16_DHP_min;
 602         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min > SkipList16_RCU_gpi_min;
 603         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min > SkipList16_RCU_gpb_min;
 604         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min > SkipList16_RCU_gpt_min;
 605 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 606         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min > SkipList16_RCU_shb_min;
 607 #endif
 608
 609         struct traits_SkipList_min_stat :
 610             public cc::skip_list::make_traits<
 611                 cc::opt::less< std::greater<Value> >
 612                 ,co::stat< cc::skip_list::stat<> >
 613             >::type
 614         {};
 615         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList32_HP_min_stat;
 616         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList32_DHP_min_stat;
 617         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpi_min_stat;
 618         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpb_min_stat;
 619         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpt_min_stat;
 620 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 621         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_shb_min_stat;
 622 #endif
 623
 624         struct traits_SkipList24_min_stat: public traits_SkipList_min_stat
 625         {
 626             typedef cc::skip_list::turbo24 random_level_generator;
 627         };
 628         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min_stat > SkipList24_HP_min_stat;
 629         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min_stat > SkipList24_DHP_min_stat;
 630         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpi_min_stat;
 631         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpb_min_stat;
 632         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpt_min_stat;
 633 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 634         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min_stat > SkipList24_RCU_shb_min_stat;
 635 #endif
 636
 637         struct traits_SkipList16_min_stat: public traits_SkipList_min_stat
 638         {
 639             typedef cc::skip_list::turbo16 random_level_generator;
 640         };
 641         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min_stat > SkipList16_HP_min_stat;
 642         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min_stat > SkipList16_DHP_min_stat;
 643         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpi_min_stat;
 644         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpb_min_stat;
 645         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpt_min_stat;
 646 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 647         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min_stat > SkipList16_RCU_shb_min_stat;
 648 #endif
 649
 650
 651         // FCPriorityQueue
 652         struct traits_FCPQueue_stat : public
 653             cds::container::fcpqueue::make_traits <
 654             cds::opt::stat < cds::container::fcpqueue::stat<> >
 655             > ::type
 656         {};
 657
 658         typedef cds::container::FCPriorityQueue< Value >    FCPQueue_vector;
 659         typedef cds::container::FCPriorityQueue< Value
 660             ,std::priority_queue<Value>
 661             ,traits_FCPQueue_stat
 662         >    FCPQueue_vector_stat;
 663
 664         typedef cds::container::FCPriorityQueue< Value
 665             ,std::priority_queue<Value, std::deque<Value> >
 666         > FCPQueue_deque;
 667         typedef cds::container::FCPriorityQueue< Value
 668             ,std::priority_queue<Value, std::deque<Value> >
 669             ,traits_FCPQueue_stat
 670         > FCPQueue_deque_stat;
 671
 672         typedef cds::container::FCPriorityQueue< Value
 673             ,std::priority_queue<Value, boost::container::deque<Value> >
 674         > FCPQueue_boost_deque;
 675         typedef cds::container::FCPriorityQueue< Value
 676             ,std::priority_queue<Value, boost::container::deque<Value> >
 677             ,traits_FCPQueue_stat
 678         > FCPQueue_boost_deque_stat;
 679
 680         typedef cds::container::FCPriorityQueue< Value
 681             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 682         > FCPQueue_boost_stable_vector;
 683         typedef cds::container::FCPriorityQueue< Value
 684             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 685             ,traits_FCPQueue_stat
 686         > FCPQueue_boost_stable_vector_stat;
 687
 688         /// Standard priority_queue
 689         typedef details::StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
 690         typedef details::StdPQueue< Value, std::vector<Value>, std::mutex >  StdPQueue_vector_mutex;
 691         typedef details::StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
 692         typedef details::StdPQueue< Value, std::deque<Value>,  std::mutex >  StdPQueue_deque_mutex;
 693     };
 694
 695 }   // namespace pqueue
 696
 697
 698 // *********************************************
 699 // Priority queue statistics
 700 namespace cds_test {
 701
 702     static inline property_stream& operator <<( property_stream& o, cds::opt::none )
 703     {
 704         return o;
 705     }
 706
 707     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::empty_stat const& )
 708     {
 709         return o;
 710     }
 711
 712     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::stat<> const& s )
 713     {
 714         return o
 715             << CDSSTRESS_STAT_OUT( s, m_nPush )
 716             << CDSSTRESS_STAT_OUT( s, m_nPushMove )
 717             << CDSSTRESS_STAT_OUT( s, m_nPop )
 718             << CDSSTRESS_STAT_OUT( s, m_nFailedPop )
 719             << static_cast<cds::algo::flat_combining::stat<> const&>(s);
 720     }
 721
 722     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::empty_stat const& /*s*/ )
 723     {
 724         return o;
 725     }
 726
 727     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::stat<> const& s )
 728     {
 729         return o
 730             << CDSSTRESS_STAT_OUT( s, m_nPushCount )
 731             << CDSSTRESS_STAT_OUT( s, m_nPopCount )
 732             << CDSSTRESS_STAT_OUT( s, m_nPushFailCount )
 733             << CDSSTRESS_STAT_OUT( s, m_nPopFailCount )
 734             << CDSSTRESS_STAT_OUT( s, m_nPushHeapifySwapCount )
 735             << CDSSTRESS_STAT_OUT( s, m_nPopHeapifySwapCount )
 736             << CDSSTRESS_STAT_OUT( s, m_nItemMovedTop )
 737             << CDSSTRESS_STAT_OUT( s, m_nItemMovedUp )
 738             << CDSSTRESS_STAT_OUT( s, m_nPushEmptyPass );
 739     }
 740
 741 } // namespace cds_test
 742
 743 #endif // #ifndef CDSSTRESS_PQUEUE_TYPES_H