tests/test-hdr/queue/hdr_intrusive_segmented_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSHDR_QUEUE_INTRUSIVE_SEGMENTED_QUEUE_H
   4 #define __CDSHDR_QUEUE_INTRUSIVE_SEGMENTED_QUEUE_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include <cds/intrusive/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 Disposer
  34         {
  35             void operator()( item * p )
  36             {
  37                 ++p->nDisposeCount;
  38             }
  39         };
  40
  41         struct Disposer2
  42         {
  43             void operator()( item * p )
  44             {
  45                 ++p->nDispose2Count;
  46             }
  47         };
  48
  49         template <typename Queue>
  50         void test()
  51         {
  52             for ( size_t nQuasiFactor = 2; nQuasiFactor <= 256; ++nQuasiFactor ) {
  53                 CPPUNIT_MSG( "QuasiFactor=" << nQuasiFactor << "..." );
  54                 test_qf<Queue>( nQuasiFactor );
  55             }
  56         }
  57
  58         template <typename Queue>
  59         void test_qf( size_t nQuasiFactor )
  60         {
  61             typedef typename Queue::value_type value_type;
  62
  63             static size_t const c_nItemCount = 1000;
  64             value_type val[c_nItemCount];
  65             for ( int i = 0; i < static_cast<int>(sizeof(val)/sizeof(val[0])); ++i )
  66                 val[i].nValue = i;
  67
  68             {
  69                 Queue q( nQuasiFactor );
  70                 CPPUNIT_CHECK( q.quasi_factor() == cds::beans::ceil2(nQuasiFactor) );
  71                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
  72                 CPPUNIT_CHECK( q.empty() );
  73
  74                 // push/enqueue
  75                 for ( size_t i = 0; i < sizeof(val)/sizeof(val[0]); ++i ) {
  76                     if ( i & 1 ) {
  77                         CPPUNIT_ASSERT( q.push( val[i] ));
  78                     }
  79                     else {
  80                         CPPUNIT_ASSERT( q.enqueue( val[i] ));
  81                     }
  82
  83                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
  84                 }
  85                 CPPUNIT_CHECK( !q.empty() );
  86
  87                 // pop/dequeue
  88                 size_t nCount = 0;
  89                 while ( !q.empty() ) {
  90                     value_type * pVal;
  91                     if ( nCount & 1 )
  92                         pVal = q.pop();
  93                     else
  94                         pVal = q.dequeue();
  95
  96                     CPPUNIT_ASSERT( pVal != NULL );
  97
  98                     int nSegment = int( nCount / q.quasi_factor() );
  99                     int nMin = nSegment * int(q.quasi_factor());
 100                     int nMax = nMin + int(q.quasi_factor()) - 1;
 101                     CPPUNIT_CHECK_EX( nMin <= pVal->nValue && pVal->nValue <= nMax, nMin << " <= " << pVal->nValue << " <= " << nMax );
 102
 103                     ++nCount;
 104                     CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) - nCount ));
 105                 }
 106                 CPPUNIT_CHECK( nCount == sizeof(val)/sizeof(val[0]) );
 107                 CPPUNIT_CHECK( q.empty() );
 108                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 109
 110                 // pop from empty queue
 111                 CPPUNIT_ASSERT( q.pop() == NULL );
 112                 CPPUNIT_CHECK( q.empty() );
 113                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 114
 115                 // check if Disposer has not been called
 116                 Queue::gc::force_dispose();
 117                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0]) ); ++i ) {
 118                     CPPUNIT_CHECK( val[i].nDisposeCount == 0 );
 119                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 120                 }
 121
 122                 // Manually dispose the items
 123                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 124                     Queue::gc::template retire<Disposer>( &(val[i]) );
 125
 126                 // check if Disposer has been called
 127                 Queue::gc::force_dispose();
 128                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 129                     CPPUNIT_CHECK( val[i].nDisposeCount == 1 );
 130                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 131                 }
 132
 133
 134                 // clear
 135                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 136                     CPPUNIT_CHECK( q.push( val[i] ) );
 137                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 138                 CPPUNIT_CHECK( !q.empty() );
 139
 140                 q.clear();
 141                 CPPUNIT_CHECK( misc::check_size( q, 0));
 142                 CPPUNIT_CHECK( q.empty() );
 143
 144                 // check if Disposer has been called
 145                 Queue::gc::force_dispose();
 146                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 147                     CPPUNIT_CHECK( val[i].nDisposeCount == 2 );
 148                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 149                 }
 150
 151                 // clear_with
 152                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 153                     CPPUNIT_CHECK( q.push( val[i] ) );
 154                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 155                 CPPUNIT_CHECK( !q.empty() );
 156
 157                 q.clear_with( Disposer2() );
 158                 CPPUNIT_CHECK( misc::check_size( q, 0));
 159                 CPPUNIT_CHECK( q.empty() );
 160
 161                 // check if Disposer has been called
 162                 Queue::gc::force_dispose();
 163                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 164                     CPPUNIT_CHECK( val[i].nDisposeCount == 2 );
 165                     CPPUNIT_CHECK( val[i].nDispose2Count == 1 );
 166                 }
 167
 168                 // check clear on destruct
 169                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 170                     CPPUNIT_CHECK( q.push( val[i] ) );
 171                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 172                 CPPUNIT_CHECK( !q.empty() );
 173             }
 174
 175             // check if Disposer has been called
 176             Queue::gc::force_dispose();
 177             for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 178                 CPPUNIT_CHECK( val[i].nDisposeCount == 3 );
 179                 CPPUNIT_CHECK( val[i].nDispose2Count == 1 );
 180             }
 181         }
 182
 183         void SegmQueue_HP();
 184         void SegmQueue_HP_mutex();
 185         void SegmQueue_HP_shuffle();
 186         void SegmQueue_HP_stat();
 187
 188         void SegmQueue_PTB();
 189         void SegmQueue_PTB_mutex();
 190         void SegmQueue_PTB_shuffle();
 191         void SegmQueue_PTB_stat();
 192
 193         CPPUNIT_TEST_SUITE(HdrIntrusiveSegmentedQueue)
 194             CPPUNIT_TEST( SegmQueue_HP )
 195             CPPUNIT_TEST( SegmQueue_HP_mutex )
 196             CPPUNIT_TEST( SegmQueue_HP_shuffle )
 197             CPPUNIT_TEST( SegmQueue_HP_stat )
 198
 199             CPPUNIT_TEST( SegmQueue_PTB )
 200             CPPUNIT_TEST( SegmQueue_PTB_mutex )
 201             CPPUNIT_TEST( SegmQueue_PTB_shuffle )
 202             CPPUNIT_TEST( SegmQueue_PTB_stat )
 203         CPPUNIT_TEST_SUITE_END()
 204     };
 205
 206 } // namespace queue
 207
 208 #endif // __CDSHDR_QUEUE_INTRUSIVE_SEGMENTED_QUEUE_H