test/unit/pqueue/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/container/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 MSPQueue : 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 = pFirst + pq.capacity();
  60
  61             ASSERT_TRUE( pq.empty() );
  62             ASSERT_EQ( pq.size(), 0 );
  63             ASSERT_EQ( pq.capacity(), base_class::c_nCapacity - 1 );
  64
  65             size_t nSize = 0;
  66
  67             // Push test
  68             for ( value_type * p = pFirst; p < pLast; ++p ) {
  69                 switch ( pq.size() & 3 ) {
  70                 case 0:
  71                     ASSERT_TRUE( pq.push_with( [p]( value_type& dest ) { dest = *p; } ) );
  72                     break;
  73                 case 1:
  74                     ASSERT_TRUE( pq.emplace( p->k, p->v ) );
  75                     break;
  76                 case 2:
  77                     ASSERT_TRUE( pq.emplace( std::make_pair( p->k, p->v ) ) );
  78                     break;
  79                 default:
  80                     ASSERT_TRUE( pq.push( *p ) );
  81                 }
  82                 ASSERT_TRUE( !pq.empty() );
  83                 ASSERT_TRUE( pq.size() == ++nSize );
  84             }
  85
  86             ASSERT_TRUE( pq.full() );
  87             ASSERT_EQ( pq.size(), pq.capacity() );
  88
  89             // The queue is full
  90             key_type k = base_class::c_nMinValue + key_type( base_class::c_nCapacity );
  91             ASSERT_TRUE( !pq.push( k ) );
  92             ASSERT_TRUE( pq.full() );
  93             ASSERT_EQ( pq.size(), pq.capacity() );
  94
  95             // Pop test
  96             key_type nPrev = base_class::c_nMinValue + key_type( pq.capacity() ) - 1;
  97             value_type kv( 0 );
  98             key_type   key;
  99             ASSERT_TRUE( pq.pop( kv ) );
 100             EXPECT_EQ( kv.k, nPrev );
 101
 102             ASSERT_EQ( pq.size(), pq.capacity() - 1 );
 103             ASSERT_TRUE( !pq.full() );
 104             ASSERT_TRUE( !pq.empty() );
 105
 106             nSize = pq.size();
 107             while ( pq.size() > 1 ) {
 108                 if ( pq.size() & 1 ) {
 109                     ASSERT_TRUE( pq.pop( kv ) );
 110                     EXPECT_EQ( kv.k, nPrev - 1 );
 111                     nPrev = kv.k;
 112                 }
 113                 else {
 114                     ASSERT_TRUE( pq.pop_with( [&key]( value_type& src ) { key = src.k;  } ) );
 115                     EXPECT_EQ( key, nPrev - 1 );
 116                     nPrev = key;
 117                 }
 118
 119                 --nSize;
 120                 ASSERT_EQ( pq.size(), nSize );
 121             }
 122
 123             ASSERT_TRUE( !pq.full() );
 124             ASSERT_TRUE( !pq.empty() );
 125             ASSERT_EQ( pq.size(), 1 );
 126
 127             ASSERT_TRUE( pq.pop( kv ) );
 128             EXPECT_EQ( kv.k, base_class::c_nMinValue );
 129
 130             ASSERT_TRUE( !pq.full() );
 131             ASSERT_TRUE( pq.empty() );
 132             ASSERT_EQ( pq.size(), 0 );
 133
 134             // Clear test
 135             for ( value_type * p = pFirst; p < pLast; ++p ) {
 136                 ASSERT_TRUE( pq.push( *p ) );
 137             }
 138             ASSERT_TRUE( !pq.empty() );
 139             ASSERT_TRUE( pq.full() );
 140             ASSERT_EQ( pq.size(), pq.capacity() );
 141             pq.clear();
 142             ASSERT_TRUE( pq.empty() );
 143             ASSERT_TRUE( !pq.full() );
 144             ASSERT_EQ( pq.size(), 0 );
 145
 146             // clear_with test
 147             for ( value_type * p = pFirst; p < pLast; ++p ) {
 148                 ASSERT_TRUE( pq.push( *p ) );
 149             }
 150             ASSERT_TRUE( !pq.empty() );
 151             ASSERT_TRUE( pq.full() );
 152             ASSERT_EQ( pq.size(), pq.capacity() );
 153
 154             {
 155                 disposer disp;
 156                 pq.clear_with( std::ref( disp ) );
 157                 ASSERT_TRUE( pq.empty() );
 158                 ASSERT_TRUE( !pq.full() );
 159                 ASSERT_EQ( pq.size(), 0 );
 160                 ASSERT_EQ( disp.m_nCallCount, pq.capacity() );
 161             }
 162         }
 163     };
 164
 165     typedef cds::opt::v::initialized_dynamic_buffer< char > dyn_buffer_type;
 166     typedef cds::opt::v::initialized_static_buffer< char, MSPQueue::c_nCapacity > static_buffer_type;
 167
 168     TEST_F( MSPQueue, dynamic )
 169     {
 170         typedef cds::container::MSPriorityQueue< MSPQueue::value_type,
 171             cds::container::mspriority_queue::make_traits<
 172                 cds::opt::buffer< dyn_buffer_type >
 173             >::type
 174         > pqueue;
 175
 176         pqueue pq( c_nCapacity );
 177         test( pq );
 178     }
 179
 180     TEST_F( MSPQueue, dynamic_cmp )
 181     {
 182         typedef cds::container::MSPriorityQueue< value_type,
 183             cds::container::mspriority_queue::make_traits<
 184                 cds::opt::buffer< dyn_buffer_type >
 185                 , cds::opt::compare< compare >
 186             >::type
 187         > pqueue;
 188
 189         pqueue pq( c_nCapacity );
 190         test( pq );
 191     }
 192
 193     TEST_F( MSPQueue, dynamic_less )
 194     {
 195         typedef cds::container::MSPriorityQueue< value_type,
 196             cds::container::mspriority_queue::make_traits<
 197                 cds::opt::buffer< dyn_buffer_type >
 198                 ,cds::opt::less< less >
 199             >::type
 200         > pqueue;
 201
 202         pqueue pq( c_nCapacity );
 203         test( pq );
 204     }
 205     TEST_F( MSPQueue, dynamic_cmp_less )
 206     {
 207         struct pqueue_traits : public cds::container::mspriority_queue::traits
 208         {
 209             typedef dyn_buffer_type buffer;
 210             typedef MSPQueue::less less;
 211             typedef MSPQueue::compare compare;
 212         };
 213         typedef cds::container::MSPriorityQueue< value_type, pqueue_traits > pqueue;
 214
 215         pqueue pq( c_nCapacity );
 216         test( pq );
 217     }
 218
 219     TEST_F( MSPQueue, dynamic_mutex )
 220     {
 221         typedef cds::container::MSPriorityQueue< value_type,
 222             cds::container::mspriority_queue::make_traits<
 223                 cds::opt::buffer< dyn_buffer_type >
 224                 ,cds::opt::compare< compare >
 225                 ,cds::opt::lock_type<std::mutex>
 226             >::type
 227         > pqueue;
 228
 229         pqueue pq( c_nCapacity );
 230         test( pq );
 231     }
 232
 233     TEST_F( MSPQueue, stat )
 234     {
 235         typedef cds::container::MSPriorityQueue< MSPQueue::value_type,
 236             cds::container::mspriority_queue::make_traits<
 237             cds::opt::buffer< static_buffer_type >
 238             >::type
 239         > pqueue;
 240
 241         std::unique_ptr< pqueue > pq( new pqueue(0));
 242         test( *pq );
 243     }
 244
 245     TEST_F( MSPQueue, stat_cmp )
 246     {
 247         typedef cds::container::MSPriorityQueue< value_type,
 248             cds::container::mspriority_queue::make_traits<
 249                 cds::opt::buffer< static_buffer_type >
 250                 ,cds::opt::compare< compare >
 251             >::type
 252         > pqueue;
 253
 254         std::unique_ptr< pqueue > pq( new pqueue(0));
 255         test( *pq );
 256     }
 257
 258     TEST_F( MSPQueue, stat_less )
 259     {
 260         typedef cds::container::MSPriorityQueue< value_type,
 261             cds::container::mspriority_queue::make_traits<
 262                 cds::opt::buffer< static_buffer_type >
 263                 ,cds::opt::less< less >
 264             >::type
 265         > pqueue;
 266
 267         std::unique_ptr< pqueue > pq( new pqueue(0));
 268         test( *pq );
 269     }
 270
 271     TEST_F( MSPQueue, stat_mutex )
 272     {
 273         typedef cds::container::MSPriorityQueue< value_type,
 274             cds::container::mspriority_queue::make_traits<
 275                 cds::opt::buffer< static_buffer_type >
 276                 ,cds::opt::less< less >
 277                 ,cds::opt::lock_type<std::mutex>
 278             >::type
 279         > pqueue;
 280
 281         std::unique_ptr< pqueue > pq( new pqueue(0));
 282         test( *pq );
 283     }
 284
 285 } // namespace