2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #include "cppunit/thread.h"
32 #include "pqueue/pqueue_item.h"
33 #include "pqueue/pqueue_type.h"
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 >(); }
44 static size_t s_nThreadCount = 8;
45 static size_t s_nQueueSize = 2000000;
51 class PQueue_Pop: public CppUnitMini::TestCase
54 template <class PQueue>
55 class Pusher: public CppUnitMini::TestThread
57 virtual TestThread * clone()
59 return new Pusher( *this );
65 typedef std::vector<size_t> array_type;
69 Pusher( CppUnitMini::ThreadPool& pool, PQueue& q )
70 : CppUnitMini::TestThread( pool )
74 : CppUnitMini::TestThread( src )
75 , m_Queue( src.m_Queue )
80 return static_cast<PQueue_Pop&>( m_Pool.m_Test );
85 cds::threading::Manager::attachThread();
89 cds::threading::Manager::detachThread();
96 for ( array_type::const_iterator it = m_arr.begin(); it != m_arr.end(); ++it ) {
97 if ( !m_Queue.push( SimpleValue( *it ) ))
102 void prepare( size_t nStart, size_t nEnd )
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() );
111 template <class PQueue>
112 class Popper: public CppUnitMini::TestThread
114 virtual TestThread * clone()
116 return new Popper( *this );
121 size_t m_nPopErrorEq;
122 size_t m_nPopSuccess;
126 Popper( CppUnitMini::ThreadPool& pool, PQueue& q )
127 : CppUnitMini::TestThread( pool )
130 Popper( Popper& src )
131 : CppUnitMini::TestThread( src )
132 , m_Queue( src.m_Queue )
135 PQueue_Pop& getTest()
137 return static_cast<PQueue_Pop&>( m_Pool.m_Test );
142 cds::threading::Manager::attachThread();
146 cds::threading::Manager::detachThread();
158 if ( m_Queue.pop( val )) {
162 while ( !m_Queue.empty() ) {
163 if ( m_Queue.pop( val )) {
165 if ( val.key > nPrevKey )
167 else if ( val.key == nPrevKey )
181 template <class PQueue>
185 test_with( testQueue );
188 template <class PQueue>
191 std::unique_ptr<PQueue> pq( new PQueue(s_nQueueSize) );
192 test_with( *pq.get() );
195 template <class PQueue>
196 void test_with( PQueue& testQueue )
198 size_t const nThreadItemCount = s_nQueueSize / s_nThreadCount;
202 CppUnitMini::ThreadPool pool( *this );
203 pool.add( new Pusher<PQueue>( pool, testQueue ), s_nThreadCount );
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;
212 CPPUNIT_MSG( " Push, thread count=" << s_nThreadCount << ", item count=" << nThreadItemCount * s_nThreadCount << " ..." );
214 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
219 CppUnitMini::ThreadPool pool( *this );
220 pool.add( new Popper<PQueue>( pool, testQueue ), s_nThreadCount );
222 CPPUNIT_MSG( " Pop, thread count=" << s_nThreadCount << ", item count=" << nThreadItemCount * s_nThreadCount << " ..." );
224 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
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);
234 nTotalPopped += pThread->m_nPopSuccess;
235 nTotalError += pThread->m_nPopError;
236 nTotalErrorEq += pThread->m_nPopErrorEq;
237 nTotalFailed += pThread->m_nPopFailed;
240 CPPUNIT_MSG( " Total: popped=" << nTotalPopped << ", empty pop=" << nTotalFailed
241 << "\n Errors: pop equal=" << nTotalErrorEq << ", priority violation=" << nTotalError
243 CPPUNIT_CHECK( nTotalPopped == nThreadItemCount * s_nThreadCount );
244 CPPUNIT_CHECK( nTotalError == 0 );
245 CPPUNIT_CHECK( nTotalErrorEq == 0 );
248 CPPUNIT_MSG( testQueue.statistics() );
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 );
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
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();
275 CPPUNIT_TEST_SUITE_REGISTRATION(pqueue::PQueue_Pop);