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 <functional>   // ref
  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     protected:
 118         template <class PQueue>
 119         void test_bounded_with( PQueue& pq )
 120         {
 121             data_array<value_type> arr( pq.capacity() );
 122             value_type * pFirst = arr.begin();
 123             value_type * pLast  = pFirst + pq.capacity();
 124
 125             CPPUNIT_ASSERT( pq.empty() );
 126             CPPUNIT_ASSERT( pq.size() == 0 );
 127             CPPUNIT_ASSERT_EX( pq.capacity() == pqueue::constants<PQueue>::nCapacity,
 128                 "pq.capacity() = " << pq.capacity() << ", pqueue::constants<PQueue>::nCapacity = " << pqueue::constants<PQueue>::nCapacity
 129                 );
 130
 131             size_t nSize = 0;
 132
 133             // Push test
 134             for ( value_type * p = pFirst; p < pLast; ++p ) {
 135                 switch ( pq.size() & 3 ) {
 136                     case 0:
 137                         CPPUNIT_ASSERT( pq.push_with( [p]( value_type& dest ) { dest = *p; } ));
 138                         break;
 139                     case 1:
 140                         CPPUNIT_ASSERT( pq.emplace( p->k, p->v ));
 141                         break;
 142                     case 2:
 143                         CPPUNIT_ASSERT( pq.emplace( std::make_pair( p->k, p->v ) ));
 144                         break;
 145                     default:
 146                         CPPUNIT_ASSERT( pq.push( *p ));
 147                 }
 148                 CPPUNIT_ASSERT( !pq.empty() );
 149                 CPPUNIT_ASSERT( pq.size() == ++nSize );
 150             }
 151
 152             CPPUNIT_ASSERT( pq.full() );
 153             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 154
 155             // The queue is full
 156             key_type k = c_nMinValue + key_type(c_nCapacity);
 157             CPPUNIT_ASSERT( !pq.push( k ));
 158             CPPUNIT_ASSERT( pq.full() );
 159             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 160
 161             // Pop test
 162             key_type nPrev = c_nMinValue + key_type(pq.capacity()) - 1;
 163             value_type kv(0);
 164             key_type   key;
 165             CPPUNIT_ASSERT( pq.pop(kv) );
 166             CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
 167
 168             CPPUNIT_ASSERT( pq.size() == pq.capacity() - 1 );
 169             CPPUNIT_ASSERT( !pq.full() );
 170             CPPUNIT_ASSERT( !pq.empty() );
 171
 172             nSize = pq.size();
 173             while ( pq.size() > 1 ) {
 174                 if ( pq.size() & 1 ) {
 175                     CPPUNIT_ASSERT( pq.pop(kv) );
 176                     CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
 177                     nPrev = kv.k;
 178                 }
 179                 else {
 180                     CPPUNIT_ASSERT( pq.pop_with( [&key]( value_type& src ) { key = src.k;  } ) );
 181                     CPPUNIT_CHECK_EX( key == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << key );
 182                     nPrev = key;
 183                 }
 184
 185                 --nSize;
 186                 CPPUNIT_ASSERT( pq.size() == nSize );
 187             }
 188
 189             CPPUNIT_ASSERT( !pq.full() );
 190             CPPUNIT_ASSERT( !pq.empty() );
 191             CPPUNIT_ASSERT( pq.size() == 1 );
 192
 193             CPPUNIT_ASSERT( pq.pop(kv) );
 194             CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
 195
 196             CPPUNIT_ASSERT( !pq.full() );
 197             CPPUNIT_ASSERT( pq.empty() );
 198             CPPUNIT_ASSERT( pq.size() == 0 );
 199
 200             // Clear test
 201             for ( value_type * p = pFirst; p < pLast; ++p ) {
 202                 CPPUNIT_ASSERT( pq.push( *p ));
 203             }
 204             CPPUNIT_ASSERT( !pq.empty() );
 205             CPPUNIT_ASSERT( pq.full() );
 206             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 207             pq.clear();
 208             CPPUNIT_ASSERT( pq.empty() );
 209             CPPUNIT_ASSERT( !pq.full() );
 210             CPPUNIT_ASSERT( pq.size() == 0 );
 211
 212             // clear_with test
 213             for ( value_type * p = pFirst; p < pLast; ++p ) {
 214                 CPPUNIT_ASSERT( pq.push( *p ));
 215             }
 216             CPPUNIT_ASSERT( !pq.empty() );
 217             CPPUNIT_ASSERT( pq.full() );
 218             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 219
 220             {
 221                 pqueue::disposer disp;
 222                 pq.clear_with( std::ref(disp) );
 223                 CPPUNIT_ASSERT( pq.empty() );
 224                 CPPUNIT_ASSERT( !pq.full() );
 225                 CPPUNIT_ASSERT( pq.size() == 0 );
 226                 CPPUNIT_ASSERT( disp.m_nCallCount == pq.capacity() );
 227             }
 228         }
 229
 230         template <class PQueue>
 231         void test_msq_stat()
 232         {
 233             PQueue pq( 0 );   // argument should be ignored for static buffer
 234             test_bounded_with( pq );
 235         }
 236         template <class PQueue>
 237         void test_msq_dyn()
 238         {
 239             PQueue pq( c_nCapacity );
 240             test_bounded_with( pq );
 241         }
 242
 243         template <class PQueue>
 244         void test_fcpqueue()
 245         {
 246             PQueue pq;
 247
 248             data_array<value_type> arr( c_nCapacity );
 249             value_type * pFirst = arr.begin();
 250             value_type * pLast  = pFirst + c_nCapacity;
 251
 252             CPPUNIT_ASSERT( pq.empty() );
 253             CPPUNIT_ASSERT( pq.size() == 0 );
 254
 255             size_t nSize = 0;
 256
 257             // Push test
 258             for ( value_type * p = pFirst; p < pLast; ++p ) {
 259                 CPPUNIT_ASSERT( pq.push( *p ));
 260                 CPPUNIT_ASSERT( !pq.empty() );
 261                 CPPUNIT_ASSERT( pq.size() == ++nSize );
 262             }
 263
 264             CPPUNIT_ASSERT( pq.size() == c_nCapacity );
 265
 266             // Pop test
 267             key_type nPrev = c_nMinValue + key_type(c_nCapacity) - 1;
 268             value_type kv(0);
 269             //key_type   key;
 270             CPPUNIT_ASSERT( pq.pop(kv) );
 271             CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
 272
 273             CPPUNIT_ASSERT( pq.size() == c_nCapacity - 1 );
 274             CPPUNIT_ASSERT( !pq.empty() );
 275
 276             nSize = pq.size();
 277             while ( pq.size() > 1 ) {
 278                 CPPUNIT_ASSERT( pq.pop(kv) );
 279                 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
 280                 nPrev = kv.k;
 281
 282                 --nSize;
 283                 CPPUNIT_ASSERT( pq.size() == nSize );
 284             }
 285
 286             CPPUNIT_ASSERT( !pq.empty() );
 287             CPPUNIT_ASSERT( pq.size() == 1 );
 288
 289             CPPUNIT_ASSERT( pq.pop(kv) );
 290             CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
 291
 292             CPPUNIT_ASSERT( pq.empty() );
 293             CPPUNIT_ASSERT( pq.size() == 0 );
 294
 295             // Clear test
 296             for ( value_type * p = pFirst; p < pLast; ++p ) {
 297                 CPPUNIT_ASSERT( pq.push( *p ));
 298             }
 299             CPPUNIT_ASSERT( !pq.empty() );
 300             CPPUNIT_ASSERT( pq.size() == c_nCapacity );
 301
 302             pq.clear();
 303             CPPUNIT_ASSERT( pq.empty() );
 304             CPPUNIT_ASSERT( pq.size() == 0 );
 305         }
 306
 307     public:
 308         void MSPQueue_st();
 309         void MSPQueue_st_cmp();
 310         void MSPQueue_st_less();
 311         void MSPQueue_st_cmpless();
 312         void MSPQueue_st_cmp_mtx();
 313         void MSPQueue_dyn();
 314         void MSPQueue_dyn_cmp();
 315         void MSPQueue_dyn_less();
 316         void MSPQueue_dyn_cmpless();
 317         void MSPQueue_dyn_cmp_mtx();
 318
 319         void FCPQueue_vector();
 320         void FCPQueue_vector_stat();
 321         void FCPQueue_vector_mutex();
 322         void FCPQueue_deque();
 323         void FCPQueue_deque_stat();
 324         void FCPQueue_deque_mutex();
 325         void FCPQueue_boost_deque();
 326         void FCPQueue_boost_deque_stat();
 327         void FCPQueue_stablevector();
 328         void FCPQueue_stablevector_stat();
 329
 330         CPPUNIT_TEST_SUITE(PQueueHdrTest)
 331             CPPUNIT_TEST(MSPQueue_st)
 332             CPPUNIT_TEST(MSPQueue_st_cmp)
 333             CPPUNIT_TEST(MSPQueue_st_less)
 334             CPPUNIT_TEST(MSPQueue_st_cmpless)
 335             CPPUNIT_TEST(MSPQueue_st_cmp_mtx)
 336             CPPUNIT_TEST(MSPQueue_dyn)
 337             CPPUNIT_TEST(MSPQueue_dyn_cmp)
 338             CPPUNIT_TEST(MSPQueue_dyn_less)
 339             CPPUNIT_TEST(MSPQueue_dyn_cmpless)
 340             CPPUNIT_TEST(MSPQueue_dyn_cmp_mtx)
 341
 342             CPPUNIT_TEST(FCPQueue_vector)
 343             CPPUNIT_TEST(FCPQueue_vector_stat)
 344             CPPUNIT_TEST(FCPQueue_vector_mutex)
 345             CPPUNIT_TEST(FCPQueue_deque)
 346             CPPUNIT_TEST(FCPQueue_deque_stat)
 347             CPPUNIT_TEST(FCPQueue_deque_mutex)
 348             CPPUNIT_TEST(FCPQueue_boost_deque)
 349             CPPUNIT_TEST(FCPQueue_boost_deque_stat)
 350             CPPUNIT_TEST(FCPQueue_stablevector)
 351             CPPUNIT_TEST(FCPQueue_stablevector_stat)
 352         CPPUNIT_TEST_SUITE_END()
 353     };
 354
 355 } // namespace priority_queue
 356
 357 namespace std {
 358     template<>
 359     struct less<priority_queue::PQueueHdrTest::value_type>
 360     {
 361         bool operator()( priority_queue::PQueueHdrTest::value_type const& v1, priority_queue::PQueueHdrTest::value_type const& v2) const
 362         {
 363             return priority_queue::PQueueHdrTest::less()( v1, v2 );
 364         }
 365     };
 366 }
 367
 368 #endif // #ifndef CDSHDRTEST_PQUEUE_H