tests/test-hdr/queue/hdr_intrusive_segmented_queue.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSTEST_HDR_INTRUSIVE_SEGMENTED_QUEUE_H
  32 #define CDSTEST_HDR_INTRUSIVE_SEGMENTED_QUEUE_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include <cds/intrusive/details/base.h>
  36 #include "size_check.h"
  37
  38 namespace queue {
  39
  40     class HdrIntrusiveSegmentedQueue : public CppUnitMini::TestCase
  41     {
  42         struct item {
  43             int  nValue;
  44
  45             size_t  nDisposeCount;
  46             size_t  nDispose2Count;
  47
  48             item()
  49                 : nValue( 0 )
  50                 , nDisposeCount( 0 )
  51                 , nDispose2Count( 0 )
  52             {}
  53
  54             item( int nVal )
  55                 : nValue( nVal )
  56                 , nDisposeCount( 0 )
  57                 , nDispose2Count( 0 )
  58             {}
  59         };
  60
  61         struct big_item : public item
  62         {
  63             big_item()
  64             {}
  65
  66             big_item( int nVal )
  67                 : item( nVal )
  68             {}
  69
  70             int arr[80];
  71         };
  72
  73         struct Disposer
  74         {
  75             void operator()( item * p )
  76             {
  77                 ++p->nDisposeCount;
  78             }
  79         };
  80
  81         struct Disposer2
  82         {
  83             void operator()( item * p )
  84             {
  85                 ++p->nDispose2Count;
  86             }
  87         };
  88
  89         template <typename Queue>
  90         void test()
  91         {
  92             for ( size_t nQuasiFactor = 2; nQuasiFactor <= 256; ++nQuasiFactor ) {
  93                 CPPUNIT_MSG( "QuasiFactor=" << nQuasiFactor << "..." );
  94                 test_qf<Queue>( nQuasiFactor );
  95             }
  96         }
  97
  98         template <typename Queue>
  99         void test_qf( size_t nQuasiFactor )
 100         {
 101             typedef typename Queue::value_type value_type;
 102
 103             static size_t const c_nItemCount = 1000;
 104             value_type val[c_nItemCount];
 105             for ( int i = 0; i < static_cast<int>(sizeof(val)/sizeof(val[0])); ++i )
 106                 val[i].nValue = i;
 107
 108             {
 109                 Queue q( nQuasiFactor );
 110                 CPPUNIT_CHECK( q.quasi_factor() == cds::beans::ceil2(nQuasiFactor) );
 111                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 112                 CPPUNIT_CHECK( q.empty() );
 113
 114                 // push/enqueue
 115                 for ( size_t i = 0; i < sizeof(val)/sizeof(val[0]); ++i ) {
 116                     if ( i & 1 ) {
 117                         CPPUNIT_ASSERT( q.push( val[i] ));
 118                     }
 119                     else {
 120                         CPPUNIT_ASSERT( q.enqueue( val[i] ));
 121                     }
 122
 123                     CPPUNIT_CHECK( misc::check_size( q, i + 1 ));
 124                 }
 125                 CPPUNIT_CHECK( !q.empty() );
 126
 127                 // pop/dequeue
 128                 size_t nCount = 0;
 129                 while ( !q.empty() ) {
 130                     value_type * pVal;
 131                     if ( nCount & 1 )
 132                         pVal = q.pop();
 133                     else
 134                         pVal = q.dequeue();
 135
 136                     CPPUNIT_ASSERT( pVal != nullptr );
 137
 138                     int nSegment = int( nCount / q.quasi_factor() );
 139                     int nMin = nSegment * int(q.quasi_factor());
 140                     int nMax = nMin + int(q.quasi_factor()) - 1;
 141                     CPPUNIT_CHECK_EX( nMin <= pVal->nValue && pVal->nValue <= nMax, nMin << " <= " << pVal->nValue << " <= " << nMax );
 142
 143                     ++nCount;
 144                     CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) - nCount ));
 145                 }
 146                 CPPUNIT_CHECK( nCount == sizeof(val)/sizeof(val[0]) );
 147                 CPPUNIT_CHECK( q.empty() );
 148                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 149
 150                 // pop from empty queue
 151                 CPPUNIT_ASSERT( q.pop() == nullptr );
 152                 CPPUNIT_CHECK( q.empty() );
 153                 CPPUNIT_CHECK( misc::check_size( q, 0 ));
 154
 155                 // check if Disposer has not been called
 156                 Queue::gc::force_dispose();
 157                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0]) ); ++i ) {
 158                     CPPUNIT_CHECK( val[i].nDisposeCount == 0 );
 159                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 160                 }
 161
 162                 // Manually dispose the items
 163                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 164                     Queue::gc::template retire<Disposer>( &(val[i]) );
 165
 166                 // check if Disposer has been called
 167                 Queue::gc::force_dispose();
 168                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 169                     CPPUNIT_CHECK( val[i].nDisposeCount == 1 );
 170                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 171                 }
 172
 173
 174                 // clear
 175                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 176                     CPPUNIT_CHECK( q.push( val[i] ) );
 177                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 178                 CPPUNIT_CHECK( !q.empty() );
 179
 180                 q.clear();
 181                 CPPUNIT_CHECK( misc::check_size( q, 0));
 182                 CPPUNIT_CHECK( q.empty() );
 183
 184                 // check if Disposer has been called
 185                 Queue::gc::force_dispose();
 186                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 187                     CPPUNIT_CHECK( val[i].nDisposeCount == 2 );
 188                     CPPUNIT_CHECK( val[i].nDispose2Count == 0 );
 189                 }
 190
 191                 // clear_with
 192                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 193                     CPPUNIT_CHECK( q.push( val[i] ) );
 194                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 195                 CPPUNIT_CHECK( !q.empty() );
 196
 197                 q.clear_with( Disposer2() );
 198                 CPPUNIT_CHECK( misc::check_size( q, 0));
 199                 CPPUNIT_CHECK( q.empty() );
 200
 201                 // check if Disposer has been called
 202                 Queue::gc::force_dispose();
 203                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 204                     CPPUNIT_CHECK( val[i].nDisposeCount == 2 );
 205                     CPPUNIT_CHECK( val[i].nDispose2Count == 1 );
 206                 }
 207
 208                 // check clear on destruct
 209                 for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i )
 210                     CPPUNIT_CHECK( q.push( val[i] ) );
 211                 CPPUNIT_CHECK( misc::check_size( q, sizeof(val)/sizeof(val[0]) ));
 212                 CPPUNIT_CHECK( !q.empty() );
 213             }
 214
 215             // check if Disposer has been called
 216             Queue::gc::force_dispose();
 217             for ( int i = 0; i < static_cast<int>( sizeof(val)/sizeof(val[0])); ++i ) {
 218                 CPPUNIT_CHECK( val[i].nDisposeCount == 3 );
 219                 CPPUNIT_CHECK( val[i].nDispose2Count == 1 );
 220             }
 221         }
 222
 223         void SegmQueue_HP();
 224         void SegmQueue_HP_mutex();
 225         void SegmQueue_HP_shuffle();
 226         void SegmQueue_HP_stat();
 227         void SegmQueue_HP_cacheline_padding();
 228         void SegmQueue_HP_mutex_cacheline_padding();
 229         void SegmQueue_HP_shuffle_cacheline_padding();
 230         void SegmQueue_HP_stat_cacheline_padding();
 231         void SegmQueue_HP_256_padding();
 232         void SegmQueue_HP_mutex_256_padding();
 233         void SegmQueue_HP_shuffle_256_padding();
 234         void SegmQueue_HP_stat_256_padding();
 235         void SegmQueue_HP_cacheline_padding_bigdata();
 236         void SegmQueue_HP_mutex_cacheline_padding_bigdata();
 237         void SegmQueue_HP_shuffle_cacheline_padding_bigdata();
 238         void SegmQueue_HP_stat_cacheline_padding_bigdata();
 239
 240         void SegmQueue_DHP();
 241         void SegmQueue_DHP_mutex();
 242         void SegmQueue_DHP_shuffle();
 243         void SegmQueue_DHP_stat();
 244         void SegmQueue_DHP_cacheline_padding();
 245         void SegmQueue_DHP_mutex_cacheline_padding();
 246         void SegmQueue_DHP_shuffle_cacheline_padding();
 247         void SegmQueue_DHP_stat_cacheline_padding();
 248         void SegmQueue_DHP_256_padding();
 249         void SegmQueue_DHP_mutex_256_padding();
 250         void SegmQueue_DHP_shuffle_256_padding();
 251         void SegmQueue_DHP_stat_256_padding();
 252         void SegmQueue_DHP_cacheline_padding_bigdata();
 253         void SegmQueue_DHP_mutex_cacheline_padding_bigdata();
 254         void SegmQueue_DHP_shuffle_cacheline_padding_bigdata();
 255         void SegmQueue_DHP_stat_cacheline_padding_bigdata();
 256
 257         CPPUNIT_TEST_SUITE(HdrIntrusiveSegmentedQueue)
 258             CPPUNIT_TEST( SegmQueue_HP )
 259             CPPUNIT_TEST( SegmQueue_HP_mutex )
 260             CPPUNIT_TEST( SegmQueue_HP_shuffle )
 261             CPPUNIT_TEST( SegmQueue_HP_stat )
 262             CPPUNIT_TEST( SegmQueue_HP_cacheline_padding )
 263             CPPUNIT_TEST( SegmQueue_HP_mutex_cacheline_padding )
 264             CPPUNIT_TEST( SegmQueue_HP_shuffle_cacheline_padding )
 265             CPPUNIT_TEST( SegmQueue_HP_stat_cacheline_padding )
 266             CPPUNIT_TEST( SegmQueue_HP_256_padding )
 267             CPPUNIT_TEST( SegmQueue_HP_mutex_256_padding )
 268             CPPUNIT_TEST( SegmQueue_HP_shuffle_256_padding )
 269             CPPUNIT_TEST( SegmQueue_HP_stat_256_padding )
 270             CPPUNIT_TEST( SegmQueue_HP_cacheline_padding_bigdata )
 271             CPPUNIT_TEST( SegmQueue_HP_mutex_cacheline_padding_bigdata )
 272             CPPUNIT_TEST( SegmQueue_HP_shuffle_cacheline_padding_bigdata )
 273             CPPUNIT_TEST( SegmQueue_HP_stat_cacheline_padding_bigdata )
 274
 275             CPPUNIT_TEST( SegmQueue_DHP )
 276             CPPUNIT_TEST( SegmQueue_DHP_mutex )
 277             CPPUNIT_TEST( SegmQueue_DHP_shuffle )
 278             CPPUNIT_TEST( SegmQueue_DHP_stat )
 279             CPPUNIT_TEST( SegmQueue_DHP_cacheline_padding )
 280             CPPUNIT_TEST( SegmQueue_DHP_mutex_cacheline_padding )
 281             CPPUNIT_TEST( SegmQueue_DHP_shuffle_cacheline_padding )
 282             CPPUNIT_TEST( SegmQueue_DHP_stat_cacheline_padding )
 283             CPPUNIT_TEST( SegmQueue_DHP_256_padding )
 284             CPPUNIT_TEST( SegmQueue_DHP_mutex_256_padding )
 285             CPPUNIT_TEST( SegmQueue_DHP_shuffle_256_padding )
 286             CPPUNIT_TEST( SegmQueue_DHP_stat_256_padding )
 287             CPPUNIT_TEST( SegmQueue_DHP_cacheline_padding_bigdata )
 288             CPPUNIT_TEST( SegmQueue_DHP_mutex_cacheline_padding_bigdata )
 289             CPPUNIT_TEST( SegmQueue_DHP_shuffle_cacheline_padding_bigdata )
 290             CPPUNIT_TEST( SegmQueue_DHP_stat_cacheline_padding_bigdata )
 291         CPPUNIT_TEST_SUITE_END()
 292     };
 293
 294 } // namespace queue
 295
 296 #endif // CDSTEST_HDR_INTRUSIVE_SEGMENTED_QUEUE_H