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