tests/test-hdr/queue/hdr_intrusive_segmented_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_INTRUSIVE_SEGMENTED_QUEUE_H
   4 #define CDSTEST_HDR_INTRUSIVE_SEGMENTED_QUEUE_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include <cds/intrusive/details/base.h>
   8 #include "size_check.h"
   9
  10 namespace queue {
  11
  12     class HdrIntrusiveSegmentedQueue : public CppUnitMini::TestCase
  13     {
  14         struct item {
  15             int  nValue;
  16
  17             size_t  nDisposeCount;
  18             size_t  nDispose2Count;
  19
  20             item()
  21                 : nValue( 0 )
  22                 , nDisposeCount( 0 )
  23                 , nDispose2Count( 0 )
  24             {}
  25
  26             item( int nVal )
  27                 : nValue( nVal )
  28                 , nDisposeCount( 0 )
  29                 , nDispose2Count( 0 )
  30             {}
  31         };
  32
  33         struct big_item : public item
  34         {
  35             big_item()
  36             {}
  37
  38             big_item( int nVal )
  39                 : item( nVal )
  40             {}
  41
  42             int arr[80];
  43         };
  44
  45         struct Disposer
  46         {
  47             void operator()( item * p )
  48             {
  49                 ++p->nDisposeCount;
  50             }
  51         };
  52
  53         struct Disposer2
  54         {
  55             void operator()( item * p )
  56             {
  57                 ++p->nDispose2Count;
  58             }
  59         };
  60
  61         template <typename Queue>
  62         void test()
  63         {
  64             for ( size_t nQuasiFactor = 2; nQuasiFactor <= 256; ++nQuasiFactor ) {
  65                 CPPUNIT_MSG( "QuasiFactor=" << nQuasiFactor << "..." );
  66                 test_qf<Queue>( nQuasiFactor );
  67             }
  68         }
  69
  70         template <typename Queue>
  71         void test_qf( size_t nQuasiFactor )
  72         {
  73             typedef typename Queue::value_type value_type;
  74
  75             static size_t const c_nItemCount = 1000;
  76             value_type val[c_nItemCount];
  77             for ( int i = 0; i < static_cast<int>(sizeof(val)/sizeof(val[0])); ++i )
  78                 val[i].nValue = i;
  79
  80             {
  81                 Queue q( nQuasiFactor );
  82                 CPPUNIT_CHECK( q.quasi_factor() == cds::beans::ceil2(nQuasiFactor) );
  83                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
  84                 CPPUNIT_CHECK( q.empty() );
  85
  86                 // push/enqueue
  87                 for ( size_t i = 0; i < sizeof(val)/sizeof(val[0]); ++i ) {
  88                     if ( i & 1 ) {
  89                         CPPUNIT_ASSERT( q.push( val[i] ));
  90                     }
  91                     else {
  92                         CPPUNIT_ASSERT( q.enqueue( val[i] ));
  93                     }
  94
  95                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
  96                 }
  97                 CPPUNIT_CHECK( !q.empty() );
  98
  99                 // pop/dequeue
 100                 size_t nCount = 0;
 101                 while ( !q.empty() ) {
 102                     value_type * pVal;
 103                     if ( nCount & 1 )
 104                         pVal = q.pop();
 105                     else
 106                         pVal = q.dequeue();
 107
 108                     CPPUNIT_ASSERT( pVal != nullptr );
 109
 110                     int nSegment = int( nCount / q.quasi_factor() );
 111                     int nMin = nSegment * int(q.quasi_factor());
 112                     int nMax = nMin + int(q.quasi_factor()) - 1;
 113                     CPPUNIT_CHECK_EX( nMin <= pVal->nValue && pVal->nValue <= nMax, nMin << " <= " << pVal->nValue << " <= " << nMax );
 114
 115                     ++nCount;
 116                     CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) - nCount ));
 117                 }
 118                 CPPUNIT_CHECK( nCount == sizeof(val)/sizeof(val[0]) );
 119                 CPPUNIT_CHECK( q.empty() );
 120                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 121
 122                 // pop from empty queue
 123                 CPPUNIT_ASSERT( q.pop() == nullptr );
 124                 CPPUNIT_CHECK( q.empty() );
 125                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 126
 127                 // check if Disposer has not been called
 128                 Queue::gc::force_dispose();
 129                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0]) ); ++i ) {
 130                     CPPUNIT_CHECK( val[i].nDisposeCount == 0 );
 131                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 132                 }
 133
 134                 // Manually dispose the items
 135                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 136                     Queue::gc::template retire<Disposer>( &(val[i]) );
 137
 138                 // check if Disposer has been called
 139                 Queue::gc::force_dispose();
 140                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 141                     CPPUNIT_CHECK( val[i].nDisposeCount == 1 );
 142                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 143                 }
 144
 145
 146                 // clear
 147                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 148                     CPPUNIT_CHECK( q.push( val[i] ) );
 149                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 150                 CPPUNIT_CHECK( !q.empty() );
 151
 152                 q.clear();
 153                 CPPUNIT_CHECK( misc::check_size( q, 0));
 154                 CPPUNIT_CHECK( q.empty() );
 155
 156                 // check if Disposer has been called
 157                 Queue::gc::force_dispose();
 158                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 159                     CPPUNIT_CHECK( val[i].nDisposeCount == 2 );
 160                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 161                 }
 162
 163                 // clear_with
 164                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 165                     CPPUNIT_CHECK( q.push( val[i] ) );
 166                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 167                 CPPUNIT_CHECK( !q.empty() );
 168
 169                 q.clear_with( Disposer2() );
 170                 CPPUNIT_CHECK( misc::check_size( q, 0));
 171                 CPPUNIT_CHECK( q.empty() );
 172
 173                 // check if Disposer has been called
 174                 Queue::gc::force_dispose();
 175                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 176                     CPPUNIT_CHECK( val[i].nDisposeCount == 2 );
 177                     CPPUNIT_CHECK( val[i].nDispose2Count == 1 );
 178                 }
 179
 180                 // check clear on destruct
 181                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 182                     CPPUNIT_CHECK( q.push( val[i] ) );
 183                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 184                 CPPUNIT_CHECK( !q.empty() );
 185             }
 186
 187             // check if Disposer has been called
 188             Queue::gc::force_dispose();
 189             for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 190                 CPPUNIT_CHECK( val[i].nDisposeCount == 3 );
 191                 CPPUNIT_CHECK( val[i].nDispose2Count == 1 );
 192             }
 193         }
 194
 195         void SegmQueue_HP();
 196         void SegmQueue_HP_mutex();
 197         void SegmQueue_HP_shuffle();
 198         void SegmQueue_HP_stat();
 199         void SegmQueue_HP_cacheline_padding();
 200         void SegmQueue_HP_mutex_cacheline_padding();
 201         void SegmQueue_HP_shuffle_cacheline_padding();
 202         void SegmQueue_HP_stat_cacheline_padding();
 203         void SegmQueue_HP_256_padding();
 204         void SegmQueue_HP_mutex_256_padding();
 205         void SegmQueue_HP_shuffle_256_padding();
 206         void SegmQueue_HP_stat_256_padding();
 207         void SegmQueue_HP_cacheline_padding_bigdata();
 208         void SegmQueue_HP_mutex_cacheline_padding_bigdata();
 209         void SegmQueue_HP_shuffle_cacheline_padding_bigdata();
 210         void SegmQueue_HP_stat_cacheline_padding_bigdata();
 211
 212         void SegmQueue_DHP();
 213         void SegmQueue_DHP_mutex();
 214         void SegmQueue_DHP_shuffle();
 215         void SegmQueue_DHP_stat();
 216         void SegmQueue_DHP_cacheline_padding();
 217         void SegmQueue_DHP_mutex_cacheline_padding();
 218         void SegmQueue_DHP_shuffle_cacheline_padding();
 219         void SegmQueue_DHP_stat_cacheline_padding();
 220         void SegmQueue_DHP_256_padding();
 221         void SegmQueue_DHP_mutex_256_padding();
 222         void SegmQueue_DHP_shuffle_256_padding();
 223         void SegmQueue_DHP_stat_256_padding();
 224         void SegmQueue_DHP_cacheline_padding_bigdata();
 225         void SegmQueue_DHP_mutex_cacheline_padding_bigdata();
 226         void SegmQueue_DHP_shuffle_cacheline_padding_bigdata();
 227         void SegmQueue_DHP_stat_cacheline_padding_bigdata();
 228
 229         CPPUNIT_TEST_SUITE(HdrIntrusiveSegmentedQueue)
 230             CPPUNIT_TEST( SegmQueue_HP )
 231             CPPUNIT_TEST( SegmQueue_HP_mutex )
 232             CPPUNIT_TEST( SegmQueue_HP_shuffle )
 233             CPPUNIT_TEST( SegmQueue_HP_stat )
 234             CPPUNIT_TEST( SegmQueue_HP_cacheline_padding )
 235             CPPUNIT_TEST( SegmQueue_HP_mutex_cacheline_padding )
 236             CPPUNIT_TEST( SegmQueue_HP_shuffle_cacheline_padding )
 237             CPPUNIT_TEST( SegmQueue_HP_stat_cacheline_padding )
 238             CPPUNIT_TEST( SegmQueue_HP_256_padding )
 239             CPPUNIT_TEST( SegmQueue_HP_mutex_256_padding )
 240             CPPUNIT_TEST( SegmQueue_HP_shuffle_256_padding )
 241             CPPUNIT_TEST( SegmQueue_HP_stat_256_padding )
 242             CPPUNIT_TEST( SegmQueue_HP_cacheline_padding_bigdata )
 243             CPPUNIT_TEST( SegmQueue_HP_mutex_cacheline_padding_bigdata )
 244             CPPUNIT_TEST( SegmQueue_HP_shuffle_cacheline_padding_bigdata )
 245             CPPUNIT_TEST( SegmQueue_HP_stat_cacheline_padding_bigdata )
 246
 247             CPPUNIT_TEST( SegmQueue_DHP )
 248             CPPUNIT_TEST( SegmQueue_DHP_mutex )
 249             CPPUNIT_TEST( SegmQueue_DHP_shuffle )
 250             CPPUNIT_TEST( SegmQueue_DHP_stat )
 251             CPPUNIT_TEST( SegmQueue_DHP_cacheline_padding )
 252             CPPUNIT_TEST( SegmQueue_DHP_mutex_cacheline_padding )
 253             CPPUNIT_TEST( SegmQueue_DHP_shuffle_cacheline_padding )
 254             CPPUNIT_TEST( SegmQueue_DHP_stat_cacheline_padding )
 255             CPPUNIT_TEST( SegmQueue_DHP_256_padding )
 256             CPPUNIT_TEST( SegmQueue_DHP_mutex_256_padding )
 257             CPPUNIT_TEST( SegmQueue_DHP_shuffle_256_padding )
 258             CPPUNIT_TEST( SegmQueue_DHP_stat_256_padding )
 259             CPPUNIT_TEST( SegmQueue_DHP_cacheline_padding_bigdata )
 260             CPPUNIT_TEST( SegmQueue_DHP_mutex_cacheline_padding_bigdata )
 261             CPPUNIT_TEST( SegmQueue_DHP_shuffle_cacheline_padding_bigdata )
 262             CPPUNIT_TEST( SegmQueue_DHP_stat_cacheline_padding_bigdata )
 263         CPPUNIT_TEST_SUITE_END()
 264     };
 265
 266 } // namespace queue
 267
 268 #endif // CDSTEST_HDR_INTRUSIVE_SEGMENTED_QUEUE_H