tests/unit/pqueue/pqueue_type.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSUNIT_PQUEUE_TYPES_H
   4 #define CDSUNIT_PQUEUE_TYPES_H
   5
   6 #include <cds/container/mspriority_queue.h>
   7 #include <cds/container/fcpriority_queue.h>
   8
   9 #include "pqueue/std_pqueue.h"
  10 #include "pqueue/ellen_bintree_pqueue.h"
  11 #include "pqueue/skiplist_pqueue.h"
  12
  13 #include <vector>
  14 #include <deque>
  15 #include <boost/container/stable_vector.hpp>
  16 #include <boost/container/deque.hpp>
  17 #include <cds/lock/spinlock.h>
  18
  19 #include "print_ellenbintree_stat.h"
  20 #include "print_skip_list_stat.h"
  21 #include "print_mspriorityqueue_stat.h"
  22
  23 namespace pqueue {
  24     namespace cc = cds::container;
  25     namespace co = cds::opt;
  26
  27     template <typename Value>
  28     struct Types
  29     {
  30         static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
  31
  32         typedef std::less<Value>    less;
  33
  34         struct cmp {
  35             int operator()( Value const& v1, Value const& v2 ) const
  36             {
  37                 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
  38             }
  39         };
  40
  41         typedef cds::urcu::gc< cds::urcu::general_instant<> >   rcu_gpi;
  42         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  rcu_gpb;
  43         typedef cds::urcu::gc< cds::urcu::general_threaded<> >  rcu_gpt;
  44 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  45         typedef cds::urcu::gc< cds::urcu::signal_buffered<> >  rcu_shb;
  46         typedef cds::urcu::gc< cds::urcu::signal_threaded<> >  rcu_sht;
  47 #endif
  48
  49
  50         // MSPriorityQueue
  51         struct traits_MSPriorityQueue_static_less : public
  52             cc::mspriority_queue::make_traits <
  53                 co::buffer < co::v::static_buffer< char, c_nBoundedCapacity > >
  54             > ::type
  55         {};
  56         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less;
  57
  58         struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits
  59         {
  60             typedef co::v::static_buffer< char, c_nBoundedCapacity > buffer;
  61             typedef cc::mspriority_queue::stat<> stat;
  62         };
  63         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat;
  64
  65         struct traits_MSPriorityQueue_static_cmp : public
  66             cc::mspriority_queue::make_traits <
  67                 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
  68                 , co::compare < cmp >
  69             > ::type
  70         {};
  71         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_cmp > MSPriorityQueue_static_cmp;
  72
  73         struct traits_MSPriorityQueue_static_mutex : public
  74             cc::mspriority_queue::make_traits<
  75                 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
  76                 , co::lock_type<std::mutex>
  77             >::type
  78         {};
  79         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
  80
  81         struct traits_MSPriorityQueue_dyn_less : public
  82             cc::mspriority_queue::make_traits<
  83                 co::buffer< co::v::dynamic_buffer< char > >
  84             >::type
  85         {};
  86         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less > MSPriorityQueue_dyn_less;
  87
  88         struct traits_MSPriorityQueue_dyn_less_stat : public
  89             cc::mspriority_queue::make_traits <
  90                 co::buffer< co::v::dynamic_buffer< char > >
  91                 , co::stat < cc::mspriority_queue::stat<> >
  92             > ::type
  93         {};
  94         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat;
  95
  96         struct traits_MSPriorityQueue_dyn_cmp : public
  97             cc::mspriority_queue::make_traits <
  98                 co::buffer< co::v::dynamic_buffer< char > >
  99                 , co::compare < cmp >
 100             > ::type
 101         {};
 102         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
 103
 104         struct traits_MSPriorityQueue_dyn_mutex : public
 105             cc::mspriority_queue::make_traits <
 106                 co::buffer< co::v::dynamic_buffer< char > >
 107                 , co::lock_type < std::mutex >
 108             > ::type
 109         {};
 110         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
 111
 112
 113         // Priority queue based on EllenBinTreeSet
 114         struct traits_EllenBinTree_max :
 115             public cc::ellen_bintree::make_set_traits<
 116                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 117                 ,cc::opt::less< std::less<Value> >
 118                 ,co::stat< cc::ellen_bintree::stat<> >
 119             >::type
 120         {};
 121         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
 122         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
 123         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
 124         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
 125         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
 126 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 127         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
 128         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_sht_max;
 129 #endif
 130
 131         struct traits_EllenBinTree_max_stat :
 132             public cc::ellen_bintree::make_set_traits<
 133                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 134                 ,cc::opt::less< std::less<Value> >
 135                 ,co::stat< cc::ellen_bintree::stat<> >
 136             >::type
 137         {};
 138         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
 139         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
 140         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
 141         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
 142         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
 143 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 144         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
 145         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_sht_max_stat;
 146 #endif
 147
 148         struct traits_EllenBinTree_min :
 149             public cc::ellen_bintree::make_set_traits<
 150                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 151                 ,cc::opt::less< std::greater<Value> >
 152             >::type
 153         {};
 154         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
 155         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
 156         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
 157         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
 158         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
 159 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 160         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
 161         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_sht_min;
 162 #endif
 163
 164         struct traits_EllenBinTree_min_stat :
 165             public cc::ellen_bintree::make_set_traits<
 166                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 167                 ,cc::opt::less< std::greater<Value> >
 168                 ,co::stat< cc::ellen_bintree::stat<> >
 169             >::type
 170         {};
 171         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
 172         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
 173         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
 174         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
 175         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
 176 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 177         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
 178         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_sht_min_stat;
 179 #endif
 180
 181         // Priority queue based on SkipListSet
 182         struct traits_SkipList_max :
 183             public cc::skip_list::make_traits <
 184             cc::opt::less < std::less<Value> >
 185             > ::type
 186         {};
 187         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList_HP_max;
 188         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList_DHP_max;
 189         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList_RCU_gpi_max;
 190         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList_RCU_gpb_max;
 191         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList_RCU_gpt_max;
 192 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 193         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList_RCU_shb_max;
 194         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_max > SkipList_RCU_sht_max;
 195 #endif
 196
 197         struct traits_SkipList_max_stat :
 198             public cc::skip_list::make_traits<
 199                 cc::opt::less< std::less<Value> >
 200                 ,co::stat< cc::skip_list::stat<> >
 201             >::type
 202         {};
 203         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList_HP_max_stat;
 204         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList_DHP_max_stat;
 205         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList_RCU_gpi_max_stat;
 206         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList_RCU_gpb_max_stat;
 207         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList_RCU_gpt_max_stat;
 208 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 209         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList_RCU_shb_max_stat;
 210         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_max_stat > SkipList_RCU_sht_max_stat;
 211 #endif
 212
 213         struct traits_SkipList_min :
 214             public cc::skip_list::make_traits<
 215                 cc::opt::less< std::greater<Value> >
 216             >::type
 217         {};
 218         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList_HP_min;
 219         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList_DHP_min;
 220         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList_RCU_gpi_min;
 221         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList_RCU_gpb_min;
 222         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList_RCU_gpt_min;
 223 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 224         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList_RCU_shb_min;
 225         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_min, false > SkipList_RCU_sht_min;
 226 #endif
 227
 228         struct traits_SkipList_min_stat :
 229             public cc::skip_list::make_traits<
 230                 cc::opt::less< std::greater<Value> >
 231                 ,co::stat< cc::skip_list::stat<> >
 232             >::type
 233         {};
 234         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList_HP_min_stat;
 235         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList_DHP_min_stat;
 236         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpi_min_stat;
 237         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpb_min_stat;
 238         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpt_min_stat;
 239 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 240         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList_RCU_shb_min_stat;
 241         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_min_stat, false > SkipList_RCU_sht_min_stat;
 242 #endif
 243
 244
 245         // FCPriorityQueue
 246         struct traits_FCPQueue_stat : public
 247             cds::container::fcpqueue::make_traits <
 248             cds::opt::stat < cds::container::fcpqueue::stat<> >
 249             > ::type
 250         {};
 251
 252         typedef cds::container::FCPriorityQueue< Value >    FCPQueue_vector;
 253         typedef cds::container::FCPriorityQueue< Value
 254             ,std::priority_queue<Value>
 255             ,traits_FCPQueue_stat
 256         >    FCPQueue_vector_stat;
 257
 258         typedef cds::container::FCPriorityQueue< Value
 259             ,std::priority_queue<Value, std::deque<Value> >
 260         > FCPQueue_deque;
 261         typedef cds::container::FCPriorityQueue< Value
 262             ,std::priority_queue<Value, std::deque<Value> >
 263             ,traits_FCPQueue_stat
 264         > FCPQueue_deque_stat;
 265
 266         typedef cds::container::FCPriorityQueue< Value
 267             ,std::priority_queue<Value, boost::container::deque<Value> >
 268         > FCPQueue_boost_deque;
 269         typedef cds::container::FCPriorityQueue< Value
 270             ,std::priority_queue<Value, boost::container::deque<Value> >
 271             ,traits_FCPQueue_stat
 272         > FCPQueue_boost_deque_stat;
 273
 274         typedef cds::container::FCPriorityQueue< Value
 275             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 276         > FCPQueue_boost_stable_vector;
 277         typedef cds::container::FCPriorityQueue< Value
 278             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 279             ,traits_FCPQueue_stat
 280         > FCPQueue_boost_stable_vector_stat;
 281
 282         /// Standard priority_queue
 283         typedef StdPQueue< Value, std::vector<Value>, cds::lock::Spin > StdPQueue_vector_spin;
 284         typedef StdPQueue< Value, std::vector<Value>, std::mutex >  StdPQueue_vector_mutex;
 285         typedef StdPQueue< Value, std::deque<Value>,  cds::lock::Spin > StdPQueue_deque_spin;
 286         typedef StdPQueue< Value, std::deque<Value>,  std::mutex >  StdPQueue_deque_mutex;
 287     };
 288
 289
 290     template <typename Stat>
 291     static inline void check_statistics( Stat const& /*s*/ )
 292     {}
 293
 294     static inline void check_statistics( cds::container::ellen_bintree::stat<> const& s )
 295     {
 296         CPPUNIT_CHECK_CURRENT( s.m_nInternalNodeCreated.get() == s.m_nInternalNodeDeleted.get() );
 297         CPPUNIT_CHECK_CURRENT( s.m_nUpdateDescCreated.get() == s.m_nUpdateDescDeleted.get() );
 298     }
 299 }   // namespace pqueue
 300
 301 namespace std {
 302
 303     static inline std::ostream& operator <<( std::ostream& o, cds::container::fcpqueue::empty_stat const& )
 304     {
 305         return o;
 306     }
 307
 308     static inline std::ostream& operator <<( std::ostream& o, cds::container::fcpqueue::stat<> const& s )
 309     {
 310         return o << "\tStatistics:\n"
 311             << "\t              Push: " << s.m_nPush.get()         << "\n"
 312             << "\t         Push move: " << s.m_nPushMove.get()     << "\n"
 313             << "\t               Pop: " << s.m_nPop.get()          << "\n"
 314             << "\t        Failed pop: " << s.m_nFailedPop.get()    << "\n"
 315             << "\tFlat combining statistics:\n"
 316             << "\t        Combining factor: " << s.combining_factor()         << "\n"
 317             << "\t         Operation count: " << s.m_nOperationCount.get()    << "\n"
 318             << "\t      Combine call count: " << s.m_nCombiningCount.get()    << "\n"
 319             << "\t        Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
 320             << "\t   Deactivate pub-record: " << s.m_nDeactivatePubRecord.get()    << "\n"
 321             << "\t     Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
 322             << "\t       Create pub-record: " << s.m_nPubRecordCreated.get()  << "\n"
 323             << "\t       Delete pub-record: " << s.m_nPubRecordDeteted.get()  << "\n"
 324             << "\t      Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
 325             << "\t      Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
 326     }
 327
 328 } // namespace std
 329
 330 #endif // #ifndef CDSUNIT_PQUEUE_TYPES_H