3 #include "cppunit/cppunit_proxy.h"
4 #include <cds/container/details/lazy_list_base.h>
7 namespace cc = cds::container;
8 namespace co = cds::container::opt;
10 class LazyListTestHeader: 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 static void insert_function( item& i )
118 i.nVal = i.nKey * 1024;
120 static void dummy_insert_function( item& /*i*/ )
122 // This function should not be called
123 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_function should not be called", __FILE__, __LINE__ );
126 struct erase_functor {
127 unsigned int nEraseCall;
133 void operator()( item const& /*i*/)
140 unsigned int m_nMultiplier;
142 check_value( unsigned int nMultiplier )
143 : m_nMultiplier( nMultiplier )
146 check_value( const check_value& s )
147 : m_nMultiplier( s.m_nMultiplier )
150 void operator()( item& i, int )
152 CPPUNIT_ASSERT_CURRENT( int(i.nKey * m_nMultiplier) == i.nVal );
156 struct check_exact_value {
159 check_exact_value( int nExpected )
160 : m_nExpected( nExpected )
163 check_exact_value( check_exact_value const& s)
164 : m_nExpected( s.m_nExpected )
167 void operator()( item& i, int )
169 CPPUNIT_ASSERT_CURRENT( i.nVal == m_nExpected );
173 struct dummy_check_value {
174 void operator()( item& /*i*/, int )
176 // This functor should not be called
177 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_check_value should not be called", __FILE__, __LINE__ );
181 struct ensure_functor {
182 void operator()( bool /*bNew*/, item& i, int n )
184 i.nVal = i.nKey * 1024;
188 static void ensure_func( bool /*bNew*/, item& i, int n )
207 template <typename T1, typename T2>
208 bool operator()( T1 const& t1, T2 const& t2 ) const
210 return t1.nKey < t2.nKey;
215 template <class OrdList>
216 void test_with( OrdList& l )
218 typedef typename OrdList::value_type value_type;
220 // The list should be empty
221 CPPUNIT_ASSERT( l.empty() );
224 CPPUNIT_ASSERT( l.insert( 50 ) );
225 CPPUNIT_ASSERT( l.insert( item( 25 )) );
226 CPPUNIT_ASSERT( l.insert( item( 100 )) );
228 // insert failed - such key exists
229 CPPUNIT_ASSERT( !l.insert( 50 ) );
230 CPPUNIT_ASSERT( !l.insert( item( 100 )) );
234 // The list should not be empty
235 CPPUNIT_ASSERT( !l.empty() );
237 // and now the list is empty
238 CPPUNIT_ASSERT( l.empty() );
240 // Test insert with functor
242 CPPUNIT_ASSERT( l.insert( 100, insert_functor() ) );
246 CPPUNIT_ASSERT( l.insert( item( 25 ), std::ref( f ) ) );
247 CPPUNIT_ASSERT( !l.insert( item( 100 ), std::ref( f ) ) );
249 // Test insert with function
250 CPPUNIT_ASSERT( l.insert( 50, insert_function ));
251 CPPUNIT_ASSERT( !l.insert( 25, dummy_insert_function ));
252 CPPUNIT_ASSERT( !l.insert( 100, dummy_insert_functor() ));
254 // The list should not be empty
255 CPPUNIT_ASSERT( !l.empty() );
257 // 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>(), std::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, std::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>(), std::ref(ef) ));
347 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
348 CPPUNIT_ASSERT( !l.erase_with( 160, lt<value_type>(), std::ref(ef) ));
349 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
351 CPPUNIT_ASSERT( l.erase( 250, std::ref(ef) ));
352 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
353 CPPUNIT_ASSERT( !l.erase( 250, std::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() );
369 CPPUNIT_ASSERT( l.emplace( 501 ) );
370 CPPUNIT_ASSERT( l.emplace( 251, 152 ));
371 CPPUNIT_ASSERT( l.emplace( item( 1001 )) );
373 // insert failed - such key exists
374 CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
375 CPPUNIT_ASSERT( !l.emplace( 251, 10) );
378 CPPUNIT_ASSERT( l.find( i, check_exact_value(501*2) ));
380 CPPUNIT_ASSERT( l.find( i, check_exact_value(152) ));
382 CPPUNIT_ASSERT( l.find( i, check_exact_value(1001*2) ));
385 CPPUNIT_ASSERT( l.empty() );
391 for ( int i = 0; i < nCount; ++i )
392 CPPUNIT_ASSERT( l.insert( i ) );
395 typename OrdList::iterator it( l.begin() );
396 typename OrdList::const_iterator cit( l.cbegin() );
397 CPPUNIT_CHECK( it == cit );
398 CPPUNIT_CHECK( it != l.end() );
399 CPPUNIT_CHECK( it != l.cend() );
400 CPPUNIT_CHECK( cit != l.end() );
401 CPPUNIT_CHECK( cit != l.cend() );
403 CPPUNIT_CHECK( it != cit );
404 CPPUNIT_CHECK( it != l.end() );
405 CPPUNIT_CHECK( it != l.cend() );
406 CPPUNIT_CHECK( cit != l.end() );
407 CPPUNIT_CHECK( cit != l.cend() );
409 CPPUNIT_CHECK( it == cit );
410 CPPUNIT_CHECK( it != l.end() );
411 CPPUNIT_CHECK( it != l.cend() );
412 CPPUNIT_CHECK( cit != l.end() );
413 CPPUNIT_CHECK( cit != l.cend() );
417 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
419 CPPUNIT_ASSERT( it->nKey == i );
422 // Check that we have visited all items
423 for ( int i = 0; i < nCount; ++i )
424 CPPUNIT_ASSERT( l.find( i, check_value(2) ));
427 CPPUNIT_ASSERT( l.empty() );
430 for ( int i = 0; i < nCount; ++i )
431 CPPUNIT_ASSERT( l.insert(i) );
434 const OrdList& rl = l;
435 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
436 // it->nVal = i * 2 ; // not!
437 CPPUNIT_ASSERT( it->nKey == i );
440 // Check that we have visited all items
441 for ( int i = 0; i < nCount; ++i )
442 CPPUNIT_ASSERT( l.find_with( i, lt<value_type>(), check_value(2) ));
445 CPPUNIT_ASSERT( l.empty() );
449 template <class OrdList>
452 typedef typename OrdList::guarded_ptr guarded_ptr;
453 typedef typename OrdList::value_type value_type;
458 static int const nLimit = 20;
460 for ( int i = 0; i < nLimit; i++ )
462 std::random_shuffle( arr, arr + nLimit );
465 for ( int i = 0; i < nLimit; ++i )
469 for ( int i = 0; i < nLimit; ++i ) {
473 CPPUNIT_ASSERT( gp );
474 CPPUNIT_ASSERT( !gp.empty());
475 CPPUNIT_CHECK( gp->nKey == nKey );
476 CPPUNIT_CHECK( gp->nVal == nKey * 2 );
479 gp = l.extract( nKey );
480 CPPUNIT_ASSERT( gp );
481 CPPUNIT_ASSERT( !gp.empty());
482 CPPUNIT_CHECK( gp->nKey == nKey );
483 CPPUNIT_CHECK( gp->nVal == nKey*2 );
487 CPPUNIT_CHECK( !gp );
488 CPPUNIT_CHECK( gp.empty());
489 CPPUNIT_CHECK( !l.extract( nKey));
490 CPPUNIT_CHECK( gp.empty());
492 CPPUNIT_ASSERT( l.empty());
493 CPPUNIT_CHECK( !l.get(arr[0]));
494 CPPUNIT_CHECK( gp.empty());
495 CPPUNIT_CHECK( !l.extract( arr[0]));
496 CPPUNIT_CHECK( gp.empty());
499 // extract_with/get_with
500 for ( int i = 0; i < nLimit; ++i )
504 for ( int i = 0; i < nLimit; ++i ) {
506 other_item key( nKey );
508 gp = l.get_with( key, other_less() );
509 CPPUNIT_ASSERT( gp );
510 CPPUNIT_ASSERT( !gp.empty());
511 CPPUNIT_CHECK( gp->nKey == nKey );
512 CPPUNIT_CHECK( gp->nVal == nKey * 2 );
515 gp = l.extract_with( key, other_less() );
516 CPPUNIT_ASSERT( gp );
517 CPPUNIT_ASSERT( !gp.empty());
518 CPPUNIT_CHECK( gp->nKey == nKey );
519 CPPUNIT_CHECK( gp->nVal == nKey*2 );
522 gp = l.get_with( key, other_less() );
523 CPPUNIT_CHECK( !gp );
524 CPPUNIT_CHECK( gp.empty());
525 CPPUNIT_CHECK( !l.extract_with( key, other_less()));
526 CPPUNIT_CHECK( gp.empty());
528 CPPUNIT_ASSERT( l.empty());
529 CPPUNIT_CHECK( !l.get_with(other_item(arr[0]), other_less()));
530 CPPUNIT_CHECK( gp.empty());
531 CPPUNIT_CHECK( !l.extract_with( other_item(arr[0]), other_less()));
532 CPPUNIT_CHECK( gp.empty());
537 template <class OrdList>
543 static int const nLimit = 20;
545 typedef typename OrdList::rcu_lock rcu_lock;
546 typedef typename OrdList::value_type value_type;
547 typedef typename OrdList::gc rcu_type;
551 for (int i = 0; i < nLimit; ++i)
553 std::random_shuffle( a, a + nLimit );
556 for ( int i = 0; i < nLimit; ++i )
557 CPPUNIT_ASSERT( l.insert( a[i] ) );
559 typename OrdList::exempt_ptr ep;
561 for ( int i = 0; i < nLimit; ++i ) {
564 value_type * pGet = l.get( a[i] );
565 CPPUNIT_ASSERT( pGet != nullptr );
566 CPPUNIT_CHECK( pGet->nKey == a[i] );
567 CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
569 ep = l.extract( a[i] );
570 CPPUNIT_ASSERT( ep );
571 CPPUNIT_ASSERT( !ep.empty() );
572 CPPUNIT_CHECK( ep->nKey == a[i] );
573 CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
578 CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
579 CPPUNIT_CHECK( !l.extract( a[i] ));
582 CPPUNIT_ASSERT( l.empty() );
586 CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
587 ep = l.extract( a[0] );
588 CPPUNIT_CHECK( !ep );
589 CPPUNIT_CHECK( ep.empty() );
592 // extract_with/get_with
593 for ( int i = 0; i < nLimit; ++i ) {
594 CPPUNIT_ASSERT( l.insert( a[i] ) );
597 for ( int i = 0; i < nLimit; ++i ) {
598 other_item itm( a[i] );
601 value_type * pGet = l.get_with( itm, other_less() );
602 CPPUNIT_ASSERT( pGet != nullptr );
603 CPPUNIT_CHECK( pGet->nKey == a[i] );
604 CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
606 ep = l.extract_with( itm, other_less() );
607 CPPUNIT_ASSERT( ep );
608 CPPUNIT_ASSERT( !ep.empty() );
609 CPPUNIT_CHECK( ep->nKey == a[i] );
610 CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
615 CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
616 ep = l.extract_with( itm, other_less() );
617 CPPUNIT_CHECK( !ep );
618 CPPUNIT_CHECK( ep.empty() );
621 CPPUNIT_ASSERT( l.empty() );
625 CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
626 CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
627 CPPUNIT_CHECK( ep.empty() );
632 template <class OrdList>
635 typedef OrdList list;
636 typedef typename list::value_type value_type;
637 typedef std::pair<typename list::iterator, bool> ensure_result;
639 typename list::iterator it;
642 CPPUNIT_ASSERT( l.empty() );
643 CPPUNIT_ASSERT( l.insert(50) != l.end() );
644 CPPUNIT_ASSERT( !l.empty() );
646 ensure_result eres = l.ensure( item(100, 33) );
647 CPPUNIT_ASSERT( eres.second );
648 CPPUNIT_ASSERT( eres.first != l.end() );
649 CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() );
651 CPPUNIT_ASSERT( l.insert(100) == l.end() );
652 eres = l.ensure( item(50, 33) );
653 CPPUNIT_ASSERT( !eres.second );
654 CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 );
655 eres.first->nVal = 63;
658 CPPUNIT_ASSERT( it == l.end() );
661 CPPUNIT_ASSERT( it != l.end() );
662 CPPUNIT_ASSERT( it->nKey == 50 );
663 CPPUNIT_ASSERT( it->nVal == 63 );
666 CPPUNIT_ASSERT( it != l.end() );
667 CPPUNIT_ASSERT( it->nKey == 100 );
668 CPPUNIT_ASSERT( it->nVal == 33 );
670 it = l.find_with( 150, lt<value_type>() );
671 CPPUNIT_ASSERT( it != l.end() );
672 CPPUNIT_ASSERT( it->nKey == 150 );
673 CPPUNIT_ASSERT( it->nVal == it->nKey * 2 );
675 CPPUNIT_ASSERT( !l.empty() );
677 CPPUNIT_ASSERT( l.empty() );
680 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
681 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
682 CPPUNIT_ASSERT( l.emplace( item( 1001 )) != l.end());
684 // insert failed - such key exists
685 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
686 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
689 CPPUNIT_ASSERT( it != l.end() );
690 CPPUNIT_ASSERT( it->nKey == 501 );
691 CPPUNIT_ASSERT( it->nVal == 501 * 2 );
693 it = l.find_with( 251, lt<value_type>() );
694 CPPUNIT_ASSERT( it != l.end() );
695 CPPUNIT_ASSERT( it->nKey == 251 );
696 CPPUNIT_ASSERT( it->nVal == 152 );
699 CPPUNIT_ASSERT( it != l.end() );
700 CPPUNIT_ASSERT( it->nKey == 1001 );
701 CPPUNIT_ASSERT( it->nVal == 1001 * 2 );
704 typename OrdList::iterator it( l.begin() );
705 typename OrdList::const_iterator cit( l.cbegin() );
706 CPPUNIT_CHECK( it == cit );
707 CPPUNIT_CHECK( it != l.end() );
708 CPPUNIT_CHECK( it != l.cend() );
709 CPPUNIT_CHECK( cit != l.end() );
710 CPPUNIT_CHECK( cit != l.cend() );
712 CPPUNIT_CHECK( it != cit );
713 CPPUNIT_CHECK( it != l.end() );
714 CPPUNIT_CHECK( it != l.cend() );
715 CPPUNIT_CHECK( cit != l.end() );
716 CPPUNIT_CHECK( cit != l.cend() );
718 CPPUNIT_CHECK( it == cit );
719 CPPUNIT_CHECK( it != l.end() );
720 CPPUNIT_CHECK( it != l.cend() );
721 CPPUNIT_CHECK( cit != l.end() );
722 CPPUNIT_CHECK( cit != l.cend() );
727 CPPUNIT_ASSERT( l.empty() );
742 void RCU_GPI_cmpmix();
747 void RCU_GPB_cmpmix();
752 void RCU_GPT_cmpmix();
757 void RCU_SHB_cmpmix();
762 void RCU_SHT_cmpmix();
770 CPPUNIT_TEST_SUITE(LazyListTestHeader)
772 CPPUNIT_TEST(HP_less)
773 CPPUNIT_TEST(HP_cmpmix)
776 CPPUNIT_TEST(DHP_cmp)
777 CPPUNIT_TEST(DHP_less)
778 CPPUNIT_TEST(DHP_cmpmix)
781 CPPUNIT_TEST(RCU_GPI_cmp)
782 CPPUNIT_TEST(RCU_GPI_less)
783 CPPUNIT_TEST(RCU_GPI_cmpmix)
784 CPPUNIT_TEST(RCU_GPI_ic)
786 CPPUNIT_TEST(RCU_GPB_cmp)
787 CPPUNIT_TEST(RCU_GPB_less)
788 CPPUNIT_TEST(RCU_GPB_cmpmix)
789 CPPUNIT_TEST(RCU_GPB_ic)
791 CPPUNIT_TEST(RCU_GPT_cmp)
792 CPPUNIT_TEST(RCU_GPT_less)
793 CPPUNIT_TEST(RCU_GPT_cmpmix)
794 CPPUNIT_TEST(RCU_GPT_ic)
796 CPPUNIT_TEST(RCU_SHB_cmp)
797 CPPUNIT_TEST(RCU_SHB_less)
798 CPPUNIT_TEST(RCU_SHB_cmpmix)
799 CPPUNIT_TEST(RCU_SHB_ic)
801 CPPUNIT_TEST(RCU_SHT_cmp)
802 CPPUNIT_TEST(RCU_SHT_less)
803 CPPUNIT_TEST(RCU_SHT_cmpmix)
804 CPPUNIT_TEST(RCU_SHT_ic)
806 CPPUNIT_TEST(NOGC_cmp)
807 CPPUNIT_TEST(NOGC_less)
808 CPPUNIT_TEST(NOGC_cmpmix)
809 CPPUNIT_TEST(NOGC_ic)
810 CPPUNIT_TEST_SUITE_END()
813 } // namespace ordlist