3 #include "set2/set_types.h"
4 #include "cppunit/thread.h"
10 # define TEST_SET(X) void X() { test<SetTypes<key_type, value_type>::X >(); }
11 # define TEST_SET_EXTRACT(X) void X() { test_extract<SetTypes<key_type, value_type>::X >(); }
12 # define TEST_SET_NOLF(X) void X() { test_nolf<SetTypes<key_type, value_type>::X >(); }
13 # define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract<SetTypes<key_type, value_type>::X >(); }
15 class Set_InsDel_string: public CppUnitMini::TestCase
17 static size_t c_nMapSize; // set size
18 static size_t c_nInsertThreadCount; // count of insertion thread
19 static size_t c_nDeleteThreadCount; // count of deletion thread
20 static size_t c_nThreadPassCount; // pass count for each thread
21 static size_t c_nMaxLoadFactor; // maximum load factor
22 static bool c_bPrintGCState;
24 typedef CppUnitMini::TestCase Base;
25 typedef std::string key_type;
26 typedef size_t value_type;
28 const std::vector<std::string> * m_parrString;
31 class Inserter: public CppUnitMini::TestThread
34 typedef typename Set::value_type keyval_type;
36 virtual Inserter * clone()
38 return new Inserter( *this );
41 size_t m_nInsertSuccess;
42 size_t m_nInsertFailed;
45 Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
46 : CppUnitMini::TestThread( pool )
49 Inserter( Inserter& src )
50 : CppUnitMini::TestThread( src )
54 Set_InsDel_string& getTest()
56 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
59 virtual void init() { cds::threading::Manager::attachThread() ; }
60 virtual void fini() { cds::threading::Manager::detachThread() ; }
69 const std::vector<std::string>& arrString = *getTest().m_parrString;
70 size_t nArrSize = arrString.size();
72 if ( m_nThreadNo & 1 ) {
73 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
74 for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
75 if ( rSet.insert( keyval_type(arrString[nItem % nArrSize], nItem * 8) ) )
83 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
84 for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
85 if ( rSet.insert( keyval_type( arrString[nItem % nArrSize], nItem * 8) ) )
96 class Deleter: public CppUnitMini::TestThread
100 virtual Deleter * clone()
102 return new Deleter( *this );
105 size_t m_nDeleteSuccess;
106 size_t m_nDeleteFailed;
109 Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
110 : CppUnitMini::TestThread( pool )
113 Deleter( Deleter& src )
114 : CppUnitMini::TestThread( src )
118 Set_InsDel_string& getTest()
120 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
123 virtual void init() { cds::threading::Manager::attachThread() ; }
124 virtual void fini() { cds::threading::Manager::detachThread() ; }
133 const std::vector<std::string>& arrString = *getTest().m_parrString;
134 size_t nArrSize = arrString.size();
136 if ( m_nThreadNo & 1 ) {
137 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
138 for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
139 if ( rSet.erase( arrString[nItem % nArrSize] ) )
147 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
148 for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
149 if ( rSet.erase( arrString[nItem % nArrSize] ) )
159 template <typename GC, class Set>
160 class Extractor: public CppUnitMini::TestThread
164 virtual Extractor * clone()
166 return new Extractor( *this );
169 size_t m_nDeleteSuccess;
170 size_t m_nDeleteFailed;
173 Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
174 : CppUnitMini::TestThread( pool )
177 Extractor( Extractor& src )
178 : CppUnitMini::TestThread( src )
182 Set_InsDel_string& getTest()
184 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
187 virtual void init() { cds::threading::Manager::attachThread() ; }
188 virtual void fini() { cds::threading::Manager::detachThread() ; }
197 typename Set::guarded_ptr gp;
199 const std::vector<std::string>& arrString = *getTest().m_parrString;
200 size_t nArrSize = arrString.size();
202 if ( m_nThreadNo & 1 ) {
203 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
204 for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
205 gp = rSet.extract( arrString[nItem % nArrSize]);
215 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
216 for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
217 gp = rSet.extract( arrString[nItem % nArrSize]);
229 template <typename RCU, class Set>
230 class Extractor<cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
234 virtual Extractor * clone()
236 return new Extractor( *this );
239 size_t m_nDeleteSuccess;
240 size_t m_nDeleteFailed;
243 Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
244 : CppUnitMini::TestThread( pool )
247 Extractor( Extractor& src )
248 : CppUnitMini::TestThread( src )
252 Set_InsDel_string& getTest()
254 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
257 virtual void init() { cds::threading::Manager::attachThread() ; }
258 virtual void fini() { cds::threading::Manager::detachThread() ; }
267 typename Set::exempt_ptr xp;
269 const std::vector<std::string>& arrString = *getTest().m_parrString;
270 size_t nArrSize = arrString.size();
272 if ( m_nThreadNo & 1 ) {
273 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
274 for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
275 if ( Set::c_bExtractLockExternal ) {
277 typename Set::rcu_lock l;
278 xp = rSet.extract( arrString[nItem % nArrSize] );
286 xp = rSet.extract( arrString[nItem % nArrSize] );
297 for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
298 for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
299 if ( Set::c_bExtractLockExternal ) {
301 typename Set::rcu_lock l;
302 xp = rSet.extract( arrString[nItem % nArrSize] );
310 xp = rSet.extract( arrString[nItem % nArrSize] );
326 void do_test( size_t nLoadFactor )
328 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
330 Set testSet( c_nMapSize, nLoadFactor );
331 do_test_with( testSet );
335 void do_test_extract( size_t nLoadFactor )
337 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
339 Set testSet( c_nMapSize, nLoadFactor );
340 do_test_extract_with( testSet );
344 void do_test_with( Set& testSet )
346 typedef Inserter<Set> InserterThread;
347 typedef Deleter<Set> DeleterThread;
348 cds::OS::Timer timer;
350 CppUnitMini::ThreadPool pool( *this );
351 pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
352 pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
354 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
356 size_t nInsertSuccess = 0;
357 size_t nInsertFailed = 0;
358 size_t nDeleteSuccess = 0;
359 size_t nDeleteFailed = 0;
360 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
361 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
363 nInsertSuccess += pThread->m_nInsertSuccess;
364 nInsertFailed += pThread->m_nInsertFailed;
367 DeleterThread * p = static_cast<DeleterThread *>( *it );
368 nDeleteSuccess += p->m_nDeleteSuccess;
369 nDeleteFailed += p->m_nDeleteFailed;
373 CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess
374 << " Del succ=" << nDeleteSuccess << "\n"
375 << " : Ins fail=" << nInsertFailed
376 << " Del fail=" << nDeleteFailed
377 << " Set size=" << testSet.size()
381 CPPUNIT_MSG( " Clear set (single-threaded)..." );
383 for ( size_t i = 0; i < m_parrString->size(); ++i )
384 testSet.erase( (*m_parrString)[i] );
385 CPPUNIT_MSG( " Duration=" << timer.duration() );
386 CPPUNIT_ASSERT( testSet.empty() );
388 additional_check( testSet );
389 print_stat( testSet );
390 additional_cleanup( testSet );
394 void do_test_extract_with( Set& testSet )
396 typedef Inserter<Set> InserterThread;
397 typedef Deleter<Set> DeleterThread;
398 typedef Extractor<typename Set::gc, Set> ExtractThread;
400 size_t nDelThreadCount = c_nDeleteThreadCount / 2;
402 CppUnitMini::ThreadPool pool( *this );
403 pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
404 pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
405 pool.add( new ExtractThread( pool, testSet ), c_nDeleteThreadCount - nDelThreadCount );
407 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
409 size_t nInsertSuccess = 0;
410 size_t nInsertFailed = 0;
411 size_t nDeleteSuccess = 0;
412 size_t nDeleteFailed = 0;
413 size_t nExtractSuccess = 0;
414 size_t nExtractFailed = 0;
415 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
416 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
418 nInsertSuccess += pThread->m_nInsertSuccess;
419 nInsertFailed += pThread->m_nInsertFailed;
422 DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
424 nDeleteSuccess += p->m_nDeleteSuccess;
425 nDeleteFailed += p->m_nDeleteFailed;
428 ExtractThread * pExtract = dynamic_cast<ExtractThread *>( *it );
430 nExtractSuccess += pExtract->m_nDeleteSuccess;
431 nExtractFailed += pExtract->m_nDeleteFailed;
436 CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess
437 << " Del succ=" << nDeleteSuccess
438 << " Extract succ= " << nExtractSuccess << "\n"
439 << " : Ins fail=" << nInsertFailed
440 << " Del fail=" << nDeleteFailed
441 << " Extract fail=" << nExtractFailed
442 << " Set size=" << testSet.size()
446 CPPUNIT_MSG( " Clear set (single-threaded)..." );
447 cds::OS::Timer timer;
448 for ( size_t i = 0; i < m_parrString->size(); ++i )
449 testSet.erase( (*m_parrString)[i] );
450 CPPUNIT_MSG( " Duration=" << timer.duration() );
451 CPPUNIT_ASSERT( testSet.empty() );
453 additional_check( testSet );
454 print_stat( testSet );
455 additional_cleanup( testSet );
461 m_parrString = &CppUnitMini::TestCase::getTestStrings();
463 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
464 << " delete=" << c_nDeleteThreadCount
465 << " pass count=" << c_nThreadPassCount
466 << " set size=" << c_nMapSize
469 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
470 do_test<Set>( nLoadFactor );
471 if ( c_bPrintGCState )
479 m_parrString = &CppUnitMini::TestCase::getTestStrings();
481 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
482 << " delete=" << c_nDeleteThreadCount
483 << " pass count=" << c_nThreadPassCount
484 << " set size=" << c_nMapSize
487 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
488 do_test_extract<Set>( nLoadFactor );
489 if ( c_bPrintGCState )
497 m_parrString = &CppUnitMini::TestCase::getTestStrings();
499 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
500 << " delete=" << c_nDeleteThreadCount
501 << " pass count=" << c_nThreadPassCount
502 << " set size=" << c_nMapSize
507 if ( c_bPrintGCState )
512 void test_nolf_extract()
514 m_parrString = &CppUnitMini::TestCase::getTestStrings();
516 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
517 << " delete=" << c_nDeleteThreadCount
518 << " pass count=" << c_nThreadPassCount
519 << " set size=" << c_nMapSize
523 do_test_extract_with( s );
524 if ( c_bPrintGCState )
528 void setUpParams( const CppUnitMini::TestCfg& cfg );
530 void run_MichaelSet(const char *in_name, bool invert = false);
531 void run_SplitList(const char *in_name, bool invert = false);
532 void run_SkipListSet(const char *in_name, bool invert = false);
533 void run_CuckooSet(const char *in_name, bool invert = false);
534 void run_StripedSet(const char *in_name, bool invert = false);
535 void run_RefinableSet(const char *in_name, bool invert = false);
536 void run_EllenBinTreeSet(const char *in_name, bool invert = false);
537 void run_StdSet(const char *in_name, bool invert = false);
539 virtual void myRun(const char *in_name, bool invert = false);
542 # include "set2/set_defs.h"
543 CDSUNIT_DECLARE_MichaelSet
544 CDSUNIT_DECLARE_SplitList
545 CDSUNIT_DECLARE_StripedSet
546 CDSUNIT_DECLARE_RefinableSet
547 CDSUNIT_DECLARE_CuckooSet
548 CDSUNIT_DECLARE_SkipListSet
549 CDSUNIT_DECLARE_EllenBinTreeSet
550 CDSUNIT_DECLARE_StdSet