3 #ifndef CDSTEST_HDR_MICHAEL_H
4 #define CDSTEST_HDR_MICHAEL_H
6 #include "cppunit/cppunit_proxy.h"
7 #include <cds/container/details/michael_list_base.h>
10 namespace cc = cds::container;
11 namespace co = cds::container::opt;
13 class MichaelListTestHeader: public CppUnitMini::TestCase
17 int nUpdateExistsCall;
40 item(int key, int val)
61 bool operator ()(const T& v1, const T& v2 ) const
63 return v1.key() < v2.key();
67 bool operator ()(const T& v1, const Q& v2 ) const
73 bool operator ()(const Q& v1, const T& v2 ) const
81 int operator ()(const T& v1, const T& v2 ) const
83 if ( v1.key() < v2.key() )
85 return v1.key() > v2.key() ? 1 : 0;
89 int operator ()(const T& v1, const Q& v2 ) const
93 return v1.key() > v2 ? 1 : 0;
97 int operator ()(const Q& v1, const T& v2 ) const
101 return v1 > v2.key() ? 1 : 0;
105 struct insert_functor {
106 void operator ()( item& i )
108 i.nVal = i.nKey * 1033;
111 struct dummy_insert_functor {
112 void operator ()( item& /*i*/ )
114 // This functor should not be called
115 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_functor should not be called", __FILE__, __LINE__ );
119 struct erase_functor {
120 unsigned int nEraseCall;
126 void operator()( item const& /*i*/)
132 static void insert_function( item& i )
134 i.nVal = i.nKey * 1024;
136 static void dummy_insert_function( item& /*i*/ )
138 // This function should not be called
139 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_function should not be called", __FILE__, __LINE__ );
144 unsigned int m_nMultiplier;
146 check_value( unsigned int nMultiplier )
147 : m_nMultiplier( nMultiplier )
150 check_value( const check_value& s )
151 : m_nMultiplier( s.m_nMultiplier )
154 void operator()( item& i, int )
156 CPPUNIT_ASSERT_CURRENT( int(i.nKey * m_nMultiplier) == i.nVal );
160 struct check_exact_value {
163 check_exact_value( int nExpected )
164 : m_nExpected( nExpected )
167 check_exact_value( check_exact_value const& s)
168 : m_nExpected( s.m_nExpected )
171 void operator()( item& i, int )
173 CPPUNIT_ASSERT_CURRENT( i.nVal == m_nExpected );
177 struct dummy_check_value {
178 void operator()( item& /*i*/, int )
180 // This functor should not be called
181 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_check_value should not be called", __FILE__, __LINE__ );
185 struct update_functor {
186 void operator()( bool /*bNew*/, item& i, int /*n*/ )
188 i.nVal = i.nKey * 1024;
192 static void update_func( bool /*bNew*/, item& i, int n )
211 template <typename T1, typename T2>
212 bool operator()( T1 const& t1, T2 const& t2 ) const
214 return t1.nKey < t2.nKey;
219 template <class OrdList>
220 void test_with( OrdList& l )
222 typedef typename OrdList::value_type value_type;
224 // The list should be empty
225 CPPUNIT_ASSERT( l.empty() );
228 CPPUNIT_ASSERT( l.insert( 50 ) );
229 CPPUNIT_ASSERT( l.insert( item( 25 )) );
230 CPPUNIT_ASSERT( l.insert( item( 100 )) );
232 // insert failed - such key exists
233 CPPUNIT_ASSERT( !l.insert( 50 ) );
234 CPPUNIT_ASSERT( !l.insert( item( 100 )) );
238 // The list should not be empty
239 CPPUNIT_ASSERT( !l.empty() );
241 // and now the list is empty
242 CPPUNIT_ASSERT( l.empty() );
244 // Test insert with functor
246 CPPUNIT_ASSERT( l.insert( 100, insert_functor() ) );
250 CPPUNIT_ASSERT( l.insert( item( 25 ), std::ref( f ) ) );
251 CPPUNIT_ASSERT( !l.insert( item( 100 ), std::ref( f ) ) );
253 // Test insert with function
254 CPPUNIT_ASSERT( l.insert( 50, insert_function ));
255 CPPUNIT_ASSERT( !l.insert( 25, dummy_insert_function ));
256 CPPUNIT_ASSERT( !l.insert( 100, dummy_insert_functor() ));
258 // The list should not be empty
259 CPPUNIT_ASSERT( !l.empty() );
261 // Check inserted values
265 CPPUNIT_ASSERT( l.contains( 100 ));
266 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
270 CPPUNIT_ASSERT( l.contains( 25, lt<value_type>() ));
271 CPPUNIT_ASSERT( l.find_with( i, lt<value_type>(), std::ref( f ) ) );
274 CPPUNIT_ASSERT( l.contains( 50 ));
275 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
278 CPPUNIT_ASSERT( !l.contains( 10, lt<value_type>() ));
279 CPPUNIT_ASSERT( !l.find_with( i, lt<value_type>(), dummy_check_value() ));
281 CPPUNIT_ASSERT( !l.contains( 75 ));
282 CPPUNIT_ASSERT( !l.find( i, dummy_check_value() ));
284 CPPUNIT_ASSERT( !l.contains( 150 ));
285 CPPUNIT_ASSERT( !l.find( i, dummy_check_value() ));
288 // The list should not be empty
289 CPPUNIT_ASSERT( !l.empty() );
291 // and now the list is empty
292 CPPUNIT_ASSERT( l.empty() );
296 std::pair<bool, bool> updateResult;
298 updateResult = l.update( 100, update_functor() );
299 CPPUNIT_ASSERT( updateResult.first );
300 CPPUNIT_ASSERT( updateResult.second );
302 updateResult = l.update( 200, std::ref( f ) );
303 CPPUNIT_ASSERT( updateResult.first );
304 CPPUNIT_ASSERT( updateResult.second );
306 updateResult = l.update( 50, update_func );
307 CPPUNIT_ASSERT( updateResult.first );
308 CPPUNIT_ASSERT( updateResult.second );
312 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
314 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
316 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
318 // update existing key
319 updateResult = l.update( 200, update_func );
320 CPPUNIT_ASSERT( updateResult.first );
321 CPPUNIT_ASSERT( !updateResult.second );
323 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
325 updateResult = l.update( 50, update_functor() );
326 CPPUNIT_ASSERT( updateResult.first );
327 CPPUNIT_ASSERT( !updateResult.second );
329 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
332 // erase test (list: 50, 100, 200)
333 CPPUNIT_ASSERT( !l.empty() );
334 CPPUNIT_ASSERT( l.insert(160));
335 CPPUNIT_ASSERT( l.insert(250));
336 CPPUNIT_ASSERT( !l.empty() );
338 CPPUNIT_ASSERT( !l.erase( 150 ));
340 CPPUNIT_ASSERT( l.erase( 100 ));
341 CPPUNIT_ASSERT( !l.erase( 100 ));
343 CPPUNIT_ASSERT( l.erase_with( 200, lt<value_type>() ));
344 CPPUNIT_ASSERT( !l.erase_with( 200, lt<value_type>() ));
348 CPPUNIT_ASSERT( ef.nEraseCall == 0 );
349 CPPUNIT_ASSERT( l.erase_with( 160, lt<value_type>(), std::ref(ef) ));
350 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
351 CPPUNIT_ASSERT( !l.erase_with( 160, lt<value_type>(), std::ref(ef) ));
352 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
354 CPPUNIT_ASSERT( l.erase( 250, std::ref(ef) ));
355 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
356 CPPUNIT_ASSERT( !l.erase( 250, std::ref(ef) ));
357 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
360 CPPUNIT_ASSERT( l.erase( 50 ));
361 CPPUNIT_ASSERT( !l.erase( 50 ));
363 CPPUNIT_ASSERT( l.empty() );
367 CPPUNIT_ASSERT( l.empty() );
373 CPPUNIT_ASSERT( l.emplace( 501 ) );
374 CPPUNIT_ASSERT( l.emplace( 251, 152 ));
375 CPPUNIT_ASSERT( l.emplace( item( 1001 )) );
377 // insert failed - such key exists
378 CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
379 CPPUNIT_ASSERT( !l.emplace( 251, 10) );
382 CPPUNIT_ASSERT( l.find( i, check_exact_value(501*2) ));
384 CPPUNIT_ASSERT( l.find( i, check_exact_value(152) ));
386 CPPUNIT_ASSERT( l.find( i, check_exact_value(1001*2) ));
389 CPPUNIT_ASSERT( l.empty() );
395 for ( int i = 0; i < nCount; ++i )
396 CPPUNIT_ASSERT( l.insert(i) );
399 typename OrdList::iterator it( l.begin() );
400 typename OrdList::const_iterator cit( l.cbegin() );
401 CPPUNIT_CHECK( it == cit );
402 CPPUNIT_CHECK( it != l.end() );
403 CPPUNIT_CHECK( it != l.cend() );
404 CPPUNIT_CHECK( cit != l.end() );
405 CPPUNIT_CHECK( cit != l.cend() );
407 CPPUNIT_CHECK( it != cit );
408 CPPUNIT_CHECK( it != l.end() );
409 CPPUNIT_CHECK( it != l.cend() );
410 CPPUNIT_CHECK( cit != l.end() );
411 CPPUNIT_CHECK( cit != l.cend() );
413 CPPUNIT_CHECK( it == cit );
414 CPPUNIT_CHECK( it != l.end() );
415 CPPUNIT_CHECK( it != l.cend() );
416 CPPUNIT_CHECK( cit != l.end() );
417 CPPUNIT_CHECK( cit != l.cend() );
421 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
423 CPPUNIT_ASSERT( it->nKey == i );
426 // Check that we have visited all items
427 for ( int i = 0; i < nCount; ++i )
428 CPPUNIT_ASSERT( l.find( i, check_value(2) ));
431 CPPUNIT_ASSERT( l.empty() );
434 for ( int i = 0; i < nCount; ++i )
435 CPPUNIT_ASSERT( l.insert(i) );
438 const OrdList& rl = l;
439 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
440 // it->nVal = i * 2 ; // not!
441 CPPUNIT_ASSERT( it->nKey == i );
444 // Check that we have visited all items
445 for ( int i = 0; i < nCount; ++i )
446 CPPUNIT_ASSERT( l.find( i, check_value(2) ));
449 CPPUNIT_ASSERT( l.empty() );
453 template <typename OrdList>
456 typedef typename OrdList::guarded_ptr guarded_ptr;
457 typedef typename OrdList::value_type value_type;
462 static int const nLimit = 20;
464 for ( int i = 0; i < nLimit; i++ )
466 shuffle( arr, arr + nLimit );
469 for ( int i = 0; i < nLimit; ++i )
473 for ( int i = 0; i < nLimit; ++i ) {
477 CPPUNIT_ASSERT( gp );
478 CPPUNIT_ASSERT( !gp.empty());
479 CPPUNIT_CHECK( gp->nKey == nKey );
480 CPPUNIT_CHECK( gp->nVal == nKey * 2 );
483 gp = l.extract( nKey );
484 CPPUNIT_ASSERT( gp );
485 CPPUNIT_ASSERT( !gp.empty());
486 CPPUNIT_CHECK( gp->nKey == nKey );
487 CPPUNIT_CHECK( gp->nVal == nKey*2 );
491 CPPUNIT_CHECK( !gp );
492 CPPUNIT_CHECK( gp.empty());
493 CPPUNIT_CHECK( !l.extract( nKey));
494 CPPUNIT_CHECK( gp.empty());
496 CPPUNIT_ASSERT( l.empty());
497 CPPUNIT_CHECK( !l.get(arr[0]));
498 CPPUNIT_CHECK( gp.empty());
499 CPPUNIT_CHECK( !l.extract( arr[0]));
500 CPPUNIT_CHECK( gp.empty());
503 // extract_with/get_with
504 for ( int i = 0; i < nLimit; ++i )
508 for ( int i = 0; i < nLimit; ++i ) {
510 other_item key( nKey );
512 gp = l.get_with( key, other_less() );
513 CPPUNIT_ASSERT( gp );
514 CPPUNIT_ASSERT( !gp.empty());
515 CPPUNIT_CHECK( gp->nKey == nKey );
516 CPPUNIT_CHECK( gp->nVal == nKey * 2 );
519 gp = l.extract_with( key, other_less() );
520 CPPUNIT_ASSERT( gp );
521 CPPUNIT_ASSERT( !gp.empty());
522 CPPUNIT_CHECK( gp->nKey == nKey );
523 CPPUNIT_CHECK( gp->nVal == nKey*2 );
526 gp = l.get_with( key, other_less() );
527 CPPUNIT_CHECK( !gp );
528 CPPUNIT_CHECK( gp.empty());
529 CPPUNIT_CHECK( !l.extract_with( key, other_less()));
530 CPPUNIT_CHECK( gp.empty());
532 CPPUNIT_ASSERT( l.empty());
533 CPPUNIT_CHECK( !l.get_with(other_item(arr[0]), other_less()));
534 CPPUNIT_CHECK( gp.empty());
535 CPPUNIT_CHECK( !l.extract_with( other_item(arr[0]), other_less()));
536 CPPUNIT_CHECK( gp.empty());
540 template <typename OrdList>
546 static int const nLimit = 20;
548 typedef typename OrdList::rcu_lock rcu_lock;
549 typedef typename OrdList::value_type value_type;
550 typedef typename OrdList::gc rcu_type;
554 for (int i = 0; i < nLimit; ++i)
556 shuffle( a, a + nLimit );
559 for ( int i = 0; i < nLimit; ++i )
560 CPPUNIT_ASSERT( l.insert( a[i] ) );
562 typename OrdList::exempt_ptr ep;
563 typename OrdList::raw_ptr rp;
565 for ( int i = 0; i < nLimit; ++i ) {
569 CPPUNIT_ASSERT( rp );
570 CPPUNIT_CHECK( rp->nKey == a[i] );
571 CPPUNIT_CHECK( rp->nVal == a[i] * 2 );
575 ep = l.extract( a[i] );
576 CPPUNIT_ASSERT( ep );
577 CPPUNIT_ASSERT( !ep.empty() );
578 CPPUNIT_CHECK( ep->nKey == a[i] );
579 CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
584 CPPUNIT_CHECK( !l.get( a[i] ));
586 ep = l.extract( a[i] );
587 CPPUNIT_CHECK( !ep );
588 CPPUNIT_CHECK( ep.empty() );
590 CPPUNIT_ASSERT( l.empty() );
594 CPPUNIT_CHECK( !l.get( a[0] ));
596 CPPUNIT_CHECK( !l.extract( a[0] ) );
597 CPPUNIT_CHECK( ep.empty() );
599 // extract_with/get_with
600 for ( int i = 0; i < nLimit; ++i ) {
601 CPPUNIT_ASSERT( l.insert( a[i] ) );
604 for ( int i = 0; i < nLimit; ++i ) {
605 other_item itm( a[i] );
608 rp = l.get_with( itm, other_less() );
609 CPPUNIT_ASSERT( rp );
610 CPPUNIT_CHECK( rp->nKey == a[i] );
611 CPPUNIT_CHECK( rp->nVal == a[i] * 2 );
615 ep = l.extract_with( itm, other_less() );
616 CPPUNIT_ASSERT( ep );
617 CPPUNIT_ASSERT( !ep.empty() );
618 CPPUNIT_CHECK( ep->nKey == a[i] );
619 CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
624 CPPUNIT_CHECK( !l.get_with( itm, other_less()));
626 ep = l.extract_with( itm, other_less() );
627 CPPUNIT_CHECK( !ep );
628 CPPUNIT_CHECK( ep.empty() );
630 CPPUNIT_ASSERT( l.empty() );
634 CPPUNIT_CHECK( !l.get_with( other_item( 0 ), other_less()));
636 CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
637 CPPUNIT_CHECK( ep.empty() );
642 template <class OrdList>
645 typedef OrdList list;
646 typedef typename list::value_type value_type;
647 typedef std::pair<typename list::iterator, bool> update_result;
649 typename list::iterator it;
652 CPPUNIT_ASSERT( l.empty() );
653 CPPUNIT_ASSERT( l.insert(50) != l.end() );
654 CPPUNIT_ASSERT( !l.empty() );
656 update_result eres = l.update( item(100, 33) );
657 CPPUNIT_ASSERT( eres.second );
658 CPPUNIT_ASSERT( eres.first != l.end() );
659 CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() );
661 CPPUNIT_ASSERT( l.insert(100) == l.end() );
662 eres = l.update( item(50, 33) );
663 CPPUNIT_ASSERT( !eres.second );
664 CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 );
665 eres.first->nVal = 63;
667 it = l.contains( 33 );
668 CPPUNIT_ASSERT( it == l.end() );
670 it = l.contains( 50 );
671 CPPUNIT_ASSERT( it != l.end() );
672 CPPUNIT_ASSERT( it->nKey == 50 );
673 CPPUNIT_ASSERT( it->nVal == 63 );
675 it = l.contains( 100, lt<value_type>() );
676 CPPUNIT_ASSERT( it != l.end() );
677 CPPUNIT_ASSERT( it->nKey == 100 );
678 CPPUNIT_ASSERT( it->nVal == 33 );
680 it = l.contains( 150 );
681 CPPUNIT_ASSERT( it != l.end() );
682 CPPUNIT_ASSERT( it->nKey == 150 );
683 CPPUNIT_ASSERT( it->nVal == it->nKey * 2 );
685 CPPUNIT_ASSERT( !l.empty() );
687 CPPUNIT_ASSERT( l.empty() );
690 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end() );
691 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
692 CPPUNIT_ASSERT( l.emplace( item( 1001 )) != l.end() );
694 // insert failed - such key exists
695 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end() );
696 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end() );
698 it = l.contains( 501 );
699 CPPUNIT_ASSERT( it != l.end() );
700 CPPUNIT_ASSERT( it->nKey == 501 );
701 CPPUNIT_ASSERT( it->nVal == 501 * 2 );
703 it = l.contains( 251 );
704 CPPUNIT_ASSERT( it != l.end() );
705 CPPUNIT_ASSERT( it->nKey == 251 );
706 CPPUNIT_ASSERT( it->nVal == 152 );
708 it = l.contains( 1001 );
709 CPPUNIT_ASSERT( it != l.end() );
710 CPPUNIT_ASSERT( it->nKey == 1001 );
711 CPPUNIT_ASSERT( it->nVal == 1001 * 2 );
714 typename OrdList::iterator it( l.begin() );
715 typename OrdList::const_iterator cit( l.cbegin() );
716 CPPUNIT_CHECK( it == cit );
717 CPPUNIT_CHECK( it != l.end() );
718 CPPUNIT_CHECK( it != l.cend() );
719 CPPUNIT_CHECK( cit != l.end() );
720 CPPUNIT_CHECK( cit != l.cend() );
722 CPPUNIT_CHECK( it != cit );
723 CPPUNIT_CHECK( it != l.end() );
724 CPPUNIT_CHECK( it != l.cend() );
725 CPPUNIT_CHECK( cit != l.end() );
726 CPPUNIT_CHECK( cit != l.cend() );
728 CPPUNIT_CHECK( it == cit );
729 CPPUNIT_CHECK( it != l.end() );
730 CPPUNIT_CHECK( it != l.cend() );
731 CPPUNIT_CHECK( cit != l.end() );
732 CPPUNIT_CHECK( cit != l.cend() );
737 CPPUNIT_ASSERT( l.empty() );
752 void RCU_GPI_cmpmix();
757 void RCU_GPB_cmpmix();
762 void RCU_GPT_cmpmix();
767 void RCU_SHB_cmpmix();
772 void RCU_SHT_cmpmix();
780 CPPUNIT_TEST_SUITE(MichaelListTestHeader)
782 CPPUNIT_TEST(HP_less)
783 CPPUNIT_TEST(HP_cmpmix)
786 CPPUNIT_TEST(DHP_cmp)
787 CPPUNIT_TEST(DHP_less)
788 CPPUNIT_TEST(DHP_cmpmix)
791 CPPUNIT_TEST(RCU_GPI_cmp)
792 CPPUNIT_TEST(RCU_GPI_less)
793 CPPUNIT_TEST(RCU_GPI_cmpmix)
794 CPPUNIT_TEST(RCU_GPI_ic)
796 CPPUNIT_TEST(RCU_GPB_cmp)
797 CPPUNIT_TEST(RCU_GPB_less)
798 CPPUNIT_TEST(RCU_GPB_cmpmix)
799 CPPUNIT_TEST(RCU_GPB_ic)
801 CPPUNIT_TEST(RCU_GPT_cmp)
802 CPPUNIT_TEST(RCU_GPT_less)
803 CPPUNIT_TEST(RCU_GPT_cmpmix)
804 CPPUNIT_TEST(RCU_GPT_ic)
806 CPPUNIT_TEST(RCU_SHB_cmp)
807 CPPUNIT_TEST(RCU_SHB_less)
808 CPPUNIT_TEST(RCU_SHB_cmpmix)
809 CPPUNIT_TEST(RCU_SHB_ic)
811 CPPUNIT_TEST(RCU_SHT_cmp)
812 CPPUNIT_TEST(RCU_SHT_less)
813 CPPUNIT_TEST(RCU_SHT_cmpmix)
814 CPPUNIT_TEST(RCU_SHT_ic)
816 CPPUNIT_TEST(NOGC_cmp)
817 CPPUNIT_TEST(NOGC_less)
818 CPPUNIT_TEST(NOGC_cmpmix)
819 CPPUNIT_TEST(NOGC_ic)
820 CPPUNIT_TEST_SUITE_END()
823 } // namespace ordlist
825 #endif // #ifndef CDSTEST_HDR_MICHAEL_H