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                 scoped_lock l( m_Lock );
 134                 return m_PQueue.empty();
 135             }
 136
 137             size_t size() const
 138             {
 139                 scoped_lock l( m_Lock );
 140                 return m_PQueue.size();
 141             }
 142
 143             cds::opt::none statistics() const
 144             {
 145                 return cds::opt::none();
 146             }
 147         };
 148
 149         // EllenBinTree priority queue
 150         template <typename GC>
 151         struct EllenBinTreePQueue_pop_max
 152         {
 153             template <typename T, typename Tree>
 154             bool operator()( T& dest, Tree& container ) const
 155             {
 156                 typename Tree::guarded_ptr gp( container.extract_max());
 157                 if ( gp )
 158                     dest = *gp;
 159                 return !gp.empty();
 160             }
 161         };
 162
 163         template <typename RCU>
 164         struct EllenBinTreePQueue_pop_max< cds::urcu::gc<RCU> >
 165         {
 166             template <typename T, typename Tree>
 167             bool operator()( T& dest, Tree& container ) const
 168             {
 169                 typename Tree::exempt_ptr ep( container.extract_max());
 170                 if ( ep )
 171                     dest = *ep;
 172                 return !ep.empty();
 173             }
 174         };
 175
 176         template <typename GC>
 177         struct EllenBinTreePQueue_pop_min
 178         {
 179             template <typename T, typename Tree>
 180             bool operator()( T& dest, Tree& container ) const
 181             {
 182                 typename Tree::guarded_ptr gp( container.extract_min());
 183                 if ( gp )
 184                     dest = *gp;
 185                 return !gp.empty();
 186             }
 187         };
 188
 189         template <typename RCU>
 190         struct EllenBinTreePQueue_pop_min< cds::urcu::gc<RCU> >
 191         {
 192             template <typename T, typename Tree>
 193             bool operator()( T& dest, Tree& container ) const
 194             {
 195                 typename Tree::exempt_ptr ep( container.extract_min());
 196                 if ( ep )
 197                     dest = *ep;
 198                 return !ep.empty();
 199             }
 200         };
 201
 202         template <typename GC, typename Key, typename T, typename Traits, bool Max = true>
 203         class EllenBinTreePQueue : protected cds::container::EllenBinTreeSet< GC, Key, T, Traits >
 204         {
 205             typedef cds::container::EllenBinTreeSet< GC, Key, T, Traits > base_class;
 206             template <typename GC2> friend struct EllenBinTreePQueue_pop_max;
 207             template <typename GC2> friend struct EllenBinTreePQueue_pop_min;
 208
 209         public:
 210             typedef T value_type;
 211
 212             bool push( value_type const& val )
 213             {
 214                 return base_class::insert( val );
 215             }
 216
 217             bool pop( value_type& dest )
 218             {
 219                 return Max ? EllenBinTreePQueue_pop_max< typename base_class::gc >()(dest, *this)
 220                     : EllenBinTreePQueue_pop_min< typename base_class::gc >()(dest, *this);
 221             }
 222
 223             void clear()
 224             {
 225                 base_class::clear();
 226             }
 227
 228             bool empty() const
 229             {
 230                 return base_class::empty();
 231             }
 232
 233             size_t size() const
 234             {
 235                 return base_class::size();
 236             }
 237
 238             typename base_class::stat const& statistics() const
 239             {
 240                 return base_class::statistics();
 241             }
 242         };
 243
 244
 245         // SkipList property queue
 246         template <typename GC>
 247         struct SkipListPQueue_pop_max
 248         {
 249             template <typename T, typename Set>
 250             bool operator()( T& dest, Set& container ) const
 251             {
 252                 typename Set::guarded_ptr gp( container.extract_max());
 253                 if ( gp )
 254                     dest = *gp;
 255                 return !gp.empty();
 256             }
 257         };
 258
 259         template <typename RCU>
 260         struct SkipListPQueue_pop_max< cds::urcu::gc<RCU> >
 261         {
 262             template <typename T, typename Set>
 263             bool operator()( T& dest, Set& container ) const
 264             {
 265                 typename Set::exempt_ptr ep( container.extract_max());
 266                 if ( ep )
 267                     dest = *ep;
 268                 return !ep.empty();
 269             }
 270         };
 271
 272         template <typename GC>
 273         struct SkipListPQueue_pop_min
 274         {
 275             template <typename T, typename Set>
 276             bool operator()( T& dest, Set& container ) const
 277             {
 278                 typename Set::guarded_ptr gp( container.extract_min());
 279                 if ( gp )
 280                     dest = *gp;
 281                 return !gp.empty();
 282             }
 283         };
 284
 285         template <typename RCU>
 286         struct SkipListPQueue_pop_min< cds::urcu::gc<RCU> >
 287         {
 288             template <typename T, typename Set>
 289             bool operator()( T& dest, Set& container ) const
 290             {
 291                 typename Set::exempt_ptr ep( container.extract_min());
 292                 if ( ep )
 293                     dest = *ep;
 294                 return !ep.empty();
 295             }
 296         };
 297
 298         template <typename GC, typename T, typename Traits, bool Max = true>
 299         class SkipListPQueue : protected cds::container::SkipListSet< GC, T, Traits >
 300         {
 301             typedef cds::container::SkipListSet< GC, T, Traits > base_class;
 302             template <typename GC2> friend struct SkipListPQueue_pop_max;
 303             template <typename GC2> friend struct SkipListPQueue_pop_min;
 304
 305         public:
 306             typedef T value_type;
 307
 308             bool push( value_type const& val )
 309             {
 310                 return base_class::insert( val );
 311             }
 312
 313             bool pop( value_type& dest )
 314             {
 315                 return Max ? SkipListPQueue_pop_max< typename base_class::gc >()(dest, *this)
 316                     : SkipListPQueue_pop_min< typename base_class::gc >()(dest, *this);
 317             }
 318
 319             void clear()
 320             {
 321                 base_class::clear();
 322             }
 323
 324             bool empty() const
 325             {
 326                 return base_class::empty();
 327             }
 328
 329             size_t size() const
 330             {
 331                 return base_class::size();
 332             }
 333
 334             typename base_class::stat const& statistics() const
 335             {
 336                 return base_class::statistics();
 337             }
 338         };
 339
 340     } // namespace details
 341
 342     template <typename Value>
 343     struct Types
 344     {
 345         static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
 346
 347         typedef std::less<Value>    less;
 348
 349         struct cmp {
 350             int operator()( Value const& v1, Value const& v2 ) const
 351             {
 352                 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
 353             }
 354         };
 355
 356         typedef cds::urcu::gc< cds::urcu::general_instant<> >   rcu_gpi;
 357         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  rcu_gpb;
 358         typedef cds::urcu::gc< cds::urcu::general_threaded<> >  rcu_gpt;
 359 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 360         typedef cds::urcu::gc< cds::urcu::signal_buffered<> >  rcu_shb;
 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 #endif
 441
 442         struct traits_EllenBinTree_max_stat :
 443             public cc::ellen_bintree::make_set_traits<
 444                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 445                 ,cc::opt::less< std::less<Value> >
 446                 ,co::stat< cc::ellen_bintree::stat<> >
 447             >::type
 448         {};
 449         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
 450         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
 451         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
 452         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
 453         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
 454 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 455         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
 456 #endif
 457
 458         struct traits_EllenBinTree_min :
 459             public cc::ellen_bintree::make_set_traits<
 460                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 461                 ,cc::opt::less< std::greater<Value> >
 462             >::type
 463         {};
 464         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
 465         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
 466         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
 467         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
 468         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
 469 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 470         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
 471 #endif
 472
 473         struct traits_EllenBinTree_min_stat :
 474             public cc::ellen_bintree::make_set_traits<
 475                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 476                 ,cc::opt::less< std::greater<Value> >
 477                 ,co::stat< cc::ellen_bintree::stat<> >
 478             >::type
 479         {};
 480         typedef details::EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
 481         typedef details::EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
 482         typedef details::EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
 483         typedef details::EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
 484         typedef details::EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
 485 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 486         typedef details::EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
 487 #endif
 488
 489         // Priority queue based on SkipListSet
 490         struct traits_SkipList_max :
 491             public cc::skip_list::make_traits <
 492                 cc::opt::less < std::less<Value> >
 493             > ::type
 494         {};
 495         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList32_HP_max;
 496         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList32_DHP_max;
 497         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList32_RCU_gpi_max;
 498         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList32_RCU_gpb_max;
 499         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList32_RCU_gpt_max;
 500 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 501         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList32_RCU_shb_max;
 502 #endif
 503
 504         struct traits_SkipList24_max: public traits_SkipList_max
 505         {
 506             typedef cc::skip_list::turbo24 random_level_generator;
 507         };
 508         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max > SkipList24_HP_max;
 509         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max > SkipList24_DHP_max;
 510         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max > SkipList24_RCU_gpi_max;
 511         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max > SkipList24_RCU_gpb_max;
 512         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max > SkipList24_RCU_gpt_max;
 513 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 514         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max > SkipList24_RCU_shb_max;
 515 #endif
 516
 517         struct traits_SkipList16_max: public traits_SkipList_max
 518         {
 519             typedef cc::skip_list::turbo16 random_level_generator;
 520         };
 521         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max > SkipList16_HP_max;
 522         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max > SkipList16_DHP_max;
 523         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max > SkipList16_RCU_gpi_max;
 524         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max > SkipList16_RCU_gpb_max;
 525         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max > SkipList16_RCU_gpt_max;
 526 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 527         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max > SkipList16_RCU_shb_max;
 528 #endif
 529
 530         struct traits_SkipList_max_stat :
 531             public cc::skip_list::make_traits<
 532                 cc::opt::less< std::less<Value> >
 533                 ,co::stat< cc::skip_list::stat<> >
 534             >::type
 535         {};
 536         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList32_HP_max_stat;
 537         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList32_DHP_max_stat;
 538         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList32_RCU_gpi_max_stat;
 539         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList32_RCU_gpb_max_stat;
 540         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList32_RCU_gpt_max_stat;
 541 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 542         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList32_RCU_shb_max_stat;
 543 #endif
 544
 545         struct traits_SkipList24_max_stat: public traits_SkipList_max_stat
 546         {
 547             typedef cc::skip_list::turbo24 random_level_generator;
 548         };
 549         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_max_stat > SkipList24_HP_max_stat;
 550         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_max_stat > SkipList24_DHP_max_stat;
 551         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpi_max_stat;
 552         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpb_max_stat;
 553         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_max_stat > SkipList24_RCU_gpt_max_stat;
 554 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 555         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_max_stat > SkipList24_RCU_shb_max_stat;
 556 #endif
 557
 558         struct traits_SkipList16_max_stat: public traits_SkipList_max_stat
 559         {
 560             typedef cc::skip_list::turbo16 random_level_generator;
 561         };
 562         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_max_stat > SkipList16_HP_max_stat;
 563         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_max_stat > SkipList16_DHP_max_stat;
 564         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpi_max_stat;
 565         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpb_max_stat;
 566         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_max_stat > SkipList16_RCU_gpt_max_stat;
 567 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 568         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_max_stat > SkipList16_RCU_shb_max_stat;
 569 #endif
 570
 571         struct traits_SkipList_min :
 572             public cc::skip_list::make_traits<
 573                 cc::opt::less< std::greater<Value> >
 574             >::type
 575         {};
 576         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList32_HP_min;
 577         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList32_DHP_min;
 578         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList32_RCU_gpi_min;
 579         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList32_RCU_gpb_min;
 580         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList32_RCU_gpt_min;
 581 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 582         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList32_RCU_shb_min;
 583 #endif
 584
 585         struct traits_SkipList24_min: public traits_SkipList_min
 586         {
 587             typedef cc::skip_list::turbo24 random_level_generator;
 588         };
 589         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min > SkipList24_HP_min;
 590         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min > SkipList24_DHP_min;
 591         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min > SkipList24_RCU_gpi_min;
 592         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min > SkipList24_RCU_gpb_min;
 593         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min > SkipList24_RCU_gpt_min;
 594 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 595         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min > SkipList24_RCU_shb_min;
 596 #endif
 597
 598         struct traits_SkipList16_min: public traits_SkipList_min
 599         {
 600             typedef cc::skip_list::turbo16 random_level_generator;
 601         };
 602         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min > SkipList16_HP_min;
 603         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min > SkipList16_DHP_min;
 604         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min > SkipList16_RCU_gpi_min;
 605         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min > SkipList16_RCU_gpb_min;
 606         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min > SkipList16_RCU_gpt_min;
 607 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 608         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min > SkipList16_RCU_shb_min;
 609 #endif
 610
 611         struct traits_SkipList_min_stat :
 612             public cc::skip_list::make_traits<
 613                 cc::opt::less< std::greater<Value> >
 614                 ,co::stat< cc::skip_list::stat<> >
 615             >::type
 616         {};
 617         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList32_HP_min_stat;
 618         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList32_DHP_min_stat;
 619         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpi_min_stat;
 620         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpb_min_stat;
 621         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList32_RCU_gpt_min_stat;
 622 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 623         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList32_RCU_shb_min_stat;
 624 #endif
 625
 626         struct traits_SkipList24_min_stat: public traits_SkipList_min_stat
 627         {
 628             typedef cc::skip_list::turbo24 random_level_generator;
 629         };
 630         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList24_min_stat > SkipList24_HP_min_stat;
 631         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList24_min_stat > SkipList24_DHP_min_stat;
 632         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpi_min_stat;
 633         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpb_min_stat;
 634         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList24_min_stat > SkipList24_RCU_gpt_min_stat;
 635 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 636         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList24_min_stat > SkipList24_RCU_shb_min_stat;
 637 #endif
 638
 639         struct traits_SkipList16_min_stat: public traits_SkipList_min_stat
 640         {
 641             typedef cc::skip_list::turbo16 random_level_generator;
 642         };
 643         typedef details::SkipListPQueue< cds::gc::HP, Value, traits_SkipList16_min_stat > SkipList16_HP_min_stat;
 644         typedef details::SkipListPQueue< cds::gc::DHP, Value, traits_SkipList16_min_stat > SkipList16_DHP_min_stat;
 645         typedef details::SkipListPQueue< rcu_gpi, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpi_min_stat;
 646         typedef details::SkipListPQueue< rcu_gpb, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpb_min_stat;
 647         typedef details::SkipListPQueue< rcu_gpt, Value, traits_SkipList16_min_stat > SkipList16_RCU_gpt_min_stat;
 648 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 649         typedef details::SkipListPQueue< rcu_shb, Value, traits_SkipList16_min_stat > SkipList16_RCU_shb_min_stat;
 650 #endif
 651
 652
 653         // FCPriorityQueue
 654         struct traits_FCPQueue_stat : public
 655             cds::container::fcpqueue::make_traits <
 656             cds::opt::stat < cds::container::fcpqueue::stat<> >
 657             > ::type
 658         {};
 659
 660         typedef cds::container::FCPriorityQueue< Value >    FCPQueue_vector;
 661         typedef cds::container::FCPriorityQueue< Value
 662             ,std::priority_queue<Value>
 663             ,traits_FCPQueue_stat
 664         >    FCPQueue_vector_stat;
 665
 666         typedef cds::container::FCPriorityQueue< Value
 667             ,std::priority_queue<Value, std::deque<Value> >
 668         > FCPQueue_deque;
 669         typedef cds::container::FCPriorityQueue< Value
 670             ,std::priority_queue<Value, std::deque<Value> >
 671             ,traits_FCPQueue_stat
 672         > FCPQueue_deque_stat;
 673
 674         typedef cds::container::FCPriorityQueue< Value
 675             ,std::priority_queue<Value, boost::container::deque<Value> >
 676         > FCPQueue_boost_deque;
 677         typedef cds::container::FCPriorityQueue< Value
 678             ,std::priority_queue<Value, boost::container::deque<Value> >
 679             ,traits_FCPQueue_stat
 680         > FCPQueue_boost_deque_stat;
 681
 682         typedef cds::container::FCPriorityQueue< Value
 683             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 684         > FCPQueue_boost_stable_vector;
 685         typedef cds::container::FCPriorityQueue< Value
 686             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 687             ,traits_FCPQueue_stat
 688         > FCPQueue_boost_stable_vector_stat;
 689
 690         /// Standard priority_queue
 691         typedef details::StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
 692         typedef details::StdPQueue< Value, std::vector<Value>, std::mutex >  StdPQueue_vector_mutex;
 693         typedef details::StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
 694         typedef details::StdPQueue< Value, std::deque<Value>,  std::mutex >  StdPQueue_deque_mutex;
 695     };
 696
 697 }   // namespace pqueue
 698
 699
 700 // *********************************************
 701 // Priority queue statistics
 702 namespace cds_test {
 703
 704     static inline property_stream& operator <<( property_stream& o, cds::opt::none )
 705     {
 706         return o;
 707     }
 708
 709     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::empty_stat const& )
 710     {
 711         return o;
 712     }
 713
 714     static inline property_stream& operator <<( property_stream& o, cds::container::fcpqueue::stat<> const& s )
 715     {
 716         return o
 717             << CDSSTRESS_STAT_OUT( s, m_nPush )
 718             << CDSSTRESS_STAT_OUT( s, m_nPushMove )
 719             << CDSSTRESS_STAT_OUT( s, m_nPop )
 720             << CDSSTRESS_STAT_OUT( s, m_nFailedPop )
 721             << static_cast<cds::algo::flat_combining::stat<> const&>(s);
 722     }
 723
 724     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::empty_stat const& /*s*/ )
 725     {
 726         return o;
 727     }
 728
 729     static inline property_stream& operator <<( property_stream& o, cds::container::mspriority_queue::stat<> const& s )
 730     {
 731         return o
 732             << CDSSTRESS_STAT_OUT( s, m_nPushCount )
 733             << CDSSTRESS_STAT_OUT( s, m_nPopCount )
 734             << CDSSTRESS_STAT_OUT( s, m_nPushFailCount )
 735             << CDSSTRESS_STAT_OUT( s, m_nPopFailCount )
 736             << CDSSTRESS_STAT_OUT( s, m_nPushHeapifySwapCount )
 737             << CDSSTRESS_STAT_OUT( s, m_nPopHeapifySwapCount )
 738             << CDSSTRESS_STAT_OUT( s, m_nItemMovedTop )
 739             << CDSSTRESS_STAT_OUT( s, m_nItemMovedUp )
 740             << CDSSTRESS_STAT_OUT( s, m_nPushEmptyPass );
 741     }
 742
 743 } // namespace cds_test
 744
 745 #endif // #ifndef CDSSTRESS_PQUEUE_TYPES_H