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/base.h>
   8 #include <cds/ref.h>
   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, cds::ref(pf) ));
 128                         }
 129                         else {
 130                             CPPUNIT_ASSERT( q.dequeue( v, cds::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 #       ifdef CDS_EMPLACE_SUPPORT
 150                 {
 151                     size_t nMajor = 0;
 152                     size_t nMinor = 0;
 153                     for ( size_t i = 0; i < c_nItemCount; ++i ) {
 154                         CPPUNIT_CHECK( q.emplace( nMajor, nMinor ));
 155                         if ( nMinor  == 15 ) {
 156                             ++nMajor;
 157                             nMinor = 0;
 158                         }
 159                         else
 160                             ++nMinor;
 161                         CPPUNIT_CHECK( !q.empty() );
 162                     }
 163                     CPPUNIT_CHECK( misc::check_size( q, c_nItemCount ));
 164
 165                     nCount = 0;
 166                     while ( !q.empty() ) {
 167                         value_type v;
 168                         if ( nCount & 1 ) {
 169                             CPPUNIT_ASSERT( q.pop( v ) );
 170                         }
 171                         else {
 172                             CPPUNIT_ASSERT( q.dequeue( v ));
 173                         }
 174
 175                         size_t nMin = nCount > q.quasi_factor() ? nCount - q.quasi_factor() : 0;
 176                         size_t nMax = nCount + q.quasi_factor();
 177                         CPPUNIT_CHECK_EX( nMin <= v.nVal && v.nVal <= nMax, nMin << " <= " << v.nVal << " <= " << nMax );
 178
 179                         ++nCount;
 180                         CPPUNIT_CHECK( misc::check_size( q, c_nItemCount - nCount ));
 181                     }
 182                     CPPUNIT_CHECK( nCount == c_nItemCount );
 183                     CPPUNIT_CHECK( q.empty() );
 184                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 185                 }
 186 #       endif
 187
 188                 // pop from empty queue
 189                 {
 190                     value_type v;
 191                     v.nVal = c_nItemCount + 1;
 192                     CPPUNIT_CHECK( q.empty() );
 193                     CPPUNIT_ASSERT( !q.pop( v ));
 194                     CPPUNIT_CHECK( q.empty() );
 195                     CPPUNIT_CHECK( misc::check_size( q, 0 ));
 196                     CPPUNIT_CHECK( v.nVal == c_nItemCount + 1 );
 197                 }
 198
 199                 // clear
 200                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 201                     if ( i & 1 ) {
 202                         CPPUNIT_ASSERT( q.push(item(i)) );
 203                     }
 204                     else {
 205                         CPPUNIT_ASSERT( q.enqueue(item(i)) );
 206                     }
 207                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
 208                     CPPUNIT_CHECK( !q.empty() );
 209                 }
 210
 211                 q.clear();
 212                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 213                 CPPUNIT_CHECK( q.empty() );
 214             }
 215         }
 216
 217         void SegmQueue_HP();
 218         void SegmQueue_HP_mutex();
 219         void SegmQueue_HP_shuffle();
 220         void SegmQueue_HP_stat();
 221
 222         void SegmQueue_PTB();
 223         void SegmQueue_PTB_mutex();
 224         void SegmQueue_PTB_shuffle();
 225         void SegmQueue_PTB_stat();
 226
 227         CPPUNIT_TEST_SUITE(HdrSegmentedQueue)
 228             CPPUNIT_TEST( SegmQueue_HP )
 229             CPPUNIT_TEST( SegmQueue_HP_mutex )
 230             CPPUNIT_TEST( SegmQueue_HP_shuffle )
 231             CPPUNIT_TEST( SegmQueue_HP_stat )
 232
 233             CPPUNIT_TEST( SegmQueue_PTB )
 234             CPPUNIT_TEST( SegmQueue_PTB_mutex )
 235             CPPUNIT_TEST( SegmQueue_PTB_shuffle )
 236             CPPUNIT_TEST( SegmQueue_PTB_stat )
 237         CPPUNIT_TEST_SUITE_END()
 238
 239     };
 240 } // namespace queue
 241
 242 #endif //#ifndef __CDSHDR_QUEUE_SEGMENTED_QUEUE_H