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 #ifndef CDSTEST_HDR_PQUEUE_H
32 #define CDSTEST_HDR_PQUEUE_H
34 #include "cppunit/cppunit_proxy.h"
35 #include "size_check.h"
37 #include <functional> // ref
39 namespace priority_queue {
42 static size_t const c_nCapacity = 1024 * 16;
58 template <typename PQueue>
60 static size_t const nCapacity = c_nCapacity;
64 class PQueueHdrTest: public CppUnitMini::TestCase
67 static size_t const c_nCapacity = pqueue::c_nCapacity;
70 static key_type const c_nMinValue = -123;
79 value_type( value_type const& kv )
84 value_type( key_type key )
89 value_type( key_type key, int val )
94 value_type( std::pair<key_type, int> const& p )
101 int operator()( value_type k1, value_type k2 ) const
108 bool operator()( value_type k1, value_type k2 ) const
114 template <typename T>
121 data_array( size_t nSize )
122 : pFirst( new T[nSize] )
123 , pLast( pFirst + nSize )
125 key_type i = c_nMinValue;
126 for ( T * p = pFirst; p != pLast; ++p, ++i )
129 shuffle( pFirst, pLast );
137 T * begin() { return pFirst; }
138 T * end() { return pLast ; }
141 return pLast - pFirst;
146 template <class PQueue>
147 void test_bounded_with( PQueue& pq )
149 data_array<value_type> arr( pq.capacity() );
150 value_type * pFirst = arr.begin();
151 value_type * pLast = pFirst + pq.capacity();
153 CPPUNIT_ASSERT( pq.empty() );
154 CPPUNIT_ASSERT( pq.size() == 0 );
155 CPPUNIT_ASSERT_EX( pq.capacity() == pqueue::constants<PQueue>::nCapacity,
156 "pq.capacity() = " << pq.capacity() << ", pqueue::constants<PQueue>::nCapacity = " << pqueue::constants<PQueue>::nCapacity
162 for ( value_type * p = pFirst; p < pLast; ++p ) {
163 switch ( pq.size() & 3 ) {
165 CPPUNIT_ASSERT( pq.push_with( [p]( value_type& dest ) { dest = *p; } ));
168 CPPUNIT_ASSERT( pq.emplace( p->k, p->v ));
171 CPPUNIT_ASSERT( pq.emplace( std::make_pair( p->k, p->v ) ));
174 CPPUNIT_ASSERT( pq.push( *p ));
176 CPPUNIT_ASSERT( !pq.empty() );
177 CPPUNIT_ASSERT( pq.size() == ++nSize );
180 CPPUNIT_ASSERT( pq.full() );
181 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
184 key_type k = c_nMinValue + key_type(c_nCapacity);
185 CPPUNIT_ASSERT( !pq.push( k ));
186 CPPUNIT_ASSERT( pq.full() );
187 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
190 key_type nPrev = c_nMinValue + key_type(pq.capacity()) - 1;
193 CPPUNIT_ASSERT( pq.pop(kv) );
194 CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
196 CPPUNIT_ASSERT( pq.size() == pq.capacity() - 1 );
197 CPPUNIT_ASSERT( !pq.full() );
198 CPPUNIT_ASSERT( !pq.empty() );
201 while ( pq.size() > 1 ) {
202 if ( pq.size() & 1 ) {
203 CPPUNIT_ASSERT( pq.pop(kv) );
204 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
208 CPPUNIT_ASSERT( pq.pop_with( [&key]( value_type& src ) { key = src.k; } ) );
209 CPPUNIT_CHECK_EX( key == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << key );
214 CPPUNIT_ASSERT( pq.size() == nSize );
217 CPPUNIT_ASSERT( !pq.full() );
218 CPPUNIT_ASSERT( !pq.empty() );
219 CPPUNIT_ASSERT( pq.size() == 1 );
221 CPPUNIT_ASSERT( pq.pop(kv) );
222 CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
224 CPPUNIT_ASSERT( !pq.full() );
225 CPPUNIT_ASSERT( pq.empty() );
226 CPPUNIT_ASSERT( pq.size() == 0 );
229 for ( value_type * p = pFirst; p < pLast; ++p ) {
230 CPPUNIT_ASSERT( pq.push( *p ));
232 CPPUNIT_ASSERT( !pq.empty() );
233 CPPUNIT_ASSERT( pq.full() );
234 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
236 CPPUNIT_ASSERT( pq.empty() );
237 CPPUNIT_ASSERT( !pq.full() );
238 CPPUNIT_ASSERT( pq.size() == 0 );
241 for ( value_type * p = pFirst; p < pLast; ++p ) {
242 CPPUNIT_ASSERT( pq.push( *p ));
244 CPPUNIT_ASSERT( !pq.empty() );
245 CPPUNIT_ASSERT( pq.full() );
246 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
249 pqueue::disposer disp;
250 pq.clear_with( std::ref(disp) );
251 CPPUNIT_ASSERT( pq.empty() );
252 CPPUNIT_ASSERT( !pq.full() );
253 CPPUNIT_ASSERT( pq.size() == 0 );
254 CPPUNIT_ASSERT( disp.m_nCallCount == pq.capacity() );
258 template <class PQueue>
261 std::unique_ptr< PQueue > pq( new PQueue( 0 )); // argument should be ignored for static buffer
262 test_bounded_with( *pq );
264 template <class PQueue>
267 PQueue pq( c_nCapacity );
268 test_bounded_with( pq );
271 template <class PQueue>
276 data_array<value_type> arr( c_nCapacity );
277 value_type * pFirst = arr.begin();
278 value_type * pLast = pFirst + c_nCapacity;
280 CPPUNIT_ASSERT( pq.empty() );
281 CPPUNIT_ASSERT( pq.size() == 0 );
286 for ( value_type * p = pFirst; p < pLast; ++p ) {
287 CPPUNIT_ASSERT( pq.push( *p ));
288 CPPUNIT_ASSERT( !pq.empty() );
289 CPPUNIT_ASSERT( pq.size() == ++nSize );
292 CPPUNIT_ASSERT( pq.size() == c_nCapacity );
295 key_type nPrev = c_nMinValue + key_type(c_nCapacity) - 1;
298 CPPUNIT_ASSERT( pq.pop(kv) );
299 CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
301 CPPUNIT_ASSERT( pq.size() == c_nCapacity - 1 );
302 CPPUNIT_ASSERT( !pq.empty() );
305 while ( pq.size() > 1 ) {
306 CPPUNIT_ASSERT( pq.pop(kv) );
307 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
311 CPPUNIT_ASSERT( pq.size() == nSize );
314 CPPUNIT_ASSERT( !pq.empty() );
315 CPPUNIT_ASSERT( pq.size() == 1 );
317 CPPUNIT_ASSERT( pq.pop(kv) );
318 CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
320 CPPUNIT_ASSERT( pq.empty() );
321 CPPUNIT_ASSERT( pq.size() == 0 );
324 for ( value_type * p = pFirst; p < pLast; ++p ) {
325 CPPUNIT_ASSERT( pq.push( *p ));
327 CPPUNIT_ASSERT( !pq.empty() );
328 CPPUNIT_ASSERT( pq.size() == c_nCapacity );
331 CPPUNIT_ASSERT( pq.empty() );
332 CPPUNIT_ASSERT( pq.size() == 0 );
337 void MSPQueue_st_cmp();
338 void MSPQueue_st_less();
339 void MSPQueue_st_cmpless();
340 void MSPQueue_st_cmp_mtx();
342 void MSPQueue_dyn_cmp();
343 void MSPQueue_dyn_less();
344 void MSPQueue_dyn_cmpless();
345 void MSPQueue_dyn_cmp_mtx();
347 void FCPQueue_vector();
348 void FCPQueue_vector_stat();
349 void FCPQueue_vector_mutex();
350 void FCPQueue_deque();
351 void FCPQueue_deque_stat();
352 void FCPQueue_deque_mutex();
353 void FCPQueue_boost_deque();
354 void FCPQueue_boost_deque_stat();
355 void FCPQueue_stablevector();
356 void FCPQueue_stablevector_stat();
358 CPPUNIT_TEST_SUITE(PQueueHdrTest)
359 CPPUNIT_TEST(MSPQueue_st)
360 CPPUNIT_TEST(MSPQueue_st_cmp)
361 CPPUNIT_TEST(MSPQueue_st_less)
362 CPPUNIT_TEST(MSPQueue_st_cmpless)
363 CPPUNIT_TEST(MSPQueue_st_cmp_mtx)
364 CPPUNIT_TEST(MSPQueue_dyn)
365 CPPUNIT_TEST(MSPQueue_dyn_cmp)
366 CPPUNIT_TEST(MSPQueue_dyn_less)
367 CPPUNIT_TEST(MSPQueue_dyn_cmpless)
368 CPPUNIT_TEST(MSPQueue_dyn_cmp_mtx)
370 CPPUNIT_TEST(FCPQueue_vector)
371 CPPUNIT_TEST(FCPQueue_vector_stat)
372 CPPUNIT_TEST(FCPQueue_vector_mutex)
373 CPPUNIT_TEST(FCPQueue_deque)
374 CPPUNIT_TEST(FCPQueue_deque_stat)
375 CPPUNIT_TEST(FCPQueue_deque_mutex)
376 CPPUNIT_TEST(FCPQueue_boost_deque)
377 CPPUNIT_TEST(FCPQueue_boost_deque_stat)
378 CPPUNIT_TEST(FCPQueue_stablevector)
379 CPPUNIT_TEST(FCPQueue_stablevector_stat)
380 CPPUNIT_TEST_SUITE_END()
383 } // namespace priority_queue
387 struct less<priority_queue::PQueueHdrTest::value_type>
389 bool operator()( priority_queue::PQueueHdrTest::value_type const& v1, priority_queue::PQueueHdrTest::value_type const& v2) const
391 return priority_queue::PQueueHdrTest::less()( v1, v2 );
396 #endif // #ifndef CDSTEST_HDR_PQUEUE_H