tests/test-hdr/priority_queue/hdr_pqueue.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_PQUEUE_H
  32 #define CDSTEST_HDR_PQUEUE_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include "size_check.h"
  36 #include <algorithm>
  37 #include <functional>   // ref
  38
  39 namespace priority_queue {
  40
  41     namespace pqueue {
  42         static size_t const c_nCapacity = 1024 * 16;
  43
  44         struct disposer {
  45             size_t   m_nCallCount;
  46
  47             disposer()
  48                 : m_nCallCount(0)
  49             {}
  50
  51             template <typename T>
  52             void operator()( T& )
  53             {
  54                 ++m_nCallCount;
  55             }
  56         };
  57
  58         template <typename PQueue>
  59         struct constants {
  60             static size_t const nCapacity = c_nCapacity;
  61         };
  62     } // namespace pqueue
  63
  64     class PQueueHdrTest: public CppUnitMini::TestCase
  65     {
  66     public:
  67         static size_t const c_nCapacity = pqueue::c_nCapacity;
  68
  69         typedef int     key_type;
  70         static key_type const c_nMinValue = -123;
  71
  72         struct value_type {
  73             key_type    k;
  74             int         v;
  75
  76             value_type()
  77             {}
  78
  79             value_type( value_type const& kv )
  80                 : k(kv.k)
  81                 , v(kv.v)
  82             {}
  83
  84             value_type( key_type key )
  85                 : k(key)
  86                 , v(key)
  87             {}
  88
  89             value_type( key_type key, int val )
  90                 : k(key)
  91                 , v(val)
  92             {}
  93
  94             value_type( std::pair<key_type, int> const& p )
  95                 : k(p.first)
  96                 , v(p.second)
  97             {}
  98         };
  99
 100         struct compare {
 101             int operator()( value_type k1, value_type k2 ) const
 102             {
 103                 return k1.k - k2.k;
 104             }
 105         };
 106
 107         struct less {
 108             bool operator()( value_type k1, value_type k2 ) const
 109             {
 110                 return k1.k < k2.k;
 111             }
 112         };
 113
 114         template <typename T>
 115         class data_array
 116         {
 117             T *     pFirst;
 118             T *     pLast;
 119
 120         public:
 121             data_array( size_t nSize )
 122                 : pFirst( new T[nSize] )
 123                 , pLast( pFirst + nSize )
 124             {
 125                 key_type i = c_nMinValue;
 126                 for ( T * p = pFirst; p != pLast; ++p, ++i )
 127                     p->k = p->v = i;
 128
 129                 shuffle( pFirst, pLast );
 130             }
 131
 132             ~data_array()
 133             {
 134                 delete [] pFirst;
 135             }
 136
 137             T * begin() { return pFirst; }
 138             T * end()   { return pLast ; }
 139             size_t size() const
 140             {
 141                 return pLast - pFirst;
 142             }
 143         };
 144
 145     protected:
 146         template <class PQueue>
 147         void test_bounded_with( PQueue& pq )
 148         {
 149             data_array<value_type> arr( pq.capacity() );
 150             value_type * pFirst = arr.begin();
 151             value_type * pLast  = pFirst + pq.capacity();
 152
 153             CPPUNIT_ASSERT( pq.empty() );
 154             CPPUNIT_ASSERT( pq.size() == 0 );
 155             CPPUNIT_ASSERT_EX( pq.capacity() == pqueue::constants<PQueue>::nCapacity,
 156                 "pq.capacity() = " << pq.capacity() << ", pqueue::constants<PQueue>::nCapacity = " << pqueue::constants<PQueue>::nCapacity
 157                 );
 158
 159             size_t nSize = 0;
 160
 161             // Push test
 162             for ( value_type * p = pFirst; p < pLast; ++p ) {
 163                 switch ( pq.size() & 3 ) {
 164                     case 0:
 165                         CPPUNIT_ASSERT( pq.push_with( [p]( value_type& dest ) { dest = *p; } ));
 166                         break;
 167                     case 1:
 168                         CPPUNIT_ASSERT( pq.emplace( p->k, p->v ));
 169                         break;
 170                     case 2:
 171                         CPPUNIT_ASSERT( pq.emplace( std::make_pair( p->k, p->v ) ));
 172                         break;
 173                     default:
 174                         CPPUNIT_ASSERT( pq.push( *p ));
 175                 }
 176                 CPPUNIT_ASSERT( !pq.empty() );
 177                 CPPUNIT_ASSERT( pq.size() == ++nSize );
 178             }
 179
 180             CPPUNIT_ASSERT( pq.full() );
 181             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 182
 183             // The queue is full
 184             key_type k = c_nMinValue + key_type(c_nCapacity);
 185             CPPUNIT_ASSERT( !pq.push( k ));
 186             CPPUNIT_ASSERT( pq.full() );
 187             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 188
 189             // Pop test
 190             key_type nPrev = c_nMinValue + key_type(pq.capacity()) - 1;
 191             value_type kv(0);
 192             key_type   key;
 193             CPPUNIT_ASSERT( pq.pop(kv) );
 194             CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
 195
 196             CPPUNIT_ASSERT( pq.size() == pq.capacity() - 1 );
 197             CPPUNIT_ASSERT( !pq.full() );
 198             CPPUNIT_ASSERT( !pq.empty() );
 199
 200             nSize = pq.size();
 201             while ( pq.size() > 1 ) {
 202                 if ( pq.size() & 1 ) {
 203                     CPPUNIT_ASSERT( pq.pop(kv) );
 204                     CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
 205                     nPrev = kv.k;
 206                 }
 207                 else {
 208                     CPPUNIT_ASSERT( pq.pop_with( [&key]( value_type& src ) { key = src.k;  } ) );
 209                     CPPUNIT_CHECK_EX( key == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << key );
 210                     nPrev = key;
 211                 }
 212
 213                 --nSize;
 214                 CPPUNIT_ASSERT( pq.size() == nSize );
 215             }
 216
 217             CPPUNIT_ASSERT( !pq.full() );
 218             CPPUNIT_ASSERT( !pq.empty() );
 219             CPPUNIT_ASSERT( pq.size() == 1 );
 220
 221             CPPUNIT_ASSERT( pq.pop(kv) );
 222             CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
 223
 224             CPPUNIT_ASSERT( !pq.full() );
 225             CPPUNIT_ASSERT( pq.empty() );
 226             CPPUNIT_ASSERT( pq.size() == 0 );
 227
 228             // Clear test
 229             for ( value_type * p = pFirst; p < pLast; ++p ) {
 230                 CPPUNIT_ASSERT( pq.push( *p ));
 231             }
 232             CPPUNIT_ASSERT( !pq.empty() );
 233             CPPUNIT_ASSERT( pq.full() );
 234             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 235             pq.clear();
 236             CPPUNIT_ASSERT( pq.empty() );
 237             CPPUNIT_ASSERT( !pq.full() );
 238             CPPUNIT_ASSERT( pq.size() == 0 );
 239
 240             // clear_with test
 241             for ( value_type * p = pFirst; p < pLast; ++p ) {
 242                 CPPUNIT_ASSERT( pq.push( *p ));
 243             }
 244             CPPUNIT_ASSERT( !pq.empty() );
 245             CPPUNIT_ASSERT( pq.full() );
 246             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 247
 248             {
 249                 pqueue::disposer disp;
 250                 pq.clear_with( std::ref(disp) );
 251                 CPPUNIT_ASSERT( pq.empty() );
 252                 CPPUNIT_ASSERT( !pq.full() );
 253                 CPPUNIT_ASSERT( pq.size() == 0 );
 254                 CPPUNIT_ASSERT( disp.m_nCallCount == pq.capacity() );
 255             }
 256         }
 257
 258         template <class PQueue>
 259         void test_msq_stat()
 260         {
 261             PQueue pq( 0 );   // argument should be ignored for static buffer
 262             test_bounded_with( pq );
 263         }
 264         template <class PQueue>
 265         void test_msq_dyn()
 266         {
 267             PQueue pq( c_nCapacity );
 268             test_bounded_with( pq );
 269         }
 270
 271         template <class PQueue>
 272         void test_fcpqueue()
 273         {
 274             PQueue pq;
 275
 276             data_array<value_type> arr( c_nCapacity );
 277             value_type * pFirst = arr.begin();
 278             value_type * pLast  = pFirst + c_nCapacity;
 279
 280             CPPUNIT_ASSERT( pq.empty() );
 281             CPPUNIT_ASSERT( pq.size() == 0 );
 282
 283             size_t nSize = 0;
 284
 285             // Push test
 286             for ( value_type * p = pFirst; p < pLast; ++p ) {
 287                 CPPUNIT_ASSERT( pq.push( *p ));
 288                 CPPUNIT_ASSERT( !pq.empty() );
 289                 CPPUNIT_ASSERT( pq.size() == ++nSize );
 290             }
 291
 292             CPPUNIT_ASSERT( pq.size() == c_nCapacity );
 293
 294             // Pop test
 295             key_type nPrev = c_nMinValue + key_type(c_nCapacity) - 1;
 296             value_type kv(0);
 297             //key_type   key;
 298             CPPUNIT_ASSERT( pq.pop(kv) );
 299             CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
 300
 301             CPPUNIT_ASSERT( pq.size() == c_nCapacity - 1 );
 302             CPPUNIT_ASSERT( !pq.empty() );
 303
 304             nSize = pq.size();
 305             while ( pq.size() > 1 ) {
 306                 CPPUNIT_ASSERT( pq.pop(kv) );
 307                 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
 308                 nPrev = kv.k;
 309
 310                 --nSize;
 311                 CPPUNIT_ASSERT( pq.size() == nSize );
 312             }
 313
 314             CPPUNIT_ASSERT( !pq.empty() );
 315             CPPUNIT_ASSERT( pq.size() == 1 );
 316
 317             CPPUNIT_ASSERT( pq.pop(kv) );
 318             CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
 319
 320             CPPUNIT_ASSERT( pq.empty() );
 321             CPPUNIT_ASSERT( pq.size() == 0 );
 322
 323             // Clear test
 324             for ( value_type * p = pFirst; p < pLast; ++p ) {
 325                 CPPUNIT_ASSERT( pq.push( *p ));
 326             }
 327             CPPUNIT_ASSERT( !pq.empty() );
 328             CPPUNIT_ASSERT( pq.size() == c_nCapacity );
 329
 330             pq.clear();
 331             CPPUNIT_ASSERT( pq.empty() );
 332             CPPUNIT_ASSERT( pq.size() == 0 );
 333         }
 334
 335     public:
 336         void MSPQueue_st();
 337         void MSPQueue_st_cmp();
 338         void MSPQueue_st_less();
 339         void MSPQueue_st_cmpless();
 340         void MSPQueue_st_cmp_mtx();
 341         void MSPQueue_dyn();
 342         void MSPQueue_dyn_cmp();
 343         void MSPQueue_dyn_less();
 344         void MSPQueue_dyn_cmpless();
 345         void MSPQueue_dyn_cmp_mtx();
 346
 347         void FCPQueue_vector();
 348         void FCPQueue_vector_stat();
 349         void FCPQueue_vector_mutex();
 350         void FCPQueue_deque();
 351         void FCPQueue_deque_stat();
 352         void FCPQueue_deque_mutex();
 353         void FCPQueue_boost_deque();
 354         void FCPQueue_boost_deque_stat();
 355         void FCPQueue_stablevector();
 356         void FCPQueue_stablevector_stat();
 357
 358         CPPUNIT_TEST_SUITE(PQueueHdrTest)
 359             CPPUNIT_TEST(MSPQueue_st)
 360             CPPUNIT_TEST(MSPQueue_st_cmp)
 361             CPPUNIT_TEST(MSPQueue_st_less)
 362             CPPUNIT_TEST(MSPQueue_st_cmpless)
 363             CPPUNIT_TEST(MSPQueue_st_cmp_mtx)
 364             CPPUNIT_TEST(MSPQueue_dyn)
 365             CPPUNIT_TEST(MSPQueue_dyn_cmp)
 366             CPPUNIT_TEST(MSPQueue_dyn_less)
 367             CPPUNIT_TEST(MSPQueue_dyn_cmpless)
 368             CPPUNIT_TEST(MSPQueue_dyn_cmp_mtx)
 369
 370             CPPUNIT_TEST(FCPQueue_vector)
 371             CPPUNIT_TEST(FCPQueue_vector_stat)
 372             CPPUNIT_TEST(FCPQueue_vector_mutex)
 373             CPPUNIT_TEST(FCPQueue_deque)
 374             CPPUNIT_TEST(FCPQueue_deque_stat)
 375             CPPUNIT_TEST(FCPQueue_deque_mutex)
 376             CPPUNIT_TEST(FCPQueue_boost_deque)
 377             CPPUNIT_TEST(FCPQueue_boost_deque_stat)
 378             CPPUNIT_TEST(FCPQueue_stablevector)
 379             CPPUNIT_TEST(FCPQueue_stablevector_stat)
 380         CPPUNIT_TEST_SUITE_END()
 381     };
 382
 383 } // namespace priority_queue
 384
 385 namespace std {
 386     template<>
 387     struct less<priority_queue::PQueueHdrTest::value_type>
 388     {
 389         bool operator()( priority_queue::PQueueHdrTest::value_type const& v1, priority_queue::PQueueHdrTest::value_type const& v2) const
 390         {
 391             return priority_queue::PQueueHdrTest::less()( v1, v2 );
 392         }
 393     };
 394 }
 395
 396 #endif // #ifndef CDSTEST_HDR_PQUEUE_H