3 #include "cppunit/thread.h"
4 #include "map2/map_type.h"
5 #include <cds/os/topology.h>
9 # define TEST_CASE(TAG, X) void X();
17 key_thread( size_t key, size_t threadNo )
28 struct cmp<key_thread> {
29 int operator ()(key_thread const& k1, key_thread const& k2) const
31 if ( k1.nKey < k2.nKey )
33 if ( k1.nKey > k2.nKey )
35 if ( k1.nThread < k2.nThread )
37 if ( k1.nThread > k2.nThread )
41 int operator ()(key_thread const& k1, size_t k2) const
49 int operator ()(size_t k1, key_thread const& k2) const
63 struct less<map2::key_thread>
65 bool operator()(map2::key_thread const& k1, map2::key_thread const& k2) const
67 if ( k1.nKey <= k2.nKey )
68 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
74 struct hash<map2::key_thread>
76 typedef size_t result_type;
77 typedef map2::key_thread argument_type;
79 size_t operator()( map2::key_thread const& k ) const
81 return std::hash<size_t>()(k.nKey);
83 size_t operator()( size_t k ) const
85 return std::hash<size_t>()(k);
91 inline size_t hash_value( map2::key_thread const& k )
93 return std::hash<size_t>()( k.nKey );
97 struct hash<map2::key_thread>
99 typedef size_t result_type;
100 typedef map2::key_thread argument_type;
102 size_t operator()(map2::key_thread const& k) const
104 return boost::hash<size_t>()( k.nKey );
106 size_t operator()(size_t k) const
108 return boost::hash<size_t>()( k );
115 class Map_DelOdd: public CppUnitMini::TestCase
118 size_t c_nInsThreadCount = 4; // insert thread count
119 size_t c_nDelThreadCount = 4; // delete thread count
120 size_t c_nExtractThreadCount = 4; // extract thread count
121 size_t c_nMapSize = 1000000; // max map size
122 size_t c_nMaxLoadFactor = 8; // maximum load factor
123 size_t c_nMultiLevelMap_HeadBits = 10; // for MultiLevelHashMap - log2(size of head array)
124 size_t c_nMultiLevelMap_ArrayBits = 8; // for MultiLevelHashMap - log2(size of array node)
126 bool c_bPrintGCState = true;
128 size_t c_nLoadFactor; // current load factor
131 std::vector<size_t> m_arrInsert;
132 std::vector<size_t> m_arrRemove;
135 typedef CppUnitMini::TestCase Base;
137 typedef key_thread key_type;
138 typedef size_t value_type;
139 typedef std::pair<key_type const, value_type> pair_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 );
156 template <typename Q>
157 void operator()( bool /*bNew*/, Q const& )
159 template <typename Q, typename V>
160 void operator()( bool /*bNew*/, Q const&, V& )
164 template <typename Q>
165 void operator()( Q&, Q*)
169 size_t m_nInsertSuccess;
170 size_t m_nInsertFailed;
173 InsertThread( CppUnitMini::ThreadPool& pool, Map& rMap )
174 : CppUnitMini::TestThread( pool )
177 InsertThread( InsertThread& src )
178 : CppUnitMini::TestThread( src )
182 Map_DelOdd& getTest()
184 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
187 virtual void init() { cds::threading::Manager::attachThread() ; }
188 virtual void fini() { cds::threading::Manager::detachThread() ; }
197 std::vector<size_t>& arrData = getTest().m_arrInsert;
198 for ( size_t i = 0; i < arrData.size(); ++i ) {
199 if ( rMap.insert( key_type( arrData[i], m_nThreadNo )))
206 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
207 if ( arrData[i] & 1 ) {
208 rMap.update( key_type( arrData[i], m_nThreadNo ), f );
212 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
217 bool operator()( key_type const& k1, key_type const& k2 ) const
219 return k1.nKey == k2.nKey;
221 bool operator()( size_t k1, key_type const& k2 ) const
223 return k1 == k2.nKey;
225 bool operator()( key_type const& k1, size_t k2 ) const
227 return k1.nKey == k2;
232 bool operator()( key_type const& k1, key_type const& k2 ) const
234 return k1.nKey < k2.nKey;
236 bool operator()( size_t k1, key_type const& k2 ) const
240 bool operator()( key_type const& k1, size_t k2 ) const
245 typedef key_equal equal_to;
248 // Deletes odd keys from [0..N)
250 class DeleteThread: public CppUnitMini::TestThread
254 virtual DeleteThread * clone()
256 return new DeleteThread( *this );
259 size_t m_nDeleteSuccess;
260 size_t m_nDeleteFailed;
263 DeleteThread( CppUnitMini::ThreadPool& pool, Map& rMap )
264 : CppUnitMini::TestThread( pool )
267 DeleteThread( DeleteThread& src )
268 : CppUnitMini::TestThread( src )
272 Map_DelOdd& getTest()
274 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
277 virtual void init() { cds::threading::Manager::attachThread() ; }
278 virtual void fini() { cds::threading::Manager::detachThread() ; }
287 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
289 for ( size_t pass = 0; pass < 2; pass++ ) {
290 std::vector<size_t>& arrData = getTest().m_arrRemove;
291 if ( m_nThreadNo & 1 ) {
292 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
293 for ( size_t i = 0; i < arrData.size(); ++i ) {
294 if ( arrData[i] & 1 ) {
295 if ( rMap.erase_with( arrData[i], key_less() ))
301 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
306 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
307 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
308 if ( arrData[i] & 1 ) {
309 if ( rMap.erase_with( arrData[i], key_less() ))
315 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
323 // Deletes odd keys from [0..N)
324 template <class GC, class Map >
325 class ExtractThread: public CppUnitMini::TestThread
329 virtual ExtractThread * clone()
331 return new ExtractThread( *this );
334 size_t m_nDeleteSuccess;
335 size_t m_nDeleteFailed;
338 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
339 : CppUnitMini::TestThread( pool )
342 ExtractThread( ExtractThread& src )
343 : CppUnitMini::TestThread( src )
347 Map_DelOdd& getTest()
349 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
352 virtual void init() { cds::threading::Manager::attachThread() ; }
353 virtual void fini() { cds::threading::Manager::detachThread() ; }
362 typename Map::guarded_ptr gp;
363 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
365 for ( size_t pass = 0; pass < 2; ++pass ) {
366 std::vector<size_t>& arrData = getTest().m_arrRemove;
367 if ( m_nThreadNo & 1 ) {
368 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
369 for ( size_t i = 0; i < arrData.size(); ++i ) {
370 if ( arrData[i] & 1 ) {
371 gp = rMap.extract_with( arrData[i], key_less());
379 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
384 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
385 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
386 if ( arrData[i] & 1 ) {
387 gp = rMap.extract_with( arrData[i], key_less());
395 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
403 template <class RCU, class Map >
404 class ExtractThread< cds::urcu::gc<RCU>, Map > : public CppUnitMini::TestThread
408 virtual ExtractThread * clone()
410 return new ExtractThread( *this );
413 size_t m_nDeleteSuccess;
414 size_t m_nDeleteFailed;
417 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
418 : CppUnitMini::TestThread( pool )
421 ExtractThread( ExtractThread& src )
422 : CppUnitMini::TestThread( src )
426 Map_DelOdd& getTest()
428 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
431 virtual void init() { cds::threading::Manager::attachThread() ; }
432 virtual void fini() { cds::threading::Manager::detachThread() ; }
441 typename Map::exempt_ptr xp;
442 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
444 std::vector<size_t>& arrData = getTest().m_arrRemove;
445 if ( m_nThreadNo & 1 ) {
446 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
447 for ( size_t i = 0; i < arrData.size(); ++i ) {
448 if ( arrData[i] & 1 ) {
449 if ( Map::c_bExtractLockExternal ) {
451 typename Map::rcu_lock l;
452 xp = rMap.extract_with( arrData[i], key_less() );
460 xp = rMap.extract_with( arrData[i], key_less() );
469 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
474 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
475 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
476 if ( arrData[i] & 1 ) {
477 if ( Map::c_bExtractLockExternal ) {
479 typename Map::rcu_lock l;
480 xp = rMap.extract_with( arrData[i], key_less() );
488 xp = rMap.extract_with( arrData[i], key_less() );
497 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
508 Map testMap( *this );
509 do_test_with( testMap );
513 void do_test_extract()
515 Map testMap( *this );
516 do_test_extract_with( testMap );
520 void do_test_with( Map& testMap )
522 typedef InsertThread<Map> insert_thread;
523 typedef DeleteThread<Map> delete_thread;
525 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
527 CppUnitMini::ThreadPool pool( *this );
528 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
529 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
531 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
533 size_t nInsertSuccess = 0;
534 size_t nInsertFailed = 0;
535 size_t nDeleteSuccess = 0;
536 size_t nDeleteFailed = 0;
537 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
538 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
540 nInsertSuccess += pThread->m_nInsertSuccess;
541 nInsertFailed += pThread->m_nInsertFailed;
544 delete_thread * p = static_cast<delete_thread *>( *it );
545 nDeleteSuccess += p->m_nDeleteSuccess;
546 nDeleteFailed += p->m_nDeleteFailed;
550 CPPUNIT_MSG( " Totals (success/failed): \n\t"
551 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
552 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
554 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
555 CPPUNIT_CHECK( nInsertFailed == 0 );
561 void do_test_extract_with( Map& testMap )
563 typedef InsertThread<Map> insert_thread;
564 typedef DeleteThread<Map> delete_thread;
565 typedef ExtractThread< typename Map::gc, Map > extract_thread;
567 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
569 CppUnitMini::ThreadPool pool( *this );
570 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
571 if ( c_nDelThreadCount )
572 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount );
573 if ( c_nExtractThreadCount )
574 pool.add( new extract_thread( pool, testMap ), c_nExtractThreadCount );
576 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
578 size_t nInsertSuccess = 0;
579 size_t nInsertFailed = 0;
580 size_t nDeleteSuccess = 0;
581 size_t nDeleteFailed = 0;
582 size_t nExtractSuccess = 0;
583 size_t nExtractFailed = 0;
584 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
585 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
587 nInsertSuccess += pThread->m_nInsertSuccess;
588 nInsertFailed += pThread->m_nInsertFailed;
591 delete_thread * p = dynamic_cast<delete_thread *>( *it );
593 nDeleteSuccess += p->m_nDeleteSuccess;
594 nDeleteFailed += p->m_nDeleteFailed;
597 extract_thread * pExtract = dynamic_cast<extract_thread *>( *it );
599 nExtractSuccess += pExtract->m_nDeleteSuccess;
600 nExtractFailed += pExtract->m_nDeleteFailed;
605 CPPUNIT_MSG( " Totals (success/failed): \n\t"
606 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
607 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
608 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
610 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
611 CPPUNIT_CHECK( nInsertFailed == 0 );
617 void analyze( Map& testMap )
619 cds::OS::Timer timer;
621 // All even keys must be in the map
623 size_t nErrorCount = 0;
624 CPPUNIT_MSG( " Check even keys..." );
625 for ( size_t n = 0; n < c_nMapSize; n +=2 ) {
626 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
627 if ( !testMap.contains( key_type(n, i) ) ) {
628 if ( ++nErrorCount < 10 ) {
629 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
634 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
637 check_before_cleanup( testMap );
639 CPPUNIT_MSG( " Clear map (single-threaded)..." );
642 CPPUNIT_MSG( " Duration=" << timer.duration() );
643 CPPUNIT_CHECK_EX( testMap.empty(), ((long long) testMap.size()) );
645 additional_check( testMap );
646 print_stat( testMap );
648 additional_cleanup( testMap );
654 if ( Map::c_bExtractSupported ) {
655 CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
656 << ", delete=" << c_nDelThreadCount
657 << ", extract=" << c_nExtractThreadCount
658 << "; set size=" << c_nMapSize
660 if ( Map::c_bLoadFactorDepended ) {
661 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
662 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
663 do_test_extract<Map>();
664 if ( c_bPrintGCState )
669 do_test_extract<Map>();
672 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
673 << " delete thread count=" << c_nDelThreadCount
674 << " set size=" << c_nMapSize
676 if ( Map::c_bLoadFactorDepended ) {
677 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
678 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
680 if ( c_bPrintGCState )
689 void setUpParams( const CppUnitMini::TestCfg& cfg );
691 # include "map2/map_defs.h"
692 CDSUNIT_DECLARE_MichaelMap
694 // This test is not suitable for MultiLevelHashMap
695 //CDSUNIT_DECLARE_MultiLevelHashMap
697 CPPUNIT_TEST_SUITE(Map_DelOdd)
698 CDSUNIT_TEST_MichaelMap
699 //CDSUNIT_TEST_MultiLevelHashMap // the test is not suitable
700 CPPUNIT_TEST_SUITE_END();
702 //CDSUNIT_DECLARE_MichaelMap
703 //CDSUNIT_DECLARE_SplitList
704 ////CDSUNIT_DECLARE_StripedMap
705 ////CDSUNIT_DECLARE_RefinableMap
706 //CDSUNIT_DECLARE_CuckooMap
707 //CDSUNIT_DECLARE_SkipListMap
708 //CDSUNIT_DECLARE_EllenBinTreeMap
709 //CDSUNIT_DECLARE_BronsonAVLTreeMap
710 //CDSUNIT_DECLARE_MultiLevelHashMap
711 ////CDSUNIT_DECLARE_StdMap