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_nCuckooInitialSize = 1024;// initial size for CuckooMap
124 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
125 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (0 - use default)
127 bool c_bPrintGCState = true;
129 size_t c_nLoadFactor; // current load factor
132 std::vector<size_t> m_arrInsert;
133 std::vector<size_t> m_arrRemove;
136 typedef key_thread key_type;
137 typedef size_t value_type;
138 typedef std::pair<key_type const, value_type> pair_type;
140 atomics::atomic<size_t> m_nInsThreadCount;
142 // Inserts keys from [0..N)
144 class InsertThread: public CppUnitMini::TestThread
148 virtual InsertThread * clone()
150 return new InsertThread( *this );
155 template <typename Q>
156 void operator()( bool /*bNew*/, Q const& )
158 template <typename Q, typename V>
159 void operator()( bool /*bNew*/, Q const&, V& )
163 template <typename Q>
164 void operator()( Q&, Q*)
168 size_t m_nInsertSuccess;
169 size_t m_nInsertFailed;
172 InsertThread( CppUnitMini::ThreadPool& pool, Map& rMap )
173 : CppUnitMini::TestThread( pool )
176 InsertThread( InsertThread& src )
177 : CppUnitMini::TestThread( src )
181 Map_DelOdd& getTest()
183 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
186 virtual void init() { cds::threading::Manager::attachThread() ; }
187 virtual void fini() { cds::threading::Manager::detachThread() ; }
196 std::vector<size_t>& arrData = getTest().m_arrInsert;
197 for ( size_t i = 0; i < arrData.size(); ++i ) {
198 if ( rMap.insert( key_type( arrData[i], m_nThreadNo )))
205 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
206 if ( arrData[i] & 1 ) {
207 rMap.update( key_type( arrData[i], m_nThreadNo ), f );
211 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
216 bool operator()( key_type const& k1, key_type const& k2 ) const
218 return k1.nKey == k2.nKey;
220 bool operator()( size_t k1, key_type const& k2 ) const
222 return k1 == k2.nKey;
224 bool operator()( key_type const& k1, size_t k2 ) const
226 return k1.nKey == k2;
231 bool operator()( key_type const& k1, key_type const& k2 ) const
233 return k1.nKey < k2.nKey;
235 bool operator()( size_t k1, key_type const& k2 ) const
239 bool operator()( key_type const& k1, size_t k2 ) const
244 typedef key_equal equal_to;
247 // Deletes odd keys from [0..N)
249 class DeleteThread: public CppUnitMini::TestThread
253 virtual DeleteThread * clone()
255 return new DeleteThread( *this );
258 size_t m_nDeleteSuccess;
259 size_t m_nDeleteFailed;
262 DeleteThread( CppUnitMini::ThreadPool& pool, Map& rMap )
263 : CppUnitMini::TestThread( pool )
266 DeleteThread( DeleteThread& src )
267 : CppUnitMini::TestThread( src )
271 Map_DelOdd& getTest()
273 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
276 virtual void init() { cds::threading::Manager::attachThread() ; }
277 virtual void fini() { cds::threading::Manager::detachThread() ; }
286 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
288 for ( size_t pass = 0; pass < 2; pass++ ) {
289 std::vector<size_t>& arrData = getTest().m_arrRemove;
290 if ( m_nThreadNo & 1 ) {
291 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
292 for ( size_t i = 0; i < arrData.size(); ++i ) {
293 if ( arrData[i] & 1 ) {
294 if ( rMap.erase_with( arrData[i], key_less() ))
300 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
305 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
306 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
307 if ( arrData[i] & 1 ) {
308 if ( rMap.erase_with( arrData[i], key_less() ))
314 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
322 // Deletes odd keys from [0..N)
323 template <class GC, class Map >
324 class ExtractThread: public CppUnitMini::TestThread
328 virtual ExtractThread * clone()
330 return new ExtractThread( *this );
333 size_t m_nDeleteSuccess;
334 size_t m_nDeleteFailed;
337 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
338 : CppUnitMini::TestThread( pool )
341 ExtractThread( ExtractThread& src )
342 : CppUnitMini::TestThread( src )
346 Map_DelOdd& getTest()
348 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
351 virtual void init() { cds::threading::Manager::attachThread() ; }
352 virtual void fini() { cds::threading::Manager::detachThread() ; }
361 typename Map::guarded_ptr gp;
362 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
364 for ( size_t pass = 0; pass < 2; ++pass ) {
365 std::vector<size_t>& arrData = getTest().m_arrRemove;
366 if ( m_nThreadNo & 1 ) {
367 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
368 for ( size_t i = 0; i < arrData.size(); ++i ) {
369 if ( arrData[i] & 1 ) {
370 gp = rMap.extract_with( arrData[i], key_less());
378 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
383 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
384 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
385 if ( arrData[i] & 1 ) {
386 gp = rMap.extract_with( arrData[i], key_less());
394 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
402 template <class RCU, class Map >
403 class ExtractThread< cds::urcu::gc<RCU>, Map > : public CppUnitMini::TestThread
407 virtual ExtractThread * clone()
409 return new ExtractThread( *this );
412 size_t m_nDeleteSuccess;
413 size_t m_nDeleteFailed;
416 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
417 : CppUnitMini::TestThread( pool )
420 ExtractThread( ExtractThread& src )
421 : CppUnitMini::TestThread( src )
425 Map_DelOdd& getTest()
427 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
430 virtual void init() { cds::threading::Manager::attachThread() ; }
431 virtual void fini() { cds::threading::Manager::detachThread() ; }
440 typename Map::exempt_ptr xp;
441 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
443 std::vector<size_t>& arrData = getTest().m_arrRemove;
444 if ( m_nThreadNo & 1 ) {
445 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
446 for ( size_t i = 0; i < arrData.size(); ++i ) {
447 if ( arrData[i] & 1 ) {
448 if ( Map::c_bExtractLockExternal ) {
450 typename Map::rcu_lock l;
451 xp = rMap.extract_with( arrData[i], key_less() );
459 xp = rMap.extract_with( arrData[i], key_less() );
468 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
473 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
474 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
475 if ( arrData[i] & 1 ) {
476 if ( Map::c_bExtractLockExternal ) {
478 typename Map::rcu_lock l;
479 xp = rMap.extract_with( arrData[i], key_less() );
487 xp = rMap.extract_with( arrData[i], key_less() );
496 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
507 Map testMap( *this );
508 do_test_with( testMap );
512 void do_test_extract()
514 Map testMap( *this );
515 do_test_extract_with( testMap );
519 void do_test_with( Map& testMap )
521 typedef InsertThread<Map> insert_thread;
522 typedef DeleteThread<Map> delete_thread;
524 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
526 CppUnitMini::ThreadPool pool( *this );
527 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
528 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
530 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
532 size_t nInsertSuccess = 0;
533 size_t nInsertFailed = 0;
534 size_t nDeleteSuccess = 0;
535 size_t nDeleteFailed = 0;
536 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
537 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
539 nInsertSuccess += pThread->m_nInsertSuccess;
540 nInsertFailed += pThread->m_nInsertFailed;
543 delete_thread * p = static_cast<delete_thread *>( *it );
544 nDeleteSuccess += p->m_nDeleteSuccess;
545 nDeleteFailed += p->m_nDeleteFailed;
549 CPPUNIT_MSG( " Totals (success/failed): \n\t"
550 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
551 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
553 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
554 CPPUNIT_CHECK( nInsertFailed == 0 );
560 void do_test_extract_with( Map& testMap )
562 typedef InsertThread<Map> insert_thread;
563 typedef DeleteThread<Map> delete_thread;
564 typedef ExtractThread< typename Map::gc, Map > extract_thread;
566 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
568 CppUnitMini::ThreadPool pool( *this );
569 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
570 if ( c_nDelThreadCount )
571 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount );
572 if ( c_nExtractThreadCount )
573 pool.add( new extract_thread( pool, testMap ), c_nExtractThreadCount );
575 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
577 size_t nInsertSuccess = 0;
578 size_t nInsertFailed = 0;
579 size_t nDeleteSuccess = 0;
580 size_t nDeleteFailed = 0;
581 size_t nExtractSuccess = 0;
582 size_t nExtractFailed = 0;
583 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
584 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
586 nInsertSuccess += pThread->m_nInsertSuccess;
587 nInsertFailed += pThread->m_nInsertFailed;
590 delete_thread * p = dynamic_cast<delete_thread *>( *it );
592 nDeleteSuccess += p->m_nDeleteSuccess;
593 nDeleteFailed += p->m_nDeleteFailed;
596 extract_thread * pExtract = dynamic_cast<extract_thread *>( *it );
598 nExtractSuccess += pExtract->m_nDeleteSuccess;
599 nExtractFailed += pExtract->m_nDeleteFailed;
604 CPPUNIT_MSG( " Totals (success/failed): \n\t"
605 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
606 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
607 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
609 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
610 CPPUNIT_CHECK( nInsertFailed == 0 );
616 void analyze( Map& testMap )
618 cds::OS::Timer timer;
620 // All even keys must be in the map
622 size_t nErrorCount = 0;
623 CPPUNIT_MSG( " Check even keys..." );
624 for ( size_t n = 0; n < c_nMapSize; n +=2 ) {
625 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
626 if ( !testMap.contains( key_type(n, i) ) ) {
627 if ( ++nErrorCount < 10 ) {
628 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
633 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
636 check_before_cleanup( testMap );
638 CPPUNIT_MSG( " Clear map (single-threaded)..." );
641 CPPUNIT_MSG( " Duration=" << timer.duration() );
642 CPPUNIT_CHECK_EX( testMap.empty(), ((long long) testMap.size()) );
644 additional_check( testMap );
645 print_stat( testMap );
647 additional_cleanup( testMap );
653 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
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>();
673 void run_test_no_extract()
675 static_assert( !Map::c_bExtractSupported, "Map class must not support extract() method" );
677 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
678 << " delete thread count=" << c_nDelThreadCount
679 << " set size=" << c_nMapSize
681 if ( Map::c_bLoadFactorDepended ) {
682 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
683 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
685 if ( c_bPrintGCState )
693 void setUpParams( const CppUnitMini::TestCfg& cfg );
695 # include "map2/map_defs.h"
696 CDSUNIT_DECLARE_MichaelMap
697 CDSUNIT_DECLARE_SplitList
698 CDSUNIT_DECLARE_SkipListMap
699 CDSUNIT_DECLARE_EllenBinTreeMap
700 CDSUNIT_DECLARE_BronsonAVLTreeMap
701 CDSUNIT_DECLARE_CuckooMap
703 // This test is not suitable for MultiLevelHashMap
704 //CDSUNIT_DECLARE_MultiLevelHashMap
706 CPPUNIT_TEST_SUITE(Map_DelOdd)
707 CDSUNIT_TEST_MichaelMap
708 CDSUNIT_TEST_SplitList
709 CDSUNIT_TEST_SkipListMap
710 CDSUNIT_TEST_EllenBinTreeMap
711 CDSUNIT_TEST_BronsonAVLTreeMap
712 CDSUNIT_TEST_CuckooMap
714 //CDSUNIT_TEST_MultiLevelHashMap // the test is not suitable
715 CPPUNIT_TEST_SUITE_END();
717 // Not implemented yet
718 ////CDSUNIT_DECLARE_StripedMap
719 ////CDSUNIT_DECLARE_RefinableMap
720 ////CDSUNIT_DECLARE_StdMap