3 #include "cppunit/thread.h"
4 #include "set2/set_type.h"
8 #define TEST_CASE(TAG, X) void X();
16 key_thread( size_t key, size_t threadNo )
17 : nKey( static_cast<uint32_t>(key))
18 , nThread( static_cast<uint16_t>(threadNo))
25 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
29 struct cmp<key_thread> {
30 int operator ()(key_thread const& k1, key_thread const& k2) const
32 if ( k1.nKey < k2.nKey )
34 if ( k1.nKey > k2.nKey )
36 if ( k1.nThread < k2.nThread )
38 if ( k1.nThread > k2.nThread )
42 int operator ()(key_thread const& k1, size_t k2) const
50 int operator ()(size_t k1, key_thread const& k2) const
64 struct less<set2::key_thread>
66 bool operator()(set2::key_thread const& k1, set2::key_thread const& k2) const
68 if ( k1.nKey <= k2.nKey )
69 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
75 struct hash<set2::key_thread>
77 typedef size_t result_type;
78 typedef set2::key_thread argument_type;
80 size_t operator()( set2::key_thread const& k ) const
82 return std::hash<size_t>()(k.nKey);
84 size_t operator()( size_t k ) const
86 return std::hash<size_t>()(k);
93 inline size_t hash_value( set2::key_thread const& k )
95 return std::hash<size_t>()( k.nKey );
99 struct hash<set2::key_thread>
101 typedef size_t result_type;
102 typedef set2::key_thread argument_type;
104 size_t operator()(set2::key_thread const& k) const
106 return boost::hash<size_t>()( k.nKey );
108 size_t operator()(size_t k) const
110 return boost::hash<size_t>()( k );
117 class Set_DelOdd: public CppUnitMini::TestCase
120 size_t c_nSetSize =1000000; // max set size
121 size_t c_nInsThreadCount = 4; // insert thread count
122 size_t c_nDelThreadCount = 4; // delete thread count
123 size_t c_nExtractThreadCount = 4; // extract thread count
124 size_t c_nMaxLoadFactor = 8; // maximum load factor
125 bool c_bPrintGCState = true;
127 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooSet
128 size_t c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
129 size_t c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
131 size_t c_nFeldmanSet_HeadBits = 10;
132 size_t c_nFeldmanSet_ArrayBits = 4;
134 size_t c_nLoadFactor = 2;
135 std::vector<size_t> m_arrData;
138 typedef key_thread key_type;
139 typedef size_t value_type;
141 atomics::atomic<size_t> m_nInsThreadCount;
143 // Inserts keys from [0..N)
145 class InsertThread: public CppUnitMini::TestThread
149 virtual InsertThread * clone()
151 return new InsertThread( *this );
154 struct update_functor
156 template <typename Q>
157 void operator()( bool /*bNew*/, key_value_pair const&, Q const& )
160 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/)
164 size_t m_nInsertSuccess;
165 size_t m_nInsertFailed;
168 InsertThread( CppUnitMini::ThreadPool& pool, Set& rMap )
169 : CppUnitMini::TestThread( pool )
172 InsertThread( InsertThread& src )
173 : CppUnitMini::TestThread( src )
177 Set_DelOdd& getTest()
179 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
182 virtual void init() { cds::threading::Manager::attachThread() ; }
183 virtual void fini() { cds::threading::Manager::detachThread() ; }
192 std::vector<size_t>& arrData = getTest().m_arrData;
193 for ( size_t i = 0; i < arrData.size(); ++i ) {
194 if ( rSet.insert( key_type( arrData[i], m_nThreadNo )))
201 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
202 if ( arrData[i] & 1 ) {
203 rSet.update( key_type( arrData[i], m_nThreadNo ), f, true );
207 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
212 bool operator()( key_type const& k1, key_type const& k2 ) const
214 return k1.nKey == k2.nKey;
216 bool operator()( size_t k1, key_type const& k2 ) const
218 return k1 == k2.nKey;
220 bool operator()( key_type const& k1, size_t k2 ) const
222 return k1.nKey == k2;
224 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
226 return operator()( k1.key, k2.key );
228 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
230 return operator()( k1.key, k2 );
232 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
234 return operator()( k1, k2.key );
236 bool operator ()( key_value_pair const& k1, size_t k2 ) const
238 return operator()( k1.key, k2 );
240 bool operator ()( size_t k1, key_value_pair const& k2 ) const
242 return operator()( k1, k2.key );
247 bool operator()( key_type const& k1, key_type const& k2 ) const
249 return k1.nKey < k2.nKey;
251 bool operator()( size_t k1, key_type const& k2 ) const
255 bool operator()( key_type const& k1, size_t k2 ) const
259 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
261 return operator()( k1.key, k2.key );
263 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
265 return operator()( k1.key, k2 );
267 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
269 return operator()( k1, k2.key );
271 bool operator ()( key_value_pair const& k1, size_t k2 ) const
273 return operator()( k1.key, k2 );
275 bool operator ()( size_t k1, key_value_pair const& k2 ) const
277 return operator()( k1, k2.key );
280 typedef key_equal equal_to;
283 // Deletes odd keys from [0..N)
285 class DeleteThread: public CppUnitMini::TestThread
289 virtual DeleteThread * clone()
291 return new DeleteThread( *this );
294 size_t m_nDeleteSuccess;
295 size_t m_nDeleteFailed;
298 DeleteThread( CppUnitMini::ThreadPool& pool, Set& rMap )
299 : CppUnitMini::TestThread( pool )
302 DeleteThread( DeleteThread& src )
303 : CppUnitMini::TestThread( src )
307 Set_DelOdd& getTest()
309 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
312 virtual void init() { cds::threading::Manager::attachThread() ; }
313 virtual void fini() { cds::threading::Manager::detachThread() ; }
315 template <typename SetType, bool>
317 static bool erase( SetType& s, size_t key, size_t /*thread*/)
319 return s.erase_with( key, key_less() );
323 template <typename SetType>
324 struct eraser<SetType, true> {
325 static bool erase(SetType& s, size_t key, size_t thread)
327 return s.erase( key_type(key, thread));
338 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
339 std::vector<size_t>& arrData = getTest().m_arrData;
341 if ( m_nThreadNo & 1 ) {
342 for (size_t i = 0; i < arrData.size(); ++i) {
343 if (arrData[i] & 1) {
344 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
345 if ( eraser<Set, Set::c_bEraseExactKey>::erase( rSet, arrData[i], k ))
351 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
356 for (size_t i = arrData.size() - 1; i > 0; --i) {
357 if (arrData[i] & 1) {
358 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
359 if (eraser<Set, Set::c_bEraseExactKey>::erase(rSet, arrData[i], k))
365 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
372 // Extracts odd keys from [0..N)
373 template <typename GC, class Set>
374 class ExtractThread: public CppUnitMini::TestThread
378 virtual ExtractThread * clone()
380 return new ExtractThread( *this );
383 size_t m_nExtractSuccess;
384 size_t m_nExtractFailed;
387 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
388 : CppUnitMini::TestThread( pool )
391 ExtractThread( ExtractThread& src )
392 : CppUnitMini::TestThread( src )
396 Set_DelOdd& getTest()
398 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
401 virtual void init() { cds::threading::Manager::attachThread() ; }
402 virtual void fini() { cds::threading::Manager::detachThread() ; }
404 template <typename SetType, bool>
406 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/)
408 return s.extract_with( key, key_less());
412 template <typename SetType>
413 struct extractor<SetType, true> {
414 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread)
416 return s.extract( key_type(key, thread));
425 m_nExtractFailed = 0;
427 typename Set::guarded_ptr gp;
429 std::vector<size_t>& arrData = getTest().m_arrData;
430 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
432 if ( m_nThreadNo & 1 ) {
433 for ( size_t i = 0; i < arrData.size(); ++i ) {
434 if (arrData[i] & 1) {
435 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
436 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k );
444 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
449 for (size_t i = arrData.size() - 1; i > 0; --i) {
450 if (arrData[i] & 1) {
451 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
452 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
460 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
467 template <typename RCU, class Set>
468 class ExtractThread< cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
472 virtual ExtractThread * clone()
474 return new ExtractThread( *this );
477 size_t m_nExtractSuccess;
478 size_t m_nExtractFailed;
481 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
482 : CppUnitMini::TestThread( pool )
485 ExtractThread( ExtractThread& src )
486 : CppUnitMini::TestThread( src )
490 Set_DelOdd& getTest()
492 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
495 virtual void init() { cds::threading::Manager::attachThread() ; }
496 virtual void fini() { cds::threading::Manager::detachThread() ; }
498 template <typename SetType, bool>
500 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/)
502 return s.extract_with(key, key_less());
506 template <typename SetType>
507 struct extractor<SetType, true> {
508 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread)
510 return s.extract(key_type(key, thread));
519 m_nExtractFailed = 0;
521 typename Set::exempt_ptr xp;
523 std::vector<size_t>& arrData = getTest().m_arrData;
524 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
526 if ( m_nThreadNo & 1 ) {
527 for (size_t i = 0; i < arrData.size(); ++i) {
528 if (arrData[i] & 1) {
529 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
530 if ( Set::c_bExtractLockExternal ) {
531 typename Set::rcu_lock l;
532 xp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
539 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
548 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
553 for (size_t i = arrData.size() - 1; i > 0; --i) {
554 if (arrData[i] & 1) {
555 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
556 if ( Set::c_bExtractLockExternal ) {
557 typename Set::rcu_lock l;
558 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
565 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
574 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
583 void do_test( size_t nLoadFactor )
585 Set testSet( c_nSetSize, nLoadFactor );
586 do_test_with( testSet );
591 void do_test_extract( size_t nLoadFactor )
593 Set testSet( c_nSetSize, nLoadFactor );
594 do_test_extract_with( testSet );
599 void do_test_with( Set& testSet )
601 typedef InsertThread<Set> insert_thread;
602 typedef DeleteThread<Set> delete_thread;
604 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
606 CppUnitMini::ThreadPool pool( *this );
607 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
608 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
610 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
612 size_t nInsertSuccess = 0;
613 size_t nInsertFailed = 0;
614 size_t nDeleteSuccess = 0;
615 size_t nDeleteFailed = 0;
616 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
617 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
619 nInsertSuccess += pThread->m_nInsertSuccess;
620 nInsertFailed += pThread->m_nInsertFailed;
623 delete_thread * p = static_cast<delete_thread *>( *it );
624 nDeleteSuccess += p->m_nDeleteSuccess;
625 nDeleteFailed += p->m_nDeleteFailed;
629 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
630 CPPUNIT_CHECK( nInsertFailed == 0 );
632 CPPUNIT_MSG( " Totals (success/failed): \n\t"
633 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
634 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
639 void do_test_extract_with( Set& testSet )
641 typedef InsertThread<Set> insert_thread;
642 typedef DeleteThread<Set> delete_thread;
643 typedef ExtractThread< typename Set::gc, Set > extract_thread;
645 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
647 CppUnitMini::ThreadPool pool( *this );
648 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
649 if ( c_nDelThreadCount )
650 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount );
651 if ( c_nExtractThreadCount )
652 pool.add( new extract_thread( pool, testSet ), c_nExtractThreadCount );
654 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
656 size_t nInsertSuccess = 0;
657 size_t nInsertFailed = 0;
658 size_t nDeleteSuccess = 0;
659 size_t nDeleteFailed = 0;
660 size_t nExtractSuccess = 0;
661 size_t nExtractFailed = 0;
662 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
663 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
665 nInsertSuccess += pThread->m_nInsertSuccess;
666 nInsertFailed += pThread->m_nInsertFailed;
669 delete_thread * p = dynamic_cast<delete_thread *>( *it );
671 nDeleteSuccess += p->m_nDeleteSuccess;
672 nDeleteFailed += p->m_nDeleteFailed;
675 extract_thread * pExt = dynamic_cast<extract_thread *>( *it );
677 nExtractSuccess += pExt->m_nExtractSuccess;
678 nExtractFailed += pExt->m_nExtractFailed;
683 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
684 CPPUNIT_CHECK( nInsertFailed == 0 );
686 CPPUNIT_MSG( " Totals (success/failed): \n\t"
687 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
688 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
689 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
693 template <typename Set>
694 void analyze( Set& testSet )
696 // All even keys must be in the set
698 CPPUNIT_MSG( " Check even keys..." );
699 size_t nErrorCount = 0;
700 for ( size_t n = 0; n < c_nSetSize; n +=2 ) {
701 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
702 if ( !testSet.contains( key_type(n, i) ) ) {
703 if ( ++nErrorCount < 10 ) {
704 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
709 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
712 check_before_clear( testSet );
714 CPPUNIT_MSG( " Clear map (single-threaded)..." );
715 cds::OS::Timer timer;
717 CPPUNIT_MSG( " Duration=" << timer.duration() );
718 CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) );
720 additional_check( testSet );
721 print_stat( testSet );
722 additional_cleanup( testSet );
728 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
730 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
731 << " delete thread count=" << c_nDelThreadCount
732 << " set size=" << c_nSetSize
735 if ( Set::c_bLoadFactorDepended ) {
736 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
737 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
739 Set testSet( *this );
740 do_test_with( testSet );
743 if ( c_bPrintGCState )
748 Set testSet( *this );
749 do_test_with( testSet );
752 if ( c_bPrintGCState )
758 void run_test_extract()
760 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
762 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
763 << " delete thread count=" << c_nDelThreadCount
764 << " extract thread count=" << c_nExtractThreadCount
765 << " set size=" << c_nSetSize
768 if ( Set::c_bLoadFactorDepended ) {
769 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
770 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
772 Set testSet( *this );
773 do_test_extract_with( testSet );
776 if ( c_bPrintGCState )
781 Set testSet( *this );
782 do_test_extract_with( testSet );
785 if ( c_bPrintGCState )
790 void setUpParams( const CppUnitMini::TestCfg& cfg );
791 virtual void endTestCase();
793 # include "set2/set_defs.h"
794 CDSUNIT_DECLARE_MichaelSet
795 CDSUNIT_DECLARE_SplitList
796 CDSUNIT_DECLARE_SkipListSet
797 CDSUNIT_DECLARE_EllenBinTreeSet
798 CDSUNIT_DECLARE_CuckooSet
799 CDSUNIT_DECLARE_FeldmanHashSet_fixed
800 CDSUNIT_DECLARE_FeldmanHashSet_city
802 CPPUNIT_TEST_SUITE_(Set_DelOdd, "Map_DelOdd")
803 CDSUNIT_TEST_MichaelSet
804 CDSUNIT_TEST_SplitList
805 CDSUNIT_TEST_SkipListSet
806 CDSUNIT_TEST_EllenBinTreeSet
807 CDSUNIT_TEST_FeldmanHashSet_fixed
808 CDSUNIT_TEST_FeldmanHashSet_city
809 CDSUNIT_TEST_CuckooSet
810 CPPUNIT_TEST_SUITE_END();