tests/unit/pqueue/pqueue_type.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSUNIT_PQUEUE_TYPES_H
  32 #define CDSUNIT_PQUEUE_TYPES_H
  33
  34 #include <cds/container/mspriority_queue.h>
  35 #include <cds/container/fcpriority_queue.h>
  36
  37 #include "pqueue/std_pqueue.h"
  38 #include "pqueue/ellen_bintree_pqueue.h"
  39 #include "pqueue/skiplist_pqueue.h"
  40
  41 #include <vector>
  42 #include <deque>
  43 #include <boost/container/stable_vector.hpp>
  44 #include <boost/container/deque.hpp>
  45 #include <cds/sync/spinlock.h>
  46
  47 #include "print_ellenbintree_stat.h"
  48 #include "print_skip_list_stat.h"
  49 #include "print_mspriorityqueue_stat.h"
  50
  51 namespace pqueue {
  52     namespace cc = cds::container;
  53     namespace co = cds::opt;
  54
  55     template <typename Value>
  56     struct Types
  57     {
  58         static size_t const c_nBoundedCapacity = 1024 * 1024 * 16;
  59
  60         typedef std::less<Value>    less;
  61
  62         struct cmp {
  63             int operator()( Value const& v1, Value const& v2 ) const
  64             {
  65                 return less()( v1, v2 ) ? -1 : less()( v2, v1 ) ? 1 : 0;
  66             }
  67         };
  68
  69         typedef cds::urcu::gc< cds::urcu::general_instant<> >   rcu_gpi;
  70         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  rcu_gpb;
  71         typedef cds::urcu::gc< cds::urcu::general_threaded<> >  rcu_gpt;
  72 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  73         typedef cds::urcu::gc< cds::urcu::signal_buffered<> >  rcu_shb;
  74         typedef cds::urcu::gc< cds::urcu::signal_threaded<> >  rcu_sht;
  75 #endif
  76
  77
  78         // MSPriorityQueue
  79         struct traits_MSPriorityQueue_static_less : public
  80             cc::mspriority_queue::make_traits <
  81                 co::buffer < co::v::static_buffer< char, c_nBoundedCapacity > >
  82             > ::type
  83         {};
  84         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less;
  85
  86         struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits
  87         {
  88             typedef co::v::static_buffer< char, c_nBoundedCapacity > buffer;
  89             typedef cc::mspriority_queue::stat<> stat;
  90         };
  91         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat;
  92
  93         struct traits_MSPriorityQueue_static_cmp : public
  94             cc::mspriority_queue::make_traits <
  95                 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
  96                 , co::compare < cmp >
  97             > ::type
  98         {};
  99         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_cmp > MSPriorityQueue_static_cmp;
 100
 101         struct traits_MSPriorityQueue_static_mutex : public
 102             cc::mspriority_queue::make_traits<
 103                 co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > >
 104                 , co::lock_type<std::mutex>
 105             >::type
 106         {};
 107         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
 108
 109         struct traits_MSPriorityQueue_dyn_less : public
 110             cc::mspriority_queue::make_traits<
 111                 co::buffer< co::v::dynamic_buffer< char > >
 112             >::type
 113         {};
 114         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less > MSPriorityQueue_dyn_less;
 115
 116         struct traits_MSPriorityQueue_dyn_less_stat : public
 117             cc::mspriority_queue::make_traits <
 118                 co::buffer< co::v::dynamic_buffer< char > >
 119                 , co::stat < cc::mspriority_queue::stat<> >
 120             > ::type
 121         {};
 122         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat;
 123
 124         struct traits_MSPriorityQueue_dyn_cmp : public
 125             cc::mspriority_queue::make_traits <
 126                 co::buffer< co::v::dynamic_buffer< char > >
 127                 , co::compare < cmp >
 128             > ::type
 129         {};
 130         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_cmp > MSPriorityQueue_dyn_cmp;
 131
 132         struct traits_MSPriorityQueue_dyn_mutex : public
 133             cc::mspriority_queue::make_traits <
 134                 co::buffer< co::v::dynamic_buffer< char > >
 135                 , co::lock_type < std::mutex >
 136             > ::type
 137         {};
 138         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_mutex > MSPriorityQueue_dyn_mutex;
 139
 140
 141         // Priority queue based on EllenBinTreeSet
 142         struct traits_EllenBinTree_max :
 143             public cc::ellen_bintree::make_set_traits<
 144                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 145                 ,cc::opt::less< std::less<Value> >
 146                 ,co::stat< cc::ellen_bintree::stat<> >
 147             >::type
 148         {};
 149         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_HP_max;
 150         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_DHP_max;
 151         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpi_max;
 152         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpb_max;
 153         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_gpt_max;
 154 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 155         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_shb_max;
 156         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max > EllenBinTree_RCU_sht_max;
 157 #endif
 158
 159         struct traits_EllenBinTree_max_stat :
 160             public cc::ellen_bintree::make_set_traits<
 161                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 162                 ,cc::opt::less< std::less<Value> >
 163                 ,co::stat< cc::ellen_bintree::stat<> >
 164             >::type
 165         {};
 166         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_HP_max_stat;
 167         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_DHP_max_stat;
 168         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpi_max_stat;
 169         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpb_max_stat;
 170         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_gpt_max_stat;
 171 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 172         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_shb_max_stat;
 173         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_max_stat > EllenBinTree_RCU_sht_max_stat;
 174 #endif
 175
 176         struct traits_EllenBinTree_min :
 177             public cc::ellen_bintree::make_set_traits<
 178                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 179                 ,cc::opt::less< std::greater<Value> >
 180             >::type
 181         {};
 182         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_HP_min;
 183         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_DHP_min;
 184         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpi_min;
 185         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpb_min;
 186         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_gpt_min;
 187 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 188         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_shb_min;
 189         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min, false > EllenBinTree_RCU_sht_min;
 190 #endif
 191
 192         struct traits_EllenBinTree_min_stat :
 193             public cc::ellen_bintree::make_set_traits<
 194                 cc::ellen_bintree::key_extractor< typename Value::key_extractor >
 195                 ,cc::opt::less< std::greater<Value> >
 196                 ,co::stat< cc::ellen_bintree::stat<> >
 197             >::type
 198         {};
 199         typedef EllenBinTreePQueue< cds::gc::HP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_HP_min_stat;
 200         typedef EllenBinTreePQueue< cds::gc::DHP, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_DHP_min_stat;
 201         typedef EllenBinTreePQueue< rcu_gpi, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpi_min_stat;
 202         typedef EllenBinTreePQueue< rcu_gpb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpb_min_stat;
 203         typedef EllenBinTreePQueue< rcu_gpt, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_gpt_min_stat;
 204 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 205         typedef EllenBinTreePQueue< rcu_shb, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_shb_min_stat;
 206         typedef EllenBinTreePQueue< rcu_sht, typename Value::key_type, Value, traits_EllenBinTree_min_stat, false > EllenBinTree_RCU_sht_min_stat;
 207 #endif
 208
 209         // Priority queue based on SkipListSet
 210         struct traits_SkipList_max :
 211             public cc::skip_list::make_traits <
 212             cc::opt::less < std::less<Value> >
 213             > ::type
 214         {};
 215         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max > SkipList_HP_max;
 216         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max > SkipList_DHP_max;
 217         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_max > SkipList_RCU_gpi_max;
 218         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_max > SkipList_RCU_gpb_max;
 219         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_max > SkipList_RCU_gpt_max;
 220 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 221         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_max > SkipList_RCU_shb_max;
 222         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_max > SkipList_RCU_sht_max;
 223 #endif
 224
 225         struct traits_SkipList_max_stat :
 226             public cc::skip_list::make_traits<
 227                 cc::opt::less< std::less<Value> >
 228                 ,co::stat< cc::skip_list::stat<> >
 229             >::type
 230         {};
 231         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_max_stat > SkipList_HP_max_stat;
 232         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_max_stat > SkipList_DHP_max_stat;
 233         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_max_stat > SkipList_RCU_gpi_max_stat;
 234         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_max_stat > SkipList_RCU_gpb_max_stat;
 235         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_max_stat > SkipList_RCU_gpt_max_stat;
 236 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 237         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_max_stat > SkipList_RCU_shb_max_stat;
 238         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_max_stat > SkipList_RCU_sht_max_stat;
 239 #endif
 240
 241         struct traits_SkipList_min :
 242             public cc::skip_list::make_traits<
 243                 cc::opt::less< std::greater<Value> >
 244             >::type
 245         {};
 246         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min, false > SkipList_HP_min;
 247         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min, false > SkipList_DHP_min;
 248         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_min, false > SkipList_RCU_gpi_min;
 249         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_min, false > SkipList_RCU_gpb_min;
 250         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_min, false > SkipList_RCU_gpt_min;
 251 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 252         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_min, false > SkipList_RCU_shb_min;
 253         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_min, false > SkipList_RCU_sht_min;
 254 #endif
 255
 256         struct traits_SkipList_min_stat :
 257             public cc::skip_list::make_traits<
 258                 cc::opt::less< std::greater<Value> >
 259                 ,co::stat< cc::skip_list::stat<> >
 260             >::type
 261         {};
 262         typedef SkipListPQueue< cds::gc::HP, Value, traits_SkipList_min_stat, false > SkipList_HP_min_stat;
 263         typedef SkipListPQueue< cds::gc::DHP, Value, traits_SkipList_min_stat, false > SkipList_DHP_min_stat;
 264         typedef SkipListPQueue< rcu_gpi, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpi_min_stat;
 265         typedef SkipListPQueue< rcu_gpb, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpb_min_stat;
 266         typedef SkipListPQueue< rcu_gpt, Value, traits_SkipList_min_stat, false > SkipList_RCU_gpt_min_stat;
 267 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 268         typedef SkipListPQueue< rcu_shb, Value, traits_SkipList_min_stat, false > SkipList_RCU_shb_min_stat;
 269         typedef SkipListPQueue< rcu_sht, Value, traits_SkipList_min_stat, false > SkipList_RCU_sht_min_stat;
 270 #endif
 271
 272
 273         // FCPriorityQueue
 274         struct traits_FCPQueue_stat : public
 275             cds::container::fcpqueue::make_traits <
 276             cds::opt::stat < cds::container::fcpqueue::stat<> >
 277             > ::type
 278         {};
 279
 280         typedef cds::container::FCPriorityQueue< Value >    FCPQueue_vector;
 281         typedef cds::container::FCPriorityQueue< Value
 282             ,std::priority_queue<Value>
 283             ,traits_FCPQueue_stat
 284         >    FCPQueue_vector_stat;
 285
 286         typedef cds::container::FCPriorityQueue< Value
 287             ,std::priority_queue<Value, std::deque<Value> >
 288         > FCPQueue_deque;
 289         typedef cds::container::FCPriorityQueue< Value
 290             ,std::priority_queue<Value, std::deque<Value> >
 291             ,traits_FCPQueue_stat
 292         > FCPQueue_deque_stat;
 293
 294         typedef cds::container::FCPriorityQueue< Value
 295             ,std::priority_queue<Value, boost::container::deque<Value> >
 296         > FCPQueue_boost_deque;
 297         typedef cds::container::FCPriorityQueue< Value
 298             ,std::priority_queue<Value, boost::container::deque<Value> >
 299             ,traits_FCPQueue_stat
 300         > FCPQueue_boost_deque_stat;
 301
 302         typedef cds::container::FCPriorityQueue< Value
 303             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 304         > FCPQueue_boost_stable_vector;
 305         typedef cds::container::FCPriorityQueue< Value
 306             ,std::priority_queue<Value, boost::container::stable_vector<Value> >
 307             ,traits_FCPQueue_stat
 308         > FCPQueue_boost_stable_vector_stat;
 309
 310         /// Standard priority_queue
 311         typedef StdPQueue< Value, std::vector<Value>, cds::sync::spin> StdPQueue_vector_spin;
 312         typedef StdPQueue< Value, std::vector<Value>, std::mutex >  StdPQueue_vector_mutex;
 313         typedef StdPQueue< Value, std::deque<Value>, cds::sync::spin> StdPQueue_deque_spin;
 314         typedef StdPQueue< Value, std::deque<Value>,  std::mutex >  StdPQueue_deque_mutex;
 315     };
 316
 317
 318     template <typename Stat>
 319     static inline void check_statistics( Stat const& /*s*/ )
 320     {}
 321
 322     static inline void check_statistics( cds::container::ellen_bintree::stat<> const& s )
 323     {
 324         CPPUNIT_CHECK_CURRENT( s.m_nInternalNodeCreated.get() == s.m_nInternalNodeDeleted.get() );
 325         CPPUNIT_CHECK_CURRENT( s.m_nUpdateDescCreated.get() == s.m_nUpdateDescDeleted.get() );
 326     }
 327 }   // namespace pqueue
 328
 329 namespace std {
 330
 331     static inline std::ostream& operator <<( std::ostream& o, cds::container::fcpqueue::empty_stat const& )
 332     {
 333         return o;
 334     }
 335
 336     static inline std::ostream& operator <<( std::ostream& o, cds::container::fcpqueue::stat<> const& s )
 337     {
 338         return o << "\tStatistics:\n"
 339             << "\t              Push: " << s.m_nPush.get()         << "\n"
 340             << "\t         Push move: " << s.m_nPushMove.get()     << "\n"
 341             << "\t               Pop: " << s.m_nPop.get()          << "\n"
 342             << "\t        Failed pop: " << s.m_nFailedPop.get()    << "\n"
 343             << "\tFlat combining statistics:\n"
 344             << "\t        Combining factor: " << s.combining_factor()         << "\n"
 345             << "\t         Operation count: " << s.m_nOperationCount.get()    << "\n"
 346             << "\t      Combine call count: " << s.m_nCombiningCount.get()    << "\n"
 347             << "\t        Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
 348             << "\t   Deactivate pub-record: " << s.m_nDeactivatePubRecord.get()    << "\n"
 349             << "\t     Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
 350             << "\t       Create pub-record: " << s.m_nPubRecordCreated.get()  << "\n"
 351             << "\t       Delete pub-record: " << s.m_nPubRecordDeteted.get()  << "\n"
 352             << "\t      Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
 353             << "\t      Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
 354     }
 355
 356 } // namespace std
 357
 358 #endif // #ifndef CDSUNIT_PQUEUE_TYPES_H