tests/unit/pqueue/pop.cpp

   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 #include "cppunit/thread.h"
  32 #include "pqueue/pqueue_item.h"
  33 #include "pqueue/pqueue_type.h"
  34
  35 #include <vector>
  36 #include <memory>
  37
  38 namespace pqueue {
  39
  40 #define TEST_CASE( Q ) void Q() { test< Types<pqueue::SimpleValue>::Q >(); }
  41 #define TEST_BOUNDED( Q ) void Q() { test_bounded< Types<pqueue::SimpleValue>::Q >(); }
  42
  43     namespace {
  44         static size_t s_nThreadCount = 8;
  45         static size_t s_nQueueSize = 2000000;
  46     }
  47 } // namespace pqueue
  48
  49 namespace pqueue {
  50
  51     class PQueue_Pop: public CppUnitMini::TestCase
  52     {
  53
  54         template <class PQueue>
  55         class Pusher: public CppUnitMini::TestThread
  56         {
  57             virtual TestThread *    clone()
  58             {
  59                 return new Pusher( *this );
  60             }
  61         public:
  62             PQueue&             m_Queue;
  63             size_t              m_nPushError;
  64
  65             typedef std::vector<size_t> array_type;
  66             array_type          m_arr;
  67
  68         public:
  69             Pusher( CppUnitMini::ThreadPool& pool, PQueue& q )
  70                 : CppUnitMini::TestThread( pool )
  71                 , m_Queue( q )
  72             {}
  73             Pusher( Pusher& src )
  74                 : CppUnitMini::TestThread( src )
  75                 , m_Queue( src.m_Queue )
  76             {}
  77
  78             PQueue_Pop&  getTest()
  79             {
  80                 return static_cast<PQueue_Pop&>( m_Pool.m_Test );
  81             }
  82
  83             virtual void init()
  84             {
  85                 cds::threading::Manager::attachThread();
  86             }
  87             virtual void fini()
  88             {
  89                 cds::threading::Manager::detachThread();
  90             }
  91
  92             virtual void test()
  93             {
  94                 m_nPushError = 0;
  95
  96                 for ( array_type::const_iterator it = m_arr.begin(); it != m_arr.end(); ++it ) {
  97                     if ( !m_Queue.push( SimpleValue( *it ) ))
  98                         ++m_nPushError;
  99                 }
 100             }
 101
 102             void prepare( size_t nStart, size_t nEnd )
 103             {
 104                 m_arr.reserve( nEnd - nStart );
 105                 for ( size_t i = nStart; i < nEnd; ++i )
 106                     m_arr.push_back( i );
 107                 shuffle( m_arr.begin(), m_arr.end() );
 108             }
 109         };
 110
 111         template <class PQueue>
 112         class Popper: public CppUnitMini::TestThread
 113         {
 114             virtual TestThread *    clone()
 115             {
 116                 return new Popper( *this );
 117             }
 118         public:
 119             PQueue&             m_Queue;
 120             size_t              m_nPopError;
 121             size_t              m_nPopErrorEq;
 122             size_t              m_nPopSuccess;
 123             size_t              m_nPopFailed;
 124
 125         public:
 126             Popper( CppUnitMini::ThreadPool& pool, PQueue& q )
 127                 : CppUnitMini::TestThread( pool )
 128                 , m_Queue( q )
 129             {}
 130             Popper( Popper& src )
 131                 : CppUnitMini::TestThread( src )
 132                 , m_Queue( src.m_Queue )
 133             {}
 134
 135             PQueue_Pop&  getTest()
 136             {
 137                 return static_cast<PQueue_Pop&>( m_Pool.m_Test );
 138             }
 139
 140             virtual void init()
 141             {
 142                 cds::threading::Manager::attachThread();
 143             }
 144             virtual void fini()
 145             {
 146                 cds::threading::Manager::detachThread();
 147             }
 148
 149             virtual void test()
 150             {
 151                 m_nPopError = 0;
 152                 m_nPopErrorEq = 0;
 153                 m_nPopSuccess = 0;
 154                 m_nPopFailed = 0;
 155
 156                 size_t nPrevKey;
 157                 SimpleValue val;
 158                 if ( m_Queue.pop( val )) {
 159                     ++m_nPopSuccess;
 160                     nPrevKey = val.key;
 161
 162                     while ( !m_Queue.empty() ) {
 163                         if ( m_Queue.pop( val )) {
 164                             ++m_nPopSuccess;
 165                             if ( val.key > nPrevKey )
 166                                 ++m_nPopError;
 167                             else if ( val.key == nPrevKey )
 168                                 ++m_nPopErrorEq;
 169                             nPrevKey = val.key;
 170                         }
 171                         else
 172                             ++m_nPopFailed;
 173                     }
 174                 }
 175                 else
 176                     ++m_nPopFailed;
 177             }
 178         };
 179
 180     protected:
 181         template <class PQueue>
 182         void test()
 183         {
 184             PQueue testQueue;
 185             test_with( testQueue );
 186         }
 187
 188         template <class PQueue>
 189         void test_bounded()
 190         {
 191             std::unique_ptr<PQueue> pq( new PQueue(s_nQueueSize) );
 192             test_with( *pq.get() );
 193         }
 194
 195         template <class PQueue>
 196         void test_with( PQueue& testQueue )
 197         {
 198             size_t const nThreadItemCount = s_nQueueSize / s_nThreadCount;
 199
 200             // push
 201             {
 202                 CppUnitMini::ThreadPool pool( *this );
 203                 pool.add( new Pusher<PQueue>( pool, testQueue ), s_nThreadCount );
 204
 205                 size_t nStart = 0;
 206                 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 207                     Pusher<PQueue> * pThread = static_cast<Pusher<PQueue> *>(*it);
 208                     pThread->prepare( nStart, nStart + nThreadItemCount );
 209                     nStart += nThreadItemCount;
 210                 }
 211
 212                 CPPUNIT_MSG( "   Push, thread count=" << s_nThreadCount << ", item count=" << nThreadItemCount * s_nThreadCount << " ..." );
 213                 pool.run();
 214                 CPPUNIT_MSG( "     Duration=" << pool.avgDuration() );
 215             }
 216
 217             // pop
 218             {
 219                 CppUnitMini::ThreadPool pool( *this );
 220                 pool.add( new Popper<PQueue>( pool, testQueue ), s_nThreadCount );
 221
 222                 CPPUNIT_MSG( "   Pop, thread count=" << s_nThreadCount << ", item count=" << nThreadItemCount * s_nThreadCount << " ..." );
 223                 pool.run();
 224                 CPPUNIT_MSG( "     Duration=" << pool.avgDuration() );
 225
 226                 // Analyze result
 227                 size_t nTotalPopped = 0;
 228                 size_t nTotalError = 0;
 229                 size_t nTotalErrorEq = 0;
 230                 size_t nTotalFailed = 0;
 231                 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 232                     Popper<PQueue> * pThread = static_cast<Popper<PQueue> *>(*it);
 233
 234                     nTotalPopped += pThread->m_nPopSuccess;
 235                     nTotalError += pThread->m_nPopError;
 236                     nTotalErrorEq += pThread->m_nPopErrorEq;
 237                     nTotalFailed += pThread->m_nPopFailed;
 238                 }
 239
 240                 CPPUNIT_MSG( "   Total: popped=" << nTotalPopped << ", empty pop=" << nTotalFailed
 241                              << "\n  Errors: pop equal=" << nTotalErrorEq << ", priority violation=" << nTotalError
 242                              );
 243                 CPPUNIT_CHECK( nTotalPopped == nThreadItemCount * s_nThreadCount );
 244                 CPPUNIT_CHECK( nTotalError == 0 );
 245                 CPPUNIT_CHECK( nTotalErrorEq == 0 );
 246             }
 247
 248             CPPUNIT_MSG( testQueue.statistics() );
 249         }
 250
 251         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 252             s_nThreadCount = cfg.getULong("ThreadCount", (unsigned long) s_nThreadCount );
 253             s_nQueueSize = cfg.getULong("QueueSize", (unsigned long) s_nQueueSize );
 254         }
 255
 256     protected:
 257 #include "pqueue/pqueue_defs.h"
 258         CDSUNIT_DECLARE_MSPriorityQueue
 259         CDSUNIT_DECLARE_EllenBinTree
 260         CDSUNIT_DECLARE_SkipList
 261         CDSUNIT_DECLARE_FCPriorityQueue
 262         CDSUNIT_DECLARE_StdPQueue
 263
 264         CPPUNIT_TEST_SUITE_(PQueue_Pop, "PQueue_Push")
 265             CDSUNIT_TEST_MSPriorityQueue
 266             CDSUNIT_TEST_EllenBinTree
 267             CDSUNIT_TEST_SkipList
 268             CDSUNIT_TEST_FCPriorityQueue
 269             CDUNIT_TEST_StdPQueue
 270         CPPUNIT_TEST_SUITE_END();
 271     };
 272
 273 } // namespace queue
 274
 275 CPPUNIT_TEST_SUITE_REGISTRATION(pqueue::PQueue_Pop);