3 #include "cppunit/thread.h"
4 #include "set2/set_types.h"
5 #include <algorithm> // random_shuffle
9 # define TEST_SET(X) void X() { test<SetTypes<key_type, value_type>::X >() ; }
10 # define TEST_SET_EXTRACT(X) void X() { test_extract<SetTypes<key_type, value_type>::X >() ; }
11 # define TEST_SET_NOLF(X) void X() { test_nolf<SetTypes<key_type, value_type>::X >() ; }
12 # define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract<SetTypes<key_type, value_type>::X >() ; }
20 key_thread( size_t key, size_t threadNo )
29 typedef SetTypes<key_thread, size_t>::key_val key_value_pair;
33 struct cmp<key_thread> {
34 int operator ()(key_thread const& k1, key_thread const& k2) const
36 if ( k1.nKey < k2.nKey )
38 if ( k1.nKey > k2.nKey )
40 if ( k1.nThread < k2.nThread )
42 if ( k1.nThread > k2.nThread )
46 int operator ()(key_thread const& k1, size_t k2) const
54 int operator ()(size_t k1, key_thread const& k2) const
68 struct less<set2::key_thread>
70 bool operator()(set2::key_thread const& k1, set2::key_thread const& k2) const
72 if ( k1.nKey <= k2.nKey )
73 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
79 struct hash<set2::key_thread>
81 typedef size_t result_type;
82 typedef set2::key_thread argument_type;
84 size_t operator()( set2::key_thread const& k ) const
86 return std::hash<size_t>()(k.nKey);
88 size_t operator()( size_t k ) const
90 return std::hash<size_t>()(k);
97 inline size_t hash_value( set2::key_thread const& k )
99 return std::hash<size_t>()( k.nKey );
103 struct hash<set2::key_thread>
105 typedef size_t result_type;
106 typedef set2::key_thread argument_type;
108 size_t operator()(set2::key_thread const& k) const
110 return boost::hash<size_t>()( k.nKey );
112 size_t operator()(size_t k) const
114 return boost::hash<size_t>()( k );
121 class Set_DelOdd: public CppUnitMini::TestCase
123 static size_t c_nSetSize; // max set size
124 static size_t c_nInsThreadCount; // insert thread count
125 static size_t c_nDelThreadCount; // delete thread count
126 static size_t c_nExtractThreadCount; // extract thread count
127 static size_t c_nMaxLoadFactor; // maximum load factor
128 static bool c_bPrintGCState;
130 std::vector<size_t> m_arrData;
133 typedef CppUnitMini::TestCase Base;
134 typedef key_thread key_type;
135 typedef size_t value_type;
137 atomics::atomic<size_t> m_nInsThreadCount;
139 // Inserts keys from [0..N)
141 class InsertThread: public CppUnitMini::TestThread
145 virtual InsertThread * clone()
147 return new InsertThread( *this );
152 template <typename Q>
153 void operator()( bool /*bNew*/, key_value_pair const&, Q const& )
157 size_t m_nInsertSuccess;
158 size_t m_nInsertFailed;
161 InsertThread( CppUnitMini::ThreadPool& pool, Set& rMap )
162 : CppUnitMini::TestThread( pool )
165 InsertThread( InsertThread& src )
166 : CppUnitMini::TestThread( src )
170 Set_DelOdd& getTest()
172 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
175 virtual void init() { cds::threading::Manager::attachThread() ; }
176 virtual void fini() { cds::threading::Manager::detachThread() ; }
185 std::vector<size_t>& arrData = getTest().m_arrData;
186 for ( size_t i = 0; i < arrData.size(); ++i ) {
187 if ( rSet.insert( key_type( arrData[i], m_nThreadNo )))
194 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
195 if ( arrData[i] & 1 ) {
196 rSet.ensure( key_type( arrData[i], m_nThreadNo ), f );
200 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
205 bool operator()( key_type const& k1, key_type const& k2 ) const
207 return k1.nKey == k2.nKey;
209 bool operator()( size_t k1, key_type const& k2 ) const
211 return k1 == k2.nKey;
213 bool operator()( key_type const& k1, size_t k2 ) const
215 return k1.nKey == k2;
217 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
219 return operator()( k1.key, k2.key );
221 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
223 return operator()( k1.key, k2 );
225 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
227 return operator()( k1, k2.key );
229 bool operator ()( key_value_pair const& k1, size_t k2 ) const
231 return operator()( k1.key, k2 );
233 bool operator ()( size_t k1, key_value_pair const& k2 ) const
235 return operator()( k1, k2.key );
240 bool operator()( key_type const& k1, key_type const& k2 ) const
242 return k1.nKey < k2.nKey;
244 bool operator()( size_t k1, key_type const& k2 ) const
248 bool operator()( key_type const& k1, size_t k2 ) const
252 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
254 return operator()( k1.key, k2.key );
256 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
258 return operator()( k1.key, k2 );
260 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
262 return operator()( k1, k2.key );
264 bool operator ()( key_value_pair const& k1, size_t k2 ) const
266 return operator()( k1.key, k2 );
268 bool operator ()( size_t k1, key_value_pair const& k2 ) const
270 return operator()( k1, k2.key );
273 typedef key_equal equal_to;
276 // Deletes odd keys from [0..N)
278 class DeleteThread: public CppUnitMini::TestThread
282 virtual DeleteThread * clone()
284 return new DeleteThread( *this );
287 size_t m_nDeleteSuccess;
288 size_t m_nDeleteFailed;
291 DeleteThread( CppUnitMini::ThreadPool& pool, Set& rMap )
292 : CppUnitMini::TestThread( pool )
295 DeleteThread( DeleteThread& src )
296 : CppUnitMini::TestThread( src )
300 Set_DelOdd& getTest()
302 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
305 virtual void init() { cds::threading::Manager::attachThread() ; }
306 virtual void fini() { cds::threading::Manager::detachThread() ; }
315 std::vector<size_t>& arrData = getTest().m_arrData;
316 if ( m_nThreadNo & 1 ) {
317 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
318 for ( size_t i = 0; i < arrData.size(); ++i ) {
319 if ( arrData[i] & 1 ) {
320 if ( rSet.erase_with( arrData[i], key_less() ))
326 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
331 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
332 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
333 if ( arrData[i] & 1 ) {
334 if ( rSet.erase_with( arrData[i], key_less() ))
340 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
347 // Extracts odd keys from [0..N)
348 template <typename GC, class Set>
349 class ExtractThread: public CppUnitMini::TestThread
353 virtual ExtractThread * clone()
355 return new ExtractThread( *this );
358 size_t m_nExtractSuccess;
359 size_t m_nExtractFailed;
362 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
363 : CppUnitMini::TestThread( pool )
366 ExtractThread( ExtractThread& src )
367 : CppUnitMini::TestThread( src )
371 Set_DelOdd& getTest()
373 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
376 virtual void init() { cds::threading::Manager::attachThread() ; }
377 virtual void fini() { cds::threading::Manager::detachThread() ; }
384 m_nExtractFailed = 0;
386 typename Set::guarded_ptr gp;
388 std::vector<size_t>& arrData = getTest().m_arrData;
389 if ( m_nThreadNo & 1 ) {
390 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
391 for ( size_t i = 0; i < arrData.size(); ++i ) {
392 if ( arrData[i] & 1 ) {
393 gp = rSet.extract_with( arrData[i], key_less());
401 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
406 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
407 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
408 if ( arrData[i] & 1 ) {
409 gp = rSet.extract_with( arrData[i], key_less());
417 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
424 template <typename RCU, class Set>
425 class ExtractThread< cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
429 virtual ExtractThread * clone()
431 return new ExtractThread( *this );
434 size_t m_nExtractSuccess;
435 size_t m_nExtractFailed;
438 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
439 : CppUnitMini::TestThread( pool )
442 ExtractThread( ExtractThread& src )
443 : CppUnitMini::TestThread( src )
447 Set_DelOdd& getTest()
449 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
452 virtual void init() { cds::threading::Manager::attachThread() ; }
453 virtual void fini() { cds::threading::Manager::detachThread() ; }
460 m_nExtractFailed = 0;
462 typename Set::exempt_ptr xp;
464 std::vector<size_t>& arrData = getTest().m_arrData;
465 if ( m_nThreadNo & 1 ) {
466 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
467 for ( size_t i = 0; i < arrData.size(); ++i ) {
468 if ( arrData[i] & 1 ) {
469 if ( Set::c_bExtractLockExternal ) {
470 typename Set::rcu_lock l;
471 xp = rSet.extract_with( arrData[i], key_less() );
478 xp = rSet.extract_with( arrData[i], key_less() );
487 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
492 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
493 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
494 if ( arrData[i] & 1 ) {
495 if ( Set::c_bExtractLockExternal ) {
496 typename Set::rcu_lock l;
497 xp = rSet.extract_with( arrData[i], key_less() );
504 xp = rSet.extract_with( arrData[i], key_less() );
513 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
522 void do_test( size_t nLoadFactor )
524 Set testSet( c_nSetSize, nLoadFactor );
525 do_test_with( testSet );
530 void do_test_extract( size_t nLoadFactor )
532 Set testSet( c_nSetSize, nLoadFactor );
533 do_test_extract_with( testSet );
538 void do_test_with( Set& testSet )
540 typedef InsertThread<Set> insert_thread;
541 typedef DeleteThread<Set> delete_thread;
543 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
545 CppUnitMini::ThreadPool pool( *this );
546 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
547 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
549 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
551 size_t nInsertSuccess = 0;
552 size_t nInsertFailed = 0;
553 size_t nDeleteSuccess = 0;
554 size_t nDeleteFailed = 0;
555 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
556 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
558 nInsertSuccess += pThread->m_nInsertSuccess;
559 nInsertFailed += pThread->m_nInsertFailed;
562 delete_thread * p = static_cast<delete_thread *>( *it );
563 nDeleteSuccess += p->m_nDeleteSuccess;
564 nDeleteFailed += p->m_nDeleteFailed;
568 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
569 CPPUNIT_CHECK( nInsertFailed == 0 );
571 CPPUNIT_MSG( " Totals (success/failed): \n\t"
572 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
573 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
578 void do_test_extract_with( Set& testSet )
580 typedef InsertThread<Set> insert_thread;
581 typedef DeleteThread<Set> delete_thread;
582 typedef ExtractThread< typename Set::gc, Set > extract_thread;
584 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
586 CppUnitMini::ThreadPool pool( *this );
587 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
588 if ( c_nDelThreadCount )
589 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount );
590 if ( c_nExtractThreadCount )
591 pool.add( new extract_thread( pool, testSet ), c_nExtractThreadCount );
593 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
595 size_t nInsertSuccess = 0;
596 size_t nInsertFailed = 0;
597 size_t nDeleteSuccess = 0;
598 size_t nDeleteFailed = 0;
599 size_t nExtractSuccess = 0;
600 size_t nExtractFailed = 0;
601 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
602 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
604 nInsertSuccess += pThread->m_nInsertSuccess;
605 nInsertFailed += pThread->m_nInsertFailed;
608 delete_thread * p = dynamic_cast<delete_thread *>( *it );
610 nDeleteSuccess += p->m_nDeleteSuccess;
611 nDeleteFailed += p->m_nDeleteFailed;
614 extract_thread * pExt = dynamic_cast<extract_thread *>( *it );
616 nExtractSuccess += pExt->m_nExtractSuccess;
617 nExtractFailed += pExt->m_nExtractFailed;
622 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
623 CPPUNIT_CHECK( nInsertFailed == 0 );
625 CPPUNIT_MSG( " Totals (success/failed): \n\t"
626 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
627 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
628 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
632 template <typename Set>
633 void analyze( Set& testSet )
635 // All even keys must be in the set
637 CPPUNIT_MSG( " Check even keys..." );
638 size_t nErrorCount = 0;
639 for ( size_t n = 0; n < c_nSetSize; n +=2 ) {
640 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
641 if ( !testSet.find( key_type(n, i) ) ) {
642 if ( ++nErrorCount < 10 ) {
643 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
648 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
651 check_before_clear( testSet );
653 CPPUNIT_MSG( " Clear map (single-threaded)..." );
654 cds::OS::Timer timer;
656 CPPUNIT_MSG( " Duration=" << timer.duration() );
657 CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) );
659 additional_check( testSet );
660 print_stat( testSet );
661 additional_cleanup( testSet );
667 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
668 << " delete thread count=" << c_nDelThreadCount
669 << " set size=" << c_nSetSize
672 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
673 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
674 do_test<Set>( nLoadFactor );
675 if ( c_bPrintGCState )
683 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
684 << " delete thread count=" << c_nDelThreadCount
685 << " extract thread count=" << c_nExtractThreadCount
686 << " set size=" << c_nSetSize
689 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
690 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
691 do_test_extract<Set>( nLoadFactor );
692 if ( c_bPrintGCState )
700 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
701 << " delete thread count=" << c_nDelThreadCount
702 << " set size=" << c_nSetSize
711 if ( c_bPrintGCState )
716 void test_nolf_extract()
718 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
719 << " delete thread count=" << c_nDelThreadCount
720 << " extract thread count=" << c_nExtractThreadCount
721 << " set size=" << c_nSetSize
726 do_test_extract_with( s );
730 if ( c_bPrintGCState )
734 void setUpParams( const CppUnitMini::TestCfg& cfg );
736 void run_MichaelSet(const char *in_name, bool invert = false);
737 void run_SplitList(const char *in_name, bool invert = false);
738 void run_CuckooSet(const char *in_name, bool invert = false);
739 void run_SkipListSet(const char *in_name, bool invert = false);
740 void run_EllenBinTreeSet(const char *in_name, bool invert = false);
742 virtual void myRun(const char *in_name, bool invert = false);
745 # include "set2/set_defs.h"
746 CDSUNIT_DECLARE_MichaelSet
747 CDSUNIT_DECLARE_SplitList
748 CDSUNIT_DECLARE_CuckooSet
749 CDSUNIT_DECLARE_SkipListSet
750 CDSUNIT_DECLARE_EllenBinTreeSet