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