tests/test-hdr/priority_queue/hdr_intrusive_pqueue.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSHDRTEST_INTRUSIVE_PQUEUE_H
   4 #define CDSHDRTEST_INTRUSIVE_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 intrusive_pqueue {
  14         static size_t const c_nCapacity = 1024 * 16;
  15
  16         struct another_disposer {
  17             size_t   m_nCallCount;
  18
  19             another_disposer()
  20                 : m_nCallCount(0)
  21             {}
  22             template <typename T>
  23             void operator()( T& p )
  24             {
  25                 ++m_nCallCount;
  26             }
  27         };
  28
  29         template <typename PQueue>
  30         struct constants {
  31             static size_t const nCapacity = c_nCapacity;
  32         };
  33     } // namespace intrusive_pqueue
  34
  35     class IntrusivePQueueHdrTest: public CppUnitMini::TestCase
  36     {
  37     public:
  38         static size_t const c_nCapacity = intrusive_pqueue::c_nCapacity;
  39
  40         typedef int     key_type;
  41         static key_type const c_nMinValue = -123;
  42
  43         struct compare {
  44             int operator()( key_type k1, key_type k2 ) const
  45             {
  46                 return k1 - k2;
  47             }
  48         };
  49
  50         template <typename T>
  51         class data_array
  52         {
  53             T *     pFirst;
  54             T *     pLast;
  55
  56         public:
  57             data_array( size_t nSize )
  58                 : pFirst( new T[nSize] )
  59                 , pLast( pFirst + nSize )
  60             {
  61                 T i = c_nMinValue;
  62                 for ( T * p = pFirst; p != pLast; ++p, ++i )
  63                     *p = i;
  64
  65                 std::random_shuffle( pFirst, pLast );
  66             }
  67
  68             ~data_array()
  69             {
  70                 delete [] pFirst;
  71             }
  72
  73             T * begin() { return pFirst; }
  74             T * end()   { return pLast ; }
  75             size_t size() const
  76             {
  77                 return pLast - pFirst;
  78             }
  79         };
  80
  81     protected:
  82         template <class PQueue>
  83         void test_bounded_with( PQueue& pq )
  84         {
  85             data_array<key_type> arr( pq.capacity() );
  86             key_type * pFirst = arr.begin();
  87             key_type * pLast  = pFirst + pq.capacity();
  88
  89             CPPUNIT_ASSERT( pq.empty() );
  90             CPPUNIT_ASSERT( pq.size() == 0 );
  91             CPPUNIT_ASSERT( pq.capacity() == intrusive_pqueue::constants<PQueue>::nCapacity );
  92
  93             size_t nSize = 0;
  94
  95             // Push test
  96             for ( key_type * p = pFirst; p < pLast; ++p ) {
  97                 CPPUNIT_ASSERT( pq.push( *p ));
  98                 CPPUNIT_ASSERT( !pq.empty() );
  99                 CPPUNIT_ASSERT( pq.size() == ++nSize );
 100             }
 101
 102             CPPUNIT_ASSERT( pq.full() );
 103             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 104
 105             // The queue is full
 106             key_type k = c_nMinValue + key_type(c_nCapacity);
 107             CPPUNIT_ASSERT( !pq.push( k ));
 108             CPPUNIT_ASSERT( pq.full() );
 109             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 110
 111             // Pop test
 112             key_type nPrev = c_nMinValue + key_type(pq.capacity()) - 1;
 113             key_type * p = pq.pop();
 114             CPPUNIT_ASSERT( p != NULL );
 115             CPPUNIT_CHECK_EX( *p == nPrev, "Expected=" << nPrev << ", current=" << *p );
 116
 117             CPPUNIT_ASSERT( pq.size() == pq.capacity() - 1 );
 118             CPPUNIT_ASSERT( !pq.full() );
 119             CPPUNIT_ASSERT( !pq.empty() );
 120
 121             nSize = pq.size();
 122             while ( pq.size() > 1 ) {
 123                 p = pq.pop();
 124                 CPPUNIT_ASSERT( p != NULL );
 125                 CPPUNIT_CHECK_EX( *p == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << *p );
 126                 nPrev = *p;
 127                 --nSize;
 128                 CPPUNIT_ASSERT( pq.size() == nSize );
 129             }
 130
 131             CPPUNIT_ASSERT( !pq.full() );
 132             CPPUNIT_ASSERT( !pq.empty() );
 133             CPPUNIT_ASSERT( pq.size() == 1 );
 134
 135             p = pq.pop();
 136             CPPUNIT_ASSERT( p != NULL );
 137             CPPUNIT_CHECK_EX( *p == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << *p );
 138
 139             CPPUNIT_ASSERT( !pq.full() );
 140             CPPUNIT_ASSERT( pq.empty() );
 141             CPPUNIT_ASSERT( pq.size() == 0 );
 142
 143             // Clear test
 144             for ( key_type * p = pFirst; p < pLast; ++p ) {
 145                 CPPUNIT_ASSERT( pq.push( *p ));
 146             }
 147             CPPUNIT_CHECK( !pq.empty() );
 148             CPPUNIT_CHECK( pq.full() );
 149             CPPUNIT_CHECK( pq.size() == pq.capacity() );
 150             pq.clear();
 151             CPPUNIT_CHECK( pq.empty() );
 152             CPPUNIT_CHECK( !pq.full() );
 153             CPPUNIT_CHECK( pq.size() == 0 );
 154
 155             // clear_with test
 156             for ( key_type * p = pFirst; p < pLast; ++p ) {
 157                 CPPUNIT_ASSERT( pq.push( *p ));
 158             }
 159             CPPUNIT_ASSERT( !pq.empty() );
 160             CPPUNIT_ASSERT( pq.full() );
 161             CPPUNIT_ASSERT( pq.size() == pq.capacity() );
 162
 163             {
 164                 intrusive_pqueue::another_disposer disp;
 165                 pq.clear_with( cds::ref(disp) );
 166                 CPPUNIT_ASSERT( pq.empty() );
 167                 CPPUNIT_ASSERT( !pq.full() );
 168                 CPPUNIT_ASSERT( pq.size() == 0 );
 169                 CPPUNIT_ASSERT( disp.m_nCallCount == pq.capacity() );
 170             }
 171         }
 172
 173         template <class PQueue>
 174         void test_msq_stat()
 175         {
 176             PQueue pq( 0 );   // argument should be ignored for static buffer
 177             test_bounded_with( pq );
 178         }
 179         template <class PQueue>
 180         void test_msq_dyn()
 181         {
 182             PQueue pq( c_nCapacity );
 183             test_bounded_with( pq );
 184         }
 185
 186     public:
 187         void MSPQueue_st();
 188         void MSPQueue_st_cmp();
 189         void MSPQueue_st_less();
 190         void MSPQueue_st_cmpless();
 191         void MSPQueue_st_cmp_mtx();
 192         void MSPQueue_dyn();
 193         void MSPQueue_dyn_cmp();
 194         void MSPQueue_dyn_less();
 195         void MSPQueue_dyn_cmpless();
 196         void MSPQueue_dyn_cmp_mtx();
 197
 198         CPPUNIT_TEST_SUITE(IntrusivePQueueHdrTest)
 199             CPPUNIT_TEST(MSPQueue_st)
 200             CPPUNIT_TEST(MSPQueue_st_cmp)
 201             CPPUNIT_TEST(MSPQueue_st_less)
 202             CPPUNIT_TEST(MSPQueue_st_cmpless)
 203             CPPUNIT_TEST(MSPQueue_st_cmp_mtx)
 204             CPPUNIT_TEST(MSPQueue_dyn)
 205             CPPUNIT_TEST(MSPQueue_dyn_cmp)
 206             CPPUNIT_TEST(MSPQueue_dyn_less)
 207             CPPUNIT_TEST(MSPQueue_dyn_cmpless)
 208             CPPUNIT_TEST(MSPQueue_dyn_cmp_mtx)
 209         CPPUNIT_TEST_SUITE_END()
 210     };
 211
 212 } // namespace priority_queue
 213
 214 #endif // #ifndef CDSHDRTEST_INTRUSIVE_PQUEUE_H