3 #ifndef CDSHDRTEST_PQUEUE_H
4 #define CDSHDRTEST_PQUEUE_H
6 #include "cppunit/cppunit_proxy.h"
7 #include "size_check.h"
9 #include <functional> // ref
11 namespace priority_queue {
14 static size_t const c_nCapacity = 1024 * 16;
24 void operator()( T& p )
30 template <typename PQueue>
32 static size_t const nCapacity = c_nCapacity;
36 class PQueueHdrTest: public CppUnitMini::TestCase
39 static size_t const c_nCapacity = pqueue::c_nCapacity;
42 static key_type const c_nMinValue = -123;
51 value_type( value_type const& kv )
56 value_type( key_type key )
61 value_type( key_type key, int val )
66 value_type( std::pair<key_type, int> const& p )
73 int operator()( value_type k1, value_type k2 ) const
80 bool operator()( value_type k1, value_type k2 ) const
93 data_array( size_t nSize )
94 : pFirst( new T[nSize] )
95 , pLast( pFirst + nSize )
97 key_type i = c_nMinValue;
98 for ( T * p = pFirst; p != pLast; ++p, ++i )
101 std::random_shuffle( pFirst, pLast );
109 T * begin() { return pFirst; }
110 T * end() { return pLast ; }
113 return pLast - pFirst;
119 void operator()( int& dest, value_type const& src ) const
126 template <class PQueue>
127 void test_bounded_with( PQueue& pq )
129 data_array<value_type> arr( pq.capacity() );
130 value_type * pFirst = arr.begin();
131 value_type * pLast = pFirst + pq.capacity();
133 CPPUNIT_ASSERT( pq.empty() );
134 CPPUNIT_ASSERT( pq.size() == 0 );
135 CPPUNIT_ASSERT_EX( pq.capacity() == pqueue::constants<PQueue>::nCapacity,
136 "pq.capacity() = " << pq.capacity() << ", pqueue::constants<PQueue>::nCapacity = " << pqueue::constants<PQueue>::nCapacity
142 for ( value_type * p = pFirst; p < pLast; ++p ) {
143 switch ( pq.size() & 3 ) {
145 CPPUNIT_ASSERT( pq.emplace( p->k, p->v ));
148 CPPUNIT_ASSERT( pq.emplace( std::make_pair( p->k, p->v ) ));
151 CPPUNIT_ASSERT( pq.push( *p ));
153 CPPUNIT_ASSERT( !pq.empty() );
154 CPPUNIT_ASSERT( pq.size() == ++nSize );
157 CPPUNIT_ASSERT( pq.full() );
158 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
161 key_type k = c_nMinValue + key_type(c_nCapacity);
162 CPPUNIT_ASSERT( !pq.push( k ));
163 CPPUNIT_ASSERT( pq.full() );
164 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
167 key_type nPrev = c_nMinValue + key_type(pq.capacity()) - 1;
170 CPPUNIT_ASSERT( pq.pop(kv) );
171 CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
173 CPPUNIT_ASSERT( pq.size() == pq.capacity() - 1 );
174 CPPUNIT_ASSERT( !pq.full() );
175 CPPUNIT_ASSERT( !pq.empty() );
178 while ( pq.size() > 1 ) {
179 if ( pq.size() & 1 ) {
180 CPPUNIT_ASSERT( pq.pop(kv) );
181 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
185 CPPUNIT_ASSERT( pq.pop_with( key, move_functor() ));
186 CPPUNIT_CHECK_EX( key == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << key );
191 CPPUNIT_ASSERT( pq.size() == nSize );
194 CPPUNIT_ASSERT( !pq.full() );
195 CPPUNIT_ASSERT( !pq.empty() );
196 CPPUNIT_ASSERT( pq.size() == 1 );
198 CPPUNIT_ASSERT( pq.pop(kv) );
199 CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
201 CPPUNIT_ASSERT( !pq.full() );
202 CPPUNIT_ASSERT( pq.empty() );
203 CPPUNIT_ASSERT( pq.size() == 0 );
206 for ( value_type * p = pFirst; p < pLast; ++p ) {
207 CPPUNIT_ASSERT( pq.push( *p ));
209 CPPUNIT_ASSERT( !pq.empty() );
210 CPPUNIT_ASSERT( pq.full() );
211 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
213 CPPUNIT_ASSERT( pq.empty() );
214 CPPUNIT_ASSERT( !pq.full() );
215 CPPUNIT_ASSERT( pq.size() == 0 );
218 for ( value_type * p = pFirst; p < pLast; ++p ) {
219 CPPUNIT_ASSERT( pq.push( *p ));
221 CPPUNIT_ASSERT( !pq.empty() );
222 CPPUNIT_ASSERT( pq.full() );
223 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
226 pqueue::disposer disp;
227 pq.clear_with( std::ref(disp) );
228 CPPUNIT_ASSERT( pq.empty() );
229 CPPUNIT_ASSERT( !pq.full() );
230 CPPUNIT_ASSERT( pq.size() == 0 );
231 CPPUNIT_ASSERT( disp.m_nCallCount == pq.capacity() );
235 template <class PQueue>
238 PQueue pq( 0 ); // argument should be ignored for static buffer
239 test_bounded_with( pq );
241 template <class PQueue>
244 PQueue pq( c_nCapacity );
245 test_bounded_with( pq );
248 template <class PQueue>
253 data_array<value_type> arr( c_nCapacity );
254 value_type * pFirst = arr.begin();
255 value_type * pLast = pFirst + c_nCapacity;
257 CPPUNIT_ASSERT( pq.empty() );
258 CPPUNIT_ASSERT( pq.size() == 0 );
263 for ( value_type * p = pFirst; p < pLast; ++p ) {
264 CPPUNIT_ASSERT( pq.push( *p ));
265 CPPUNIT_ASSERT( !pq.empty() );
266 CPPUNIT_ASSERT( pq.size() == ++nSize );
269 CPPUNIT_ASSERT( pq.size() == c_nCapacity );
272 key_type nPrev = c_nMinValue + key_type(c_nCapacity) - 1;
275 CPPUNIT_ASSERT( pq.pop(kv) );
276 CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
278 CPPUNIT_ASSERT( pq.size() == c_nCapacity - 1 );
279 CPPUNIT_ASSERT( !pq.empty() );
282 while ( pq.size() > 1 ) {
283 CPPUNIT_ASSERT( pq.pop(kv) );
284 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
288 CPPUNIT_ASSERT( pq.size() == nSize );
291 CPPUNIT_ASSERT( !pq.empty() );
292 CPPUNIT_ASSERT( pq.size() == 1 );
294 CPPUNIT_ASSERT( pq.pop(kv) );
295 CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
297 CPPUNIT_ASSERT( pq.empty() );
298 CPPUNIT_ASSERT( pq.size() == 0 );
301 for ( value_type * p = pFirst; p < pLast; ++p ) {
302 CPPUNIT_ASSERT( pq.push( *p ));
304 CPPUNIT_ASSERT( !pq.empty() );
305 CPPUNIT_ASSERT( pq.size() == c_nCapacity );
308 CPPUNIT_ASSERT( pq.empty() );
309 CPPUNIT_ASSERT( pq.size() == 0 );
314 void MSPQueue_st_cmp();
315 void MSPQueue_st_less();
316 void MSPQueue_st_cmpless();
317 void MSPQueue_st_cmp_mtx();
319 void MSPQueue_dyn_cmp();
320 void MSPQueue_dyn_less();
321 void MSPQueue_dyn_cmpless();
322 void MSPQueue_dyn_cmp_mtx();
324 void FCPQueue_vector();
325 void FCPQueue_vector_stat();
326 void FCPQueue_vector_mutex();
327 void FCPQueue_deque();
328 void FCPQueue_deque_stat();
329 void FCPQueue_deque_mutex();
330 void FCPQueue_boost_deque();
331 void FCPQueue_boost_deque_stat();
332 void FCPQueue_stablevector();
333 void FCPQueue_stablevector_stat();
335 CPPUNIT_TEST_SUITE(PQueueHdrTest)
336 CPPUNIT_TEST(MSPQueue_st)
337 CPPUNIT_TEST(MSPQueue_st_cmp)
338 CPPUNIT_TEST(MSPQueue_st_less)
339 CPPUNIT_TEST(MSPQueue_st_cmpless)
340 CPPUNIT_TEST(MSPQueue_st_cmp_mtx)
341 CPPUNIT_TEST(MSPQueue_dyn)
342 CPPUNIT_TEST(MSPQueue_dyn_cmp)
343 CPPUNIT_TEST(MSPQueue_dyn_less)
344 CPPUNIT_TEST(MSPQueue_dyn_cmpless)
345 CPPUNIT_TEST(MSPQueue_dyn_cmp_mtx)
347 CPPUNIT_TEST(FCPQueue_vector)
348 CPPUNIT_TEST(FCPQueue_vector_stat)
349 CPPUNIT_TEST(FCPQueue_vector_mutex)
350 CPPUNIT_TEST(FCPQueue_deque)
351 CPPUNIT_TEST(FCPQueue_deque_stat)
352 CPPUNIT_TEST(FCPQueue_deque_mutex)
353 CPPUNIT_TEST(FCPQueue_boost_deque)
354 CPPUNIT_TEST(FCPQueue_boost_deque_stat)
355 CPPUNIT_TEST(FCPQueue_stablevector)
356 CPPUNIT_TEST(FCPQueue_stablevector_stat)
357 CPPUNIT_TEST_SUITE_END()
360 } // namespace priority_queue
364 struct less<priority_queue::PQueueHdrTest::value_type>
366 bool operator()( priority_queue::PQueueHdrTest::value_type const& v1, priority_queue::PQueueHdrTest::value_type const& v2) const
368 return priority_queue::PQueueHdrTest::less()( v1, v2 );
373 #endif // #ifndef CDSHDRTEST_PQUEUE_H