tests/test-hdr/queue/hdr_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_QUEUE_H
   4 #define CDSTEST_HDR_QUEUE_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include <cds/details/defs.h>
   8
   9 namespace queue {
  10
  11     //
  12     // Test queue operation in single thread mode
  13     //
  14     class HdrTestQueue: public CppUnitMini::TestCase
  15     {
  16     protected:
  17         template <class Queue>
  18         void test_no_ic()
  19         {
  20             Queue   q;
  21             test_with( q );
  22             test_emplace( q );
  23         }
  24
  25         template <class Queue>
  26         void test_with( Queue& q )
  27         {
  28             int     it;
  29             int     nPrev;
  30
  31             // push/pop
  32             for ( size_t i = 0; i < 3; ++i ) {
  33                 CPPUNIT_ASSERT( q.empty() );
  34 #ifndef _DEBUG
  35                 CPPUNIT_ASSERT( q.size() == 0 );
  36 #endif
  37                 CPPUNIT_ASSERT( q.enqueue( 1 ) );
  38                 CPPUNIT_ASSERT( !q.empty() );
  39                 CPPUNIT_ASSERT( q.push( 10 ) );
  40                 CPPUNIT_ASSERT( !q.empty() );
  41 #ifndef _DEBUG
  42                 CPPUNIT_ASSERT( q.size() == 0 )     ;   // no queue's item counter!
  43 #endif
  44
  45                 it = -1;
  46                 CPPUNIT_ASSERT( q.pop( it ) );
  47                 CPPUNIT_ASSERT( it == 1 );
  48                 CPPUNIT_ASSERT( !q.empty() );
  49                 CPPUNIT_ASSERT( q.dequeue( it ) );
  50                 CPPUNIT_ASSERT( it == 10 );
  51 #ifndef _DEBUG
  52                 CPPUNIT_ASSERT( q.size() == 0 );
  53 #endif
  54                 CPPUNIT_ASSERT( q.empty() );
  55                 it += 2009;
  56                 nPrev = it;
  57                 CPPUNIT_ASSERT( !q.dequeue( it ) );
  58                 CPPUNIT_ASSERT( it == nPrev )       ;   // it must not be changed!
  59             }
  60
  61             // push_with/pop_with
  62             for ( size_t i = 0; i < 3; ++i ) {
  63                 CPPUNIT_ASSERT( q.empty() );
  64 #ifndef _DEBUG
  65                 CPPUNIT_ASSERT( q.size() == 0 );
  66 #endif
  67                 CPPUNIT_ASSERT( q.enqueue_with( []( int& dest ) { dest = 1; } ));
  68                 CPPUNIT_ASSERT( !q.empty() );
  69                 CPPUNIT_ASSERT( q.push_with( []( int& dest ) { dest = 10; } ));
  70                 CPPUNIT_ASSERT( !q.empty() );
  71 #ifndef _DEBUG
  72                 CPPUNIT_ASSERT( q.size() == 0 );   // no queue's item counter!
  73 #endif
  74
  75                 it = -1;
  76                 CPPUNIT_ASSERT( q.pop_with( [&it]( int src ) { it = src; } ));
  77                 CPPUNIT_ASSERT( it == 1 );
  78                 CPPUNIT_ASSERT( !q.empty() );
  79                 CPPUNIT_ASSERT( q.dequeue_with( [&it]( int src ) { it = src; } ));
  80                 CPPUNIT_ASSERT( it == 10 );
  81 #ifndef _DEBUG
  82                 CPPUNIT_ASSERT( q.size() == 0 );
  83 #endif
  84                 CPPUNIT_ASSERT( q.empty() );
  85                 it += 2009;
  86                 nPrev = it;
  87                 CPPUNIT_ASSERT( !q.dequeue_with( [&it]( int src ) { it = src; } ));
  88                 CPPUNIT_ASSERT( it == nPrev );   // it must not be changed!
  89             }
  90         }
  91
  92         template <class Queue>
  93         void test_emplace( Queue& q )
  94         {
  95             int     it;
  96             for ( size_t i = 0; i < 3; ++i ) {
  97                 CPPUNIT_ASSERT( q.emplace( static_cast<int>( i * 42 )) );
  98                 CPPUNIT_ASSERT( !q.empty() );
  99                 it = -1;
 100                 CPPUNIT_ASSERT( q.pop( it ));
 101                 CPPUNIT_ASSERT( it == static_cast<int>( i * 42 ));
 102                 CPPUNIT_ASSERT( q.empty() );
 103             }
 104         }
 105
 106         template <class Queue>
 107         void test_ic()
 108         {
 109             Queue   q;
 110             test_ic_with( q );
 111             test_emplace_ic( q );
 112         }
 113
 114         template <class Queue>
 115         void testFCQueue()
 116         {
 117             Queue   q;
 118             test_ic_with( q );
 119         }
 120
 121         template <class Queue>
 122         void test_ic_with( Queue& q )
 123         {
 124             int     it;
 125             int     nPrev;
 126
 127             // push/pop
 128             for ( size_t i = 0; i < 3; ++i ) {
 129                 CPPUNIT_ASSERT( q.empty() );
 130                 CPPUNIT_ASSERT( q.size() == 0 );
 131                 CPPUNIT_ASSERT( q.enqueue( 1 ) );
 132                 CPPUNIT_ASSERT( q.size() == 1 );
 133                 CPPUNIT_ASSERT( !q.empty() );
 134                 CPPUNIT_ASSERT( q.push( 10 ) );
 135                 CPPUNIT_ASSERT( !q.empty() );
 136                 CPPUNIT_ASSERT( q.size() == 2 );
 137
 138                 it = -1;
 139                 CPPUNIT_ASSERT( q.pop( it ) );
 140                 CPPUNIT_ASSERT( it == 1 );
 141                 CPPUNIT_ASSERT( !q.empty() );
 142                 CPPUNIT_ASSERT( q.size() == 1 );
 143                 CPPUNIT_ASSERT( q.dequeue( it ) );
 144                 CPPUNIT_ASSERT( it == 10 );
 145                 CPPUNIT_ASSERT( q.size() == 0 );
 146                 CPPUNIT_ASSERT( q.empty() );
 147                 CPPUNIT_ASSERT( q.size() == 0 );
 148                 it += 2009;
 149                 nPrev = it;
 150                 CPPUNIT_ASSERT( !q.dequeue( it ) );
 151                 CPPUNIT_ASSERT( it == nPrev )       ;   // it must not be changed!
 152
 153                 CPPUNIT_ASSERT( q.empty() );
 154                 CPPUNIT_ASSERT( q.size() == 0 );
 155             }
 156
 157             // push_with/pop_with
 158             for ( size_t i = 0; i < 3; ++i ) {
 159                 CPPUNIT_ASSERT( q.empty() );
 160                 CPPUNIT_ASSERT( q.size() == 0 );
 161                 CPPUNIT_ASSERT( q.enqueue_with( []( int& dest ) { dest = 1; } ) );
 162                 CPPUNIT_ASSERT( !q.empty() );
 163                 CPPUNIT_ASSERT( q.size() == 1 );
 164                 CPPUNIT_ASSERT( q.push_with( []( int& dest ) { dest = 10; } ) );
 165                 CPPUNIT_ASSERT( !q.empty() );
 166                 CPPUNIT_ASSERT( q.size() == 2 );
 167
 168                 it = -1;
 169                 CPPUNIT_ASSERT( q.pop_with( [&it]( int src ) { it = src; } ) );
 170                 CPPUNIT_ASSERT( it == 1 );
 171                 CPPUNIT_ASSERT( !q.empty() );
 172                 CPPUNIT_ASSERT( q.size() == 1 );
 173                 CPPUNIT_ASSERT( q.dequeue_with( [&it]( int src ) { it = src; } ) );
 174                 CPPUNIT_ASSERT( it == 10 );
 175                 CPPUNIT_ASSERT( q.size() == 0 );
 176                 CPPUNIT_ASSERT( q.empty() );
 177                 it += 2009;
 178                 nPrev = it;
 179                 CPPUNIT_ASSERT( !q.dequeue_with( [&it]( int src ) { it = src; } ) );
 180                 CPPUNIT_ASSERT( it == nPrev );   // it must not be changed!
 181
 182                 CPPUNIT_ASSERT( q.size() == 0 );
 183                 CPPUNIT_ASSERT( q.empty() );
 184             }
 185         }
 186
 187         template <class Queue>
 188         void test_emplace_ic( Queue& q )
 189         {
 190             int     it = 0;
 191             for ( size_t i = 0; i < 3; ++i ) {
 192                 CPPUNIT_ASSERT( q.emplace( (int) i * 10 ) );
 193                 CPPUNIT_ASSERT( !q.empty() );
 194                 CPPUNIT_ASSERT( q.size() == 1 );
 195                 CPPUNIT_ASSERT( q.pop( it ));
 196                 CPPUNIT_ASSERT( it == (int) i * 10 );
 197                 CPPUNIT_ASSERT( q.empty() );
 198                 CPPUNIT_ASSERT( q.size() == 0 );
 199             }
 200         }
 201
 202         template <class Queue>
 203         void test_bounded_no_ic()
 204         {
 205             Queue   q;
 206             test_with( q );
 207             test_emplace( q );
 208
 209             CPPUNIT_ASSERT( q.empty() );
 210             size_t nCapacity = q.capacity();
 211             for ( size_t i = 0; i < nCapacity; ++i ) {
 212                 CPPUNIT_CHECK_EX( q.push( static_cast<int>(i) ), "capacity=" << nCapacity << ", i=" << i );
 213             }
 214             // The queue is full
 215             CPPUNIT_CHECK( !q.empty() );
 216             CPPUNIT_ASSERT( !q.push_with( [nCapacity]( int& itm ) { itm = static_cast<int>(nCapacity); } ) );
 217             int n = -1;
 218             CPPUNIT_CHECK( q.pop(n) );
 219             CPPUNIT_CHECK( n == 0 );
 220             CPPUNIT_ASSERT( q.push( static_cast<int>(nCapacity) ) );
 221             CPPUNIT_ASSERT( !q.push( static_cast<int>(nCapacity) ) );
 222         }
 223
 224         template <class Queue>
 225         void test_bounded_ic()
 226         {
 227             Queue   q;
 228             test_ic_with( q );
 229             test_emplace_ic( q );
 230
 231             CPPUNIT_ASSERT( q.empty() );
 232             size_t nCapacity = q.capacity();
 233             for ( size_t i = 0; i < nCapacity; ++i ) {
 234                 CPPUNIT_CHECK_EX( q.push( static_cast<int>(i) ), "capacity=" << nCapacity << ", i=" << i );
 235             }
 236             // The queue is full
 237             CPPUNIT_CHECK( !q.empty() );
 238             CPPUNIT_CHECK( q.size() == nCapacity );
 239             CPPUNIT_ASSERT( !q.push_with( [nCapacity]( int& itm ) { itm = static_cast<int>(nCapacity); } ));
 240             int n = -1;
 241             CPPUNIT_CHECK( q.pop( n ) );
 242             CPPUNIT_CHECK( n == 0 );
 243             CPPUNIT_ASSERT( q.push( static_cast<int>(nCapacity) ) );
 244             CPPUNIT_CHECK( q.size() == nCapacity );
 245             CPPUNIT_ASSERT( !q.push( static_cast<int>(nCapacity) ) );
 246             CPPUNIT_CHECK( q.size() == nCapacity );
 247         }
 248
 249     public:
 250         void MSQueue_HP();
 251         void MSQueue_HP_relax();
 252         void MSQueue_HP_seqcst();
 253         void MSQueue_HP_relax_align();
 254         void MSQueue_HP_seqcst_align();
 255         void MSQueue_HP_Counted();
 256         void MSQueue_HP_Counted_relax();
 257         void MSQueue_HP_Counted_seqcst();
 258         void MSQueue_HP_Counted_relax_align();
 259         void MSQueue_HP_Counted_seqcst_align();
 260
 261         void MSQueue_DHP();
 262         void MSQueue_DHP_relax();
 263         void MSQueue_DHP_seqcst();
 264         void MSQueue_DHP_relax_align();
 265         void MSQueue_DHP_seqcst_align();
 266         void MSQueue_DHP_Counted();
 267         void MSQueue_DHP_Counted_relax();
 268         void MSQueue_DHP_Counted_seqcst();
 269         void MSQueue_DHP_Counted_relax_align();
 270         void MSQueue_DHP_Counted_seqcst_align();
 271
 272         void MoirQueue_HP();
 273         void MoirQueue_HP_relax();
 274         void MoirQueue_HP_seqcst();
 275         void MoirQueue_HP_relax_align();
 276         void MoirQueue_HP_seqcst_align();
 277         void MoirQueue_HP_Counted();
 278         void MoirQueue_HP_Counted_relax();
 279         void MoirQueue_HP_Counted_seqcst();
 280         void MoirQueue_HP_Counted_relax_align();
 281         void MoirQueue_HP_Counted_seqcst_align();
 282
 283         void MoirQueue_DHP();
 284         void MoirQueue_DHP_relax();
 285         void MoirQueue_DHP_seqcst();
 286         void MoirQueue_DHP_relax_align();
 287         void MoirQueue_DHP_seqcst_align();
 288         void MoirQueue_DHP_Counted();
 289         void MoirQueue_DHP_Counted_relax();
 290         void MoirQueue_DHP_Counted_seqcst();
 291         void MoirQueue_DHP_Counted_relax_align();
 292         void MoirQueue_DHP_Counted_seqcst_align();
 293
 294         void OptimisticQueue_HP();
 295         void OptimisticQueue_HP_relax();
 296         void OptimisticQueue_HP_seqcst();
 297         void OptimisticQueue_HP_relax_align();
 298         void OptimisticQueue_HP_seqcst_align();
 299         void OptimisticQueue_HP_Counted();
 300         void OptimisticQueue_HP_Counted_relax();
 301         void OptimisticQueue_HP_Counted_seqcst();
 302         void OptimisticQueue_HP_Counted_relax_align();
 303         void OptimisticQueue_HP_Counted_seqcst_align();
 304
 305         void OptimisticQueue_DHP();
 306         void OptimisticQueue_DHP_relax();
 307         void OptimisticQueue_DHP_seqcst();
 308         void OptimisticQueue_DHP_relax_align();
 309         void OptimisticQueue_DHP_seqcst_align();
 310         void OptimisticQueue_DHP_Counted();
 311         void OptimisticQueue_DHP_Counted_relax();
 312         void OptimisticQueue_DHP_Counted_seqcst();
 313         void OptimisticQueue_DHP_Counted_relax_align();
 314         void OptimisticQueue_DHP_Counted_seqcst_align();
 315
 316         void BasketQueue_HP();
 317         void BasketQueue_HP_relax();
 318         void BasketQueue_HP_seqcst();
 319         void BasketQueue_HP_relax_align();
 320         void BasketQueue_HP_seqcst_align();
 321         void BasketQueue_HP_Counted();
 322         void BasketQueue_HP_Counted_relax();
 323         void BasketQueue_HP_Counted_seqcst();
 324         void BasketQueue_HP_Counted_relax_align();
 325         void BasketQueue_HP_Counted_seqcst_align();
 326
 327         void BasketQueue_DHP();
 328         void BasketQueue_DHP_relax();
 329         void BasketQueue_DHP_seqcst();
 330         void BasketQueue_DHP_relax_align();
 331         void BasketQueue_DHP_seqcst_align();
 332         void BasketQueue_DHP_Counted();
 333         void BasketQueue_DHP_Counted_relax();
 334         void BasketQueue_DHP_Counted_seqcst();
 335         void BasketQueue_DHP_Counted_relax_align();
 336         void BasketQueue_DHP_Counted_seqcst_align();
 337
 338         void RWQueue_default();
 339         void RWQueue_mutex();
 340         void RWQueue_ic();
 341         void RWQueue_ic_mutex();
 342
 343         void TsigasCycleQueue_static();
 344         void TsigasCycleQueue_static_ic();
 345         void TsigasCycleQueue_dyn();
 346         void TsigasCycleQueue_dyn_ic();
 347
 348         void VyukovMPMCCycleQueue_static();
 349         void VyukovMPMCCycleQueue_static_ic();
 350         void VyukovMPMCCycleQueue_dyn();
 351         void VyukovMPMCCycleQueue_dyn_ic();
 352
 353         CPPUNIT_TEST_SUITE( HdrTestQueue )
 354             CPPUNIT_TEST(MSQueue_HP);
 355             CPPUNIT_TEST(MSQueue_HP_relax);
 356             CPPUNIT_TEST(MSQueue_HP_seqcst);
 357             CPPUNIT_TEST(MSQueue_HP_relax_align);
 358             CPPUNIT_TEST(MSQueue_HP_seqcst_align);
 359             CPPUNIT_TEST(MSQueue_HP_Counted);
 360             CPPUNIT_TEST(MSQueue_HP_Counted_relax);
 361             CPPUNIT_TEST(MSQueue_HP_Counted_seqcst);
 362             CPPUNIT_TEST(MSQueue_HP_Counted_relax_align);
 363             CPPUNIT_TEST(MSQueue_HP_Counted_seqcst_align);
 364
 365             CPPUNIT_TEST(MSQueue_DHP);
 366             CPPUNIT_TEST(MSQueue_DHP_relax);
 367             CPPUNIT_TEST(MSQueue_DHP_seqcst);
 368             CPPUNIT_TEST(MSQueue_DHP_relax_align);
 369             CPPUNIT_TEST(MSQueue_DHP_seqcst_align);
 370             CPPUNIT_TEST(MSQueue_DHP_Counted);
 371             CPPUNIT_TEST(MSQueue_DHP_Counted_relax);
 372             CPPUNIT_TEST(MSQueue_DHP_Counted_seqcst);
 373             CPPUNIT_TEST(MSQueue_DHP_Counted_relax_align);
 374             CPPUNIT_TEST(MSQueue_DHP_Counted_seqcst_align);
 375
 376             CPPUNIT_TEST(MoirQueue_HP);
 377             CPPUNIT_TEST(MoirQueue_HP_relax);
 378             CPPUNIT_TEST(MoirQueue_HP_seqcst);
 379             CPPUNIT_TEST(MoirQueue_HP_relax_align);
 380             CPPUNIT_TEST(MoirQueue_HP_seqcst_align);
 381             CPPUNIT_TEST(MoirQueue_HP_Counted);
 382             CPPUNIT_TEST(MoirQueue_HP_Counted_relax);
 383             CPPUNIT_TEST(MoirQueue_HP_Counted_seqcst);
 384             CPPUNIT_TEST(MoirQueue_HP_Counted_relax_align);
 385             CPPUNIT_TEST(MoirQueue_HP_Counted_seqcst_align);
 386
 387             CPPUNIT_TEST(MoirQueue_DHP);
 388             CPPUNIT_TEST(MoirQueue_DHP_relax);
 389             CPPUNIT_TEST(MoirQueue_DHP_seqcst);
 390             CPPUNIT_TEST(MoirQueue_DHP_relax_align);
 391             CPPUNIT_TEST(MoirQueue_DHP_seqcst_align);
 392             CPPUNIT_TEST(MoirQueue_DHP_Counted);
 393             CPPUNIT_TEST(MoirQueue_DHP_Counted_relax);
 394             CPPUNIT_TEST(MoirQueue_DHP_Counted_seqcst);
 395             CPPUNIT_TEST(MoirQueue_DHP_Counted_relax_align);
 396             CPPUNIT_TEST(MoirQueue_DHP_Counted_seqcst_align);
 397
 398             CPPUNIT_TEST(OptimisticQueue_HP);
 399             CPPUNIT_TEST(OptimisticQueue_HP_relax);
 400             CPPUNIT_TEST(OptimisticQueue_HP_seqcst);
 401             CPPUNIT_TEST(OptimisticQueue_HP_relax_align);
 402             CPPUNIT_TEST(OptimisticQueue_HP_seqcst_align);
 403             CPPUNIT_TEST(OptimisticQueue_HP_Counted);
 404             CPPUNIT_TEST(OptimisticQueue_HP_Counted_relax);
 405             CPPUNIT_TEST(OptimisticQueue_HP_Counted_seqcst);
 406             CPPUNIT_TEST(OptimisticQueue_HP_Counted_relax_align);
 407             CPPUNIT_TEST(OptimisticQueue_HP_Counted_seqcst_align);
 408
 409             CPPUNIT_TEST(OptimisticQueue_DHP);
 410             CPPUNIT_TEST(OptimisticQueue_DHP_relax);
 411             CPPUNIT_TEST(OptimisticQueue_DHP_seqcst);
 412             CPPUNIT_TEST(OptimisticQueue_DHP_relax_align);
 413             CPPUNIT_TEST(OptimisticQueue_DHP_seqcst_align);
 414             CPPUNIT_TEST(OptimisticQueue_DHP_Counted);
 415             CPPUNIT_TEST(OptimisticQueue_DHP_Counted_relax);
 416             CPPUNIT_TEST(OptimisticQueue_DHP_Counted_seqcst);
 417             CPPUNIT_TEST(OptimisticQueue_DHP_Counted_relax_align);
 418             CPPUNIT_TEST(OptimisticQueue_DHP_Counted_seqcst_align);
 419
 420             CPPUNIT_TEST(BasketQueue_HP);
 421             CPPUNIT_TEST(BasketQueue_HP_relax);
 422             CPPUNIT_TEST(BasketQueue_HP_seqcst);
 423             CPPUNIT_TEST(BasketQueue_HP_relax_align);
 424             CPPUNIT_TEST(BasketQueue_HP_seqcst_align);
 425             CPPUNIT_TEST(BasketQueue_HP_Counted);
 426             CPPUNIT_TEST(BasketQueue_HP_Counted_relax);
 427             CPPUNIT_TEST(BasketQueue_HP_Counted_seqcst);
 428             CPPUNIT_TEST(BasketQueue_HP_Counted_relax_align);
 429             CPPUNIT_TEST(BasketQueue_HP_Counted_seqcst_align);
 430
 431             CPPUNIT_TEST(BasketQueue_DHP);
 432             CPPUNIT_TEST(BasketQueue_DHP_relax);
 433             CPPUNIT_TEST(BasketQueue_DHP_seqcst);
 434             CPPUNIT_TEST(BasketQueue_DHP_relax_align);
 435             CPPUNIT_TEST(BasketQueue_DHP_seqcst_align);
 436             CPPUNIT_TEST(BasketQueue_DHP_Counted);
 437             CPPUNIT_TEST(BasketQueue_DHP_Counted_relax);
 438             CPPUNIT_TEST(BasketQueue_DHP_Counted_seqcst);
 439             CPPUNIT_TEST(BasketQueue_DHP_Counted_relax_align);
 440             CPPUNIT_TEST(BasketQueue_DHP_Counted_seqcst_align);
 441
 442             CPPUNIT_TEST( TsigasCycleQueue_static )
 443             CPPUNIT_TEST( TsigasCycleQueue_static_ic )
 444             CPPUNIT_TEST( TsigasCycleQueue_dyn )
 445             CPPUNIT_TEST( TsigasCycleQueue_dyn_ic )
 446
 447             CPPUNIT_TEST( VyukovMPMCCycleQueue_static )
 448             CPPUNIT_TEST( VyukovMPMCCycleQueue_static_ic )
 449             CPPUNIT_TEST( VyukovMPMCCycleQueue_dyn )
 450             CPPUNIT_TEST( VyukovMPMCCycleQueue_dyn_ic )
 451
 452             CPPUNIT_TEST( RWQueue_default)
 453             CPPUNIT_TEST( RWQueue_mutex )
 454             CPPUNIT_TEST( RWQueue_ic )
 455
 456         CPPUNIT_TEST_SUITE_END();
 457
 458     };
 459 } // namespace queue
 460
 461 #endif // #ifndef CDSTEST_HDR_QUEUE_H