3 #include "cppunit/cppunit_proxy.h"
4 #include <cds/container/michael_list_base.h>
7 namespace cc = cds::container;
8 namespace co = cds::container::opt;
10 class MichaelListTestHeader: public CppUnitMini::TestCase
14 int nEnsureExistsCall;
37 item(int key, int val)
58 bool operator ()(const T& v1, const T& v2 ) const
60 return v1.key() < v2.key();
64 bool operator ()(const T& v1, const Q& v2 ) const
70 bool operator ()(const Q& v1, const T& v2 ) const
78 int operator ()(const T& v1, const T& v2 ) const
80 if ( v1.key() < v2.key() )
82 return v1.key() > v2.key() ? 1 : 0;
86 int operator ()(const T& v1, const Q& v2 ) const
90 return v1.key() > v2 ? 1 : 0;
94 int operator ()(const Q& v1, const T& v2 ) const
98 return v1 > v2.key() ? 1 : 0;
102 struct insert_functor {
103 void operator ()( item& i )
105 i.nVal = i.nKey * 1033;
108 struct dummy_insert_functor {
109 void operator ()( item& i )
111 // This functor should not be called
112 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_functor should not be called", __FILE__, __LINE__ );
116 struct erase_functor {
117 unsigned int nEraseCall;
123 void operator()( item const& /*i*/)
129 static void insert_function( item& i )
131 i.nVal = i.nKey * 1024;
133 static void dummy_insert_function( item& i )
135 // This function should not be called
136 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_function should not be called", __FILE__, __LINE__ );
141 unsigned int m_nMultiplier;
143 check_value( unsigned int nMultiplier )
144 : m_nMultiplier( nMultiplier )
147 check_value( const check_value& s )
148 : m_nMultiplier( s.m_nMultiplier )
151 void operator()( item& i, int )
153 CPPUNIT_ASSERT_CURRENT( int(i.nKey * m_nMultiplier) == i.nVal );
157 struct check_exact_value {
160 check_exact_value( int nExpected )
161 : m_nExpected( nExpected )
164 check_exact_value( check_exact_value const& s)
165 : m_nExpected( s.m_nExpected )
168 void operator()( item& i, int )
170 CPPUNIT_ASSERT_CURRENT( i.nVal == m_nExpected );
174 struct dummy_check_value {
175 void operator()( item& i, int )
177 // This functor should not be called
178 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_check_value should not be called", __FILE__, __LINE__ );
182 struct ensure_functor {
183 void operator()( bool bNew, item& i, int n )
185 i.nVal = i.nKey * 1024;
189 static void ensure_func( bool bNew, item& i, int n )
208 template <typename T1, typename T2>
209 bool operator()( T1 const& t1, T2 const& t2 ) const
211 return t1.nKey < t2.nKey;
216 template <class OrdList>
217 void test_with( OrdList& l )
219 typedef typename OrdList::value_type value_type;
221 // The list should be empty
222 CPPUNIT_ASSERT( l.empty() );
225 CPPUNIT_ASSERT( l.insert( 50 ) );
226 CPPUNIT_ASSERT( l.insert( item( 25 )) );
227 CPPUNIT_ASSERT( l.insert( item( 100 )) );
229 // insert failed - such key exists
230 CPPUNIT_ASSERT( !l.insert( 50 ) );
231 CPPUNIT_ASSERT( !l.insert( item( 100 )) );
235 // The list should not be empty
236 CPPUNIT_ASSERT( !l.empty() );
238 // and now the list is empty
239 CPPUNIT_ASSERT( l.empty() );
241 // Test insert with functor
243 CPPUNIT_ASSERT( l.insert( 100, insert_functor() ) );
247 CPPUNIT_ASSERT( l.insert( item(25), boost::ref(f)) );
248 CPPUNIT_ASSERT( !l.insert( item(100), boost::ref(f)) );
250 // Test insert with function
251 CPPUNIT_ASSERT( l.insert( 50, insert_function ));
252 CPPUNIT_ASSERT( !l.insert( 25, dummy_insert_function ));
253 CPPUNIT_ASSERT( !l.insert( 100, dummy_insert_functor() ));
255 // The list should not be empty
256 CPPUNIT_ASSERT( !l.empty() );
258 // Check inserted values
262 CPPUNIT_ASSERT( l.find( 100 ));
263 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
267 CPPUNIT_ASSERT( l.find_with( 25, lt<value_type>() ));
268 CPPUNIT_ASSERT( l.find_with( i, lt<value_type>(), boost::ref(f) ));
271 CPPUNIT_ASSERT( l.find( 50 ));
272 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
275 CPPUNIT_ASSERT( !l.find_with( 10, lt<value_type>() ));
276 CPPUNIT_ASSERT( !l.find_with( i, lt<value_type>(), dummy_check_value() ));
278 CPPUNIT_ASSERT( !l.find( 75 ));
279 CPPUNIT_ASSERT( !l.find( i, dummy_check_value() ));
281 CPPUNIT_ASSERT( !l.find( 150 ));
282 CPPUNIT_ASSERT( !l.find( i, dummy_check_value() ));
285 // The list should not be empty
286 CPPUNIT_ASSERT( !l.empty() );
288 // and now the list is empty
289 CPPUNIT_ASSERT( l.empty() );
293 std::pair<bool, bool> ensureResult;
295 ensureResult = l.ensure( 100, ensure_functor() );
296 CPPUNIT_ASSERT( ensureResult.first );
297 CPPUNIT_ASSERT( ensureResult.second );
299 ensureResult = l.ensure( 200, boost::ref(f) );
300 CPPUNIT_ASSERT( ensureResult.first );
301 CPPUNIT_ASSERT( ensureResult.second );
303 ensureResult = l.ensure( 50, ensure_func );
304 CPPUNIT_ASSERT( ensureResult.first );
305 CPPUNIT_ASSERT( ensureResult.second );
309 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
311 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
313 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
315 // ensure existing key
316 ensureResult = l.ensure( 200, ensure_func );
317 CPPUNIT_ASSERT( ensureResult.first );
318 CPPUNIT_ASSERT( !ensureResult.second );
320 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
322 ensureResult = l.ensure( 50, ensure_functor() );
323 CPPUNIT_ASSERT( ensureResult.first );
324 CPPUNIT_ASSERT( !ensureResult.second );
326 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
329 // erase test (list: 50, 100, 200)
330 CPPUNIT_ASSERT( !l.empty() );
331 CPPUNIT_ASSERT( l.insert(160));
332 CPPUNIT_ASSERT( l.insert(250));
333 CPPUNIT_ASSERT( !l.empty() );
335 CPPUNIT_ASSERT( !l.erase( 150 ));
337 CPPUNIT_ASSERT( l.erase( 100 ));
338 CPPUNIT_ASSERT( !l.erase( 100 ));
340 CPPUNIT_ASSERT( l.erase_with( 200, lt<value_type>() ));
341 CPPUNIT_ASSERT( !l.erase_with( 200, lt<value_type>() ));
345 CPPUNIT_ASSERT( ef.nEraseCall == 0 );
346 CPPUNIT_ASSERT( l.erase_with( 160, lt<value_type>(), cds::ref(ef) ));
347 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
348 CPPUNIT_ASSERT( !l.erase_with( 160, lt<value_type>(), cds::ref(ef) ));
349 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
351 CPPUNIT_ASSERT( l.erase( 250, cds::ref(ef) ));
352 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
353 CPPUNIT_ASSERT( !l.erase( 250, cds::ref(ef) ));
354 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
357 CPPUNIT_ASSERT( l.erase( 50 ));
358 CPPUNIT_ASSERT( !l.erase( 50 ));
360 CPPUNIT_ASSERT( l.empty() );
364 CPPUNIT_ASSERT( l.empty() );
366 #ifdef CDS_EMPLACE_SUPPORT
371 CPPUNIT_ASSERT( l.emplace( 501 ) );
372 CPPUNIT_ASSERT( l.emplace( 251, 152 ));
373 CPPUNIT_ASSERT( l.emplace( item( 1001 )) );
375 // insert failed - such key exists
376 CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
377 CPPUNIT_ASSERT( !l.emplace( 251, 10) );
380 CPPUNIT_ASSERT( l.find( i, check_exact_value(501*2) ));
382 CPPUNIT_ASSERT( l.find( i, check_exact_value(152) ));
384 CPPUNIT_ASSERT( l.find( i, check_exact_value(1001*2) ));
387 CPPUNIT_ASSERT( l.empty() );
394 for ( int i = 0; i < nCount; ++i )
395 CPPUNIT_ASSERT( l.insert(i) );
398 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
400 CPPUNIT_ASSERT( it->nKey == i );
403 // Check that we have visited all items
404 for ( int i = 0; i < nCount; ++i )
405 CPPUNIT_ASSERT( l.find( i, check_value(2) ));
408 CPPUNIT_ASSERT( l.empty() );
411 for ( int i = 0; i < nCount; ++i )
412 CPPUNIT_ASSERT( l.insert(i) );
415 const OrdList& rl = l;
416 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
417 // it->nVal = i * 2 ; // not!
418 CPPUNIT_ASSERT( it->nKey == i );
421 // Check that we have visited all items
422 for ( int i = 0; i < nCount; ++i )
423 CPPUNIT_ASSERT( l.find( i, check_value(2) ));
426 CPPUNIT_ASSERT( l.empty() );
430 template <typename OrdList>
433 typedef typename OrdList::guarded_ptr guarded_ptr;
434 typedef typename OrdList::value_type value_type;
439 static int const nLimit = 20;
441 for ( int i = 0; i < nLimit; i++ )
443 std::random_shuffle( arr, arr + nLimit );
446 for ( int i = 0; i < nLimit; ++i )
450 for ( int i = 0; i < nLimit; ++i ) {
453 CPPUNIT_ASSERT( l.get(gp, nKey));
454 CPPUNIT_ASSERT( !gp.empty());
455 CPPUNIT_CHECK( gp->nKey == nKey );
456 CPPUNIT_CHECK( gp->nVal == nKey * 2 );
459 CPPUNIT_ASSERT( l.extract(gp, nKey));
460 CPPUNIT_ASSERT( !gp.empty());
461 CPPUNIT_CHECK( gp->nKey == nKey );
462 CPPUNIT_CHECK( gp->nVal == nKey*2 );
465 CPPUNIT_CHECK( !l.get(gp, nKey));
466 CPPUNIT_CHECK( gp.empty());
467 CPPUNIT_CHECK( !l.extract( gp, nKey));
468 CPPUNIT_CHECK( gp.empty());
470 CPPUNIT_ASSERT( l.empty());
471 CPPUNIT_CHECK( !l.get(gp, arr[0]));
472 CPPUNIT_CHECK( gp.empty());
473 CPPUNIT_CHECK( !l.extract( gp, arr[0]));
474 CPPUNIT_CHECK( gp.empty());
477 // extract_with/get_with
478 for ( int i = 0; i < nLimit; ++i )
482 for ( int i = 0; i < nLimit; ++i ) {
484 other_item key( nKey );
486 CPPUNIT_ASSERT( l.get_with(gp, key, other_less()));
487 CPPUNIT_ASSERT( !gp.empty());
488 CPPUNIT_CHECK( gp->nKey == nKey );
489 CPPUNIT_CHECK( gp->nVal == nKey * 2 );
492 CPPUNIT_ASSERT( l.extract_with(gp, key, other_less()));
493 CPPUNIT_ASSERT( !gp.empty());
494 CPPUNIT_CHECK( gp->nKey == nKey );
495 CPPUNIT_CHECK( gp->nVal == nKey*2 );
498 CPPUNIT_CHECK( !l.get_with(gp, key, other_less()));
499 CPPUNIT_CHECK( gp.empty());
500 CPPUNIT_CHECK( !l.extract_with( gp, key, other_less()));
501 CPPUNIT_CHECK( gp.empty());
503 CPPUNIT_ASSERT( l.empty());
504 CPPUNIT_CHECK( !l.get_with(gp, other_item(arr[0]), other_less()));
505 CPPUNIT_CHECK( gp.empty());
506 CPPUNIT_CHECK( !l.extract_with( gp, other_item(arr[0]), other_less()));
507 CPPUNIT_CHECK( gp.empty());
511 template <typename OrdList>
517 static int const nLimit = 20;
519 typedef typename OrdList::rcu_lock rcu_lock;
520 typedef typename OrdList::value_type value_type;
521 typedef typename OrdList::gc rcu_type;
525 for (int i = 0; i < nLimit; ++i)
527 std::random_shuffle( a, a + nLimit );
530 for ( int i = 0; i < nLimit; ++i )
531 CPPUNIT_ASSERT( l.insert( a[i] ) );
533 typename OrdList::exempt_ptr ep;
535 for ( int i = 0; i < nLimit; ++i ) {
538 value_type * pGet = l.get( a[i] );
539 CPPUNIT_ASSERT( pGet != nullptr );
540 CPPUNIT_CHECK( pGet->nKey == a[i] );
541 CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
543 CPPUNIT_ASSERT( l.extract( ep, a[i] ));
544 CPPUNIT_ASSERT( !ep.empty() );
545 CPPUNIT_CHECK( ep->nKey == a[i] );
546 CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
551 CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
552 CPPUNIT_CHECK( !l.extract( ep, a[i] ));
553 CPPUNIT_CHECK( ep.empty() );
556 CPPUNIT_ASSERT( l.empty() );
560 CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
561 CPPUNIT_CHECK( !l.extract( ep, a[0] ) );
562 CPPUNIT_CHECK( ep.empty() );
565 // extract_with/get_with
566 for ( int i = 0; i < nLimit; ++i ) {
567 CPPUNIT_ASSERT( l.insert( a[i] ) );
570 for ( int i = 0; i < nLimit; ++i ) {
571 other_item itm( a[i] );
574 value_type * pGet = l.get_with( itm, other_less() );
575 CPPUNIT_ASSERT( pGet != nullptr );
576 CPPUNIT_CHECK( pGet->nKey == a[i] );
577 CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
579 CPPUNIT_ASSERT( l.extract_with( ep, itm, other_less() ));
580 CPPUNIT_ASSERT( !ep.empty() );
581 CPPUNIT_CHECK( ep->nKey == a[i] );
582 CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
587 CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
588 CPPUNIT_CHECK( !l.extract_with( ep, itm, other_less() ));
589 CPPUNIT_CHECK( ep.empty() );
592 CPPUNIT_ASSERT( l.empty() );
596 CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
597 CPPUNIT_CHECK( !l.extract_with( ep, other_item(0), other_less() ));
598 CPPUNIT_CHECK( ep.empty() );
604 template <class OrdList>
607 typedef OrdList list;
608 typedef typename list::value_type value_type;
609 typedef std::pair<typename list::iterator, bool> ensure_result;
611 typename list::iterator it;
614 CPPUNIT_ASSERT( l.empty() );
615 CPPUNIT_ASSERT( l.insert(50) != l.end() );
616 CPPUNIT_ASSERT( !l.empty() );
618 ensure_result eres = l.ensure( item(100, 33) );
619 CPPUNIT_ASSERT( eres.second );
620 CPPUNIT_ASSERT( eres.first != l.end() );
621 CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() );
623 CPPUNIT_ASSERT( l.insert(100) == l.end() );
624 eres = l.ensure( item(50, 33) );
625 CPPUNIT_ASSERT( !eres.second );
626 CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 );
627 eres.first->nVal = 63;
630 CPPUNIT_ASSERT( it == l.end() );
633 CPPUNIT_ASSERT( it != l.end() );
634 CPPUNIT_ASSERT( it->nKey == 50 );
635 CPPUNIT_ASSERT( it->nVal == 63 );
637 it = l.find_with( 100, lt<value_type>() );
638 CPPUNIT_ASSERT( it != l.end() );
639 CPPUNIT_ASSERT( it->nKey == 100 );
640 CPPUNIT_ASSERT( it->nVal == 33 );
643 CPPUNIT_ASSERT( it != l.end() );
644 CPPUNIT_ASSERT( it->nKey == 150 );
645 CPPUNIT_ASSERT( it->nVal == it->nKey * 2 );
647 CPPUNIT_ASSERT( !l.empty() );
649 CPPUNIT_ASSERT( l.empty() );
651 #ifdef CDS_EMPLACE_SUPPORT
653 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end() );
654 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
655 CPPUNIT_ASSERT( l.emplace( item( 1001 )) != l.end() );
657 // insert failed - such key exists
658 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end() );
659 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end() );
662 CPPUNIT_ASSERT( it != l.end() );
663 CPPUNIT_ASSERT( it->nKey == 501 );
664 CPPUNIT_ASSERT( it->nVal == 501 * 2 );
667 CPPUNIT_ASSERT( it != l.end() );
668 CPPUNIT_ASSERT( it->nKey == 251 );
669 CPPUNIT_ASSERT( it->nVal == 152 );
672 CPPUNIT_ASSERT( it != l.end() );
673 CPPUNIT_ASSERT( it->nKey == 1001 );
674 CPPUNIT_ASSERT( it->nVal == 1001 * 2 );
677 CPPUNIT_ASSERT( l.empty() );
698 void RCU_GPI_cmpmix();
703 void RCU_GPB_cmpmix();
708 void RCU_GPT_cmpmix();
713 void RCU_SHB_cmpmix();
718 void RCU_SHT_cmpmix();
726 CPPUNIT_TEST_SUITE(MichaelListTestHeader)
728 CPPUNIT_TEST(HP_less)
729 CPPUNIT_TEST(HP_cmpmix)
732 CPPUNIT_TEST(PTB_cmp)
733 CPPUNIT_TEST(PTB_less)
734 CPPUNIT_TEST(PTB_cmpmix)
737 CPPUNIT_TEST(HRC_cmp)
738 CPPUNIT_TEST(HRC_less)
739 CPPUNIT_TEST(HRC_cmpmix)
742 CPPUNIT_TEST(RCU_GPI_cmp)
743 CPPUNIT_TEST(RCU_GPI_less)
744 CPPUNIT_TEST(RCU_GPI_cmpmix)
745 CPPUNIT_TEST(RCU_GPI_ic)
747 CPPUNIT_TEST(RCU_GPB_cmp)
748 CPPUNIT_TEST(RCU_GPB_less)
749 CPPUNIT_TEST(RCU_GPB_cmpmix)
750 CPPUNIT_TEST(RCU_GPB_ic)
752 CPPUNIT_TEST(RCU_GPT_cmp)
753 CPPUNIT_TEST(RCU_GPT_less)
754 CPPUNIT_TEST(RCU_GPT_cmpmix)
755 CPPUNIT_TEST(RCU_GPT_ic)
757 CPPUNIT_TEST(RCU_SHB_cmp)
758 CPPUNIT_TEST(RCU_SHB_less)
759 CPPUNIT_TEST(RCU_SHB_cmpmix)
760 CPPUNIT_TEST(RCU_SHB_ic)
762 CPPUNIT_TEST(RCU_SHT_cmp)
763 CPPUNIT_TEST(RCU_SHT_less)
764 CPPUNIT_TEST(RCU_SHT_cmpmix)
765 CPPUNIT_TEST(RCU_SHT_ic)
767 CPPUNIT_TEST(NOGC_cmp)
768 CPPUNIT_TEST(NOGC_less)
769 CPPUNIT_TEST(NOGC_cmpmix)
770 CPPUNIT_TEST(NOGC_ic)
771 CPPUNIT_TEST_SUITE_END()
774 } // namespace ordlist