3 #include "map2/map_type.h"
4 #include "cppunit/thread.h"
10 #define TEST_CASE(TAG, X) void X();
12 class Map_InsDel_Item_int: public CppUnitMini::TestCase
15 size_t c_nMapSize = 1000000; // map size
16 size_t c_nThreadCount = 4; // thread count
17 size_t c_nAttemptCount = 100000; // count of SUCCESS insert/delete for each thread
18 size_t c_nMaxLoadFactor = 8; // maximum load factor
19 bool c_bPrintGCState = true;
21 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
22 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
23 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
25 size_t c_nMultiLevelMap_HeadBits = 10;
26 size_t c_nMultiLevelMap_ArrayBits = 4;
29 size_t c_nLoadFactor = 2; // current load factor
32 typedef CppUnitMini::TestCase Base;
33 typedef size_t key_type;
34 typedef size_t value_type;
37 class Inserter: public CppUnitMini::TestThread
41 virtual Inserter * clone()
43 return new Inserter( *this );
48 void operator()( bool bNew, std::pair<key_type const, value_type>& item )
51 item.second = item.first;
53 // for boost::container::flat_map
54 void operator()( bool bNew, std::pair<key_type, value_type>& item )
57 item.second = item.first;
60 // for BronsonAVLTreeMap
61 void operator()( bool bNew, key_type key, value_type& val )
67 // for MultiLevelHashMap
68 void operator()( std::pair<key_type const, value_type>& item, std::pair<key_type const, value_type> * pOld )
71 item.second = item.first;
76 size_t m_nInsertSuccess;
77 size_t m_nInsertFailed;
80 Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
81 : CppUnitMini::TestThread( pool )
84 Inserter( Inserter& src )
85 : CppUnitMini::TestThread( src )
89 Map_InsDel_Item_int& getTest()
91 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
94 virtual void init() { cds::threading::Manager::attachThread() ; }
95 virtual void fini() { cds::threading::Manager::detachThread() ; }
104 size_t nGoalItem = getTest().c_nGoalItem;
105 size_t const nAttemptCount = getTest().c_nAttemptCount;
107 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
108 if ( nAttempt % 2 == 0 ) {
109 if ( rMap.insert( nGoalItem, nGoalItem )) {
117 std::pair<bool, bool> updateResult = rMap.update( nGoalItem, update_func(), true );
118 if ( updateResult.second ) {
130 class Deleter: public CppUnitMini::TestThread
134 virtual Deleter * clone()
136 return new Deleter( *this );
139 size_t m_nDeleteSuccess;
140 size_t m_nDeleteFailed;
143 Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
144 : CppUnitMini::TestThread( pool )
147 Deleter( Deleter& src )
148 : CppUnitMini::TestThread( src )
152 Map_InsDel_Item_int& getTest()
154 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
157 virtual void init() { cds::threading::Manager::attachThread() ; }
158 virtual void fini() { cds::threading::Manager::detachThread() ; }
167 size_t nGoalItem = getTest().c_nGoalItem;
168 size_t const nAttemptCount = getTest().c_nAttemptCount;
169 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
170 if ( rMap.erase( nGoalItem )) {
183 void do_test( Map& testMap )
185 typedef Inserter<Map> InserterThread;
186 typedef Deleter<Map> DeleterThread;
187 cds::OS::Timer timer;
190 CPPUNIT_MSG( " Fill map (" << c_nMapSize << " items)...");
193 std::vector<key_type> v;
194 v.reserve( c_nMapSize );
195 for ( size_t i = 0; i < c_nMapSize; ++i )
197 shuffle( v.begin(), v.end() );
198 for ( size_t i = 0; i < v.size(); ++i ) {
199 CPPUNIT_ASSERT( testMap.insert( v[i], v[i] ));
202 CPPUNIT_MSG( " Duration=" << timer.duration() );
204 CPPUNIT_MSG( " Insert/delete the key " << c_nGoalItem << " (" << c_nAttemptCount << " successful times)...");
205 CppUnitMini::ThreadPool pool( *this );
206 pool.add( new InserterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
207 pool.add( new DeleterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
209 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
211 size_t nInsertSuccess = 0;
212 size_t nInsertFailed = 0;
213 size_t nDeleteSuccess = 0;
214 size_t nDeleteFailed = 0;
215 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
216 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
218 CPPUNIT_CHECK( pThread->m_nInsertSuccess == c_nAttemptCount );
219 nInsertSuccess += pThread->m_nInsertSuccess;
220 nInsertFailed += pThread->m_nInsertFailed;
223 DeleterThread * p = static_cast<DeleterThread *>( *it );
224 CPPUNIT_CHECK( p->m_nDeleteSuccess == c_nAttemptCount );
225 nDeleteSuccess += p->m_nDeleteSuccess;
226 nDeleteFailed += p->m_nDeleteFailed;
229 CPPUNIT_CHECK( nInsertSuccess == nDeleteSuccess );
230 size_t nGoalItem = c_nGoalItem;
231 CPPUNIT_CHECK( testMap.contains( nGoalItem ));
234 CPPUNIT_MSG( " Totals: Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed );
236 // Check if the map contains all items
237 CPPUNIT_MSG( " Check if the map contains all items" );
239 for ( size_t i = 0; i < c_nMapSize; ++i ) {
240 CPPUNIT_CHECK_EX( testMap.contains( i ), "key " << i );
242 CPPUNIT_MSG( " Duration=" << timer.duration() );
244 check_before_cleanup( testMap );
247 additional_check( testMap );
248 print_stat( testMap );
249 additional_cleanup( testMap );
255 if ( Map::c_bLoadFactorDepended ) {
256 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
257 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
258 Map testMap( *this );
260 if ( c_bPrintGCState )
265 Map testMap( *this );
266 do_test<Map>( testMap );
267 if ( c_bPrintGCState )
272 void setUpParams( const CppUnitMini::TestCfg& cfg );
274 # include "map2/map_defs.h"
275 CDSUNIT_DECLARE_MichaelMap
276 CDSUNIT_DECLARE_SplitList
277 CDSUNIT_DECLARE_SkipListMap
278 CDSUNIT_DECLARE_EllenBinTreeMap
279 CDSUNIT_DECLARE_BronsonAVLTreeMap
280 CDSUNIT_DECLARE_MultiLevelHashMap
281 CDSUNIT_DECLARE_StripedMap
282 CDSUNIT_DECLARE_RefinableMap
283 CDSUNIT_DECLARE_CuckooMap
284 // CDSUNIT_DECLARE_StdMap // very slow!!
286 CPPUNIT_TEST_SUITE(Map_InsDel_int)
287 CDSUNIT_TEST_MichaelMap
288 CDSUNIT_TEST_SplitList
289 CDSUNIT_TEST_SkipListMap
290 CDSUNIT_TEST_EllenBinTreeMap
291 CDSUNIT_TEST_BronsonAVLTreeMap
292 CDSUNIT_TEST_MultiLevelHashMap
293 CDSUNIT_TEST_CuckooMap
294 CDSUNIT_TEST_StripedMap
295 CDSUNIT_TEST_RefinableMap
296 // CDSUNIT_TEST_StdMap // very slow!!
297 CPPUNIT_TEST_SUITE_END();