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