3 #include "cppunit/thread.h"
4 #include "set2/set_type.h"
8 # define TEST_SET(IMPL, C, X) void C::X() { test<set_type<IMPL, key_type, value_type>::X >(); }
9 # define TEST_SET_EXTRACT(IMPL, C, X) void C::X() { test_extract<set_type<IMPL, key_type, value_type>::X >(); }
10 # define TEST_SET_NOLF(IMPL, C, X) void C::X() { test_nolf<set_type<IMPL, key_type, value_type>::X >(); }
11 # define TEST_SET_NOLF_EXTRACT(IMPL, C, X) void C::X() { test_nolf_extract<set_type<IMPL, key_type, value_type>::X >(); }
19 key_thread( size_t key, size_t threadNo )
28 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
32 struct cmp<key_thread> {
33 int operator ()(key_thread const& k1, key_thread const& k2) const
35 if ( k1.nKey < k2.nKey )
37 if ( k1.nKey > k2.nKey )
39 if ( k1.nThread < k2.nThread )
41 if ( k1.nThread > k2.nThread )
45 int operator ()(key_thread const& k1, size_t k2) const
53 int operator ()(size_t k1, key_thread const& k2) const
67 struct less<set2::key_thread>
69 bool operator()(set2::key_thread const& k1, set2::key_thread const& k2) const
71 if ( k1.nKey <= k2.nKey )
72 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
78 struct hash<set2::key_thread>
80 typedef size_t result_type;
81 typedef set2::key_thread argument_type;
83 size_t operator()( set2::key_thread const& k ) const
85 return std::hash<size_t>()(k.nKey);
87 size_t operator()( size_t k ) const
89 return std::hash<size_t>()(k);
96 inline size_t hash_value( set2::key_thread const& k )
98 return std::hash<size_t>()( k.nKey );
102 struct hash<set2::key_thread>
104 typedef size_t result_type;
105 typedef set2::key_thread argument_type;
107 size_t operator()(set2::key_thread const& k) const
109 return boost::hash<size_t>()( k.nKey );
111 size_t operator()(size_t k) const
113 return boost::hash<size_t>()( k );
120 class Set_DelOdd: public CppUnitMini::TestCase
122 static size_t c_nSetSize; // max set size
123 static size_t c_nInsThreadCount; // insert thread count
124 static size_t c_nDelThreadCount; // delete thread count
125 static size_t c_nExtractThreadCount; // extract thread count
126 static size_t c_nMaxLoadFactor; // maximum load factor
127 static bool c_bPrintGCState;
129 std::vector<size_t> m_arrData;
132 typedef CppUnitMini::TestCase Base;
133 typedef key_thread key_type;
134 typedef size_t value_type;
136 atomics::atomic<size_t> m_nInsThreadCount;
138 // Inserts keys from [0..N)
140 class InsertThread: public CppUnitMini::TestThread
144 virtual InsertThread * clone()
146 return new InsertThread( *this );
151 template <typename Q>
152 void operator()( bool /*bNew*/, key_value_pair const&, Q const& )
156 size_t m_nInsertSuccess;
157 size_t m_nInsertFailed;
160 InsertThread( CppUnitMini::ThreadPool& pool, Set& rMap )
161 : CppUnitMini::TestThread( pool )
164 InsertThread( InsertThread& src )
165 : CppUnitMini::TestThread( src )
169 Set_DelOdd& getTest()
171 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
174 virtual void init() { cds::threading::Manager::attachThread() ; }
175 virtual void fini() { cds::threading::Manager::detachThread() ; }
184 std::vector<size_t>& arrData = getTest().m_arrData;
185 for ( size_t i = 0; i < arrData.size(); ++i ) {
186 if ( rSet.insert( key_type( arrData[i], m_nThreadNo )))
193 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
194 if ( arrData[i] & 1 ) {
195 rSet.ensure( key_type( arrData[i], m_nThreadNo ), f );
199 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
204 bool operator()( key_type const& k1, key_type const& k2 ) const
206 return k1.nKey == k2.nKey;
208 bool operator()( size_t k1, key_type const& k2 ) const
210 return k1 == k2.nKey;
212 bool operator()( key_type const& k1, size_t k2 ) const
214 return k1.nKey == k2;
216 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
218 return operator()( k1.key, k2.key );
220 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
222 return operator()( k1.key, k2 );
224 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
226 return operator()( k1, k2.key );
228 bool operator ()( key_value_pair const& k1, size_t k2 ) const
230 return operator()( k1.key, k2 );
232 bool operator ()( size_t k1, key_value_pair const& k2 ) const
234 return operator()( k1, k2.key );
239 bool operator()( key_type const& k1, key_type const& k2 ) const
241 return k1.nKey < k2.nKey;
243 bool operator()( size_t k1, key_type const& k2 ) const
247 bool operator()( key_type const& k1, size_t k2 ) const
251 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
253 return operator()( k1.key, k2.key );
255 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
257 return operator()( k1.key, k2 );
259 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
261 return operator()( k1, k2.key );
263 bool operator ()( key_value_pair const& k1, size_t k2 ) const
265 return operator()( k1.key, k2 );
267 bool operator ()( size_t k1, key_value_pair const& k2 ) const
269 return operator()( k1, k2.key );
272 typedef key_equal equal_to;
275 // Deletes odd keys from [0..N)
277 class DeleteThread: public CppUnitMini::TestThread
281 virtual DeleteThread * clone()
283 return new DeleteThread( *this );
286 size_t m_nDeleteSuccess;
287 size_t m_nDeleteFailed;
290 DeleteThread( CppUnitMini::ThreadPool& pool, Set& rMap )
291 : CppUnitMini::TestThread( pool )
294 DeleteThread( DeleteThread& src )
295 : CppUnitMini::TestThread( src )
299 Set_DelOdd& getTest()
301 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
304 virtual void init() { cds::threading::Manager::attachThread() ; }
305 virtual void fini() { cds::threading::Manager::detachThread() ; }
314 std::vector<size_t>& arrData = getTest().m_arrData;
315 if ( m_nThreadNo & 1 ) {
316 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
317 for ( size_t i = 0; i < arrData.size(); ++i ) {
318 if ( arrData[i] & 1 ) {
319 if ( rSet.erase_with( arrData[i], key_less() ))
325 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
330 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
331 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
332 if ( arrData[i] & 1 ) {
333 if ( rSet.erase_with( arrData[i], key_less() ))
339 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
346 // Extracts odd keys from [0..N)
347 template <typename GC, class Set>
348 class ExtractThread: public CppUnitMini::TestThread
352 virtual ExtractThread * clone()
354 return new ExtractThread( *this );
357 size_t m_nExtractSuccess;
358 size_t m_nExtractFailed;
361 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
362 : CppUnitMini::TestThread( pool )
365 ExtractThread( ExtractThread& src )
366 : CppUnitMini::TestThread( src )
370 Set_DelOdd& getTest()
372 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
375 virtual void init() { cds::threading::Manager::attachThread() ; }
376 virtual void fini() { cds::threading::Manager::detachThread() ; }
383 m_nExtractFailed = 0;
385 typename Set::guarded_ptr gp;
387 std::vector<size_t>& arrData = getTest().m_arrData;
388 if ( m_nThreadNo & 1 ) {
389 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
390 for ( size_t i = 0; i < arrData.size(); ++i ) {
391 if ( arrData[i] & 1 ) {
392 gp = rSet.extract_with( arrData[i], key_less());
400 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
405 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
406 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
407 if ( arrData[i] & 1 ) {
408 gp = rSet.extract_with( arrData[i], key_less());
416 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
423 template <typename RCU, class Set>
424 class ExtractThread< cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
428 virtual ExtractThread * clone()
430 return new ExtractThread( *this );
433 size_t m_nExtractSuccess;
434 size_t m_nExtractFailed;
437 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
438 : CppUnitMini::TestThread( pool )
441 ExtractThread( ExtractThread& src )
442 : CppUnitMini::TestThread( src )
446 Set_DelOdd& getTest()
448 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
451 virtual void init() { cds::threading::Manager::attachThread() ; }
452 virtual void fini() { cds::threading::Manager::detachThread() ; }
459 m_nExtractFailed = 0;
461 typename Set::exempt_ptr xp;
463 std::vector<size_t>& arrData = getTest().m_arrData;
464 if ( m_nThreadNo & 1 ) {
465 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
466 for ( size_t i = 0; i < arrData.size(); ++i ) {
467 if ( arrData[i] & 1 ) {
468 if ( Set::c_bExtractLockExternal ) {
469 typename Set::rcu_lock l;
470 xp = rSet.extract_with( arrData[i], key_less() );
477 xp = rSet.extract_with( arrData[i], key_less() );
486 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
491 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
492 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
493 if ( arrData[i] & 1 ) {
494 if ( Set::c_bExtractLockExternal ) {
495 typename Set::rcu_lock l;
496 xp = rSet.extract_with( arrData[i], key_less() );
503 xp = rSet.extract_with( arrData[i], key_less() );
512 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
521 void do_test( size_t nLoadFactor )
523 Set testSet( c_nSetSize, nLoadFactor );
524 do_test_with( testSet );
529 void do_test_extract( size_t nLoadFactor )
531 Set testSet( c_nSetSize, nLoadFactor );
532 do_test_extract_with( testSet );
537 void do_test_with( Set& testSet )
539 typedef InsertThread<Set> insert_thread;
540 typedef DeleteThread<Set> delete_thread;
542 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
544 CppUnitMini::ThreadPool pool( *this );
545 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
546 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
548 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
550 size_t nInsertSuccess = 0;
551 size_t nInsertFailed = 0;
552 size_t nDeleteSuccess = 0;
553 size_t nDeleteFailed = 0;
554 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
555 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
557 nInsertSuccess += pThread->m_nInsertSuccess;
558 nInsertFailed += pThread->m_nInsertFailed;
561 delete_thread * p = static_cast<delete_thread *>( *it );
562 nDeleteSuccess += p->m_nDeleteSuccess;
563 nDeleteFailed += p->m_nDeleteFailed;
567 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
568 CPPUNIT_CHECK( nInsertFailed == 0 );
570 CPPUNIT_MSG( " Totals (success/failed): \n\t"
571 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
572 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
577 void do_test_extract_with( Set& testSet )
579 typedef InsertThread<Set> insert_thread;
580 typedef DeleteThread<Set> delete_thread;
581 typedef ExtractThread< typename Set::gc, Set > extract_thread;
583 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
585 CppUnitMini::ThreadPool pool( *this );
586 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
587 if ( c_nDelThreadCount )
588 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount );
589 if ( c_nExtractThreadCount )
590 pool.add( new extract_thread( pool, testSet ), c_nExtractThreadCount );
592 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
594 size_t nInsertSuccess = 0;
595 size_t nInsertFailed = 0;
596 size_t nDeleteSuccess = 0;
597 size_t nDeleteFailed = 0;
598 size_t nExtractSuccess = 0;
599 size_t nExtractFailed = 0;
600 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
601 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
603 nInsertSuccess += pThread->m_nInsertSuccess;
604 nInsertFailed += pThread->m_nInsertFailed;
607 delete_thread * p = dynamic_cast<delete_thread *>( *it );
609 nDeleteSuccess += p->m_nDeleteSuccess;
610 nDeleteFailed += p->m_nDeleteFailed;
613 extract_thread * pExt = dynamic_cast<extract_thread *>( *it );
615 nExtractSuccess += pExt->m_nExtractSuccess;
616 nExtractFailed += pExt->m_nExtractFailed;
621 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
622 CPPUNIT_CHECK( nInsertFailed == 0 );
624 CPPUNIT_MSG( " Totals (success/failed): \n\t"
625 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
626 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
627 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
631 template <typename Set>
632 void analyze( Set& testSet )
634 // All even keys must be in the set
636 CPPUNIT_MSG( " Check even keys..." );
637 size_t nErrorCount = 0;
638 for ( size_t n = 0; n < c_nSetSize; n +=2 ) {
639 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
640 if ( !testSet.find( key_type(n, i) ) ) {
641 if ( ++nErrorCount < 10 ) {
642 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
647 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
650 check_before_clear( testSet );
652 CPPUNIT_MSG( " Clear map (single-threaded)..." );
653 cds::OS::Timer timer;
655 CPPUNIT_MSG( " Duration=" << timer.duration() );
656 CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) );
658 additional_check( testSet );
659 print_stat( testSet );
660 additional_cleanup( testSet );
666 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
667 << " delete thread count=" << c_nDelThreadCount
668 << " set size=" << c_nSetSize
671 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
672 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
673 do_test<Set>( nLoadFactor );
674 if ( c_bPrintGCState )
682 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
683 << " delete thread count=" << c_nDelThreadCount
684 << " extract thread count=" << c_nExtractThreadCount
685 << " set size=" << c_nSetSize
688 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
689 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
690 do_test_extract<Set>( nLoadFactor );
691 if ( c_bPrintGCState )
699 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
700 << " delete thread count=" << c_nDelThreadCount
701 << " set size=" << c_nSetSize
710 if ( c_bPrintGCState )
715 void test_nolf_extract()
717 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
718 << " delete thread count=" << c_nDelThreadCount
719 << " extract thread count=" << c_nExtractThreadCount
720 << " set size=" << c_nSetSize
725 do_test_extract_with( s );
729 if ( c_bPrintGCState )
733 void setUpParams( const CppUnitMini::TestCfg& cfg );
735 void run_MichaelSet(const char *in_name, bool invert = false);
736 void run_SplitList(const char *in_name, bool invert = false);
737 void run_CuckooSet(const char *in_name, bool invert = false);
738 void run_SkipListSet(const char *in_name, bool invert = false);
739 void run_EllenBinTreeSet(const char *in_name, bool invert = false);
741 virtual void myRun(const char *in_name, bool invert = false);
744 # include "set2/set_defs.h"
745 CDSUNIT_DECLARE_MichaelSet
746 CDSUNIT_DECLARE_SplitList
747 CDSUNIT_DECLARE_CuckooSet
748 CDSUNIT_DECLARE_SkipListSet
749 CDSUNIT_DECLARE_EllenBinTreeSet