test/unit/pqueue/intrusive_mspqueue.cpp

   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 #include "test_data.h"
  32 #include <cds/intrusive/mspriority_queue.h>
  33
  34 namespace {
  35
  36     struct disposer {
  37         size_t   m_nCallCount;
  38
  39         disposer()
  40             : m_nCallCount( 0 )
  41         {}
  42
  43         template <typename T>
  44         void operator()( T& )
  45         {
  46             ++m_nCallCount;
  47         }
  48     };
  49
  50     class IntrusiveMSPQueue : public cds_test::PQueueTest
  51     {
  52         typedef cds_test::PQueueTest base_class;
  53     protected:
  54         template <class PQueue>
  55         void test( PQueue& pq )
  56         {
  57             data_array<value_type> arr( pq.capacity() );
  58             value_type * pFirst = arr.begin();
  59             value_type * pLast = arr.end();
  60
  61             ASSERT_TRUE( pq.empty() );
  62             ASSERT_FALSE( pq.full() );
  63             ASSERT_EQ( pq.size(), 0 );
  64             ASSERT_EQ( pq.capacity(), base_class::c_nCapacity - 1 );
  65
  66             size_t nSize = 0;
  67
  68             // Push test
  69             for ( value_type * p = pFirst; p < pLast; ++p ) {
  70                 ASSERT_TRUE( pq.push( *p ) );
  71                 ASSERT_FALSE( pq.empty() );
  72                 ASSERT_EQ( pq.size(), ++nSize );
  73             }
  74
  75             ASSERT_TRUE( pq.full() );
  76             ASSERT_EQ( pq.size(), pq.capacity() );
  77
  78             // The queue is full
  79             {
  80                 value_type k( base_class::c_nMinValue + key_type( base_class::c_nCapacity ));
  81                 ASSERT_FALSE( pq.push( k ) );
  82                 ASSERT_TRUE( pq.full() );
  83                 ASSERT_EQ( pq.size(), pq.capacity() );
  84             }
  85
  86             // Pop test
  87             key_type nPrev = base_class::c_nMinValue + key_type( pq.capacity() ) - 1;
  88             value_type * p = pq.pop();
  89             ASSERT_TRUE( p != nullptr );
  90             EXPECT_EQ( p->k, nPrev );
  91
  92             ASSERT_EQ( pq.size(), pq.capacity() - 1 );
  93             ASSERT_FALSE( pq.full() );
  94             ASSERT_FALSE( pq.empty() );
  95
  96             nSize = pq.size();
  97             while ( pq.size() > 1 ) {
  98                 p = pq.pop();
  99                 ASSERT_TRUE( p != nullptr );
 100                 EXPECT_EQ( p->k, nPrev - 1 );
 101                 nPrev = p->k;
 102                 --nSize;
 103                 ASSERT_EQ( pq.size(), nSize );
 104             }
 105
 106             ASSERT_FALSE( pq.full() );
 107             ASSERT_FALSE( pq.empty() );
 108             ASSERT_EQ( pq.size(), 1 );
 109
 110             p = pq.pop();
 111             ASSERT_TRUE( p != nullptr );
 112             EXPECT_EQ( p->k, base_class::c_nMinValue );
 113
 114             ASSERT_FALSE( pq.full() );
 115             ASSERT_TRUE( pq.empty() );
 116             ASSERT_EQ( pq.size(), 0 );
 117
 118             // Clear test
 119             for ( value_type * p = pFirst; p < pLast; ++p ) {
 120                 ASSERT_TRUE( pq.push( *p ) );
 121             }
 122             EXPECT_FALSE( pq.empty() );
 123             EXPECT_TRUE( pq.full() );
 124             EXPECT_EQ( pq.size(), pq.capacity() );
 125             pq.clear();
 126             EXPECT_TRUE( pq.empty() );
 127             EXPECT_FALSE( pq.full() );
 128             EXPECT_EQ( pq.size(), 0 );
 129
 130             // clear_with test
 131             for ( value_type * p = pFirst; p < pLast; ++p ) {
 132                 ASSERT_TRUE( pq.push( *p ) );
 133             }
 134             ASSERT_FALSE( pq.empty() );
 135             ASSERT_TRUE( pq.full() );
 136             ASSERT_EQ( pq.size(), pq.capacity() );
 137
 138             {
 139                 disposer disp;
 140                 pq.clear_with( std::ref( disp ) );
 141                 ASSERT_TRUE( pq.empty() );
 142                 ASSERT_FALSE( pq.full() );
 143                 ASSERT_EQ( pq.size(), 0 );
 144                 ASSERT_EQ( disp.m_nCallCount, pq.capacity() );
 145             }
 146         }
 147     };
 148
 149     typedef cds::opt::v::dynamic_buffer< char > dyn_buffer_type;
 150     typedef cds::opt::v::static_buffer< char, IntrusiveMSPQueue::c_nCapacity > static_buffer_type;
 151
 152     TEST_F( IntrusiveMSPQueue, dynamic )
 153     {
 154         struct traits : public cds::intrusive::mspriority_queue::traits
 155         {
 156             typedef dyn_buffer_type buffer;
 157         };
 158         typedef cds::intrusive::MSPriorityQueue< value_type, traits > pqueue;
 159
 160         pqueue pq( c_nCapacity );
 161         test( pq );
 162     }
 163
 164     TEST_F( IntrusiveMSPQueue, dynamic_cmp )
 165     {
 166         struct traits : public cds::intrusive::mspriority_queue::traits
 167         {
 168             typedef dyn_buffer_type buffer;
 169             typedef IntrusiveMSPQueue::compare compare;
 170         };
 171         typedef cds::intrusive::MSPriorityQueue< value_type, traits > pqueue;
 172
 173         pqueue pq( c_nCapacity );
 174         test( pq );
 175     }
 176
 177     TEST_F( IntrusiveMSPQueue, dynamic_less )
 178     {
 179         typedef cds::intrusive::MSPriorityQueue< value_type,
 180             cds::intrusive::mspriority_queue::make_traits<
 181                 cds::opt::buffer< dyn_buffer_type >
 182                 ,cds::opt::less< std::less<value_type> >
 183             >::type
 184         > pqueue;
 185
 186         pqueue pq( c_nCapacity );
 187         test( pq );
 188     }
 189
 190     TEST_F( IntrusiveMSPQueue, dynamic_cmp_less )
 191     {
 192         typedef cds::intrusive::MSPriorityQueue< value_type,
 193             cds::intrusive::mspriority_queue::make_traits<
 194                 cds::opt::buffer< dyn_buffer_type >
 195                 ,cds::opt::less< std::less<value_type> >
 196                 ,cds::opt::compare< IntrusiveMSPQueue::compare >
 197             >::type
 198         > pqueue;
 199
 200         pqueue pq( c_nCapacity );
 201         test( pq );
 202     }
 203
 204     TEST_F( IntrusiveMSPQueue, dynamic_mutex )
 205     {
 206         struct traits : public cds::intrusive::mspriority_queue::traits
 207         {
 208             typedef dyn_buffer_type buffer;
 209             typedef IntrusiveMSPQueue::compare compare;
 210             typedef std::mutex lock_type;
 211         };
 212         typedef cds::intrusive::MSPriorityQueue< value_type, traits > pqueue;
 213
 214         pqueue pq( c_nCapacity );
 215         test( pq );
 216     }
 217
 218     TEST_F( IntrusiveMSPQueue, stat )
 219     {
 220         struct traits : public cds::intrusive::mspriority_queue::traits
 221         {
 222             typedef static_buffer_type buffer;
 223         };
 224         typedef cds::intrusive::MSPriorityQueue< value_type, traits > pqueue;
 225
 226         std::unique_ptr<pqueue> pq( new pqueue(0));
 227         test( *pq );
 228     }
 229
 230     TEST_F( IntrusiveMSPQueue, stat_cmp )
 231     {
 232         typedef cds::intrusive::MSPriorityQueue< value_type,
 233             cds::intrusive::mspriority_queue::make_traits<
 234                 cds::opt::buffer< static_buffer_type >
 235                 ,cds::opt::compare< compare >
 236             >::type
 237         > pqueue;
 238
 239         std::unique_ptr<pqueue> pq( new pqueue( 0 ) );
 240         test( *pq );
 241     }
 242
 243     TEST_F( IntrusiveMSPQueue, stat_less )
 244     {
 245         typedef cds::intrusive::MSPriorityQueue< value_type,
 246             cds::intrusive::mspriority_queue::make_traits<
 247                 cds::opt::buffer< static_buffer_type >
 248                 ,cds::opt::less< less >
 249             >::type
 250         > pqueue;
 251
 252         std::unique_ptr<pqueue> pq( new pqueue( 0 ) );
 253         test( *pq );
 254     }
 255
 256     TEST_F( IntrusiveMSPQueue, stat_mutex )
 257     {
 258         struct traits : public cds::intrusive::mspriority_queue::traits
 259         {
 260             typedef static_buffer_type buffer;
 261             typedef IntrusiveMSPQueue::compare compare;
 262             typedef std::mutex lock_type;
 263         };
 264         typedef cds::intrusive::MSPriorityQueue< value_type, traits > pqueue;
 265
 266         std::unique_ptr<pqueue> pq( new pqueue( 0 ) );
 267         test( *pq );
 268     }
 269
 270 } // namespace