tests/test-hdr/queue/hdr_segmented_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSHDR_QUEUE_SEGMENTED_QUEUE_H
   4 #define __CDSHDR_QUEUE_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 HdrSegmentedQueue: public CppUnitMini::TestCase
  13     {
  14         struct item {
  15             size_t nVal;
  16
  17             item() {}
  18             item( size_t v ): nVal(v) {}
  19             item( size_t nMajor, size_t nMinor ): nVal( nMajor * 16 + nMinor ) {}
  20         };
  21
  22         struct other_item {
  23             size_t  nVal;
  24         };
  25
  26         template <typename Queue>
  27         void test()
  28         {
  29             for ( size_t nQuasiFactor = 2; nQuasiFactor <= 256; ++nQuasiFactor ) {
  30                 CPPUNIT_MSG( "QuasiFactor=" << nQuasiFactor << "..." );
  31                 test_qf<Queue>( nQuasiFactor );
  32             }
  33         }
  34
  35         template <typename Queue>
  36         void test_qf( size_t nQuasiFactor )
  37         {
  38             typedef typename Queue::value_type value_type;
  39
  40             static size_t const c_nItemCount = 1000;
  41
  42             {
  43                 Queue q( nQuasiFactor );
  44                 CPPUNIT_CHECK( q.quasi_factor() == cds::beans::ceil2(nQuasiFactor) );
  45                 CPPUNIT_CHECK( q.empty() );
  46                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
  47
  48                 // push/enqueue
  49                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
  50                     if ( i & 1 ) {
  51                         CPPUNIT_ASSERT( q.push(item(i)) );
  52                     }
  53                     else {
  54                         CPPUNIT_ASSERT( q.enqueue(item(i)) );
  55                     }
  56                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
  57                     CPPUNIT_CHECK( !q.empty() );
  58                 }
  59
  60                 // pop/dequeue
  61                 size_t nCount = 0;
  62                 while ( !q.empty() ) {
  63                     value_type v;
  64                     if ( nCount & 1 ) {
  65                         CPPUNIT_ASSERT( q.pop( v ) );
  66                     }
  67                     else {
  68                         CPPUNIT_ASSERT( q.dequeue( v ));
  69                     }
  70
  71                     int nSegment = int( nCount / q.quasi_factor() );
  72                     int nMin = nSegment * int(q.quasi_factor());
  73                     int nMax = nMin + int(q.quasi_factor()) - 1;
  74                     CPPUNIT_CHECK_EX( nMin <= static_cast<int>(v.nVal) && static_cast<int>( v.nVal ) <= nMax, nMin << " <= " << v.nVal << " <= " << nMax );
  75
  76                     ++nCount;
  77                     CPPUNIT_CHECK( misc::check_size( q, c_nItemCount - nCount ));
  78                 }
  79                 CPPUNIT_CHECK( nCount == c_nItemCount );
  80                 CPPUNIT_CHECK( q.empty() );
  81                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
  82
  83
  84                 // push/pop with functor
  85                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
  86                     other_item itm;
  87                     itm.nVal = i;
  88                     if ( i & 1 ) {
  89                         CPPUNIT_ASSERT( q.push_with( [&itm]( item& dest ) { dest.nVal = itm.nVal; } ));
  90                     }
  91                     else {
  92                         CPPUNIT_ASSERT( q.enqueue_with( [&itm]( item& dest ) { dest.nVal = itm.nVal; } ));
  93                     }
  94                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
  95                     CPPUNIT_CHECK( !q.empty() );
  96                 }
  97
  98                 {
  99                     other_item v;
 100
 101                     nCount = 0;
 102                     size_t nFuncCount = 0;
 103                     while ( !q.empty() ) {
 104                         if ( nCount & 1 ) {
 105                             CPPUNIT_ASSERT( q.pop_with( [&v, &nFuncCount]( item& src ) {v.nVal = src.nVal; ++nFuncCount; } ));
 106                         }
 107                         else {
 108                             CPPUNIT_ASSERT( q.dequeue_with( [&v, &nFuncCount]( item& src ) {v.nVal = src.nVal; ++nFuncCount; } ));
 109                         }
 110
 111                         // It is possible c_nItemCount % quasi_factor() != 0
 112                         // In this case the segment cannot be calculated here
 113                         size_t nMin = nCount > q.quasi_factor() ? nCount - q.quasi_factor() : 0;
 114                         size_t nMax = nCount + q.quasi_factor();
 115                         CPPUNIT_CHECK_EX( nMin <= v.nVal && v.nVal <= nMax, nMin << " <= " << v.nVal << " <= " << nMax );
 116
 117                         ++nCount;
 118                         CPPUNIT_CHECK( nFuncCount == nCount );
 119                         CPPUNIT_CHECK( misc::check_size( q, c_nItemCount - nCount ));
 120                     }
 121                     CPPUNIT_CHECK( nCount == c_nItemCount );
 122                     CPPUNIT_CHECK( q.empty() );
 123                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 124                 }
 125
 126                 //emplace
 127                 {
 128                     size_t nMajor = 0;
 129                     size_t nMinor = 0;
 130                     for ( size_t i = 0; i < c_nItemCount; ++i ) {
 131                         CPPUNIT_CHECK( q.emplace( nMajor, nMinor ));
 132                         if ( nMinor  == 15 ) {
 133                             ++nMajor;
 134                             nMinor = 0;
 135                         }
 136                         else
 137                             ++nMinor;
 138                         CPPUNIT_CHECK( !q.empty() );
 139                     }
 140                     CPPUNIT_CHECK( misc::check_size( q, c_nItemCount ));
 141
 142                     nCount = 0;
 143                     while ( !q.empty() ) {
 144                         value_type v;
 145                         if ( nCount & 1 ) {
 146                             CPPUNIT_ASSERT( q.pop( v ) );
 147                         }
 148                         else {
 149                             CPPUNIT_ASSERT( q.dequeue( v ));
 150                         }
 151
 152                         size_t nMin = nCount > q.quasi_factor() ? nCount - q.quasi_factor() : 0;
 153                         size_t nMax = nCount + q.quasi_factor();
 154                         CPPUNIT_CHECK_EX( nMin <= v.nVal && v.nVal <= nMax, nMin << " <= " << v.nVal << " <= " << nMax );
 155
 156                         ++nCount;
 157                         CPPUNIT_CHECK( misc::check_size( q, c_nItemCount - nCount ));
 158                     }
 159                     CPPUNIT_CHECK( nCount == c_nItemCount );
 160                     CPPUNIT_CHECK( q.empty() );
 161                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 162                 }
 163
 164                 // pop from empty queue
 165                 {
 166                     value_type v;
 167                     v.nVal = c_nItemCount + 1;
 168                     CPPUNIT_CHECK( q.empty() );
 169                     CPPUNIT_ASSERT( !q.pop( v ));
 170                     CPPUNIT_CHECK( q.empty() );
 171                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 172                     CPPUNIT_CHECK( v.nVal == c_nItemCount + 1 );
 173                 }
 174
 175                 // clear
 176                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 177                     if ( i & 1 ) {
 178                         CPPUNIT_ASSERT( q.push(item(i)) );
 179                     }
 180                     else {
 181                         CPPUNIT_ASSERT( q.enqueue(item(i)) );
 182                     }
 183                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
 184                     CPPUNIT_CHECK( !q.empty() );
 185                 }
 186
 187                 q.clear();
 188                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 189                 CPPUNIT_CHECK( q.empty() );
 190             }
 191         }
 192
 193         void SegmQueue_HP();
 194         void SegmQueue_HP_mutex();
 195         void SegmQueue_HP_shuffle();
 196         void SegmQueue_HP_stat();
 197         void SegmQueue_HP_cacheline_padding();
 198         void SegmQueue_HP_mutex_cacheline_padding();
 199         void SegmQueue_HP_shuffle_cacheline_padding();
 200         void SegmQueue_HP_stat_cacheline_padding();
 201
 202         void SegmQueue_DHP();
 203         void SegmQueue_DHP_mutex();
 204         void SegmQueue_DHP_shuffle();
 205         void SegmQueue_DHP_stat();
 206         void SegmQueue_DHP_cacheline_padding();
 207         void SegmQueue_DHP_mutex_cacheline_padding();
 208         void SegmQueue_DHP_shuffle_cacheline_padding();
 209         void SegmQueue_DHP_stat_cacheline_padding();
 210
 211         CPPUNIT_TEST_SUITE(HdrSegmentedQueue)
 212             CPPUNIT_TEST( SegmQueue_HP )
 213             CPPUNIT_TEST( SegmQueue_HP_mutex )
 214             CPPUNIT_TEST( SegmQueue_HP_shuffle )
 215             CPPUNIT_TEST( SegmQueue_HP_stat )
 216             CPPUNIT_TEST( SegmQueue_HP_cacheline_padding )
 217             CPPUNIT_TEST( SegmQueue_HP_mutex_cacheline_padding )
 218             CPPUNIT_TEST( SegmQueue_HP_shuffle_cacheline_padding )
 219             CPPUNIT_TEST( SegmQueue_HP_stat_cacheline_padding )
 220
 221             CPPUNIT_TEST( SegmQueue_DHP )
 222             CPPUNIT_TEST( SegmQueue_DHP_mutex )
 223             CPPUNIT_TEST( SegmQueue_DHP_shuffle )
 224             CPPUNIT_TEST( SegmQueue_DHP_stat )
 225             CPPUNIT_TEST( SegmQueue_DHP_cacheline_padding )
 226             CPPUNIT_TEST( SegmQueue_DHP_mutex_cacheline_padding )
 227             CPPUNIT_TEST( SegmQueue_DHP_shuffle_cacheline_padding )
 228             CPPUNIT_TEST( SegmQueue_DHP_stat_cacheline_padding )
 229             CPPUNIT_TEST_SUITE_END()
 230
 231     };
 232 } // namespace queue
 233
 234 #endif //#ifndef __CDSHDR_QUEUE_SEGMENTED_QUEUE_H