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                     while ( !q.empty() ) {
 103                         if ( nCount & 1 ) {
 104                             CPPUNIT_ASSERT( q.pop_with( [&v, &nCount]( item& src ) {v.nVal = src.nVal; ++nCount; } ));
 105                         }
 106                         else {
 107                             CPPUNIT_ASSERT( q.dequeue_with( [&v, &nCount]( item& src ) {v.nVal = src.nVal; ++nCount; } ));
 108                         }
 109
 110                         // It is possible c_nItemCount % quasi_factor() != 0
 111                         // In this case the segment cannot be calculated here
 112                         size_t nMin = nCount > q.quasi_factor() ? nCount - q.quasi_factor() : 0;
 113                         size_t nMax = nCount + q.quasi_factor();
 114                         CPPUNIT_CHECK_EX( nMin <= v.nVal && v.nVal <= nMax, nMin << " <= " << v.nVal << " <= " << nMax );
 115
 116                         ++nCount;
 117                         CPPUNIT_CHECK( pf.nCount == nCount );
 118                         CPPUNIT_CHECK( misc::check_size( q, c_nItemCount - nCount ));
 119                     }
 120                     CPPUNIT_CHECK( nCount == c_nItemCount );
 121                     CPPUNIT_CHECK( q.empty() );
 122                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 123                 }
 124
 125                 //emplace
 126                 {
 127                     size_t nMajor = 0;
 128                     size_t nMinor = 0;
 129                     for ( size_t i = 0; i < c_nItemCount; ++i ) {
 130                         CPPUNIT_CHECK( q.emplace( nMajor, nMinor ));
 131                         if ( nMinor  == 15 ) {
 132                             ++nMajor;
 133                             nMinor = 0;
 134                         }
 135                         else
 136                             ++nMinor;
 137                         CPPUNIT_CHECK( !q.empty() );
 138                     }
 139                     CPPUNIT_CHECK( misc::check_size( q, c_nItemCount ));
 140
 141                     nCount = 0;
 142                     while ( !q.empty() ) {
 143                         value_type v;
 144                         if ( nCount & 1 ) {
 145                             CPPUNIT_ASSERT( q.pop( v ) );
 146                         }
 147                         else {
 148                             CPPUNIT_ASSERT( q.dequeue( v ));
 149                         }
 150
 151                         size_t nMin = nCount > q.quasi_factor() ? nCount - q.quasi_factor() : 0;
 152                         size_t nMax = nCount + q.quasi_factor();
 153                         CPPUNIT_CHECK_EX( nMin <= v.nVal && v.nVal <= nMax, nMin << " <= " << v.nVal << " <= " << nMax );
 154
 155                         ++nCount;
 156                         CPPUNIT_CHECK( misc::check_size( q, c_nItemCount - nCount ));
 157                     }
 158                     CPPUNIT_CHECK( nCount == c_nItemCount );
 159                     CPPUNIT_CHECK( q.empty() );
 160                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 161                 }
 162
 163                 // pop from empty queue
 164                 {
 165                     value_type v;
 166                     v.nVal = c_nItemCount + 1;
 167                     CPPUNIT_CHECK( q.empty() );
 168                     CPPUNIT_ASSERT( !q.pop( v ));
 169                     CPPUNIT_CHECK( q.empty() );
 170                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 171                     CPPUNIT_CHECK( v.nVal == c_nItemCount + 1 );
 172                 }
 173
 174                 // clear
 175                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 176                     if ( i & 1 ) {
 177                         CPPUNIT_ASSERT( q.push(item(i)) );
 178                     }
 179                     else {
 180                         CPPUNIT_ASSERT( q.enqueue(item(i)) );
 181                     }
 182                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
 183                     CPPUNIT_CHECK( !q.empty() );
 184                 }
 185
 186                 q.clear();
 187                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 188                 CPPUNIT_CHECK( q.empty() );
 189             }
 190         }
 191
 192         void SegmQueue_HP();
 193         void SegmQueue_HP_mutex();
 194         void SegmQueue_HP_shuffle();
 195         void SegmQueue_HP_stat();
 196
 197         void SegmQueue_DHP();
 198         void SegmQueue_DHP_mutex();
 199         void SegmQueue_DHP_shuffle();
 200         void SegmQueue_DHP_stat();
 201
 202         CPPUNIT_TEST_SUITE(HdrSegmentedQueue)
 203             CPPUNIT_TEST( SegmQueue_HP )
 204             CPPUNIT_TEST( SegmQueue_HP_mutex )
 205             CPPUNIT_TEST( SegmQueue_HP_shuffle )
 206             CPPUNIT_TEST( SegmQueue_HP_stat )
 207
 208             CPPUNIT_TEST( SegmQueue_DHP )
 209             CPPUNIT_TEST( SegmQueue_DHP_mutex )
 210             CPPUNIT_TEST( SegmQueue_DHP_shuffle )
 211             CPPUNIT_TEST( SegmQueue_DHP_stat )
 212         CPPUNIT_TEST_SUITE_END()
 213
 214     };
 215 } // namespace queue
 216
 217 #endif //#ifndef __CDSHDR_QUEUE_SEGMENTED_QUEUE_H