tests/test-hdr/priority_queue/hdr_pqueue.h

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