test/unit/queue/test_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 CDSUNIT_QUEUE_TEST_SEGMENTED_QUEUE_H
  32 #define CDSUNIT_QUEUE_TEST_SEGMENTED_QUEUE_H
  33
  34 #include <cds_test/check_size.h>
  35
  36 namespace cds_test {
  37
  38     class segmented_queue : public ::testing::Test
  39     {
  40     protected:
  41         template <typename Queue>
  42         void test( Queue& q )
  43         {
  44             typedef typename Queue::value_type value_type;
  45             value_type it;
  46
  47             const size_t nSize = 100;
  48
  49             ASSERT_TRUE( q.empty());
  50             ASSERT_CONTAINER_SIZE( q, 0 );
  51
  52             // enqueue/dequeue
  53             for ( size_t i = 0; i < nSize; ++i ) {
  54                 it = static_cast<value_type>(i);
  55                 ASSERT_TRUE( q.enqueue( it ));
  56                 ASSERT_CONTAINER_SIZE( q, i + 1 );
  57             }
  58             ASSERT_FALSE( q.empty());
  59             ASSERT_CONTAINER_SIZE( q, nSize );
  60
  61             for ( size_t i = 0; i < nSize; ++i ) {
  62                 it = -1;
  63                 ASSERT_TRUE( q.dequeue( it ));
  64                 ASSERT_CONTAINER_SIZE( q, nSize - i - 1 );
  65
  66                 int nSegment = int( i / q.quasi_factor());
  67                 int nMin = nSegment * int( q.quasi_factor());
  68                 int nMax = nMin + int( q.quasi_factor()) - 1;
  69                 EXPECT_LE( nMin, it );
  70                 EXPECT_LE( it, nMax );
  71             }
  72             ASSERT_TRUE( q.empty());
  73             ASSERT_CONTAINER_SIZE( q, 0 );
  74
  75             // push/pop
  76             for ( size_t i = 0; i < nSize; ++i ) {
  77                 it = static_cast<value_type>(i);
  78                 ASSERT_TRUE( q.push( it ));
  79                 ASSERT_CONTAINER_SIZE( q, i + 1 );
  80             }
  81             ASSERT_FALSE( q.empty());
  82             ASSERT_CONTAINER_SIZE( q, nSize );
  83
  84             size_t nPushed = nSize;
  85             size_t nStartSegment = nPushed / q.quasi_factor();
  86             size_t nOffset = nPushed % q.quasi_factor();
  87             for ( size_t i = 0; i < nSize; ++i ) {
  88                 it = -1;
  89                 ASSERT_TRUE( q.pop( it ));
  90                 ASSERT_CONTAINER_SIZE( q, nSize - i - 1 );
  91
  92                 int nSegment = static_cast<int>((i + nPushed) / q.quasi_factor() - nStartSegment );
  93                 int nMin = nSegment * static_cast<int>( q.quasi_factor());
  94                 if ( nSegment )
  95                     nMin -= static_cast<int>( nOffset );
  96                 int nMax = nMin + static_cast<int>( q.quasi_factor()) - 1;
  97                 EXPECT_LE( nMin, it );
  98                 EXPECT_LE( it, nMax );
  99             }
 100             ASSERT_TRUE( q.empty());
 101             ASSERT_CONTAINER_SIZE( q, 0 );
 102
 103             // push/pop with lambda
 104             for ( size_t i = 0; i < nSize; ++i ) {
 105                 it = static_cast<value_type>(i);
 106                 EXPECT_NE( it, -1 );
 107                 auto f = [&it]( value_type& dest ) { dest = it; it = -1; };
 108                 if ( i & 1 )
 109                     ASSERT_TRUE( q.enqueue_with( f ));
 110                 else
 111                     ASSERT_TRUE( q.push_with( f ));
 112                 ASSERT_EQ( it, -1 );
 113                 ASSERT_CONTAINER_SIZE( q, i + 1 );
 114             }
 115             ASSERT_FALSE( q.empty());
 116             ASSERT_CONTAINER_SIZE( q, nSize );
 117
 118             nPushed += nSize;
 119             nStartSegment = nPushed / q.quasi_factor();
 120             nOffset = nPushed % q.quasi_factor();
 121             for ( size_t i = 0; i < nSize; ++i ) {
 122                 it = -1;
 123                 auto f = [&it]( value_type& src ) { it = src; src = -1; };
 124                 if ( i & 1 )
 125                     ASSERT_TRUE( q.pop_with( f ));
 126                 else
 127                     ASSERT_TRUE( q.dequeue_with( f ));
 128                 ASSERT_CONTAINER_SIZE( q, nSize - i - 1 );
 129
 130                 int nSegment = static_cast<int>((i + nPushed) / q.quasi_factor() - nStartSegment);
 131                 int nMin = nSegment * static_cast<int>(q.quasi_factor());
 132                 if ( nSegment )
 133                     nMin -= static_cast<int>(nOffset);
 134                 int nMax = nMin + static_cast<int>(q.quasi_factor()) - 1;
 135                 EXPECT_LE( nMin, it );
 136                 EXPECT_LE( it, nMax );
 137             }
 138             ASSERT_TRUE( q.empty());
 139             ASSERT_CONTAINER_SIZE( q, 0 );
 140
 141             // clear
 142             for ( size_t i = 0; i < nSize; ++i ) {
 143                 ASSERT_TRUE( q.push( static_cast<value_type>(i)) );
 144             }
 145             ASSERT_FALSE( q.empty());
 146             ASSERT_CONTAINER_SIZE( q, nSize );
 147
 148             q.clear();
 149             ASSERT_TRUE( q.empty());
 150             ASSERT_CONTAINER_SIZE( q, 0 );
 151
 152             // pop from empty queue
 153             it = nSize * 2;
 154             ASSERT_FALSE( q.pop( it ));
 155             ASSERT_EQ( it, static_cast<value_type>( nSize * 2 ));
 156             ASSERT_TRUE( q.empty());
 157             ASSERT_CONTAINER_SIZE( q, 0 );
 158
 159             ASSERT_FALSE( q.dequeue( it ));
 160             ASSERT_EQ( it, static_cast<value_type>( nSize * 2 ));
 161             ASSERT_TRUE( q.empty());
 162             ASSERT_CONTAINER_SIZE( q, 0 );
 163         }
 164
 165         template <class Queue>
 166         void test_string( Queue& q )
 167         {
 168             std::string str[3];
 169             str[0] = "one";
 170             str[1] = "two";
 171             str[2] = "three";
 172             const size_t nSize = sizeof( str ) / sizeof( str[0] );
 173
 174             // emplace
 175             for ( size_t i = 0; i < nSize; ++i ) {
 176                 ASSERT_TRUE( q.emplace( str[i].c_str()));
 177                 ASSERT_CONTAINER_SIZE( q, i + 1 );
 178             }
 179             ASSERT_FALSE( q.empty());
 180             ASSERT_CONTAINER_SIZE( q, nSize );
 181
 182             {
 183                 std::string s;
 184                 auto f = [&s]( std::string& src ) {
 185                     ASSERT_FALSE( src.empty());
 186                     s = std::move( src );
 187                     ASSERT_NE( s, src );
 188                 };
 189                 for ( size_t i = 0; i < nSize; ++i ) {
 190                     if ( i & 1 )
 191                         ASSERT_TRUE( q.pop_with( f ));
 192                     else
 193                         ASSERT_TRUE( q.dequeue_with( f ));
 194
 195                     ASSERT_CONTAINER_SIZE( q, nSize - i - 1 );
 196                     ASSERT_TRUE( s == str[0] || s == str[1] || s == str[2] );
 197                 }
 198             }
 199             ASSERT_TRUE( q.empty());
 200             ASSERT_CONTAINER_SIZE( q, 0 );
 201
 202
 203             // move push
 204             for ( size_t i = 0; i < nSize; ++i ) {
 205                 std::string s = str[i];
 206                 ASSERT_FALSE( s.empty());
 207                 if ( i & 1 )
 208                     ASSERT_TRUE( q.enqueue( std::move( s )));
 209                 else
 210                     ASSERT_TRUE( q.push( std::move( s )));
 211                 ASSERT_TRUE( s.empty());
 212                 ASSERT_CONTAINER_SIZE( q, i + 1 );
 213             }
 214             ASSERT_FALSE( q.empty());
 215             ASSERT_CONTAINER_SIZE( q, nSize );
 216
 217             for ( size_t i = 0; i < nSize; ++i ) {
 218                 std::string s;
 219                 ASSERT_TRUE( q.pop( s ));
 220                 ASSERT_CONTAINER_SIZE( q, nSize - i - 1 );
 221                 ASSERT_TRUE( s == str[0] || s == str[1] || s == str[2] );
 222             }
 223             ASSERT_TRUE( q.empty());
 224             ASSERT_CONTAINER_SIZE( q, 0 );
 225         }
 226
 227     };
 228
 229 } // namespace cds_test
 230
 231 #endif // CDSUNIT_QUEUE_TEST_SEGMENTED_QUEUE_H