test/unit/queue/test_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-2017
   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 CDSUNIT_QUEUE_TEST_INTRUSIVE_SEGMENTED_QUEUE_H
  32 #define CDSUNIT_QUEUE_TEST_INTRUSIVE_SEGMENTED_QUEUE_H
  33
  34 #include <cds_test/check_size.h>
  35
  36 namespace cds_test {
  37
  38     class intrusive_segmented_queue : public ::testing::Test
  39     {
  40     protected:
  41         struct item {
  42             int  nValue;
  43
  44             size_t  nDisposeCount;
  45             size_t  nDispose2Count;
  46
  47             item()
  48                 : nValue( 0 )
  49                 , nDisposeCount( 0 )
  50                 , nDispose2Count( 0 )
  51             {}
  52
  53             item( int nVal )
  54                 : nValue( nVal )
  55                 , nDisposeCount( 0 )
  56                 , nDispose2Count( 0 )
  57             {}
  58         };
  59
  60         struct big_item : public item
  61         {
  62             big_item()
  63             {}
  64
  65             big_item( int nVal )
  66                 : item( nVal )
  67             {}
  68
  69             int arr[80];
  70         };
  71
  72         struct Disposer
  73         {
  74             void operator()( item * p )
  75             {
  76                 ++p->nDisposeCount;
  77             }
  78         };
  79
  80         struct Disposer2
  81         {
  82             void operator()( item * p )
  83             {
  84                 ++p->nDispose2Count;
  85             }
  86         };
  87
  88         template <typename Queue, typename Data>
  89         void test( Queue& q, Data& val )
  90         {
  91             typedef typename Queue::value_type value_type;
  92             val.resize( 100 );
  93             for ( size_t i = 0; i < val.size(); ++i )
  94                 val[i].nValue = static_cast<int>( i );
  95
  96             ASSERT_TRUE( q.empty());
  97             ASSERT_CONTAINER_SIZE( q, 0u );
  98
  99             // push/enqueue
 100             for ( size_t i = 0; i < val.size(); ++i ) {
 101                 if ( i & 1 ) {
 102                     ASSERT_TRUE( q.push( val[i] ));
 103                 }
 104                 else {
 105                     ASSERT_TRUE( q.enqueue( val[i] ));
 106                 }
 107
 108                 ASSERT_CONTAINER_SIZE( q, i + 1 );
 109             }
 110             EXPECT_TRUE( !q.empty());
 111
 112             // pop/dequeue
 113             size_t nCount = 0;
 114             while ( !q.empty()) {
 115                 value_type * pVal;
 116                 if ( nCount & 1 )
 117                     pVal = q.pop();
 118                 else
 119                     pVal = q.dequeue();
 120
 121                 ASSERT_TRUE( pVal != nullptr );
 122
 123                 int nSegment = int( nCount / q.quasi_factor());
 124                 int nMin = nSegment * int( q.quasi_factor());
 125                 int nMax = nMin + int( q.quasi_factor()) - 1;
 126                 EXPECT_TRUE( nMin <= pVal->nValue && pVal->nValue <= nMax ) << nMin << " <= " << pVal->nValue << " <= " << nMax;
 127
 128                 ++nCount;
 129                 EXPECT_CONTAINER_SIZE( q, val.size() - nCount );
 130             }
 131             EXPECT_EQ( nCount, val.size());
 132             EXPECT_TRUE( q.empty());
 133             EXPECT_CONTAINER_SIZE( q, 0u );
 134
 135             // pop from empty queue
 136             ASSERT_TRUE( q.pop() == nullptr );
 137             EXPECT_TRUE( q.empty());
 138             EXPECT_CONTAINER_SIZE( q, 0u );
 139
 140             // check that Disposer has not been called
 141             Queue::gc::force_dispose();
 142             for ( size_t i = 0; i < val.size(); ++i ) {
 143                 EXPECT_EQ( val[i].nDisposeCount, 0u );
 144                 EXPECT_EQ( val[i].nDispose2Count, 0u );
 145             }
 146
 147             // clear
 148             for ( size_t i = 0; i < val.size(); ++i )
 149                 EXPECT_TRUE( q.push( val[i] ));
 150             EXPECT_CONTAINER_SIZE( q, val.size());
 151             EXPECT_TRUE( !q.empty());
 152
 153             q.clear();
 154             EXPECT_CONTAINER_SIZE( q, 0u );
 155             EXPECT_TRUE( q.empty());
 156
 157             // check if Disposer has been called
 158             Queue::gc::force_dispose();
 159             for ( size_t i = 0; i < val.size(); ++i ) {
 160                 EXPECT_EQ( val[i].nDisposeCount, 1u );
 161                 EXPECT_EQ( val[i].nDispose2Count, 0u );
 162             }
 163
 164             // clear_with
 165             for ( size_t i = 0; i < val.size(); ++i )
 166                 EXPECT_TRUE( q.push( val[i] ));
 167             EXPECT_CONTAINER_SIZE( q, val.size());
 168             EXPECT_TRUE( !q.empty());
 169
 170             q.clear_with( Disposer2());
 171             EXPECT_CONTAINER_SIZE( q, 0u );
 172             EXPECT_TRUE( q.empty());
 173
 174             // check if Disposer has been called
 175             Queue::gc::force_dispose();
 176             for ( size_t i = 0; i < val.size(); ++i ) {
 177                 EXPECT_EQ( val[i].nDisposeCount, 1u );
 178                 EXPECT_EQ( val[i].nDispose2Count, 1u );
 179             }
 180
 181             // check clear on destruct
 182             for ( size_t i = 0; i < val.size(); ++i )
 183                 EXPECT_TRUE( q.push( val[i] ));
 184             EXPECT_CONTAINER_SIZE( q, val.size());
 185             EXPECT_TRUE( !q.empty());
 186         }
 187     };
 188
 189 } // namespace cds_test
 190
 191 #endif // CDSUNIT_QUEUE_TEST_INTRUSIVE_SEGMENTED_QUEUE_H